Produit à champs nommés (enregistrements) : { ••• }

Comme un type *, un type enregistrement implémente les n-uplets. La différence tient essentiellement à ce que chaque composante (ou champ) d’un n-uplet enregistrement possède un nom (une étiquette). De plus si un des champs d’un type enregistrement a été déclaré mutable, alors ce champ peut être modifié dans une valeur de ce type. Par exemple, pour implémenter les triplets formés de deux chaines de caractères et d’un entier modifiable, on peut définir le type
type individu = {Nom : string; Prenom : string; mutable Age : int};;
La syntaxe générale est type <ident> = {[mutable] <étiquette> : <expression de type> ;. . . }
où mutable est optionnel et les étiquettes peuvent être des identificateurs quelconques.
Pour définir une valeur de type enregistrement, on utilise le signe = comme dans let dupont = {Nom = « Dupont »; Pr´enom = « Jean »; Age = 19};;
Si x est une valeur de type enregistrement et si e est l’étiquette d’un champ de ce type, on accède au champ d’étiquette e de x par x.e; au cas où le champ a été déclaré mutable, l’affectation de v au champ e de la valeur x se fait par l’expression de type unit : x.e <- v.
Par exemple, après l’instruction 1
dupont.Age <- 20;; l’expression dupont.Pr´enom ^  »  » ^ dupont.Nom ^  » a  » ^ (string_of_int dupont.Age) ^  » ans. » aura pour valeur la chaine « Jean Dupont a 20 ans. ».
MOTIFS :
– si les mi sont des motifs et si les ei sont des étiquettes d’un même type enregistrement, alors {e1 = m1;. . .} est un motif.
Par exemple, les fonctions function x -> x.Age et function {Age = n} -> n de type in-dividu -> int sont équivalentes.

Somme : ••• | •••

Un type somme permet d’implémenter la réunion disjointe d’ensembles eux-mêmes implé-mentés par des types donnés. La syntaxe générale de définition d’un type somme est
type <ident> = <constructeur> of <expression de type> | . . . ;;
où les <constructeurs> sont des identificateurs quelconques 2. Dans une telle déclaration, chaque terme de la somme représente un type et la somme elle-même implémente la réunion de ces types. Au cas où l’un des termes représente un type réduit à un élément comme le type unit, il ne faut pas définir ce terme par <constructeur> of unit mais, plus simplement par <constructeur>; on parle alors de constructeur constant. Par exemple, pour implémenter la droite numérique achevée, R = R ∪{+∞} ∪{−∞} on peut définir le type
type r_barre = R´eel of float | Plusinfini | Moinsinfini;;
Pour construire des expressions d’un type somme, on utilise la syntaxe
<constructeur non constant> <expr> ou <constructeur constant>
Par exemple, les éléments 3,14 et +∞ de R sont implémentés respectivement par les valeurs CAML R´eel 3.14 et Plusinfini de type r_barre.
MOTIFS :
– si c onst r est un constructeur constant, c onst r est un motif (qui ne filtre qu’une valeur);
– si c onst r est un constructeur non constant et si m est un motif du type associé à c onst r alors c onst r m est un motif de type somme.
Par exemple, la valeur CAML suivante
(function R´eel x -> R´eel (x *. x) | _ -> Plusinfini) : r_barre -> r_barre
implémente l’application x ∈ R 7→x2 ∈ R.
1. On appelle ici instruction une expression de type unit.
2. Mais l’usage veut que la première lettre d’un constructeur soit une majuscule.

Fonctions : ’a -> ’b

Le type ’a -> ’b implémente l’ensemble des fonctions de ’a dans ’b 1.
Si f : ’a -> ’b et x : ’a, alors l’expression f x s’évalue en la valeur de la fonction f pour l’argument x.
La syntaxe d’une expression de type ’a -> ’b est function <motif1> -> <expr1> | . . . | <motifn > -> <exprn > où les <motifi > filtrent des valeurs de type ’a et les <expri > sont des expressions de type ’b. Si f : ’a -> ’b -> ’c est une fonction curryfiée, x : ’a et y : ’b alors l’expression f x y
: ’c se lit ( f (x))(y).
La syntaxe d’une expression de type ’a -> ’b -> ’c est fun <motif11> <motif21> -> <expr1> | . . . | <motif1n > <motif2n > -> <exprn >

Les structures de contrôle

Séquence

Quand une expression de la forme <expr1> ; <expr2> est évaluée, <expr1> puis <expr2> sont évaluées et la valeur de l’expression entière est celle de <expr2>. Par exemple, l’expression false;3.14;1 s’évalue en 1.

Filtrage d’une expression

Soient <expr> une expression de type t , <motifi > des motifs de type t et <expri > des expres-sions de type t 0. Alors l’expression <expr0> suivante
match <expr> with <motif1> -> <expr1> | . . .
est une expression de type t 0 évaluée comme suit :
<expr> est filtrée par <motif1>. Si le filtrage réussit, <expr0> s’évalue en <expr1> avec les liaisons effectuées par le filtrage. S’il échoue, <expr> est filtrée par <motif2> et ainsi de suite 2.

Liaison locale

L’expression <expr> suivante let <motif> = <expr1> in <expr2>
s’évalue ainsi : <expr1> est filtrée par <motif> et si le filtrage réussit (ce qui sera toujours le cas si <motif> est un identificateur) 3, <expr> s’évalue en la valeur de <expr2> avec les liaisons effec-tuées par le filtrage 4.
Pour lier un identificateur à une fonction, on peut remplacer l’expression let <ident> = fun <motif1> . . . <motifn > -> <expr1> in <expr2>
par l’expression simplifiée équivalente let <ident> <motif1> . . . <motifn > = <expr1> in <expr2>
Dans le cas d’une fonction récursive (<expr1> contient des appels de la fonction <ident>) il faut remplacer let par let rec comme dans let rec fact n = if n = 0 then 1 else n * fact (n – 1) in fact 5
qui s’évalue en 5! = 120 5.
Pour effectuer plusieurs liaisons, utiliser and :
let . . . = . . . and . . . and . . . = . . . in <expr>
1. Voir page 13.
2. Une expression équivalente à <expr0> est donc (function <motif1> -> <expr1> | . . . ) <expr>
3. Si le filtrage échoue, une exception Match_failure est déclenchée.
4. <expr> est donc équivalente à l’expression match <expr1> with <motif> -> <expr2>
5. Il est parfois possible d’utiliser let rec pour lier des identificateurs à des valeurs cycliques non fonctionnelles comme dans let rec x = 1 :: x in x = tl x qui s’évalue en true.

Sélection

Si <expr1> est une expression de type bool et si <expr2> et <expr3> sont deux expressions de même type,alors if <expr1> then <expr2> else <expr3> est une expression qui s’évalue en la valeur de <expr2> si <expr1> s’évalue en true et en celle de <expr3> si <expr1> s’évalue en false.
L’expression
if <expr1> then <expr2> else ()
peut être simplifiée en
if <expr1> then <expr2> 1

Répétition (boucle for)

Si <expr1> et <expr2> sont deux expressions de type int et si <expr3> est une expression de type quelconque, alors l’expression
for <ident> = <expr1> to <expr2> do <expr3> done
évalue <expr3> pour les valeurs <expr1>, <expr1> +1, . . ., <expr2> de <ident> (ne fait rien si <expr1> > <expr2>); la valeur de l’expression entière est ().
L’indice <ident> croît donc dans la boucle. Pour le faire décroître, remplacer to par downto.

Répétition (boucle while)

Si <expr1> est une expression de type bool et si <expr2> est une expression de type quel-conque, alors l’expression while <expr1> do <expr2> done évalue <expr2> tant que <expr1> s’évalue en true; la valeur de l’expression entière est ().

Gestion des exceptions

Arrêt d’un programme par déclenchement d’une exception

Le type exn est un type somme prédéfini en CAML de la manière suivante :
type exn = Exit | Not_found | Failure of string;; 2
Le type exn a la particularité d’être extensible. Pour ajouter un terme au type exn, il faut employer l’une des deux syntaxes
exception <constructeur constant> ;;
exception <constructeur non constant> of <expression de type>;; Ainsi, si l’on définit
exception Monexception of int;;
le type exn deviendra
Exit | Not_found | Failure of string | Monexception of int;;
On dispose de la fonction fondamentale de déclenchement d’exception
raise : exn -> ’a
Cette fonction est à valeurs dans un type quelconque (’a), ce qui signifie que, si e est une ex-pression de type exn (une valeur exceptionnelle), l’expression raise e peut être placée dans un programme à tout endroit où on attend une expression (quelque soit le type de l’expression at-tendue). Si raise e est évaluée, l’éxécution du programme est immédiatement stoppée (le pro-gramme « plante ») et on voit s’afficher le message (d’erreur) :
Uncaught exception : e qui signifie « exception non rattrapée : e ». On dit que l’exception e a été déclenchée.
Exemple 1.1 La bibliothèque CAML fournit la fonction failwith : string -> ’a définie par let faiwith s = raise (Failure s);;. On convient d’utiliser la fonction failwith pour
1. <expr2> doit donc être de type unit.
2. En fait, le type exn contient d’autres termes comme Out_of_memory, Invalid_argument of string et Match_failure of string * int * int (pour les échecs de filtrages).
déclencher l’exception Failure « <ident> » quand la fonction <ident> a été appelée avec un argument invalide. Par exemple si on définit la fonction fact par le programme 1.1 alors fact 5 s’évalue en 120 et l’évaluation de fact (-5) déclenche l’exception Failure « fact ».
Programme 1.1 Factorielle
let rec fact = function (* fact : int -> int *)
0 -> 1 | n -> if n < 0 then failwith « fact » else n * fact(n-1);;
Exemple 1.2 Considérons la fonction rech du programme 1.2.
Programme 1.2 Recherche dans un tableau non trié avec déclenchement d’une exception en cas de succés exception Indice of int;;
let rech t x = (* rech : ’a vect -> ’a -> unit *)
for i = 0 to vect_length t – 1 do
if x = t.(i) then raise(Indice i)
done;;
rech [|5;10;-8|] 10;; (* d´eclenche l’exception Indice 1 *)
rech [|5;10;-8|] 1;; (* renvoie () *)
Soit i le plus petit indice tel que t .(i ) = x, s’il en existe, alors l’évaluation de rech t x dé-clenche l’exception Indice i ; si i n’existe pas, rech t x s’évalue simplement en ().

Rattrapage d’une exception

En fait, planter un programme est toujours fâcheux. On s’arrange toujours pour que l’éxécu-tion d’un programme ou bien ne déclenche jamais d’exception, ou bien rattrape chaque excep-tion déclenchée. Cela se fait en utilisant la syntaxe
try <expr> with <motif1> -> <expr1> | . . . | <motifn > -> <exprn >
où <expr> et les <expri > sont des expressions de même type t et les <motifi > sont des motifs de type exn.
L’expression try . . . est une expression <expr0> de type t évaluée de la manière suivante :
En premier lieu, <expr> est évaluée;
– si l’évaluation de <expr> fournit le résultat v (sans déclencher d’exception) alors l’évalua-tion de <expr0> est terminée et le résultat est v;
– si l’évaluation de <expr> déclenche l’exception e, alors<expr0> s’évalue en match e with <motif1> -> <expr1> | . . . | <motifn > -> <exprn >
si le filtrage réussit pour <motifi >, <expr0> s’évalue donc en <expri >; si le filtrage échoue, <expr0> déclenche l’exception e.
Exemple 1.3 (suite de l’exemple 1.1) Le programme 1.3, qui utilise la fonction fact du pro-gramme 1.1, fournit une fonction c : int -> int -> int telle que, si n et p sont Ê 0, c n p renvoie le nombre de parties à p éléments d’un ensemble à n éléments 1.
Programme 1.3 Coefficient du binôme
let c n p =
try fact n / (fact p * fact(n-p)) with Failure « fact » -> 0;;
c 4 2;; (* renvoie 6 *)
c 2 4;; (* renvoie 0 *)
1. La méthode utilisée est particulièrement inefficace : il serait préférable d’utiliser le triangle de Pascal.
Exemple 1.4 (suite de l’exemple 1.2) Le programme 1.4 fournit une fonction rech’ : ’a vect -> ’a -> int telle que rech’ t x renvoie le plus petit indice i tel que t .(i ) = x s’il en existe et −1 sinon.
Programme 1.4 Recherche dans un tableau non trié
let rech’ t x =
try
for i = 0 to vect_length t – 1 do
if x = t.(i) then raise(Indice i)
done;
-1
with Indice i -> i;;
rech’ [|5;10;-8|] 10;; (* renvoie 1 *)
rech’ [|5;10;-8|] 1;; (* renvoie -1 *)

Priorités et associativités des opérateurs

Le tableau 1.1 donne les priorités des opérateurs de construction d’expressions, de motifs et d’expressions de type. Dans chacun des trois cas un opérateur est prioritaire sur tout autre opérateur situé plus bas. Les opérateurs situés sur une même ligne ont la même priorité.
De plus, la plupart des opérateurs binaires possèdent une associativité gauche ou droite. Ainsi l’opérateur de construction d’expressions / est associatif à gauche, ce qui signifie que l’ex-pression a / b / c est équivalente à ( a / b ) / c. On a déja vu à la section 1.1.3 que l’opérateur -> de construction d’expressions de type était associatif à droite.

La bibliothèque Caml

Les éléments CAML décrits jusqu’à présent font partie du noyau de base du langage. Les élé-ments complémentaires décrits dans cette section constituent l’essentiel de la bibliothèque d’uti-litaires. Cette bibliothèque est partagée en modules.
Pour accéder aux éléments d’un module, il suffit d’ouvrir ce module par la directive :
#open « <nom du module> »;;
Soit e un élément d’un module (une valeur, un type, etc.); même si le module n’est pas ouvert, il est possible d’accéder à cet élément à condition d’employer la syntaxe
<nom du module>__e
Cette manière de faire est d’ailleurs la seule possible dans le cas où l’on désire utiliser deux élé-ments de deux modules différents qui ont le même nom 1.
Certains des modules contiennent de nouvelles fonctions (une fonction de tri, des fonctions permettant de générer des nombres aléatoires et des fonctions graphiques); d’autres implémentent de nouvelles structures de données.
Une structure de données abstraite est définie par un ensemble d’objets et par un ensemble d’opérations sur ces objets. par exemple, les objets de la structure de données tableau sont les n-uplets d’éléments d’un ensemble fixé et les opérations sont :
– création d’un tableau de longueur donnée;
– accés à un élément d’indice donné d’un tableau;
– modification d’un élément d’un tableau donné par son indice.
Une structure de données est dite dynamique si les opérations peuvent modifier un objet de la structure (c’est le cas des tableaux).
Une structure de données (concrète) est une implémentation d’une structure de données abstraite. Deux structures de données concrètes implémentant une même structure de données abstraite peuvent avoir des performances différentes en espace pour le stockage des objets; et en temps pour les opérations.

Fonction de tri (module sort)

sort : (’a -> ’a -> bool) -> ’a list -> ’a list
sort f ` trie la liste ` en ordre croissant selon la relation d’ordre définie par f : x É y ⇔ f x y.
merge : (’a -> ’a -> bool) -> ’a list -> ’a list -> ’a list
merge f `1 `2 fusionne les listes `1 et `2 supposées triées pour renvoyer une liste triée contenant les éléments de `1 et de `2.

 Piles (module stack)

Les piles ou files LIFO (Last In First Out) forment une structure de données dynamique dont les objets sont les n-uplets d’éléments d’un ensemble E. Le dernier élément d’une pile non vide est appelé le sommet, ce qui suggère de représenter une pile verticalement. Les opérations de base sont
– création d’une pile vide;
– empiler (ou push) : ajouter un élément au sommet d’une pile (cet élément devient le nou-veau sommet);
– dépiler (ou pop) : supprimer le sommet d’une pile non vide et le renvoyer.
Le module stack implémente les piles.
type ’a t le type des piles.
new : unit -> ’a t new() retourne une pile vide.
push : ’a -> ’a t -> unit push x p ajoute x au sommet de p.
pop : ’a t -> ’a pop p supprime et retourne le sommet de p.
clear : ’a t -> unit clear p vide la pile.
length : ’a t -> int length p retourne le nombre d’éléments de p.
iter : (’a -> ’b) -> ’a t -> unit iter f p applique f à chaque élément de p.
La fonction pop déclenche l’exception Empty quand elle est appelée sur une pile vide.
iter opère en partant du sommet.
1. Par exemple, les modules stack et queue contiennent tous les deux un type nommé t et une fonction nommée new. Pour utiliser les deux modules conjointement, il faut préciser le module comme dans stack__new ou queue__new.
2. int : int -> int
3. init : int -> unit

Files d’attente (module queue)

Les files d’attente ou files FIFO (First In First Out) forment une structure de données dyna-mique dont les objets sont les n-uplets d’éléments d’un ensemble E. Les opérations de base sont
– création d’une file vide;
– ajouter un élément à la fin d’une file (cet élément devient le nouveau dernier élément);
– supprimer et renvoyer le premier élément (début) d’une file non vide.
type ’a t le type des files d’attente.
new : unit -> ’a t new() retourne une file vide.
add : ’a -> ’a t -> unit add x ` ajoute x à la fin de `.
take : ’a t -> ’a supprime et retourne l’élément de début de la file.
peek : ’a t -> ’a retourne l’élément de début de la file.
clear : ’a t -> unit vide la file.
length : ’a t -> int retourne le nombre d’éléments de la file.
iter : (’a -> ’b) -> ’a t -> unit iter f ` applique f à chaque élément de `.
Appelées sur une file vide, les fonctions take et peek déclenchent l’exception Empty.
iter opère du début à la fin de la file.

1 Memento CAML 
1.1 Généralités
1.1.1 Types et expressions
1.1.2 Expressions fonctionnelles
1.1.3 Fonctions curryfiées
1.1.4 Opérateurs binaires
1.1.5 Motifs
1.1.6 Conventions
1.2 Sessions Caml
1.2.1 Expressions
1.2.2 Définitions de valeurs globales
1.2.3 Définitions de types
1.2.4 Définitions d’exceptions
1.2.5 Directives
1.3 Les types Caml et leurs utilisation
1.3.1 Ensemble à un élément : unit
1.3.2 Valeurs booléennes : bool
1.4 Les structures de contrôle
1.4.1 Séquence
1.4.2 Filtrage d’une expression
1.4.3 Liaison locale
1.4.4 Sélection
1.4.5 Répétition (boucle for)
1.4.6 Répétition (boucle while)
1.5 Gestion des exceptions
1.5.1 Arrêt d’un programme par déclenchement d’une exception
1.5.2 Rattrapage d’une exception
1.6 Priorités et associativités des opérateurs
1.7 La bibliothèque Caml
1.7.1 Fonction de tri (module sort)
1.7.2 Piles (module stack)
1.7.3 Files d’attente (module queue)
2 Preuve et évaluation d’un programme 
2.1 Preuve de validité d’un programme
2.1.1 Objets d’un programme
2.1.2 Spécifications d’un bloc d’instructions
2.1.3 Spécifications d’une fonction
2.1.4 Affectation
2.2 Complexité d’un programme
2.2.1 Récurrences « affines »
2.2.2 Récurrences « diviser pour régner »
2.2.3 Un autre exemple de récurrence : le tri rapide
3 Notions de base 
3.1 Mots et langages
3.1.1 Le monoïde libre des mots sur un alphabet
3.1.2 Définition d’un morphisme sur le monoïde libre par sa restriction aux lettres
3.1.3 Langages
3.2 Graphes et arbres non ordonnés
3.2.1 Graphes orientés
3.2.2 Arbres non ordonnés
3.2.3 Graphes non orientés
3.2.4 Parcours d’un graphe
4 Arbres
4.1 Arbres binaires
4.1.1 Définitions
4.1.2 Implémentation
4.1.3 Dénombrements dans les arbres binaires
4.2 Arbres ordonnés
4.2.1 Définitions
4.2.2 Implémentation
4.2.3 Parcours préfixe et postfixe d’un arbre et d’une forêt
4.3 Termes
4.3.1 Syntaxe et sémantique : les termes et les algèbres
4.3.2 Syntaxe concrète
4.3.3 Forme concrète postfixée d’un terme
5 Automates finis 
5.1 Automates finis non déterministes
5.1.1 Définition
5.1.2 Représentations d’un automate
5.1.3 Langage reconnu par un automate
5.1.4 Fonction de transition d’un automate
5.2 Automates finis déterministes
5.2.1 Définition
5.2.2 Déterminisation d’un automate
5.2.3 Fermeture de la classe des langages reconnaissables par les opérations ensemblistes
5.3 Automateminimal
5.3.1 Résiduels d’un langage
5.3.2 Définition
5.4 Transitions instantanées
5.4.1 Définition
5.4.2 Suppression des transitions instantanées
5.4.3 Application
5.5 Rat(X¤)=Rec(X¤)
5.6 Implémentation
5.6.1 Analyse syntaxique (prog. 5.1)
5.6.2 Représentation d’un AF (prog. 5.2)
5.6.3 Opérations sur les AF (prog. 5.3)
Bibliographie