Programmation Fonctionnelle
Cours 04
Michele Pagani
Université Paris Diderot
UFR Informatique
Laboratoire Preuves, Programmes et Systèmes
pagani@[Link]
16 Octobre 2014
Fonctions
Les fonctions sont des valeurs de 1ère classe
Les fonctions peuvent être utilisées sans restriction, par exemple:
• liées à un identificateur (ou variable):
# l e t sum = f u n x y −> x+y ; ;
v a l sum : i n t −> i n t −> i n t = <fun>
• passées en argument à une autre fonction:
# L i s t . f o l d _ l e f t sum 0 [ 1 ; 3 ; 4 ] ; ;
− : int = 8
• retourées comme résultat d’une fonction:
# L i s t . f o l d _ l e f t sum 0 ; ;
− : i n t l i s t −> i n t = <fun>
• faire partie des structures de données:
# [ sum ; ( f u n x y −> x −y ) ; ( f u n x y −> x ∗ y ) ] ; ;
− : ( i n t −> i n t −> i n t ) l i s t = [< fun >; <fun >; <fun >]
Les fonctions sont des valeurs de 1ère classe
Les fonctions peuvent être utilisées sans restriction, par exemple:
• liées à un identificateur (ou variable):
# l e t sum = f u n x y −> x+y ; ;
v a l sum : i n t −> i n t −> i n t = <fun>
• passées en argument à une autre fonction:
# L i s t . f o l d _ l e f t sum 0 [ 1 ; 3 ; 4 ] ; ;
− : int = 8
• retourées comme résultat d’une fonction:
# L i s t . f o l d _ l e f t sum 0 ; ;
− : i n t l i s t −> i n t = <fun>
• faire partie des structures de données:
# [ sum ; ( f u n x y −> x −y ) ; ( f u n x y −> x ∗ y ) ] ; ;
− : ( i n t −> i n t −> i n t ) l i s t = [< fun >; <fun >; <fun >]
Les fonctions sont des valeurs de 1ère classe
Les fonctions peuvent être utilisées sans restriction, par exemple:
• liées à un identificateur (ou variable):
# l e t sum = f u n x y −> x+y ; ;
v a l sum : i n t −> i n t −> i n t = <fun>
• passées en argument à une autre fonction:
# L i s t . f o l d _ l e f t sum 0 [ 1 ; 3 ; 4 ] ; ;
− : int = 8
• retourées comme résultat d’une fonction:
# L i s t . f o l d _ l e f t sum 0 ; ;
− : i n t l i s t −> i n t = <fun>
• faire partie des structures de données:
# [ sum ; ( f u n x y −> x −y ) ; ( f u n x y −> x ∗ y ) ] ; ;
− : ( i n t −> i n t −> i n t ) l i s t = [< fun >; <fun >; <fun >]
Les fonctions sont des valeurs de 1ère classe
Les fonctions peuvent être utilisées sans restriction, par exemple:
• liées à un identificateur (ou variable):
# l e t sum = f u n x y −> x+y ; ;
v a l sum : i n t −> i n t −> i n t = <fun>
• passées en argument à une autre fonction:
# L i s t . f o l d _ l e f t sum 0 [ 1 ; 3 ; 4 ] ; ;
− : int = 8
• retourées comme résultat d’une fonction:
# L i s t . f o l d _ l e f t sum 0 ; ;
− : i n t l i s t −> i n t = <fun>
• faire partie des structures de données:
# [ sum ; ( f u n x y −> x −y ) ; ( f u n x y −> x ∗ y ) ] ; ;
− : ( i n t −> i n t −> i n t ) l i s t = [< fun >; <fun >; <fun >]
Fonctions à un argument
function id −> exp
• C’est une fonction qui prend un argument, dénoté par
l’identificateur id, et qui renvoie comme résultat la valeur de
l’expression exp.
• La portée de id est exp
• Le type de cette valeur est t1 − >t2 , où t1 est le type de
l’argument et t2 est le type du résultat de la fonction.
• Le type est déterminé utilisant des informations dans
l’expression exp, et peut être polymorphe. (⇒ voir cours 3)
• en général, on peut avoir un filtrage par motif:
function
| motif_1 −> exp_1
...
| motif_n −> exp_n
Fonctions à un argument
function id −> exp
• C’est une fonction qui prend un argument, dénoté par
l’identificateur id, et qui renvoie comme résultat la valeur de
l’expression exp.
• La portée de id est exp
• Le type de cette valeur est t1 − >t2 , où t1 est le type de
l’argument et t2 est le type du résultat de la fonction.
• Le type est déterminé utilisant des informations dans
l’expression exp, et peut être polymorphe. (⇒ voir cours 3)
• en général, on peut avoir un filtrage par motif:
function
| motif_1 −> exp_1
...
| motif_n −> exp_n
Fonctions à un argument
function id −> exp
• C’est une fonction qui prend un argument, dénoté par
l’identificateur id, et qui renvoie comme résultat la valeur de
l’expression exp.
• La portée de id est exp
• Le type de cette valeur est t1 − >t2 , où t1 est le type de
l’argument et t2 est le type du résultat de la fonction.
• Le type est déterminé utilisant des informations dans
l’expression exp, et peut être polymorphe. (⇒ voir cours 3)
• en général, on peut avoir un filtrage par motif:
function
| motif_1 −> exp_1
...
| motif_n −> exp_n
Fonctions à un argument
function id −> exp
• C’est une fonction qui prend un argument, dénoté par
l’identificateur id, et qui renvoie comme résultat la valeur de
l’expression exp.
• La portée de id est exp
• Le type de cette valeur est t1 − >t2 , où t1 est le type de
l’argument et t2 est le type du résultat de la fonction.
• Le type est déterminé utilisant des informations dans
l’expression exp, et peut être polymorphe. (⇒ voir cours 3)
• en général, on peut avoir un filtrage par motif:
function
| motif_1 −> exp_1
...
| motif_n −> exp_n
Fonctions à un argument
function id −> exp
• C’est une fonction qui prend un argument, dénoté par
l’identificateur id, et qui renvoie comme résultat la valeur de
l’expression exp.
• La portée de id est exp
• Le type de cette valeur est t1 − >t2 , où t1 est le type de
l’argument et t2 est le type du résultat de la fonction.
• Le type est déterminé utilisant des informations dans
l’expression exp, et peut être polymorphe. (⇒ voir cours 3)
• en général, on peut avoir un filtrage par motif:
function
| motif_1 −> exp_1
...
| motif_n −> exp_n
Exemples
# f u n c t i o n x −> x + 1 ; ;
− : i n t −> i n t = <fun>
# f u n c t i o n y −> [ [ y +2; y + 3 ] ; [ y ; y ∗ y ] ] ; ;
− : i n t −> i n t l i s t l i s t = <fun>
# ( f u n c t i o n x −> x +3) 5 ; ;
− : int = 8
# ( f u n c t i o n x −> x ∗ x ) ( f u n c t i o n x −> x +1) 3 ; ; ( ∗ e r r e u r ∗ )
^^^^^^^^^^^^^^^^^
E r r o r : T h i s f u n c t i o n h a s t y p e i n t −> i n t
I t i s a p p l i e d t o t o o many a r g u m e n t s ;
maybe you f o r g o t a ‘ ; ’ .
# ( f u n c t i o n x −> x ∗ x ) ( ( f u n c t i o n x −> x + 1 ) 3 ) ; ; ( ∗OK∗ )
− : i n t = 16
Exemples
# function
| [ ] −> " v i d e "
| _ : : _ −> " p a s ␣ v i d e " ; ;
− : ’ a l i s t −> s t r i n g = <fun>
# function
| n when n>=0 −> n
| n −> −n ; ;
− : i n t −> i n t = <fun>
# function
n+1 −> n ; ; (∗ pas motif ∗)
^^
E r r o r : Syntax e r r o r
# f u n c t i o n t : : q −> t ; ; (∗ pas e x h a u s t i f ∗)
^^^^^^^^^^^^^^^^^
Warning 8 : t h i s p a t t e r n −m a t c h i n g i s not e x h a u s t i v e .
Here i s an e x a m p l e o f a v a l u e t h a t i s not matched : [ ]
− : ’ a l i s t −> ’ a = <fun>
Déclaration des fonctions
let f x = exp raccourci pour let f = function x −> exp
# l e t s u c = f u n c t i o n x −> x + 1 ; ;
v a l s u c : i n t −> i n t = <fun>
# suc 5 ; ;
− : suc = 6
# l e t s u c x = x+1 ; ; ( ∗ e q u i v a l e n t au p r e c e d e n t ∗ )
v a l s u c : i n t −> i n t = <fun>
let rec f i b = function
| 0 −> 0
| 1 −> 1
| x −> ( f i b ( x −1))∗( f i b ( x − 2 ) ) ; ;
val f i b : i n t −> i n t = <fun>
# l e t r e c f i b x = match x w i t h
| 0 | 1 −> x
| x −> ( f i b ( x −1))∗( f i b ( x − 2 ) ) ; ; ( ∗ e q u i v a l e n t au p r e c e d e n t ∗ )
v a l f i b : i n t −> i n t = <fun>
Qu’est-ce qu’il se passe lors d’une
application ?
(exp_f)(exp_a)
Le typage nous garantie (si on ignore la polymorphie):
• exp_f est d’un type fonctionnel ta 7→ tr
• exp_a est du type ta
L’évaluation procède par étapes:
1 évaluation de exp_f function x −> exp_c
(pas d’évaluation dans le corps de function)
2 évaluation de exp_a val_a
3 substitution toute occurrence de x par val_a exp_c[x/val_a]
4 évaluation de l’expression ainsi obtenue val_r
Qu’est-ce qu’il se passe lors d’une
application ?
(exp_f)(exp_a)
Le typage nous garantie (si on ignore la polymorphie):
• exp_f est d’un type fonctionnel ta 7→ tr
• exp_a est du type ta
L’évaluation procède par étapes:
1 évaluation de exp_f function x −> exp_c
(pas d’évaluation dans le corps de function)
2 évaluation de exp_a val_a
3 substitution toute occurrence de x par val_a exp_c[x/val_a]
4 évaluation de l’expression ainsi obtenue val_r
Qu’est-ce qu’il se passe lors d’une
application ?
(exp_f)(exp_a)
Le typage nous garantie (si on ignore la polymorphie):
• exp_f est d’un type fonctionnel ta 7→ tr
• exp_a est du type ta
L’évaluation procède par étapes:
1 évaluation de exp_f function x −> exp_c
(pas d’évaluation dans le corps de function)
2 évaluation de exp_a val_a
3 substitution toute occurrence de x par val_a exp_c[x/val_a]
4 évaluation de l’expression ainsi obtenue val_r
Qu’est-ce qu’il se passe lors d’une
application ?
(exp_f)(exp_a)
Le typage nous garantie (si on ignore la polymorphie):
• exp_f est d’un type fonctionnel ta 7→ tr
• exp_a est du type ta
L’évaluation procède par étapes:
1 évaluation de exp_f function x −> exp_c
(pas d’évaluation dans le corps de function)
2 évaluation de exp_a val_a
3 substitution toute occurrence de x par val_a exp_c[x/val_a]
4 évaluation de l’expression ainsi obtenue val_r
Qu’est-ce qu’il se passe lors d’une
application ?
(exp_f)(exp_a)
Le typage nous garantie (si on ignore la polymorphie):
• exp_f est d’un type fonctionnel ta 7→ tr
• exp_a est du type ta
L’évaluation procède par étapes:
1 évaluation de exp_f function x −> exp_c
(pas d’évaluation dans le corps de function)
2 évaluation de exp_a val_a
3 substitution toute occurrence de x par val_a exp_c[x/val_a]
4 évaluation de l’expression ainsi obtenue val_r
Qu’est-ce qu’il se passe lors d’une
application ?
(function x −> 2∗x−x)(1+2)
(pas d’éval au dessous de function −> x)
Qu’est-ce qu’il se passe lors d’une
application ?
(function x −> 2∗x−x)(1+2)
(pas d’éval au dessous de function −> x)
⇓ 2 eval de argument
(function x −> 2∗x−x) 3
Qu’est-ce qu’il se passe lors d’une
application ?
(function x −> 2∗x−x)(1+2)
(pas d’éval au dessous de function −> x)
⇓ 2 eval de argument
(function x −> 2∗x−x) 3
⇓ 3 substitution du parametre
2∗3−3
Qu’est-ce qu’il se passe lors d’une
application ?
(function x −> 2∗x−x)(1+2)
(pas d’éval au dessous de function −> x)
⇓ 2 eval de argument
(function x −> 2∗x−x) 3
⇓ 3 substitution du parametre
2∗3−3
⇓ 4 eval du résultat
3
Qu’est-ce qu’il se passe lors d’une
application ?
snd ("Hello", (function x −> 2∗x−x)) (1+2)
⇓ 1 eval de fonction
(function x −> 2∗x−x)(1+2)
(pas d’éval au dessous de function −> x)
⇓ 2 eval de argument
(function x −> 2∗x−x) 3
⇓ 3 substitution du parametre
2∗3−3
⇓ 4 eval du résultat
3
Pas d’evaluation au dessous de
function y −>
# l e t f = f u n c t i o n x −> f u n c t i o n y −> y / x ; ;
v a l f : i n t −> i n t −> i n t = <fun>
# let g = f 0;; (∗ pas d ’ e r r e u r ∗)
v a l g : i n t −> i n t = <fun>
# let z = g 5;; (∗ E r r e u r : d i v i s i o n par z e r o ∗)
Exception : Division_by_zero .
Fonctions à plusieurs arguments
fun id_1 ... id_n −> exp
est un raccourci pour
function id_1 −> ... function id_n −> exp
• c’est une fonction qui prend une suite de n arguments
• application partielle:
(function id_1 −> ... function id_n −> exp ) exp1
est une fonction qui prend une suite de n − 1 arguments
• filtrage par motif:
on peut utiliser match id_i with pour déclarer l’argument
id_i dont depend le filtrage.
• déclaration:
let f id_1 ... id_n = exp est un raccourci pour
let f = fun id_1 ... id_n −> exp
Fonctions à plusieurs arguments
fun id_1 ... id_n −> exp
est un raccourci pour
function id_1 −> ... function id_n −> exp
• c’est une fonction qui prend une suite de n arguments
• application partielle:
(function id_1 −> ... function id_n −> exp ) exp1
est une fonction qui prend une suite de n − 1 arguments
• filtrage par motif:
on peut utiliser match id_i with pour déclarer l’argument
id_i dont depend le filtrage.
• déclaration:
let f id_1 ... id_n = exp est un raccourci pour
let f = fun id_1 ... id_n −> exp
Fonctions à plusieurs arguments
fun id_1 ... id_n −> exp
est un raccourci pour
function id_1 −> ... function id_n −> exp
• c’est une fonction qui prend une suite de n arguments
• application partielle:
(function id_1 −> ... function id_n −> exp ) exp1
est une fonction qui prend une suite de n − 1 arguments
• filtrage par motif:
on peut utiliser match id_i with pour déclarer l’argument
id_i dont depend le filtrage.
• déclaration:
let f id_1 ... id_n = exp est un raccourci pour
let f = fun id_1 ... id_n −> exp
Fonctions à plusieurs arguments
fun id_1 ... id_n −> exp
est un raccourci pour
function id_1 −> ... function id_n −> exp
• c’est une fonction qui prend une suite de n arguments
• application partielle:
(function id_1 −> ... function id_n −> exp ) exp1
est une fonction qui prend une suite de n − 1 arguments
• filtrage par motif:
on peut utiliser match id_i with pour déclarer l’argument
id_i dont depend le filtrage.
• déclaration:
let f id_1 ... id_n = exp est un raccourci pour
let f = fun id_1 ... id_n −> exp
Plusieurs arguments (exemples)
# l e t s o i t = f u n c t i o n x −> f u n c t i o n y −> match x w i t h
| t r u e −> ( match y w i t h
| t r u e −> f a l s e
| f a l s e −> t r u e )
| f a l s e −> y ; ;
v a l s o i t : b o o l −> b o o l −> b o o l = <fun>
# l e t s o i t = f u n x y −> match x w i t h
| t r u e −> ( match y w i t h
| t r u e −> f a l s e
| f a l s e −> t r u e )
| f a l s e −> y ; ; ( ∗ e q u i v a l e n t au p r e c e d e n t ∗ )
v a l s o i t : b o o l −> b o o l −> b o o l = <fun>
# l e t s o i t x y = match x w i t h
| t r u e −> ( match y w i t h
| t r u e −> f a l s e
| f a l s e −> t r u e )
| f a l s e −> y ; ; ( ∗ e q u i v a l e n t au p r e c e d e n t ∗ )
v a l s o i t : b o o l −> b o o l −> b o o l = <fun>
Plusieurs arguments (exemples)
# soit true true ; ;
− : bool = f a l s e
# soit true fa ls e ; ;
− : bool = true
# l e t neg = s o i t t r u e ; ; (∗ a p p l i c a t i o n p a r t i e l l e ∗)
v a l neg : b o o l −> b o o l = <fun>
# neg t r u e ; ;
− : bool = f a l s e
# neg f a l s e ; ;
− : bool = true
Plusieurs arguments (exemples)
# l e t f x y z = x +2∗y+3∗z ; ;
v a l f : i n t −> i n t −> i n t −> i n t = <fun>
# let g = f 2;;
v a l g : i n t −> i n t −> i n t = <fun>
# let h = g 3;;
v a l h : i n t −> i n t = <fun>
• Combien ça vaut h 4 ?
# h 4;;
− : i n t = 20
# l e t f x y = x∗y ; ;
v a l f : i n t −> i n t −> i n t = <fun>
• Combien ça vaut ( f 2)(( f 3)4) ?
# ( f 2)(( f 3)4);;
− : i n t = 24
Récurrence terminale
Qu’est ce qu’il s’est passé ?
# l e t r e c m k l i s t n = match n w i t h
0 −> [ ]
| n −> n : : ( m k l i s t ( n − 1 ) ) ; ;
v a l m k l i s t : i n t −> i n t l i s t = <fun>
# mklist 3;;
− : int l i s t = [ 3 ; 2; 1]
# mklist 1000000;;
Stack o v e r f l o w during e v a l u a t i o n ( l o o p i n g r e c u r s i o n ? ) .
Qu’est ce qu’il s’est passé ?
# l e t r e c m k l i s t n = match n w i t h
0 −> [ ]
| n −> n : : ( m k l i s t ( n − 1 ) ) ; ;
v a l m k l i s t : i n t −> i n t l i s t = <fun>
mklist 3 ⇒ 3:: ( mklist 2) ⇒ 3::2:: ( mklist 1) ⇒ 3::2::1 ( mklist 0)
⇒ 3::2:: 1::[] ⇒ 3:: 2::[1] ⇒ 3::[2;1] ⇒ [3;2;1]
• à chaque appel de fonction, il faut stocker plusieurs
informations d’environnement
• ces informations sont sauvegardées dans la pile d’exécution
(angl. call stack)
• quand l’appel est terminé, ces informations sont balayées du
sommet de la pile
Consequence: si trop d’appels imbriquées, on peut épuiser l’espace
disponible pour la pile !
Qu’est ce qu’il s’est passé ?
# l e t r e c m k l i s t n = match n w i t h
0 −> [ ]
| n −> n : : ( m k l i s t ( n − 1 ) ) ; ;
v a l m k l i s t : i n t −> i n t l i s t = <fun>
mklist 3 ⇒ 3:: ( mklist 2) ⇒ 3::2:: ( mklist 1) ⇒ 3::2::1 ( mklist 0)
⇒ 3::2:: 1::[] ⇒ 3:: 2::[1] ⇒ 3::[2;1] ⇒ [3;2;1]
• à chaque appel de fonction, il faut stocker plusieurs
informations d’environnement
• ces informations sont sauvegardées dans la pile d’exécution
(angl. call stack)
• quand l’appel est terminé, ces informations sont balayées du
sommet de la pile
Consequence: si trop d’appels imbriquées, on peut épuiser l’espace
disponible pour la pile !
Qu’est ce qu’il s’est passé ?
# l e t r e c m k l i s t n = match n w i t h
0 −> [ ]
| n −> n : : ( m k l i s t ( n − 1 ) ) ; ;
v a l m k l i s t : i n t −> i n t l i s t = <fun>
mklist 3 ⇒ 3:: ( mklist 2) ⇒ 3::2:: ( mklist 1) ⇒ 3::2::1 ( mklist 0)
⇒ 3::2:: 1::[] ⇒ 3:: 2::[1] ⇒ 3::[2;1] ⇒ [3;2;1]
• à chaque appel de fonction, il faut stocker plusieurs
informations d’environnement
• ces informations sont sauvegardées dans la pile d’exécution
(angl. call stack)
• quand l’appel est terminé, ces informations sont balayées du
sommet de la pile
Consequence: si trop d’appels imbriquées, on peut épuiser l’espace
disponible pour la pile !
Exemple: DrawSquare appèle DrawLine
Merci, Wikipedia
Qu’est ce qu’il s’est passé ?
# l e t r e c m k l i s t n = match n w i t h
0 −> [ ]
| n −> n : : ( m k l i s t ( n − 1 ) ) ; ;
v a l m k l i s t : i n t −> i n t l i s t = <fun>
mklist 3 ⇒ 3:: ( mklist 2) ⇒ 3::2:: ( mklist 1) ⇒ 3::2::1 ( mklist 0)
⇒ 3::2:: 1::[] ⇒ 3:: 2::[1] ⇒ 3::[2;1] ⇒ [3;2;1]
• à chaque appel de fonction, il faut stocker plusieurs
informations d’environnement
• ces informations sont sauvegardées dans la pile d’exécution
(angl. call stack)
• quand l’appel est terminé, ces informations sont balayées du
sommet de la pile
Consequence: si trop d’appels imbriquées, on peut épuiser l’espace
disponible pour la pile !
Qu’est ce qu’il s’est passé ?
# l e t r e c m k l i s t n = match n w i t h
0 −> [ ]
| n −> n : : ( m k l i s t ( n − 1 ) ) ; ;
v a l m k l i s t : i n t −> i n t l i s t = <fun>
mklist 3 ⇒ 3:: ( mklist 2) ⇒ 3::2:: ( mklist 1) ⇒ 3::2::1 ( mklist 0)
⇒ 3::2:: 1::[] ⇒ 3:: 2::[1] ⇒ 3::[2;1] ⇒ [3;2;1]
• à chaque appel de fonction, il faut stocker plusieurs
informations d’environnement
• ces informations sont sauvegardées dans la pile d’exécution
(angl. call stack)
• quand l’appel est terminé, ces informations sont balayées du
sommet de la pile
Consequence: si trop d’appels imbriquées, on peut épuiser l’espace
disponible pour la pile !
Qu’est ce qu’il s’est passé ?
# l e t r e c m k l i s t n = match n w i t h
0 −> [ ]
| n −> n : : ( m k l i s t ( n − 1 ) ) ; ;
v a l m k l i s t : i n t −> i n t l i s t = <fun>
mklist 3 ⇒ 3:: ( mklist 2) ⇒ 3::2:: ( mklist 1) ⇒ 3::2::1 ( mklist 0)
⇒ 3::2:: 1::[] ⇒ 3:: 2::[1] ⇒ 3::[2;1] ⇒ [3;2;1]
• à chaque appel de fonction, il faut stocker plusieurs
informations d’environnement
• ces informations sont sauvegardées dans la pile d’exécution
(angl. call stack)
• quand l’appel est terminé, ces informations sont balayées du
sommet de la pile
Consequence: si trop d’appels imbriquées, on peut épuiser l’espace
disponible pour la pile !
Récurrence terminale
• Il est parfois possible de réécrire une fonction en une fonction
qui utilise des appels terminaux:
• appel terminal: une fonction f appèl une fonction g , mais le
résultat envoyé par g est envoyé tout de suite par f ,
• dans ce cas, on n’a plus besoin des valeurs d’environnement de
la fonction f quand on lance g
• l’espace sur la pile d’exécution peut être libérée avant de
lancer g !
• Récurrence terminale (angl.: tail recursion): fonction recursive,
avec tous les appels récursifs à des positions terminales.
• Avantage: peu importe la profondeur de la récurrence,
l’utilisation d’espace reste constante !
• En plus, le compilateur souvent optimise le temps d’exécution
sur les appels terminaux !
Récurrence terminale
• Il est parfois possible de réécrire une fonction en une fonction
qui utilise des appels terminaux:
• appel terminal: une fonction f appèl une fonction g , mais le
résultat envoyé par g est envoyé tout de suite par f ,
• dans ce cas, on n’a plus besoin des valeurs d’environnement de
la fonction f quand on lance g
• l’espace sur la pile d’exécution peut être libérée avant de
lancer g !
• Récurrence terminale (angl.: tail recursion): fonction recursive,
avec tous les appels récursifs à des positions terminales.
• Avantage: peu importe la profondeur de la récurrence,
l’utilisation d’espace reste constante !
• En plus, le compilateur souvent optimise le temps d’exécution
sur les appels terminaux !
Récurrence terminale
• Il est parfois possible de réécrire une fonction en une fonction
qui utilise des appels terminaux:
• appel terminal: une fonction f appèl une fonction g , mais le
résultat envoyé par g est envoyé tout de suite par f ,
• dans ce cas, on n’a plus besoin des valeurs d’environnement de
la fonction f quand on lance g
• l’espace sur la pile d’exécution peut être libérée avant de
lancer g !
• Récurrence terminale (angl.: tail recursion): fonction recursive,
avec tous les appels récursifs à des positions terminales.
• Avantage: peu importe la profondeur de la récurrence,
l’utilisation d’espace reste constante !
• En plus, le compilateur souvent optimise le temps d’exécution
sur les appels terminaux !
Récurrence terminale
• Il est parfois possible de réécrire une fonction en une fonction
qui utilise des appels terminaux:
• appel terminal: une fonction f appèl une fonction g , mais le
résultat envoyé par g est envoyé tout de suite par f ,
• dans ce cas, on n’a plus besoin des valeurs d’environnement de
la fonction f quand on lance g
• l’espace sur la pile d’exécution peut être libérée avant de
lancer g !
• Récurrence terminale (angl.: tail recursion): fonction recursive,
avec tous les appels récursifs à des positions terminales.
• Avantage: peu importe la profondeur de la récurrence,
l’utilisation d’espace reste constante !
• En plus, le compilateur souvent optimise le temps d’exécution
sur les appels terminaux !
Récurrence terminale
• Il est parfois possible de réécrire une fonction en une fonction
qui utilise des appels terminaux:
• appel terminal: une fonction f appèl une fonction g , mais le
résultat envoyé par g est envoyé tout de suite par f ,
• dans ce cas, on n’a plus besoin des valeurs d’environnement de
la fonction f quand on lance g
• l’espace sur la pile d’exécution peut être libérée avant de
lancer g !
• Récurrence terminale (angl.: tail recursion): fonction recursive,
avec tous les appels récursifs à des positions terminales.
• Avantage: peu importe la profondeur de la récurrence,
l’utilisation d’espace reste constante !
• En plus, le compilateur souvent optimise le temps d’exécution
sur les appels terminaux !
Récurrence terminale (exemples)
• Ceci n’est pas une récurrence terminale:
# l e t r e c m k l i s t n = match n w i t h
0 −> [ ]
| n −> n : : ( m k l i s t ( n − 1 ) ) ; ;
• on exécute un calcul (n :: ... ) avant de renvoyer le résultat de
l’appel récursif (mklist (n−1))
• Voici une variante terminale:
# let mklist n =
l e t r e c mkaux n l = match n w i t h
| 0 −> l
| n −> mkaux ( n−1) (n : : l )
i n L i s t . r e v ( mkaux n []);;
v a l m k l i s t : i n t −> i n t l i s t = <fun>
• aucun calcul après l’appel récursif (mkaux (n−1) (n::l))
• on utilise une fonction auxiliaire (mkaux) avec un argument
accumulateur ( l )
• attention à renverser l’ordre des elements de la liste
Récurrence terminale (exemples)
• Ceci n’est pas une récurrence terminale:
# l e t r e c m k l i s t n = match n w i t h
0 −> [ ]
| n −> n : : ( m k l i s t ( n − 1 ) ) ; ;
• on exécute un calcul (n :: ... ) avant de renvoyer le résultat de
l’appel récursif (mklist (n−1))
• Voici une variante terminale:
# let mklist n =
l e t r e c mkaux n l = match n w i t h
| 0 −> l
| n −> mkaux ( n−1) (n : : l )
i n L i s t . r e v ( mkaux n []);;
v a l m k l i s t : i n t −> i n t l i s t = <fun>
• aucun calcul après l’appel récursif (mkaux (n−1) (n::l))
• on utilise une fonction auxiliaire (mkaux) avec un argument
accumulateur ( l )
• attention à renverser l’ordre des elements de la liste
Récurrence terminale (exemples)
• Ceci n’est pas une récurrence terminale:
# l e t r e c m k l i s t n = match n w i t h
0 −> [ ]
| n −> n : : ( m k l i s t ( n − 1 ) ) ; ;
• on exécute un calcul (n :: ... ) avant de renvoyer le résultat de
l’appel récursif (mklist (n−1))
• Voici une variante terminale:
# let mklist n =
l e t r e c mkaux n l = match n w i t h
| 0 −> l
| n −> mkaux ( n−1) (n : : l )
i n L i s t . r e v ( mkaux n []);;
v a l m k l i s t : i n t −> i n t l i s t = <fun>
• aucun calcul après l’appel récursif (mkaux (n−1) (n::l))
• on utilise une fonction auxiliaire (mkaux) avec un argument
accumulateur ( l )
• attention à renverser l’ordre des elements de la liste
Récurrence terminale (exemples)
# let mklist n =
l e t r e c mkaux n l = match n w i t h
| 0 −> l
| n −> mkaux ( n−1) (n : : l )
i n L i s t . r e v ( mkaux n []);;
v a l m k l i s t : i n t −> i n t l i s t = <fun>
mklist 3 ⇒ List . rev(mkaux 3 []) ⇒ List . rev(mkaux 2 (3::[]) )
⇒ List . rev(mkaux 2 (3::[]) ) ⇒ List . rev(mkaux 2 [3])
⇒ List . rev(mkaux 1 (2::[3]) ) ⇒ List . rev(mkaux 1 (2::[3]) )
⇒ List . rev(mkaux 1 [2;3]) ⇒ List . rev(mkaux 0 (1::[2;3]) )
⇒ List . rev(mkaux 0 (1::[2;3]) ) ⇒ List . rev(mkaux 0 [1;2;3] )
⇒ List . rev [1;2;3] ⇒ · · · ⇒ [3; 2; 1]
• à chaque appel récursif, la quantité
d’informations d’environnement à stocker est constante
• consequence. . .
Récurrence terminale (exemples)
# let mklist n =
l e t r e c mkaux n l = match n w i t h
| 0 −> l
| n −> mkaux ( n−1) (n : : l )
i n L i s t . r e v ( mkaux n []);;
v a l m k l i s t : i n t −> i n t l i s t = <fun>
mklist 3 ⇒ List . rev(mkaux 3 []) ⇒ List . rev(mkaux 2 (3::[]) )
⇒ List . rev(mkaux 2 (3::[]) ) ⇒ List . rev(mkaux 2 [3])
⇒ List . rev(mkaux 1 (2::[3]) ) ⇒ List . rev(mkaux 1 (2::[3]) )
⇒ List . rev(mkaux 1 [2;3]) ⇒ List . rev(mkaux 0 (1::[2;3]) )
⇒ List . rev(mkaux 0 (1::[2;3]) ) ⇒ List . rev(mkaux 0 [1;2;3] )
⇒ List . rev [1;2;3] ⇒ · · · ⇒ [3; 2; 1]
• à chaque appel récursif, la quantité
d’informations d’environnement à stocker est constante
• consequence. . .
Récurrence terminale (exemples)
# mklist 100000;;
− : int l i s t =
[100000; 99999; 99998; 99997; 99996; 99995; 99994; 99993; 99992; 99991;
99990; 99989; 99988; 99987; 99986; 99985; 99984; 99983; 99982; 99981; 99980;
99979; 99978; 99977; 99976; 99975; 99974; 99973; 99972; 99971; 99970; 99969;
99968; 99967; 99966; 99965; 99964; 99963; 99962; 99961; 99960; 99959; 99958;
99957; 99956; 99955; 99954; 99953; 99952; 99951; 99950; 99949; 99948; 99947;
99946; 99945; 99944; 99943; 99942; 99941; 99940; 99939; 99938; 99937; 99936;
99935; 99934; 99933; 99932; 99931; 99930; 99929; 99928; 99927; 99926; 99925;
99924; 99923; 99922; 99921; 99920; 99919; 99918; 99917; 99916; 99915; 99914;
99913; 99912; 99911; 99910; 99909; 99908; 99907; 99906; 99905; 99904; 99903;
99902; 99901; 99900; 99899; 99898; 99897; 99896; 99895; 99894; 99893; 99892;
99891; 99890; 99889; 99888; 99887; 99886; 99885; 99884; 99883; 99882; 99881;
99880; 99879; 99878; 99877; 99876; 99875; 99874; 99873; 99872; 99871; 99870;
99869; 99868; 99867; 99866; 99865; 99864; 99863; 99862; 99861; 99860; 99859;
99858; 99857; 99856; 99855; 99854; 99853; 99852; 99851; 99850; 99849; 99848;
99847; 99846; 99845; 99844; 99843; 99842; 99841; 99840; 99839; 99838; 99837;
99836; 99835; 99834; 99833; 99832; 99831; 99830; 99829; 99828; 99827; 99826;
99825; 99824; 99823; 99822; 99821; 99820; 99819; 99818; 99817; 99816; 99815;
99814; 99813; 99812; 99811; 99810; 99809; 99808; 99807; 99806; 99805; 99804;
99803; 99802; 99801; 99800; 99799; 99798; 99797; 99796; 99795; 99794; 99793;
99792; 99791; 99790; 99789; 99788; 99787; 99786; 99785; 99784; 99783; 99782;
99781; 99780; 99779; 99778; 99777; 99776; 99775; 99774; 99773; 99772; 99771;
99770; 99769; 99768; 99767; 99766; 99765; 99764; 99763; 99762; 99761; 99760;
99759; 99758; 99757; 99756; 99755; 99754; 99753; 99752; 99751; 99750; 99749;
99748; 99747; 99746; 99745; 99744; 99743; 99742; 99741; 99740; 99739; 99738;
99737; 99736; 99735; 99734; 99733; 99732; 99731; 99730; 99729; 99728; 99727;
99726; 99725; 99724; 99723; 99722; 99721; 99720; 99719; 99718; 99717; 99716;
99715; 99714; 99713; 99712; 99711; 99710; 99709; 99708; 99707; 99706; 99705;
99704; 99703; 99702; . . . ]
Doggy bag
• fonctions
• valeurs de 1ère class
• définition par filtrage par motif
• evaluation d’une application
• substitution
• évaluation paresseuse
• récurrence terminale
• pile d’exécution
• erreur de “stack overflow”
• appel terminal d’une fonction
Exercices
Transformez les récurrences suivantes en récurrences terminales:
• la factorielle:
l e t r e c f a c t n = match n w i t h
| 0 −> 1
| n −> n ∗ ( f a c t ( n − 1 ) ) ; ;
v a l f a c t : i n t −> i n t = <fun>
• itération d’une fonction sur une liste:
# l e t r e c f o l d _ r i g h t f l b = match l w i t h
| [ ] −> b
| t : : r −> f t ( f o l d _ r i g h t f r b ) ; ;
v a l f o l d _ r i g h t : ( ’ a−> ’ b−> ’ b)−> ’ a l i s t −> ’ b−> ’ b=<fun>
• Fibonacci:
# l e t r e c f i b n = match n w i t h
| 0 | 1−> n
| n −> f i b ( n−1)+ f i b ( n − 2 ) ; ;
v a l f i b : i n t −> i n t = <fun>
Évaluer l’efficacité des deux variants à l’aide de la fonction
[Link] () (voir module Sys).
