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.
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
|
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.
|
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 +. , -. , *. , /.
|
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.
|
Votre calculatrice peut faire appel à des fonctions mathématiques 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.
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;;.
|
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.
|
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 :
|
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
il peut être intéressant de calculer d’abord une bonne fois pour toutes log(sin(1.2)). On écrira donc en Caml
|
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.
|
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 :
|
et que localement ou pourra écrire :
|
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
|
Supposons que nous voulions construire la représentation graphique de la fonction
xsin(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 :
|
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.
|
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
on peut écrire en Caml :
|
L’attribution au symbole f de la valeur xlog(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 :
|
La définition de la fonction f est locale alors que la définition de la fonction g est globale.
La fonction f : xx2 + 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 :
|
Dans la définition d’une fonction xx2 + 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
|
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 :
|
En mathématiques, plutôt que de dire soit f la fonction xx2 + 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 :
|
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 :
|
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 :
|
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
|
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
|
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
Nous allons définir une fonction Caml trapeze qui effectue ce calcul.
|
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 : x2f(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 :
|
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.
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
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 :
|
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 (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).
|
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.
|
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) :
|
La fonction non curryfiée correspondante est la fonction add_nc définie par
|
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
|
Par contre, sous sa forme curryfiée, add 3 désigne la fonction qui à tout entier x associe 3 + x.
|
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 :
|
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.
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 :
|
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 :
|
(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.
|
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.
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.
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) :
|
On constate effectivement que Caml a effectué l’ordre d’écriture à l’écran puis retourné le résultat (). Comparez avec :
|
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.
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 :
|
puisque le résultat de la première évaluation a été négligée. Par contre, il peut être intéressant d’écrire :
|
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
|
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 :
|
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.
|
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 :
|
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).
|
Par contre, rien n’empêche de manipuler une référence comme une valeur Caml ordinaire et d’écrire :
|
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.
|
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 :
|
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
|
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 :
|
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 :
|
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.
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.
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 :
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
|
Bien entendu, des structures conditionnelles peuvent être imbriquées et si l’on veut définir une fonction sur les entiers par
on écrira
|
(notez les indentations qui facilitent la lecture et permettent de repérer facilement les différents cas).
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 :
|
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 :
|
Commençons par un cas simple avec la fonction f définie sur les entiers par
Nous la définirons en Caml par
|
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
|
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) :
|
Essayons un cas plus complexe avec la fonction de deux entiers définie par
On peut la définir en Caml sous forme non curryfiée par :
|
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+n où m désigne l’entier de gauche et n l’entier de droite.
|
Sous forme curryfiée, nous pouvons définir cette même fonction par
|
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 :
|
avec une variable z qui est pratiquement inutilisée, il est plus commode de faire disparaître la variable z et d’écrire :
|
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).
|
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)
|
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.
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
|
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 :
|
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.
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.
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.
|
Les limites sur les réels en virgule flottante sont plus larges, et dépendent de la machine :
|
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) :
|
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 :
|
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 :
|
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.
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.
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 :=.
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 :
|
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 :
|
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 :
|
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.
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
|
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
|
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.
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 où 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
|
et à partir de cette déclaration, on dispose de nouvelles valeurs
Maintenant nous pouvons poser :
|
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 :
|
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
|
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
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 | adresse | numéro de compte | montant |
Mitterrand | François | Palais de l’Elysée | 12547 | 12504,00 |
Balladur | Edouard | Hotel Matignon | 54218 | 11152,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
|
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
|
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
|
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.
|
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
où 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 :
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.
Les règles qui gouvernent la syntaxe des motifs sont les suivantes
{etiquette1 =motif1;...;etiquetteN = motifN}
est un motif.
Les règles qui gouvernent la reconnaissance des motifs sont les suivantes
motif1,...,motifN
reconnaît les N-uplets expr1,...,exprN tels que expr1 est reconnue par motif1,…, exprN est reconnue par motifN ; dans ce cas, il effectue les liaisons correspondant à ces N reconnaissances
[motif1;...;motifN]
reconnaît les listes de longueur N [expr1;...;exprN] tels que expr1 est reconnue par motif1,…, exprN est reconnue par motifN ; dans ce cas, il effectue les liaisons correspondant à ces N reconnaissances ; même chose avec des vecteurs
[|motif1;...;motifN|]
{etiquette1 =motif1;...;etiquetteN = motifN}
reconnaît les enregistrements qui définissent au moins les champs etiquette1 à etiquetteN et tels que la valeur associée à etiquette1 est reconnue par motif1, …, la valeur associée à etiquetteN est reconnue par motifN (les autres champs de l’enregistrement sont ignorés dans le processus de reconnaissance) ; dans ce cas, il effectue les liaisons correspondant à ces N reconnaissances
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.
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 :
|
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) :
|
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)
|
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) :
|
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) :
|
Caml dispose de deux autres exceptions utilisées par la bibliothèque standard qui sont
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
|
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 :
|
ou bien :
|
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 :
|
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
|
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 :
|
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 à :
|