Structures de contrôle
Les entrées-sorties et les valeurs modifiables produisent des effets
de bord. Leur utilisation est facilitée par un style de programmation
impératif muni de nouvelles structures de contrôles. Nous présentons
dans ce paragraphe la structure séquentielle et les structures
itératives.
Nous avons déjà rencontré la structure de contrôle
conditionnelle à la page ?? dont la forme abrégée
if then prend son sens dans le monde impératif. On
écrira, par exemple :
# let n = ref 1 ;;
val n : int ref = {contents=1}
# if !n > 0 then n := n-1 ;;
Characters 20-21:
This expression has type int ref but is here used with type int
Séquence
La première de des structures typiquement impérative est la
séquence. Elle permet l'évaluation ordonnée de gauche à
droite d'une suite d'expressions séparées par un point-virgule.
Syntaxe
expr1 ; ...; exprn
Une séquence est une expression dont la valeur est celle de sa
dernière expression (ici, exprn). Néanmoins toutes les
expressions sont évaluées, et en particulier leurs effets de bord sont
pris en compte.
# print_string "2 = "; 1+1 ;;
2 = - : int = 2
Avec effet de bord, on retrouve la construction usuelle des langages
impératifs.
# let x = ref 1 ;;
val x : int ref = {contents=1}
# x:=!x+1 ; x:=!x*4 ; !x ;;
- : int = 8
Comme les valeurs précédant un point-virgule sont oubliées,
Objective CAML émet un avertissement quand elles ne sont pas de type
unit.
# print_int 1; 2 ; 3 ;;
Characters 14-15:
Warning: this expression should have type unit.
1- : int = 3
Pour éviter ce message, on peut utiliser la fonction
ignore :
# print_int 1; ignore 2; 3 ;;
1- : int = 3
Un message différent est obtenu si la valeur possède un type
fonctionnel car Objective CAML soupçonne que vous avez oublié un
paramètre d'une fonction.
# let g x y = x := y ;;
val g : 'a ref -> 'a -> unit = <fun>
# let a = ref 10;;
val a : int ref = {contents=10}
# let u = 1 in g a ; g a u ;;
Characters 13-16:
Warning: this function application is partial,
maybe some arguments are missing.
- : unit = ()
# let u = !a in ignore (g a) ; g a u ;;
- : unit = ()
En règle générale on parenthèse les séquences pour en clarifier la
portée. Syntaxiquement, le parenthésage peut prendre deux formes :
Syntaxe
( expr )
Syntaxe
begin expr end
On peut maintenant écrire de façon plus naturelle le programme C+/C-
de la page ?? :
# let rec cpcm n =
print_string "taper un nombre : ";
let i = read_int () in
if i = n then print_string "BRAVO\n\n"
else
begin
if i < n then print_string "C+\n" else print_string "C-\n" ;
cpcm n
end ;;
val cpcm : int -> unit = <fun>
Boucles
Les structures de contrôle itératives sont elles aussi en dehors du
monde fonctionnel. La condition de répétition, ou de sortie,
d'une boucle n'a de sens que si une modification physique de la
mémoire permet d'en changer la valeur. Il existe
deux structures de contrôle itératives : la boucle
for pour une itération bornée et la boucle
while pour une itération non bornée.
Les structures de boucle elles-mêmes sont des expressions du
langage. Elles retournent donc une valeur : la constante () du
type unit.
La boucle for peut être croissante (to) ou
décroissante (downto) d'un pas de un.
Syntaxe
| for nom = expr1 to
expr2 do expr3 done |
| for nom = expr1 downto
expr2 do expr3 done |
Les expressions expr1 et expr2 sont de type
int. Si expr3 n'est pas de type unit, le
compilateur engendre un message d'avertissement.
# for i=1 to 10 do print_int i; print_string " " done; print_newline() ;;
1 2 3 4 5 6 7 8 9 10
- : unit = ()
# for i=10 downto 1 do print_int i; print_string " " done; print_newline() ;;
10 9 8 7 6 5 4 3 2 1
- : unit = ()
La boucle non bornée est la boucle << tant que >> dont la syntaxe
est :
Syntaxe
while expr1 do expr2 done
L'expression expr1 doit être de type bool. Et,
comme pour la boucle for, si expr2 n'est pas de type
unit, le compilateur engendre un message d'avertissement.
# let r = ref 1
in while !r < 11 do
print_int !r ;
print_string " " ;
r := !r+1
done ;;
1 2 3 4 5 6 7 8 9 10 - : unit = ()
Il est important de comprendre que les boucles sont des expressions
comme les autres qui calculent la valeur () du type
unit.
# let f () = print_string "-- fin\n" ;;
val f : unit -> unit = <fun>
# f (for i=1 to 10 do print_int i; print_string " " done) ;;
1 2 3 4 5 6 7 8 9 10 -- fin
- : unit = ()
Notez que la chaîne "-- fin\n" est affichée après
qu'aient été affichés les entiers de 1 à 10 : on a là la
manifestation que les arguments (ici la boucle) sont évalués avant
d'être passés à la fonction.
En programmation impérative, le corps d'une boucle (l'expression
expr) ne calcule pas de valeur, mais procède par effets de
bords. En Objective CAML, lorsque le corps d'une boucle n'est pas de type
unit, le compilateur affiche un avertissement, comme pour la
séquence :
# let s = [5; 4; 3; 2; 1; 0] ;;
val s : int list = [5; 4; 3; 2; 1; 0]
# for i=0 to 5 do List.tl s done ;;
Characters 17-26:
Warning: this expression should have type unit.
- : unit = ()
Exemple : implantation de piles
La structure de données 'a pile sera implantée sous forme
d'un enregistrement contenant un tableau d'éléments et la première
position libre dans ce tableau. Voici le type correspondant :
# type 'a pile = { mutable ind:int; taille:int; mutable elts : 'a array } ;;
Le champ taille contient la taille maximale de la pile.
Les opérations sur ces piles seront init_pile pour
l'initialisation d'une pile, empile pour empiler un élément
dans une pile et depile pour retourner le sommet de pile et
le dépiler.
# let init_pile n = {ind=0; taille=n; elts =[||]} ;;
val init_pile : int -> 'a pile = <fun>
Cette fonction ne peut pas créer un tableau non vide car il faudrait lui
fournir la valeur avec lequel le construire. C'est pour cela que le
champ elts reçoit un tableau vide.
Deux exceptions sont déclarées pour gérer les tentatives
de dépilement d'une pile vide et d'ajout d'un élément sur une pile
pleine. Elles sont utilisées dans les fonctions depile et
empile.
# exception Pile_vide ;;
# exception Pile_pleine ;;
# let depile p =
if p.ind = 0 then raise Pile_vide
else (p.ind <- p.ind - 1; p.elts.(p.ind)) ;;
val depile : 'a pile -> 'a = <fun>
# let empile e p =
if p.elts = [||] then
(p.elts <- Array.create p.taille e;
p.ind <- 1)
else if p.ind >= p.taille then raise Pile_pleine
else (p.elts.(p.ind) <- e; p.ind <- p.ind + 1) ;;
val empile : 'a -> 'a pile -> unit = <fun>
Voici un petit exemple d'utilisation de cette structure :
# let p = init_pile 4 ;;
val p : '_a pile = {ind=0; taille=4; elts=[||]}
# empile 1 p ;;
- : unit = ()
# for i = 2 to 5 do empile i p done ;;
Uncaught exception: Pile_pleine
# p ;;
- : int pile = {ind=4; taille=4; elts=[|1; 2; 3; 4|]}
# depile p ;;
- : int = 4
# depile p ;;
- : int = 3
Si l'on désire éviter que l'ajout d'un élément dans une pile provoque
le déclenchement de l'exception Pile_pleine, on peut
agrandir le tableau. Pour cela le champ taille doit être
également modifiable :
# type 'a pile =
{mutable ind:int ; mutable taille:int ; mutable elts : 'a array} ;;
# let init_pile n = {ind=0; taille=max n 1; elts = [||]} ;;
# let n_empile e p =
if p.elts = [||]
then
begin
p.elts <- Array.create p.taille e;
p.ind <- 1
end
else if p.ind >= p.taille then
begin
let nt = 2 * p.taille in
let nv = Array.create nt e in
for j=0 to p.taille-1 do nv.(j) <- p.elts.(j) done ;
p.elts <- nv;
p.taille <- nt;
p.ind <- p.ind + 1
end
else
begin
p.elts.(p.ind) <- e ;
p.ind <- p.ind + 1
end ;;
val n_empile : 'a -> 'a pile -> unit = <fun>
Il faut néanmoins faire attention aux structures de données pouvant
s'agrandir à outrance. Voici un petit exemple où la pile initiale
grandit selon les besoins.
# let p = init_pile 4 ;;
val p : '_a pile = {ind=0; taille=4; elts=[||]}
# for i = 1 to 5 do n_empile i p done ;;
- : unit = ()
# p ;;
- : int pile = {ind=5; taille=8; elts=[|1; 2; 3; 4; 5; 5; 5; 5|]}
# p.taille ;;
- : int = 8
Il est d'usage d'ajouter à la fonction depile la possibilité
de diminuer la taille de la pile pour éviter d'utiliser trop d'espace
mémoire.
Exemple : calcul sur les matrices
Dans cet exemple on cherche à définir un type pour les matrices,
tableaux à deux dimensions contenant des nombres flottants, et à écrire
quelques opérations sur les matrices. Le type mat monomorphe
est un enregistrement contenant les dimensions et les éléments de la
matrice. Les fonctions creer_mat, acces_mat et
mod_mat sont respectivement les fonctions de création,
d'accès à un élément et de modification d'un élément.
# type mat = { n:int; m:int; t: float array array };;
type mat = { n: int; m: int; t: float array array }
# let creer_mat n m = { n=n; m=m; t = Array.create_matrix n m 0.0 } ;;
val creer_mat : int -> int -> mat = <fun>
# let acces_mat m i j = m.t.(i).(j) ;;
val acces_mat : mat -> int -> int -> float = <fun>
# let mod_mat m i j e = m.t.(i).(j) <- e ;;
val mod_mat : mat -> int -> int -> float -> unit = <fun>
# let a = creer_mat 3 3 ;;
val a : mat = {n=3; m=3; t=[|[|0; 0; 0|]; [|0; 0; 0|]; [|0; 0; 0|]|]}
# mod_mat a 1 1 2.0; mod_mat a 1 2 1.0; mod_mat a 2 1 1.0 ;;
- : unit = ()
# a ;;
- : mat = {n=3; m=3; t=[|[|0; 0; 0|]; [|0; 2; 1|]; [|0; 1; 0|]|]}
La somme de deux matrices a et b est une matrice c telle que
cij = aij + bij.
# let add_mat p q =
if p.n = q.n && p.m = q.m then
let r = creer_mat p.n p.m in
for i = 0 to p.n-1 do
for j = 0 to p.m-1 do
mod_mat r i j (p.t.(i).(j) +. q.t.(i).(j))
done
done ;
r
else failwith "add_mat : dimensions incompatibles";;
val add_mat : mat -> mat -> mat = <fun>
# add_mat a a ;;
- : mat = {n=3; m=3; t=[|[|0; 0; 0|]; [|0; 4; 2|]; [|0; 2; 0|]|]}
Le produit de deux matrices a et b est une matrice c telle que
cij = åk=1k=ma aik. bkj
# let mul_mat p q =
if p.m = q.n then
let r = creer_mat p.n q.m in
for i = 0 to p.n-1 do
for j = 0 to q.m-1 do
let c = ref 0.0 in
for k = 0 to p.m-1 do
c := !c +. (p.t.(i).(k) *. q.t.(k).(j))
done;
mod_mat r i j !c
done
done;
r
else failwith "mul_mat : dimensions incompatibles" ;;
val mul_mat : mat -> mat -> mat = <fun>
# mul_mat a a;;
- : mat = {n=3; m=3; t=[|[|0; 0; 0|]; [|0; 5; 2|]; [|0; 2; 1|]|]}