let rec fact n =
if n <= 1 then (* cas de base *)
1
else (* cas récursif *)
n * fact (n-1) (* on se rappelle sur n-1, donc on
arrivera à 1 ou 0 à un moment *)
Observons l'exécution « fact 6 ».
fact 6
6 * fact 5
5 * fact 4
4 * fact 3
3 * fact 2
2 * fact 1
1 ← cas de base
2
6
24
120
720
Dans les architectures modernes, une zone de la mémoire est
allouée pour le programme et utilisée de façon particulière :
la pile d'exécution.
C'est dans cette zone que sont allouée les variables locales à
la fonction. Lorsque l'on fait un appel de fonction, le code
machine effectue les instructions suivantes
La fonction appelée :
On va illustrer le comportement des fonctions récursives avec du code assembleur intel 64 bits
Le code est tout à fait similaire sur d'autres architectures (MIPS, ARM, …)
Quelques points à savoir :
pile
6 0xabcde 5 0x12345 4 0x12345 3 0x12345 2 0x12345 1 0x12345
rax
6
5
4
3
2
1
2
6
24
120
720
fact:
▶ cmpq 1, %rsp[+8] #compare n à 1
▶ jle Lthen #si <=, then
▶ movq %rsp[+8], %rax # sinon copier n dans rax
▶ subq 1, %rax # rax := rax - 1
▶ push %rax # place n-1 sur la pile
▶ call fact # appelle fact, la valeur de
# retour est dans rax
# ici : adresse 0x12345
▶ addq 8, %rsp # on nettoie la pile
▶ imulq %rsp[+8], %rax #
▶ ret # on revient
Lthen:
▶ movq 1, %rax
▶ ret
main:
▶ push 6
▶ call fact
▶ ... #située à l'adresse 0xabcde
La pile grandit à chaque appel récursif.
Si on fait trop d'appels (en particulier mauvais cas de base, on ne s'arrête jamais), la pile dépasse sa taille maximale autorisée ⇒ Erreur Stack Overflow
Par défaut sous linux, la pile fait 8192 octets.
Elle peut être agrandie par le système ou l'utilisateur (command ulimit -s)
Pour la factorielle, la solution n'est pas satisfaisante, on utilise 16000ko pour calculer fact 1000 !
Considérons la fonction fact_alt :
let rec fact_alt n acc =
if n <= 1 then
acc
else
fact_alt (n - 1) (n * acc)
fact_alt 6 1
fact_alt 5 6
fact_alt 4 30
fact_alt 3 120
fact_alt 2 360
fact_alt 1 720
720 ← cas de base
720
720
720
720
720
La fonction fact_alt calcule son résultat « en descendant » :
fact_alt est une fonction récursive terminale.
Une fonction est récursive terminale si tous les appels récursifs sont terminaux.
Un appel récursif est terminal si c'est la dernière instruction à s'exécuter.
let rec fact_alt n acc =
if n <= 1 then
acc
else
fact_alt (n - 1) (n * acc)
let rec fact n =
if n <= 1 then
1
else
n * fact (n-1)
Le compilateur OCaml optimise les fonctions recursives terminales en les compilant comme des boucles, ce qui donne du code très efficace et qui consomme une quantité de mémoire bornée (et non pas une pile arbitrairement grande)
On peut appliquer une technique générale pour transformer une boucle while en fonction récursive terminale. Soit le pseudo code (Java) :
int i = 0;
int res = 0;
while (i < 1000) {
res = f (i, res); //on calcule un résultat
//en fonction des valeurs
//précédentes et de l'indice de boucle
i = i + 1;
}
return res;
Le code OCaml correspondant :
let rec loop i limit res =
if i >= limit then res (* return final *)
else
loop (i+1) limit (f i res)
let r = loop 0 1000 0
Attention, certains problèmes nécessitent forcément d'utiliser de la mémoire. Une fonction récursive non-terminale pourra alors être élégante, alors qu'un code impératif devra utiliser une boucle et une pile explicite.
Première solution :
let rec fact_alt n acc =
if n <= 1 then
acc
else
fact_alt (n - 1) (n * acc)
let fact n = fact_alt n 1
C'est bien, mais pas très satisfaisant (pourquoi ?)
En OCaml, une fonction est une valeur comme une autre. On peut donc définir des fonctions locales à des expressions :
let x = 42
let x2 =
let carre n = n * n
in
carre x
La fonction carre est une fonction locale à l'expression dans laquelle elle se trouve. La notation :
let f x1 … xn =
ef
in
e
permet de définir la fonction et de ne l'utiliser que pour l'expression e. La fonction f n'est pas visible à l'extérieur.
Une utilisation courante des fonctions locales est la définition de fonctions auxiliaires à l'intérieur d'une fonction principale :
let fact m =
let rec fact_alt n acc =
if n <= 1 then
acc
else
fact_alt (n - 1) (n * acc)
in
fact_alt m 1
Ici, il est impossible d'appeler fact_alt depuis
l'extérieur (et en particulier avec de mauvais paramètres).
C'est une forme d'encapsulation.
Remarque : fact n'a pas besoin d'être récursive, il
n'y a que fact_alt qui doit être déclarée avec « let
rec ».
Les appels récursifs ne sont pas limités à une seule fonction. Il est courant de vouloir définir deux fonctions qui s'appellent l'une l'autre :
let rec pair n =
if n == 0 then
true
else
impair (n-1)
and impair n =
if n == 0 then
false
else
pair (n-1)
pair 6
impair 5
pair 4
impair 3
pair 2
impair 1
pair 0
true ← cas de base.
Remarque : ces deux fonctions sont récursives terminales !
On aura l'occasion de revoir les fonctions mutuellement récursives lorsqu'on travaillera sur des structures de données plus complexes que des entiers.
Le compilateur OCaml effectue une inférence de types :
# let x = 2 ;;
val x : int = 2
# let y = 3 ;;
val y : int = 3
# let f n = n + 1;;
val f : int -> int = <fun>
# let g x = sqrt (float x);;
val g : int -> float = <fun>
Le compilateur affecte à chaque variable de programme une variable de type.
Il pose ensuite des équations entre ces variables de types
Si des équations sont contradictoires, OCaml indique une erreur de type
let f n =
if n <= 1 then
42
else
n + 45
αn : type de n
αf : type de retour de f
αn = int (car n <= 1)
αn = int (car n + 45)
αf = int (car on renvoie 42)
αf = int (car on n + 45)
n : αn= int
f : αn -> αf = int -> int
let g n =
if n <= 1 then
42
else
"Boo!"
αn : type de n
αg : type de retour de g
αn = int (car n <= 1)
αg = int (car on renvoie 42)
αg = string (car on renvoie "Boo!")
n : int ≠ string ⇒ erreur de typage
Soit une fonction :
let f x1 … xn =
ef
Le type de f se note : t1 -> … -> tn -> tf où :
let mult_add a b c = a * b + c;; (* int -> int -> int -> int *)
let carte n =
if n = 1 then "As"
else if n = 11 then "Valet"
else if n = 12 then "Reine"
else if n = 13 then "Roi"
else if n > 13 then "invalide"
else string_of_int n
(* int -> string *)
let us_time h m =
let s = if h > 12 then "pm" else "am" in
let h = if h > 12 then h - 12 else h in
Printf.printf "%d:%d %s" h m s
(* int -> int -> unit *)
let to_seq j h m s =
float (j * 3600 * 24 + h * 3600 + m * 60) +. s
(* int -> int -> int -> float -> float *)
Well-typed expressions do not go wrong.
Robin Milner 1978.
Dans les langages statiquement typé (comme OCaml), les opérations sont toujours appliquées à des arguments du bon type.
Certaines classes d'erreurs sont donc impossible. Cela donne du code robuste et permet d'éviter toute un catégorie de tests.
Certaines erreurs dynamiques sont toujours possible : division par 0, stack overflow, …
L'inféference de type évite au programmeur le travail fastidieux d'écrire les types pour toutes les variables de son programme.
Comme les tests, le typage est un outil précieux pour le développement et la maintenance des programmes.
Histoire d'horreur (adaptée)
Un programmeur Javascript définit une fonction f(s)
qui prend en argument une chaîne de caractère représentant une
date s. Cette fonction est une fonction utilitaire,
utilisée par plein d'autres collaborateurs dans leur code.
Le programmeur décide changer cette fonction
en f(d,m,y) qui prend trois entiers et il oublie de
prévenir ses collègues.
Le code de l'application continue de s'exécuter. La
fonction f est appelée avec une chaîne de
caractère. Utilisée comme un nombre, elle est convertie
en NaN (nombre invalide) et ne provoque pas d'erreur,
elle renvoie juste des résultats incorrects.
En OCaml (mais aussi en Java ou en C++) : les collègues sont avertis automatiquement, le code ne compile plus ! Ils modifient leur code pour appeler f avec les bons arguments.