Précédent Remonter Suivant
Annexe B Objective Caml


Le langage ML[7] a été conçu par Milner à Edimbourg en 1978 comme un langage typé de manipulation symbolique, servant de métalangage au système de démonstration automatique LCF. Caml est un de ses dialectes conçu et développé à l'INRIA à partir de 1984. Les langages de la famille ML ont d'autres descendants, comme comme Haskell, développé à Glasgow et à Yale, Miranda à Kent, et surtout SML/NJ [9], à Bell laboratories et à CMU. Comme Java, ML est fortement typé, il autorise les définitions algébriques des structures de données et la gestion automatique de la mémoire. Les langages de la famille ML sont devenus populaires dans la communauté du calcul symbolique et dans l'enseignement de l'informatique.

Caml est un langage de programmation fonctionnelle, c'est-à-dire un langage qui encourage un style de programmation fondé sur la notion de calcul plutôt que sur la notion de modification de l'état de la mémoire de la machine. Ce style, souvent plus proche des définitions mathématiques, repose sur l'utilisation intensive des fonctions, et n'est possible qu'à cause de l'effort porté sur la compilation des fonctions et la gestion de la mémoire. A ce titre, Caml est assez différent de Pascal et de C, quoiqu'il propose aussi des aspects impératifs qui autorisent un style assez proche du style impératif traditionnel. Il partage avec Java son typage fort et la gestion automaituqe de la mémoire, mais il a des types polymorphes paramétrés et des opérations de filtrage sur les structures de données dynamiques. Ici, comme en Java, nous ne ferons pas de programmation fonctionnelle, et nous nous contenterons d'un usage assez impératif.

On trouve une introduction didactique au langage SML/NJ dans les livres de Paulson[6] et d'Ulmann[8]. Pour une introduction à Caml, on consultera les livres de Weis-Leroy [1], Cousineau-Mauny [3], Hardin-Donzeau-Gouge [4], Monasse [5] ou Chailloux-Manoury-Pagano [10]. Le ``Manuel de référence du langage Caml'' [2] décrit le langage en détail. Cette annexe a été écrite par Pierre Weis.

B.1 Un exemple simple

Exercice imposé, écrivons l'exemple des carrés magiques en Objective Caml:

open Printf;;

let magique a =
 let n = Array.length a in
 let i = ref (n - 1) in
 let j = ref (n / 2) in
 for k = 1 to n * n do
  a.(!i).(!j) <- k;
  if k mod n = 0 then decr i else
   begin
    i := (!i + 1) mod n;
    j := (!j + 1) mod n;
   end
 done;;

let erreur s = printf "Erreur fatale: %s\n" s; exit 1;;

let lire () =
 printf "Taille du carré magique, svp ? ";
 let n = int_of_string (read_line ()) in
 if n <= 0 || n mod 2 = 0 then erreur "Taille impossible" else n;;

let imprimer a =
 for i = 0 to Array.length a - 1 do
  for j = 0 to Array.length a - 1 do
   printf "%4d " a.(i).(j)
  done;
  printf "\n"
 done;;

let main () =
 let n = lire () in
 let a = Array.make_matrix n n 0 in
 magique a;
 imprimer a;
 exit 0;;

main ();;

Phrases

On constate qu'un programme Caml est une suite de phrases qui se terminent toutes par ;;. Ces phrases sont des définitions de valeurs, de procédures ou de fonctions, ou encore des expressions qui sont évaluées dans l'ordre de présentation. Ainsi, la dernière phrase est l'expression main();; qui déclenche l'exécution du programme. On remarque aussi que les définitions des objets précédent toujours leur première utilisation.

Une définition est introduite par le mot clé let suivi du nom de l'entité définie. Par exemple, let n = Array.lengtha définit la variable n comme la longueur du vecteur a et let magique a =... définit la fonction magique avec a pour argument. À l'occasion, on remarque qu'en Caml on évite les parenthèses inutiles (mais le langage admet les parenthèses superflues); ainsi, l'application des fonctions est notée par simple juxtaposition, et l'on écrit Array.lengtha plutôt que Array.length(a).

La valeur des variables en Caml est fixée une fois pour toutes lors de leur définition et cette liaison n'est pas modifiable (il est impossible de changer la valeur liée à un nom défini par let). Comme en mathématiques, les variables sont des noms liés à des constantes qu'on calcule lors de la définition de ce nom. C'est aussi analogue aux constantes de Pascal, si ce n'est que l'expression liée à une variable Caml est quelconque et qu'il n'y a pas de limite à sa complexité.
En Caml, la valeur d'une variable est fixée lors de sa définition.
Références

Les variables de Caml ne sont donc pas des variables au sens traditionnel des langages de programmation, puisqu'il est impossible de modifier leur valeur. Il est pourtant souvent nécessaire d'utiliser dans les programmes des variables modifiables au sens de Pascal ou de C. En Caml, on utilise pour cela une référence modifiable vers une valeur, c'est-à-dire une case mémoire dont on peut lire et écrire le contenu. Pour créer une référence, on applique le constructeur ref au contenu initial de la case mémoire. C'est le cas pour la variable i, définie par la ligne let i = ref (n -1), dont la valeur est une référence qui contient n -1 à la création. Pour lire le contenu d'une référence, on utilise l'opérateur !, qu'on lit ``contenu de'' (ou ``deref'' car on l'appelle aussi opérateur de déréférencement). Pour écrire le contenu d'une référence on utilise l'opérateur d'affectation :=. Par exemple, i := !i +1 incrémente le contenu de la référence de la variable i, ce qui a finalement le même effet que l'affectation i := i +1 de Pascal ou l'affectation i = i +1 de C. Noter que les références ne contredisent pas le dogme ``une variable est toujours liée à la même valeur'': la variable i est liée à une unique référence et il est impossible de la changer. Plus précisément, la valeur de i est l'adresse de la case mémoire modifiable qui contient la valeur, et cette adresse est une constante. On ne peut que modifier le contenu de l'adresse.

Le connaisseur de Pascal ou de C est souvent troublé par cette distinction explicite entre une référence et son contenu qui oblige à appliquer systématiquement l'opérateur ! pour obtenir le contenu d'une référence, alors que ce déréférencement est implicite en Pascal et en C. En Caml, quand i a été défini comme une référence, la valeur de i est la référence elle-même et jamais son contenu: pour obtenir le contenu, il faut appliquer une opération de déréférencement explicite et l'on écrit !i. Sémantiquement, !i est à rapprocher de *i en C ou i^ en Pascal.

L'opérateur d'affectation := doit être rapproché aussi des opérateurs ordinaires dont il a le statut, e1 :=e2 signifie que le résultat de l'évaluation de e1 est une référence dont le contenu va devenir la valeur de e2 (de même que e1 +e2 renvoie la somme des valeurs de e1 et e2). Évidemment, dans la grande majorité des cas, la partie gauche de l'affectation est réduite à un identificateur, et l'on affecte simplement la référence qui lui est liée. Ainsi, en écrivant i := !i -1, on décrémente le contenu de la référence i en y mettant le prédécesseur de son contenu actuel. Cette opération de décrémentation est d'ailleurs prédéfinie sous la forme d'une procédure qui prend une référence en argument et la décrémente:

let decr x =
  x := !x - 1;;
Dans cet exemple, la distinction référence-contenu est évidente: l'argument de decr est la référence elle-même, pas son contenu. Cette distinction référence-contenu s'éclaire encore si l'on considère les références comme des vecteurs à une seule case: c'est alors un prolongement naturel de la nécessaire distinction entre un vecteur et le contenu de ses cases.

L'opérateur d'affectation en Caml pose une petite difficulté supplémentaire aux habitués des langages impératifs: comme nous venons de le voir, l'écriture e1 :=e2 impose que le résultat de l'évaluation de e1 soit une référence. Pour des raisons de typage, il n'est donc pas question d'utiliser le symbole := pour affecter des cases de vecteurs, ni des caractères de chaînes, ni même des champs d'enregistrement. Chacune de ces opérations possède son propre opérateur (où intervient le symbole <-).
En Caml, l'opérateur := est réservé aux références.
Vecteurs et tableaux

Un vecteur est une succession de cases mémoires. Les indices des éléments commencent en 0, si le vecteur est de longueur n les indices vont de 0 à n - 1. Pour accéder aux éléments d'un vecteur v, on utilise la notation v.(indice). Pour modifier le contenu des cases de vecteur, on utilise le symbole <- qu'on lit reçoit. Par exemple v.(i) <-k met la valeur k dans la case i du vecteur v.

Pour créer un tableau, on appelle la primitive Array.make_matrix. La ligne
let c = Array.make_matrix n n 0 in

définit donc une matrice n × n, dont les éléments sont des entiers, tous initialisés à 0. Chaque élément de la matrice c ainsi définie est accédé par la notation c.(i).(j), et modifié par la notation c.(i).(j)<- nouvelle valeur. Comme la notation le suggère, c.(i).(j) signifie en fait (c.(i)).(j), c'est-à-dire accès au jième élément du vecteur c.(i). Cela veut dire que la matrice est en réalité un vecteur dont les éléments sont eux-mêmes des vecteurs: les lignes de la matrice. (Mais rien n'empêche évidemment de définir une matrice comme le vecteur de ses colonnes.) Retenons qu'en Caml comme en C, les tableaux sont des vecteurs de vecteurs. D'autre part, la ligne let c = make_matrix n n 0 in  définit un tableau dont la taille n'est pas une constante connue à la compilation, mais une valeur déterminée à l'exécution (ici n est lue sur l'entrée standard); cependant, une fois le tableau créé, sa taille est fixée une fois pour toutes et n'est plus modifiable.
En Caml, la taille des vecteurs est fixée à la création.
Fonctions et procédures

Caml est un langage fonctionnel: comme nous l'avons déjà vu, les fonctions forment les briques de base des programmes. En outre, les fonctions sont des valeurs primitives du langage qu'on manipule au même titre que les autres valeurs. Il est très facile de définir des fonctions qui manipulent des fonctions ou même de fabriquer des structures de données qui comportent des fonctions. Une fonction peut librement être prise en argument ou rendue en résultat, et il n'y a pas de restriction à son usage dans les structures de données.
En Caml, les fonctions sont des valeurs comme les autres.
Comme en mathématiques, une fonction a des arguments et rend un résultat qu'elle calcule avec une expression où intervient la valeur de ses arguments. Comme pour les autres valeurs, la définition d'une fonction est introduite par un mot clé let suivi du nom de la fonction et de la liste de ses arguments, ce qui nous donne typiquement let f x =... pour une fonction à un argument et let f x1 x2 ... xn =... pour une fonction à n arguments.

Voici un exemple de fonction des entiers dans les entiers:
let prochain x = if x mod 2 = 1 then 3 * x + 1 else x / 2;;

La fonction prochain renvoie 3x+1 si x est impair, et ë x/2 û si x est pair. (On peut s'amuser à itérer cette fonction et à observer ses résultats successifs; on ne sait toujours pas démontrer qu'on obtient finalement 1, quelque soit l'entier de départ. Par exemple: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1).

Définissons maintenant le prédicat even, qui teste la parité des entiers (c'est une fonction des entiers dans les booléens):
let even x = x mod 2 = 0;;

On remarque que les définitions de prochain et de even ne font pas intervenir de types: la signature des fonctions est implicite. Pourtant Caml dispose, comme Pascal, d'un typage fort, c'est-à-dire strict et vérifié complètement à la compilation. En effet, les types des arguments et du résultat des fonctions sont automatiquement calculés par le compilateur, sans intervention du programmeur, ni annotations de type dans les programmes. L'habitué de Pascal ou C pourra s'il le désire insérer des types dans ses programmes, à l'aide de contraintes de type. Une contrainte de type consiste en un morceau de programme mis entre parenthèses et décoré avec son type. Ainsi (x : int) impose que x soit un entier. Avec une contrainte sur son argument et son résultat la fonction even s'écrirait:
let even (x : int) = (x mod 2 = 0 : bool);;
Comme on le constate sur le programme du carré magique, les contraintes de type ne sont pas nécessaires, il n'est donc pas d'usage d'en mettre dans les programmes.
En Caml, le typage est à la charge du compilateur.
Lorsque l'argument ou le résultat d'une fonction sont sans intérêt, on le note alors (), l'unique valeur du type unit. Une telle fonction est souvent qualifiée de procédure au lieu de fonction, mais ce n'est qu'une distinction commode qui n'est pas faite par le langage. Par exemple, main est une procédure, et l'on constate qu'elle est définie exactement de la même manière que notre fonction prochain ou le prédicat even.

La fonction magique est elle aussi une procédure, elle construit un carré magique d'ordre n impair de la même façon qu'en Pascal ou C.

La fonction lire lit la taille du carré magique et fait quelques vérifications sur sa valeur. En cas de taille incorrecte, elle appelle la fonction erreur qui affiche un message et arrête le programme en erreur. Pour lire cette taille, elle appelle la procédure de lecture d'une ligne read_line, après avoir imprimé un message sur le terminal. La procédure d'impression formatée printf a pour premier paramètre une chaîne de caractères, délimitée par des guillemets. C'est le format qui indique comment imprimer les arguments qui suivent: on spécifie le type d'impression désiré, à l'aide de caractères symboliques, précédés de l'indicateur %. Par exemple %s signifie qu'on doit imprimer une chaîne de caractères, et %d un entier. L'ordre des indications d'impression dans le format doit être corrélé avec l'ordre des arguments à imprimer. Dans la procédure imprimer qui imprime le tableau a, l'indication %4d indique l'impression d'un entier sur 4 caractères, cadré à droite.

Enfin, la procédure main est la procédure principale du programme qui fait appel successivement aux différentes procédures, dans un ordre simple et compréhensible. La méthode qui consiste à définir de petites fonctions, qu'on appelle ensuite dans la fonction principale est un principe de programmation structurée. Elle améliore la lisibilité et facilite les modifications, mais n'est pas une obligation du langage. Nous aurions pu définir toutes les fonctions locales à la fonction main, mais en général ce style est mauvais, car on mélange le coeur algorithmique du programme (la procédure magique) avec des détails annexes comme l'impression et la lecture. Remarquons qu'il faut appeler explicitement le programme principal, ce que fait la ligne main ();; À défaut, la procédure main serait définie mais pas appelée, et le programme ne ferait rien.

B.2 Quelques éléments de Caml

Appel au compilateur

Sur la plupart des machines, le système Objective Caml propose un compilateur indépendant ocamlc qui produit de façon traditionnelle un programme exécutable à partir d'un programme source, contenu dans un fichier ayant l'extension .ml. On précise le nom de l'exécutable produit en donnant l'option -onom_de_programme au compilateur; à défaut, il produit le programme a.out. Voici un exemple de compilation obtenue sous le système Unix.
poly% cat fact.ml
let rec fact x = if x <= 1 then 1 else x * fact (x - 1);;

print_int (fact 10); print_newline ();;
poly% ocamlc fact.ml
poly% a.out
3628800

En dehors du compilateur proprement dit, les systèmes Caml offrent une interface interactive de dialogue avec le compilateur. Dans cette interface, on entre successivement des phrases qui sont compilées, puis exécutées au vol. Voici une session obtenue sur une machine Unix en lançant le système interactif par la commande ocaml.
poly% ocaml
        Objective Caml version 3.04

#let rec fact x = if x <= 1 then 1 else x * fact (x - 1);;
val fact : int -> int = <fun>
#fact 10;;
- : int = 3628800
##quit;;
poly%
Dans cette utilisation, Caml indique le résultat des calculs et le type des objets définis. Il trouve automatiquement ces types par un algorithme d'inférence de type. Au lieu de taper directement les programmes, on peut charger les fichiers qui les contiennent par la directive #use. Les phrases du fichier sont alors compilées et exécutées à la volée, exactement comme si on les avait tapées dans le système interactif. Ainsi, le chargement du fichier fact.ml exécute les phrases dans l'ordre la fin du programme. On peut alors reprendre l'interaction comme avant le chargement:
##use "fact.ml";;
fact : int -> int = <fun>
3628800
- : unit = ()
#

Le système interactif est donc plutôt réservé à l'apprentissage du langage. Lorsqu'on maîtrise Caml et qu'on développe de gros programmes, on privilégie le compilateur indépendant qui s'intègre plus facilement aux outils de gestion automatique des logiciels. On réserve alors le système interactif au test rapide des programmes, et dans une moindre mesure à la mise au point.

B.2.1 Fonctions

On utilise la notation A ® B pour dénoter les fonctions de l'ensemble A dans l'ensemble B et par exemple int ->int est le type de la fonction fact ci-dessus. La valeur d'une fonction est une valeur fonctionnelle, notée conventionnellement <fun>. Remarquons à nouveau que toute définition lie un identificateur à une valeur; ainsi fact possède une valeur et il s'évalue normalement:
#fact;;
- : int -> int = <fun>

À l'occasion de la définition de fact, on observe aussi que les fonctions récursives doivent être introduites par le mot-clé letrec, pour signaler au système qu'on fait référence à leur nom avant leur définition effective.
Les fonctions récursives doivent être introduites par le mot-clé let rec.
Pour terminer sur les fonctions, citons l'existence des fonctions anonymes, c'est-à-dire des valeurs fonctionnelles qui n'ont pas de nom. On les introduit avec le nouveau mot clé function et la construction function x ->... Par exemple:
#(function x -> x + 1);;
- : int -> int = <fun>
#(function x -> x + 1) 2;;
- : int = 3
Lorsqu'on donne un nom à une fonction anonyme, on définit alors très logiquement une fonction ``normale'':
#let successeur = (function x -> x + 1);;
val successeur : int -> int = <fun>
#successeur 2;;
- : int = 3
On utilise la plupart du temps les fonctions anonymes en argument des fonctionnelles que nous décrivons maintenant.

Fonctionnelles

Il n'y a pas de contraintes sur les arguments et résultats des procédures et des fonctions: les arguments et résultats fonctionnels sont donc autorisés. Une bonne illustration consiste à écrire une procédure de recherche d'une racine d'une fonction sur un intervalle donné. La procédure zéro prend une fonction f en argument (et pour cette raison on dit que zéro est une fonctionnelle). Définissons d'abord une fonction auxiliaire qui calcule la valeur absolue d'un flottant.
let abs x = if x >= 0.0 then x else -. x;;
Nous notons à l'occasion que les nombres flottants comportent obligatoirement un point, même 0. Les opérations sur les nombres flottants sont également distinctes de celles des nombres entiers, puisqu'elles sont systématiquement suffixées par un point (sauf les comparaisons). Notre fonctionnelle s'écrit alors:
let trouve_zéro f a b epsilon max_iterations =
 let rec trouve x y n =
  if abs (y -. x) < epsilon || n >= max_iterations then x
  else
   let m = (x +. y) /. 2.0 in
   if (f m > 0.0) = (f x > 0.0)
   then trouve m y (n + 1)
   else trouve x m (n + 1) in
 trouve a b 1;;
let zéro f a b = trouve_zéro f a b 1.0E-7 100;;
Remarquons la définition locale de la fonction récursive trouve, qu'on applique ensuite avec les arguments a, b et 1. Si on a des difficultés à comprendre ce style fonctionnel, voici la même fonction en version impérative (avec une boucle while que nous verrons plus loin):
let zéro f a b =
 let epsilon = 1.0E-7
 and nmax  = 100 in
 let n = ref 1
 and m = ref ((a +. b) /. 2.0) in
 let x = ref a
 and y = ref b in
 while abs (!y -. !x) > epsilon && !n < nmax do
  m := (!x +. !y) /. 2.0;
  if (f !m > 0.0) = (f !x > 0.0)
   then x := !m
   else y := !m;
  n := !n + 1
 done;
 !x;;
Le type inféré par Caml pour zéro est (float -> float) -> float -> float -> float qui indique bien que le premier argument est une fonction des flottants dans les flottants. Utilisons la fonctionnelle zéro pour trouver un zéro de la fonction logarithme entre 1/2 et 3/2:
#open Printf;;
#let log10 x = log x /. log 10.0;;
val log10 : float -> float = <fun>
#printf "le zéro de log10 est %f\n" (zéro log10 0.5 1.5);;
le zéro de log10 est 1.000000
- : unit = ()
Les arguments fonctionnels sont naturels et rendent souvent l'écriture plus élégante. Il faut noter que l'efficacité du programme n'en souffre pas forcément, surtout dans les langages fonctionnels qui optimisent la compilation des fonctions et de leurs appels.

B.2.2 Symboles, séparateurs, identificateurs

Les identificateurs sont des séquences de lettres, de chiffres, d'apostrophes et de soulignés commençant par une lettre. Les identificateurs sont séparés par des espaces, des caractères de tabulation, des retours à la ligne ou par des caractères spéciaux comme +, -, *. Certains identificateurs sont réservés pour des mots clés de la syntaxe, comme and, type, begin, end, while, ...

Nous abandonnons la convention adoptée en Pascal et C dans ce cours qui consiste à commencer par une majuscule les noms de constantes et par une minuscule les noms de variables. En Caml, toutes les variables ont une valeur constante (au sens de Pascal et de C) et devraient donc commencer par une majuscule. Nous préférons utiliser les minuscules comme première lettre des variables. (Seuls les noms de constructeurs des types somme et les exceptions commenceront par une majuscule.)

B.2.3 Types de base

L'unique valeur rien a le type prédéfini unit; elle est notée () et est lue ``voïde''. La valeur rien sert à compléter une conditionnelle à une seule branche (par else ()), à déclencher les procédures (print_newline ()), et comme instruction vide dans le corps d'une boucle.

Les booléens ont le type prédéfini bool, qui contient deux constantes true et false.

Les entiers ont le type prédéfini int. Les constantes entières sont une suite de chiffres décimaux, éventuellement précédée d'un signe -, comme 234, -128, ...Les valeurs extrémales dépendent de l'implémentation.

Les flottants ont le type prédéfini float. Les constantes flottantes sont une suite de chiffres décimaux comprenant un point, éventuellement suivie d'une indication d'exposant, comme 3.1416 ou 3141.6E-3 pour désigner 3141,6 × 10-3.

Les caractères ont le type prédéfini char. Une constante caractère est une lettre entourée du symbole ', comme 'a', 'b', ..., '+', ':'. Certains caractères sont codés spécialement comme '\n' pour le changement de ligne, '\r' pour le retour charriot, '\t' pour la tabulation, '\'' pour le caractère apostrophe, et '\\' pour la barre oblique. Enfin, on dénote n'importe quel caractère en le désignant par son numéro décimal dans le code ASCII (American Standard Codes for Information Interchange) (ISO-latin), sur trois chiffres et précédé d'une barre oblique. Ainsi '\032' désigne le caractère espace et '\233' est équivalent à 'é'. La fonction int_of_char donne la valeur entre 0 et 255 dans le code ASCII du caractère. Inversement, la fonction char_of_int donne le caractère par son code ASCII. En Objective Caml, on peut aussi utiliser les fonctions Char.code et Char.chr.

Les chaînes de caractères ont le type prédéfini string. Ce sont des suites de caractères rangés consécutivement en mémoire. Une constante chaîne est une suite de caractères entourée de guillemets. Dans une chaîne, le caractère guillemet se note \" en ajoutant une barre oblique devant le guillemet, et les caractères spéciaux obéissent aux mêmes conventions que pour les constantes caractères. Les éléments d'une chaîne de caractères sont numérotés à partir de 0. On accède à l'élément i de la chaîne s à l'aide de la notation s.[i]. On remplace l'élément i de la chaîne s par la valeur c, à l'aide de la notation s.[i]<- c. En évaluant String.make l c, on obtient une chaîne de caractères de longueur l, initialisée avec des caractères c. L'opérateur infixe ^ sert à concaténer deux chaînes, la fonction String.sub permet d'extraire une sous-chaîne, et la procédure String.blit de transférer des caractères d'une chaîne à une autre. Pour plus d'information, voir le module string de la librairie.

Les vecteurs ont le type prédéfini array. Ce sont des suites d'éléments de même type, rangés consécutivement en mémoire. Une constante vecteur est une suite d'éléments séparés par des ; et entourée de ``parenthèses'' [| et |]. Par exemple:
#let v = [| 1; 2; 3 |];;
val v : int array = [|1; 2; 3|]

Remarquons la notation suffixe pour le constructeur de type des vecteurs. Le type d'un vecteur d'entiers s'écrit intvect, et le type d'une matrice d'entiers int vectvect. Les éléments d'un vecteur sont numérotés à partir de 0. On accède à l'élément i du vecteur v à l'aide de la notation v.(i). On remplace l'élément i du vecteur v par la valeur c, à l'aide de la notation v.(i) <- c. En évaluant Array.make l c, on obtient un vecteur de longueur l, initialisé avec l'élément c. On dispose aussi des fonctions Array.sub pour extraire des sous-chaînes et Array.blit pour transférer des éléments d'un vecteur à un autre. Pour plus d'information, voir le module vect de la librairie.

Les références ont le type prédéfini ref. Comme les vecteurs le constructeur de type des références ref utilise la notation suffixe. Une référence est construite par l'application du constructeur (de valeur) ref à sa valeur initiale. En évaluant ref v, on obtient une référence, initialisée avec la valeur v. On accède au contenu d'une référence r à l'aide de la notation !r. On remplace le contenu de la référence r par la valeur c, à l'aide de la notation r := c.

Les paires d'éléments de type t1 et t2 ont le type t1 *t2. On écrit la paire des valeurs v1 et v2 de la manière mathématique classique: (v1,v2). La notation s'étend aux n-uplets. Il n'y a pas de limitation à l'usage des n-uplets, qui peuvent être librement pris en argument et rendus en résultat des fonctions. Par exemple, la symétrie par rapport à l'origine du repère s'écrit:
#let symétrie (x, y) = (-x, -y);;
val symétrie : int * int -> int * int = <fun>
Attention, les n-uplets ne sont pas associatifs et (1, 2, 3) ¹ ((1, 2), 3).

B.2.4 Expressions

Les expressions arithmétiques font intervenir les opérateurs classiques sur les entiers + (addition), - (soustraction), * (multiplication), / (division entière), mod (modulo). On utilise les parenthèses comme en mathématiques. Ainsi, si x et y sont deux entiers, on écrit 3 * (x + 2 * y) + 2 * x *x pour 3 (x + 2y) + 2 x2.

Les mêmes opérateurs, suffixés par un point, servent pour les expressions flottantes. Donc, si z est un flottant, on écrit 3.0 *. (z +. 1) /.2.0 pour 3 (z+1) / 2. Les fonctions int_of_float et float_of_int autorisent les conversions des flottants dans les entiers: la première donne la partie entière, la seconde convertit un entier en flottant. Contrairement à Pascal ou à C, les conversions ne sont jamais automatiques: par exemple 3.5 +2 est toujours mal typé.
En Caml, les conversions sont explicites.
Une expression conditionnelle ou alternative s'écrit:
if e then e1 else e2
où la condition e est une expression booléenne du type bool, et e1, e2 sont deux expressions de même type qui est celui du résultat.

Les expressions booléennes sont construites à partir des opérateurs ||, &&, not, des booléens et des opérateurs de comparaison. Ainsi, si b et c sont deux identificateurs de type bool, l'expression
(b && not c) || (not b && c)

représente le ou-exclusif de b et c. Les deux opérateurs || et && se comportent exactement comme une construction ``if then else''. Par définition, a &&b signifie if a then b else false et a ||b signifie if a then true else b. Parfois ces opérateurs rendent un résultat sans évaluer certains de leurs arguments. Si a s'évalue en faux, alors a &&b rend false sans que l'expression b soit évaluée. Les opérateurs de comparaison =, <>, <=, <, >, >= rendent aussi des valeurs booléennes. On peut comparer des entiers, des flottants, des booléens, des caractères (dans ce dernier cas, l'ordre est celui du code ASCII) et même deux valeurs quelconques, pourvu qu'elles soient du même type.

La précédence des opérateurs est naturelle. Ainsi * est plus prioritaire que +, lui-même plus prioritaire que =. Si un doute existe, il ne faut pas hésiter à mettre des parenthèses. De manière générale, seules les parenthèses vraiment significatives sont nécessaires. Par exemple, dans
if (x > 1) && (y = 3) then ...

la signification ne change pas si l'on ôte toutes les parenthèses. De même, dans l'expression du ou-exclusif
(b && not c) || (not b && c)
les parenthèses sont superflues. En effet les précédences respectives de &&, || et not sont analogues à celles de *, + et -. On écrit donc plus simplement b && not c || not b && c. (Encore plus simple: b <>c!) Évidemment, certaines parenthèses sont impératives pour grouper les expressions. L'exemple des arguments de fonctions est plus particulièrement fréquent: comme en mathématiques f (x +1) est essentiellement différent de f (x) +1. Et comme on omet souvent les parenthèses autour des arguments très simples (variables ou constantes), il faut aussi noter que f (x) +1 est synonyme de f x +1. De toutes façons, les parenthèses sont indispensables pour les arguments de fonctions compliqués. Pour la même raison les parnthèses sont nécessaires autour des arguments négatifs f(-1) ¹ f-1, car f-1 est synonyme de f -1 qui est une soustraction.

f (x +1) ¹ f x +1.


L'ordre d'évaluation des opérateurs dans les expressions respecte les conventions mathématiques lorsqu'elles existent (priorité de l'addition par rapport à la multiplication par exemple). En ce qui concerne l'application des fonctions, on évalue les arguments avant de rentrer dans le corps de la fonction (appel par valeur). Comme en C, il n'y a pas d'appel par référence mais on peut pratiquement le simuler en utilisant des références (c'est le cas pour la fonction decr décrite page ??). L'ordre d'évaluation des arguments des opérateurs et des fonctions n'est pas spécifié par le langage. C'est pourquoi il faut impérativement éviter de faire des effets dans les arguments de fonctions. En règle générale, il ne faut pas mélanger les effets (impressions, lectures ou modification de la mémoire, déclenchement d'exceptions) avec l'évaluation au sens mathématique.
En Caml, l'ordre d'évaluation des arguments n'est pas spécifié.
L'opérateur d'égalité s'écrit avec le symbole usuel =. C'est un opérateur polymorphe, c'est-à-dire qu'il s'applique sans distinction à tous les types de données. En outre, c'est une égalité structurelle, c'est-à-dire qu'elle parcourt complètement ses arguments pour détecter une différence ou prouver leur égalité. L'habitué de C peut être surpris, si par mégarde il utilise le symbole == au lieu de =, car il existe aussi un opérateur == en Caml (et son contraire !=). Cet opérateur teste l'égalité physique des valeurs (identité des adresses mémoire en cas de valeurs allouées). Deux objets physiquement égaux sont bien sûr égaux. La réciproque n'est pas vraie:
#"ok" = "ok";;
- : bool = true
#"ok" == "ok";;
- : bool = false
L'égalité physique est indispensable pour comparer directement les références, plutôt que leur contenu (ce que fait l'égalité structurelle). On s'en sert par exemple dans les algorithmes sur les graphes.
#let x = ref 1;;
val x : int ref = ref 1
#let y = ref 1;;
val y : int ref = ref 1
#x = y;;
- : bool = true
#x == y;;
- : bool = false
#x == x;;
- : bool = true
#x := 2;;
- : unit = ()
#x = y;;
- : bool = false

B.2.5 Blocs et portée des variables

Dans le corps des fonctions, on définit souvent des valeurs locales pour calculer le résultat de la fonction. Ces définitions sont introduites par une construction let ident = expression in.... Il n'y a pas de restriction sur les valeurs locales, et les définitions de fonctions sont admises. Ces fonctions locales sont elles-mêmes susceptibles de comprendre de nouvelles définitions de fonctions si nécessaire et ce ad libitum.

Lorsqu'on cite un identificateur x dans un programme, il fait nécessairement référence au dernier identificateur de nom x lié par une définition let, ou introduit comme paramètre d'une fonction après le mot-clé function. En général, il est plus élégant de garder les variables aussi locales que possible et de minimiser le nombre de variables globales. Ce mode de liaison des identificateurs (qu'on appelle la portée statique) est surprenant dans le système interactif. En effet, on ne peut jamais modifier la définition d'un identificateur; en particulier, la correction d'une fonction incorrecte n'a aucun effet sur les utilisations antérieures de cette fonction dans les fonctions déjà définies.
let successeur x = x - 1;;
let plus_deux x = successeur (successeur x);;
#plus_deux 1;;
- : int = -1
Ici, on constate la bévue dans la définition de successeur, on corrige la fonction, mais cela n'a aucun effet sur la fonction plus_deux.
#let successeur x = x + 1;;
val successeur : int -> int = <fun>
#plus_deux 1;;
- : int = -1
La solution à ce problème est de recharger complètement les fichiers qui définissent le programme. En cas de doute, quitter le système interactif et recommencer la session.

B.2.6 Correction des programmes
Le suivi de l'exécution des fonctions est obtenu à l'aide du mode trace qui permet d'afficher les arguments d'une fonction à l'entrée dans la fonction et le résultat à la sortie. Dans l'exemple du paragraphe précédent, le mécanisme de trace nous renseigne utilement: en traçant la fonction successeur on constate qu'elle n'est jamais appelée pendant l'évaluation de plus_deux1 (puisque c'est l'ancienne version de successeur qui est appelée).
#trace successeur;;
successeur is now traced.
- : unit = ()
#successeur 1;;
successeur <-- 1
successeur --> 2
- : int = 2
#plus_deux 1;;
- : int = -1
Le mode trace est utile pour suivre le déroulement des calculs, mais moins intéressant pour pister l'évolution de la mémoire. En ce cas, on imprime des messages pendant le déroulement du programme.

B.2.7 Instructions

Caml n'a pas à proprement parler la notion d'instructions, puisqu'en dehors des définitions, toutes les constructions syntaxiques sont des expressions qui donnent lieu à une évaluation et produisent un résultat. Parmi ces expressions, la séquence joue un rôle particulier: elle permet d'évaluer successivement les expressions. Une séquence est formée de deux expressions séparées par un ;, par exemple e1 ; e2. La valeur d'une séquence est celle de son dernier élément, les résultats intermédiaires sont ignorés. Dans e1 ; e2, on évalue e1, on oublie le résultat obtenu, puis on évalue e2 qui donne le résultat final de la séquence. Comme en Pascal, on peut entourer une séquence des mots-clé begin et end.
begin e1e2; ...; en   end
Dans une séquence, on admet les alternatives sans partie else:
if e then e1

qui permet d'évaluer e1 seulement quand e est vraie, alors que l'alternative complète
if e then e1 else e2

évalue e2 quand e est faux. En réalité, la conditionnelle partielle est automatiquement complétée en une alternative complète avec else(). Cela explique pourquoi le système rapporte des erreurs concernant le type unit, en cas de conditionnelle partielle dont l'unique branche n'est pas de type unit:
#if true then 1;;
              ^
This expression has type int but is here used with type unit
#if true then printf "Hello world!\n";;
Hello world!
- : unit = ()
On lève les ambiguités dans les cascades de conditionnelles en utilisant begin et end. Ainsi
if e then if e' then e1 else e2

équivaut à
if e then begin if e ' then e1 else e2 end

Filtrage
Caml fournit d'autres méthodes pour aiguiller les calculs: match permet d'éviter une cascade d'expressions if et opère un aiguillage selon les différentes valeurs possibles d'une expression. Ce mécanisme s'appelle le filtrage; il est plus riche qu'une simple comparaison avec l'égalité, car il fait intervenir la forme de l'expression et opère des liaisons de variables. À la fin d'un filtrage, un cas _ se comporte comme un cas par défaut. Ainsi
match e with
v1 -> e1
v2 -> e2
  ...
vn -> en
| _ -> défaut

permet de calculer l'expression ei si e = vi, ou défaut si e ¹ vi pour tout i. Nous reviendrons sur ce mécanisme plus tard.

Boucles
Les autres constructions impératives servent à l'itération, ce sont les boucles for et while. Dans les deux cas, le corps de la boucle est parenthésé par les mot clés do et done. La boucle for permet d'itérer, sans risque de non terminaison, avec un indice de boucle, un identificateur dont la valeur augmente automatiquement de 1 ou de -1 à chaque itération. Ainsi

for i = e1 to e2 do e done

évalue l'expression e avec i valant successivement e1, e1 + 1, ... jusqu'à e2 compris. Si e1 est supérieur à e2, le corps de la boucle n'est jamais évalué. De même
for i = e1 downto e2 do e done

itère de e1 à e2 en décroissant. Dans les deux cas, l'indice de boucle est introduit par la boucle et disparaît à la fin de celle-ci. En outre, cet indice de boucle n'est pas lié à une référence mais à un entier: sa valeur ne peut être modifiée par une affectation dans le corps de la boucle. Les seuls pas d'itération possibles sont 1 et -1. Pour obtenir d'autres pas, il faut multiplier la valeur de la variable de contrôle ou employer une boucle while.
On ne peut pas affecter l'indice de boucle d'une boucle for.
La construction while,
while e1 do e done

évalue répétitivement l'expression e tant que la condition booléenne e1 est vraie. (Si e1 est toujours fausse, le corps de la boucle n'est jamais exécuté.) Lorsque le corps d'une boucle while est vide, on la remplace par la valeur rien, (), qui joue alors le rôle d'une instruction vide. Par exemple,
while not button_down () do () done;

attend que le bouton de la souris soit enfoncé.

B.2.8 Exceptions

Il existe un dispositif de gestion des cas exceptionnels. En appliquant la primitive raise à une valeur exceptionnelle, on déclenche une erreur. De façon symétrique, la construction syntaxique try calcul with filtrage permet de récupérer les erreurs qui se produiraient lors de l'évaluation de calcul. La valeur renvoyée s'il n'y a pas d'erreur doit être du même type que celle renvoyée en cas d'erreur dans la partie with de la construction. Ainsi, le traitement des situations exceptionnelles (dans la partie with) est disjoint du déroulement normal du calcul. En cas de besoin, le programmeur définit ses propres exceptions à l'aide de la construction exception nom-de-l'exception;; pour les exceptions sans argument; ou exception nom-de-l'exception of type-de-l'argument;; pour les exceptions avec argument. L'argument des exceptions permet de véhiculer une valeur, de l'endroit où se produit l'erreur à celui où elle est traitée (voir plus loin).

B.2.9 Entrées -- Sorties

On lit sur le terminal (ou la fenêtre texte) à l'aide de la fonction prédéfinie read_line qui renvoie la chaîne de caractères tapée.

Pour les impressions simples, on dispose de primitives pour les types de base: print_int, print_char, print_float et print_string; la procédure print_newline permet de passer à la ligne. Pour des impressions plus sophistiquées, on emploie la fonction d'impression formatée printf (de la bibliothèque printf).

La lecture et l'écriture sur fichiers a lieu par l'intermédiaire de canaux d'entrées-sorties. Un canal est ouvert par l'une des primitives open_in ou open_out. L'appel open_in nom_de_fichier crée un canal d'entrée sur le fichier nom_de_fichier, ouvert en lecture. L'appel open_out nom_de_fichier crée un canal de sortie sur le fichier nom_de_fichier, ouvert en écriture. La lecture s'opère principalement par les primitives input_char pour lire un caractère, ou input, input_line pour les chaînes de caractères. En sortie, on utilise output_char, output_string et output. Il ne faut pas oublier de fermer les canaux ouverts lorsqu'ils ne sont plus utilisés (à l'aide de close_in ou close_out). En particulier, pour les fichier ouverts en écriture, la fermeture du canal assure l'écriture effective sur le fichier (sinon les écritures sont réalisées en mémoire, dans des tampons).

Copie de fichiers

Le traitement des fichiers nous permet d'illustrer le mécanisme d'exception. Par exemple, l'ouverture d'un fichier inexistant se solde par le déclenchement d'une erreur par le système d'exploitation: l'exception Sys_error est lancée avec pour argument la chaîne de caractères "fichier: No such file ordirectory".
#open_in "essai";;
Uncaught exception: Sys_error "essai: No such file or directory".

On remarque qu'une exception qui n'est pas rattrapée interrompt complètement les calculs.

Supposons maintenant que le fichier de nom essai existe. Après avoir ouvert un canal sur ce fichier et l'avoir lu entièrement, toute tentative de lecture provoque aussi le déclenchement d'une exception, l'exception prédéfinie End_of_file:

#let ic = open_in "essai" in
  while true do input_line ic done;;
Uncaught exception: End_of_file.
À l'aide d'une construction try, on récupèrerait facilement l'erreur pour l'imprimer (et éventuellement continuer autrement le programme). Nous illustrons ce mécanisme en écrivant une procédure qui copie un fichier dans un autre. On utilise une boucle infinie qui copie ligne à ligne le canal d'entrée et ne s'arrête que lorsqu'on atteint la fin du fichier à copier, qu'on détecte par le déclenchement de l'exception prédéfinie End_of_file. Ici le déclenchement de l'exception n'est pas une erreur, c'est au contraire l'indication attendue de la fin du traitement.
open Printf;;

let copie_channels ic oc =
 try
  while true do
   let line = input_line ic in
   output_string oc line;
   output_char oc '\n'
  done
 with
 | End_of_file -> close_in ic; close_out oc;;

La procédure de copie elle-même se contente de créer les canaux sur les fichiers d'entrée et de sortie, puis d'appeler la procédure copie_channels. Comme les ouvertures des fichiers d'entrée et de sortie sont susceptibles d'échouer, la procédure utilise deux try imbriqués pour assurer la bonne gestion des erreurs. En particulier, le canal d'entrée n'est pas laissé ouvert quand il y a impossibilité d'ouvrir le canal de sortie. Dans le try intérieur qui protège l'ouverture du fichier de sortie et la copie, on remarque le traitement de deux exceptions. La deuxième, Sys.Break, est déclenchée quand on interrompt le programme. En ce cas un message est émis, les canaux sont fermés et l'on déclenche à nouveau l'interruption pour prévenir la fonction appelante que la copie ne s'est pas déroulé normalement.
let copie origine copie =
 try
  let ic = open_in origine in
   try
    let oc = open_out copie in
    copie_channels ic oc
   with
   | Sys_error s ->
      close_in ic;
      printf "Impossible d'ouvrir le ficher %s \n" copie;
      raise (Sys_error s)
   | Sys.Break ->
      close_in ic;
      close_out oc;
      printf "Interruption pendant la copie de %s dans %s\n" origine copie;
      raise (Sys.Break)
 with
 | Sys_error s ->
    printf "Le ficher %s n'existe pas\n" origine;
    raise (Sys_error s);;

B.2.10 Définitions de types

Types sommes: types énumérés

L'utilisateur peut définir ses propres types de données. Par exemple, les types énumérés couleur et sens définissent un ensemble de constantes qui désignent des objets symboliques.
type couleur = Bleu | Blanc | Rouge
and sens = Gauche | Haut | Droite | Bas;;

let c = Bleu
and s = Droite in
...
end;


couleur est l'énumération des trois valeurs Bleu, Blanc, Rouge. On aura remarqué que le symbole | signifie ``ou''. Le type bool est aussi un type énuméré prédéfini tel que:
type bool = false | true;;
Par exception à la règle et pour la commodité du programmeur, les constructeurs du type bool ne commencent pas par une majuscule.

Types sommes: unions

Les types sommes sont une généralisation des types énumérés: au lieu de définir des constantes, on définit des constructeurs qui prennent des arguments pour définir une valeur du nouveau type. Considérons par exemple un type d'expressions contenant des constantes (définies par leur valeur entière), des variables (définies par leur nom), des additions et des multiplications (définies par le couple de leurs deux opérandes), et des exponentiations définies par le couple d'une expression et de son exposant. On définira le type expression par:
type expression =
 | Const of int
 | Var of string
 | Add of expression * expression
 | Mul of expression * expression
 | Exp of expression * int;;

On crée des valeurs de type somme en appliquant leurs constructeurs à des arguments du bon type. Par exemple le polynôme 1 + 2x3 est représenté par l'expression:
let p = Add (Const 1, Mul (Const 2, Exp (Var "x", 3)));;

Les types somme permettent de faire du filtrage (pattern matching), afin de distinguer les cas en fonction d'une valeur filtrée. Ainsi la dérivation par rapport à une variable x se définirait simplement par:
let rec dérive x e =
 match e with
 | Const _ -> Const 0
 | Var s -> if x = s then Const 1 else Const 0
 | Add (e1, e2) -> Add (dérive x e1, dérive x e2)
 | Mul (Const i, e2) -> Mul (Const i, dérive x e2)
 | Mul (e1, e2) -> Add (Mul (dérive x e1, e2), Mul (e1, dérive x e2))
 | Exp (e, i) -> Mul (Const i, Mul (dérive x e, Exp (e, i - 1)));;

Nous ne donnerons ici que la signification intuitive du filtrage sur notre exemple particulier. La construction match du corps de dérive signifie qu'on examine la valeur de l'argument e et selon que c'est: On constate sur cet exemple la puissance et l'élégance du mécanisme. Combiné à la récursivité, il permet d'obtenir une définition de dérive qui se rapproche des définitions mathématiques usuelles.On obtient la dérivée du polynôme p = 1 + 2x3 en évaluant:
#dérive "x" p;;
- : expression =
 Add
  (Const 0,
   Mul (Const 2, Mul (Const 3, Mul (Const 1, Exp (Var "x", 2)))))
On constate que le résultat obtenu est grossièrement simplifiable. On écrit alors un simplificateur (naïf) par filtrage sur les expressions:
let rec puissance i j =
 match j with
 | 0 -> 1
 | 1 -> i
 | n -> i * puissance i (j - 1);;

let rec simplifie e =
 match e with
 | Add (Const 0, e) -> simplifie e
 | Add (Const i, Const j) -> Const (i + j)
 | Add (e, Const i) -> simplifie (Add (Const i, e))
 | Add (e1, e2) -> Add (simplifie e1, simplifie e2)
 | Mul (Const 0, e) -> Const 0
 | Mul (Const 1, e) -> simplifie e
 | Mul (Const i, Const j) -> Const (i * j)
 | Mul (e, Const i) -> simplifie (Mul (Const i, e))
 | Mul (e1, e2) -> Mul (simplifie e1, simplifie e2)
 | Exp (Const 0, j) -> Const 0
 | Exp (Const 1, j) -> Const 1
 | Exp (Const i, j) -> Const (puissance i j)
 | Exp (e, 0) -> Const 1
 | Exp (e, 1) -> simplifie e
 | Exp (e, i) -> Exp (simplifie e, i)
 | e -> e;;

Pour comprendre le filtrage de la fonction simplifie, il faut garder à l'esprit que l'ordre des clauses est significatif puisqu'elles sont essayées dans l'ordre. Un exercice intéressant consiste aussi à prouver formellement que la fonction simplifie termine toujours. On obtient maintenant la dérivée du polynôme p = 1 + 2x3 en évaluant:
#simplifie (dérive "x" p);;
- : expression = Mul (Const 2, Mul (Const 3, Exp (Var "x", 2)))

Types produits: enregistrements

Les enregistrements (records en anglais) permettent de regrouper des informations hétérogènes. Ainsi, on déclare un type date comme suit:
type mois =
 | Janvier | Février | Mars | Avril | Mai | Juin | Juillet
 | Aout | Septembre | Octobre | Novembre | Décembre;;

type date = {j: int; m: mois; a: int};;

let berlin = {j = 10; m = Novembre; a = 1989}
and bastille = {j = 14; m = Juillet; a = 1789};;

Un enregistrement contient des champs de type quelconque, donc éventuellement d'autres enregistrements. Supposons qu'une personne soit représentée par son nom, et sa date de naissance; le type correspondant comprendra un champ contenant un enregistrement de type date:
type personne = {nom: string; naissance: date};;

let poincaré =
 {nom = "Poincaré"; naissance = {j = 29; m = Avril; a = 1854}};;

Les champs d'un enregistrement sont éventuellement mutables, c'est-à-dire modifiables par affectation. Cette propriété est spécifique à chaque champ et se déclare lors de la définition du type, en ajoutant le mot clé mutable devant le nom du champ. Pour modifier le champ label du record r en y déposant la valeur v, on écrit r.label <-v.

#type point = {mutable x : int; mutable y : int};;
Le type t est défini.
#let origine = {x = 0; y = 0};;
origine : point = {x = 0; y = 0}
#origine.x <- 1;;
- : unit = ()
#origine;;
- : point = {x = 1; y = 0}

En combinaison avec les types somme, les enregistrements modélisent des types de données complexes:
type complexe =
   | Cartésien of cartésiennes
   | Polaire of polaires

and cartésiennes = {re: float; im: float}
and polaires = {rho: float; theta: float};;

let pi = 4.0 *. atan 1.0;;

let x = Cartésien {re = 0.0; im = 1.0}
and y = Polaire {rho = 1.0; theta = pi /. 2.0};;

Une rotation de p/2 s'écrit alors:
let rotation_pi_sur_deux = function
  | Cartésien x -> Cartésien {re = -. x.im; im = x.re}
  | Polaire x -> Polaire {rho = x.rho; theta = x.theta +. pi /. 2.0};;

Types abréviations

On donne un nom à une expression de type à l'aide d'une définition d'abréviation. C'est quelquefois utile pour la lisibilité du programme. Par exemple:
type compteur = int;;
définit un type compteur équivalent au type int.

Types abstraits

Si, dans l'interface d'un module (voir ci-dessous), on exporte un type sans rien en préciser (sans donner la liste de ses champs s'il s'agit d'un type enregistrement, ni la liste de ses constructeurs s'il s'agit d'un type somme), on dit qu'on a abstrait ce type, ou qu'on l'a exporté abstraitement. Pour exporter abstraitement le type t, on écrit simplement

type t;;

L'utilisateur du module qui définit ce type abstrait n'a aucun moyen de savoir comment le type t est implémenté s'il n'a pas accès au source de l'implémentation du module. Cela permet de changer cette implémentation (par exemple pour l'optimiser) sans que l'utilisateur du module n'ait à modifier ses propres programmes. C'est le cas du type des piles dans l'interface du module stack décrit ci-dessous.

Égalité de types

La concordance des types se fait par nom. Les définitions de type sont qualifiées de génératives, c'est-à-dire qu'elles introduisent toujours de nouveaux types (à la manière des let emboîtés qui introduisent toujours de nouveaux identificateurs). Ainsi, deux types sont égaux s'ils font référence à la même définition de type.

Attention: ce phénomène implique que deux types de même nom coexistent parfois dans un programme. Dans le système interactif, cela arrive quand on redéfinit un type qui était erroné. Le compilateur ne confond pas les deux types, mais il énonce éventuellement des erreurs de type bizarres, car il n'a pas de moyen de nommer différemment les deux types. Étrangement, il indique alors qu'un type t (l'ancien) n'est pas compatible avec un type t (mais c'est le nouveau). Considérons les définitions
#type t = C of int;;
type t = C of int
#let int_of_t x =
  match x with C i -> i;;
val int_of_t : t -> int = <fun>

Jusque là rien d'anormal. Mais définissons t à nouveau (pour lui ajouter un nouveau constructeur par exemple): l'argument de la fonction int_of_t est de l'ancien type t et on ne peut pas l'appliquer à une valeur du nouveau type t. (Voir aussi l'URL http://pauillac.inria.fr/caml/FAQ/FAQ_EXPERT-fra.html.)
#type t = C of int | D of float;;
type t = C of int | D of float
#int_of_t (C 2);;
           ^^^
This expression has type t but is here used with type t
Ce phénomène se produit aussi avec le compilateur indépendant (en cas de gestion erronée des dépendances de modules). Si l'on rencontre cet étrange message d'erreur, il faut tout recommencer; soit quitter le système interactif et reprendre une nouvelle session; soit recompiler entièrement tous les modules de son programme.

Structures de données polymorphes

Toutes les données ne sont pas forcément d'un type de base. Certaines sont polymorphes c'est-à-dire qu'elles possèdent un type dont certaines composantes ne sont pas complètement déterminées mais comporte des variables de type. L'exemple le plus simple est la liste vide, qui est évidemment une liste d'entiers (intlist) ou une liste de booléens (boollist) et plus généralement une liste de ``n'importe quel type'', ce que Caml symbolise par 'a (et la liste vide polymorphe est du type 'alist).

On définit des structures de données polymorphes en faisant précéder le nom de leur type par la liste de ses paramètres de type. Par exemple:
type 'a liste =
   | Nulle
   | Cons of 'a * 'a liste;;

ou encore pour des tables polymorphes:
type ('a, 'b) table = {nb_entrées : int; contenu : ('a * 'b) vect};;

Les listes prédéfinies en Caml forment le type list et sont équivalentes à notre type liste. La liste vide est symbolisée par [] et le constructeur de liste est noté ::, et correspond à notre constructeur Cons. Pour plus de commodité, l'opérateur :: est infixe: x ::l représente la liste qui commence par x, suivi des éléments de la liste l. En outre, on dispose d'une syntaxe légère pour construire des listes littérales: on écrit les éléments séparés par des point-virgules, le tout entre crochets [ et ].
#let l = [1; 2; 3];;
val l : int list = [1; 2; 3]
#let ll = 0 :: l;;
val ll : int list = [0; 1; 2; 3]
Les listes sont munies de nombreuses opérations prédéfinies, dont les fonctionnelles de parcours ou d'itération, map, do_list ou it_list, ou encore la concaténation @. À titre d'exemple emblématique de fonction définie sur les listes, nous redéfinissons la fonctionnelle map qui applique une fonction sur tous les éléments d'une liste.
#let print_list l = do_list print_int l;;
val print_list : int list -> unit = <fun>
#print_list l;;
123- : unit = ()
#let rec map f l =
  match l with
  | [] -> []
  | x :: rest -> f x :: map f rest;;
map : ('a -> 'b) -> 'a list -> 'b list = <fun>
#let succ_l = map (function x -> x + 1) ll;;
val succ_l : int list = [1; 2; 3; 4]
#print_list succ_l;;
1234- : unit = ()
#let somme l = it_list (function x -> function y -> x + y) 0 l;;
val somme : int list -> int = <fun>
#somme ll;;
- : int = 6
#somme succ_l;;
- : int = 10

La manipulation des listes est grandement facilitée par la gestion automatique de la mémoire, puisque l'allocation et la désallocation sont prises en charge par le gestionnaire de mémoire et son programme de récupération automatique des structures devenues inutiles (le ramasse-miettes, ou glaneur de cellules, ou GC (garbage collector)).
En Caml, la gestion mémoire est automatique.
B.2.11 Modules

On dispose d'un système de modules simple qui définit un module comme un couple de fichiers. Le fichier d'interface spécifie les fonctionalités offertes par le module, et le fichier d'implémentation contient le code source qui crée ces fonctionalités. Le fichier d'interface a l'extension .mli (ml interface) et le fichier d'implémentation l'extension .ml. Prenons l'exemple d'un module Stack implémentant les piles. Son fichier d'interface est le fichier stack.mli suivant:
(* Stacks *)

(* This module implements stacks (LIFOs), with in-place modification. *)

type 'a t;;
        (* The type of stacks containing elements of type ['a]. *)

exception Empty;;
        (* Raised when [pop] is applied to an empty stack. *)

val create: unit -> 'a t
        (* Return a new stack, initially empty. *)
val push: 'a -> 'a t -> unit
        (* [push x s] adds the element [x] at the top of stack [s]. *)
val pop: 'a t -> 'a
        (* [pop s] removes and returns the topmost element in stack [s],
           or raises [Empty] if the stack is empty. *)
val clear : 'a t -> unit
        (* Discard all elements from a stack. *)
val length: 'a t -> int
        (* Return the number of elements in a stack. *)
val iter: ('a -> 'b) -> 'a t -> unit
        (* [iter f s] applies [f] in turn to all elements of [s], from the
           element at the top of the stack to the element at the
           bottom of the stack. The stack itself is unchanged. *)
;;
L'interface déclare les signatures des objets fournis par le module, types, exceptions ou valeurs. Une implémentation répondant à cette spécification est:
type 'a t = { mutable c : 'a list };;

let create () = { c = [] };;

let clear s = s.c <- [];;

let push x s = s.c <- x :: s.c;;

let pop s =
  match s.c with
  | hd::tl -> s.c <- tl; hd
  | []     -> raise Empty;;

let length s = List.length s.c;;

let iter f s = List.iter f s.c;;

La compilation de l'interface du module Stack produit un fichier stack.cmi et celle de l'implémentation le fichier stack.cmo. Quand le module Stack est compilé, on dispose de ses fonctionalités en écrivant la ligne

open Stack;;

en tête du fichier qui l'utilise. L'appel direct des identificateurs fournis par le module utilise la notation qualifiée, qui consiste à suffixer le nom du module par le symbole . suivi de l'identificateur. Ainsi Stack.pop désigne la fonction pop du module Stack. Nous avons déjà utilisé la notation dans nos programmes pour désigner les exceptions Sys.Break. De même, il est courant de ne pas ouvrir le module Printf pour un simple appel à la fonction d'impression formatée: on appelle directement la fonction Printf par son nom qualifié Printf.printf.

Pour qu'on puisse accéder aux identificateurs du module Stack, il faut que ce module soit accessible, c'est-à-dire résidant dans le répertoire de travail actuel ou bien dans la bibliothèque standard de Objective Caml, ou bien encore dans l'un des répertoires indiqués sur la ligne de commande du compilateur avec l'option -I. Lors de la création de l'exécutable, il faut également demander l'édition des liens de tous les modules utilisés dans l'application (autres que les modules de la bibliothèque standard).

Les modules permettent évidemment la compilation séparée, ce qui sous le système Unix s'accompagne de l'utilisation de l'utilitaire make. Nous donnons donc un makefile minimum pour gérer un programme découpé en modules. On s'inspirera de ce fichier pour créer ses propres makefiles. Dans ce squelette de fichier make, la variable OBJS est la liste des modules, et EXEC contient le nom de l'exécutable à fabriquer. Pour simplifier, on suppose qu'il y a deux modules seulement module1 et module2, et que l'exécutable s'appelle prog.
CAMLC=ocamlc -W -g -I .

OBJS= module1.zo module2.zo
EXEC= prog

all: $(OBJS)
        $(CAMLC) -o $(EXEC) $(OBJS)

clean:
        rm -f *.cm[io] *.cmix *~ #*#

depend:
        mv Makefile Makefile.bak
        (sed -n -e '1,/^### DO NOT DELETE THIS LINE/p' Makefile.bak; \
         camldep *.mli *.ml) > Makefile
        rm Makefile.bak

.SUFFIXES:
.SUFFIXES: .ml .mli .zo .zi

.mli.cmi:
        $(CAMLC) -c $<
.ml.cmo:
        $(CAMLC) -c $<

### EVERYTHING THAT GOES BEYOND THIS COMMENT IS GENERATED
### DO NOT DELETE THIS LINE

La commande makeall ou simplement make, refabrique l'exécutable et makeclean efface les fichiers compilés. Les dépendances entre modules sont automatiquement recalculées en lançant makedepend. La commande camldep est un perl script qui se trouve à l'adresse
http://pauillac.inria.fr/caml/FAQ/FAQ_EXPERT-fra.html#make.

Bibliothèques

Les bibliothèques du système Caml résident dans le répertoire lib de l'installation pour les bibliothèques de base indispensables. Les bibliothèques auxiliaires sont installées au même endroit; leur source se trouve dans le répertoire contrib de la distribution. Une documentation minimale est incluse dans les fichiers d'interface, sous la forme de commentaires. Sous Unix, il est très utile d'utiliser la commande camlbrowser (d'habitude créée lors de l'intallation du système), pour parcourir les librairies ou ses propres sources. Parmi les bibliothèques, nous citons simplement la bibliothèque du générateur de nombres aléatoires, celle de traitement de grammaires et celle des utilitaires graphiques.

Nombres aléatoires

Pour les essais, il est souvent pratique de disposer d'un générateur de nombres aléatoires. Le module Random propose la fonction Random.int qui renvoie un nombre aléatoire compris entre 0 inclus et son argument exclus. Random.float est analogue mais renvoie un nombre flottant. La fonction Random.init permet d'initialiser le générateur avec un nombre entier.

Analyse syntaxique et lexicale

Il existe une interface avec les générateurs d'analyseurs syntaxiques et lexicaux d'Unix (Yacc et Lex). Les fichiers d'entrée de camllex et camlyacc ont les extensions .mll et .mly. Sur le fonctionnement de ces traits avancés, consulter la documentation du langage.

B.2.12 Fonctions graphiques


Les primitives graphiques sont indépendantes de la machine. Sur les micros-ordinateurs le graphique est intégré à l'application; sur les machines Unix, il faut appeler une version interactive spéciale ocamlg (avec toutes les fonctions graphiques préchargées), qui s'obtient par la commande ocamlmktop -o ocamlg graphics.cma. On accède aux primitives graphiques en ouvrant le module Graphics. On crée la fenêtre de dessin en appelant la fonction open_graph qui prend en argument une chaîne de description de la géométrie de la fenêtre (par défaut, une chaîne vide assure un comportement raisonnable). La description de la fenêtre dépend de la machine et n'est pas obligatoirement prise en compte par l'implémentation de la bibliothèque.

Un programme qui utilise le graphique commence donc par ces deux lignes:
open Graphics;;
open_graph "";;

La taille de l'écran graphique dépend de l'implémentation, mais l'origine du système de coordonnées est toujours en bas et à gauche. L'axe des abscisses va classiquement de la gauche vers la droite et l'axe des ordonnées du bas vers le haut. Il y a une notion de point courant et de crayon avec une taille et une couleur courantes. On déplace le crayon, sans dessiner ou en dessinant des segments de droite par les fonctions suivantes:
moveto x y
déplace le crayon aux coordonnées absolues (x, y).

lineto x y
trace une ligne depuis le point courant jusqu'au point de coordonnées (x, y).
plot x y
trace le point (x, y).

set_color c
fixe la couleur du crayon. (Les couleurs sont obtenues par la fonction rgb; on dispose aussi des constantes black, white, red, green, blue, yellow, cyan et magenta.)

set_line_width n
change la largeur du trait du crayon.
draw_arc x y rx ry a1 a2
trace un arc d'ellipse de centre (x, y) de rayon horizontal rx, vertical ry, de l'angle a1 à l'angle a2 (en degrés).

draw_ellipse x y rx ry
trace une ellipse de centre (x, y) de rayon horizontal rx, et de rayon vertical ry.

draw_circle x y r
trace un cercle centre (x, y) et de rayon r.
On peint l'intérieur de ces courbes avec fill_rect, fill_arc, fill_ellipse, fill_circle. Dans la fenêtre graphique, on imprime avec les fonctions:
draw_char c
affiche le caractère c au point courant dans la fenêtre graphique.
draw_string s
affiche la chaîne de caractères s.
close_graph ()
détruit la fenêtre graphique.
clear_graph ()
efface l'écran.

size_x ()
renvoie la taille de l'écran en abscisses.
size_y ()
renvoie la taille de l'écran en ordonnées..

background
et foreground sont respectivement les couleurs du fond et du crayon.

point_color x y
renvoie la couleur du point (x, y).

current_point ()
renvoie la position du point courant.
button_down
renvoie vrai si le bouton de la souris est enfoncé, faux sinon.

mouse_pos ()
renvoie les cordonnées du curseur de la souris.

read_key ()
attend l'appui sur une touche, la renvoie.
key_pressed ()
renvoie vrai si une touche est enfoncée, faux sinon.
Plus généralement, un certain nombre d'événements observent l'interaction entre la machine et l'utilisateur:
wait_next_event evl
attend jusqu'à ce que l'un des événements de la liste evl se produise, et renvoie le statut de la souris et du clavier à ce moment-là. Les événements possibles sont:
Nous ne décrirons pas ici les primitives de manipulation des images qu'on trouve dans le module graphics.

Un exemple
Nous faisons rebondir une balle dans un rectangle, première étape vers un jeu de ping-pong.
open Graphics;;
open_graph "";;

let c = 5;;              (* Le rayon de la balle  *)

let draw_balle x y =
 set_color foreground; fill_circle x y c;;

let clear_balle x y =
 set_color background; fill_circle x y c;;

let get_mouse () =
 while not (button_down ()) do () done;
 mouse_pos();;

let wait () = for i = 0 to 1000 do () done;;

let v_x = 2              (* Vitesse de déplacement de la balle *)
and v_y = 3;;

let x_min = 2 * c + v_x;; (* Cadre autorisé *)
let x_max = size_x () - x_min;;
let y_min = 2 * c + v_y;;
let y_max = size_y () - y_min;;

let rec pong_aux x y dx dy =
 draw_balle x y;
 let new_x = x + dx
 and new_y = y + dy in
 let new_dx =
  if new_x <= x_min || new_x >= x_max then (- dx) else dx
 and new_dy =
  if new_y <= y_min || new_y >= y_max then (- dy) else dy in
 wait ();
 clear_balle x y;
 pong_aux new_x new_y new_dx new_dy;;

let pong () = clear_graph(); pong_aux 20 20 v_x v_y;;

pong ();;

Les adeptes du style impératif écriraient plutôt la procédure pong ainsi:
let dx = ref v_x
and dy = ref v_y;;

let pong () =
 clear_graph();
 let x = ref 20
 and y = ref 20 in
 while true do
  let cur_x = !x
  and cur_y = !y in
  draw_balle cur_x cur_y;
  x := cur_x + !dx;
  y := cur_y + !dy;
  if !x <= x_min || !x >= x_max then dx := - !dx;
  if !y <= y_min || !y >= y_max then dy := - !dy;
  wait ();
  clear_balle cur_x cur_y
 done;;

Documentation

La documentation de Caml se trouve évidemment dans le manuel de référence [2]. On trouve aussi de la documentation en anglais, sous forme d'aide en ligne sur les micros ordinateurs Macintosh et PC. Beaucoup d'informations sont disponibles directement sur la toile ou World Wide Web:

http://caml.inria.fr/index-fra.html: site principal de Caml.

http://caml.inria.fr/ocaml/htmlman/index.html: manuel en anglais.

http://caml.inria.fr/hump.html: bibliothèque et outils.

http://caml.inria.fr/FAQ/index-fra.html: la FAQ de Caml, les questions et réponses fréquemment posées au sujet du langage.

B.3 Syntaxe BNF de Caml



Nous donnons une syntaxe BNF (Backus Naur Form) étendue. Chaque règle de la grammaire définit un non-terminal par une production. Le non-terminal défini est à gauche du symbole ::=, la production à droite. Un non-terminal est écrit ainsi, les mots clés et symboles terminaux ainsi. Dans les membres droits de règles, le symbole | signifie l'alternative, les crochets indiquent une partie optionnelle [ ainsi ], les accolades une partie qui peut être répétée un nombre quelconque de fois { ainsi }, tandis qu'un symbole + en exposant des accolades indique une partie répétée au moins une fois, { ainsi }+. Dans les règles lexicales les trois points ..., situés entre deux caractères a et b, indiquent l'ensemble des caractères entre a et b dans l'ordre du code ASCII. Finalement, les parenthèses servent au groupement (ainsi).

Règles de grammaires

implementation ::= { impl-phrase   ;; }

impl-phrase ::= expression    |    value-definition
  | type-definition    |    exception-definition    |    directive

value-definition ::= let   [ rec ]   let-binding   { and   let-binding }

let-binding ::= pattern   =   expression    |    variable   pattern-list   =   expression

interface ::= { intf-phrase   ;; }

intf-phrase ::= value-declaration    |    type-definition    |    exception-definition    |    directive

value-declaration ::= value   ident   :   type-expression   { and   ident   :   type-expression }

expression ::= primary-expression
  | construction-expression
  | nary-expression
  | sequencing-expression

primary-expression ::= ident    |    variable    |    constant    |    (   expression   )
  | begin   expression   end    |    (   expression   :   type-expression   )

construction-expression ::= ncconstr   expression
  | expression   ,   expression   { ,   expression }
  | expression   ::   expression    |    [   expression   { ;   expression }   ]
  | [|   expression   { ;   expression }   |]
  | {   label   =   expression   { ;   label   =   expression }   }
  | function   simple-matching    |    fun   multiple-matching

nary-expression ::= expression   expression
  | prefix-op   expression    |    expression   infix-op   expression
  | expression   &   expression    |    expression   or   expression
  | expression   .   label    |    expression   .   label   <-   expression
  | expression   .(   expression   )    |    expression   .(   expression   )   <-   expression
  | expression   .[   expression   ]    |    expression   .[   expression   ]   <-   expression

sequencing-expression ::= expression   ;   expression
  | if   expression   then   expression   [ else   expression ]
  | match   expression   with   simple-matching
  | try   expression   with   simple-matching
  | while   expression   do   expression   done
  | for   ident   =   expression   ( to | downto )   expression   do   expression   done
  | let   [ rec ]   let-binding   { and   let-binding }   in   expression

simple-matching ::= pattern   ->   expression   { |   pattern   ->   expression }

multiple-matching ::= pattern-list   ->   expression   { |   pattern-list   ->   expression }

pattern-list ::= pattern   { pattern }

prefix-op ::= - | -. | !

infix-op ::= + | - | * | / | mod | +. | -. | *. | /. | @ | ^ | ! | :=
  | = | <> | == | != | < | <= | > | <= | <. | <=. | >. | <=.

pattern ::= ident    |    constant    |    (   pattern   )    |    (   pattern   :   type-expression   )
  | ncconstr   pattern
  | pattern   ,   pattern   { ,   pattern }
  | pattern   ::   pattern    |    [   pattern   { ;   pattern }   ]
  | {   label   =   pattern   { ;   label   =   pattern }   }
  | pattern   |   pattern
  | _    |    pattern   as   ident

exception-definition ::= exception   constr-decl   { and   constr-decl }

type-definition ::= type   typedef   { and   typedef }

typedef ::= type-params   ident   =   constr-decl   { |   constr-decl }
  | type-params   ident   =   {   label-decl   { ;   label-decl }   }
  | type-params   ident   ==   type-expression
  | type-params   ident

type-params ::= nothing    |    '   ident    |    (   '   ident   { ,   '   ident }   )

constr-decl ::= ident    |    ident   of   type-expression

label-decl ::= ident   :   type-expression    |    mutable   ident   :   type-expression

type-expression ::= '   ident    |    (   type-expression   )
  | type-expression   ->   type-expression    |    type-expression   { *   type-expression }+
  | typeconstr    |    type-expression   typeconstr
  | (   type-expression   { ,   type-expression }   )   typeconstr

constant ::= integer-literal    |    float-literal    |    char-literal    |    string-literal    |    cconstr

global-name ::= ident    |    ident   __   ident

variable ::= global-name    |    prefix   operator-name

operator-name ::= + | - | * | / | mod | +. | -. | *. | /.
  | @ | ^ | ! | := | = | <> | == | != | !
  | < | <= | > | <= | <. | <=. | >. | <=.

cconstr ::= global-name    |    []    |    ()

ncconstr ::= global-name    |    prefix   ::

typeconstr ::= global-name

label ::= global-name

directive ::= #   open   string    |    #   close   string    |    #   ident   string

Précédences

Les précédences relatives des opérateurs et des constructions non fermées sont données dans l'ordre décroissant. Chaque nouvelle ligne indique une précédence décroissante. Sur chaque ligne les opérateurs de même précédence sont cités séparés par des blancs; ou séparés par une virgule suivie du mot puis, en cas de précédence plus faible. La décoration [droite] ou [gauche] signifie que le ou les opérateurs qui précédent possèdent l'associativité correspondante.

Les précédences relatives des opérations dans les expressions sont les suivantes:

Accès: !, puis . .( .[

Applications: application de fonction [droite], puis application de constructeur

Arithmétique: - -. (unaire), puis mod [gauche], puis * *. / /. [gauche], puis + +. - -. [gauche]

Opérations non arithmétiques: :: [droite], puis @ ^ [droite]

Conditions: (= == < etc.) [gauche], puis not, puis & [gauche], puis or [gauche]

Paires: ,

Affectations: <- := [droite]

Constructions: if, puis ; [droite], puis let match fun function try.

Les précédences relatives des opérations dans les filtres sont les suivantes:

application de constructeur, puis :: [droite], puis ,, puis | [gauche], puis as.

Les précédences relatives des opérations dans les types sont les suivantes:

application de constructeur de type, puis *, puis -> [droite].



Règles lexicales

ident ::= letter   { letter | 0 ...9 | _ }

letter ::= A ... Z | a ... z

integer-literal ::= [ - ]   { 0 ...9 }+
  | [ - ]   ( 0x | 0X )   { 0 ...9 | A ...F | a ...f }+
  | [ - ]   ( 0o | 0O )   { 0 ...7 }+
  | [ - ]   ( 0b | 0B )   { 0 ...1 }+

float-literal ::= [ - ]   { 0 ...9 }+   [ .   { 0 ...9 } ]   [ ( e | E )   [ + | - ]   { 0 ...9 }+ ]


char-literal ::= `   regular-char   `
  | `   \   ( \ | ` | n | t | b | r )   `
  | `   \   ( 0 ...9 )   ( 0 ...9 )   ( 0 ...9 )   `


string-literal ::= "   { string-character }   "

string-character ::= regular-char
  | \   ( \ | " | n | t | b | r )
  | \   ( 0 ...9 )   ( 0 ...9 )   ( 0 ...9 )

Ces identificateurs sont des mots-clés réservés:
        and    as     begin       do      done      downto 
        else   end    exception   for     fun       function 
        if     in     let         match   mutable   not 
        of     or     prefix      rec     then      to 
        try    type   value       where   while     with
Les suites de caractères suivantes sont aussi des mots clés:
        #    !    !=   &    (    )    *    *.   +    +. 
        ,    -    -.   ->   .    .(   .[   /    /.   : 
        ::   :=   ;    ;;   <    <.   <-   <=   <=.  <>
        <>.  =    =.   ==   >    >.   >=   >=.  @    [ 
        [|   ]    ^    _    __   {    |    |]   }    '
Les ambiguités lexicales sont résolues par la règle du plus long préfixe (ou ``longest match''): quand une suite de caractères permet de trouver plusieurs lexèmes, le plus long est choisi.

Bibliographie

Précédent Remonter Suivant