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

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.

[GN⁺]

Avis Hacker News

• Le cours SICP a une forte densité d’information, mais prend beaucoup de temps à cause des questions-réponses des étudiants et de l’usage du tableau. L’ordre du cours pourrait aussi être réorganisé. Personnellement, je prévois une nouvelle série de vidéos

  • Le cours SICP utilise un langage moderne comme Python tout en conservant son intention d’origine
  • Python est un langage multiparadigme avec une grande expressivité

• Présentation d’une méthode pour encoder l’état avec des fonctions pures. Il existe divers encodages purement fonctionnels pour différents types de données

  • Les encodages peuvent être déroutants, mais ils sont élégants et concis
  • Un exemple d’implémentation fonctionnelle de la monade Maybe en JavaScript est montré

• À cause de l’ancre/hash dans l’URL du billet de blog, on arrivait directement au post-scriptum, ce qui était déroutant

• Voir cons/car/cdr implémentés avec des lambdas donnait l’impression de voir de la magie la première fois. Cela montre que le runtime du langage doit implémenter un dictionnaire clé/valeur

• David Beazley est une figure légendaire dans l’univers Python, et ce cours a d’abord surpris, avant de paraître très vite comme une combinaison parfaite. Inscription au prochain cours

  • Cela montre à quoi pourrait ressembler la formation continue des ingénieurs logiciels

• Découverte de l’idée qu’il faut des types de données inductifs. Avec le seul encodage de Church, on ne peut pas prouver des théorèmes comme 0 != 1

  • Le contenu lié a été publié sur Notion

• L’article lui-même était intéressant, mais la navigation sur la page était difficile. Les flèches du clavier ne permettaient pas de faire défiler

• Il y a une faute de frappe dans le code de la section « modèle alternatif ». Il faut utiliser fibonacci au lieu de fib. Le code du dépôt GitHub est correct

• Il existe un lien vers une discussion en cours sur le livre. On se demande pourquoi ce lien pointe directement vers la discussion en bas de page et s’il peut être fusionné avec une autre discussion

• Un lien YouTube est fourni