Manuel : Compléments

abstraction concrète


L'évaluation

"Il peut être difficile d'être vraiment paresseux."

Considérons l'association d'une expression à la valeur qu'elle représente, l'évaluation est la transformation de cette expression en la valeur exprimée. Cette transformation correspond à un enchaînement de calculs déterminés par l'application de règles de réduction, compte tenu du contexte de l'environnement. Chaque étape, ou application d'une règle, définit une nouvelle expression réduite. La syntaxe de l'expression détermine le type des calculs. Quant à l'ordre de ces calculs dans la séquence, il donne lieu à plusieurs choix possibles. Ainsi pour évaluer une application, on peut :

En ce qui le concerne, Caml est un langage à évaluation stricte. Néanmoins, l'évaluation paresseuse est mise à contribution dans certaines extensions propres à Caml-Light avec les flux ou flots de données.

L'évaluation retardée

Caml évalue les arguments d'une application avant de procéder au calcul de l'application. Or, il est, parfois, utile de retarder l'evaluation des arguments afin d'en assurer le contrôle, au niveau du programme, à la place de l'évaluateur Caml.

Pour retarder l'évaluation d'un argument de fonction dans une application, on aura recours à la règle de réduction-abstraction :
 (function x -> f(x)) E  est équivalent à  f(E/x) 
, où f(E/x) signifie que l'on remplace toutes les occurences de la variable liée x par la valeurE, dans f, par y() Dans une application h(e), l'argument e est évalué en premier.
Nous appliquons la règle d'abstraction à l'argument e et nous écrivons que :

e est équivalent à (function x -> e) x.

Ainsi nous transformons l'expression réduite de l'argument e en une application (function x -> e) x faisant intervenir un nouvel argument x.

Cette transformation a pour but de faire apparaître l'expression fonctionnelle function x -> e, qui délivrera la valeur e dans l'application (function x -> e) a. La valeur a est une valeur quelconque du type de l'argument de la fonction.

On remarque que la valeur de a n'a aucune importance. Par conséquent, on est libre de choisir la valeur () de type unit. Et dans ce cas l'expression fonctionnelle peut être définie de façon à filtrer la valeur ():unit.
Cela donne l'expression fonctionnelle function () -> e.
Et la transformation s'écrit alors :

e est équivalent à (function () -> e) ()

La fonction h = function y -> E est à son tour transformée en une nouvelle fonction h' = function y -> E(z/y) avec z = y(). L’application obtenue h’(function () -> e) est retardée. En effet, l'argument et évalué, son évaluation retourne une valeur fonctionnelle, et celle-ci ne sera utilisée que lors de son application dans les occurrences de a du corps de la fonction h'.

Les expressions de flux en Caml-Light

Dans de nombreuses circonstances, les programmes reçoivent des flots de données, appliquent des traitements à ces données et rendent les résultats correspondants, au fur et à mesure des entrées, élément par élément, selon le schéma :
Entrée de
flot de données
-->
Traitement
--> Sortie de
flot de données.
C'est le cas de programmes de traitement de fichiers (conversion de format, cryptage/décryptage, compression/décompression de données), de gestion de terminaux (lecture clavier, traitement, affichage écran), de compilateurs, d'interprétes, etc.

Les flots de données ou flux sont quelque peu semblables à des listes, avec des différences essentielles. Leurs éléments constitutifs sont les composants de flux, et les flux eux-mêmes.

Les composants du flux ne sont pas évalués lors de l'appel du flux. Au contraire, seul le composant requis est évalué, directement lors de son accès par filtrage du flux.

Syntaxe des flux

flux ::= [< >]
flux ::= [< composant_de_flux >]
flux ::= [< composant_de_flux;
... ; composant_de_flux >]

composant_de_flux ::= flux
composant_de_flux ::= 'expression

[< >] représente le flux vide.

Règle de typage de flux

E:T
---------------------
[< 'E >] : T stream

E:T stream
---------------------
[< E >] : T stream

Exemples de flux

Flux d'entiers :
#let a=[<'1;'2>];;
a : int stream = <abstr>
#let b=[<'3;'4;a>];;
b : int stream = <abstr>
Flux de caractères :
#let c=[<'`d`;'`e`;[<'`x`;'`y`>];'`u`>];;
c : char stream = <abstr>

Fonctions de flux

La fonction stream_next : ‘a stream -> a est la fonction qui retourne et évalue le prochain élément d’un flux, et après exécution de la fonction, le flux est privé de cet élément. Quand le flux est vide l’exception Parse_failure est déclenchée.

Exemples

# let a=[<'1;'2>];;
a : int stream = <abstr>
# let b=[<a;'3;'4>];;
b : int stream = <abstr>

Filtrage avec les flux

La puissance des flux est particulièrement mise en valeur par des formes de filtrage spécifiques.

Syntaxe du filtrage de flux

motif_de_flux ::= [< >]
motif_de_flux ::= [< motif_composant >]
motif_de_flux ::= [< motif_composant;
... ; motif_composant >]

motif_composant ::= identificateur_de_flux
motif_composant ::= 'motif
motif_composant ::= expression_fonctionnelle motif

Remarque importante : Il ne faut pas confondre la syntaxe du motif_composant (expression_fonctionnelle motif) avec celle d’une application. Ici, motif correspond au résultat de l’application de la fonction expression_fonctionnelle au flux courant qui n’est pas apparent dans cette forme syntaxique, mais implicite (c’est le flux objet du filtrage).

Exemples de filtrage de flux

#let c=[<'`d`;'`e`;[<'`x`;'`y`>];'`u`>];;
c : char stream = <abstr>
#let analyse = function
    [<'`y`>] -> "1. lettre y"
  | [<'`x`>] -> "2. lettre x"
  | [<'`u`>] -> "3. lettre u"
  | [<'`e`>] -> "4. lettre e"
  | [<'`d`>] -> "5. lettre d" ;;
analyse : char stream -> string = <fun>

#analyse c ;;
- : string = "5. lettre d"
#analyse c ;;
- : string = "4. lettre e"
#analyse c ;;
- : string = "2. lettre x"
#analyse c ;;
- : string = "1. lettre y"
#analyse c ;;
- : string = "3. lettre u"
#analyse c ;;
Uncaught exception: Parse_failure
#analyse [< '`z`>] ;;
Uncaught exception: Parse_failure
Lorsque le filtrage échoue l’exception "Parse_failure" est déclenchée.
# let lire = function 
      [<'1>] -> true | [< >] -> false ;;
lire : int stream -> bool = <fun>
# let filtre = function
  [< lire true >] -> "premier cas"
| [< '3;'4 >] -> "deuxième cas"
| [< >] -> "dernier cas" ;;
filtre : int stream -> string = <fun>

# let b = [<'3;'4;'1>] 
  and a = [<'1;>] ;;

#filtre b;;
- : string = "deuxième cas"
#filtre b;;
- : string = "premier cas"
#filtre b;;
- : string = "dernier cas"
#filtre a;;
- : string = "premier cas"
#filtre a;;
- : string = "dernier cas"
Dans son utilisation, le motif de flux [< >] capture tous les flux résiduels, y compris le flux vide, par conséquent le filtrage réussit toujours et aucune exception n'est déclenchée.

Les ensembles infinis

Le principe de l'évaluation paresseuse offre aussi la possibilité d'implémenter les ensembles infinis, en ayant recours, par exemple, aux flots de données.

Exemple : la fonction génératrice de la liste des entiers

Typage de la fonction entiers:
entiers : int -> int stream

Définition :
let rec entiers n = [< 'n; (entiers (n+1)) >] ;;

La valeur du paramètre n de la fonction entiers sert à initialiser la première valeur de la liste des entiers.

Construction de la liste des entiers :
let N = entiers 0 ;;

Extraction et affichage du premier entier de la liste :
stream_next N ;;
- : int = 0

Extraction et affichage de l'entier suivant de la liste :
#stream_next N ;;
- : int = 1


Les types de données mutables et la mémoire

Mémoire et environnement

On représentera la mémoire d'une machine à états par un ensemble de cellules dans lequel : Une cellule de la mémoire est modélisée par une association (référence_typée = @x, valeur = v) établie entre une référence typée notée @x et une valeur v formant une paire.
Le type de la référence d'une cellule de mémoire est déterminé par le type de la valeur qu'elle contient. Ce qui revient à écrire qu'une cellule est décrite par la paire (@xt ref, vt) où vt est la valeur du type t contenue dans la cellule, et la valeur @xt ref est la référence d'une cellule contenant une valeur de type t.

La définition d'un identificateur n associé à une référence de cellule de mémoire initialisée avec une valeur v du type t construit une liaison (n, @xt ref ) dans l'environnement courant et forme la cellule (@xt ref, vt) dans la mémoire.

Références

Définition

Dans un état initial,
environnement = Eini
mémoire = M
si on définit un identificateur id de type:t ref, la valeur liée à x dans l'environnement est une référence à une valeur de type t.
#let id = ref v ;;	
id : t ref = ref v
Il y a création d'une liaison dans laquelle l'identificateur id est associé à une référence @x qui pointe sur une adresse de la mémoire correspondant à une cellule de type t.

La cellule de la mémoire référencée par @x est initialisée avec la valeur v.
Après la définition, on a le nouvel état :
environnement : (id,@x)Eini
mémoire : (@x, v)M

Déréférencement

Dans un état initial,
environnement = (id,@x)Eini
mémoire = (@x, v)M
on recherche le contenu de la cellule référencée par l'identificateur id.
#!id;;
- : t = v
Le contexte (environnement, mémoire) reste inchangé.
environnement = (id,@x)Eini
mémoire = (@x, v)M

Affectation

Etat avant l'affectation :
environnement = (id,@x)Eini
mémoire = (@x, v)M
On effectue la modification du contenu de la cellule référencée par l'identificateur id. La nouvelle valeur u est du même type que la précédente v. La liaison (id, cellule référencée par l'identificateur id) n'est pas modifiée et par conséquent, l'environnement n'est pas modifé. Mais le contexte change, car la mémoire est modifiée.
#id := u ;;
- : unit = ()
Etat après l'affectation :
environnement = (id,@x)Eini
mémoire = (@x, u)M
L'affectation est une instruction qui change le contenu de la mémoire.

Le membre gauche et le membre droit de l'affectation sont de types différents. Ce qui signifie que, dans une affectation x := e, si e est une expression du type e:T, alors que le membre gauche n'est pas du type T, mais décrit une valeur du type référence sur une cellule mémoire contenant une valeur du type T. Le membre gauche est du type x:ref T.

Exemples

#let alpha = ref 54;;        (* définition de référence *)
alpha : int ref = ref 54
#!alpha;;                    (* déréférencement *)
- : int = 54
#alpha := 8;;                (* affectation *)
- : unit = ()
#!alpha;;                    (* déréférencement *)
- : int = 8

Champs mutables dans un enregistrement

Définition d'un enregistrement contenant des champs mutables

On définit un nouveau type enregistrement : type_enreg_id, contenant un champ mutable nommé champ1 de type t1 et un champ mutable intitulé champ2 de type t2 :
#type type_enreg_id =
  { mutable champ1 : t1 ; mutable champ2 : t2 } ;;
Type type_enreg_id defined.
On déclare un enregistrement : un_enreg, en définissant des valeurs v1 de type t1 pour champ1 et v2 de type t2 pour champ2 :
#let un_enreg =
  { champ1 = v1 ; champ2 = v2 } ;;
un_enreg : type_enreg_id = { champ1 = v1 ; champ2 = v2 }

Evaluation d'un champ d'enregistrement

Recherche du contenu d'un champ.
#un_enreg.champ1;;
- : t1 = v1
#un_enreg.champ2;;
- : t2 = v2

Affectation dans un enregistrement contenant des champs mutables

Modification du contenu d'un champ.
#un_enreg.champ1 <- u1;;
- : unit = ()
#un_enreg.champ1;;
- : t1 = v1

#un_enreg.champ2 <- u2;;
- : unit = ()
#un_enreg.champ2;;
- : t2 = v2

Exemples

#type art = { mutable mois : string ; mutable année : int } ;;
Type art defined.

#let sujet = { mois = "JANVIER" ; année = 1995 };;
sujet : art = { mois = "JANVIER" ; année = 1995 }

#sujet.mois;;
- : string = "JANVIER"
#sujet.année;;
- : int = 1995
#sujet.mois <- "MARS";;
- : unit = ()
#sujet.mois;;
- : string = "MARS"

Champs mutables dans un type somme

Le type variant, présenté ici, est une extension propre au langage Caml-Light. Et, à nouveau, nous insistons sur la précarité de leur existence et les risques liés à leur utilisation.

Définition d'un type variant

On définit un type variant : type_variant_id, contenant un champ mutable Etiq1 of t1 et un champ mutable Etiq2 of t2 :
#type type_variant_id =
  Etiq1 of mutable t1
 | Etiq2 of mutable t2 ;;
Type type_variant_id defined.
On déclare un identificateur un_variant associé à une valeur v1 du type t1 :
#let un_variant = Etiq1 v1 ;;
un_variant : type_variant_id = Etiq1 v1

Evaluation d'un variant

#un_variant;;
- : type_variant_id = Etiq1 v1

Affectation

Pour la modification de la valeur d’un variant, on procède à un filtrage de la valeur en créant une liaison avec une variable d’affectation, à partir du motif filtrant. On peut créer une fonction d’affectation, comme dans le modèle suivant, avec l’application (affecte_t1 u1 un_variant) dans laquelle :
#let affecte_t1 x = function  
  Etiq1 y -> y <- x     (* y=variable d’affectation *)
  | _ -> ();;
affecte_t1 : t1 -> type_variant_id -> unit = 
#affecte_t1 u1 un_variant ;;          (*affectation *)
- : unit = ()
#un_variant;;
- : t1 = u1

Exemples

#type nombre = 
  Entier of mutable int 
| Décimal of mutable float ;;
Type nombre defined.
(* définition d’un variant *)
#let a = Entier 5 ;;
a : nombre = Entier 5
#a ;;
- : nombre = Entier 5
(* définition de fonction d’affectation d’entier *)
#let affecte_entier x = function
    Entier y -> y <- x
  | _ -> ();;
affecte_entier : int -> nombre -> unit = 
(* affectation *)
#affecte_entier 8 a ;;
- : unit = ()
#a ;;
- : nombre = Entier 8
(* définition d’un variant *)
#let b = Décimal 0.01517 ;;
b : nombre = Décimal 0.01517
#b ;;
- : nombre = Décimal 0.01517
(* définition de fonction d’affectation de décimal *)
#let affecte_décimal x = function
    Décimal y -> y <- x
  | _ -> ();;
affecte_décimal : float -> nombre -> unit = 
(* affectation *)
#affecte_décimal 7.71802 b ;;
- : unit = ()
#b ;;
- : nombre = Décimal 7.71802

Vecteurs

Définition d'un vecteur

Soit n expressions e1 à en d'un même type : t, on déclare le vecteur m de type t vect, de n éléments v1 à vn dont les valeurs correspondent aux expressions e1 à en.
#let m = [| e1; ...; en |] ;;	
m : t vect = [| v1; ...; vn |]

Evaluation des éléments d’un vecteur

Recherche du contenu de l'élément i d'un vecteur. La position d'un élément est indicée à partir de 0 pour la première position.
#m.(i);;
- : t = vi 

Affectation

Modification du contenu d'un élément à la position i dans un vecteur. La nouvelle valeur k est du même type t que la précédente vi.
#m.(i) <- k ;;
- : unit = ()

#m.(i);;
- : t = k

La fonction make_vect

La fonction make_vect permet, à la fois, de définir et d'initialiser un vecteur.

Ainsi, l'application make_vect num val crée et initialise un nouveau vecteur de num éléments de valeur val.

#let v = make_vect 3 9 ;;	
v : int vect = [|9; 9; 9|]
Tous les éléments du vecteur créé par make_vect sont physiquement égaux à val.
#let car = ref `H` ;;	
car : char ref = ref `H`
#let v = make_vect 3 car ;;	
v : char ref vect = [|ref `H`; ref `H`; ref `H`|]
On change la valeur de car, celle des éléments de v est modifiée.
#car := `X` ;;
- : unit = ()
#v ;;
- : char ref vect = [|ref `X`; ref `X`; ref `X`|]
On change la valeur d'un élément de v.
#v.(1) <- ref `A` ;;
- : unit = ()
#v ;;
- : char ref vect = [|ref `X`; ref `A`; ref `X`|]
Mais, attention.
#v.(0):= `Z` ;;
- : unit = ()
#v ;;
- : char ref vect = [|ref `Z`; ref `A`; ref `Z`|]
#car ;;	
- : char ref = ref `Z`
On a affecté car et tous les éléments solidaires de car, en agissant sur v.(0). Par contre, v.(1) n'étant plus solidaire de car, on a :
#v.(1):= `O` ;;
- : unit = ()
#v ;;
- : char ref vect = [|ref `Z`; ref `O`; ref `Z`|]
#car ;;	
- : char ref = ref `Z`

Exemples

#let jours = [| "lundi"; "mardi"; "mercredi"; "JEUDI"; "vendredi"; "samedi"; "dimanche"; |] ;;	
jours : string vect = [| "lundi"; "mardi"; "mercredi"; "JEUDI"; "vendredi"; "samedi"; "dimanche"; |]
#jours.(0) ;;
- : string = "lundi"
#jours.(3) ;;
- : string = "JEUDI"
#jours.(3) <- "jeudi" ;;
- : unit = ()
#jours.(3) ;;
- : string = "jeudi"

Exercice 29

Comment faut-il modifier la fonction entrer_entier de l'exercice 2.7 pour éviter le passage des arguments lors de chaque appel récursif.

Solution

Les exceptions
Programmation fonctionnelle et machines à états
Les types de données mutables et la mémoire
La séquentialité

Exercice 30

Soit une session Caml dans un environnement E, typer et évaluer les phrases suivantes, et décrire l'environnement après chaque évaluation :
1. #let alpha = function a -> function b -> function c -> 
      let  rec gamma = function 
        [] -> [] 
      | x::R -> if x = a then b::(gamma R) else x::(gamma R) 
      in gamma c ;; 
2. #let delta = alpha 5 8 ;; 
3. #delta([ 1; 5; 8; 9; 5; 4; 1; 3; 5; 9; 4]) ;;  
4. #let rec omega a = function [] -> 0 
      | x::R -> (a * x) + (omega (a+1) R) ;; 
5. #let epsilon = alpha 9 1 [ 1; 5; 8; 9; 5; 8; 1; 1; 5; 9] 
      in omega 0 (alpha 8 1(delta epsilon));;
Solution

Type et valeur des expressions
Définitions et environnement
Expressions conditionnelles
Le type produit vectoriel
Fonctions

Exercice 31

Construire une fonction Caml équivalente à la fonction alpha de l'exercice 2.10, en utilisant la fonction prédéfinie map.

Solution

Fonctions
La récursivité
Le filtrage
Le type somme
Les listes

Exercice 32

A ) On souhaite traiter des k_listes dont les éléments, les kAtomes, sont construits à partir :
- des valeurs Null et Tout,
- d'entiers,
- de caractères,
- ou de k_listes.
La k_liste principale est de niveau 0.
Une k_liste quelconque définie comme élément d'une k_liste de niveau n est de niveau (n+1), et ses élément sont des éléments de niveau (n+1) de la k_liste qui la contient.
La profondeur d'une k_liste est donnée par le niveau le plus élevé de ses éléments.
1) Définir un type permettant de représenter les kAtomes en Caml.
2) Définir une fonction pour déterminer la profondeur d'une k_liste.
B ) L'application substituer k1 k2 listeK permet de remplacer chaque élément k1 de la k_liste listeK par un élément k2, quel que soit son niveau dans la liste listeK.
A partir du type kAtome défini dans l'exercice 3, écrire une définition de la fonction substituer.
C ) Etablir le module d'interface permettant d'exporter le type kAtome et la fonction substituer.

Solution

Type et valeur des expressions
Les modules
La programmation modulaire
Fonctions
La récursivité
Le filtrage
Le type somme
Les listes

Exercice 33

Si on considère que Pn(x) est un polynôme de degré n. Une manière de représenter les polynômes :
Pn(x)=anxn+...+aixi +...+a0x0
dont la syntaxe en ASCII peut être décrite par :
Pn(x)= an*x^n+...+ai*x^i +...+a0*x^0
consiste à utiliser les listes de paires (d,c) formées par le degré d = i et par le coefficient c = ai de chaque monôme M(x)= ai*x^i.
A) Ecrire une liste de paires comme représentation du polynôme :
A = 2*x^5-8*x^3+3*x^2-x-7.
B) Ecrire le polynôme B correspondant à la représentation suivante :
B = [(4,8);(0,9);(1,-5);(3,7)].
C) Construire la fonction qui détermine le degré n d'un polynôme Pn(x) donné.
D) Sachant que la dérivée d'un monôme M(x)= ai*x^i correspond à :
M'(x)= 0 quand i = 0
sinon M'(x)= i*ai*x^(i-1), quand i <> 0.
Ecrire la fonction Caml deriver_poly permettant de calculer la dérivée d'un polynôme Pn(x).
E) Ecrire une fonction de conversion de tout polynôme Pn(x) en chaîne de caractère représentant ce polynôme sous sa forme normale, c'est-à-dire comme la somme algébrique de monômes ai*x^i rangés dans l'ordre des degrés décroissants.
Solution

Le type produit vectoriel
Le filtrage
Les listes

Exercice 34

Typer et évaluer les phrases de la session Caml suivante :
1)#let a = ref (5 - 3 * 2) ;; 
2)#let b = 
	 let x = 3 and y = 4, 2 in 
	 !a + (snd y) * x, !a*x + fst y ;; 
3)#let h = function x -> function y -> ( y * (x y) ) ;; 
4)#a := h (fun x -> x + x) 5 ;; 
5)#a;;  
Solution

Type et valeur des expressions
Définitions et environnement
Le type produit vectoriel
Fonctions

Exercice 35

Définir en Caml une fonction génère_numéro qui génère automatiquement un numéro de séquence, à partir de 0.
A chaque appel de la fonction le numéro de séquence est incrémenté de la valeur du pas : 1.
syntaxe = génère_numéro ()
typage = génère_numéro : unit -> int

Solution

Les types de données mutables et la mémoire

Exercice 36

Le stock est représenté par un tableau d'articles où chaque article est décrit par un type produit composé des 3 éléments : Le code de l'article est son indice de position dans le tableau suivant,
 
#let table_articles = 
[|("Guitare", 3500, 45);
("Banjo", 2300, 18);
("Ukulele", 1800, 34);
................
("Flûte à bec", 1100, 55) |] ;;
1) Ecrire une fonction entrée_en_stock à deux arguments code et qte, qui retrouve l'article correspondant à code et ajoute qte à la quantité en stock, le résultat est la valeur de l'article modifié.
syntaxe : entrée_en_stock code qte
typage : entrée_en_stock int -> int -> int
2) Ecrire une fonction sortie_de_stock à deux arguments code et qte, qui retrouve l'article correspondant à code et retire qte à la quantité en stock si qte est inférieur ou égal à cette quantité, sinon la fonction renvoie une exception erreur_sortie_stock indiquant en message l'excédent de qte par rapport à la quantité en stock.
Le résultat est la valeur de l'article modifié.
syntaxe : sortie_de_stock code qte
typage : sortie_de_stock int -> int -> int

Solution

Type et valeur des expressions
Le type produit vectoriel
Le type somme
Le polymorphisme

Exercice 37

Dans une facture doivent figurer les informations suivantes :
- nom_client : le nom du client
- date_facture : la date de facture est représentée par un type produit composé de 3 valeurs entières : le jour, le mois, l'année
- livré : indication si la livraison a déjà été effectuée ou non
- règlement : le mode de règlement :
. si le client règle au comptant : COMPTANT suivi de la mention : Chèque ou Espèce ou Carte_bancaire
. si le client règle à crédit : CREDIT
- liste_achats : la liste des lignes d'achats effectués par le client.
Chaque ligne d'achat mentionne :
. code : le code de l'article (valeurs entières),
. quantité : la quantité achetée (valeurs entières).
Définir les types mention, mode_règlement, ligne_achat, et facture.

Solution

Le type produit vectoriel
Le type somme
Les listes


La séquentialité

Séquentialité et structure de programme

La séquence formée par deux instructions a et b exécutées successivement dans cet ordre est notée : a ; b

Dans ce qui suit, chaque instruction ai peut être une instruction élémentaire, ou une instruction complexe, c'est-à-dire une instruction formée à partir d'une liste finie d'instructions élémentaires ou complexes. Une instruction complexe, parfois appelée bloc d'instructions, est une structure de base des procédures ou sous-programmes. Un programme impératif A se présentera comme une liste finie d'instructions (a0;a1;...;ai;...;an), dans laquelle l'indice i indique l'ordre de la séquence des instructions du programme.

Programmation fonctionnelle

Les applications évaluent leurs arguments avant de les passer à la fonction. Ainsi, dans l'expression f0( f1( ...fn( expr ) ... ) ), l'expression expr sera évaluée en premier donnant la valeur v, puis ce sera le tour de l'expression f0( f1( ...fn(v) ... ) ) avec fn(v) donnant la valeur vn, et ainsi de suite jusqu'à f0( f1(v2) ), avec f1(v2) donnant v1 et en dernier f0(v1) donnant v0.

En utilisant ce principe dans le cas des instructions construites comme des fonctions du type unit -> unit, cela nous donne :
Avec l'expression f0( f1( ...fn( expr ) ... ) ), l'expression expr sera évaluée en premier donnant ( ), puis ce sera le tour de l'expression f0( f1( ...fn( ) ... ) ) avec fn( ) donnant ( ), et ainsi de suite jusqu'à f0( f1( ) ), avec f1( ) donnant ( ) et en dernier f0( ) donnant ( ). Ce qui s'exprime par la suite d'expressions :
f0( f1( ...fn( expr ) ... ) )
f0( f1( ...fn( ) ... ) )
...
f0( f1(f2( ) ) )
f0( f1( ) )
f0( )
( )

Programmation impérative

L'utilisation de l'opérateur séquentiel ";" que nous avons présenté avec l'introduction à la programmation impérative doit nous permettre de construire un programme équivalent au schéma fonctionnel précédent.
0.expr ;<=>f0( f1( ...fn-1( fn( expr )) ... ) )
1. fn( ) ;<=>f0( f1( ...fn-1( fn( )) ... ) )
2. fn-1( ) ;<=>f0( f1( ...fn-1( ) ... ) )
... .........
(n-1). f2( ) ;<=>f0( f1( f2( ) ) )
n. f1( ) ;<=>f0( f1( ) )
(n+1). f0( )<=>f0( )
En résumé nous considèrerons comme fonctionnellement équivalents :
l'application de la séquence de fonctions : f0( f1( ...fn( expr ) ... ) )
et la séquence de programme : expr; fn( ); fn-1( ); ...; f2( ); f1( ); f0( )

Les boucles d'itération

Implémentation fonctionnelle de while : WHILE

Pour la construction de la version fonctionnelle de la boucle d'itération, nous définissons la fonction WHILE :

Syntaxe de l'application de la fonction :

WHILE condition_while DO action_while DONE

L'argument condition_while est une expression fonctionnelle du type unit -> bool qui retourne une valeur booléenne, et l'argument action_while est une expression fonctionnelle de type unit -> 'a considérée comme instruction. Quant aux arguments DO et DONE ils n’ont, ici, aucune utilité fonctionnelle.

Typage de la fonction :

WHILE : (unit -> bool) -> do_while -> (unit -> 'a) -> done_while -> unit

Noter l'utilisation de l'évaluation retardée, par passage d'une fonction pour l'argument action_while et par son application dans le corps de la fonction. En effet, l'emploi d'une expression non fonctionnelle comme paramètre actuel pour l'argument action_while aurait pour résultat de retourner directement (sans effet de bord) la valeur produite par l'évaluation de l'expression, or ce résultat est ignoré par notre boucle. Tout effet de bord se produirait lors de l'évaluation de l'argument et non lors de l'exécution de la boucle.
Ici, seul l'effet de bord produit par l'instruction correspondant à l'application de la fonction action_while aura une incidence sur le changement d'état de la machine au cours de l'exécution de la boucle, le résultat de l'application de la fonction action_while est ignoré.
DO et DONE sont des valeurs du type do_while et done_while mises en place afin de se rapprocher de la syntaxe de la boucle pré-définie while de Caml.
#type do_while = DO
 and done_while = DONE ;;
Type do_while defined.
Type done_while defined.

#let WHILE =
  function condition_while ->
  function DO ->
  function action_while ->
  function DONE ->
    let rec boucle c =
      if (c ()) then (action_while () ; boucle c) 
      else () 
    in boucle condition_while ;;
WHILE : (unit -> bool) -> do_while -> (unit -> 'a) -> done_while -> unit = <fun>

Exemple de session :

#let ok = ref true ;;	(* initialisation de la condition *)
ok : bool ref = ref true
let condition = 
  function x -> 
  function () -> !x ;;		(* évaluation retardée de la condition *)
condition : 'a ref -> unit -> 'a = <fun>
let rec action = 
  function i -> 
  function () ->			(* évaluation retardée de l'action *)
    if i < 10 then begin print_string "a "; action (i+1) () end
    else ok := false ;;
action : int -> unit -> unit = <fun>

#WHILE (condition ok) DO (action 0) DONE ;;
a a a a a a a a a a - : unit = ()

Implémentation fonctionnelle de for : FOR

FOR_r : une construction récursive sans références

Pour cette construction nous définissons la fonction FOR_r:

Syntaxe de l'application de la fonction :

FOR_r debut TO fin DO action_for DONE

debut et fin sont des expressions fonctionnelles du type int. Dans ce cas, debut est la valeur initiale du compteur d'itération et fin est la valeur finale. Ici, la valeur de debut doit nécessairement être inférieure à celle de fin.
action_for est une expression fonctionnelle de type (unit -> 'a) considérée comme instruction.

Typage de la fonction :

FOR_r : int -> to_for -> int -> do_for -> (unit -> unit) -> done_for -> unit

Noter l'utilisation de l'évaluation retardée de action par passage d'une fonction comme argument dans l'application de FOR_r, pour les mêmes raisons que dans le cas de la boucle WHILE du cas précédemment étudié.
DO, DONE et TO sont des valeurs du type do_for, done_for et to_for mises en place afin de se rapprocher de la syntaxe de la boucle for pré-définie de Caml. En la circonstance, DO, DONE et TO n'ont pas d'utilité fonctionnelle significative et auraient pu être omis.
#type do_for = DO
 and done_for = DONE 
 and to_for = TO ;;
Type do_for defined.
Type done_for defined.
Type to_for defined.

#let FOR_r =
  function début ->
  function TO ->
  function fin ->
  function DO ->
  function action_for ->
  function DONE ->
    let rec boucle i =
      if i > fin then ()
      else action_for (boucle (i+1)) in
    boucle (début) ;;
FOR_r : int -> to_for -> int -> do_for -> (unit -> unit) -> done_for -> unit = <fun>

Exemple de session :

let action = function () -> print_string "a ";;

#FOR_r 1 TO 10 DO (action) DONE ;;
a a a a a a a a a a - : unit = ()

FOR_i : une construction récursive de avec références

Pour cette construction nous définissons la fonction FOR_i :

Syntaxe de l'application de la fonction :

FOR_i debut TO fin DO action_for DONE

Les spécifications de la boucle FOR_i sont identiques à celles de la boucle FOR_r. Typage de la fonction :

FOR_i : int -> to_for -> int -> do_for -> (unit -> unit) -> done_for -> unit

let FOR_i =
  function début ->
  function TO ->
  function fin ->
  function DO ->
  function action_for ->
  function DONE ->
    let i = ref début in
      let rec boucle () =
        if !i > fin then ()
        else action_for (boucle (incr i))    in
    boucle () ;;

FOR_i : int -> to_for -> int -> do_for -> (unit -> unit) -> done_for -> unit = <fun>

Exemple de session :

#FOR_i 1 TO 10 DO (action) DONE ;;
a a a a a a a a a a - : unit = ()

Retour au début du document

dernière modification : 06/12/96