Chapitre 2
Introduction à la programmation en Caml

2.1 Le calculateur Caml

Avertissement : c’est volontairement qu’au cours de cette section nous suivrons au plus près les notations mathématiques usuelles ce qui, lors d’une première lecture pourra choquer les habitués du langage Caml ou plus généralement d’un langage fonctionnel. Ce n’est que petit à petit que nous nous libérerons de ces notations et en particulier des produits cartésiens et des parenthèses superflues. Pour la même raison, les exemples de ce paragraphe seront la plupart du temps tirés des mathématiques.

2.1.1 Calculs numériques

Nous allons dans un premier temps utiliser Caml en tant que calculatrice évoluée. Pour cela entrons une ligne de calcul en retenant qu’en Caml toute instruction doit se terminer par un double point virgule pour montrer qu’elle est bien achevée et que Caml doit l’évaluer. Faisons quelques calculs élémentaires sur les nombres entiers. Dans le tableau suivant les entrées sont précédées du signe # alors que les résultats donnés par Caml sont précédées du symbole - :1


>       Caml Light version 0.6  
 
#1+1;;  
 - : int = 2  
#34*78;;  
 - : int = 2652  
#1238/45;;  
 - : int = 27  
#8976-2345;;  
 - : int = 6631


Programme 2.1: calculs sur des entiers

Ces calculs appellent quelques commentaires. D’une part, Caml connaît les entiers et sait les reconnaître automatiquement. C’est ainsi que de lui-même il a attribué le type entier (ici int) aux résultats de ces calculs. D’autre part, il sait effectuer les calculs élémentaires sur ces entiers : addition, multiplication, division, soustraction. Remarquons simplement en ce qui concerne la division que le résultat est le quotient entier des deux nombres et non le quotient réel ni le quotient rationnel (d’ailleurs Caml ne connaît pas à l’origine les nombres rationnels).

Essayons les mêmes calculs sur les réels. Ici le point décimal remplace, comme chez les anglo-saxons, la virgule décimale chère aux francophones.


#1.2 + 3.65;;  
 > Toplevel input:  
 >1.2 + 3.65;;  
 >^^^  
 > Expression of type float  
 > cannot be used with type int


Programme 2.2: calculs sur des réels

Caml a donc refusé de faire les calculs considérant que le symbole + est réservé aux entiers (le type int) et ne peut donc pas être utilisé pour des réels (le type float qui désigne le type des réels en virgule flottante). En Caml, il faut faire suivre le symbole d’opération sur les réels du point décimal pour indiquer qu’on demande un calcul portant sur des représentations de nombres réels en virgule flottante : les opérateurs deviennent respectivement  +. , -. , *. , /.


#1.25 +. 2.63;;  
 - : float = 3.88  
#1.2345 *. 6.35678 -. 2.7658;;  
 - : float = 5.08164491  
#5.45674 /. 8.6354;;  
 - : float = 0.631903559766


Programme 2.3: opérations sur les réels

Cette fois-ci, tout s’est bien passé. Caml a reconnu automatiquement le type float des représentations de nombres réels en virgule flottante et a appliqué les opérations correspondantes. Remarquez que ces calculs peuvent s’enchaîner avec les priorités habituelles accordées aux opérateurs, les expressions pouvant en cas de besoin être parenthésées.


#(2.34598 -. 5.6475) *. (4.87654 +. 6.3265) -. 1.368;;  
 - : float = -38.3550606208


Programme 2.4: parenthésages

Votre calculatrice peut faire appel à des fonctions mathématiques usuelles :


#exp(1.) *. cos(4.56);;  
 - : float = -0.412634796919


Programme 2.5: fonctions usuelles

Remarquez le point qui suit le 1, permettant de distinguer l’entier 1 du nombre réel dont la représentation en virgule flottante est 1.00000 ; la même expression écrite sous la forme exp(1) *. cos(4.56) conduit à une erreur car la fonction exponentielle de Caml s’applique uniquement à des réels représentés en virgule flottante.

2.1.2 Variables globales, variables locales

Supposons que nous utilisions une approximation du nombre π. Plutôt que d’entrer tout au long de nos calculs le réel 3.141592653 il peut être agréable de stocker ce nombre une bonne fois pour toutes dans une variable. En Caml, ceci se fait de manière très simple : comme on écrit en mathématiques soit π = 3.141592653 on écrira en Caml let pi=3.141592653;;.


#let pi = 3.141592653;;  
pi : float = 3.141592653


Programme 2.6: définition de constantes

On dit que l’on a effectué une liaison (ici globale car elle est valable pendant toute la session, à moins qu’elle ne soit remise en cause par la suite) entre le symbole pi et la valeur 3.141592653. A partir de maintenant et jusqu’à ce qu’une nouvelle valeur soit attribuée au symbole pi, celui ci prendra dans tout calcul la valeur 3.141592653.


#sin(pi);;  
 - : float = 5.8979322576e-10  
#cos(pi);;  
 - : float = -1  
#tan(pi/. 4.);;  
 - : float = 0.999999999705


Programme 2.7: calculs numériques sur des constantes

Remarquez qu’en ce qui concerne les réels, l’interpréteur Caml est un calculateur numérique et non un calculateur formel : même lorsqu’existe une valeur exacte d’une expression, Caml en donne une valeur approchée avec une précision qui peut dépendre de la machine utilisée.

Rien ne vous empêche par la suite d’attribuer une nouvelle valeur (et au passage un autre type) au symbole pi et de faire de nouveaux calculs avec cette nouvelle valeur et ce nouveau type :


#let pi = 8;;  
 pi : int = 8  
#pi*375;;  
 - : int = 3000


Programme 2.8: redéfinition de constantes

Contrairement à d’autres langages de programmation, les variables de Caml ne sont pas typées de manière rigide. Leurs types peuvent varier au cours d’un même programme suivant les valeurs qui leurs sont attribuées.

Bien souvent, dans un calcul complexe, aussi bien pour gagner du temps que de la place, il peut être commode d’attribuer provisoirement un nom à une sous-expression. Pour éviter que cette attribution n’interfère avec des calculs ultérieurs, il est possible de rendre cette liaison locale à une expression à l’aide de la construction

let ... = ... in ... 

qui signifie en gros posons a = dans l’expression (et uniquement dans cette expression). C’est ainsi que pour calculer l’expression

cos(2 log(sin(1.2)))- 1
exp(log(sin(1.2)))+-1-

il peut être intéressant de calculer d’abord une bonne fois pour toutes log(sin(1.2)). On écrira donc en Caml


#let a = log(sin(1.2)) in (cos(2. *. a)-. 1.)/. (exp(a) +. 1.);;  
 - : float = -0.0051191979432


Programme 2.9: définition locale de constante auxiliaire

Remarquons que l’attribution de la valeur log(sin(1.2)) au symbole a est locale à l’expression. Si par exemple nous avions par ailleurs déjà attribué une valeur au symbole a par une instruction globale let a=14;;, cette valeur n’aurait pas été perdue. Elle aurait tout simplement été masquée à l’intérieur de l’expression évaluée par celle qui lui est provisoirement attribuée et le symbole retrouverait sa valeur première dès la sortie de l’expression.


#let a = 14;;  
 a : int = 14  
#let a = log(sin(1.2)) in (cos(2.*. a)-. 1.)/. (exp(a)+. 1.);;  
 - : float  = -0.0051191979432  
#2*a;;  
 - : int = 28


Programme 2.10: localité des définitions de constantes

Dans la mesure du possible et afin que les différents calculs n’interfèrent pas les uns avec les autres, il est souhaitable de rendre les variables locales. Une erreur fréquente est en effet d’attribuer une valeur à un symbole a, de modifier quelque temps après cette valeur, puis de réutiliser plus loin le symbole a en ayant oublié la modification opérée.

On peut attribuer des valeurs locales ou globales à plusieurs symboles à la fois grâce à une syntaxe étendue de la construction let sous la forme

let ... = ...   and  ... = ...  and ...  

C’est ainsi que globalement on pourra poser :


#let pi = 3.141592653 and e = exp(1.);;  
 pi : float = 3.141592653  
 e : float = 2.71828182846


Programme 2.11: définition de plusieurs constantes

et que localement ou pourra écrire :


#let a = sin(1.35) and b = cos(2.65) in  
     (a +. b)/. (a -. b);;  
 - : float = 0.050686954422


Programme 2.12: définition de plusieurs constantes locales

En CAML 0.7, on peut, pour accroître la lisibilité, utiliser une construction équivalente à la construction let ... in, la construction where. C’est ainsi que la construction

let attribution in expression

peut être remplacée par la construction équivalente

expression where attribution

On pourra donc écrire de façon tout à fait équivalente à la précédente


#(a +. b)/. (a -. b)  
    where a = sin(1.35) and b = cos(2.65);;  
- : float = 0.050686954422


Programme 2.13: construction where

2.1.3 Fonctions d’une variable

Supposons que nous voulions construire la représentation graphique de la fonction x↦→sin(x)log(cos(x)). Nous aurons donc à calculer les valeurs de cette fonction pour différentes valeurs de x. En mathématiques, on pourrait donc définir un nouveau symbole f en posant : soit f la fonction qui à x associe sin(x)log(cos(x)) ce qu’on noterait encore, soit f : x↦→sin(x)log(cos(x)). De la même façon, en Caml, on définira :


#let f = function x -> sin(x) *. log(cos(x));;  
 f : float -> float = <fun>


Programme 2.14: définition de fonction d’une variable

L’interpréteur Caml a constaté que l’on définissait une fonction (d’où le symbole <fun>) et que cette fonction allait des réels dans les réels (d’où le type float -> float). A partir de maintenant nous pouvons utiliser la fonction f au même titre que les fonctions prédéfinies de Caml comme les fonctions trigonométriques élémentaires.


#f(1.);;  
 - : float = -0.51803181231  
#f(1.5);;  
 - : float = -2.64214841544  
#f(3.);;  
 - : float = NAN(036)  
#f(2.);;  
 - : float = NAN(036)  
#f(-0.5);;  
 - : float = 0.062605419808


Programme 2.15: utilisation de fonction définie

Remarquons que Caml a détecté certaines incohérences (logarithme d’un nombre négatif), et plutôt que de renvoyer une erreur a préféré répondre par un NAN, qui est une abréviation de l’anglais Not A Number.

Rien ne vous empêche (et c’est même souvent conseillé) de rendre la définition de la fonction locale à une expression. C’est ainsi que pour calculer l’expression

cos(2-log(sin(1.2)))--1
exp(log(sin(2.56)))+ 1

on peut écrire en Caml :


#let f = function x -> log(sin(x)) in  
   (cos(2. *. f(1.2))-. 1.)/. (exp(f(2.56)) +. 1.);;  
 - : float = -0.00638361623325


Programme 2.16: définition locale de fonction

L’attribution au symbole f de la valeur x↦→log(sin(x)) ne sera valable qu’à l’intérieur de l’évaluation de l’expression. Cette attribution masque provisoirement toute autre valeur de tout autre type qui aurait pu être attribuée au symbole f. Mais dès la sortie de l’expression, le symbole f retrouve son ancienne valeur. Rien n’empêche d’ailleurs de combiner une définition locale de fonction avec une définition globale : de la même façon qu’on écrirait soit g : x↦→sin(2f(x)) + cos(f(x)) avec f : y↦→y2 + 1 , on écrira en Caml :


#let g = (let f = function y -> y *. y+. 1. in  
    function x -> sin(2. *. f(x)) +. cos(f(x)));;  
 
g : float -> float = <fun>  
#g(1.);;  
 - : float = -1.17294933186


Programme 2.17: définition locale de fonction dans une définition globale

La définition de la fonction f est locale alors que la définition de la fonction g est globale. La fonction f : x↦→x2 + 1 n’est pas réutilisable par la suite. Par contre, la fonction g : x↦→sin(2(x2 + 1)) + cos(x2 + 1) est maintenant à notre disposition pour tous les calculs que nous voudrons faire par la suite. Remarquez la syntaxe un peu lourde mais logique. La définition let f = function y->y*. y+. 1. est locale au calcul de l’expression function x-> sin(2. *. f(x))+. cos(f(x)) et c’est ensuite cette expression fonctionnelle qui est attribuée comme valeur au symbole f. Nous aurions pu écrire sans parenthèses :


#let g = let f = function y -> y *. y+. 1. in  
    function x ->  sin(2. *. f(x)) +. cos(f(x));;  
 
g : float -> float = <fun>


Programme 2.18: définition locale de fonction dans une définition globale

Dans la définition d’une fonction x↦→x2 + 1 le nom de la variable x est sans importance. Il en est de même en Caml. Les deux fonctions x -> x *. x+. 1. et y -> y *. y+. 1. sont parfaitement identiques et c’est uniquement par souci de clarté que nous n’avons pas écrit la définition parfaitement équivalente, avec le même nom de variable pour f et pour g


#let g = let f = function x -> x *. x +. 1. in  
    function x -> sin(2. *. f(x)) +. cos(f(x));;  
 
g : float -> float = <fun>


Programme 2.19: variables muettes

L’imbrication des deux constructions let peut nuire à la lisibilité. En CAML 0.7, on peut utiliser la construction where qui lui est équivalente et écrire :


#let g = (function x -> sin(2. *. f(x)) +. cos(f(x))  
       where f = function x -> x *. x +. 1. );;  
 
g : float -> float = <fun>


Programme 2.20: construction where

En mathématiques, plutôt que de dire soit f la fonction x↦→x2 + 1 , on dit souvent à la place posons f(x) = x2 + 1 . Caml permet le même abus d’écriture : à la place de let f = function x -> x *. x+. 1. on pourra écrire de façon totalement équivalente let f(x) = x *. x+. 1.. Notre définition de fonction g pourra ainsi s’écrire :


#let g(x) = (let f(y) = y*. y+. 1. in  
    sin(2. *. f(x))+. cos(f(x)));;  
 
g : float -> float = <fun>  
#g(1.4);;  
 - : float = -1.33881087302


Programme 2.21: définition étendue de fonction

2.1.4 Fonctions de plusieurs variables

En mathématiques, étant donné deux ensembles E et F, on définit leur produit cartésien E × F comme l’ensemble des couples (x,y) où x ∈ E et y ∈ F. De même, étant donné n ensembles E1,,En, on définit leur produit cartésien comme étant l’ensemble E1 ×⋅⋅⋅×En formé des n-uplets (x1,,xn) avec x1 ∈ E1,,xn ∈ En.

De la même façon, étant donné deux objets de Caml notés x et y, on peut construire le couple (x,y). C’est ainsi que l’on pourra poser :


#let a = (2,5);;  
 a : int * int = 2, 5  
#let b = (2.567,3.432);;  
 b : float * float = 2.567, 3.432  
#let c = (2,3.6758);;  
 c : int * float = 2, 3.6758


Programme 2.22: couple de valeurs

Remarquons deux choses. La première est que Caml utilise le symbole * pour désigner le produit cartésien de deux types ; le type int * float désigne le type des objets Caml formés de couples dont le premier terme est un entier et le second un réel en virgule flottante. La seconde est que Caml quand il rappelle la valeur attribuée à un symbole (par exemple a) oublie les parenthèses et écrit 2,5 à la place de (2,5). Nous verrons en effet plus loin que les parenthèses en Caml ne servent qu’à indiquer des priorités et sont le plus souvent omises lorsqu’elles ne sont pas indispensables. On aurait très bien pu écrire let a = 2,5;; à la place de let a = (2,5).

Ce que l’on a fait pour les couples peut être fait pour les n-uplets, et rien n’interdit d’écrire :


#let triple = (2, 3.56, 8);;  
triple : int * float * int = 2, 3.56, 8


Programme 2.23: n-uplets de valeurs

avec un type qui est logiquement int * float * int (triplets formés d’un entier, puis d’un réel, puis d’un entier).

A partir de là, il est facile de construire des fonctions de deux (ou plusieurs variables). C’est ainsi que pour définir la fonction mathématique f : (x,y)↦→sin(x2 + y2) on posera en Caml


#let f = function (x,y) ->  sin(x *. x+. y *. y);;  
 f : float * float -> float = <fun>  
#f(1.56,0.89);;  
 - : float = -0.0840082182762


Programme 2.24: fonction d’un couple de variables

On voit que l’interpréteur Caml a reconnu f comme une fonction qui à un couple de réels associe un autre nombre réel. On aurait pu écrire de manière équivalente


#let f(x,y) = sin(x *. x+. y *. y);;  
 f : float * float -> float = <fun>


Programme 2.25: fonction d’un couple de variables

2.1.5 Les fonctions : des objets comme les autres

Nous avons vu précédemment comment définir une fonction grâce à la construction function ... -> ... et comment lui attribuer un nom. Nous avons vu en même temps que Caml attribuait un type à l’objet ainsi défini, par exemple float -> float. C’est qu’en Caml, les fonctions sont (au même titre que les entiers ou les réels en virgule flottante) des objets comme les autres susceptibles de recevoir un nom, de faire partie de n-uplets, d’être envoyés comme paramètres à d’autres fonctions ou d’être renvoyés comme résultats d’autres fonctions. C’est là une des particularités des langages fonctionnels comme Caml, LISP ou Mathematica qui les distingue fondamentalement des langages procéduraux comme Pascal ou C ; dans ces derniers en effet on distingue complètement les structures de données (entiers, réels, tableaux, pointeurs) des constructions qui les manipulent (procédures ou fonctions).

Supposons par exemple que nous souhaitions construire une fonction qui associe à une fonction f : R R et à deux réels a et b, l’aire du trapèze de sommets (a,0), (b,0), (a,f(a)) et (b,f(b)). Mathématiquement c’est l’application

                 f (a) +f (b)
T : (f,a,b) ↦→ (b - a)---2----

Nous allons définir une fonction Caml trapeze qui effectue ce calcul.


#let trapeze (f,a,b) = (b -. a)*. (f(a) +.f(b)) /. 2.;;  
trapeze : (float -> float) * float * float -> float = <fun>  
#let f(x) = x *. x in trapeze(f,0.,2.);;  
- : float = 4  
#let f(x) = x *. x in trapeze(f,0.,2.2);;  
- : float = 5.324  
#let f(x) = sin(x) in trapeze(f,0.,1.57);;  
- : float = 0.784999751101


Programme 2.26: fonction d’une fonction

On voit que Caml a parfaitement déterminé le type de la fonction trapeze. À un triplet composé d’une fonction des réels dans les réels (le type float -> float) et de deux réels elle associe un nombre réel. Donc trapeze a bien comme type

(float -> float) * float * float -> float

Le lecteur vérifiera facilement la validité du résultat obtenu.

De la même façon, imaginons que nous voulions construire une fonction qui à toute fonction f : R R associe la fonction 2f : x↦→2f(x). Nous allons ensuite appliquer cette fonction à la fonction f : x↦→x2 pour obtenir comme résultat la fonction x↦→2x2 que nous appellerons g. Nous allons donc poser en Caml :


#let par2(f) = function x -> 2. *. f(x);;  
par2 : (’a -> float) -> ’a -> float = <fun>  
#let g = (let f(x) = x *. x in par2(f));;  
g : float -> float = <fun>  
#g(3.);;  
- : float = 18


Programme 2.27: fonctionnelle

La réponse concernant le type de la fonction par2 demande ici une explication. Caml a constaté que le type du paramètre x de la fonction f n’avait pas d’importance du moment que le résultat est un réel : la fonction f peut aller de n’importe quoi dans les réels. Le symbole ’a est ce qu’on appelle un paramètre de type : il peut être remplacé par n’importe quel type. Autrement dit le type attribué à la fonction par2 est celui d’une fonction qui à une fonction f de n’importe quoi dans les réels (le type ’a -> float) associe une nouvelle fonction du même n’importe quoi dans les réels. C’est donc bien le type (’a -> float) -> (’a -> float) moyennant quelques économies de parenthèses habituelles à Caml.

2.1.6 Curryfication, décurryfication

Nous avons vu dans le paragraphe précédent qu’une fonction Caml pouvait renvoyer une fonction comme résultat. Or cette situation n’est pas du tout inhabituelle en mathématiques. Considérons en effet une fonction f définie sur un produit cartésien E ×F et à valeurs dans un ensemble G, (x,y)↦→f(x,y). A chaque x ∈ E, on peut associer l’application fx : y↦→f(x,y) qui va de F dans G ; nous obtenons ainsi une fonction φ qui à tout x de E associe la fonction fx de F dans G définie par fx(y) = f(x,y). On a donc

∀x ∈ E, ∀y ∈ F, f(x,y) = [φ (x)](y)

Inversement, à toute fonction φ qui va de E dans l’ensemble des applications de F dans G, on peut associer une unique fonction f : E × F G par la formule ci dessus. On dira alors que φ est la curryfiée de la fonction f et que f est la décurryfiée de la fonction φ.

Construisons par exemple en Caml la fonction curryfiée de l’addition des entiers. Nous allons construire une fonction add qui à tout entier x associe la fonction qui à un entier y associe x+y. Avec nos connaissances, cela ne présente aucune difficulté et on a donc :


#let add = function x -> (function y -> x+y);;  
add : int -> int -> int = <fun>  
#(add(2))(8);;  
- : int = 10


Programme 2.28: fonction curryfiée

Nous voyons que le type de la fonction add est celui d’une fonction des entiers dans l’ensemble des fonctions des entiers dans les entiers, soit int -> (int -> int). Avec une économie de parenthèses (le symbole -> étant associatif à droite) ceci donne donc bien le type détecté int -> int -> int. Bien entendu, le calcul de 2 + 8 n’est pas vraiment facilité puisque nous sommes alors obligés de parenthéser l’expression sous la forme [φ (x )](y) soit en Caml (add(2))(8). Mais Caml essaye au maximum de faire disparaître les parenthèses. Pour cela la convention utilisée est que si f est une fonction Caml et si x est un objet Caml, f  x (avec un espace entre les deux) désigne f(x). Autrement dit, on peut calculer 2 + 8 en écrivant simplement add 2 8 : en effet add 2 va signifier add(2) et donc, la juxtaposition étant associative à gauche, add 2 8 va signifier (add(2))(8).


#add 2 8;;  
- : int = 10


Programme 2.29: application d’une fonction curryfiée

Attention : il faut résister à l’envie d’écrire add (2 8) En effet, dans ce cas, Caml va d’abord tenter d’évaluer l’expression 2 8 autrement dit d’appliquer une pseudo-fonction 2 à l’entier 8 avant d’appliquer au tout la fonction add. Mais comme 2 est un entier et non une fonction définie sur les entiers, Caml va détecter une erreur : l’objet 2 de type int ne peut pas être utilisé comme une fonction allant de quelque chose vers les entiers.


#add (2 8);;  
> Toplevel input:  
>add (2 8);;  
>     ^  
> Expression of type int  
> cannot be used with type ’a -> int


Programme 2.30: parenthésage d’une fonction curryfiée

En fait, les informaticiens (contrairement aux mathématiciens) n’aiment pas beaucoup les fonctions définies sur des produits cartésiens et préfèrent enchaîner des fonctions d’une variable plutôt que de définir des fonctions de plusieurs variables ; ils préfèrent les fonctions curryfiées aux fonctions non curryfiées. La construction d’une fonction curryfiée est malheureusement très lourde : pour définir l’addition il faut écrire

function x -> (function y -> x+y)

Pour cela Caml admet une syntaxe simplifiée sous la forme fun x y -> x+y. Plus généralement l’expression

fun x1 x2 ... xn -> y

est équivalente à

function x1 -> function x2 -> ... -> function xn -> y

qui elle même est équivalente (en tenant compte de l’associativité à droite du symbole ->) à

function x1 -> (function x2 -> ... -> (function xn -> y)...)

Dans le but de simplifier encore l’écriture, dans l’attribution d’un nom à une fonction curryfiée, Caml admet que l’on écrive

let g x1 x2 ... xn = y

plutôt que d’écrire

let g = fun x1 x2 ... xn -> y

Nous pouvons donc maintenant réécrire notre fonction d’addition curryfiée sous la forme suivante (surtout pas de parenthèses autour du couple x y) :


#let add x y = x+y;;  
add : int -> int -> int = <fun>


Programme 2.31: addition curryfiée

La fonction non curryfiée correspondante est la fonction add_nc définie par


#let add_nc (x,y) = x+y;;  
add_nc : int * int -> int = <fun>


Programme 2.32: addition non curryfiée

Une différence essentielle est à signaler qui montre la supériorité de la fonction curryfiée sur la fonction non curryfiée. Essayons d’appliquer chacune des deux fonctions à l’entier 3. Sous la forme non curryfiée, nous obtenons une erreur puisque 3 n’est pas un couple formé de deux entiers


#let plus3_nc = add_nc 3;;  
> Toplevel input:  
>let plus3_nc = add_nc 3;;  
>                    ^  
> Expression of type int  
> cannot be used with type int * int


Programme 2.33: erreur dans une fonction non curryfiée

Par contre, sous sa forme curryfiée, add 3 désigne la fonction qui à tout entier x associe 3 + x.


#let plus3 = add 3;;  
plus3 : int -> int = <fun>  
#plus3(15);;  
- : int = 18


Programme 2.34: application partielle de l’addition curryfiée

Nous n’avons mis des parenthèses autour du 15 que pour la commodité du lecteur. On aurait pu écrire plus simplement plus3 15.

Réécrivons alors la fonction trapeze de notre paragraphe précédent sous forme curryfiée :


#let trapeze f a b = (b-. a)*. (f(a)+.f(b))/. 2.;;  
trapeze : (float -> float) -> float -> float -> float = <fun>  
#let f x = x*. x in trapeze f  0.  2.2;;  
- : float = 5.324


Programme 2.35: fonction trapèze curryfiée

Par la suite, sauf raison particulière, nous préférerons les formes curryfiées des fonctions et nous n’écrirons plus les parenthèses autour des paramètres des fonctions.

2.1.7 Les calculs logiques

Comme tout langage de programmation, Caml est capable de faire ce que l’on appelle du calcul propositionnel c’est-à-dire d’effectuer des opérations sur des expressions dont il sait tester si elles sont vraies ou fausses (ce qu’on appellera des propositions).

Pour tester la véracité de certaines assertions, Caml introduit, comme la plupart des langages de programmation, un type booléen, simplement noté bool. Ce type ne comprend que deux objets désignant l’un ce qui est vrai, l’autre ce qui est faux. Le vrai est désigné par l’objet true, le faux par l’objet false. C’est ainsi que nous pouvons effectuer certains tests sur les nombres réels ou entiers : les deux nombres sont-ils égaux, le premier est-il plus petit que le second, le premier est-il plus grand que le second :


#0 = 0;;  
- : bool = true  
#0 > 1;;  
- : bool = false  
#1.5 <=. 1.7;;  
- : bool = true  
#0 <> 1;;  
- : bool = true  
#1.5 <> 1.6;;  
- : bool = true


Programme 2.36: relations booléennes

Nous voyons que Caml dispose d’un certains nombres d’opérateurs logiques (c’est-à-dire dont les résultats sont des booléens) comme l’égalité =, la non égalité <>, l’opérateur inférieur <, l’opérateur inférieur ou égal <=, l’opérateur plus grand >, l’opérateur plus grand ou égal >=. Les deux premiers (égalité ou non égalité) peuvent s’appliquer à deux objets Caml quelconques du moment qu’ils sont de même type, les autres s’appliquent exclusivement à des nombres entiers2 (ils ont leurs analogues pointés <., <=., >. et >=. pour les réels en virgule flottante).

Contrairement à ce qui se passe en mathématiques, une expression du type a=b n’est pas l’affirmation que a est égal à b, mais au contraire une question posée qui admet soit la réponse vrai, soit la réponse faux.

Nous pouvons construire des fonctions booléennes (c’est-à-dire des fonctions qui renvoient une réponse vrai ou faux) comme par exemple la fonction ci dessous qui teste si la somme de deux nombres est nulle :


#let sommeNulle x y = (x+y = 0);;  
sommeNulle : int -> int -> bool = <fun>  
#sommeNulle 2 0;;  
- : bool = false  
#sommeNulle 2 (-2);;  
- : bool = true


Programme 2.37: définition de fonction booléenne

(les parenthèses autour du - 2 empêchent Caml d’effectuer la différence 2 - 2).

Les seules opérations existantes sur les booléens sont le et logique, le ou logique et le non logique respectivement définis par les opérateurs &, or et not3. C’est ainsi que si p et q sont deux booléens, p & q est le booléen true si et seulement si p et q valent tous deux true, sinon c’est le booléen false. De même p or q est le booléen true si et seulement si au moins l’un des deux p et q vaut true, sinon (c’est-à-dire s’ils valent tous deux false) c’est le booléen false. Quant à l’opérateur unaire not, il échange logiquement le vrai et le faux, transformant true en false et false en true.

Les opérateurs & et or ne sont pas limités à deux arguments et on peut écrire p1 & p2 & ... & pn ou q1 or q2 or ... or qn. Le premier vaut true si et seulement si tous les pi vaut true, le second vaut true si et seulement si l’un au moins des pi vaut true4.

Voyons quelques exemples.


#(1 < 5) & (3 < 8) & (1.2 <. 3.6);;  
- : bool = true  
#(1 < 5) & (3 > 8) & (1.2 <. 3.6);;  
- : bool = false  
#((1 < 5) & (3 > 8)) or (1.2 <. 3.6);;  
- : bool = true


Programme 2.38: opérateurs booléens

Dans le premier cas, les trois affirmations sont vraies donc le résultat est vrai. Dans le second cas, la deuxième est fausse donc le résultat est faux. Dans le troisième cas, la première affirmation (1 < 5) & (3 > 8) est fausse (puisque sa seconde partie est fausse), mais la deuxième 1.2 <. 3.6 est vraie, donc leur ou logique est vrai5.

2.2 Effets de bord

Jusqu’à maintenant, nous avons considéré Caml comme une simple calculatrice. Les seuls objets que nous savons construire sont des fonctions dans lesquelles on entre des paramètres et qui retournent un résultat. Il se trouve tout simplement que l’interpréteur Caml permet de récupérer ce résultat car celui ci est affiché à l’écran en écho. On voit bien cependant que la méthode a ses limites et qu’il est nécessaire qu’un programme puisse agir sur son environnement : modifier une valeur en mémoire, afficher quelque chose à l’écran, écrire une valeur dans un fichier sur une disquette sont des actions indispensables pour lesquelles la structure de calculatrice est a priori mal adaptée.

Toutes ces actions qui modifient physiquement l’environnement sont appelées des effets de bord. Ceux-ci doivent être soigneusement maîtrisés et ne doivent être utilisés qu’à bon escient et avec parcimonie. Nous allons passer en revue dans cet ordre : les actions destinées à modifier l’environnement sans retourner de résultat (les procédures), leur conséquence logique qu’est la séquence, et enfin les références.

2.2.1 Les procédures

Les procédures6 sont des fonctions d’un type particulier dont le seul but est de modifier l’environnement de travail : écrire sur l’écran ou sur une disquette, modifier un emplacement mémoire, dessiner sur l’écran, émettre un son, etc. En conséquence, elles n’ont pas besoin de renvoyer un résultat intéressant. On pourrait choisir de faire retourner à une telle fonction une valeur quelconque (par exemple 0 ou 3.14159) ; cela serait dangereux puisque cette valeur risquerait d’être réemployée, volontairement ou par mégarde, en croyant qu’elle a une signification, alors qu’elle n’en a aucune. Pour cette raison, Caml a choisi de faire renvoyer à ces fonctions particulières un type particulier appelé unit. Ce type n’a qu’un seul élément, à savoir le rien, qui est noté () et qui est en gros analogue à l’ensemble vide en mathématiques. Ce type est bien entendu incompatible avec tous les autres, si bien qu’il n’y a aucun risque de réutiliser cette valeur particulière () à mauvais escient.

Parmi ces procédures, les plus couramment utilisées sont celles qui permettent d’écrire à l’écran. Nous citerons les procédures print_int et print_float dont le but est d’écrire à l’écran la représentation décimale d’un entier ou d’un nombre réel en virgule flottante. Voici un exemple d’affichage (sachant que l’évaluation de power x y retourne la représentation en virgule flottante de xy) :


#print_int (256 + 894);;  
1150- : unit = ()  
#print_float (power 2. 128.);;  
3.40282366921e+38- : unit = ()


Programme 2.39: écriture à l’écran

On constate effectivement que Caml a effectué l’ordre d’écriture à l’écran puis retourné le résultat (). Comparez avec :


#256+894;;  
- : int = 1150  
#power 2. 128.;;  
- : float = 3.40282366921e+38


Programme 2.40: affichage d’évaluation

Dans le premier cas, Caml a obéi à un ordre d’affichage à l’écran et a retourné le résultat rien ; ce type de comportement est programmable. Dans le deuxième cas, Caml a effectué un calcul, puis n’a écrit le résultat à l’écran que parce qu’il le voulait bien et que l’on travaillait en mode interactif (autrement dit en mode calculatrice) ; ce comportement n’est pas programmable.

Le type unit est un type comme les autres, même s’il ne s’applique qu’à un seul objet rien. En particulier on peut passer () en paramètres de certaines fonctions qui ne nécessitent aucun paramètre. On prendra garde simplement de ne pas confondre f (), qui désigne le résultat de l’évaluation de f quand on lui passe () comme paramètre, avec f, qui désigne l’objet fonction lui-même.

2.2.2 Les séquences

L’enchaînement de deux ou plusieurs fonctions n’a guère de sens puisque le résultat des premières fonctions ne peut qu’être perdu et que seul pourra être conservé le résultat de la dernière. Par contre rien n’interdit d’enchaîner deux ou plusieurs actions modifiant l’environnement (par exemple afficher un résultat à l’écran, puis émettre un bip pour en avertir l’utilisateur distrait). Pour cela, Caml dispose de la construction dite de séquences d’expressions. Si expr1,,exprn sont des expressions, l’évaluation de

expr1 ; expr2 ;  ; exprn

provoque l’évaluation de expr1,,exprn dans cet ordre (avec tous les effets de bord qui peuvent découler de ces évaluations), tous les résultats de ces expressions étant négligés sauf le dernier découlant de l’évaluation de exprn qui est retourné comme résultat de l’expression séquence. Il est clair que la plupart du temps les résultats de toutes les expressions sauf la dernière seront de type unit ; il serait en effet absurde d’écrire une séquence du type :


#exp(1.0); exp(2.5);;  
- : float = 12.1824939607


Programme 2.41: séquence d’appels de fonctions

puisque le résultat de la première évaluation a été négligée. Par contre, il peut être intéressant d’écrire :


#print_float (exp 1.0); print_newline ();  
          print_float (exp 2.5); print_newline ();;  
2.71828182846  
12.1824939607  
- : unit = ()


Programme 2.42: séquence d’appels de procédures

en sachant que la fonction print_newline est une fonction de type unit -> unit c’est à dire une fonction qui prend rien en paramètre (mais il faut impérativement qu’il y figure), qui retourne rien et provoque un passage à la ligne à l’écran.

Il n’est pas toujours facile, quand plusieurs structures de contrôle sont imbriquées, de délimiter avec certitude une séquence, et les règles d’associativité sont un peu complexes. Une première méthode est de délimiter une séquence par des parenthèses comme dans une expression mathématique habituelle. Ceci ne facilite pas la lisibilité de cette séquence, surtout lorsque celle-ci se poursuit, comme il arrive fréquemment, sur plusieurs lignes. L’habitude est dans ce cas d’encadrer la séquence par les deux mots clés begin et end qui sont équivalents à une parenthèse ouvrante et une parenthèse fermante, tout en décalant légèrement le corps de la séquence vers la droite (on dit que l’on fait une indentation), et en passant à la ligne après chaque point-virgule de séparation. Très souvent une séquence se présentera donc sous la forme


        begin  
           expression1;  
           expression2;  
           ...........  
           expressionN  
        end


Programme 2.43: délimitation de séquence

chacune des expressions pouvant elle-même contenir des séquences. Les deux mots begin et end servent plus généralement à délimiter toute structure Caml en cas de besoin. Voici un exemple typique de programme Caml :


  if b1 < b2 & (sans_interférences env arg1)  
    then  
      begin  
        let (reg2, reg1) = compile_arg env arg2 arg1 in (reg1, reg2)  
      end  
    else  
      begin  
        compile_expr env arg1 reg_libre;  
        if b2 < dernier_registre - reg_libre  
          then  
            begin  
              compile_expr env arg2 (reg_libre + 1);  
              (reg_libre, reg_libre + 1)  
            end  
          else  
            begin  
              réserve_pile 1;  
              compile_expr env arg2 reg_libre;  
              libère_pile 1;  
              (29, reg_libre)  
            end  
       end


Programme 2.44: exemple de programme Caml

2.2.3 Les références

Supposons que nous voulions nous accorder une place en mémoire pour stocker des valeurs que nous pourrons ensuite réutiliser et modifier par programme. Une première possibilité est d’utiliser l’une des constructions let, c’est-à-dire soit la construction globale let ident =expression qui lie de manière permanente (jusqu’à la prochaine liaison faisant intervenir ident) l’identificateur ident à la valeur de expression, soit la construction locale let ident =expr1 in expr2 qui n’effectue la liaison entre l’identificateur ident et la valeur de expr1 qu’à l’intérieur de l’évaluation de expr2.

Il est clair que la deuxième construction ne permet un stockage temporaire qu’à l’intérieur de l’évaluation de expr2 et ne répond guère à nos besoins de modification. Quant à la première construction, elle souffre de deux défauts rédhibitoires. D’une part, elle est globale et permanente avec tous les dangers que cela comporte ; d’autre part, la liaison entre l’identificateur et sa valeur n’est pas modifiable par programme mais uniquement par l’utilisateur : en effet la construction let ident =expression n’est pas une expression Caml ordinaire qui retourne un résultat, mais plutôt un ordre donné à Caml d’attribuer un nom à une constante (même si celle-ci est calculée). En particulier, il est interdit d’insérer une instruction let globale dans une séquence, puisqu’une séquence ne peut contenir que des expressions.


#(let x = 2); exp(1.0);;  
> Toplevel input:  
>(let x = 2); exp(1.0);;  
>          ^  
> Syntax error.


Programme 2.45: essai erroné d’affectation

Autrement dit, pour continuer notre comparaison avec les mathématiques, la construction let ressemble beaucoup plus à la définition d’une constante mathématique (posons e = exp(1)) plutôt qu’à la définition d’une variable x dans laquelle nous pourrons stocker successivement et par programme des valeurs intéressantes et modifiables.

Pour ce stockage de valeurs (temporaire ou définitif, local ou global), Caml dispose des objets références. Ces objets désignent en fait des emplacements en mémoire (d’autres langages les appelleraient des pointeurs), dans lesquels on peut stocker des valeurs, ces valeurs étant récupérables à l’aide de l’opérateur unaire ! et modifiables à l’aide de l’opérateur binaire :=.

On peut construire une référence très simplement à l’aide de let. La construction

let ident= ref expression

libère une place en mémoire, y stocke la valeur de l’expression expression et attribue le nom ident à cette place en mémoire (et non à l’expression elle même) ; on dit aussi que l’identificateur ident est lié à la référence.

La construction d’une référence peut être locale (et doit l’être le plus souvent possible). La construction

let ident= ref expr1 in expr2

définit une référence qui ne sera valable qu’à l’intérieur de l’évaluation de expr2 ; cette expression expr2 sera le plus souvent une séquence d’expressions qui utiliseront la valeur stockée dans la référence, la modifieront, etc. Une fois l’évaluation de expr2 terminée, la référence sera oubliée, l’identificateur ident ne sera plus lié à la référence, l’emplacement en mémoire sera rendu disponible par Caml qui cherchera à le récupérer dès qu’il aura besoin de mémoire (c’est le processus appelé garbage collector en anglais, c’est-à-dire le ramassage de poubelles) ; alors que beaucoup de langages obligent à une libération explicite des références ou des pointeurs, Caml se charge lui-même de cette libération.

Essayons de définir globalement quelques références :


#let n = ref 1;;  
n : int ref = ref 1  
#let x = ref 1.56743;;  
x : float ref = ref 1.56743


Programme 2.46: définitions globales de références

On voit que Caml attribue un type à une référence, à savoir le type type_contenu ref, où nous notons type_contenu le type du contenu de la référence. Si par exemple nous tentons de savoir si nos deux références ci-dessus sont égales, Caml provoquera une erreur car les deux objets n et x ne sont pas de même type : l’un est de type int ref (référence vers un entier), l’autre de type float ref (référence vers un réel).


#n = x;;  
> Toplevel input:  
>n = x;;  
>    ^  
> Expression of type float ref  
> cannot be used with type int ref


Programme 2.47: typage des références

Par contre, rien n’empêche de manipuler une référence comme une valeur Caml ordinaire et d’écrire :


#let y = x;;  
y : float ref = ref 1.56743


Programme 2.48: liaison de références

A partir de ce moment, l’identificateur y désigne le même emplacement mémoire que l’identificateur x ; toute modification de la valeur contenue dans cet emplacement mémoire pour l’un se répercutera sur l’autre.

Voyons maintenant de manière plus précise comment on récupère ou modifie la valeur contenue dans l’emplacement mémoire désigné par un identificateur x. La récupération se fait par l’opérateur unaire ! : si l’identificateur x est lié à une référence (c’est-à-dire désigne un emplacement mémoire), !x désigne le contenu de la référence. Bien entendu, si x est de type type_contenu ref, !x est de type type_contenu.


#let x = ref 1.56743;;  
x : float ref = ref 1.56743  
#!x;;  
- : float = 1.56743


Programme 2.49: valeur pointée par une référence

La modification de la valeur contenue dans une référence (on dit plutôt pointée par la référence) se fait à l’aide de l’opérateur :=, où l’on met à gauche l’identificateur de la référence et à droite la valeur à stocker avec la syntaxe

ident :=expr

L’expression expr est évaluée et sa valeur est stockée dans la référence liée à l’identificateur ident. Si ident est de type type_contenu ref, la valeur de expression doit être de type type_contenu (pas question de stocker un entier dans une référence de type float ref).

Il est par exemple très facile d’ajouter 15 à notre référence n définie plus haut. Il suffit de réaffecter à la référence n le contenu de la référence n augmenté de 15 ce qui s’écrit :


#let n = ref 1;;  
n : int ref = ref 1  
#n := !n + 15;;  
- : unit = ()  
#n;;  
- : int ref = ref 16


Programme 2.50: affectation et modification de références

Nous voyons que l’opérateur := est considéré par Caml comme une application qui à une référence vers un type donné et à un objet de ce type associe () c’est-à-dire rien. Bien entendu, cette application (qui est donc une procédure) ne vaut que par son effet de bord qui est de stocker la valeur dans l’emplacement mémoire désigné7

Comme l’opérateur := renvoie le type unit c’est-à-dire rien, c’est l’élément rêvé pour faire partie d’une séquence d’expressions. C’est ainsi que l’on pourra écrire


#let x = ref 3.14 in  
         x := !x +. 12.; x := sin(!x *. !x); x := !x /. (!x +. 1.);  
         print_float(!x);print_newline();;  
0.104263104374  
- : unit = ()


Programme 2.51: séquences d’affectations

2.2.4 Evaluation immediate, évaluation différée

Nous avons longuement insisté dans le paragraphe précédent sur la différence entre la liaison d’un identificateur et d’une valeur et la définition de référence. Il existe un autre point qui sépare ceux-ci en ce qui concerne l’évaluation, qui est une distinction importante en calcul formel.

La règle est que les liaisons sont toujours évaluées immédiatement, même si c’est à l’intérieur de la définition d’une fonction comme le montre l’exemple suivant :


#let b = 2;;  
b : int = 2  
#let double x = b*x;;  
double : int -> int = <fun>  
#let b = 145;;  
b : int = 145  
#double 3;;  
- : int = 6


Programme 2.52: évaluation immédiate d’une liaison

On voit que l’identificateur b a été remplacée par sa valeur 2 au moment de la définition de la fonction. On a beau par la suite modifier la valeur attribuée (liée) à l’identificateur b, c’est la valeur qui lui était attribuée au moment de la définition de la fonction qui est utilisée et non la valeur effective qui lui est attribuée au moment de l’utilisation de la fonction8.

Ecrivons un petit programme similaire avec des références :


#let b = ref 2;;  
b : int ref = ref 2  
#let double x = !b * x;;  
double : int -> int = <fun>  
#b := 145;;  
- : unit = ()  
#double 3;;  
- : int = 435


Programme 2.53: évaluation retardée d’une référence

On voit cette fois que c’est la valeur contenue dans la référence au moment de l’exécution de la fonction double (qui porte d’ailleurs bien mal son nom) qui est utilisée, et non celle qui lui était attribuée au moment de la définition de la fonction. C’est tout à fait normal puisque !b réalise un appel de fonction (la fonction prefix !) avec le paramètre b et que les appels de fonctions subordonnées ne sont effectués qu’au moment de l’exécution effective de la fonction principale.

Dans le cas de la liaison, il y a évaluation immédiate de la liaison. Dans le cas de la référence, il y a évaluation différée du contenu de la référence.

2.3 Les structures de contrôle

Pour le moment, nous nous sommes contentés d’évaluer des expressions linéairement : autrement dit, à aucun moment n’intervenait de choix ni de répétition. Nous allons maintenant entrer vraiment dans le cadre de la programmation en se donnant la possibilité de faire des choix ou de répéter certaines actions.

2.3.1 Expression conditionnelle

Le résultat d’un calcul ou l’action à effectuer dépend souvent du résultat d’un test. Il en est ainsi par exemple de la valeur absolue :

    {
      x   si x > 0
|x| =  - x si x ≤ 0

Il est facile de simuler ce fonctionnement en Caml. L’évaluation de l’expression conditionnelle

if test then expr1 else expr2

se déroule en deux étapes : dans un premier temps la valeur de l’expression test est calculée. Cette valeur doit être un booléen. Si cette expression a la valeur true alors expr1 est évaluée et sa valeur est renvoyée comme valeur de toute l’expression conditionnelle ; si par contre la valeur de l’expression test est false, alors c’est expr2 qui est évaluée et sa valeur qui est renvoyée comme valeur de toute l’expression conditionnelle. Ainsi notre fonction valeur absolue peut être définie comme


#let abs x = (if x > 0 then x else -x );;  
abs : int -> int = <fun>  
#abs -1200;;  
- : int = 1200


Programme 2.54: structure conditionnelle

Bien entendu, des structures conditionnelles peuvent être imbriquées et si l’on veut définir une fonction sur les entiers par

      {
        0   si n < 0
f(n) =  2n  si 0 ≤ n ≤ 5
        n2  si n ≥ 6

on écrira


#let f x = if x < 0 then 0  
           else if x <= 5 then 2 * x  
           else x * x;;  
f : int -> int = <fun>  
#f(-8);;  
- : int = 0  
#f(3);;  
- : int = 6  
#f(10);;  
- : int = 100


Programme 2.55: structures conditionnelles imbriquées

(notez les indentations qui facilitent la lecture et permettent de repérer facilement les différents cas).

2.3.2 Conditionnelle par cas, reconnaissance de motifs

Plutôt que d’effectuer un test booléen, on peut avoir besoin de tester la forme de la valeur d’une expression. En Caml, les motifs permettent à la fois de reconnaître la forme d’une expression et de nommer les différentes parties de cette expression.

Lors de l’évaluation d’une expression du type

match expr with motif1 -> expr1 | motif2 -> expr2 | | motifn -> exprn

Caml va tout d’abord évaluer l’expression expr ; ensuite il va essayer de faire correspondre successivement cette expression avec motif1,,motifn dans cet ordre ; dès qu’une concordance est trouvée, les parties de l’expression correspondant au motif sont nommées en fonction des noms figurant dans le motif et la valeur de l’expression est renvoyée.

Il est fortement conseillé, pour améliorer la lisibilité, d’indenter une expression conditionnelle par cas en mettant chaque barre verticale au début du cas qui la concerne sous la forme :


  match  expr  with  
            motif1 -> expr1  
        |   motif2 -> expr2  
        |   ...............  
        |   motifn -> exprn


Programme 2.56: présentation d’une expression conditionnelle par cas

A cet effet, Caml 0.7 admet même que l’on fasse précéder la première ligne d’une barre verticale sous la forme :


  match  expr  with  
        |   motif1 -> expr1  
        |   motif2 -> expr2  
        |   ...............  
        |   motifn -> exprn


Programme 2.57: présentation d’une expression conditionnelle par cas de Caml 0.7

Commençons par un cas simple avec la fonction f définie sur les entiers par

      { 18  si n = 0
f(n) =  24  si n = 1
        n2  si n ∕∈ {0,1}

Nous la définirons en Caml par


#let f x = match x with  
            0 -> 18  
        |   1 -> 24  
        |   y -> y*y ;;  
f : int -> int = <fun>  
#f 0;;  
- : int = 1  
#f 1;;  
- : int = 2  
#f 2;;  
- : int = 4


Programme 2.58: conditionnelle par cas

Lors de l’évaluation de f 0, Caml essaye tout d’abord de faire correspondre la valeur 0 de x avec 0, ce qui réussit ; l’expression match ... renvoie donc 18 qui est la valeur associée à 0. Lors de l’évaluation de f 1, Caml essaye tout d’abord de faire correspondre la valeur 1 de x avec 0, ce qui échoue ; il tente alors de faire correspondre la valeur 1 de x avec 1 (ligne suivante), ce qui réussit ; l’expression match ... renvoie donc 24 qui est la valeur associée à 1. Lors de l’évaluation de f 2, Caml essaye tout d’abord de faire correspondre 2 avec 0, ce qui échoue ; il tente alors de faire correspondre 2 avec 1 (ligne suivante), ce qui échoue à nouveau ; il tente alors de faire correspondre 2 avec y ce qui réussit à condition de donner la valeur 2 à y ; il évalue donc l’expression y*y en donnant à y la valeur 2 et renvoie le résultat.

Remarque  L’ordre dans lequel les différents motifs sont examinés est crucial. Si vous définissez


#let f x =  
     match x with  
        0 -> 18  
      | y -> y*y  
      | 1 -> 24;;


Programme 2.59: ordre dans les motifs

le troisième motif n’est jamais examiné puisque dès que la première correspondance n’est pas satisfaite, le second l’est obligatoirement. D’ailleurs la réponse de Caml ne se fait pas attendre : il vous signale qu’un cas n’est jamais utilisé (tout en ne refusant pas la définition) :


#let f x =  
      match x with  
        0 -> 18  
      | y -> y*y  
      | 1 -> 24;;  
Toplevel input:  
>      | 1 -> 24;;  
>        ^  
Warning: this matching case is unused.  
f : int -> int = <fun>


Programme 2.60: avertissement : ”case unused”

Essayons un cas plus complexe avec la fonction de deux entiers définie par

         { m      si n = 0
f(m,n ) =  - n    si m = 0
           m + n  si m ⁄= 0 et n ⁄= 0

On peut la définir en Caml sous forme non curryfiée par :


#let f z =  
         match z with  
           (m,0) -> m  
         | (0,n) -> -n  
         | (m,n) -> m+n;;  
f : int * int -> int = <fun>


Programme 2.61: reconnaissance multiple de motifs

Remarquons tout d’abord que Caml a constaté que nous essayons de faire correspondre la variable z avec un couple de deux entiers (puisque m et n peuvent valoir 0) et que donc nécessairement la fonction f est définie sur les couples d’entiers ; elle leur associe clairement un entier, donc son type est int * int -> int. Lors de l’évaluation de l’expression match , Caml commence par calculer la valeur de z qui doit être un couple d’entiers. Si l’entier de droite est 0, Caml trouve une correspondance avec le premier motif, donc il nomme m l’entier de gauche et retourne l’expression m. Si l’entier de droite n’est pas nul mais que le second est nul, Caml trouve une correspondance avec le second motif (0,n), donc il nomme n l’entier de droite et retourne la valeur de l’expression -n correspondante. Enfin, si les deux sont non nuls, Caml examine le troisième motif. Caml trouve évidemment une correspondance avec le couple (m,n) à condition d’appeler m l’entier de gauche et n l’entier de droite ; il retourne donc la valeur de l’expression m+nm désigne l’entier de gauche et n l’entier de droite.


#f(3,0);;  
- : int = 3  
#f(0,6);;  
- : int = -6  
#f(1,7);;  
- : int = 8


Programme 2.62: application d’une reconnaissance de motifs

Sous forme curryfiée, nous pouvons définir cette même fonction par


#let f x y =  
        match (x,y) with  
           (m,0) -> m  
        |  (0,n) -> -n  
        |  (m,n) -> m+n;;  
f : int * int -> int = <fun>


Programme 2.63: reconnaissance de motifs dans une fonction curryfiée

Cette fois, c’est l’expression (x,y) que Caml va essayer de faire correspondre avec les différents motifs et il retournera la valeur de l’expression correspondante.

Une expression conditionnelle par cas doit examiner tous les cas possibles : dans le cas contraire, Caml vous avertira que votre étude de cas n’est pas exhaustive. Si vous persistez et évaluez votre expression match ... alors qu’aucune correspondance ne peut être trouvée, Caml provoquera une erreur Match failure à l’exécution.

Remarque  La conditionnelle par cas ne remplace pas les tests. C’est ainsi qu’on ne peut pas tester si les deux éléments d’un couple sont égaux en tentant un

match z with (x,x)->...

en effet en Caml, un motif peut contenir des variables, mais il ne doit contenir qu’une et une seule fois chaque variable. En conséquence, (x,x) n’est pas un motif valide car il contient deux fois la variable x. Il faut remplacer cette expression erronée par

match z with (x,y)->if x=y then ... else ...

Dans le cas de fonctions d’une variable, Caml admet (et souhaite) une syntaxe simplifiée. Plutôt que de poser :


let f z =  
        match z with  
           (m,0) -> m  
        |  (0,n) -> -n  
        |  (m,n) -> m+n;;


Programme 2.64: syntaxe avec variable

avec une variable z qui est pratiquement inutilisée, il est plus commode de faire disparaître la variable z et d’écrire :


let f = function  
           (m,0) -> m  
        |  (0,n) -> -n  
        |  (m,n) -> m+n;;


Programme 2.65: syntaxe fonctionnelle

qui peut se lire de la façon suivante : f est la fonction qui à quelque chose de la forme (m,0) associe m, qui à quelque chose de la forme (0,n) associe -n et qui à quelque chose de la forme (m,n) associe m+n (avec cet ordre de priorité) ; cette syntaxe généralise celle de notre première introduction des fonctions avec par exemple let f = function x->x*x : dans cette syntaxe simple, il n’y a qu’un seul motif alors que dans cette syntaxe étendue on peut envisager plusieurs motifs.

Remarque : Caml 0.7 admet également des motifs conditionnels (qui dépendent d’un test booléen). Ceux ci sont introduits par la syntaxe complémentaire

motif when test -> expr

Si la reconnaissance de la valeur par motif est réalisée, les liaisons entre les variables et les valeurs sont effectuées, puis test est évalué. Si la valeur de test est true, la reconnaissance du motif est validée et la valeur de expr est renvoyée normalement. Si par contre la valeur de test est false, la reconnaissance du motif est invalidée, les liaisons sont annulées et Caml passe au cas suivant (s’il existe).


#let f = function  
      |   (m,n) when m = n -> 0  
      |   (m,n) when m > n -> 1  
      |    _ -> -1;;  
f : ’a * ’a -> int = <fun>  
#f(1,0);;  
- : int = 1  
#f(1,2);;  
- : int = -1  
#f(3,3);;  
- : int = 0


Programme 2.66: motif conditionnel

2.3.3 Boucles avec tests booléens ou boucles conditionnelles

Il arrive très souvent que l’on ait besoin d’effectuer une action tant qu’une condition est vérifiée. Pour cela, Caml dispose d’une structure de contrôle particulière, qui est une structure répétitive conditionnelle, encore appelée boucle conditionnelle.

L’évaluation de l’expression

while test do action done

effectue action tant que le test (qui doit être une expression à valeur booléenne) retourne true. Le test est effectué avant que l’action ne soit effectuée ; en conséquence, si lors de la première exécution de la boucle, test s’évalue en false, l’action n’est jamais effectuée. L’expression Caml while elle même retourne le résultat () (c’est-à-dire rien).

Essayons de construire une fonction qui à deux entiers x et y associe la plus grande puissance de x qui est inférieure ou égale à y. Il suffit d’utiliser une variable que nous initialiserons à 1, puis que nous multiplierons par x jusqu’à ce qu’elle devienne strictement supérieure à y. Ceci suggère d’utiliser une référence pour stocker la valeur de cette variable et une boucle pour effectuer les multiplications successives. Nous pouvons écrire une telle fonction sous la forme (en supposant au départ que x > 1 et y 1)


#let pg_puissance x y =  
            let p = ref 1 in  
            while !p <= y do p := !p * x  done;  
            !p / x;;  
pg_puissance : int -> int -> int = <fun>  
#pg_puissance 2 63;;  
- : int = 32  
#pg_puissance 2 64;;  
- : int = 64  
#pg_puissance 6 5;;  
- : int = 1  
#pg_puissance 5 12345678;;  
- : int = 9765625


Programme 2.67: boucle avec test booléen

Montrons que notre fonction calcule bien la plus grande puissance xn telle que xn y. Au départ la valeur pointée par p est bien une puissance de x (1 = x0) et elle est inférieure ou égale à y. Tant que la boucle est effectuée, au départ de l’exécution du corps de la boucle, la valeur pointée par p reste une puissance de x qui est inférieure ou égale à y. Comme la suite des valeurs pointées par p est strictement croissante (car x > 1), au bout d’un nombre fini d’opérations, cette valeur pointée par p devient strictement supérieure à y et le test retournant false, il y a sortie de la boucle ; à ce moment la valeur pointée par p est strictement supérieure à y, mais la valeur précédente !p/x est inférieure ou égale à y ; il ne reste plus qu’à retourner la valeur précédente !p/x qui est la plus grande puissance de x inférieure à y (puisque la suivante est strictement supérieure à y).

Notre fonction n’est pas parfaite puisqu’elle n’est pas protégée contre un comportement stupide de l’utilisateur qui introduirait par exemple des nombres négatifs ou la valeur x = 1 qui bouclerait indéfiniment. Elle impose donc des conditions aux paramètres (ce qu’on appelle des préconditions), ici x > 1 et y 1. Nous avons par contre démontré que la boucle accomplissait bien ce qu’on attendait d’elle (transformer la valeur 1 pointée par p en la plus petite puissance de x strictement supérieure à y) et ceci en deux temps : en exhibant d’une part une propriété qui reste invariante tout au long de l’exécution de la boucle (à l’entrée dans l’exécution de la boucle, la valeur pointée par p est une puissance de x inférieure ou égale à y), en montrant d’autre part que la boucle s’arrêtait au bout d’un nombre fini d’exécutions (du fait que la suite pointée par p est strictement croissante). Nous retrouverons cette technique de preuve tout au long de ce cours.

2.3.4 Boucles indexées ou inconditionnelles

Fréquemment, une boucle consiste simplement à définir un compteur entier, à l’initialiser à une valeur entière début et à l’incrémenter (ou le décrémenter) de 1 à chaque exécution du corps de la boucle jusqu’à ce qu’il dépasse une valeur fin fixée au départ. Caml, comme beaucoup de langages, dispose d’une instruction particulière pour effectuer ceci qui est beaucoup plus efficace que la boucle while, aussi bien du point de vue de la programmation que de l’exécution. Il s’agit d’une structure répétitive inconditionnelle, encore appelée boucle indexée.

L’instruction

for compteur=début to fin do expression done

évalue tout d’abord les expressions début et fin : les résultats doivent être des entiers n et p ; ensuite le corps de la boucle expression est évalué en liant successivement l’identificateur compteur aux valeurs n,n + 1,,p (c’est-à-dire que compteur prendra successivement ces différentes valeurs) ; si n > p le corps de la boucle n’est jamais évalué, sinon il est évidemment évalué p - n + 1 fois. La liaison du compteur9 et de ses valeurs est locale à la boucle et masque toute liaison qui pouvait exister antérieurement (bien entendu sans la détruire). L’expression

for compteur=début to fin do expression done

elle même renvoie une valeur de type unit, c’est-à-dire rien ; le corps de la boucle lui-même est souvent une séquence d’expressions. On peut par exemple facilement programmer une procédure qui écrit tous les cubes des entiers de m à n de la façon suivante


#let ecris_cube m n =  
         for i = m to n do  
             print_int(i*i*i); print_newline()  
         done;;  
 
ecris_cube : int -> int -> unit = <fun>  
#ecris_cube 4 8;;  
64  
125  
216  
343  
512  
- : unit = ()  
#ecris_cube 8 6;;  
- : unit = ()


Programme 2.68: boucle indexée

La boucle indexée croissante a un analogue décroissant où on remplace seulement le mot clé to par le mot clé downto. L’instruction

for compteur=début downto fin do expression done

évalue tout d’abord les expressions début et fin qui doivent s’évaluer en des entiers n et p ; ensuite le corps de la boucle expression est évaluée en liant successivement l’identificateur compteur aux valeurs n,n - 1,,p (c’est-à-dire que compteur prendra successivement ces différentes valeurs) ; si n < p le corps de la boucle n’est jamais évalué, sinon il est évalué p - n + 1 fois.

Pour écrire les cubes en décroissant :


#let ecris_cube_dec m n =  
         for i = m downto n do  
             print_int(i*i*i); print_newline()  
         done;;  
ecris_cube_dec : int -> int -> unit = <fun>  
#ecris_cube_dec 10 6;;  
1000  
729  
512  
343  
216  
- : unit = ()  
#ecris_cube_dec 6 8;;  
- : unit = ()


Programme 2.69: boucle indexée décroissante

Comme on aura l’occasion de le voir dans les chapitres suivants, les techniques de preuves sur les boucles indexées sont les mêmes que sur les boucles à tests booléens : recherche d’un invariant, démonstration de la terminaison.

2.4 Types de données

Sans chercher à formaliser complètement la notion de type de données dans un langage de programmation, disons simplement qu’elle recouvre assez bien la notion d’ensemble mathématique. Nous allons étudier les types de données préexistants dans Caml, puis les constructeurs de nouveaux types.

2.4.1 Types simples

Nous avons déjà rencontré la plupart des types simples préexistants dans Caml :

Il faut prendre garde au fait que les deux premiers types ont leur domaine de validité. Le type int est limité à des entiers compris entre - 230 et 230 - 1 ; un calcul qui conduit à des résultats partiels ou à un résultat final en dehors de cet intervalle ne produit pas d’erreur, mais donne des résultats qui semblent mathématiquement incorrects, à moins de comprendre qu’il s’agit d’une arithmétique dans Z∕nZ pour n = 231. L’exemple suivant montre qu’en élevant successivement un nombre entier au carré, on finit par aboutir à un résultat négatif.


#let x = ref 3 in  
      while !x>0 do  
           x := !x * !x;  
           print_int(!x);  
           print_newline()  
      done;;  
9  
81  
6561  
43046721  
-501334399  
- : unit = ()


Programme 2.70: débordement d’entiers

Les limites sur les réels en virgule flottante sont plus larges, et dépendent de la machine :


#let x = ref 3. in  
      for i = 1 to 11 do  
           x := !x*. !x;  
           print_float(!x);  
           print_newline()  
      done;;  
9  
81  
6561  
43046721  
1.85302018885e+15  
3.43368382029e+30  
1.17901845777e+61  
1.39008452377e+122  
1.93233498323e+244  
INF  
INF


Programme 2.71: débordement de flottants

Remarquons que Caml n’utilise qu’un nombre limité de chiffres significatifs et passe en notation scientifique dès que ce nombre est dépassé : ici 1.39008452377e+122 désigne le nombre décimal 1.39008452377 10122.

Ajoutons à ces types simples l’ensemble des caractères, dénoté par le type char ; il comprend les lettres, les chiffres et les symboles affichables sur votre écran, plus quelques autres ; un caractère est noté entre deux accents graves (pour ne pas le confondre avec un identificateur du langage). Ainsi ‘a‘, ‘Z‘, ‘1‘, ‘#‘ sont des caractères. Il existe aussi quelques caractères spéciaux comme le caractère noté ‘\n‘ qui désigne le caractère caché de passage à la ligne suivante (le retour-chariot) ou le caractère ‘\\‘ qui désigne la barre oblique inverse. Chaque caractère a un code (appelé code ASCII) qui est un nombre compris entre 0 et 255. Deux fonctions permettent de passer d’un caractère à son code (la fonction int_of_char) ou du code au caractère (le fonction char_of_int) ; la fonction print_char permet d’afficher à l’écran un caractère. On peut par exemple afficher tous les caractères standards visibles (leur code commence à 32 et s’arrête à 127) :


#for i = 1 to 3 do  
for j = 0 to 31 do  
      print_char(char_of_int(32*i+j))  
   done;  
   print_newline()  
done;;  
 !"#$%&’()*+,-./0123456789:;<=>?  
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_  
‘abcdefghijklmnopqrstuvwxyz{|}~  
- : unit = ()


Programme 2.72: codes des caractères

2.4.2 Chaînes de caractères

Nous avons rencontré le type caractère dans le paragraphe précédent. Comme d’habitude, un assemblage de caractères fait un mot ou une phrase. Caml dispose du type string (c’est-à-dire chaîne) pour dénoter ces assemblages de caractères, que nous appellerons de façon plus précise des chaînes de caractères. Une chaîne de caractères est donc une suite (ou un tableau) de caractères numérotés à partir de 0 : le premier caractère de la chaîne a donc le numéro 0 et le dernier a pour numéro n - 1, si n est le nombre total de caractères de la chaîne.

Pour délimiter une chaîne de caractères, il suffit d’encadrer la suite de caractères par des guillemets ". Dans une telle chaîne de caractère, tous les caractères sont autorisés (en particulier les espaces) à l’exception de deux qui ont une signification spéciale : " et \ ; le premier sert à délimiter la chaîne de caractères, le second à introduire des caractères spéciaux. Les caractères spéciaux commencent tous par un \ ; parmi ceux ci nous noterons les plus utiles :

Voici donc quelques chaînes de caractères valides

et quelques chaînes de caractères non valides : "Il dit "bonjour"" (le deuxième guillemet est considéré comme délimitant la fin de la chaîne de caractères, et le reste perd toute signification), "b:\caml" (car \c n’est pas un caractère valide).

Il existe de nombreuses fonctions ou procédures manipulant les chaînes de caractères. Parmi celles ci, signalons

Voici quelques exemples :


#let s = "Nous n’irons plus au bois";;  
s : string = "Nous n’irons plus au bois"  
#string_length s;;  
- : int = 25  
#s.[2];; (* CAML 0.7 *)  
- : char = ‘u‘  
#nth_char s 2;;  
- : char = ‘u‘  
#s.[13] <- ‘P‘;; (* CAML 0.7 *)  
- : unit = ()  
#s;;  
- : string = "Nous n’irons Plus au bois"  
#set_nth_char s 5 ‘N‘;;  
- : unit = ()  
#s;;  
- : string = "Nous N’irons Plus au bois"


Programme 2.73: chaînes de caractères

Les chaînes de caractères ne disposent que d’un seul opérateur : la concaténation. L’opérateur de concaténation est désigné par l’accent circonflexe ^ ; il renvoie une nouvelle chaîne de caractères obtenue en collant les deux chaînes opérandes :


#s ^ ", les lauriers sont coupes";;  
 - : string = "Nous N’irons plus au bois, les lauriers sont coupes"


Programme 2.74: concaténation de chaînes de caractères

2.4.3 Types fonctionnels

Nous avons déjà rencontré précédemment les types fonctionnels. Si type1 et type2 sont deux types, le type

type1 -> type2

est le type de l’ensemble des fonctions de l’ensemble des objets de type type1 dans l’ensemble des objets de type type2.

2.4.4 Produits cartésiens

Nous avons déjà rencontré précédemment les produits cartésiens de types. Si type1,,typeN sont N types, le type

type1 **typeN

est le type des N-uplets dont le premier élément est de type type1,, le N-ième de type typeN. Un tel N-uplet est écrit comme en mathématiques, les éléments étant séparés par des virgules, les parenthèses encadrantes étant facultatives.

Par exemple (1 , "essai" , 3.14) est un objet de type int * string * float.

2.4.5 Références

Nous avons déjà rencontré précédemment les références vers un type. Si type1 est un type, le type type1 ref désigne l’ensemble des références vers le type type1, c’est-à-dire des objets Caml désignant un emplacement mémoire dans lequel est stocké un objet de type type1. Si x est de type type1 ref, alors !x désigne l’objet de type type1 pointé par la référence (c’est-à-dire contenu dans l’emplacement mémoire) et on modifie l’objet pointé par x par l’opérateur :=.

2.4.6 Tableaux ou vecteurs

Les tableaux (ou vecteurs) sont des suites finies, de taille variable (mais fixée au départ) de valeurs du même type, ces valeurs étant modifiables. Un tableau peut être créé de manière littérale par la construction

[| objet1 ; ;objetN |]

où les N objets sont du même type leType. Le type d’un tel objet tableau est alors leType vect. Contrairement aux listes (que nous verrons plus loin) les tableaux ne sont pas redimensionnables une fois créés. Voici un exemple de création d’un tableau de taille 4 lié à l’identificateur v :


#let v = [| 1 ; 2 ; 3 ; 4 |];;  
 v : int vect = [|1; 2; 3; 4|]


Programme 2.75: définition extensive de tableau

Comme pour une chaîne de caractères, les éléments d’un tableau de longueur N sont numérotés de 0 à N - 1. On accède au p-ième élément d’un tableau v sous la forme v.(p) (qui est de type leType si v est de type leType vect). Comme une référence, un élément d’un tableau est modifiable en place par la construction

monTableau.(numéro) <- expression

qui remplace dans monTableau (qui est de type leType vect) l’élément numéro par la valeur de expression (qui doit être de type leType). C’est ainsi, qu’avec la définition ci dessus :


#let v = [| 1 ; 2 ; 3 ; 4 |];;  
 v : int vect = [|1; 2; 3; 4|]  
#v.(0);;  
 - : int = 1  
#v.(0),v.(1),v.(2);;  
- : int * int * int = 1, 2, 3  
#v.(1)<- 31415;;  
 - : unit = ()  
#v;;  
 - : int vect = [|1; 31415; 3; 4|]


Programme 2.76: accès aux éléments d’un tableau

En Caml 0.7, on peut aussi utiliser la construction équivalente

monTableau.(numéro) := expression

pour affecter une valeur à un élément d’un tableau.

On dispose de nombreuses fonctions de manipulation de tableaux. Citons entre autres

Voyons un exemple :


#let v = make_vect 6 0;;  
 v : int vect = [|0; 0; 0; 0; 0; 0|]  
#for i = 0 to 5 do v.(i)<- i*i  done;;  
 - : unit = ()  
#v;;  
 - : int vect = [|0; 1; 4; 9; 16; 25|]  
#let decremente x=x-1;;  
 decremente : int -> int = <fun>  
#let w = map_vect decremente v;;  
 w : int vect = [|-1; 0; 3; 8; 15; 24|]  
#let ecris_int x = print_int(x); print_char(‘,‘);;  
 ecris_int : int -> unit = <fun>  
#do_vect ecris_int w;;  
 -1,0,3,8,15,24,- : unit = ()


Programme 2.77: fonctions sur les tableaux

Nous construisons d’abord un tableau initialisé avec la valeur 0, tableau que nous remplissons ensuite avec les carrés des entiers. Nous créons ensuite une fonction decremente qui à un entier n associe n - 1 et nous obtenons un nouveau tableau w en appliquant cette fonction à v. Enfin, nous créons une procédure qui écris un entier n suivi d’une virgule et nous appliquons cette procédure à tous les éléments de w.

2.4.7 Listes

Un des gros inconvénients des tableaux est leur caractère figé en ce qui concerne la taille. Bien entendu on peut faire croître un tableau en le recopiant dans un tableau plus grand, mais c’est à la fois coûteux en temps et en mémoire. Pour le cas de structures dynamiques (dont la taille est appelée à évoluer au cours de l’exécution du programme), la structure de liste est mieux adaptée que la structure de tableau.

Les listes sont des suites finies, de taille variable au cours du temps, formées de valeurs du même type. En fait les listes sont définies de la manière suivante (par récurrence)

Une telle définition par récurrence (ici sur la longueur de la liste) est appelée en informatique une définition récursive10.

Cette définition a un certain nombre de conséquences. La première (et c’est l’effet recherché) c’est qu’une liste peut croître au cours du temps par simple ajout d’un élément en tête de la liste. La deuxième, qui peut être considérée comme une contrainte, est que dans une liste on ne peut accéder directement qu’au premier élément de la liste (encore appelé la tête ou le car) et à la liste composée de tous les éléments sauf le premier (encore appelée le reste ou le cdr11). Le plus simple pour cela est d’utiliser une reconnaissance de motif sous la forme

match maListe with h::r -> expression

qui liera h avec la tête et r avec le reste de la liste non vide maListe dans l’évaluation de expression ; il faudra simplement veiller à distinguer soigneusement le cas de la liste vide qui n’a ni tête ni reste pour construire une fonction robuste. Le traitement des listes se fera donc la plupart du temps sous la forme


   match maListe with  
       []   -> expression1  
    |  h::r -> expression2


Programme 2.78: traitement de listes par reconnaissance de motifs

Une liste peut être créée explicitement par la construction

[ objet1 ; ;objetN ]

où les N objets sont du même type leType. Le type d’un tel objet liste est alors leType list. Voici un exemple de création d’une liste de taille 4 lié à l’identificateur v ainsi que le renvoi du couple formé de la tête et du reste de la liste


#let maListe = [0;1;2;3;4;5];;  
 maListe : int list = [0; 1; 2; 3; 4; 5]  
#match maListe with deb::fin ->  (deb,fin);;  
 > Toplevel input: >match maListe with deb::fin -> (deb,fin);;  
 >                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^  
 > Warning: pattern matching is not exhaustive  
 - : int * int list = 0, [1; 2; 3; 4; 5]


Programme 2.79: définition extensive de liste, motifs sur les listes

Remarquez que Caml nous avertit au passage que nous avons oublié d’examiner le cas où la liste maListe aurait été vide (ce qui n’est manifestement pas le cas ici).

On dispose de nombreuses fonctions de manipulation de listes (bien plus nombreuses que pour les tableaux). Citons entre autres

Nous reviendrons plus longuement sur les listes quand nous parlerons des structures de données récursives.

2.4.8 Types construits, types sommes

Contrairement à d’autres langages, il est possible en Caml de construire de nouveaux types autrement que par simple assemblage de types précédemment définis. On obtient ce qu’on pourrait appeler des types formels et que Caml préfère appeler des types construits.

Pour cela considérons Constr un identificateur (appelé un constructeur de type). Alors la déclaration

type monType = Constr

construit un nouveau type (c’est-à-dire un nouvel ensemble de valeurs) de nom monType n’ayant qu’une seule valeur à savoir Constr (un peu analogue à la définition d’une constante mathématique de nom Constr qui ne serait jamais évaluée). On dit alors que Constr est un constructeur constant (nous avons en fait déjà rencontré quatre constructeurs constants, à savoir true, false, [] et ()).

De la même façon, si on désigne par leType un type déjà connu, alors la déclaration

type monType = Constr of leType

construit un nouveau type (c’est-à-dire un nouvel ensemble de valeurs) de nom monType dont les valeurs sont exactement les assemblages Constr x x est un objet de type leType ; ceci est tout à fait analogue à une fonction formelle mathématique f(x) qui ne serait jamais évaluée (de la même façon que dans une expression mathématique on manipule le symbole sin(1) sans jamais l’évaluer). On dit alors que Constr est un constructeur non constant.

Tout ceci ne serait pas bien intéressant pour construire de nouveaux types si on ne pouvait pas mêler à volonté au sein d’un même type des types construits que ce soit avec des constructeurs constants ou avec des constructeurs non constants. On obtient ainsi des types sommes, tout à fait analogues à une réunion d’ensembles mathématiques (réunion évidemment disjointe). Pour cela il suffit de séparer les différentes constructions de type par une barre verticale |. C’est ainsi que pour définir un nouveau type qui mèle à la fois deux constantes Gamma et Epsilon, des ”sinus” d’entiers Sin x et des couples formés d’une chaîne de caractère et d’un réel, on pourra poser


#type Idiot =  Gamma |  Epsilon  |  
                Sin of int    |  
                Couple of string * float;;  
Type Idiot defined.


Programme 2.80: type construit

et à partir de cette déclaration, on dispose de nouvelles valeurs

Maintenant nous pouvons poser :


#let x1 = Gamma;;  
x1 : Idiot = Gamma  
#let x2 = Sin 2;;  
x2 : Idiot = Sin 2  
#let x3 = Couple("baba",3.1415);;  
x3 : Idiot = Couple ("baba", 3.1415)


Programme 2.81: utilisation de type construit

De cette manière nous avons construit une réunion disjointe de deux singletons, de l’ensemble des sinus d’entiers et du produit cartésien de l’ensemble des chaînes de caractères par l’ensemble des réels en virgule flottante.

Rien ne nous interdit alors de définir une fonction f qui associera à Gamma la valeur 0.0, à Epsilon la valeur 10-10, à un entier considéré comme un nombre réel son sinus (le vrai cette fois) et à un couple formé d’une chaîne de caractères et d’un réel, ce réel. Par reconnaissance de motif, c’est très facile :


let f = function  
            Gamma -> 0.0  
        |   Epsilon -> 1e-10  
        |   Sin n -> sin(float_of_int(n))  
        |   Couple(s,x) -> x;;  
f : Idiot -> float = <fun>  
#f Epsilon;;  
- : float = 1e-10  
#f x2;;  
- : float = 0.909297426826  
#f x3;;  
- : float = 3.1415


Programme 2.82: reconnaissance de motifs dans un type construit

On remarque que la reconnaissance de motif suit exactement la définition du type. Ce n’est pas indispensable, mais si nous oublions d’examiner un cas, Caml nous en avertira en précisant que la liste des motifs n’est pas exhaustive pour le type en question (autrement dit que le domaine de définition de notre fonction n’est pas l’ensemble considéré tout entier).

On peut même définir des types sommes génériques, c’est-à-dire dont le type dépend de certains paramètres qui sont eux-mêmes des types (analogues aux vecteurs, listes ou références qui dépendent du type auxquels on les applique). Pour cela, on fait précéder le nom du nouveau type des paramètres de type qu’il recevra, séparés par des virgules et encadrés par des parenthèses s’il y en a plusieurs ; bien entendu, comme on l’a déjà vu, les paramètres de type sont précédés d’une apostrophe.

C’est ainsi que l’on définira un type générique Bidon qui associera à deux types quelconques type1 et type2 un nouveau type (type1,type2) Bidon comprenant une constante universelle Rho et des triplets (x,y,z) d’un élément de type type1, d’un élément de type type2 et d’un entier de la façon suivante


#type (’a, ’b) Bidon =  
                  Rho  
               |  Triplet of (’a * ’b * int);;  
Type Bidon defined.  
#let x1 = Triplet (2,"abc",10);;  
x1 : (int, string) Bidon = Triplet (2, "abc", 10)


Programme 2.83: paramètres de types génériques

On voit que Caml a reconnu que x1 est lié à une valeur de type (int, string) Bidon.

Ces constructions de type génériques sont très puissantes. Nous y ferons largement appel dans le chapitre consacré aux listes

2.4.9 Types enregistrements

Le dernier type d’objets utilisé par Caml est le type enregistrement. Il part de la constatation qu’un objet courant est souvent construit à partir d’un certain nombre de caractéristiques (un nom, un prénom, une adresse, un numéro de compte, un montant, etc.), les unes étant fixes (nom, prénom, numéro de compte), les autres étant variables (montant, éventuellement adresse). Caml (comme Pascal ou C) permet de définir des objets de type enregistrement, chacun ayant un certain nombre de champs qui sont eux mêmes de objets Caml. Chaque champ est décrit par un identificateur (un nom). Prenons l’exemple d’un compte en banque. Dans un tableur, on présenterait par exemple l’ensemble des comptes en banque sous la forme :






nom prénom adressenuméro de comptemontant










MitterrandFrançoisPalais de l’Elysée 1254712504,00





Balladur Edouard Hotel Matignon 5421811152,38





De la même façon, nous représenterons chaque ligne par un objet Caml composé de cinq champs : un champ nom de type string, un champ prenom de type string, un champ adresse de type string, un champ numero de type int et un champ montant de type float. Pour cela nous ferons une déclaration de type sous la forme


#type compte_en_banque = {nom:string; prenom: string;  
          mutable adresse:string; numero: int;  
          mutable montant: float};;  
Type compte_en_banque defined.


Programme 2.84: type enregistrement

Le mot clé mutable précède les noms des champs (on dit plutôt les étiquettes) qui seront modifiables, un peu à la manière d’une référence. On peut alors poser


#let xMit = { nom = "Mitterrand";prenom = "Francois";  
      adresse = "Palais de l’Elysee";  
      numero=12547; montant=12504.00 };;  
xMit : compte_en_banque = {nom = "Mitterrand"; prenom = "Francois";  
      adresse = "Palais de l’Elysee"; numero = 12547; montant = 12504}


Programme 2.85: création d’un objet de type enregistrement

A partir de cet instant, l’identificateur xMit est lié à un objet composé de 5 champs, dont deux seront modifiables. On accèdera à un champ donné d’un objet sous la forme

nom_objet.etiquette


#xMit.adresse;;  
- : string = "Palais de l’Elysee"  
#xMit.numero;;  
- : int = 12547


Programme 2.86: accès aux champs d’un enregistrement

Les champs modifiables sont modifiés comme les éléments d’un tableau sous la forme

nom_objet.etiquette<-valeur

En Caml 0.7 on peut utiliser la construction équivalente

nom_objet.etiquette:=valeur

pour affecter une valeur à un champ modifiable d’un enregistrement.


#xMit.adresse <- "Latche";;  
- : unit = ()  
#xMit;;  
- : compte_en_banque = {nom = "Mitterrand"; prenom = "Francois";  
          adresse = "Latche"; numero = 12547; montant = 12504}


Programme 2.87: champs modifiables d’un enregistrement

2.4.10 Nommer des types

Nous avons vu précédemment comment Caml permettait d’enrichir les types simples de départ (entiers, réels en virgule flottante, booléens, caractères, chaînes de caractères, unit) au moyen de nouvelles constructions : fonctions, produits cartésiens, références, tableaux, listes. Ces nouveaux types peuvent être nommés en leur attribuant un identificateur. Pour ceci, Caml utilise la syntaxe

type [type_params] type_ident ==expression_type

type_params désigne une liste facultative de paramètres de types de la forme ’ident et où expression_type désigne une expression de type avec les règles suivantes :

2.5 Les motifs

Les motifs sont une des particularités les plus intéressantes de Caml. Certains autres langages de programmation, comme celui de Mathematica ou dans une moindre mesure celui de Maple, disposent également de la notion de motif et de la reconnaissance. Nous savons comment utiliser les motifs grâce à la construction

match expr with motif1 -> expr1 | motif2 -> expr2 | | motifn -> exprn

et son extension aux définitions de fonctions sous la forme

function motif1 -> expr1 | motif2 -> expr2 | | motifn -> exprn

Nous allons voir ici de façon plus précise la syntaxe des motifs et les règles qui gouvernent la reconnaissance des motifs.

2.5.1 Syntaxe des motifs

Les règles qui gouvernent la syntaxe des motifs sont les suivantes

2.5.2 La reconnaissance des motifs

Les règles qui gouvernent la reconnaissance des motifs sont les suivantes

2.6 Les exceptions

2.6.1 Qu’est-ce qu’une exception ?

Il arrive de temps en temps que l’on veuille brutaliser un programme en lui faisant adopter un comportement pour lequel il ne semble pas prévu. Cela peut se produire pour deux raisons principales : soit parce qu’une erreur majeure s’est produite au cours de l’exécution d’une instruction qui rend sans intérêt l’exécution des instructions suivantes, soit au contraire parce qu’une instruction a permis d’aboutir à un résultat souhaité qui rend sans objet l’exécution des instructions suivantes.

Le premier cas est typique des erreurs de calcul ou d’entrée-sortie. Si lors de l’évaluation d’une expression complexe se produit une erreur de calcul (division par 0 ou logarithme d’un nombre négatif par exemple), la poursuite de l’évaluation de l’expression n’a plus aucune signification et il vaut mieux s’arrêter, soit en interrompant carrément l’exécution du programme (c’est le comportement de la plupart des langages de programmation), soit en interceptant l’erreur pour renvoyer une valeur par défaut ou demander à l’utilisateur de modifier ses données pour éviter que l’erreur ne se reproduise (ce que permet Caml). Il en est de même lors de la lecture d’un fichier sur une disquette : si une erreur se produit parce que le fichier n’existe pas, il est vain d’exécuter la suite du programme qui devait servir à traiter le fichier en question.

Le deuxième cas est typique d’un certain nombre d’algorithmes de recherches d’un élément dans une structure donnée (tableau, liste, arbres, tables,) : on peut construire une fonction qui explore systématiquement la structure pour chercher l’élément en question, mais qui s’interrompt brutalement en criant ”j’ai trouvé” dès sa découverte.

La plupart des langages de programmation permettent de gérer les erreurs d’entrée-sortie de manière raisonnable, car ces erreurs sont extrêmement fréquentes et difficilement prévisibles : il serait inadmissible qu’un programme de traitement de textes se bloque irrémédiablement dès que l’utilisateur commet une faute d’orthographe dans le nom d’un fichier. Par contre beaucoup de langages de programmation ne savent pas gérer les erreurs arithmétiques autrement que par l’interruption totale de l’exécution du programme : dans ce cas, il est de la responsabilité du programmeur d’éviter par des tests adéquats qu’une telle erreur puisse se produire (tester si un nombre est non nul avant d’effectuer une division par exemple). Enfin, très peu de ces langages permettent au programmeur non seulement d’intercepter les erreurs non désirées, mais aussi de créer lui-même de nouveaux comportements exceptionnels. Nous allons voir que Caml le permet très facilement.

2.6.2 Les exceptions prédéfinies

Caml dispose au départ d’un certain nombre d’exceptions prédéfinies qui toutes correspondent à des erreurs détectées au cours de l’exécution d’un programme. Il en est ainsi de l’exception de division par 0 qui correspond à une erreur arithmétique :


#1/0;;  
Uncaught exception: Division_by_zero


Programme 2.88: division par zéro

Remarquons que le calcul similaire ne produit pas d’exception avec des nombres réels en virgule flottante car les calculs ne sont plus gérés par Maple mais par le processeur arithmétique de l’ordinateur qui se contente de renvoyer par exemple un NAN (Not A Number) ou un INF (infini) :


#log(-1.);;  
- : float = NAN(036).0  
#1. /. 0. ;;  
- : float = INF.0


Programme 2.89: erreurs en virgule flottante

Une autre exception classique déclenchée par l’exécution d’un programme est Invalid_argument (argument invalide). Cette exception est déclenchée par Caml chaque fois qu’une fonction reçoit des paramètres pour lesquelles elle n’a pas de sens. Un cas typique est la demande d’accès à un élément d’indice n dans un tableau ou dans une chaîne de caractères, alors que la longueur de l’objet est plus petite que n. En ce qui concerne une chaîne de caractères, Caml nous prévient que l’exception Invalid_argument a été déclenchée par la fonction nth_char dont la fonction est justement d’accéder au caractère d’indice n d’une chaîne donnée (rappelons que les indices commencent à 0)


#let chaine="Nous n’irons plus aux bois";;  
chaine : string = "Nous n’irons plus aux bois"  
#chaine.[25];;  
- : char = ‘s‘  
#chaine.[30];;  
Uncaught exception: Invalid_argument "nth_char"


Programme 2.90: débordement dans une chaîne de caractères

De même dans un tableau avec la fonction vect_item qui se charge d’accéder à l’élément d’indice n d’un tableau (toujours à partir de 0) :


#let tableau=[|1;2;3|];;  
tableau : int vect = [|1; 2; 3|]  
#tableau.(2);;  
- : int = 3  
#tableau.(3);;  
Uncaught exception: Invalid_argument "vect_item"


Programme 2.91: débordement dans un tableau

Un autre type d’erreurs peut se produire lors d’un filtrage par un motif. Si aucun des cas examinés n’est reconnu par le filtrage, Caml déclenche l’exception Match_failure. Normalement, ce type d’erreurs ne peut se produire que si le filtrage n’est pas exhaustif, ce dont Caml vous prévient préalablement. Dans la fonction suivante, nous n’avons défini que f(0) et nous demandons de calculer f(2) :


#let f= function 0 -> 1;;  
Toplevel input:  
>let f= function 0 -> 1;;  
>       ^^^^^^^^^^^^^^^  
Warning: this matching is not exhaustive.  
f : int -> int = <fun>  
#f 2;;  
Uncaught exception: Match_failure ("", 182, 197)


Programme 2.92: erreur dans un filtrage

Caml dispose de deux autres exceptions utilisées par la bibliothèque standard qui sont

2.6.3 Déclencher une exception

Rien n’est plus facile que de déclencher soi-même une exception. La fonction prédéfinie raise suivie du nom de l’exception provoque son déclenchement. De cette façon vous pourrez poser


#let f x= if x=0.0 then  
             raise Division_by_zero  
             else (x +. 1.) /. x;;  
f : float -> float = <fun>  
#f(1.);;  
- : float = 2.0  
#f(0.);;  
Uncaught exception: Division_by_zero


Programme 2.93: déclenchement d’une exception

De même, au cours d’une recherche d’un élément dans un tableau, vous pourrez déclencher l’exception prédéfinie Not_found si l’élément ne s’y trouve pas.

Les deux exceptions Failure et Invalid_argument sont mêmes tellement courantes, que Caml a prévu des fonctions spéciales pour les déclencher. C’est ainsi que failwith message, où message est une chaîne de caractères, est équivalent à raise Failure message. De même invalid_arg message, où message est une chaîne de caractères, est équivalent à raise Invalid_argument message. C’est ainsi que l’on pourra poser :


#let f x= if x>0.0  
            then log(x)  
            else invalid_arg "logarithme non défini";;  
f : float -> float = <fun>  
#f(1.5);;  
- : float = 0.405465108108  
#f(-3.);;  
Uncaught exception: Invalid_argument "logarithme non défini"


Programme 2.94: déclenchement d’une exception : argument non valide

ou bien :


#let f x=  
        let y=sin(x) in  
          if y>0.0  
             then log(y)  
             else failwith "fonction non définie";;  
f : float -> float = <fun>  
#2. +. f(1.5);;  
- : float = 1.99749184381  
#2. +. f(3.5);;  
Uncaught exception: Failure "fonction non définie"


Programme 2.95: déclenchement d’une exception : erreur lors d’un calcul

2.6.4 Rattraper une exception

Tel que nous l’avons décrit pour le moment, le mécanisme des exceptions souffre d’un grave défaut : tout déclenchement d’exception provoque l’arrêt du programme avec affichage d’un message d’erreur. Il s’agit d’un comportement assez primaire, qui n’est pas acceptable en programmation évoluée. Heureusement Caml permet de rattraper (on dit encore d’intercepter) une exception à l’aide de la construction

try expr with filtrage

Comme tout dictionnaire anglais-français vous l’indiquera, try signifie essayer. Lors de l’évaluation de l’expression try expr with filtrage, Caml essaye d’abord d’évaluer la sous-expression expr. Si aucune exception n’est déclenchée par cette évaluation, tout se passe normalement et la valeur de l’expression totale est simplement la valeur de la sous expression expr. Par contre si l’évaluation de expr déclenche une exception, Caml passe immédiatement au filtrage de cette exception par filtrage ; la valeur de l’expression totale est alors la valeur attribuée par le filtrage qui est chargé de prendre les mesures adéquates suivant le type d’exception déclenché.

Définissons par exemple une fonction de division entière qui renvoie 0 quand le dénominateur est nul :


#let div x y=  
      try x/y with Division_by_zero->0;;  
div : int -> int -> int = <fun>  
#div 9 3;;  
- : int = 3  
#div 9 0;;  
- : int = 0


Programme 2.96: division entière sans division par zéro

Bien entendu le filtrage peut prendre en compte plusieurs exceptions et renvoyer des résultats adaptés. C’est ainsi que l’on pourrait imaginer quelque chose du type


#let ma_fonction expr=  
         try  
            .........  (* des tas de choses *)  
          with  
             Division_by_zero -> "coucou"  
           | Invalid_argument s -> "erreur:" ^ s  
           | Failure x -> "faute:" ^ x  
           | Not_found -> "pas trouvé" ;;


Programme 2.97: gestion d’exceptions multiples

2.6.5 Définir une nouvelle exception

On peut avoir besoin de définir de nouvelles exceptions pour répondre à des besoins particuliers. En premier lieu, ce peut être pour gérer de nouvelles erreurs susceptibles de se produire dans des fonctions que nous définissons. Mais également, comme nous allons le voir ci dessous, la définition de nouvelles exceptions peut aussi conduire à un style remarquable de programmation.

Définissons une fonction de recherche d’un élément dans un tableau de la manière suivante : nous explorons tout le tableau à la recherche d’un élément à l’aide d’une simple boucle indexée ; dès que l’élément en question est trouvé, nous interrompons la boucle par le déclenchement d’une exception (c’est d’ailleurs le seul moyen en Caml d’interrompre une boucle indexée) ; cette exception sera bien entendu interceptée pour annoncer que l’élément a été trouvé, le filtrage de l’exception renvoyant la valeur true ; si par contre la boucle se déroule jusqu’au bout, c’est que l’élément recherché ne figure pas dans le tableau et nous renvoyons la valeur booléenne false.

Pour cela nous allons définir une nouvelle exception sans paramètre Trouve (analogue à un constructeur constant). Cela se fait à l’aide de la construction

exception nom_exception

soit ici exception Trouve. Voici ce que l’on peut écrire :


#exception Trouve;;  
Exception Trouve defined.  
#let cherche t x=  
     try  
        for i=0 to (vect_length t)-1 do  
           if t.(i)=x then raise Trouve  
        done;  
        false  
     with Trouve -> true;;  
cherche : ’a vect -> ’a -> bool = <fun>  
#cherche [| 1;7;4;5 |] 4;;  
- : bool = true  
#cherche [| 1;7;4;5 |] 3;;  
- : bool = false


Programme 2.98: recherche dans un tableau

Ceci nous conduit à une programmation à la fois élégante, sûre et efficace : nous n’avons aucun besoin d’utiliser une référence, il n’y a pas de risque de débordement du tableau et les performances sont remarquables puisque l’on fait le minimum de tests.

Et si nous voulons connaître en plus le rang de l’élément recherché dans le tableau, c’est très facile car nous pouvons également définir des exceptions qui transmettent des paramètres. Nous avons déjà rencontré de telles exceptions prédéfinies comme Failure ou Invalid_argument qui transmettent une chaîne de caractères. Pour cela nous définirons, à la manière d’un constructeur non constant, une exception avec paramètre de type mon_type par la construction

exception nom_exception of mon_type

Lorsque l’élément est trouvé à l’index i, nous déclenchons l’exception Trouve en lui transmettant la valeur de i que nous récupérons ensuite par filtrage. Nous avons choisi de renvoyer - 1 si l’élément ne figure pas dans le tableau. Ceci nous conduit à :


#exception Trouve of int;;  
Exception Trouve defined.  
#let cherche t x=  
     try  
        for i=0 to (vect_length t)-1 do  
           if t.(i)=x then raise (Trouve i)  
        done;  
        -1  
     with Trouve x -> x;;  
cherche : ’a vect -> ’a -> int = <fun>  
#cherche [| 1;7;4;5 |] 4;;  
- : int = 2  
#cherche [| 1;7;4;5 |] 3;;  
- : int = -1


Programme 2.99: recherche dans un tableau