Tout est fonction : retour sur le cours SICP de David Beazley

(ezzeriesa.notion.site)

2 points par GN⁺ 2024-11-18 | 1 commentaires | Partager sur WhatsApp

Retour sur le cours SICP de David Beazley : une semaine d’expérience

Je partage ici mon expérience de participation au cours SICP de David Beazley à la fin de l’année 2022. Il existe de nombreuses ressources gratuites, mais le cours de Dave s’est révélé très efficace en choisissant des sujets précis et en les expliquant en profondeur.

Point de départ

Le cours SICP était donné en langage Scheme, et on y expliquait le modèle fondamental de substitution en implémentant un interpréteur Scheme simple en Python.

Bases du langage Scheme

Primitives : valeurs de base (par ex. des entiers)
Opérateurs : opérations de base comme +, -, *, /, utilisées en notation préfixée
define : définition de variables

> (define x 2)  
> (+ x 3) ; résultat : 5

if : conditionnelle
lambda : définition de fonctions anonymes

> ((lambda (x) (* x x)) 3) ; résultat : 9

Interpréteur Scheme en Python

Implémentation d’un interpréteur simple qui évalue du code Scheme en utilisant Python. Les opérations de base sont définies comme des fonctions Python.

definitions = {  
    "+": lambda x, y: x + y,  
    "*": lambda x, y: x * y,  
}

Exemple :

> evaluate(("+", 2, 3)) # résultat : 5

L’implémentation couvre aussi define, lambda et le traitement de la conditionnelle if.

Modèle de substitution (Substitution Model)

Le modèle de substitution est une manière simple d’interpréter un programme : on évalue le programme en remplaçant les variables par leurs valeurs. Mais ce modèle échoue dès qu’on introduit une affectation (assignment).

État (State)

L’affectation (assignment) est un bon exemple de situation où le modèle de substitution se brise. Par exemple, lorsqu’on modélise le solde d’un compte bancaire, on met à jour la variable avec set!.

(define balance 100)  
  
(define (withdraw amount)  
  (set! balance (- balance amount))  
  balance)

Dans ce cas, le modèle de substitution ne permet pas de distinguer l’état du solde avant et après l’opération.

Le modèle d’environnement (Environment) devient alors nécessaire. Les variables y sont définies dans un environnement, et chaque procédure possède son propre environnement.

Flux (Streams)

Les streams constituent une autre manière de modéliser l’état. Grâce à l’évaluation paresseuse (lazy evaluation), ils permettent aussi de modéliser des valeurs futures.

Boucle infinie et ordre d’évaluation

Différence d’ordre d’évaluation : la plupart des langages utilisent l’évaluation en ordre applicatif (applicative-order evaluation), qui évalue d’abord les arguments.

> (square (+ 1 2)) ; résultat : 9

Mais l’évaluation en ordre normal (normal-order evaluation) retarde l’évaluation des arguments jusqu’au moment où ils deviennent réellement nécessaires. Cela permet d’éviter certaines boucles infinies.

> (define (p) (p))  
> (define (test x y) (if (= x 0) 0 y))  
> (test 0 (p)) ; renvoie 0 en ordre normal, boucle infinie en ordre applicatif

Calcul lambda et numéraux de Church

L’encodage de Church permet de représenter les nombres comme des procédures. C’est un concept important de la programmation fonctionnelle.

(define (zero f) (lambda (x) x))  
(define (increment n) (lambda (f) (lambda (x) (f ((n f) x)))))

zero est une fonction qui renvoie simplement son argument (fonction identity).
increment applique un appel de fonction supplémentaire.

Exemple

> ((zero (lambda (x) (+ x 1))) 0) ; résultat : 0  
> (((increment zero) (lambda (x) (+ x 1))) 0) ; résultat : 1

Itération vs récursion

Scheme utilise la récursion plutôt que des boucles for pour effectuer les tâches répétitives.

Exemple de récursion : factorielle

(define (factorial n)  
  (if (= n 1)   
    1   
    (* n (factorial (- n 1)))))

Cet appel récursif peut consommer beaucoup de mémoire en utilisant la pile.

Optimisation des appels terminaux (Tail-call optimization)

Scheme réduit l’usage mémoire grâce à l’optimisation des appels terminaux, ce qui lui permet de fonctionner comme un processus itératif.

(define (factorial n)  
  (define (iter product counter)  
    (if (> counter n)  
        product  
        (iter (* product counter) (+ counter 1))))  
  (iter 1 1))

Conclusion

Le cours de David Beazley aborde en profondeur, à partir d’une sélection ciblée, les concepts majeurs de SICP. Il aide en particulier à mieux comprendre différents paradigmes de programmation, notamment la programmation fonctionnelle, le calcul lambda et l’ordre d’évaluation.

Citation de Knuth

Si vous n’étudiez que la théorie, cela signifie qu’il est temps de vous concentrer sur la pratique ; et si vous ne faites que de la pratique, cela signifie qu’il est temps de vous concentrer sur la théorie.

1 commentaires

GN⁺ 2024-11-18

Commentaires sur Hacker News

À titre d’avertissement, se plonger profondément dans SICP/Lisp/Scheme peut changer votre façon de penser la programmation, et ce genre de stimulation intellectuelle est toujours bienvenu.
Mais appliquer ces idées en bloc à une base de code orientée objet produit généralement l’effet inverse ou suscite la résistance de l’équipe.
Par exemple, après Lisp, on peut avoir envie de remplacer toutes les boucles for par des forEach, ou de tout transformer en chaînes map/reduce, mais si le langage n’embrasse pas pleinement la programmation fonctionnelle, cela peut nuire à la fois à la lisibilité et aux performances.
Au final, se rappeler que la mémoire mutable et le CPU exécutent le code aide à garder les pieds sur terre ; aujourd’hui, je trouve qu’au quotidien, la conception orientée données et l’« empathie mécanique » adaptée aux réalités du hardware sont plus pratiques que des abstractions comme les nombres de Church.
- Je considère que l’immuabilité est plus sûre.
  Moins il y a d’effets de bord, plus le comportement est prévisible, et l’orienté objet est souvent utilisé même là où de simples fonctions suffiraient.
  Dans le développement de jeux, avec beaucoup de calculs et de code à risque, l’orienté objet convient plutôt bien ; mais dans le développement web, la programmation fonctionnelle est bien plus naturelle, et dans le SaaS, des langages comme Elixir permettent d’écrire du code plus fiable, avec moins de bugs et plus facile à tester.
- Il y a aussi des choses comme le Common Lisp Object System, non ?
  En plus, des choses comme forEach et map/reduce existaient déjà dans les collections Smalltalk, et ont aussi été reprises dans Object Pascal et C++, même si ce n’était pas une syntaxe de première classe.
  Comme la mémoire sous-jacente est mutable, même les langages de la famille ML disposent de mécanismes pour gérer la mutation quand c’est vraiment nécessaire.
- Le seul moyen dont dispose un CPU pour implémenter le flux de contrôle ressemble à goto, mais goto est encore moins populaire que Lisp.
  Ce qui est encore plus étrange, c’est que sur les CPU modernes, les caches sont indispensables aux performances, et pourtant aucun langage ne traite encore la hiérarchie mémoire comme un citoyen de première classe.
  Ce qui s’en rapproche le plus semble être du C à la Linux, avec une mer de traits de soulignement.
Cela fournit une bonne introduction à l’encodage de l’état avec des fonctions pures.
En pratique, il existe beaucoup plus d’encodages purement fonctionnels pour toutes sortes de données : arbres, entiers, types somme/produit, images, monades, etc.
L’encodage peut être un peu déroutant, mais il est aussi élégant et compact.
Par exemple, en JavaScript, une implémentation fonctionnelle de la monade Maybe donne ceci :
Nothing = nothing => just => nothing
Just = v => nothing => just => just(v)
pure = Just
bind = mx => f => mx(mx)(f)
evalMaybe = maybe => maybe("Nothing")(v => "Just " + v)
console.log(evalMaybe(bind(Nothing)(n => pure(n + 1)))) // Nothing
console.log(evalMaybe(bind(Just(42))(n => pure(n + 1)))) // Just 43
- Ce genre d’implémentation peut se déduire du principe de récursion du type en question.
  data Maybe a = Nothing | Just a
  foldMaybe :: (Unit -> r) -> (a -> r) -> Maybe a -> r
  Les deux fonctions d’ordre supérieur passées à foldMaybe correspondent respectivement à Nothing et Just.
  Cela dit, du côté de Nothing, on ajoute un paramètre Unit pour être un peu plus précis.
- On peut voir cela comme la transformation d’un type inductif en type de sa fonction récursive.
  En théorie des types, c’est assez élégant, mais en programmation réelle, ce n’est pas franchement idéal.
- Mathématiquement, cela peut être élégant, mais quand c’est transmis au moyen d’un langage composé uniquement du jeu de caractères ASCII, sans mise en forme ni justification interne, c’est assez pénible à lire.
- En bref, le lambda-calcul non typé est Turing-complet.
J’avais déjà regardé le vrai cours SICP, c’est-à-dire les enregistrements de 1986 du MIT OCW.
On le félicite souvent pour sa forte densité d’information, mais en réalité pas mal de temps est perdu avec les questions-réponses des étudiants, les moments où l’enseignant attire l’attention sur une tentative de présentation « multimédia » dans la salle, ou encore le fait que le plan global du cours n’était pas entièrement calé à l’avance et ne permettait donc pas d’anticiper certaines questions.
Le temps passé à écrire au tableau devient aussi considérable une fois cumulé.
Bien sûr, l’ordre des supports peut toujours être discuté et réorganisé, et je prévois un jour de réaliser moi-même une série de vidéos expliquant ce contenu d’une manière qui corresponde à ma sensibilité.
Je suis content de voir que ce cours semble conserver ses racines tout en utilisant un langage plus moderne comme Python, et je pense que, comme Python est un langage multiparadigme pratique, les gens ne reconnaissent pas assez son expressivité au travers des idiomes fonctionnels, même si ce n’est pas une pureté totale.
- Ce cours implémente Scheme en Python, puis réimplémente Scheme en Scheme.
  À mon avis, Python pourrait, et devrait, être retiré de ce cours.
  Python prend très mal en charge la programmation fonctionnelle.
  Les listes ne sont pas fondées sur cons, les lambdas sont très limitées, le pattern matching est atroce et n’est pas basé sur des expressions, et les espaces de noms sont aussi étranges.
  Python est difficilement un langage moderne : il est resté dans les années 1990, et il n’a grandi, malheureusement au détriment de meilleurs langages, que parce qu’il dispose d’une C-API correcte.
- La programmation fonctionnelle en Python est assez faible, et je pense que JavaScript est même meilleur sur ce point.
  Comme il n’y a pas d’optimisation des appels terminaux, certains exercices de code nécessitent des solutions complètement différentes de celles en Scheme.
  Si du code traduit à l’identique échoue, l’enseignant doit-il dire aux étudiants de simplement le croire parce que cela ne fonctionne pas ainsi à cause du langage choisi, ou bien faut-il considérer chaque cas comme un problème d’externalisation complète de la pile et le résoudre de cette façon ?
  Forcer SICP à rentrer dans Python me semble assez idiot.
- Il existe aussi les cours d’ArsDigita University.
  Le site est désormais hors ligne, mais les cours sont consultables sur archive.org.
  https://en.m.wikipedia.org/wiki/ArsDigita#ArsDigita_Foundati...
  https://archive.org/details/arsdigita_01_sicp/
  Ils vendaient une clé USB contenant tout le programme ; ce serait vraiment bien si quelqu’un mettait l’ISO en ligne.
  https://web.archive.org/web/20190222145553/aduni.org/drives/
- Le problème de Python et de la plupart des langages non issus de Lisp est qu’ils ne permettent pas facilement de traiter les programmes comme des données.
  Des choses qui s’expriment simplement en Scheme deviennent des exercices complexes dans d’autres langages.
  Au lieu de se concentrer sur les concepts sous-jacents, les étudiants se retrouvent à se focaliser sur des détails du langage d’implémentation dont ils n’auraient pas à se soucier en Scheme.
La première fois que j’ai vu cons/car/cdr implémentés avec des lambdas, ça m’a paru magique.
Mais au final, j’y vois surtout une démonstration du fait que le runtime du langage implémente un dictionnaire clé/valeur, et qu’on peut s’appuyer sur cette implémentation pour construire d’autres structures de données.
- Je trouve la logique de déstructuration d’Elixir beaucoup plus intéressante, et la version affaiblie d’ES6 beaucoup plus pratique.
  En Elixir, on peut extraire autant d’éléments qu’on veut depuis le début.
- Il n’y a pas besoin d’un dictionnaire clé/valeur, seulement de pointeurs.
  Une closure sans comportement n’est qu’un pointeur vers les variables capturées, et une closure avec deux pointeurs est une paire dont on peut obtenir car et cdr.
  Le runtime doit permettre d’utiliser ce qui est pointé même en dehors de la définition, ce qui nécessite de l’analyse d’échappement, du garbage collection, etc., mais pas de dictionnaire.
Récemment, je suis tombé sur l’idée selon laquelle, en démonstration de théorèmes, pour prouver quelque chose comme 0 != 1, l’encodage de Church ne suffit pas et il faut des types de données inductifs.
J’ai mis quelques éléments en vrac à ce sujet ici, avec aussi une critique distincte de SICP : https://intellec7.notion.site/Drinking-SICP-hatorade-and-why...
J’aimerais mieux comprendre les limites du point de vue selon lequel « tout n’est que fonction ».
- S’il existe d’autres faits concrets exploitables sur les inégalités, on doit pouvoir prouver 0 ≠ 1.
  On peut déduire du théorème f = g -> f x = g x un fait d’inégalité sur le membre de droite, puis en prendre la contraposée.
  Il me semble exact de dire qu’on ne peut pas prouver directement une inégalité entre nombres de Church sans autre fait sur les inégalités.
  En revanche, avec les types de données inductifs, le système de preuve peut « observer » directement l’égalité ou l’inégalité en retirant récursivement l’application du constructeur le plus externe de deux instances concrètes du même type inductif.
- La démonstration de théorèmes nécessite des types Sigma et Pi, ainsi qu’une forme de notion d’égalité.
  Je me demande si l’on peut y parvenir avec l’encodage de Scott ou l’encodage de Church.
- Lien corrigé : https://goosetaco.notion.site/Drinking-SICP-hatorade-and-why...
Le livre lui-même est déjà discuté ici : https://news.ycombinator.com/item?id=42157558
Je me demande s’il y a une raison pour laquelle le lien mène à une discussion plus bas dans la page plutôt qu’au début de celle-ci.
Peut-être pourrait-on fusionner cet article avec la discussion existante.
David Beazley est une figure assez légendaire dans le monde Python, et même si ce cours m’a d’abord semblé être une idée surprenante, après y avoir réfléchi deux secondes, ça m’a paru être une combinaison parfaite, donc je me suis inscrit au cours suivant.
Le point essentiel, c’est que ce type de format ressemble à ce que pourrait devenir la formation continue des ingénieurs logiciels.
- S’il n’a pas couvert la compilation du chapitre 5, il est passé à côté de la meilleure partie de SICP.
Il y a une coquille dans le code de la section « the substitution model ».
("+", ("fib", ("-", "n", 2)), ("fib", ("-", "n", 1))),
Ce qui est défini, c’est fibonacci, et fib ne l’est pas ; les deux appels à fib devraient donc clairement être fibonacci.
Le code du dépôt GitHub réel est correct : https://github.com/savarin/pyscheme/blob/0f47292c8e5112425b5...
Je pense que SICP est excellent.
Cela dit, plus j’apprends et plus j’étudie les maths, plus je me rapproche de la conclusion que les relations constituent un concept primitif plus fondamental.
Toute fonction peut être exprimée comme une relation de forme restreinte, mais l’inverse ne tient pas sans ajouter tout un appareillage supplémentaire.
Les bases de données relationnelles et SQL sont certes les exemples les plus connus et les plus réussis de programmation relationnelle, mais je pense que ce domaine reste encore largement inexploré.
En ce moment, mon intérêt porte moins sur la conception de langages de programmation que sur l’enseignement des bases des mathématiques à de très jeunes enfants.
Curieusement, enseigner un prédicat comme « est grand » comme une relation unaire, et « est plus grand que » comme une relation binaire, est bien plus facile que d’essayer de saisir le même concept sous forme de fonction.
Je n’aime pas trop la perspective « tout est fonction », car elle est trop simplificatrice et souvent peu utile.
Par exemple, il existe des fonctions qui ne tiennent pas dans le cache, la RAM, le disque, etc., des fonctions dont le Big O explose, comme les JOIN à N voies ou la recherche/le matching, et aussi des fonctions avec effets de bord, y compris non idempotentes.
Presque personne ne pense aux attaques par canal auxiliaire sur les fonctions.
Il existe aussi des fonctions non déterministes qui dépendent de dates, d’heures, de durées, etc., et les fonctions peuvent échouer en cours de route, voire ne pas échouer proprement.
Il est également difficile de supposer qu’elles ne consomment pas de ressources qui affectent d’autres « fonctions » utilisant un pool de ressources partagé.
Les arguments d’une fonction peuvent être arbitrairement grands ou complexes, mais dans le monde réel il y a des limites ; il faut alors des pointeurs, puis à nouveau des références distantes comme le Web ou le disque.
Dites-moi quand m’arrêter, je pourrais continuer longtemps.
- Une simplification excessive peut parfois être excellente.
  Dans ce cas, le modèle du lambda-calcul est le fondement de l’approche « tout n’est que fonction » ; il est très simple, tout en étant plus facile à manipuler et à raisonner que les machines de Turing, entre autres, ce qui en fait un bon modèle de calcul.
  C’est pourquoi il se trouve à la base de la plupart des systèmes de logique informatique et de preuve.
- Beaucoup de ces choses peuvent être modélisées comme des fonctions, et il suffit qu’elles soient effectivement écrites ainsi.
  Si une fonction a besoin d’une ressource, faites en sorte qu’elle demande cette ressource ; si elle dépend de la date/de l’heure, faites en sorte qu’elle dépende de la date/de l’heure ; si elle renvoie une valeur non déterministe, faites en sorte qu’elle renvoie une valeur non déterministe.
  L’une des raisons pour lesquelles l’approche de la programmation fonctionnelle brille, c’est qu’elle oblige à traiter ces choses sérieusement.
  Si vous voulez utiliser une ressource partagée implicitement, vous devez la modéliser, et une « fonction » qui dépend d’une ressource partagée implicite se distingue explicitement d’une vraie fonction.
- La moitié de ce qui est appelé ici fonction n’en est en réalité pas une, et beaucoup de gens dans le monde de la programmation fonctionnelle ne l’appelleraient pas non plus ainsi.
  Cela relève plutôt de la procédure.
  Une fonction est une procédure, mais toutes les procédures ne sont pas des fonctions.
- À des fins théoriques, je pense que c’est le seul espoir.