IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Le langage fonctionnel Caml

Support de cours basé sur Caml Light


précédentsommairesuivant

III. Fonctions

Dans ce chapitre nous pénétrons au coeur de Caml, puisque dans ce langage un programme n'est pas autre chose qu'une suite de définitions de valeurs ou de fonctions, suivie d'une expression à évaluer par applications successives d'une fonction à son argument.

En Caml, les fonctions sont des valeurs à part entière : elles peuvent être argument et valeur d'une fonction. Nous étudierons tout d'abord les fonctions à un seul argument : comment les construire et comment les appliquer. Nous montrerons ensuite que les fonctions à plusieurs arguments peuvent être traitées comme une suite de fonctions à un argument. Nous terminerons par l'étude des fonctions récursives.

III-A. Construction et application d'une fonction

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 Ec 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 1 -> t 2 t 1 et t 2 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 :

 
Sélectionnez
function x -> e

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

 
Sélectionnez
fermeture(x -> e, Env_courant)

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

 
Sélectionnez
#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 1 -> t 2 et e une expression de type t 1 . L'application de f à e est une expression de type t 2 , ayant la forme suivante :

 
Sélectionnez
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 :

 
Sélectionnez
#(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 :

 
Sélectionnez
#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

Le typage d'une fonction n'est pas trivial car le type de son argument n'est pas déclaré dans l'expression qui la construit. Il peut être réalisé par la procédure suivante dont l'automatisation nécessite la mise en œuvre de techniques de démonstration automatique.

TYPE D'UNE FONCTION. Soit Env un environnement et function x -> e une fonction à typer dans cet environnement. On désigne par t 1 le type de x (type de départ de la fonction) et par t 2 le type de e (type d'arrivée de la fonction). Une analyse du type de chaque sous-expression qui compose le corps e , permet d'établir un ensemble de contraintes sur t 1 et t 2. Deux cas peuvent alors se présenter :
1) Les contraintes sont compatibles et déterminent complètement t 1 et t 2 , c'est-à-dire qu'il existe deux types Caml a et b tel que t 1 = a et t 2 = b . On a alors type (function x -> e , Env ) = a -> b .
2) Les contraintes sont incompatibles. Cela signifie qu'il y a une erreur de typage.

Considérons, par exemple, la fonction function x -> x * x. Soit t 1 le type de x et t 2 le type de x * x. Puisque * est un opérateur sur les entiers qui produit un entier, l'ensemble des contraintes est { t 1 = int, t 2 = int}. t 1 et t 2 sont complètement déterminés. Le type de cette fonction est donc int -> int. Vérifions-le :

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

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

Les variables (ou noms de valeur) apparaissant dans le corps d'une fonction peuvent être classées en deux catégories : l'argument formel de la fonction est une variable liée , les autres sont des variables libres . Par exemple, dans l'expression fonctionnelle :

 
Sélectionnez
function r -> pi *. r *. r

(où *. est la multiplication des flottants) r est liée et pi est libre. Lors de l'application d'une fonction, l'argument formel est lié à la valeur de son argument effectif. Pour les arguments libres deux choix sont possibles. On peut les lier à la valeur qu'ils avaient dans l'environnement de construction de la fonction ou bien, à la valeur qu'ils ont dans son environnement d'application. On parle de langage à portée statique dans le premier cas et de langage à portée dynamique dans le second.

Caml est un langage à portée statique. Les langages à portée statique assurent la transparence référentielle : quelque soit le contexte où elle apparaît une fonction fournit la même valeur lorsque est appliquée au même argument. Montrons le sur l'exemple suivant :

 
Sélectionnez
#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

On remarque que la redéfinition de pi n'a pas modifié la valeur de l'application de la fonction surface_cercle à 10. Si Caml avait été à portée dynamique la deuxième application aurait eue la valeur 314.16.

Il faut donc que l'environnement dans lequel une fonction a été construite avec le corps de cette fonction. C'est pourquoi, en Caml, une fonction est une fermeture qui réunit l'argument formel de la fonction, son corps et l'environnement dans lequel elle a été définie. La règle d'évaluation d'une définition de fonction est donc la suivante :

VALEUR D'UNE CONSTRUCTION DE FONCTION. Si Env est un environnement et function x -> e est une fonction valide dans Env , alors :
val (function x -> e, Env ) = fermeture ( x -> e , Env ).

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

Les règles de typage et d'évaluation d'une application de fonction sont les suivantes :

TYPE ET VALEUR D'UNE APPLICATION DE FONCTION. Si Env est un environnement et si e1, e2 sont des expressions telles que type(e1, Env) = t1 -> t2 et type(e2, Env) = t1 et val(e1, Env) = fermeture(x -> e, Envc), alors :
type(e1 e2, Env) = t2,
val(e1 e2, Env) = val(e, Envc  {x = val(e2, Env)}).

Considérons, par exemple, l'application (function x -> x * x) 2. On a :

 
Sélectionnez
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 &#61637; {x = 2}) = 4

Vérifions-le :

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

III-B. Fonctions à plusieurs arguments

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é :

 
Sélectionnez
#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 :

 
Sélectionnez
f x1 x2 &#8230; xn &#61626; (&#8230;((f x1) x2)&#8230;) xn
t1 -> (t2 -> &#8230;(tn -> t)&#8230;) -> t &#61626; t1 -> &#8230; -> tn -> t

Soit f une fonction de type t 1 -> … tk -> … t n -> t et x 1 , …, x k , …, xn des valeurs de type respectifs t 1 , …, t k , …, t n . Alors :

  • f x 1 xn est une application totale de f qui a pour type ;
  • f x 1 xk 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 :

 
Sélectionnez
#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 :

 
Sélectionnez
#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 :

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

III-C. Facilités d'écriture

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 :

 
Sélectionnez
fun x1 &#8230; xn -> e &#61626; function x1 -> &#8230; function xn -> e
let n x1 &#8230; xk = e;; &#61626; let n = function x1 -> &#8230; function xk -> e;;

Par exemple :

 
Sélectionnez
#(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 :

 
Sélectionnez
#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.

III-D. Fonctions récursives

Considérons la session Caml suivante :

 
Sélectionnez
#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 :

 
Sélectionnez
#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 :

ENVIRONNEMENT AJOUTE PAR UNE DÉFINITION RÉCURSIVE. Si Env un environnement, si n est un nom de valeur et si function x -> e est une construction de fonction, alors :
Env_def (let rec n = function x -> e , Env ) = { n : t = f },
t = type (function x -> e , Env  { n : t }) et f = fermeture ( x -> e , Env  { n = f }).

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 , Envd  {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 1 le type de n et t 2 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 1 -> t 2 }.
  2. Soit t 3 le type de l'expression n = 1 et t 4 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 3 = bool et t 2 = t 4 = int. Le système de contraintes devient { t = t 1 -> int, t 3 = bool, t 2 = t 4 = 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 1 et que celui de 1 est int, on en déduit les contraintes t 1 = int et t 3 = bool. Le système de contraintes devient { t = int -> int, t 3 = bool, t 1 = t 2 = t 4 = 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 1 = int (déjà présente), t 5 = int et t 4 = int (déjà présente). Le système de contraintes devient { t = int -> int, t 3 = bool, t 1 = t 2 = t 4 = t 5 = 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 6 = int et t 5 = int (déjà présente). Le système de contraintes devient { t = int -> int, t 3 = bool, t 2 = int, t 4 = int, t 5 = int, t 6 = 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 1 et que celui de 1 est int on en déduit les contraintes t 1 = int et t 6 = 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 :

 
Sélectionnez
Env_def(let rec fac = &#8230;, Env) = {fac : int -> int = f}
où f = fermeture(n -> if n = 1 then 1 else &#8230;, Env &#61637; {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 f = fermeture (n -> if n = 1 then 1 else n * fac (n - 1), Env d  {fac = f }). On a :

 
Sélectionnez
val(fac 2, Env)
= val(if n = 1 then 1 else n * fac (n - 1), Envd &#61637; {fac = f, n = 2})
= val(2 * fac 1, Envd &#61637; {fac = f, n = 2})
= 2 * val(fac 1, Envd &#61637; {fac = f, n = 2})
= 2 * val(if n = 1 then 1 &#8230;, Envd &#61637; {fac = f, n = 1})
= 2 * 1
= 2

III-E. Fonctions mutuellement récursives

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 1 , …, fn et de corps respectifs e 1 , …, en est une phrase qui a la forme suivante :

 
Sélectionnez
let rec f1 = e1 and &#8230; 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 fi enfermera les liaisons associées aux noms f 1 , …, f n .

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

 
Sélectionnez
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 :

 
Sélectionnez
#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

précédentsommairesuivant

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2013 Jacques Le Maitre. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.