Penser et écrire en RacketCM1 : variables, fonctions et arité, prédicats, tests, récursivité, encapsulation, valeur par défaut

0Mode d'emploi

• Ce cours suit ton CM1 dans l'ordre : les numéros de slides entre parenthèses renvoient au PDF du cours (38 slides).
• Tout le code a été exécuté dans Racket 8.10, la version du cours. Ce qui suit ; → est ce que DrRacket affiche. Quand une ligne provoque une erreur, j'indique le début du message : ; → erreur : ....
• Prédis avant de lire. Cache le résultat d'un exemple, écris ta prédiction sur une feuille, puis vérifie. Le DST se passe sur papier, avec la cheatsheet imprimée pour seul document (slide 5) : ce qui est noté, c'est ta capacité à exécuter du code dans ta tête et à en écrire sans machine.
• Les encadrés « À toi » : réponds par écrit avant de déplier les réponses (clique sur le titre replié).
• Les exercices sont dans PF1 - Chapitre 1 - Exercices, avec le fichier d'autocorrection PF1-ch1-autocorrection.rkt à ouvrir dans DrRacket.
• Rythme conseillé :
  • séance 1 : parties 1 à 4, puis exercices A et B ;
  • séance 2 : parties 5 à 8, puis exercices C, D et E ;
  • séance 3 : parties 9 et 10, puis exercices F et G ;
  • séance 4 : parties 11 à 14, exercices H, puis le DST blanc chronométré.

Plan

1. 1. Programmer sans donner d'ordres
2. 2. DrRacket, ton atelier
3. 3. La syntaxe, une règle et des parenthèses
4. 4. Les nombres et les opérations
5. 5. Booléens, comparaisons et prédicats
6. 6. Nommer avec define
7. 7. Choisir avec if et cond
8. 8. Variables locales et portée
9. 9. La récursivité enveloppée
10. 10. La récursivité terminale
11. 11. Hors programme, à reconnaître
12. 12. Lire les messages d'erreur
13. 13. Tes notes du CM1, relues
14. 14. Checklist avant le DST

1Programmer sans donner d'ordres

1.1 Quatre façons de programmer (slide 3)

Python, comme tu l'as noté, est multi-paradigme : on peut y écrire dans plusieurs de ces styles. Racket aussi, mais ce cours n'en utilise qu'un.

La slide 3 range le fonctionnel du côté déclaratif. Pense à une requête SQL : SELECT nom FROM etudiants WHERE moyenne >= 10;. Tu ne dis pas comment parcourir la table, ni dans quel ordre, ni où ranger les résultats : tu décris ce que tu veux. C'est le « quoi » de l'introduction du cours, par opposition au « comment ».

1.2 Le « quoi » plutôt que le « comment »

Même problème, deux styles : la somme des carrés des entiers de 1 à n.

# Python, style impératif : le « comment »
def somme_carres(n):
    total = 0
    i = 1
    while i <= n:
        total = total + i * i
        i = i + 1
    return total

Pour comprendre ce code, tu dois simuler la mémoire : total et i changent de valeur à chaque tour. Le programme est une recette.

;; Racket, style fonctionnel : le « quoi »
(define (somme-carres n)
  (if (= n 0)
      0
      (+ (* n n) (somme-carres (- n 1)))))

(somme-carres 3)   ; → 14

Ce code se lit comme une définition mathématique : « la somme des carrés jusqu'à n vaut 0 si n = 0, et sinon n² plus la somme des carrés jusqu'à n − 1 ». En maths, tu écrirais $S(0) = 0$ et $S(n) = n^2 + S(n-1)$. Aucune variable ne change de valeur. Si la syntaxe te paraît opaque pour l'instant, c'est normal : à la fin de la partie 9, tu sauras écrire ce genre de fonction seul.

1.3 Ce que le style fonctionnel s'interdit (slide 3)

La slide 3 énumère trois absences, qui vont ensemble.

• Pas d'affectation (assignment). En Python, x = x + 1 modifie x. Dans ce cours, un nom, une fois défini, garde sa valeur. define crée une liaison (binding) entre un nom et une valeur : c'est une étiquette collée sur une valeur, pas une boîte dont on change le contenu. Comme en maths : quand tu écris « soit x = 3 » au début d'une démonstration, x ne devient pas 4 trois lignes plus bas.
• Pas de variable globale ni d'état (state) : aucune donnée partagée que n'importe quelle partie du programme pourrait modifier.
• Pas d'effet de bord (side effect). La note de la slide précise : modification de l'environnement, affectation, entrées/sorties. Afficher quelque chose, lire un fichier, modifier une variable : tout ce qui change le monde au lieu de simplement calculer une valeur.

Une fonction sans effet de bord est une fonction pure (pure function) : avec les mêmes arguments, elle renvoie toujours le même résultat. (+ 2 3) vaut 5 aujourd'hui, demain et le jour du DST. Contre-exemple : (random 10), qui peut renvoyer une valeur différente à chaque appel.

La récompense s'appelle la transparence référentielle (referential transparency) : on peut remplacer n'importe quelle expression par sa valeur sans changer le sens du programme. C'est exactement ce qui permet de calculer un programme à la main, étape par étape (partie 3.6). En Python, impossible de raisonner aussi tranquillement si une fonction modifie une variable globale en douce.

1.4 D'où vient Racket (slide 4)

• Le lambda-calcul (Alonzo Church, années 1930) : un modèle mathématique du calcul où tout est fonction. C'est de là que vient le mot lambda, que tu croiseras sur la cheatsheet.
• Lisp (John McCarthy, 1958) : l'un des plus anciens langages encore utilisés. Il reprend la notation lambda de Church, et il est célèbre pour ses parenthèses.
• VLisp (1971) : le V est celui de Vincennes. Ce Lisp a été développé à l'université Paris 8, quand elle était encore installée à Vincennes. Ton université fait partie de l'histoire de ce langage.
• Scheme (1975) et Common Lisp (1984) : deux grands dialectes de Lisp. Racket descend de Scheme.
• DrScheme (1995), l'environnement devenu DrRacket en 2010, quand le langage a pris le nom de Racket.

1.5 Interpréteur, compilateur, machine virtuelle

Tes notes mélangent un peu les trois. La distinction propre :

• Un interpréteur (interpreter) lit ton programme et l'exécute directement, au fur et à mesure.
• Un compilateur (compiler) traduit ton programme dans un autre langage : le code machine du processeur, ou un code intermédiaire appelé bytecode. Il n'exécute rien lui-même : l'exécution est une étape à part.
• Une machine virtuelle (virtual machine) est un programme qui exécute du bytecode. Java en est l'exemple type : javac compile en bytecode, puis la JVM l'exécute. Python fait la même chose en coulisse : il compile ton .py en bytecode, que sa machine virtuelle exécute.

Racket, dans sa version « CS » (celle du cours : DrRacket affiche [cs] au démarrage, slide 6), compile tes expressions en code machine juste avant de les exécuter, même celles que tu tapes à la main. Pour toi, tout se passe comme avec un interpréteur : tu tapes une expression, Racket affiche sa valeur. Cette boucle s'appelle le REPL (read-eval-print loop) : lire, évaluer, afficher, recommencer. Retiens surtout qu'« interprété » ou « compilé » décrit une implémentation d'un langage, pas le langage lui-même.

1.6 Ce que dit la slide 7

• Typage dynamique (dynamic typing) : comme en Python, le type d'une valeur n'est vérifié qu'au moment où le calcul a lieu. (+ 1 "2") n'est refusé que lorsqu'on l'exécute. Typed Racket (#lang typed/racket) vérifie au contraire les types avant l'exécution : c'est le typage statique.
• Références et ramasse-miettes (garbage collector) : un nom désigne une valeur rangée en mémoire (ta note « référence = lien vers case mémoire ») ; quand plus aucun nom ne mène à une valeur, le ramasse-miettes récupère sa place. Pas de free à faire à la main comme en C : Python fonctionne pareil.
• « Évaluation paresseuse » : attention, voir la partie 3.5. Racket évalue les arguments d'une fonction avant l'appel ; seules quelques formes spéciales n'évaluent que le nécessaire.

2DrRacket, ton atelier

• Lancer : commande drracket (slide 6). Sur ta Debian, le paquet racket fournit racket et drracket (sudo apt install racket).
• Deux zones. En haut, la zone de définitions (definitions window) : ton fichier .rkt, qui commence toujours par la ligne #lang racket. Ton enseignant l'omet dans ses slides (slide 6) ; toi, ne l'oublie jamais. En bas, la zone d'interactions (interactions window) : le REPL, avec son invite >.
• Run repart de zéro : Racket oublie tout, relit le fichier depuis le haut, vérifie la syntaxe et les noms, exécute les définitions et affiche la valeur de chaque expression écrite au premier niveau du fichier. Ensuite, la zone d'interactions connaît tes définitions.
• Conséquence : une définition tapée seulement dans la zone d'interactions disparaît au Run suivant. Ce qui doit rester va en haut.
• Les erreurs s'affichent en rouge, avec le code fautif surligné et un bouton « Jump To Error » (slide 19). Dans 3-unsaved-editor:2:1: f: unbound identifier in: f, lis : le fichier, la ligne 2, la colonne 1 (les colonnes se comptent à partir de 0), puis le nom qui pose problème et la raison.
• Stop interrompt un calcul qui ne se termine pas (partie 9.4). Au démarrage, DrRacket annonce memory limit: 256 MB : au-delà, il arrête tout avec Interactions disabled; out of memory (slide 34).
• L'indentation est ton détecteur de parenthèses. DrRacket indente tout seul (la touche Tab réindente la ligne courante) : si une ligne se place bizarrement, une parenthèse est mal placée au-dessus. Quand le curseur touche une parenthèse, DrRacket surligne sa jumelle.

3La syntaxe, une règle et des parenthèses

3.1 Atomes et applications (slide 8)

Un programme Racket est fait de deux sortes de briques.

• Les atomes (atoms), qui s'écrivent d'un seul bloc : des nombres (42, -7, 3.14, 1/3), des booléens (#t, #f), des chaînes de caractères ("abc"), et des identificateurs (identifiers), c'est-à-dire des noms : x, carre, even?, et même +.
• Les applications (applications) : une paire de parenthèses qui contient d'abord une fonction, puis ses arguments, séparés par des espaces.

(fonction argument1 argument2 ...)

C'est la notation préfixée (prefix notation) de la slide 8 : la fonction vient en premier, à l'intérieur de la parenthèse. Pour passer de Python à Racket, une seule règle : la parenthèse ouvrante passe devant le nom de la fonction, et les virgules disparaissent.

Les deux dernières lignes sont le vrai changement : en Racket, + et * sont des fonctions comme les autres, donc elles se placent en tête, comme max.

Le nombre d'arguments d'une fonction s'appelle son arité (arity). Dans (f 1 10), f reçoit deux arguments : elle est d'arité 2 (slide 8). Un point de vocabulaire utile au DST : dans la définition (define (f x y) ...), x et y sont les paramètres (parameters) ; dans l'appel (f 1 10), 1 et 10 sont les arguments (arguments). La slide dit « 1 est le premier paramètre » : c'est l'usage courant en français, où l'on parle aussi de paramètres effectifs.

3.2 Pas de priorités, les parenthèses décident

En maths et en Python, 1 + 2 * 3 repose sur une convention : la multiplication passe avant l'addition. Racket n'a aucune règle de priorité : chaque opération a sa propre paire de parenthèses, et la structure du calcul est écrite noir sur blanc.

Méthode pour traduire une expression mathématique :

1. Parenthèse tout, selon les priorités habituelles.
2. Réécris chaque paire en préfixe, de l'intérieur vers l'extérieur.

Exemple, avec l'expression de la slide 11 : $1 + \frac{2 \times 3}{4} + 5 \times 6$.

1. Tout parenthéser : $\big(1 + ((2 \times 3) / 4) + (5 \times 6)\big)$.
2. En préfixe : (* 2 3), puis (/ (* 2 3) 4), puis (* 5 6), puis le tout, avec un seul + puisqu'il accepte trois arguments :

(+ 1 (/ (* 2 3) 4) (* 5 6))   ; → 65/2

65/2, c'est 32,5 écrit comme une fraction exacte (partie 4.1). L'expression est un arbre (syntax tree) : chaque parenthèse est un nœud, sa fonction en est l'étiquette, ses arguments en sont les enfants.

          +
       /  |  \
      1   /    *
         / \   / \
        *   4 5   6
       / \
      2   3

Racket évalue de l'intérieur vers l'extérieur, des feuilles vers la racine :

(+ 1 (/ (* 2 3) 4) (* 5 6))
(+ 1 (/ 6 4) (* 5 6))
(+ 1 3/2 (* 5 6))
(+ 1 3/2 30)
65/2

3.3 Les parenthèses ne sont jamais décoratives

En Python, on peut ajouter des parenthèses sans rien changer : ((x)) vaut x. En Racket, chaque parenthèse ouvrante signifie « applique ce qui suit ». Une paire en trop change le sens ou provoque une erreur. Tape ces lignes une par une dans la zone d'interactions :

(5)          ; → erreur : application: not a procedure
((+ 1 2))    ; → erreur : application: not a procedure
(1 + 2)      ; → erreur : application: not a procedure

Le message complet du deuxième cas est :

application: not a procedure;
 expected a procedure that can be applied to arguments
  given: 3

Racket a calculé (+ 1 2), obtenu 3, puis a essayé d'utiliser 3 comme une fonction, parce que la parenthèse extérieure le lui demandait. Dans le troisième cas, il essaie d'appliquer la « fonction » 1 aux arguments + et 2. C'est le message le plus fréquent chez ceux qui viennent de Python : quand tu le vois, cherche une parenthèse en trop ou une notation infixe.

C'est la réponse à ta note « ouvrir une parenthèse c'est appeler une fonction » : oui, à une exception près, les formes spéciales (partie 3.5).

3.4 Les espaces séparent tout

Les espaces sont les seuls séparateurs, et les tirets sont autorisés dans les noms (une-fonction, slide 18). D'où trois pièges. Le premier :

(+1 2)   ; → erreur : application: not a procedure

+1 sans espace est lu comme le nombre 1 (« plus un ») : Racket essaie d'appliquer 1 à 2. Le deuxième, le plus sournois :

(define (fact n)
  (if (= n 1)
      1
      (* n (fact n-1))))   ; → erreur : n-1: unbound identifier

n-1 est un seul nom, pas une soustraction, et ce nom n'est défini nulle part : il faut écrire (- n 1). L'erreur apparaît dès le Run, avant tout appel, car Racket vérifie que chaque nom existe avant d'exécuter le fichier. Le troisième : dans (-x), Racket voit un seul nom, -x, qui n'existe pas ; l'opposé de x s'écrit (- x).

Enfin, les retours à la ligne et l'indentation ne comptent pas pour Racket, contrairement à Python. Ils ne comptent que pour les humains, dont celui qui corrige ta copie.

3.5 Les formes spéciales, exceptions à la règle

Pour une application (f a b), Racket suit toujours la même règle : il évalue f, a et b, tous les arguments d'abord, puis il applique la fonction aux valeurs obtenues. C'est l'évaluation stricte (strict evaluation, ou eager evaluation). La preuve :

(define (ignore x) 1)   ; une fonction qui n'utilise pas son argument
(ignore (/ 1 0))        ; → erreur : /: division by zero

ignore n'a pas besoin de x, mais Racket calcule quand même (/ 1 0) avant l'appel, et échoue.

Certains mots ne sont pourtant pas des fonctions : ce sont des formes spéciales (special forms), qui ont chacune leur propre règle d'évaluation. Dans ce chapitre : define, if, cond, and, or, let, let*, lambda et when. Par exemple, if évalue la condition, puis une seule des deux branches :

(if #t 1 (/ 1 0))   ; → 1
(and #f (/ 1 0))    ; → #f
(or #t (/ 1 0))     ; → #t

La division par zéro n'est jamais calculée : c'est là, et seulement là, que Racket évalue « uniquement si nécessaire ». C'est sans doute ce que la slide 7 appelle « évaluation paresseuse ». Mais dans le vocabulaire de Racket, l'évaluation paresseuse (lazy evaluation) désigne autre chose : le mode #lang lazy, cité sur la même slide, dans lequel l'exemple ignore renvoie 1 sans erreur.

C'est aussi pour cela que (define x 5) ne provoque pas d'erreur alors que x n'existe pas encore : define n'évalue pas le nom qu'on lui donne.

3.6 Le modèle de substitution, pour exécuter à la main

Voici ton outil principal pour le DST. Pour évaluer l'appel d'une fonction que tu as définie :

1. évalue les arguments ;
2. remplace l'appel par le corps de la fonction, où chaque paramètre est remplacé par la valeur de l'argument correspondant ;
3. continue jusqu'à obtenir une valeur.

Avec la fonction de la slide 18, (define (f x) (+ 1 (* 3 x))) :

(f (+ 2 3))
(f 5)             ; on évalue l'argument
(+ 1 (* 3 5))     ; on remplace x par 5 dans le corps de f
(+ 1 15)
16

Ce modèle de substitution (substitution model) ne fonctionne que parce qu'il n'y a pas d'affectation (partie 1.3) : un nom désigne toujours la même valeur. Il servira à suivre la récursivité pas à pas (partie 9.2).

3.7 Parenthèses, crochets, accolades (slide 8)

(), [] et {} sont interchangeables, à condition d'aller par paires du même type :

[+ 1 2]   ; → 3
{* 2 3}   ; → 6

(+ 1 2]   ; → erreur : read-syntax: expected `)` to close preceding `(`, found instead `]`

L'usage (slides 23 et 26) : des parenthèses partout, et des crochets pour les lignes d'un cond et les liaisons d'un let, parce que c'est plus lisible.

3.8 Les commentaires (slides 8, 11 et 21)

• ; : commentaire jusqu'à la fin de la ligne. L'usage : ; après du code, ;; pour une ligne entière, ;;; pour un titre de section (la cheatsheet l'utilise).
• #| ... |# : commentaire sur plusieurs lignes. Correction de tes notes : tu as écrit #! !#, c'est #| et |#.
• #; : met en commentaire l'expression suivante tout entière, même si elle tient sur plusieurs lignes. Pratique pour garder l'ancienne version d'une définition (slide 21).

#| Un commentaire
   sur deux lignes |#
#;(define (f x) (+ 1 (* 3 x)))   ; cette définition est ignorée
(define (f x) (+ 2 (* 3 x)))
(f 10)   ; → 32

(define a 3)
(define b 5)
(define x 2)
(/ (+ a b) 2)                 ; → 4
(+ (* 3 x x) (* -2 x) 1)      ; → 9
(+ (- (* 3 x x) (* 2 x)) 1)   ; → 9

4Les nombres et les opérations

4.1 Exact ou inexact (slides 9 à 11)

Racket distingue deux familles de nombres :

• les nombres exacts (exact numbers) : les entiers, de taille illimitée, et les rationnels, c'est-à-dire les fractions. Les calculs sont exacts, sans arrondi ;
• les nombres inexacts (inexact numbers) : les flottants (floating-point numbers), comme les float de Python, qui sont des approximations.

(/ 7 2)               ; → 7/2
(/ 6 4)               ; → 3/2
(/ 8 4)               ; → 2
(/ 7 2.0)             ; → 3.5
(exact->inexact 7/2)  ; → 3.5
(+ 1 2.0)             ; → 3.0
(expt 2 100)          ; → 1267650600228229401496703205376
(+ 0.1 0.2)           ; → 0.30000000000000004
(+ 1/10 2/10)         ; → 3/10

Trois règles à retenir :

• la division de deux entiers donne une fraction exacte et simplifiée, pas un flottant comme 7 / 2 en Python (qui donne 3.5) ;
• il suffit d'un seul nombre inexact dans un calcul pour que le résultat soit inexact ;
• exact->inexact convertit en flottant (slide 11).

Les slides 9 et 10 (bases 16, 8 et 2, infinis, NaN) sont hors programme. Retiens seulement que 2 et 2.0 sont égaux pour =, mais différents pour equal? (partie 5.2).

4.2 Des opérations à nombre d'arguments variable

+, -, * et / acceptent autant d'arguments que tu veux : elles sont variadiques (variadic), ou n-aires, comme dit la slide 28.

(+ 1 2 3 4)    ; → 10
(- 10 1 2 3)   ; → 4
(* 2 3 4)      ; → 24
(/ 60 2 3)     ; → 10
(- 5)          ; → -5
(/ 2)          ; → 1/2
(+)            ; → 0
(*)            ; → 1

(- a b c) calcule a − b − c, et (/ a b c) calcule a / b / c. Avec un seul argument, - donne l'opposé et / l'inverse. Sans argument, + et * renvoient leur élément neutre, 0 et 1. Cette souplesse a un revers : une parenthèse mal placée ne provoque pas toujours d'erreur, elle peut changer le calcul en silence. L'exercice B4 te montre un exemple réel.

4.3 La division entière avec quotient, remainder et modulo (slide 12)

Pour les entiers positifs, pas de surprise :

(quotient 17 5)    ; → 3
(remainder 17 5)   ; → 2
(modulo 17 5)      ; → 2

Avec des négatifs, les trois se séparent, et la slide 12 utilise justement −13 :

• quotient tronque vers zéro : −13/3 ≈ −4,33 devient −4.
• remainder a le signe de a (le dividende) et va avec quotient : $a = b \times \text{quotient} + \text{remainder}$, soit $-13 = 3 \times (-4) + (-1)$.
• modulo a le signe de b (le diviseur) et va avec la division arrondie vers le bas : $-13 = 3 \times (-5) + 2$.

Deux usages reviendront sans cesse dans les exercices :

(modulo 2026 10)      ; → 6
(quotient 2026 10)    ; → 202
(= (modulo 12 4) 0)   ; → #t

Pour n ≥ 0, (modulo n 10) donne le dernier chiffre de n et (quotient n 10) enlève ce dernier chiffre. (= (modulo a b) 0) teste si a est divisible par b.

4.4 Les autres fonctions de la slide 12

(expt 3 3)    ; → 27
(expt 2 -1)   ; → 1/2
(sqrt 16)     ; → 4
(sqrt 2)      ; → 1.4142135623730951
(max 3 5 1)   ; → 5
(min 3 5)     ; → 3
(max 1 2.0)   ; → 2.0
(abs -7)      ; → 7
pi            ; → 3.141592653589793

sqrt renvoie un résultat exact quand c'est possible (16 est un carré parfait), un flottant sinon. max et min suivent la règle de contamination : un seul argument inexact rend le résultat inexact. (sqrt -4) renvoie le nombre complexe 0+2i, hors programme. Enfin, Racket fournit déjà pi ; le (define PI 3) de la cheatsheet n'est qu'un exemple de syntaxe.

4.5 Le hasard avec random (slide 12)

• (random 10) renvoie un entier exact entre 0 et 9 : dix valeurs possibles, 10 exclu.
• (random), sans argument, renvoie un flottant strictement compris entre 0 et 1, donc dans $]0 ; 1[$ et pas dans $[0 ; 1]$. La documentation de Racket dit « between 0 and 1, exclusive » ; la slide et tes notes écrivent [0 ; 1].
• Pour un dé : (+ 1 (random 6)), un entier entre 1 et 6.

(random 10)        ; → (aléatoire) un entier entre 0 et 9
(random)           ; → (aléatoire) un flottant entre 0 et 1, bornes exclues
(+ 1 (random 6))   ; → (aléatoire) un entier entre 1 et 6

random n'est pas une fonction pure (partie 1.3). Un détail qui t'intéressera : la documentation précise que ce générateur est pseudo-aléatoire (pseudo-random), donc prévisible pour qui connaît son état interne, et qu'il faut utiliser crypto-random-bytes dès que la sécurité est en jeu (un mot de passe, un jeton). C'est la même règle qu'en Python avec les modules random et secrets.

(/ 9 6)                         ; → 3/2
(/ 9 6.0)                       ; → 1.5
(* 1.0 1/4)                     ; → 0.25
(quotient 17 -5)                ; → -3
(remainder -17 5)               ; → -2
(modulo -17 5)                  ; → 3
(- 20 5 5)                      ; → 10
(/ 100 5 2)                     ; → 10
(- (- 3))                       ; → 3
(modulo (quotient 2026 10) 10)  ; → 2

5Booléens, comparaisons et prédicats

5.1 Deux valeurs de vérité (slide 13)

Racket a deux booléens : #t (vrai, true) et #f (faux, false). Les noms true et false existent aussi (« #t abrège true », slide 13), mais DrRacket affiche toujours #t et #f.

5.2 Comparer des nombres (slides 14 et 15)

(< 1 2)       ; → #t
(<= 3 3)      ; → #t
(< 1 2 3)     ; → #t
(< 1 3 2)     ; → #f
(= 2 2 2)     ; → #t
(= 1 1.0)     ; → #t
(= 1/2 0.5)   ; → #t

Les comparaisons sont variadiques elles aussi : (< a b c) signifie a < b < c, exactement comme 1 < 2 < 3 en Python. C'est très pratique : (<= 0 x 10) teste si x est dans l'intervalle [0 ; 10].

=, <, >, <= et >= ne comparent que des nombres (slides 14 et 15) :

(= #t #t)   ; → erreur : =: contract violation

Pour comparer autre chose, la cheatsheet donne equal? :

(equal? "abc" "abc")   ; → #t
(equal? 1 1.0)         ; → #f
(equal? 'a 'b)         ; → #f

Sur les nombres, equal? est plus strict que = : 1 (exact) et 1.0 (inexact) ont la même valeur numérique, mais ce ne sont pas les mêmes valeurs Racket. 'a est un symbole, un type que tu verras dans un prochain chapitre.

5.3 not, and, or (slides 14 et 24)

(not #f)                ; → #t
(not (= 1 0))           ; → #t
(and #t #f)             ; → #f
(and (= 1 1) (= 2 2))   ; → #t
(or #f #t)              ; → #t
(or (= 1 2) (= 1 0))    ; → #f

• and est vrai si tous ses arguments le sont. Il les évalue de gauche à droite et s'arrête au premier #f.
• or est vrai si l'un au moins de ses arguments l'est. Il s'arrête à la première valeur vraie.
• Ce sont des formes spéciales (partie 3.5) : c'est l'évaluation en court-circuit (short-circuit evaluation).
• Ils acceptent autant d'arguments qu'on veut, et renvoient une valeur, pas forcément un booléen, comme en Python :

(and 1 2 3)   ; → 3
(or #f 5)     ; → 5

5.4 Le piège de la vérité : seul #f est faux

En Python, 0, "", [] et None comptent comme faux. En Racket, tout ce qui n'est pas #f compte comme vrai, y compris 0 et la chaîne vide :

(if 0 "vrai" "faux")    ; → "vrai"
(if "" "vrai" "faux")   ; → "vrai"
(not 0)                 ; → #f

La slide 14 dit que not s'utilise « uniquement pour des booléens ». C'est une excellente règle de style (ne lui donne que des booléens), mais Racket accepte n'importe quelle valeur, et not ne répond #t que pour #f.

5.5 Les prédicats (slide 13)

Un prédicat (predicate) est une fonction qui renvoie un booléen, #t ou #f. Par convention, son nom se termine par ? et se lit comme une question : even?, c'est « est-ce pair ? ». Les prédicats de la slide 13 :

(even? 2)        ; → #t
(odd? 1)         ; → #t
(zero? 0)        ; → #t
(positive? 0)    ; → #f
(negative? -1)   ; → #t
(integer? 2.0)   ; → #t
(number? "12")   ; → #f
(boolean? #f)    ; → #t
(boolean? 0)     ; → #f

Deux pièges dans cette liste : 0 n'est ni positif ni négatif pour Racket (les deux tests sont stricts), et 2.0 est un entier au sens de integer?, même s'il est inexact.

Ta note disait « définir un prédicat (?????) ». On le définit comme n'importe quelle fonction ; simplement, son corps est une expression booléenne : une comparaison, un autre prédicat, ou une combinaison avec and, or et not.

(define (majeur? age) (>= age 18))
(majeur? 20)        ; → #t
(majeur? 15)        ; → #f

(define (divisible? a b) (= (modulo a b) 0))
(divisible? 12 4)   ; → #t

(define (entre? x a b) (<= a x b))
(entre? 5 1 10)     ; → #t

C'est le même objet que dans ton cours de logique : un prédicat P(x) est une proposition avec un trou, qui devient vraie ou fausse dès qu'on donne une valeur à x. majeur? en est un.

(define (majeur-bof? age) (if (>= age 18) #t #f))   ; juste, mais maladroit
(define (majeur? age) (>= age 18))                   ; la comparaison est déjà un booléen

(= (even? 4) #t)   ; → erreur : =: contract violation

(and 1 #f 3)           ; → #f
(or #f #f)             ; → #f
(or (> 2 1) (/ 1 0))   ; → #t
(if "" 1 2)            ; → 1
(<= 1 1 2 2)           ; → #t
(equal? 2 2.0)         ; → #f

(define (impair? n) (not (even? n)))
(impair? 7)            ; → #t

(define (meme-parite? a b) (even? (+ a b)))
(meme-parite? 3 7)     ; → #t
(meme-parite? 2 7)     ; → #f

6Nommer avec define

6.1 Définir une constante (slide 18)

(define NOM expression) évalue l'expression une seule fois, puis lie le nom à la valeur obtenue. Convention de ton enseignant : les constantes en majuscules (UNE_CONSTANTE).

(define SIZE 10)
(define HALFSIZE (/ SIZE 2))
HALFSIZE   ; → 5

6.2 Définir une fonction

(define (nom-de-la-fonction param1 param2 ...)
  corps)

La valeur d'un appel est la valeur du corps. Il n'y a pas de return : le corps est le résultat.

(define (f x) (+ 1 (* 3 x)))
(f 10)   ; → 31

C'est l'équivalent de def f(x): return 1 + 3 * x. Convention : les fonctions en minuscules, les mots séparés par des tirets (une-fonction, slide 18). La cheatsheet écrit plus_petit ; ça fonctionne aussi, mais les tirets sont l'usage en Racket. Attention, Racket distingue majuscules et minuscules : A et a sont deux noms différents.

6.3 MYR contre (myr), la leçon de la slide 18

(define MYR (random 100))
(define (myr) (random 100))
MYR           ; → (aléatoire) par exemple 29
(= MYR MYR)   ; → #t
(myr)         ; → (aléatoire) par exemple 18
(myr)         ; → (aléatoire) probablement un autre nombre
myr           ; → #<procedure:myr>

• MYR est une constante : (random 100) a été évalué une fois, au moment de la définition. Ensuite, MYR est un nombre, toujours le même (29, puis 29, sur la slide).
• (myr) est l'appel d'une fonction d'arité 0 : son corps est réévalué à chaque appel (18, puis 90, sur la slide).
• myr sans parenthèses désigne la fonction elle-même, pas son résultat : DrRacket affiche #<procedure:myr>.

Toute la différence tient dans une paire de parenthèses : exactement le genre de détail qu'une question de DST peut tester.

6.4 lambda, les fonctions sans nom (slide 20, hors programme)

(define (f x) corps) est un raccourci, un sucre syntaxique (syntactic sugar), pour (define f (lambda (x) corps)). lambda fabrique une fonction sans nom, une fonction anonyme (anonymous function), comme lambda x: x + 1 en Python. La cheatsheet en montre deux, dont celle-ci :

(define suivant (lambda (x) (+ x 1)))
(suivant 41)                      ; → 42
((lambda (x) (+ 1 (* 3 x))) 11)   ; → 34

Dans la dernière ligne, le premier élément de la parenthèse n'est pas un nom mais une fonction fabriquée sur place, appliquée aussitôt à 11 (slide 20). La slide la classe hors programme : sache la lire, et au DST, écris la forme courte sauf si on te demande lambda.

6.5 Les erreurs de définition (slides 19 et 21)

Un nom inconnu donne unbound identifier : faute de frappe, nom jamais défini, nom utilisé hors de sa portée (partie 8.4), ou n-1 collé (partie 3.4). Dans un fichier où f n'est pas défini :

(f 10)   ; → erreur : f: unbound identifier

Dans la zone d'interactions, le même oubli donne un autre message, f: undefined; cannot reference an identifier before its definition. Les deux veulent dire : ce nom n'a pas de valeur ici.

Définir deux fois le même nom dans le fichier est interdit (slide 21). Dans la zone d'interactions, on peut redéfinir ; dans le fichier, non. Pour garder une ancienne version, mets-la en commentaire avec #;.

(define (f x) (+ 1 (* 3 x)))
(define (f x) (+ 1 (* 3 x)))   ; → erreur : module: identifier already defined

Le mauvais nombre d'arguments donne arity mismatch :

(define (carre x) (* x x))
(carre 2 3)   ; → erreur : carre: arity mismatch

carre: arity mismatch;
 the expected number of arguments does not match the given number
  expected: 1
  given: 2

L'ordre des définitions. Une fonction peut appeler une fonction définie plus bas dans le fichier, car son corps n'est évalué qu'au moment de l'appel :

(define (a x) (b x))
(define (b x) (* 2 x))
(a 5)   ; → 10

Une constante, en revanche, est calculée immédiatement : elle ne peut pas utiliser une fonction définie plus bas.

(define Y (b 3))         ; → erreur : b: undefined
(define (b x) (* 2 x))

Le message complet est b: undefined; cannot reference an identifier before its definition.

(define A (* 2 21))
(define (a) (* 2 21))
A      ; → 42
(a)    ; → 42
a      ; → #<procedure:a>
(A)    ; → erreur : application: not a procedure

(define (aire-rectangle l h) (* l h))
(aire-rectangle 3 4)   ; → 12

(define (f x) (x + 1))
(f 3)   ; → erreur : application: not a procedure

7Choisir avec if et cond

7.1 if (slide 22)

(if condition
    expression-si-vrai
    expression-si-faux)

(define (f x) (if (> x 10) (+ x 1) (- x 1)))
(f 15)   ; → 16
(f 5)    ; → 4

Les trois parties sont obligatoires. Sans la branche « sinon », le fichier ne se lance même pas :

(define (f x) (if (> x 0) x))   ; → erreur : if: missing an "else" expression

if est une expression, qui a une valeur. L'analogie avec Python n'est pas l'instruction if:, mais l'expression conditionnelle a if c else b. On peut donc la placer partout où l'on attend une valeur :

(define (valeur-absolue x) (if (< x 0) (- x) x))
(valeur-absolue -4)        ; → 4
(* 2 (if (> 3 1) 10 20))   ; → 20

La cheatsheet en donne un autre exemple : (define (plus_petit x y) (if (< x y) x y)).

7.2 cond (slide 23)

Dès qu'il y a plus de deux cas, les if imbriqués deviennent illisibles (la fonction f1 de la slide 23). On utilise cond :

(cond [condition1 résultat1]
      [condition2 résultat2]
      ...
      [else résultat-par-défaut])

Racket teste les conditions dans l'ordre. La première vraie l'emporte : son résultat est la valeur du cond, et les suivantes ne sont même pas évaluées. else attrape tout le reste.

(define (mention note)
  (cond [(>= note 16) "très bien"]
        [(>= note 14) "bien"]
        [(>= note 12) "assez bien"]
        [(>= note 10) "passable"]
        [else "ajourné"]))

(mention 15)   ; → "bien"
(mention 8)    ; → "ajourné"

Pour 15, la première condition est fausse et la deuxième vraie. Inutile d'écrire (and (>= note 14) (< note 16)) : si Racket arrive à la deuxième ligne, c'est que la première était fausse, donc que la note est déjà inférieure à 16.

L'ordre compte. Reprenons la slide 23 :

(define (f2 x)
  (cond ((> x 10) (+ x 1))
        ((> x 100) (+ x 10))
        (else (- x 1))))
(f2 200)   ; → 201

Pour 200, la première condition est déjà vraie. En fait, la deuxième ligne n'est atteinte pour aucun x, puisque tout nombre supérieur à 100 est aussi supérieur à 10 : c'est du code mort (dead code). Règle : place les conditions les plus restrictives en premier. Même piège dans mention : si tu commences par (>= note 10), tout le monde a « passable ».

Un cond sans else dont aucune condition n'est vraie ne renvoie rien, et ce « rien » fait échouer le calcul suivant :

(define (signe-bof x) (cond [(> x 0) 1] [(< x 0) -1]))
(+ 1 (signe-bof 0))   ; → erreur : +: contract violation

7.3 when (slide 22, hors programme)

(when condition expression) n'a pas de branche « sinon » : quand la condition est fausse, il ne renvoie rien (une valeur spéciale, #<void>, que DrRacket n'affiche pas). La slide le dit « dangereux », pour la raison qu'on vient de voir. Dans ce cours, préfère if et cond.

7.4 Écrire proprement sur papier

Recopie l'indentation de DrRacket : les deux branches d'un if alignées sous la condition, les lignes d'un cond alignées sous la première.

(define (signe x)
  (cond [(> x 0) 1]
        [(< x 0) -1]
        [else 0]))

(signe -5)   ; → -1

Tu peux regrouper les parenthèses fermantes en fin de ligne, comme ici, ou les mettre sur une ligne à part, comme ton enseignant le fait parfois : l'essentiel est que l'indentation montre la structure.

(define (f2 x)
  (cond [(> x 100) (+ x 10)]
        [(> x 10) (+ x 1)]
        [else (- x 1)]))
(f2 200)   ; → 210
(f2 50)    ; → 51
(f2 5)     ; → 4

(define (max3 a b c)
  (if (> a b)
      (if (> a c) a c)
      (if (> b c) b c)))
(max3 3 9 4)   ; → 9
(max3 9 3 4)   ; → 9
(max3 3 4 9)   ; → 9

8Variables locales et portée

8.1 let, pour nommer un calcul intermédiaire (slide 26)

La slide 26 calcule $\sqrt{x^2+1} + \sqrt{x^2+2}$, donc x² deux fois. let permet de le nommer et de ne le calculer qu'une fois :

(define (f x)
  (let ([x2 (* x x)])
    (+ (sqrt (+ 1 x2)) (sqrt (+ 2 x2)))))
(f 0)   ; → 2.414213562373095

(let ([nom1 expression1]
      [nom2 expression2])
  corps)

Racket calcule expression1 et expression2, lie les noms à leurs valeurs, puis évalue le corps : la valeur du let est celle du corps. Les noms n'existent qu'entre les parenthèses du let : c'est leur portée (scope). Deux avantages : on calcule une seule fois (slide 26 : « réduire le calcul nécessaire »), et on donne un nom à une idée intermédiaire, ce qui rend le code lisible.

8.2 let en parallèle, let* en séquence (slide 27)

Dans un let, toutes les expressions sont calculées avant qu'aucun nom n'existe : une liaison ne peut pas utiliser une autre liaison du même let.

(let ([a 1] [b (+ a 1)]) b)   ; → erreur : a: unbound identifier

let* lie les noms un par un, et chacun peut utiliser les précédents :

(let* ([a 1] [b (+ a 1)]) b)   ; → 2

C'est exactement la même chose que deux let imbriqués :

(let ([a 1])
  (let ([b (+ a 1)])
    b))   ; → 2

D'où les deux versions de la slide 27 : avec let, il faut calculer x³ par (* x x x) ; avec let*, on peut réutiliser x² :

(define (g x)
  (let* ([x2 (* x x)]
         [x3 (* x2 x)])
    (+ (sqrt (+ x2 x3)) (sqrt (+ 1 x2)) x3)))
(g 2)   ; → 13.700169592637543

8.3 define à l'intérieur d'une fonction (slides 29 et 32)

On peut aussi placer des define au début du corps d'une fonction : ce sont des définitions locales (local definitions).

(define (g x)
  (define x2 (* x x))
  (+ (sqrt (+ 1 x2)) (sqrt (+ 2 x2))))
(g 0)   ; → 2.414213562373095

La slide 32 compare les deux outils. define : un niveau de parenthèses en moins, et des fonctions locales qui peuvent s'appeler entre elles. let : une portée bien visible, délimitée par ses parenthèses. Quand le corps d'une fonction contient plusieurs expressions, la fonction renvoie la valeur de la dernière (slide 29) ; en dehors d'un define, pour enchaîner plusieurs expressions, il faut begin (la rubrique « séquences » de la cheatsheet).

8.4 La portée et le masquage (slides 29 et 30)

Portée lexicale (lexical scope) : un nom local n'est visible qu'entre les parenthèses où il est défini. C'est l'exemple de la slide 30 :

(define (f x)
  (define (g x) (* x x))
  (h x))
(define (h x)
  (g x))   ; → erreur : g: unbound identifier
(f 1)

g vit à l'intérieur de f ; h, écrite ailleurs, ne la voit pas. L'erreur apparaît dès le Run, avant même l'exécution de (f 1), puisque Racket vérifie les noms d'abord.

Point important : la portée dépend de l'endroit où le code est écrit, pas de celui qui l'appelle.

(define x 10)
(define (ajoute-x y) (+ x y))
(let ([x 1]) (ajoute-x 5))   ; → 15

Dans le let, x vaut 1 ; mais ajoute-x a été écrite dehors, là où x vaut 10, et c'est ce x-là qu'elle utilise.

Masquage (shadowing) : un nom local peut porter le même nom qu'un nom plus global ; dans sa portée, il le cache. Slide 29 :

(define (f x y)
  (define (f a b) (expt a b))
  (f (f x y) (f y x)))
(f 2 3)   ; → 134217728

Dans le corps, f désigne la fonction locale, donc expt : ce n'est pas un appel récursif. (f 2 3) calcule (expt (expt 2 3) (expt 3 2)), soit $8^9 = 134\,217\,728$. La slide 28 fait la même chose avec un f local défini par lambda. Un paramètre masque lui aussi un nom global : dans (define (f x) ...), le x du corps est le paramètre, même s'il existe un x global.

Encapsulation (le mot du titre du CM) : cacher les fonctions auxiliaires à l'intérieur de la fonction qui s'en sert. Personne d'autre ne peut les appeler ni en dépendre, donc on peut les modifier sans rien casser ailleurs. On s'en servira en partie 10.4.

(let ([x 2] [y 3]) (let ([x 10]) (+ x y)))   ; → 13

(define x 10)
(let ([x 2] [y x]) y)    ; → 10
(let* ([x 2] [y x]) y)   ; → 2

(define (h a b)
  (let ([s (+ a b)])
    (+ (* s s) (/ 1 s))))
(h 1 1)   ; → 9/2

9La récursivité enveloppée

9.1 Se définir à partir d'un cas plus petit (slide 33)

La slide 33 rapproche la récursivité de la définition par récurrence des suites : $U_n$ est définie à partir de n et de $U_{n-1}$, comme f(n) à partir de n et de f(n − 1). Prends une suite de ton cours de maths, définie par $u_0 = 3$ et $u_n = 2u_{n-1} - 1$ pour n ≥ 1 :

(define (u n)
  (if (= n 0)
      3
      (- (* 2 (u (- n 1))) 1)))
(u 0)   ; → 3
(u 3)   ; → 17

Le code est une traduction mot à mot de la définition. L'exemple du cours est la factorielle : n! = n × (n − 1) × … × 1, autrement dit n! = n × (n − 1)! et 1! = 1.

(define (f n)
  (if (= n 1)
      1
      (* n (f (- n 1)))))
(f 5)   ; → 120

Toute fonction récursive a deux ingrédients :

• un cas de base (base case) : un cas dont on connaît la réponse directement, sans appel récursif (ici n = 1, réponse 1). C'est là que la récursion s'arrête ;
• un cas récursif (recursive case) : la fonction s'appelle elle-même sur un problème plus petit (n − 1) et fait quelque chose du résultat (elle le multiplie par n).

En Racket, la récursivité est la façon de répéter un calcul : dans ce cours, pas de boucle while ni for (les boucles for existent, mais la slide 37 les classe hors programme et « peu désirables en fonctionnel »).

9.2 Suivre l'exécution avec une trace

Le modèle de substitution (partie 3.6), appliqué à (f 4) :

(f 4)
(* 4 (f 3))
(* 4 (* 3 (f 2)))
(* 4 (* 3 (* 2 (f 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
24

Regarde la forme : l'expression s'allonge, puis se replie. Chaque (* 4 ... est une opération en attente (deferred operation) : Racket ne peut pas multiplier par 4 tant qu'il ne connaît pas (f 3). L'appel récursif est enveloppé dans une multiplication : d'où le nom de récursivité enveloppée que lui donne ton enseignant (en anglais, on dit simplement recursion, ou non-tail recursion).

Au DST, « donnez la trace de (f 4) » attend exactement cela : une ligne par étape, sans sauter la phase où l'expression grandit.

9.3 Écrire une fonction récursive, la méthode des quatre questions

1. Quel est le cas le plus simple ? Celui dont tu connais la réponse sans calcul : c'est le cas de base.
2. Si j'avais la réponse pour le cas juste plus petit, comment obtiendrais-je la réponse pour n ? C'est le cas récursif. Ne simule pas tous les appels dans ta tête : suppose que (f (- n 1)) renvoie la bonne réponse, et sers-t'en. Cet acte de confiance est l'étape la plus difficile au début, et la plus importante.
3. Chaque appel se rapproche-t-il du cas de base, et finit-il par l'atteindre ? Si n diminue de 1 à chaque appel et que le cas de base est n = 0, c'est bon pour tout n ≥ 0.
4. Teste le cas de base, un petit cas tracé à la main (n = 2 ou 3), et un cas bizarre (0, un négatif, un très grand nombre).

Appliquons la méthode à la somme des entiers de 1 à n.

1. Cas le plus simple : n = 0, la somme vaut 0.
2. Si je connais la somme jusqu'à n − 1, la somme jusqu'à n vaut n plus cette somme.
3. n diminue de 1 à chaque appel : on atteint 0 si l'on part de n ≥ 0.

(define (somme n)
  (if (= n 0)
      0
      (+ n (somme (- n 1)))))
(somme 0)     ; → 0
(somme 4)     ; → 10
(somme 100)   ; → 5050

4. Tests : le cas de base donne 0, et voici la trace de (somme 3) :

(somme 3)
(+ 3 (somme 2))
(+ 3 (+ 2 (somme 1)))
(+ 3 (+ 2 (+ 1 (somme 0))))
(+ 3 (+ 2 (+ 1 0)))
(+ 3 (+ 2 1))
(+ 3 3)
6

Au passage, 5050 = 100 × 101 / 2 : c'est la formule $\frac{n(n+1)}{2}$, que tu démontreras justement par récurrence en maths. Le nombre de chiffres d'un entier, la somme de ses chiffres ou la puissance se traitent avec la même méthode : ce sont les exercices F.

9.4 Quand la récursion ne s'arrête pas (slide 31)

Trois façons de ne jamais atteindre le cas de base :

• pas de cas de base du tout. C'est le premier exemple de la slide 31, une fonction qui s'appelle elle-même avec le même argument :

(define (f x)
  (f x))
(f 1)   ; → (ne termine pas) : clique sur Stop

• pas de progrès : l'argument ne diminue pas, par exemple (+ n (somme n)) au lieu de (+ n (somme (- n 1))) ;
• un cas de base qu'on enjambe. La factorielle du cours s'arrête à n = 1. Que se passe-t-il pour (f 0) ?

La boucle de la slide 31 ne se comporte pas comme (f 0) : (f x) qui appelle (f x) tourne indéfiniment sans jamais épuiser la mémoire, jusqu'à ce que tu cliques sur Stop. La partie 10.5 explique pourquoi. Le deuxième exemple de la slide, deux fonctions qui s'appellent mutuellement (f appelle g, qui appelle f), se comporte de la même façon.

9.5 Ce que ça coûte, la pile d'exécution (slides 34 et 35)

Chaque appel en cours doit se souvenir de ce qu'il lui reste à faire après l'appel récursif : « multiplier le résultat par 4 », puis « par 3 »… Ce pense-bête est rangé dans un cadre de pile (stack frame), sur la pile d'exécution (call stack). Avec la récursivité enveloppée, les cadres s'empilent : pour (f n), n cadres attendent en même temps. La mémoire utilisée grandit avec n.

L'image : une pile de post-it. Chaque appel colle un post-it « quand tu auras le résultat, multiplie-le par 4 ». Au cas de base, n post-it sont empilés ; ensuite, on les décolle un par un, en partant du dessus.

Racket et Python ne réagissent pas pareil :

• en Python, la pile est limitée par défaut à environ 1000 appels : une factorielle récursive de 5000 lève RecursionError: maximum recursion depth exceeded ;
• en Racket, la pile n'a pas de taille fixe : elle grandit dans la mémoire tant qu'il en reste. Dans DrRacket, le (f 5000000) de la slide 34 s'arrête sur Interactions disabled; out of memory, à cause de la limite de 256 Mo et du mode « debugging » (annoncé au démarrage), qui ajoute des informations à chaque appel. En ligne de commande (racket fichier.rkt), sans ces deux freins, le même appel a réussi dans mon test, avec environ 150 Mo de mémoire. C'est exactement le message de la slide 35 : la taille de la pile dépend du langage, du processeur, de la RAM, du système et de ses paramètres.

10La récursivité terminale

10.1 Qu'est-ce qu'un appel terminal ?

Un appel terminal (tail call) est un appel dont le résultat est directement le résultat de la fonction : il ne reste plus rien à faire après lui. Une fonction est récursive terminale (tail-recursive) quand tous ses appels récursifs sont terminaux.

Le test à retenir : « Que fait-on du résultat de l'appel récursif ? » Si l'on en fait quelque chose (l'ajouter, le multiplier, le passer à une autre fonction, le comparer), la récursivité est enveloppée. Si on le renvoie tel quel, elle est terminale.

• Dans (* n (f (- n 1))), le résultat de (f (- n 1)) est ensuite multiplié par n : enveloppée.
• Dans (g (- n 1) (* n acc)), le résultat de g est renvoyé tel quel : terminale. La multiplication (* n acc) est faite avant l'appel, puisque c'est un argument (évaluation stricte, partie 3.5), et non après.

Les positions terminales sont les branches d'un if (quand ce if est lui-même en position terminale), le résultat de chaque ligne d'un cond, le corps d'un let, et la dernière expression d'un and ou d'un or. Un appel placé en argument d'une autre fonction n'est jamais terminal.

10.2 L'accumulateur, faire le travail avant l'appel (slide 33)

L'idée : au lieu de laisser des multiplications en attente, on transporte le résultat partiel dans un paramètre supplémentaire, l'accumulateur (accumulator). C'est la version de la slide 33 :

(define (g n [acc 1])
  (if (= n 1)
      acc
      (g (- n 1) (* n acc))))
(g 5)   ; → 120

[acc 1] déclare un paramètre facultatif avec une valeur par défaut (default value, slide 25) : si tu appelles (g 5) avec un seul argument, acc commence à 1. La trace de (g 4) :

(g 4)       ; acc vaut 1 par défaut
(g 4 1)
(g 3 4)
(g 2 12)
(g 1 24)
24

Compare avec la partie 9.2 : l'expression garde la même largeur. Il n'y a aucune opération en attente, le résultat partiel voyage dans acc.

L'image : un caissier de supermarché. La version enveloppée note chaque prix sur un post-it et additionne tout à la fin ; la version terminale tient le total à jour sur l'écran de la caisse, article après article.

Et l'analogie avec Python : c'est la boucle while de la partie 1.2. acc joue le rôle de total, n celui du compteur, et chaque appel récursif correspond à un tour de boucle avec de nouvelles valeurs. À une différence près : aucune variable n'est modifiée, chaque appel reçoit ses propres n et acc.

10.3 La méthode pour rendre une fonction terminale

1. Ajoute un paramètre acc. Sa valeur de départ est ce que renvoie le cas de base de la version enveloppée : 1 pour la factorielle, 0 pour la somme. C'est l'élément neutre (identity element) de l'opération.
2. Cas de base : renvoie acc.
3. Cas récursif : fais l'opération maintenant, sur acc, et transmets le résultat : (g (- n 1) (op n acc)).

Avec la somme de la partie 9.3 :

(define (somme-t n [acc 0])
  (if (= n 0)
      acc
      (somme-t (- n 1) (+ n acc))))
(somme-t 4)     ; → 10
(somme-t 100)   ; → 5050

(somme-t 3)
(somme-t 3 0)
(somme-t 2 3)
(somme-t 1 5)
(somme-t 0 6)
6

Attention à l'ordre des opérations. somme calculait 3 + (2 + (1 + 0)) ; somme-t calcule ((0 + 3) + 2) + 1 : les nombres sont combinés dans l'ordre inverse. Pour + et ×, aucune différence, car ces opérations sont commutatives et associatives. Pour d'autres calculs, le résultat peut sortir à l'envers : l'exercice G5 joue là-dessus.

10.4 La version avec fonction auxiliaire

Avec [acc 1], l'accumulateur est visible de l'extérieur, et rien n'empêche d'appeler g avec deux arguments :

(define (g n [acc 1])
  (if (= n 1)
      acc
      (g (- n 1) (* n acc))))
(g 5 2)   ; → 240

Le résultat est faux, parce que l'accumulateur est parti de 2. La solution classique cache l'accumulateur dans une fonction auxiliaire locale (encapsulation, partie 8.4) :

(define (fact-t n)
  (define (boucle n acc)
    (if (= n 1)
        acc
        (boucle (- n 1) (* n acc))))
  (boucle n 1))
(fact-t 5)   ; → 120

Seule fact-t, à un paramètre, est visible de l'extérieur ; boucle est locale. Les deux versions sont justes. Ton enseignant utilise la valeur par défaut (slides 33 et 34), alors que la slide 25 classe les valeurs par défaut hors programme : demande-lui quelle forme il attend au DST, et sache écrire les deux.

10.5 Pourquoi la version terminale économise la mémoire (slide 34)

Quand un appel est terminal, l'appel en cours n'a plus rien à faire : son cadre de pile ne sert plus. Racket garantit qu'il le réutilise au lieu d'en empiler un nouveau : c'est l'élimination des appels terminaux (tail call optimization). Une récursivité terminale s'exécute donc en mémoire constante, comme une boucle. C'est ce que la slide 34 appelle « mettre à jour les valeurs de la pile d'exécution ».

(define (f n)
  (if (= n 1)
      1
      (+ 1 (f (- n 1)))))
(define (g n [acc 1])
  (if (= n 1)
      acc
      (g (- n 1) (+ 1 acc))))
(g 5000000)   ; → 5000000
(f 5000000)   ; → (mémoire) out of memory dans DrRacket, voir la partie 9.5

Deux conséquences :

• en Racket, une récursivité terminale est une boucle ;
• une récursivité terminale infinie (le (f x) qui appelle (f x) de la slide 31) est une boucle infinie qui n'épuise jamais la mémoire : elle tourne jusqu'au Stop. Une récursivité enveloppée infinie, comme (f 0) en partie 9.4, finit en out of memory.

Python ne fait pas cette optimisation : même écrite sous forme terminale, une fonction récursive s'arrête vers 1000 appels. C'est une des raisons pour lesquelles Python préfère les boucles, et Racket la récursivité.

10.6 Le conseil de ton enseignant (slide 35)

La slide 35 est claire : « ne pas se dédier à l'écriture de fonctions récursives terminales », « ne pas voir des dépassements de pile partout », « commencer par écrire une première version simple » et se poser les questions d'optimisation ensuite. En pratique :

1. écris d'abord la version enveloppée, la plus proche de la définition mathématique, donc la plus facile à rendre juste ;
2. teste-la ;
3. transforme-la en version terminale seulement si l'énoncé le demande, ou si n peut devenir énorme.

10.7 Reconnaître au premier coup d'œil

(define (a n) (if (= n 0) 0 (+ 1 (a (- n 1)))))
(define (b n acc) (if (= n 0) acc (b (- n 1) (+ acc 2))))
(define (c n) (if (< n 10) n (c (quotient n 10))))
(define (d n) (if (= n 0) #t (not (d (- n 1)))))
(define (e n)
  (cond [(= n 0) 0]
        [(even? n) (e (quotient n 2))]
        [else (+ 1 (e (- n 1)))]))

(define (a n) (if (= n 0) 0 (+ 1 (a (- n 1)))))
(define (b n acc) (if (= n 0) acc (b (- n 1) (+ acc 2))))
(define (c n) (if (< n 10) n (c (quotient n 10))))
(define (d n) (if (= n 0) #t (not (d (- n 1)))))
(define (e n)
  (cond [(= n 0) 0]
        [(even? n) (e (quotient n 2))]
        [else (+ 1 (e (- n 1)))]))
(a 5)      ; → 5
(b 5 0)    ; → 10
(c 2026)   ; → 2
(d 4)      ; → #t
(e 13)     ; → 3

11Hors programme, à reconnaître

Le CM montre plusieurs outils marqués « hors programme ». Sache les lire, sans t'en servir au DST sauf si l'énoncé le demande.

#x29                                    ; → 41
#b010101                                ; → 21
(string-append "a" "bc")                ; → "abc"
(string-length "abcde")                 ; → 5
(define (f #:x x #:y y) (+ x (* 2 y)))
(f #:y 1 #:x 2)                         ; → 4
(for ([i 3]) (printf "~a~n" i))         ; affiche : 0 1 2

Afficher n'est pas renvoyer

C'est la confusion classique quand on vient de Python, entre print et return.

• Une fonction renvoie la valeur de son corps : c'est ce qu'on utilise dans les calculs.
• display, print et printf affichent du texte : c'est un effet de bord (une sortie), et ils ne renvoient rien d'utilisable.

(define (carre x) (* x x))
(define (carre-affiche x) (display (* x x)))
(+ 1 (carre 3))           ; → 10
(+ 1 (carre-affiche 3))   ; → erreur : +: contract violation

carre-affiche montre bien 9 à l'écran, mais ce qu'elle renvoie est « rien », et + ne peut pas l'additionner. La cheatsheet utilise print ; voici la différence entre les trois :

(print "bonjour")                 ; affiche : "bonjour"
(display "bonjour")               ; affiche : bonjour
(printf "~a + ~a = ~a~n" 2 3 5)   ; affiche : 2 + 3 = 5

print affiche comme le REPL (avec les guillemets), display affiche pour un humain, et printf insère des valeurs à la place des ~a (~n passe à la ligne).

12Lire les messages d'erreur

Une erreur arrive à l'un de ces deux moments :

• avant l'exécution, au Run : Racket lit le fichier (les parenthèses), analyse la syntaxe (define, if, let…) et vérifie que chaque nom existe. En cas d'erreur à ce stade, rien n'est exécuté ;
• pendant l'exécution : mauvais type, mauvais nombre d'arguments, division par zéro. Ces erreurs n'apparaissent que si la ligne fautive est réellement exécutée.

C'est une précision sur la slide 7 (« détection des erreurs à l'exécution ») : c'est vrai pour les types, pas pour la syntaxe ni pour les noms.

(define f x (+ x 1))   ; → erreur : define: bad syntax

(define (moyenne a b) (/ (+ a b) 2)   ; → erreur : read-syntax: expected a `)` to close `(`

13Tes notes du CM1, relues

Ce qui est juste. Les définitions des paradigmes (séquence d'ordres pour l'impératif, décrire le problème plutôt que l'algorithme pour le déclaratif), Python multi-paradigme, l'absence d'affectation et le sens du =, la filiation lambda-calcul, Lisp, VLisp, l'interpréteur qui lit et exécute, la référence comme lien vers une case mémoire, ; pour commenter, la liste des opérations, (random 10) dans [0 ; 9], la définition du prédicat, define pour les variables et les fonctions. Et tu as noté le bon objectif : la récursivité terminale, c'est la partie 10.

Ce qu'il faut corriger ou compléter.

• #! !# → les commentaires sur plusieurs lignes s'écrivent #| … |# (partie 3.8).
• « pas d'affection » → pas d'affectation (assignment) (partie 1.3).
• « random [0;1] » → (random) sans argument renvoie un flottant dans ]0 ; 1[, bornes exclues (partie 4.5).
• Le compilateur « exécute le code dans une machine virtuelle » → le compilateur traduit, il n'exécute pas ; c'est la machine virtuelle qui exécute le bytecode (partie 1.5).
• « ouvrir une parenthèse c'est appeler une fonction » → oui, sauf pour les formes spéciales (define, if, cond, and, or, let), et une parenthèse n'est jamais décorative (parties 3.3 et 3.5).
• « définir un prédicat (?????) » → une fonction dont le corps est une expression booléenne, avec un nom terminé par ? (partie 5.5).
• « pro obj = rendre un travail rébarbatif amusant » → je ne sais pas à quoi renvoie « pro obj » (programmation objet ? objectif du prof ?) : à compléter avec un camarade. Le CM définit la programmation orientée objet par « manipulation d'objets » (partie 1.1).
• La liste des opérations → ajoute quotient, expt et sqrt, qui sont sur la slide 12 et sur la cheatsheet (parties 4.3 et 4.4).

14Checklist avant le DST

Tu dois pouvoir, sur papier et sans machine :

• traduire une expression mathématique ou Python en Racket, et l'inverse (parties 3.1 et 3.2) ;
• évaluer à la main les pièges du chapitre : (/ 7 2), (quotient -13 3), (modulo -13 3), (and 1 2), (if 0 1 2), ((+ 1 2)) (parties 3 à 5) ;
• expliquer la différence entre (define A ...) et (define (a) ...) (partie 6.3) ;
• écrire un prédicat sans if inutile (partie 5.5) ;
• écrire un cond dans le bon ordre et repérer du code mort (partie 7.2) ;
• choisir entre let et let*, et dire pourquoi (partie 8.2) ;
• expliquer la portée et le masquage sur l'exemple de la slide 29 (partie 8.4) ;
• écrire une fonction récursive avec la méthode des quatre questions, et donner sa trace (parties 9.2 et 9.3) ;
• dire si une fonction est enveloppée ou terminale, et passer de l'une à l'autre avec un accumulateur, dans les deux styles (partie 10) ;
• expliquer pourquoi (f 5000000) échoue dans DrRacket et pas (g 5000000) (partie 10.5) ;
• reconnaître chaque message d'erreur de la partie 12, et dire s'il arrive avant ou pendant l'exécution.

Et après ? La cheatsheet annonce la suite du semestre : les listes (cons, first, rest, empty?), map, filter et foldl, match, puis les images. Tout reposera sur ce chapitre : une fonction récursive sur une liste suit exactement la méthode des quatre questions, avec la liste vide comme cas de base.