Noyau fonctionnel d'Objective CAML
Comme tout langage fonctionnel, Objective CAML est un langage d'expressions
comprenant principalement la création de fonctions et l'application de
celles-ci. Le résultat du calcul d'une de ces expressions est une
valeur du langage et l'exécution d'un programme est le calcul de
toutes les expressions le constituant.
Valeurs, fonctions et types de base
Les nombres entiers et flottants, les caractères,
les chaînes de caractères et les booléens sont prédéfinis en Objective CAML.
Nombres
On distingue les nombres entiers1 de type int et les nombres flottants de type
float. Objective CAML suit la norme IEEE 7542 pour
représenter les nombres flottants en double précision. Les
opérations sur les entiers et sur les flottants sont décrites à la
figure
2.1. Notons que lorsque le résultat d'une
opération entière sort de l'intervalle de définition des valeurs
de type int, cela ne produit pas une erreur mais le résultat
est un entier dans l'intervalle des entiers du système. En d'autres
termes, toutes les opérations sur les entiers sont des opérations
modulo les bornes de l'intervalle.
| nombres entiers |
nombres flottants |
| + |
addition |
| - |
soustraction et moins unaire |
| * |
multiplication |
| / |
division entière |
| mod |
reste de la division entière |
|
| +. |
addition |
| -. |
soustraction et moins unaire |
| *. |
multiplication |
| /. |
division |
| ** |
exponentiation |
|
# 1 ;;
- : int = 1
# 1 + 2 ;;
- : int = 3
# 9 / 2 ;;
- : int = 4
# 11 mod 3 ;;
- : int = 2
(* limites de la représentation *)
(* des entiers *)
# 2147483650 ;;
- : int = 2
|
# 2.0 ;;
- : float = 2
# 1.1 +. 2.2 ;;
- : float = 3.3
# 9.1 /. 2.2 ;;
- : float = 4.13636363636
# 1. /. 0. ;;
- : float = Inf
(* limites de la représentation *)
(* des flottants *)
# 222222222222.11111 ;;
- : float = 222222222222
|
Figure 2.1 : opérations sur les nombres
Différence entre nombres entiers et flottants
Des valeurs ayant des types différents comme float et
int ne peuvent pas être directement comparées. Mais
il existe des fonctions de conversion (float_of_int et
int_of_float) de l'un vers l'autre.
# 2 = 2.0 ;;
Characters 5-8:
This expression has type float but is here used with type int
# 3.0 = float_of_int 3 ;;
- : bool = true
De même, les opérateurs sur les flottants sont distincts de ceux sur
les entiers.
# 3 + 2 ;;
- : int = 5
# 3.0 +. 2.0 ;;
- : float = 5
# 3.0 + 2.0 ;;
Characters 0-3:
This expression has type float but is here used with type int
# sin 3.14159 ;;
- : float = 2.65358979335e-06
Un calcul non défini, comme une division entière par zéro,
déclenchera une exception (voir page ??) qui
interrompt le calcul. Les nombres flottants ont une représentation
pour les valeurs infinies (affichées comme Inf) et les calculs
non définis (affichés comme NaN3).
Les principales fonctions sur les nombres flottants sont décrites à la
figure 2.2.
| fonctions sur les flottants |
fonctions trigonométriques |
| ceil |
|
| floor |
|
| sqrt |
racine carrée |
| exp |
exponentielle |
| log |
log népérien |
| log10 |
log en base 10 |
|
| cos |
cosinus |
| sin |
sinus |
| tan |
tangente |
| acos |
arccosinus |
| asin |
arcsinus |
| atan |
arctangente |
|
# ceil 3.4 ;;
- : float = 4
# floor 3.4 ;;
- : float = 3
# ceil (-.3.4) ;;
- : float = -3
# floor (-.3.4) ;;
- : float = -4
|
# sin 1.57078 ;;
- : float = 0.999999999867
# sin (asin 0.707) ;;
- : float = 0.707
# acos 0.0 ;;
- : float = 1.57079632679
# asin 3.14 ;;
- : float = NaN
|
Figure 2.2 : fonctions sur les flottants
Caractères et Chaînes
Les caractères, type char, correspondent aux entiers
compris entre 0 et 255 selon le codage ASCII pour les 128 premiers.
Les fonctions
char_of_int et int_of_char permettent les
conversions entre entiers et caractères.
Les chaînes de caractères, type string, sont des
suites de caractères de longueur connue (inférieure à 224-6).
L'opérateur de concaténation est .
Les fonctions int_of_string, string_of_int,
string_of_float et float_of_string effectuent
les différentes conversions entre nombres et chaînes de
caractères.
# 'B' ;;
- : char = 'B'
# int_of_char 'B' ;;
- : int = 66
# "est une chaîne" ;;
- : string = "est une cha\238ne"
# (string_of_int 1987) ^ " est l'année de la création de CAML" ;;
- : string = "1987 est l'ann\233e de la cr\233ation de CAML"
Même si une chaîne contient les caractères d'un nombre, il ne
sera pas possible de l'utiliser dans des opérations sur les
nombres sans effectuer une conversion explicite.
# "1999" + 1 ;;
Characters 1-7:
This expression has type string but is here used with type int
# (int_of_string "1999") + 1 ;;
- : int = 2000
Les nombreuses fonctions sur les chaînes de caractères sont regroupées
dans le module String (voir page ??).
Booléens
Un booléen appartient à un ensemble formé de deux valeurs :
true et false. Les opérateurs de base sont
décrits à la figure 2.3. Pour des raisons historiques, les
opérateurs << et >> et << ou >> possèdent deux formes.
| not |
négation |
| && |
et séquentiel |
| || |
ou séquentiel |
|
| |
| & |
synonyme pour && |
| or |
synonyme pour || |
| |
|
Figure 2.3 : opérateurs sur les booléens
# true ;;
- : bool = true
# not true ;;
- : bool = false
# true && false ;;
- : bool = false
Les opérateurs && et ||, ou leurs synonymes,
évaluent leur argument de gauche et, selon sa valeur, évaluent leur
argument à droite. Ils peuvent se réécrire sous forme de structures
conditionnelles (voir page ??).
| = |
égalité structurelle |
| == |
égalité physique |
| <> |
négation de = |
| != |
négation de == |
|
| < |
inférieur |
| > |
supérieur |
| <= |
inférieur ou égal |
| >= |
supérieur ou égal |
|
Figure 2.4 : opérateurs d'égalité et de comparaison
Les opérateurs d'égalité et de comparaison sont décrits à la figure
2.4.
Ils sont polymorphes, c'est-à-dire qu'ils sont aussi bien utilisables
pour comparer deux entiers que deux chaînes de caractères. La seule
contrainte reste que leurs deux opérandes doivent être du même type
(voir page ??).
# 1<=118 && (1=2 || not(1=2)) ;;
- : bool = true
# 1.0 <= 118.0 && (1.0 = 2.0 || not (1.0 = 2.0)) ;;
- : bool = true
# "un" < "deux" ;;
- : bool = false
# 0 < '0' ;;
Characters 4-7:
This expression has type char but is here used with type int
L'égalité structurelle teste l'égalité de deux valeurs en explorant
leur structure, alors que l'égalité physique teste si les deux valeurs
occupent la même zone mémoire. Ces deux égalités retournent le même
résultat pour les valeurs simples : booléens, caractères, entiers et
constructeurs constants (page ??).
Warning
Les nombres flottants et les chaînes de caractères sont considérés
comme des valeurs structurées.
Unité
Le type unit décrit un ensemble ne possédant qu'une seule valeur notée : ().
# () ;;
- : unit = ()
Cette valeur sera plus particulièrement utilisée dans les programmes
impératifs (3, page ??) pour les
fonctions qui effectuent des effets de bord. Les fonctions dont le
résultat est la valeur () simulent la notion de procédure
qui n'existe pas en Objective CAML comme le fait le type void dans le
langage C.
Produit cartésien, n-uplet
Des valeurs de types différents peuvent être regroupées en
couple ou plus généralement en n-uplets. Les valeurs constituant
un n-uplet sont séparées par une virgule. Le constructeur de type
* indique un n-uplet. Le type int * string est le
type des couples dont le premier élément est un entier (de type
int) et le second une chaîne de caractères (de type
string).
# ( 12 , "octobre" ) ;;
- : int * string = 12, "octobre"
Lorsqu'il n'y a pas ambiguïté, on écrit plus simplement :
# 12 , "octobre" ;;
- : int * string = 12, "octobre"
Les fonctions fst et snd permettent d'accéder au premier et au second élément d'un couple.
# fst ( 12 , "octobre" ) ;;
- : int = 12
# snd ( 12 , "octobre" ) ;;
- : string = "octobre"
Ces deux fonctions acceptent des couples dont les composants sont de type quelconque. Elles sont polymorphes, à l'instar de l'égalité.
# fst;;
- : 'a * 'b -> 'a = <fun>
# fst ( "octobre", 12 ) ;;
- : string = "octobre"
Le type int * char * string est celui des
triplets dont le premier élément est de type int, le
deuxième de type char et le troisième de type
string. Ses valeurs s'écrivent
# ( 65 , 'B' , "ascii" ) ;;
- : int * char * string = 65, 'B', "ascii"
Warning
Les fonctions fst et snd
appliquées à un n-uplet, autre qu'un couple, provoquent une erreur
de typage.
# snd ( 65 , 'B' , "ascii" ) ;;
Characters 7-25:
This expression has type int * char * string but is here used with type
'a * 'b
Il y a effectivement une différence entre le type d'un couple et celui
d'un triplet. Le type int * int * int est différent
des types (int * int) * int et int * (int * int).
Les accesseurs d'un triplet (et des autres n-uplets) ne sont
pas définis dans la bibliothèque de base. On utilisera le filtrage de
motifs pour les définir si besoin est (voir page
??).
Listes
Des valeurs d'un même type peuvent être regroupées en liste. Une
liste peut être soit vide soit constituée d'éléments du même
type.
# [] ;;
- : 'a list = []
# [ 1 ; 2 ; 3 ] ;;
- : int list = [1; 2; 3]
# [ 1 ; "deux" ; 3 ] ;;
Characters 15-18:
This expression has type int list but is here used with type string list
La fonction qui ajoute un élément en tête de liste est
l'opérateur infixe :: . C'est l'analogue du cons de
Lisp.
# 1 :: 2 :: 3 :: [] ;;
- : int list = [1; 2; 3]
La concaténation de deux listes est aussi un opérateur infixe @.
# [ 1 ] @ [ 2 ; 3 ] ;;
- : int list = [1; 2; 3]
# [ 1 ; 2 ] @ [ 3 ] ;;
- : int list = [1; 2; 3]
Les autres fonctions de manipulation des listes sont définies dans
la bibliothèque List. Les fonctions hd et
tl de cette bibliothèque donnent respectivement la tête
et la queue d'une liste quand ces valeurs existent. On note ces
fonctions List.hd et List.tl pour indiquer au
système qu'il doit les trouver dans le module
List4.
# List.hd [ 1 ; 2 ; 3 ] ;;
- : int = 1
# List.hd [] ;;
Uncaught exception: Failure("hd")
Dans ce dernier exemple, il est effectivement problématique de vouloir
récupérer le premier élément d'une liste vide. C'est pour cela que
le système déclenche une exception (voir page
??).
Structure de contrôle conditionnelle
Une des structures de contrôle indispensable pour tout langage de
programmation est la structure dite conditionnelle (ou alternative)
qui oriente le calcul en fonction d'une condition.
Syntaxe
if expr1 then expr2 else
expr3
L'expression expr1 est de type bool. Les expressions
expr2 et expr3 doivent être du même type, quel
qu'il soit.
# if 3=4 then 0 else 4 ;;
- : int = 4
# if 3=4 then "0" else "4" ;;
- : string = "4"
# if 3=4 then 0 else "4";;
Characters 20-23:
This expression has type string but is here used with type int
Une expression conditionnelle est, elle aussi, une expression et son
calcul retourne une valeur.
# (if 3=5 then 8 else 10) + 5 ;;
- : int = 15
Remarque
La branche else peut être omise, mais, dans ce cas elle est
implicitement remplacée par else (). En conséquence le type
de l'expression expr2 doit être unit (voir page
??).
Déclarations de valeurs
Une déclaration associe un nom à une valeur. On distingue les
déclarations globales des déclarations locales. Dans
le premier cas, les noms déclarés sont connus de toutes les
expressions suivant la déclaration ; dans le second, les noms déclarés
ne sont connus que d'une expression. Il est également possible de
déclarer simultanément plusieurs associations nom-valeur.
Déclarations globales
Syntaxe
let nom = expr ;;
Une déclaration globale définit l'association du nom nom à la
valeur de l'expression expr qui sera connue de toutes les
expressions ultérieures.
# let an = "1999" ;;
val an : string = "1999"
# let x = int_of_string(an) ;;
val x : int = 1999
# x ;;
- : int = 1999
# x + 1 ;;
- : int = 2000
# let nouvel_an = string_of_int (x + 1) ;;
val nouvel_an : string = "2000"
Déclarations globales simultanées
Syntaxe
| let nom1 = expr1 |
| and nom2 = expr2 |
| : |
| and nomn = exprn ;; |
Une déclaration simultanée déclare au même niveau différents
symboles. Ils ne seront connus qu'à la fin de toutes les
déclarations.
# let x = 1 and y = 2 ;;
val x : int = 1
val y : int = 2
# x + y ;;
- : int = 3
# let z = 3 and t = z + 2 ;;
Characters 18-19:
Unbound value z
Il est possible de regrouper plusieurs déclarations globales dans
une même phrase, l'affichage de leur type et de leur valeur
n'intervient alors qu'à la fin de la phrase marquée par le double « ;; ».
Ces déclarations sont
évaluées séquentiellement à la différence d'une déclaration combinée.
# let x = 2
let y = x + 3 ;;
val x : int = 2
val y : int = 5
Une déclaration globale peut être masquée par une nouvelle déclaration du
même nom (voir page ??).
Déclarations locales
Syntaxe
let nom = expr1 in
expr2;;
Le nom nom n'est connu que pour le calcul de
expr2. La déclaration locale lui associe la valeur de
expr1.
# let xl = 3 in xl * xl ;;
- : int = 9
La déclaration locale liant xl à la valeur 3 n'est
conservée que pour le temps du calcul de xl * xl.
# xl ;;
Characters 1-3:
Unbound value xl
Une déclaration locale masque toute déclaration antérieure du
même nom, mais l'ancienne valeur est retrouvée lorsque l'on sort
de la portée de la déclaration locale :
# let x = 2 ;;
val x : int = 2
# let x = 3 in x * x ;;
- : int = 9
# x * x ;;
- : int = 4
Une déclaration locale est une expression et peut donc être
utilisée pour construire d'autres expressions :
# (let x = 3 in x * x) + 1 ;;
- : int = 10
Les déclarations locales peuvent aussi être simultanées.
Syntaxe
| let |
nom1 = expr1 |
| and |
nom2 = expr2 |
| : |
| and |
nomn = exprn |
| in |
expr ;; |
# let a = 3.0 and b = 4.0 in sqrt (a*.a +. b*.b) ;;
- : float = 5
# b ;;
Characters 0-1:
Unbound value b
Expressions fonctionnelles, fonctions
Une expression fonctionnelle est constituée d'un paramètre et
d'un corps. Le paramètre formel est un nom de variable et le
corps une expression. On dit que le paramètre est
abstrait. C'est pour cela qu'une expression fonctionnelle est
aussi appelée abstraction.
Syntaxe
function p -> expr
Ainsi la fonction qui élève au carré son argument s'écrit :
# function x -> x*x ;;
- : int -> int = <fun>
Le système Objective CAML déduit son type. Le type fonctionnel
int -> int indique une fonction attendant un paramètre de
type int et retournant une valeur de type int.
L'application d'une fonction à un argument s'écrit comme la fonction
suivie par l'argument.
# (function x -> x * x) 5 ;;
- : int = 25
Le calcul d'une application revient à calculer le corps de la fonction,
ici x * x, où le paramètre formel, x, est remplacé
par la valeur de l'argument (ou paramètre d'appel, ou encore
paramètre effectif), ici 5.
Dans la construction d'une expression fonctionnelle, expr est
une expression quelconque. En particulier, expr peut
elle-même être une expression fonctionnelle.
# function x -> (function y -> 3*x + y) ;;
- : int -> int -> int = <fun>
Les parenthèses ne sont pas obligatoires. On peut écrire plus
simplement :
# function x -> function y -> 3*x + y ;;
- : int -> int -> int = <fun>
Le type de cette expression peut être lu de la façon usuelle
comme le type d'une fonction qui attend deux entiers et retourne une
valeur entière. Mais dans le cadre d'un langage fonctionnel comme
Objective CAML il s'agit plus exactement du type d'une fonction qui attend
un entier et retourne une valeur fonctionnelle de type
int -> int :
# (function x -> function y -> 3*x + y) 5 ;;
- : int -> int = <fun>
On peut, bien entendu, utiliser l'expression fonctionnelle de
façon usuelle en l'appliquant à deux arguments. On écrit :
# (function x -> function y -> 3*x + y) 4 5 ;;
- : int = 17
Lorsque l'on écrit f a b, il y a un parenthésage implicite à
gauche ce qui rend cette expression équivalente à :
(f a) b.
Revenons sur le détail de l'application
(function x -> function y -> 3*x + y) 4 5
Pour calculer la valeur de cette expression, il faut calculer la
valeur de
(function x -> function y -> 3*x + y) 4
qui est une expression fonctionnelle équivalente à
function y -> 3*4 + y
obtenue en remplaçant x par 4 dans
3*x + y.
En appliquant cette valeur (qui est une fonction) à 5 on
obtient la valeur finale 3*4+5 = 17 :
# (function x -> function y -> 3*x + y) 4 5 ;;
- : int = 17
Arité d'une fonction
On appelle arité d'une fonction le nombre de ces arguments.
L'usage, hérité des mathématiques veut que les arguments d'une
fonction soient donnés entre parenthèse après le nom de la
fonction. On écrit : f(4,5). Nous venons de voir qu'en Objective CAML,
on écrit plutôt : f 4 5. On peut, bien entendu, en Objective CAML
écrire une expression fonctionnelle que l'on applique à (4,5) :
# function (x,y) -> 3*x + y ;;
- : int * int -> int = <fun>
Mais, comme l'indique son type, cette dernière expression, n'attend
pas deux, mais un seul argument : un couple d'entiers. Tenter
d'appliquer deux argument à une fonction qui attend un couple ou
tenter d'appliquer un couple à une fonction qui attend deux
arguments provoquent une erreur de typage :
# (function (x,y) -> 3*x + y) 4 5 ;;
Characters 29-30:
This expression has type int but is here used with type int * int
# (function x -> function y -> 3*x + y) (4, 5) ;;
Characters 39-43:
This expression has type int * int but is here used with type int
Syntaxe alternative
Il existe une manière plus compacte d'écrire des expressions
fonctionnelles à plusieurs paramètres. C'est une survivance des
anciennes versions du langage Caml. Sa forme est la suivante :
Syntaxe
fun p1 ...pn
-> expr
Elle permet de ne pas répéter le mot clé function ni les
flèches. Elle est équivalente à la traduction suivante :
function p1 -> -> function pn -> expr
# fun x y -> 3*x + y ;;
- : int -> int -> int = <fun>
# (fun x y -> 3*x + y) 4 5 ;;
- : int = 17
On la rencontre encore souvent, en particulier dans les bibliothèques
fournies avec la distribution d'Objective CAML.
Fermeture
Objective CAML considère une expression
fonctionnelle comme toute autre expression et sait calculer sa
valeur. La valeur retournée par le calcul
d'une expression fonctionnelle est
appelée une fermeture. Toute expression Objective CAML est
évaluée dans un environnement constitué des associations
noms-valeurs provenant des déclarations précédant l'expression à
calculer. On peut décrire une fermeture comme le triplet constitué
du nom du paramètre formel, du corps de la fonction et
de l'environnement de l'expression. On a besoin de conserver cet
environnement car le corps d'une expression fonctionnelle peut
utiliser, en plus des paramètres formels, toute autre variable
déclarée précédemment. Ces variables sont dites libres
dans l'expression fonctionnelle. On aura besoin de leur valeur lorsque
l'expression fonctionnelle sera appliquée.
# let m = 3 ;;
val m : int = 3
# function x -> x + m ;;
- : int -> int = <fun>
# (function x -> x + m) 5 ;;
- : int = 8
Lorsque
l'application d'une fermeture à un argument retourne une nouvelle
fermeture, celle-ci possède dans son environnement toutes les
associations nécessaires à une future application. Le paragraphe sur
la portée des variables (voir page ??)
détaille cette notion. Nous reviendrons sur le représentation mémoire
d'une fermeture au chapitre 4 (page
??) ainsi qu'au chapitre 12 (page
??).
Les expressions fonctionnelles utilisées jusqu'à présent sont
anonymes. Il est assez pratique de pouvoir les nommer.
Déclarations de valeurs fonctionnelles
On déclare une valeur fonctionnelle de la même manière que les autres
valeurs du langage par la construction let.
# let succ = function x -> x + 1 ;;
val succ : int -> int = <fun>
# succ 420 ;;
- : int = 421
# let g = function x -> function y -> 2*x + 3*y ;;
val g : int -> int -> int = <fun>
# g 1 2;;
- : int = 8
Pour simplifier l'écriture la notation suivante est
acceptée :
Syntaxe
let nom p1 ... pn
= expr
qui est équivalente à la forme suivante :
let nom = function p1 -> -> function pn -> expr
Les déclarations suivantes de succ et de g sont équivalentes
à leur déclaration
précédente.
# let succ x = x + 1 ;;
val succ : int -> int = <fun>
# let g x y = 2*x + 3*y ;;
val g : int -> int -> int = <fun>
On découvre le caractère pleinement fonctionnel d'Objective CAML dans
l'exemple suivant où la fonction h1 est obtenue par
application de g à un seul entier. On parle alors
d'application partielle :
# let h1 = g 1 ;;
val h1 : int -> int = <fun>
# h1 2 ;;
- : int = 8
On peut aussi, à partir de g, définir une fonction h2
en fixant la valeur du second paramètre (y) de g :
# let h2 = function x -> g x 2 ;;
val h2 : int -> int = <fun>
# h2 1 ;;
- : int = 8
Déclaration de fonctions infixes
Certaines fonctions à deux arguments peuvent être appliquées sous
forme infixe. C'est le cas de l'addition sur les entiers. On écrit
3 + 5 pour l'application de + à
3 et 5. Pour utiliser le symbole + comme
valeur fonctionnelle classique, il faut syntaxiquement l'indiquer en
entourant ce symbole infixe par des parenthèses.
La syntaxe est la suivante :
Syntaxe
(op)
L'exemple suivant définit la fonction succ en utilisant
(+).
# (+) ;;
- : int -> int -> int = <fun>
# let succ = (+) 1 ;;
val succ : int -> int = <fun>
# succ 3 ;;
- : int = 4
Il est aussi possible de définir de nouveaux opérateurs. On définit
un opérateur ++ d'addition de couples d'entiers
# let (++) c1 c2 = (fst c1)+(fst c2), (snd c1)+(snd c2) ;;
val ++ : int * int -> int * int -> int * int = <fun>
# let c = (2,3) ;;
val c : int * int = 2, 3
# c ++ c ;;
- : int * int = 4, 6
Il y a une limitation importante sur les opérateurs possibles. Ils ne
doivent contenir que des symboles (tels *, +,
$, etc. ) à l'exclusion des lettres et des chiffres. Font
exception à la règle certaines fonctions prédéfinies comme
infixes dont la liste suit :
or mod land lor lxor lsl lsr asr.
Fonctions d'ordre supérieur
Une valeur fonctionnelle (une fermeture) peut être retournée comme
résultat. Elle peut également être prise comme argument d'une
fonction. Les fonctions prenant en argument ou retournant des valeurs
fonctionnelles sont dites d'ordre supérieur.
# let h = function f -> function y -> (f y) + y ;;
val h : (int -> int) -> int -> int = <fun>
Remarque
L'application est parenthésée à gauche, mais les types
fonctionnels sont parenthésés à droite. Ainsi le type de la
fonction h peut s'écrire
(int -> int) -> int -> int
ou
(int -> int) -> (int -> int)
Les fonctions d'ordre supérieur offrent une possibilité
élégante de traiter les listes. Par exemple la fonction
List.map permet d'appliquer une fonction à tous les
éléments d'une liste et de retourner la liste des résultats.
# List.map ;;
- : ('a -> 'b) -> 'a list -> 'b list = <fun>
# let square x = string_of_int (x*x) ;;
val square : int -> string = <fun>
# List.map square [1; 2; 3; 4] ;;
- : string list = ["1"; "4"; "9"; "16"]
Autre exemple, la fonction List.for_all permet de savoir si
tous les éléments d'une liste satisfont un certain critère.
# List.for_all ;;
- : ('a -> bool) -> 'a list -> bool = <fun>
# List.for_all (function n -> n<>0) [-3; -2; -1; 1; 2; 3] ;;
- : bool = true
# List.for_all (function n -> n<>0) [-3; -2; 0; 1; 2; 3] ;;
- : bool = false
Portée des variables
Pour que l'évaluation d'une expression soit possible, il faut que
toutes les variables qui y apparaissent soient définies. C'est en
particulier le cas pour l'expression e de la déclaration
let p = e. Or p n'étant pas encore connue dans
cette expression, cette variable ne peut être présente que si
elle référence une autre valeur issue d'une déclaration antérieure.
# let p = p ^ "-suffixe" ;;
Characters 9-10:
Unbound value p
# let p = "préfixe" ;;
val p : string = "pr\233fixe"
# let p = p ^ "-suffixe" ;;
val p : string = "pr\233fixe-suffixe"
En Objective CAML, les variables sont liées statiquement. L'environnement
utilisé pour exécuter l'application d'une fermeture est celui de
sa déclaration (portée statique) et non celui courant au moment de
l'application (portée dynamique).
# let p = 10 ;;
val p : int = 10
# let k x = (x, p, x+p) ;;
val k : int -> int * int * int = <fun>
# k p ;;
- : int * int * int = 10, 10, 20
# let p = 1000 ;;
val p : int = 1000
# k p ;;
- : int * int * int = 1000, 10, 1010
La fonction k possède une variable libre :
p. Celle-ci étant définie dans l'environnement global, la
définition de k est acceptée. La liaison entre le nom
p et la valeur 10 dans l'environnement de la
fermeture k est statique, c'est-à-dire ne dépend pas de la
dernière définition de p.
Déclarations récursives
Une déclaration de variable est dite récursive
si elle utilise son propre identificateur dans sa définition.
Cette possibilité est principalement utilisée pour les
fonctions, notamment pour simuler une définition par récurrence.
Nous
venons de voir que la déclaration let ne le permet pas. Pour
déclarer une fonction récursive on utilisera une construction syntaxique
dédiée.
Syntaxe
let rec nom = expr ;;
On peut également utiliser la facilité syntaxique des définitions de
valeurs fonctionnelles en indiquant les paramètres des fonctions :
Syntaxe
let rec nom p1 ...pn
= expr ;;
En guise d'exemple, voici la fonction sigma qui calcule la somme
des entiers (positifs) compris entre 0 et la valeur de son
argument.
# let rec sigma x = if x = 0 then 0 else x + sigma (x-1) ;;
val sigma : int -> int = <fun>
# sigma 10 ;;
- : int = 55
On peut remarquer que cette fonction risque de ne pas terminer
si son argument est strictement négatif.
Une valeur récursive est en général une fonction. Et le
compilateur rejette certaines déclarations récursives dont la
valeur n'est pas fonctionnelle :
# let rec x = x + 1 ;;
Characters 13-18:
This kind of expression is not allowed as right-hand side of `let rec'
Nous verrons cependant que dans certains cas de telles déclarations
sont admises (voir page ??).
La déclaration let rec peut être combinée avec la
construction and. Dans ce cas, toutes les fonctions définies
au même niveau sont connues dans le corps de toutes les autres. Cela
permet, entre autres, des déclarations de fonctions mutuellement
récursives.
# let rec pair n = (n<>1) && ((n=0) or (impair (n-1)))
and impair n = (n<>0) && ((n=1) or (pair (n-1))) ;;
val pair : int -> bool = <fun>
val impair : int -> bool = <fun>
# pair 4 ;;
- : bool = true
# impair 5 ;;
- : bool = true
De même, les déclarations locales peuvent être
récursives. Cette nouvelle définition de sigma teste la
validité de l'argument avant d'effectuer le calcul de la somme
définie par une fonction locale sigma_rec.
# let sigma x =
let rec sigma_rec x = if x = 0 then 0 else x + sigma_rec (x-1) in
if (x<0) then "erreur : argument négatif"
else "sigma = " ^ (string_of_int (sigma_rec x)) ;;
val sigma : int -> string = <fun>
Remarque
La nécessité de donner une valeur de retour qui soit de
même type, que l'argument soit négatif ou non, nous a poussé à
rendre le résultat sous forme d'une chaîne de caractères. Car
quelle valeur doit rendre sigma quand son argument est
négatif ? Nous verrons la bonne façon de régler ce
problème en utilisant les exceptions (voir page
??).
Polymorphisme et contrainte de type
Un certain nombre de fonctions exécutent le même code pour des
arguments ayant des types différents. Par exemple, la création
d'un couple à partir de deux valeurs ne nécessite pas d'avoir des
fonctions différentes pour chaque type connu du
système5. De même, l'accès au
premier champ d'un couple n'a pas à être différencié selon le
type de la valeur de ce premier champ.
# let make_pair a b = (a,b) ;;
val make_pair : 'a -> 'b -> 'a * 'b = <fun>
# let p = make_pair "papier" 451 ;;
val p : string * int = "papier", 451
# let a = make_pair 'B' 65 ;;
val a : char * int = 'B', 65
# fst p ;;
- : string = "papier"
# fst a ;;
- : char = 'B'
Les fonctions dont l'un des paramètres ou la valeur de retour est
d'un type qu'il n'est pas nécessaire de préciser sont dites
polymorphes. Le synthétiseur de types contenu dans le compilateur
d'Objective CAML trouve le type le plus général pour chaque expression.
Dans ce cas, Objective CAML utilise des variables, ici
'a et 'b, pour désigner ces types généraux.
Ces variables sont instanciées par le type
de l'argument lors de l'application de la fonction.
Avec les fonctions polymorphes d'Objective CAML nous cumulons les avantages
de pouvoir écrire un code générique utilisable pour des valeurs
de tout type, tout en conservant la sûreté d'exécution du typage
statique. En effet, bien que make_pair soit polymorphe, la
valeur créée par (make_pair 'B' 65) possède un type bien
précis qui est différent de celui de
(make_pair "papier" 451).
En outre, la vérification des types est effectuée à la
compilation, donc la généricité du code ne nuit pas à
l'efficacité du programme.
Exemples de fonctions et valeurs polymorphes
Les exemples suivants de fonctions polymorphes possèdent
des paramètres fonctionnels dont le type est paramétré.
La fonction app applique une fonction à un argument.
# let app = function f -> function x -> f x ;;
val app : ('a -> 'b) -> 'a -> 'b = <fun>
On peut donc l'appliquer à la fonction impair définie
précédemment :
# app impair 2;;
- : bool = false
La fonction identité (id ) prend un paramètre et le retourne
tel quel.
# let id x = x ;;
val id : 'a -> 'a = <fun>
# app id 1 ;;
- : int = 1
La fonction compose prend deux fonctions et une autre
valeur pour composer ces l'application de ces deux fonctions sur cette
valeur.
# let compose f g x = f (g x) ;;
val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
# let add1 x = x+1 and mul5 x = x*5 in compose mul5 add1 9 ;;
- : int = 50
On voit que le résultat de g doit être de même
type que le paramètre de f.
Les valeurs non fonctionnelles peuvent elles aussi être
polymorphes. C'est le cas par exemple de la liste vide :
# let l = [] ;;
val l : 'a list = []
L'exemple suivant montre que la synthèse du type provient bien de la
résolution des contraintes d'une application et non de la valeur
obtenue à l'exécution.
# let q = List.tl [2] ;;
val q : int list = []
Le type de List.tl est 'a list -> 'a list, donc cette
fonction appliquée à une liste d'entiers retourne une liste
d'entiers. Le fait qu'à l'exécution ce soit la liste vide qui est
obtenue ne change rien à son type.
Objective CAML engendre des types paramétrés pour toute
fonction qui n'utilise pas la forme de ses arguments.
Ce polymorphisme est appelé paramétrique6.
Contrainte de type
Comme le synthétiseur de types en Caml engendre le type le plus
général, il peut être utile ou nécessaire de préciser le type d'une
expression.
La forme syntaxique d'une contrainte de type est la suivante :
Syntaxe
( expr : t )
Lorsqu'il rencontre une telle contrainte, le synthétiseur de type
en tiendra compte pour la construction du type de l'expression.
L'usage des contraintes de type permet :
-
de rendre visible le type des paramètres d'une fonction ;
- d'interdire l'utilisation d'une fonction en dehors de son cadre ;
- de spécifier le type d'une expression, ce qui sera particulièrement
pratique pour les valeurs physiquement modifiables (voir page
??).
Les exemples suivants montrent l'utilisation de telles contraintes de type
# let add (x:int) (y:int) = x + y ;;
val add : int -> int -> int = <fun>
# let make_pair_int (x:int) (y:int) = x,y;;
val make_pair_int : int -> int -> int * int = <fun>
# let compose_fn_int (f : int -> int) (g : int -> int) (x:int) =
compose f g x;;
val compose_fn_int : (int -> int) -> (int -> int) -> int -> int = <fun>
# let nil = ([] : string list);;
val nil : string list = []
# 'H'::nil;;
Characters 5-8:
This expression has type string list but is here used with type char list
Cette restriction du polymorphisme permet de mieux contrôler le type
des expressions en restreignant le polymorphisme du type
déduit par le système. On peut utiliser n'importe quel type défini,
pouvant contenir des variables de type, comme le montre l'exemple
suivant :
# let llnil = ([] : 'a list list) ;;
val llnil : 'a list list = []
# [1;2;3]:: llnil ;;
- : int list list = [[1; 2; 3]]
Le symbole llnil est une liste de listes de n'importe quel
type.
Il s'agit ici de contraintes et non d'un typage explicite
remplaçant la synthèse de type d'Objective CAML. En particulier, on ne
peut pas généraliser le type plus que ne le permet l'inférence.
# let add_general (x:'a) (y:'b) = add x y ;;
val add_general : int -> int -> int = <fun>
Les contraintes de type seront utilisées dans les interfaces de modules
(14) ainsi que dans les déclarations de classes
(15).
Exemples
Nous donnons dans ce paragraphe quelques exemples un peu élaborés
de fonctions. La plupart de ces fonctions sont
prédéfinies en Objective CAML. Nous les redéfinissons à titre
<< pédagogique >>.
Ici, le test du cas d'arrêt des fonctions récursives est
réalisé par une conditionnelle.
D'où un style de
programmation plus proche de Lisp. Nous verrons comment donner un
caractère plus ML à ces définitions lorsque nous présenterons
une autre façon de définir des fonctions par cas (voir page
??).
Longueur d'une liste
Commençons par la fonction null qui teste si une liste
est vide.
# let null l = (l = []) ;;
val null : 'a list -> bool = <fun>
On définit alors la fonction size de calcul de la longueur
d'une liste (i.e. le nombre de ses éléments).
# let rec size l =
if null l then 0
else 1 + (size (List.tl l)) ;;
val size : 'a list -> int = <fun>
# size [] ;;
- : int = 0
# size [1;2;18;22] ;;
- : int = 4
La fonction size teste si la liste argument est vide, si oui
elle retourne 0, sinon elle retourne 1 ajouté à la
valeur résultant du calcul de la longueur de la queue de la liste.
Itération de composition
L'expression iterate n f calcule la valeur fn qui
correspond à l'application de f itérée n fois.
# let rec iterate n f =
if n = 0 then (function x -> x)
else compose f (iterate (n-1) f) ;;
val iterate : int -> ('a -> 'a) -> 'a -> 'a = <fun>
La fonction iterate teste si n vaut 0, si oui elle
retourne la fonction identité, sinon elle compose f avec
l'itération de f n-1 fois.
On peut, en utilisant iterate, définir l'élévation à
la puissance comme itération de la multiplication.
# let rec power i n =
let i_times = ( * ) i in
iterate n i_times 1 ;;
val power : int -> int -> int = <fun>
# power 2 8 ;;
- : int = 256
La fonction power itère n fois l'expression fonctionnelle
i_times, puis applique ce résultat à 1, ce qui calcule
bien la puissance n-ième d'un nombre entier.
Table de multiplication
On veut écrire la fonction multab qui calcule la table de
multiplication d'un entier passé en argument.
On définit dans un premier temps la fonction
apply_fun_list telle que, si f_list est une liste de
fonctions, apply_fun_list x f_list retourne la liste des
résultats de l'application de chaque élément de f_list à
x.
# let rec apply_fun_list x f_list =
if null f_list then []
else ((List.hd f_list) x)::(apply_fun_list x (List.tl f_list)) ;;
val apply_fun_list : 'a -> ('a -> 'b) list -> 'b list = <fun>
# apply_fun_list 1 [(+) 1;(+) 2;(+) 3] ;;
- : int list = [2; 3; 4]
La fonction mk_mult_fun_list retourne la liste des
fonctions multipliant leur argument par i,
pour i variant de 0 à n.
# let mk_mult_fun_list n =
let rec mmfl_aux p =
if p = n then [ ( * ) n ]
else (( * ) p) :: (mmfl_aux (p+1))
in (mmfl_aux 1) ;;
val mk_mult_fun_list : int -> (int -> int) list = <fun>
On obtient la table de multiplication de 7 par :
# let multab n = apply_fun_list n (mk_mult_fun_list 10) ;;
val multab : int -> int list = <fun>
# multab 7 ;;
- : int list = [7; 14; 21; 28; 35; 42; 49; 56; 63; 70]
Itération sur les listes
L'appel de la fonction fold_left f a [e1; e2; ... ; en] retourne
f ... (f (f a e1) e2) ... en. Il y a donc n applications.
# let rec fold_left f a l =
if null l then a
else fold_left f ( f a (List.hd l)) (List.tl l) ;;
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
La fonction fold_left permet la définition compacte d'une
fonction de calcul de la somme des éléments d'une liste
d'entiers :
# let sum_list = fold_left (+) 0 ;;
val sum_list : int list -> int = <fun>
# sum_list [2;4;7] ;;
- : int = 13
Ou encore, la concaténation des éléments d'une liste de chaînes :
# let concat_list = fold_left (^) "" ;;
val concat_list : string list -> string = <fun>
# concat_list ["Hello "; "world" ; " "; "!"] ;;
- : string = "Hello world !"