Le langage fonctionnel Caml

En Caml, une fonction est une valeur particulière appelée fermeture et symbolisée par le mot-clé <fun>. Une fermeture est un triplet que nous noterons fermeture ( n -> e , E _c ) où n est un nom : l' argument formel de la fonction, e est une expression : le corps de la fonction et E_c est l'environnement dans lequel la fonction a été construite et dans lequel sa valeur devra être calculée.

Le type d'une fonction est noté t ₁ -> t ₂ où t ₁ et t ₂ sont des expressions de type qui dénotent respectivement le type de départ et le type d'arrivée de la fonction. Le symbole -> est un constructeur de type.

La construction d'une fonction est une expression qui a la forme suivante :

function x -> e

où x est un identificateur et e est une expression. La valeur de cette expression est la fermeture :

fermeture(x -> e, Env_courant)

La fonction suivante, par exemple, calcule le carré de son argument :

#function x -> x * x;;
- : int -> int = <fun>

Une fermeture n'étant pas une valeur affichable, elle est symbolisée par <fun>.

Nous appellerons expression fonctionnelle , une expression dont la valeur est une fonction.

Une fonction est destinée à être appliquée. Soit f une expression fonctionnelle de type t ₁ -> t ₂ et e une expression de type t ₁ . L'application de f à e est une expression de type t ₂ , ayant la forme suivante :

f e

(il suffit tout simplement de juxtaposer la fonction et son argument). La valeur de l'expression e est l' argument effectif de la fonction f . Par exemple :

#(function x -> x * x) 2;;
- : int = 4

La fonction construite ci-dessus est anonyme. Comme toute valeur, une fonction peut être nommée par une définition globale ou locale. Par exemple :

#let carre = function x -> x * x;;
carre : int -> int = <fun>
#let carre = (function x -> x * x) in carre (carre 5);;
- : int = 625

III-A-1. Typage d'une fonction▲

#(function x -> x * x);;
- : int -> int = <fun>

III-A-2. Évaluation d'une construction de fonction▲

function r -> pi *. r *. r

#let pi = 3.14;;
pi : float = 3.14
#let surface_cercle = function r -> pi *. r *. r;;
surface_cercle : float -> float = <fun>
#surface_cercle 10.;;
- : float = 314
#let pi = 3.1416;;
pi : float = 3.1416
#surface_cercle 10.;;
- : float = 314

III-A-3. Type et valeur d'une application de fonction▲

type((function x -> x * x) 2, Env) = int, car type(function x -> x * x, Env) = int -> int et type(2, Env) = int.
val((function x -> x * x) 2, Env) = 4, car val((function x -> x * x), Env) = fermeture(x -> x * x, Env), val(2, Env) = 2 et val(x * x, Env  {x = 2}) = 4

#(function x -> x * x) 2;;
- : int = 4

Considérons la fonction à deux arguments divisible_par , qui appliquée à deux entiers x et y , indique si y est divisible par x . En Caml, cette fonction sera construite comme une fonction qui appliquée à x fournira une fonction qui appliquée à y fournira le résultat cherché :

#let divisible_par =
    function x -> function y -> (y mod x) = 0;;
divisible_par : int -> int -> bool = <fun>
#divisible_par 4 5;;
- : bool = false
#divisible_par 2 4;;
- : bool = true

(la fonction prédéfinie mod calcule le reste de la division de deux entiers).

Une fonction à plusieurs arguments est donc traitée en Caml comme une suite de fonctions à un seul argument. En Caml, l'application est associative à gauche et le constructeur de type -> est associatif à droite. On a :

f x1 x2 … xn  (…((f x1) x2)…) xn
t1 -> (t2 -> …(tn -> t)…) -> t  t1 -> … -> tn -> t

Soit f une fonction de type t ₁ -> … t_k -> … t _n -> t et x ₁ , …, x _k , …, x_n des valeurs de type respectifs t ₁ , …, t _k , …, t _n . Alors :

• f x ₁ … x_n est une application totale de f qui a pour type t  ;
• f x ₁ … x_k est une application partielle de f qui a pour type t _{k +1} -> … -> t _n -> t .

Par exemple, l'expression divisible_par 2 4 est une application totale de la fonction divisible_par et divisible_par 2 en est une application partielle :

#divisible_par 2 4;;
- : bool = true
#divisible_par 2;;
- : int -> bool = <fun>

La fonction divisible_par 2 indique si un entier est pair. On peut lui donner le nom est_pair :

#let est_pair = divisible_par 2;;
est_pair : int -> bool = <fun>
#est_pair 12;;
- : bool = true
#est_pair 17;;
- : bool = false

Une fonction à n arguments construite comme une suite d'applications partielles est dite curryfiée . Ce terme a été adopté en hommage au logicien Haskell Curry.

Les opérateurs prédéfinis infixés tels que + - * / sont eux-mêmes des fonctions à deux arguments. Ils peuvent donc faire l'objet d'applications partielles. Cela nécessite de pouvoir les écrire en position préfixe, ce qui est possible en les faisant précéder du mot-clé prefix. En voici un exemple classique :

#prefix +;;
- : int -> int -> int = <fun>
#let successeur = (prefix +) 1;;
successeur : int -> int = <fun>
#successeur 9;;
- : int = 10

Les deux facilités d'écriture suivantes peuvent rendre plus lisibles la construction d'une fonction à plusieurs arguments ou la définition d'un nom de fonction :

fun x1 … xn -> e  function x1 -> … function xn -> e
let n x1 … xk = e;;  let n = function x1 -> … function xk -> e;;

Par exemple :

#(fun x y -> (y mod x) = 0) 3 9;;
- : bool = true
#let carre x = x * x;;
carre : int -> int = <fun>
#let divisible_par x y = (y mod x) = 0;;
divisible_par : int -> int -> bool = <fun>

On peut indiquer à Caml, par la directive #infix n , qu'une fonction de nom n s'appliquera en position infixe (une directive est une instruction placée dans un programme à destination du compilateur). Par exemple :

#let et x y = x + y;;
et : int -> int -> int = <fun>
##infix "et";;
#2 et 2;;
- : int = 4
#4 et 4;;
- : int = 8

(« …huit et huit font seize… Répétez ! dit le maître … »). Pour pouvoir appliquer à nouveau la fonction en position préfixe, il faut envoyer à Caml la directive #uninfix.

Considérons la session Caml suivante :

#let fac n = if n = 1 then 1 else n * fac (n - 1);;
> Toplevel input:
>let fac n = if n = 1 then 1 else n * fac (n - 1);;
> ^^^
> Variable fac is unbound.

Que s'est il passé ? Une erreur a été signalée car tout nom apparaissant dans une expression doit appartenir à l'environnement dans lequel cette expression est typée puis évaluée. Ce n'est pas le cas du nom fac qui est en cours de définition. Il aurait fallu écrire :

#let rec fac n = if n = 1 then 1 else n * fac (n - 1);;
fac : int -> int = <fun>

Le mot-clé rec indique à Caml que la définition de fac est récursive et donc que le nom fac sera rencontré dans sa définition. Nous appellerons définition récursive une telle définition.

Pour que les règles de typage et d'évaluation d'une définition de fonction données au §II.A soient applicables aux fonctions récursives, il faut que l'environnement de définition soit étendu par une liaison entre le nom de la fonction récursive, son type et sa valeur. Ces deux derniers n'étant pas connus à ce moment-là, ils seront chacun désignés par une variable.

L'environnement ajouté par une définition d'un nom de fonction récursive peut être calculée par la règle suivante :

Illustrons cette règle en calculant l'environnement ajouté par la définition de la fonction fac dans l'environnement Envd . D'après la règle ci-dessus cet environnement est égal à {fac : t = f } où t = type (let rec fac n = if n = 1 then 1 else n * fac (n - 1), Envd  {fac : t }) et f = fermeture ( x -> e , Env_d  {fac = f }).

Rappelons au préalable que let rec fac n = if n = 1 then 1 else n * fac (n - 1) est une écriture simplifiée équivalente à let rec fac = function n -> if n = 1 then 1 else n * fac (n - 1).

Il faut d'abord calculer t = type (function n -> if n = 1 then 1 else n * fac (n - 1), Env  {fac : t }}). Pour cela on applique la règle de typage d'une fonction (cf. ci-dessus § II.A.1) :

1. Soit t ₁ le type de n et t ₂ le type de l'expression if n = 1 then 1 else n * fac (n - 1). Le système de contraintes initial est donc { t = t ₁ -> t ₂ }.
2. Soit t ₃ le type de l'expression n = 1 et t ₄ celui de l'expression n * fac (n - 1). Par définition de l'alternative et sachant que le type de l'expression 1 est int, on a les contraintes suivantes t ₃ = bool et t ₂ = t ₄ = int. Le système de contraintes devient { t = t ₁ -> int, t ₃ = bool, t ₂ = t ₄ = int}.
3. L'expression n = 1 est équivalente à (prefix =) n 1. L'opérateur (prefix =) est de type int -> int -> bool. Sachant que le type de n est t ₁ et que celui de 1 est int, on en déduit les contraintes t ₁ = int et t ₃ = bool. Le système de contraintes devient { t = int -> int, t ₃ = bool, t ₁ = t ₂ = t ₄ = int}.
4. L'expression n * fac (n - 1) est équivalente à (prefix *) n (fac (n - 1)). Soit t 5 le type de l'expression (fac (n - 1)). Sachant que l'opérateur (prefix *) est de type int -> int -> int et que le type de n est t 1, on en déduit les contraintes t ₁ = int (déjà présente), t ₅ = int et t ₄ = int (déjà présente). Le système de contraintes devient { t = int -> int, t ₃ = bool, t ₁ = t ₂ = t ₄ = t ₅ = int }.
5. L'expression (fac (n - 1)) est équivalente à fac (n - 1). Soit t 6 le type de (n - 1). Sachant que type de fac est égal à t qui est égal à int -> int, on en déduit les nouvelle contraintes t ₆ = int et t ₅ = int (déjà présente). Le système de contraintes devient { t = int -> int, t ₃ = bool, t ₂ = int, t ₄ = int, t ₅ = int, t ₆ = int}.
6. L'expression (n - 1) est équivalente à (prefix -) n 1. Sachant que type de l'opérateur prédéfini (prefix -) est égal à int -> int -> int, que le type de n est t ₁ et que celui de 1 est int on en déduit les contraintes t ₁ = int et t ₆ = int (déjà présentes). Le système de contraintes reste donc inchangé.

Le système de contraintes est sans contradiction et contient la contrainte t = int -> int. On a donc :

Env_def(let rec fac = …, Env) = {fac : int -> int = f}
où f = fermeture(n -> if n = 1 then 1 else …, Env  {fac = f})

L'application d'une fonction récursive se déroule de la même façon que celle d'une fonction non récursive. Montrons-le en évaluant fac 2 dans un environnement Env contenant la liaison fac : int -> int = f où f = fermeture (n -> if n = 1 then 1 else n * fac (n - 1), Env _d  {fac = f }). On a :

val(fac 2, Env)
= val(if n = 1 then 1 else n * fac (n - 1), Envd  {fac = f, n = 2})
= val(2 * fac 1, Envd  {fac = f, n = 2})
= 2 * val(fac 1, Envd  {fac = f, n = 2})
= 2 * val(if n = 1 then 1 …, Envd  {fac = f, n = 1})
= 2 * 1
= 2

Plusieurs fonctions sont dites mutuellement récursives lorsqu'elles s'appellent de façon croisée c.-à-d. lorsque le nom de l'une peut apparaître dans le corps de l'autre et inversement. La définition de n fonctions mutuellement récursives de noms f ₁ , …, f_n et de corps respectifs e ₁ , …, e_n est une phrase qui a la forme suivante :

let rec f1 = e1 and … and fn = en ;;

que nous appellerons définition mutuellement récursive .

La règle calculant l'environnement ajouté par une définition récursive (§II.C) se généralise aisément à une définition mutuellement récursives. La fermeture obtenue comme valeur de chaque fonction f_i enfermera les liaisons associées aux noms f ₁ , …, f _n .

Un bon exemple est constitué par les suites de Fibonacci qui sont définies par les équations suivantes :

u0 = 1 ; v0 = 1 ; un = un-1 + 2 * vn-1 ; vn = 3 * un-1 + vn-1

En Caml elles pourront être définies de la façon suivante :

#let rec
    u = function n -> if (n = 0) then 1 else u(n - 1) + 2 * v(n - 1)
and v = function n ->
        if (n = 0) then 1 else 3 * u(n - 1) + v(n - 1);;
u : int -> int = <fun>
v : int -> int = <fun>
#u 3;;
- : int = 37
#v 3;;
- : int = 46