Manuel : Approfondissement

abstraction concrète


La récursivité

Récursivité = voir "Récursivité".

La définition récursive précédente conduit à une lecture en boucle qui ne termine jamais. L'entrée de la définition est associée à une partie explicative qui fait référence à l'entrée de la définition...
Pour éviter, au lecteur, une quête sans fin et sans espoir, nous lui déconseillerons de lire cette première définition.

Récursivité (2ème définition) : Si la définition est comprise, inutile de lire la suite, sinon voir Récursivité (2ème définition).

Le second exemple constitue une version améliorée de la définition qui au moyen d'un contrôle permet un choix conditionnel vers soit la terminaison, soit la poursuite de la boucle.

Avec une partialité incontestable, dans notre étude, nous nous intéresserons uniquement à la seconde définition.

Définitions récursives

Les définitions récursives sont formées à partir d'expressions fonctionnelles ou d'expressions dans lesquelles les variables récursives figurent exclusivement dans des champs de données, comme dans les listes ou les enregistrements.

Syntaxe de définition récursive simple

définition_récursive ::=
let rec ident = expression

Syntaxe de définition récursive multiple

définition_récursive ::=
let rec ident_1 = expression_1
and ident_2 = expression_2
...
and ident_n = expression_n

Syntaxe de définition récursive locale

définition_récursive ::=
let rec ident = expression_1
in expression_2

Syntaxe de définition récursive locale (variante)

Par souci d'exhaustivité, signalons encore une variante avec l'extension Caml-Ligth where rec. Comme nous l'avons vu avec les définitions locales, nous rappelons que du fait de la précarité de leur existence, l'usage des extensions n'est pas conseillé.

définition_récursive ::=
expression_1
where rec ident = expression_2

Exemple d'enregistrement infini

#type enreg = {a:int; b:enreg} ;;
Type enreg defined.
#let rec u ={a=1;b=v}
and v ={a=2;b=u};;
u : enreg =
{a = 1; b = {a = 2; b = {a = 1; b = {a = 2; b = {a = 1; b = {a = 2; b = {a = 1; b = {a = 2; b = .}}}}}}}}}}}}}}}}
v : enreg =
{a = 2; b = {a = 1; b = {a = 2; b = {a = 1; b = {a = 2; b = {a = 1; b = {a = 2; b = {a = 1; b = .}}}}}}}}}}}}}}}}

Fonctions récursives

Une fonction récursive f est définie pour partie en référence à elle même. Sa définition est une structure alternative ou conditionnelle comprenant :

Modèle de définition récursive avec expression conditionnelle :

let rec f = 
   function x -> if t(x) then a(x) else k(f(g(x)))

Modèle de définition récursive avec conditionnelle par cas :


let rec f = function
    v1 -> a1(v1)
  | v2 -> a2(v2)
  ...
  | vi -> ai(vi)
  | vj -> kj(f(gj(vj)))
  ...
  | vn -> kn(f(gn(vn)))
  | x  -> k (f(g (x)))

Dans le modèle de fonction récursive utilisant l’expression conditionnelle par cas, les motifs étant parcourus successivement dans l’ordre de la définition, il est nécessaire de disposer les cas d’arrêt en premier (motifs v1 à vi, dans l’exemple). Les cas suivants correspondent aux appels récursifs de la fonction appliqués aux fonctions de convergence vers les cas d’arrêt.

Exemple 1 : Fonction factorielle forme alternative

#let rec fact = function x ->
   if x=0              (* test d'arrêt *)
      then 1           (* partie non récursive *)
      else x*fact(x-1) ;;    (* partie récursive *)
fact : int -> int = <fun>

#(fact  5 , fact  7) ;;
- : int * int = 120, 5040

Exemple 2 : Fonction factorielle forme conditionnelle par cas

#let rec fact' = function 
   0 -> 1
 | x -> x*fact'(x-1) ;;
fact' : int -> int = <fun>

#(fact' 5 , fact' 7) ;;
- : int * int = 120, 5040

Exemple 3 : Fonction de Fibonacci sous forme conditionnelle par cas

#let rec fib = function 
    0 -> 1
  | 1 -> 1
  | n -> fib(n-1)+fib(n-2) ;;
fib : int -> int = <fun>

#(fib 1, fib 3, fib 5, fib 8, fib 13) ;;
- : int * int * int * int * int = 1, 3, 8, 34, 377

Exercice

Dans les exemples donnés, fact et fib sont des fonctions partielles. Elles ne sont définies que pour des valeurs non négatives du type int. Si une valeur négative est passée en argument à l'une ou l'autre des fonctions, l'évaluation ne termine pas.
1) Donner une version fact_1 et fib_1 de fact et fib avec terminaison contrôlée de l'évaluation.
2) Donner une version fact_2 et fib_2 de fact et fib transformées en fonctions totales.

La récursivité mutuelle

Les fonctions mutuellement récursives sont définies pour partie par des références mutuelles, dans une définition récursive multiple. Chaque définition est une structure alternative ou conditionnelle comprenant :

Exemple de syntaxe de fonctions mutuellement récursives

let rec f_A = function x -> if t1(x) then a(x) else k1(f_B(g1(x)))
    and f_B = function x -> if t2(x) then b(x) else k2(f_A(g2(x)))

Exemple

# let rec pair = 
  function x -> 
    if x < 0 then pair (-x) 
    else (x=0)||(impair (x-1))
and impair = 
  function x -> 
    if x < 0 then impair (-x) 
    else (x<>0)&&(pair (x-1)) ;;
pair : int -> bool = 
impair : int -> bool = 

# impair 111 ;;
- : bool = true 
# pair 111 ;;
- : bool = false 

Exercice 14

Ecrire une fonction int_of_base, du type : int -> string -> int.
L'application(int_of_base n s) reçoit deux arguments :
- un entier n indiquant la base du nombre représenté par s
- et une chaîne de caractères s représentant un nombre en base n,
et renvoie un entier, le nombre représenté par s (en base n) converti en base 10.

Solution

Type et valeur des expressions
Expressions conditionnelles
Fonctions

Exercice 15

Ecrire une fonction base_of_int, du type : int -> int -> string.
L'application(base_of_int n x) reçoit deux arguments :
- un entier n indiquant la base du nombre à retourner par la fonction
- et un entier x correspondant à un nombre en base 10, à convertir en base n,
et renvoie une chaîne de caractères représentant le nombre x en base n.

Solution

Type et valeur des expressions
Expressions conditionnelles
Fonctions

Exercice 16

Ecrire une fonction convbase, du type : int -> int -> string -> string.
L'application(convbase b1 b2 s) reçoit 3 arguments :
- un entier b1 indiquant la base du nombre représenté par s
- un entier b2 indiquant la base du nombre à retourner par la fonction
- et une chaîne de caractères s représentant un nombre en base b1,
et renvoie une chaîne de caractères représentant le nombre s en base b2.

Solution

Type et valeur des expressions
Expressions conditionnelles
Fonctions


Le filtrage

Le filtrage par composants

Le filtrage est une construction syntaxique qui soumet une expression à un ensemble de filtres. Un filtre est une fonction partielle dans laquelle l'argument est associé à un modèle de valeur ou motif. L'expression soumise au filtrage est filtrée lorsque la valeur de cette expression correspond au motif de l'une des fonctions partielles. Alors, le filtrage rend le résultat du filtre déclenché par l'expression. Le filtrage est présenté comme une série de filtres parcourus successivement. Il se termine au premier filtre déclenché. Si aucun motif ne correspond à l'expression à filtrer, une exception Match_failure est déclenchée.

Syntaxe du filtrage par composants

filtrage ::= motif -> expression
motif ::= ident
motif ::= ( motif )
motif ::= constante_1 | ... | constante_n
motif ::= motif_1, ..., motif_n
motif ::= {etiquette_1 = motif_1;...;etiquette_n = motif_n}
motif ::= motif as ident
motif ::= _

Le filtrage est réalisé par l'utilisation d'un modèle (motif) des constituants du type de l'expression dont on veut filtrer la valeur. Les motifs sont des modèles de valeurs.

Le tiret bas "_" (underscore ou souligné) filtre toutes les valeurs qui lui sont présentées, de façon exhaustive, sans utiliser d'identificateur, donc sans établir de liaison.

Le motif alias motif_x as ident permet de filtrer toutes les valeurs qui sont filtrées par motif_x, en construisant une liaison entre la valeur filtrée et l'identificateur ident.

Remarque : un identificateur ne peut pas être utilisé de façon répétitive dans un motif.

Exemple de motifs de filtrage

Le filtrage par valeurs

Ici le filtrage doit énumérer toutes les valeurs possibles pour être exhaustif.

Syntaxe du filtrage par valeurs

filtrage ::=
valeur_1 -> expression_1
| valeur_2 -> expression_2
....
| valeur_n -> expression_n

Le filtrage par cas

Cette technique est une combinaison des deux précédentes.

Syntaxe du filtrage par cas

filtrage ::=
motif_1 -> expression_1
| motif_2 -> expression_2
....
| motif_n -> expression_n

Exemple des filtrage

L'exhaustivité

Le filtrage est exhaustif si il permet la capture de toutes les valeurs prises par l'expression qu'il doit examiner.

Le motif "_" (underscore ou souligné) capture toutes les valeurs sans création de liaison (identificateur, valeur_filtrée) : les valeurs filtrées ne sont pas récupérées.

L'utilisation d'un identificateur dans un motif permet de capturer toutes les valeurs avec création d'une liaison (identificateur, valeur_filtrée) : l'identificateur du motif (partie gauche du filtre) peut alors intervenir dans l'expression de la partie droite du filtre avec sa valeur_filtrée associée.

La non exhaustivité peut être intentionnelle, de la part du programmeur qui doit, alors, en contrôler les effets.

La redondance

Le filtrage est redondant si certains filtres à partir du filtre i et suivants ne peuvent jamais être atteints. Ceci se produit quand les filtres précédant le filtre i aboutissent à un filtrage exhaustif.

La redondance est inutile et c'est un indice de mauvaise conception.

La redondance et la non exhaustivité sont détectées et signalées lors de la compilation.

Les gardes

Certains langages tels que Miranda et Caml offrent la possibilité de définir des fonctions filtrantes à partir d'expressions conditionnelles (les gardes).

Première approche de l'implémentation de gardes en Caml

La première approche propose la syntaxe suivante, dans laquelle les mots "vaut", "quand", "autres", sont des fonctions créées pour la mise en forme syntaxique :

filtrage_par_gardes ::= vaut
(expression_1) quand (condition_1)
...
(expression_i) quand (condition_i)
...
(expression_n) quand (condition_n)
(expression_résiduelle) autres cas ;;

Implémentation

#let vaut = function x -> function q -> q x
and alterne =
  function x -> function c1 -> function q -> function c2 ->
  q x (c1 or c2) ;;
vaut : 'a -> ('a -> 'b) -> 'b = 
alterne : 'a -> bool -> ('a -> bool -> 'b) -> bool -> 'b = 

let quand = function x -> function c -> function y ->
    if c then alterne x c else alterne y c
and autres x y = x and cas = true ;;
quand : 'a -> bool -> 'a -> ('a -> bool -> 'b) -> bool -> 'b = 
autres : 'a -> 'b -> 'a = 
cas : bool = true

Exemples

(* PREMIER EXEMPLE *)
#let g x y = vaut
  0 		quand (x<0)
  y 		quand (x=0)
  (x+1)	quand (y=0)
  x		autres cas ;;
g : int -> int -> int = 
Expression Typage et évaluation
#g (-5) 12;; - : int = 0
#g 9 (-3);; - : int = 9
#g 0 12;; - : int = 12
#g 9 0;; - : int = 10
#g 9 12;; - : int = 9

(* DEUXIEME EXEMPLE *)
#let g x y = vaut
  (y/x)	quand (x<0)
  1		quand (x=0)
  2		quand (y=0)
  (x/y)	autres cas ;;
g : int -> int -> int = 
Expression Typage et évaluation
#g (-5) 12;; - : int = -2
#g (-3) 12;; - : int = -4
#g 0 12;; Uncaught exception: Division_by_zero
#g 9 12;; - : int = 0
#g 9 0;; Uncaught exception: Division_by_zero

Tous les cas sont évalués même quand il n'y a pas lieu de les évaluer, ce qui conduit à la non terminaison du programme dans le cas de la division par zéro.

Deuxième approche de l'implémentation de gardes en Caml (évaluation retardée)

Les valeurs à filtrer, à gauche du quand, sont passées à la fonction de filtrage, dans le corps d’expressions fonctionnelles du type unit -> ‘a. Celles-ci sont évaluées par la fonction, et cette dernière retourne le cas filtré par la condition satisfaite. Pour finir, l’application de la fonction de filtrage à l’arument () donne le résulat attendu, dont l’évaluation a été retardée jusqu’ici.
filtrage_par_gardes ::= (vaut
(expr_fonctionnelle_1) quand (condition_1)
...
(expr_fonctionnelle_i) quand (condition_i)
...
(expr_fonctionnelle_n) quand (condition_n)
(expr_fonctionnelle_résiduelle) autres cas) () ;;

Implémentation

Identique à celle de la première approche.

Exemples

#let f x = ( vaut
  (fun () -> x*x		quand (x<0)
  (fun () -> 1		quand (x=0)
  (fun () -> 1		quand (x=1)
  (fun () -> 100/x	autres cas  ) () ;;
f : int -> int = 
Expression Typage et évaluation
#f (-5);; - : int = 25
#f 0;; - : int = 1
#f 1;; - : int = 1
#f 5;; - : int = 20

Seul le cas pour lequel la condition est satisfaite, est évalué. Mais, par contre, un risque de non terminaison subsiste, lié aux expressions des gardes qui sont toutes évaluées. De plus, la syntaxe des expressions fonctionnelles de chacun des cas nuit beaucoup à la clarté et à la simplicité du programme.

Troisième approche de l'implémentation de gardes en Caml (évaluation paresseuse)

Ici nous avons recours à l'évaluation paresseuse par utilisation des flots de données.

filtrage_par_gardes ::= vaut
[< expression_1 >] quand (condition_1)
...
[< expression_i >] quand (condition_i)
...
[< expression_n >] quand (condition_n)
[< expression_n_résiduelle >] autres cas ;;

Implémentation

L'implémentation est identique à celles de la première et de la deuxième approches, mis à part une seule fonction à modifier, la fonction autres :

let autres x y = stream_next x ;;
autres : 'a stream -> 'b -> 'a =

Exemples

#let f x y = vaut
  [< '1 >]		quand (x=0)
  [< '1 >]		quand (y=0)
  [< '(y*y/x) >]	quand (y<0)
  [<'(x*x/y) >]	autres cas ;;
f : int -> int -> int = 
Expression Typage et évaluation
#f (-5) (-8) ;; - : int = -12
#f (0) (-8) ;; - : int = 1
#f (-5) (0) ;; - : int = 1
#f (10) (-8) ;; - : int = 6
#f (-5) (10) ;; - : int = 2
#f (0) (0) ;; - : int = 1
#f (11) (12) ;; - : int = 10

Les gardes en Caml

Dans les extensions de langage de la version 0.7 de Caml-Light, les gardes sont introduites avec la syntaxe suivante :

Syntaxe du filtrage gardé

filtrage_par_gardes ::=
garde_1 -> expr_1
...
garde_n -> expr_n

garde := motif
garde := motif when condition

Exemples

#let teste x y = match (x+y) with
0 -> [0;x;y;1;0]
|s when x = 0 -> [1;x;y;1;s]
|s when y = 0 -> [2;x;y;1;s]
|s when s < 0 -> [3;x;y;(x*y)/(y*x);s]
|s -> [4;x;y;(x*y)/(y*x);s] ;;
teste : int -> int -> int list = <fun>
#teste 0 0;;
- : int list = [0; 0; 0; 1; 0]
#teste 0 5;;
- : int list = [1; 0; 5; 1; 5]
#teste 9 0;;
- : int list = [2; 9; 0; 1; 9]
#teste (-3) 1;;
- : int list = [3; -3; 1; 1; -2]
#teste 9 5;;
- : int list = [4; 9; 5; 1; 14]

Remarque :

Le filtrage n'est pas une expression. C'est un constituant de fonction ou de conditionnelle par cas.

La conditionnelle par cas

Syntaxe de la conditionnelle par cas

expression_conditionnelle ::=
match expression with
filtrage

Règle de typage d'une conditionnelle par cas

E:T M1:T...Mn:T E1:T'...En:T'
-----------------------------------------
(match E with M1 -> E1| ... |Mn -> En):T'

Exemples

#let cas x = match x with
  0 -> "ZERO"
| 1 -> "UN"
| _ -> "PLUSIEURS" ;;
cas : int -> string = 

#cas 0, cas 1, cas 2;;
- : string * string * string = "ZERO", "UN", "PLUSIEURS"

Le filtrage et la définition de fonctions

Syntaxe de fonction définie par filtrage

expression_conditionnelle ::=
function filtrage

Règle de typage de fonction définie par filtrage

E:T M1:T...Mn:T E1:T'...En:T'
------------------------------------------
(function M1 -> E1| ... |Mn -> En):T -> T'

Exemples

#let string_of_bool = function 
  true -> "true"
| _ -> "false" ;;
string_of_bool : bool -> string = 

#string_of_bool true, string_of_bool false;;
- : string * string = "true", "false"

Exercice 17

Au cours d'une autre session Caml, examiner la définition suivante, et indiquer si le filtrage est exhaustif,
1. # let rec h = function 
		(5,_) -> 0 
	|	(_,5) -> 1 
	|	(x,9) -> x 
	|	(x,y) -> y ;; 
Dans la suite de la même session indiquer le type et la valeur des expressions :
2. # h(5,5), h(0,5), h(5,9), h(9,5) ;; 
3. # h(9,4), h(4,9), h(11,9), h(7,8) ;; 
4. # h(h(5,9),h(9,9)), h(h(9,7),h(5,9)) ;;  
Solution

Fonctions
Le filtrage

Exercice 18

Soit une session Caml dans un environnement E, évaluer les phrases suivantes :
1. # let a = 80;; 
2. # let b = a + 20;; 
3. # let a = b + 50 in a + a * 3 ;; 
4. # let a = let b = 50 in a + b * 3 
     and b = let b = 50 in let a = 20 in a + b * 3 ;; 
5. # let c = 8 in c * c + a + b;; 
Décrire l'environnement après chaque évaluation. Quelles sont les valeurs associées aux identificateurs a, b et c après la dernière définition ?
Solution

Type et valeur des expressions
Définitions et environnement

Exercice 19

Typer et évaluer les phrases Caml suivantes :
1. # (17 + 4*7) <= (58 - 3*12) ;; 
2. # ("a" ^ "b"), (5+2) = 7, 0 ;; 
3. # function x -> (4 < x) = ("a" = "b") ;; 
4. # ("a" + 5) = ("a" + 5) ;; 
5. # (function x -> snd(x)), (function x -> fst(x)) ;; 
6. # let f = function (x,y) -> y*y ;; 
7. # let g = function (a,b,u) -> u(b,a) ;; 
8. # g (0,5,f) ;; 
9. # function _ -> 0 ;; 
10.# function x -> (function f -> f(x)) ;; 

Solution

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

Exercice 20

En utilisant les fonctions pré-définies string_length et sub_string, construire les fonctions suivantes :

hd_str : string -> string
hd_str s renvoie la chaîne formée par le premier caractère de la chaîne s fournie en argument, si s est la chaîne vide, le résultat est la chaîne vide.

tl_str : string -> string
tl_str renvoie la chaîne formée par tous les caractères de la chaîne s fournie en argument, sauf le premier. Si la chaîne fournie en argument est vide, le résultat est la chaîne vide.

A partir des fonctions hd_str et tl_str imaginer une fonction renverse :
renverse s : string -> string
renverse s renvoie la chaîne s fournie en argument, renversée.
Par exemple, renverse "abcd" renvoie "dcba".

En utilisant la fonction renverse définir la fonction est_palindrome :
est_palindrome : string -> bool
est_palindrome s renvoie true si la chaîne s fournie en argument est un palindrome, false sinon.

Solution

Fonctions
La récursivité
Le filtrage
Le type somme


D'autres types

Synonymes de types

La définition de types synonymes attribue de nouveaux noms à des expressions de type. De cette manière, le programmeur a la liberté d'exprimer des types existants en utilisant des identificateurs plus évocateurs par rapport au contexte. Un synonyme de type est substituable à l'expression de type avec laquelle il a été défini, et réciproquement. Intuitivement, on peut considérer que toutes les fonctions et tous les opérateurs définis pour une expression de type sont définis pour les types synonymes de cette expression.

Syntaxe d'une définition de types synonymes

définition_type_synonyme ::=
type nom_type == expression_type

Exemples

#type entier == int and décimal == float ;;
Type entier defined.
Type décimal defined.
#type rationnel == int * int ;;
Type rationnel defined.
Dans notre exemple, le type entier (resp. décimal et resp. rationnel) est synonyme du type int (resp. float et resp. int * int). Il ne s'agit pas d'un nouveau type.

Types somme

Le type somme généralise le cas particulier du type construit que nous avons déjà rencontré. C’est un regroupement de formes alternatives de valeurs construites représentées par des constructeurs de valeurs différents éventuellement associés à des expressions de type.

Syntaxe de définition de type somme

définition_type_somme ::=
type nom_type =
déf_constructeur_1
| déf_constructeur_2
....
| déf_constructeur_n

déf_constructeur ::= identificateur
déf_constructeur ::= identificateur of expression_type

Exemples

#type nombre =
    Entier of int
  | Decimal of float
  | Rationnel of int * int ;;
Type nombre defined.
#Entier 45 ;;
- : nombre = Entier 45
#Decimal 3.0017 ;;
- : nombre = Decimal 3.0017
#Rationnel(5,8) ;;
- : nombre = Rationnel (5, 8)
Dans notre exemple, le type nombre est un nouveau type entièrement différent des types int et float. Ici, Entier, Decimal et Rationnel sont des constructeurs de valeurs. Pour illustrer l'application de la technique du filtrage au type somme, définissons un nouveau type somme ensemble_de_nombres et une fonction nommée ensemble, du type nombre -> ensemble_de_nombres, qui détermine l'ensemble auquel appartient le nombre décrit par la valeur de type nombre :
#type ensemble_de_nombres = ENTIER | DECIMAL | RATIONNEL ;;
Type ensemble_de_nombres defined.
#let ensemble = function
    Entier n -> ENTIER
  | Decimal d -> DECIMAL
  | Rationnel n -> RATIONNEL ;;
ensemble : nombre -> ensemble_de_nombres = <fun>
#ensemble (Entier 8) ;;
- : ensemble_de_nombres = ENTIER
#ensemble (Rationnel(13,71)) ;;
- : ensemble_de_nombres = RATIONNEL
#ensemble (Decimal (-1.085)) ;;
- : ensemble_de_nombres = DECIMAL

Types énumérés

Syntaxe d'une définition de type énuméré

Il s'agit d'un type somme dont les différents cas sont uniquement formés d'un constructeur de valeur, sans expression de type associée au constructeur. Le type ensemble_de_nombres de l'exemple précédent est un exemple de type énuméré.

définition_type_énuméré ::=
type nom_type =
constructeur_de_valeur_1
| constructeur_de_valeur_2
...
| constructeur_de_valeur_n

Exemples

#type couleur = violet | rouge | orange| jaune | vert  | bleu | indigo
 and planete =
        Mercure | Venus | Terre | Mars | Jupiter
         | Saturne | Uranus | Neptune | Pluton
 and direction = Nord | Sud | Est | Ouest ;;
Type couleur defined.
Type planete defined.
Type direction defined.
#bleu, Saturne, Est ;;
- : couleur * planete * direction = bleu, Saturne, Est

#type jour =
  lundi | mardi | mercredi | jeudi | vendredi | samedi | dimanche
 and mois =
     janvier | février | mars | avril | mai | juin
   | juillet | août | septembre | octobre | novembre | décembre ;;
Type jour defined.
Type mois defined.
#let date = mercredi, 23, décembre, 1994 ;;
date : jour * int * mois * int = mercredi, 23, décembre, 1994

Conversion de types

La contrainte de travailler avec diverses représentations informatiques d'un même objet fait naître la nécessité de réaliser le passage d'une de ces représentations à une autre. C'est le cas, lorsque l'on souhaite transformer la représentation numérique d'un nombre résultant d'un calcul en une représentation sous forme de chaîne de caractères afin d'intégrer ce résultat dans un texte. Dans le langage Caml, plusieurs fonctions pré-définies de la bibliothèque de base répondent pour une part à ce problème :

Fonctions de conversion pré-définies

Conversions entre un type numérique et un type chaîne de caractères
conversion du type int vers le type string : string_of_int : int -> string
conversion du type string vers le type int : int_of_string : string -> int
conversion du type float vers le type string : string_of_float : float -> string
conversion du type string vers le type float : float_of_string : string -> float
Conversions entre types numériques
conversion du type int vers le type float : float_of_int : int -> float
conversion du type float vers le type int : int_of_float : float -> int
Conversion entre un type numérique et un type caractère
conversion du type int vers le type char : char_of_int : int -> char
conversion du type char vers le type int : int_of_char : char -> int

Types récursifs

Le type récursif est formé à partir d'un type somme et en référence à lui-même.

Exemple de définition de type récursif direct :

# type arbre_d'entiers = 
    Feuille of int 
  | Fourche of arbre_d'entiers * arbre_d'entiers ;;
Type arbre_d'entiers defined.

# let a = Feuille(4) ;;
a : arbre_d'entiers = Feuille 4
# Fourche(Feuille(1),a) ;;
- : arbre_d'entiers = Fourche (Feuille 1, Feuille 4)

Exemple de définition de types récursifs mutuels :

# type arbre_1= 
    Feuille_1 of int 
  | Fourche_1 of arbre_2 * arbre_2 
  and arbre_2 = 
    Feuille_2 of char 
  | Fourche_2 of arbre_1 * arbre_1 ;;
Type arbre_1 defined.
Type arbre_2 defined.

# let a = Feuille_1(1) and b = Feuille_1(3) 
  in Fourche_1(Feuille_2(`+`),Fourche_2(a,b)) ;;
- : arbre_1 = 
        Fourche_1 ( Feuille_2 `+`, 
                    Fourche_2 (Feuille_1 1, Feuille_1 3))

Construction des listes à partir d'un type somme récursif et d'une paire (type produit)

Une liste est une suite de 0 à n éléments du même type. Une liste de 0 élément est une liste vide. Toute liste non vide peut être considérée comme une liste constituée par un premier élément et d'une liste restante contenant les éléments résiduels sauf le premier. Sur ces bases, on définit un type somme récursif :
#type 'a liste = Fin | Suite of 'a * 'a liste ;;
Type liste defined.

Définition d'une liste vide :

On définit un type liste vide à partir d'un type construit à une valeur.

#let liste_nulle = Fin ;;
liste_nulle : 'a liste = Fin

Construction d'une liste :

On construit une liste à partir d'un premier élément et d'un reste de liste.

#let liste_a = Suite(10, liste_nulle) ;;
liste_a : int liste = Suite (10, Fin)
#let liste_b = Suite(20, liste_a) ;;
liste_b : int liste = Suite (20, Suite (10, Fin))

Définition d'une fonction de construction de liste à partir d'un élément et d'un reste de liste :

#let construire_liste e R = Suite(e, R) ;;
construire_liste : 'a -> 'a liste -> 'a liste = <fun>
#construire_liste 30 liste_b ;;
- : int liste = Suite (30, Suite (20, Suite (10, Fin)))

Définition d'une fonction tête de liste, qui retourne le premier élément d'une liste, s'il existe :

#let tête_liste = function
    Suite(e, _) -> e
  | Fin -> failwith "tête_liste" ;;
tête_liste : 'a liste -> 'a = <fun>
#tête_liste liste_b ;;
- : int = 20

Définition d'une fonction reste de liste, qui retourne une liste privée de son premier élément :

#let reste_liste = function Suite(_, R) -> R | Fin -> failwith "reste_liste" ;; reste_liste : 'a liste -> 'a liste = <fun> #reste_liste liste_b ;; - : int liste = Suite (10, Fin)

Exercice 21

Dans un programme Caml on définit un type nombre qui regroupe des valeurs entières, réelles et complexes (les nombres complexes seront représentés comme des couples de nombres réels).
a) Construire une définition du type nombre.
b) Définir une fonction carré à un arguments, permettant de calculer le carré du nombre fourni en argument avec le type nombre :
syntaxe = carré x
typage = carré : nombre -> nombre
Règles de calcul appliquées : (les expressions suivantes ne sont pas des expressions Caml)
R1 : Le carré d'un entier m est un entier = m2
R2 : Le carré d'un réel x est un réel = x2
R3 : Le carré d'un complexe (a,b) est un complexe = (a2-b2, 2ab)

Solution

Fonctions
Le filtrage


Les listes (version prédéfinie)

Construction des listes

Le symbole «::» est le constructeur de liste, cons (prononcer "konce"). Il est associatif à droite.
L'expression x::R représente une liste dont x est le premier élément et R le reste de la liste.
Les crochets droits «[]» réprésentent une liste vide (0 élément), et une liste quelconque de n éléments ei sera notée comme une chaîne d'éléments associés par le constructeur de liste et terminée par la liste vide : e1:: e2:: ... ei:: ... en:: [].

Syntaxe de liste

une_liste ::= []
une_liste ::= expression :: une_liste

Règle de typage d'une liste

E:T R:T list
---------------
(E::R):T list

Représentation des listes en extension

Une liste peut être décrite par une série d'éléments entre crochets.
La notation [expression_1; ...; expression_n] décrit la liste formée par la suite des expressions expression_1 à expression_n.

Exemple de construction d'une liste par étapes :

   1::2::3::4::5::[ ] 
=> 1::2::3::4::[ 5 ] 
=> 1::2::3::[ 4; 5 ]
=> 1::2::[ 3; 4; 5 ] 
=> 1::[ 2; 3; 4; 5 ] 
=> [ 1; 2; 3; 4; 5 ]
Toutes ces listes sont équivalentes.

Concaténation des listes

Le symbole «[]», nommé append, est l'opérateur de concaténation des listes (append)

L'expression de la concaténation de deux listes L1 et L2 s'écrit L1 @ L2. Il s'agit d'une nouvelle liste formée par L1 placée en tête de L2.
Rappelons que tous les éléments d'une liste sont du même type. Par exemple, si L1 = [1] et si L2 = [true] alors la concaténation de L1 et L2 n'est pas possible.

Exemples

# let L1 = [1] and L2 = [4] in L1@L2 ;;
- : int list = [1; 4]
mais, si L1 et L2 ne sont pas du même type :
# let L1 = [1] and L2 = [true] in L1@L2 ;;
Toplevel input:
>let L1 = [1] and L2 = [true] in L1@L2 ;;
>                                   ^^
This expression has type bool list,
but is used with type int list.

Quelques exemples de listes

liste vide : [ ]
liste contenant au moins un élément : x::R
liste contenant au moins deux éléments : x::y::R
liste contenant un seul élément : x::[ ]
liste contenant un seul élément : [ x ]
liste d'entiers à 4 éléments : [ 1; 2; 9; 452 ]
liste de 3 chaînes formée par
concaténation de deux listes de chaînes :
[ "abc"]@[ "def"; "hij" ]

Exemple de liste circulaire

Dans le paragraphe concernant la récursivité, nous avons vu un exemple de définition récursive, les enregistrements infinis. Voici un autre exemple de définition récursive, les listes circulaires.

#let rec liste_circulaire =
0::1::2::3::4::5::6::7::8::9::liste_circulaire ;;
liste_circulaire : int list =
[0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0; 1; 2; 3; 4; 5; 6; 7; 8; ...]

Quelques fonctions de listes pré-définies

  • La fonction tête de liste hd : 'a list -> 'a. Appliquée à une liste x::R la fonction hd retourne la valeur de l'élément x. Appliquée à une liste vide la fonction hd déclenche l’exception Failure "hd"
    #hd [3;2;1;0];;
    - : int = 3
    #hd [];;
    Uncaught exception: Failure "hd"
    
  • La fonction reste de liste tl : 'a list -> 'a list. Appliquée à une liste x::R la fonction tl retourne la valeur de la liste R. Appliquée à une liste vide la fonction tl déclenche l’exception Failure "tl"
    #tl [3;2;1;0];;
    - : int list = [2;1;0]
    #tl [];;
    Uncaught exception: Failure "tl"
    
  • La fonction membre de liste mem : 'a -> 'a list -> bool. Appliquée à un élément x et à une liste L la fonction mem retourne true si l'élément x est membre de la liste L.
    #mem 7 [3;2;1;0];;
    - : bool = false
    #mem 2 [3;2;1;0];;
    - : bool = true
    
  • La fonction vectorielle map : ('a -> 'b) -> 'a list -> 'b list. L'application map f L retourne la liste des résultats de l'application de la fonction f aux éléments successifs de la liste L.
    #map (fun x -> x+5) [3;2;1;0];;
    - : int list = [8; 7; 6; 5]
    #map (fun x -> x+5) [];;
    - : int list = []
    
  • La fonction do_list : ('a -> 'b) -> 'a list -> unit. L'application do_list f L applique successivement la fonction f aux éléments successifs de la liste L. Les résultats sont ignorés. La fonction retourne la valeur ().
    #do_list print_int [34;27;51;9];;
    3427519- : unit = ()
    
  • La fonction prédicat exists : ('a -> bool) -> 'a list -> bool. L'application exists f L retourne la valeur de vérité de la disjonction des résultats de l'application de la fonction prédicat f aux éléments successifs de la liste L.
    #exists (fun x -> x=5) [3;2;1;0];;
    - : bool = false
    #exists (fun x -> x=5) [3;2;1;0;5;8];;
    - : bool = true
    
  • La fonction prédicat for_all : ('a -> bool) -> 'a list -> bool. L'application for_all f L retourne la valeur de vérité de la conjonction des résultats de l'application de la fonction prédicat f aux éléments successifs de la liste L.
    #for_all (fun x -> x<5) [3;2;1;0];;
    - : bool = true
    #for_all (fun x -> x<5) [3;2;1;0;4;8];;
    - : bool = false
    

    Exercice 22

    Un centre de formation propose des formations donnant lieu à des stages :
    une formation est représentée par une paire dont le premier élément est son numéro de code formation (entier) et son deuxième élément, un enregistrement défini par :
    - un intitulé de la formation (libellé de 25 caractères),
    - un nombre de séances de formation,
    - un niveau de progression, représenté par un littéral : Initiation ou Perfectionnement,
    - le nombre maximum de stagiaires et
    - le tarif de formation (nombre réel).
    1) Définir les types de données niveau_de_progression et formation.
    2) La journée de travail est découpée en deux sessions : la session du matin et la session de l'après-midi.
    Chaque séance de stage mobilise une session complète, soit le matin, soit l'après-midi.
    La session est simplement représentée par un littéral : MATIN ou APRES_MIDI.
    Une séance de stage est définie par :
    la date de la séance, la session, le code de la salle de formation affectée à la séance (les salles ont un code formé par la lettre correspondant au batiment A ou B, suivie d'un simple numéro de salle).
    Un stage correspondant à une formation programmée dans un calendrier, il est défini par :
    - le code du stage : numéro du stage dans l'année, - le code de la formation correspondante, - le nom du formateur (libellé de 25 caractères) et - la liste des séances.
    Donner une définition des types de données date, code_salle, session_type et séance :

    Solution

    Le type produit vectoriel
    Le type somme
    Les listes

    Exercice 23

    On considère les éléments d'un ensemble fini A comme étant les ceux d'une liste CAML.
    Ecrire une fonction parties qui retourne une liste correspondant à l'ensemble P(A) des parties de A.

    syntaxe = parties liste
    typage = parties : 'a list -> 'a list list

    exemple :
    #parties [1; 2; 3; 4] ;;
    - : int list list = [[1; 2; 3; 4]; [1; 2; 3]; [1; 2; 4]; [1; 2]; [1; 3; 4]; [1; 3]; [1; 4]; [1]; [2; 3; 4]; [2; 3]; [2; 4]; [2]; [3; 4]; [3]; [4]; []]

    Solution

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

    Exercice 24

    On considère les éléments d'un ensemble fini A comme étant les ceux d'une liste CAML.
    Ecrire une fonction lister_sous_liste qui retourne toutes les listes de n éléments extraites d'une liste donnée, au sens des ensembles, c'est-à-dire que deux listes contenant les mêmes éléments placés dans un ordre différent sont identiques.

    syntaxe = lister_sous_liste nombre liste
    typage = lister_sous_liste : int -> 'a list -> 'a list list

    exemple :
    #liste_sous_liste 2 [1; 2; 3; 4] ;;
    - : int list list = [[4; 3]; [3; 2]; [4; 2]; [2; 1]; [3; 1]; [4; 1]]

    Solution

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

    Exercice 25

    On considère les éléments d'un ensemble fini A comme étant ceux d'une liste CAML.
    Ecrire une fonction permuter qui retourne une liste de toutes les permutations d'une liste donnée.
    syntaxe : permuter liste
    typage : permuter : 'a list -> 'a list list

    exemple :
    #permuter [1; 2; 3] ;;
    - : int list list = [[1; 2; 3]; [1; 3; 2]; [2; 1; 3]; [2; 3; 1]; [3; 2; 1]; [3; 1; 2]]

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


    Transformation de fonctions

    Equivalence d'une fonction à plusieurs arguments avec une fonction à un argument

    L' opérateur fonctionnel -> est associatif à droite.
    Par application de la règle d'associativité à droite de l' opérateur fonctionnel "->" l'expression fonctionnelle
    function v1 -> function v2 ->...function vn -> corps_f
    est équivalente à :
    function v1 -> (function v2 ->...(function vn -> corps_f)...)
    En posant A = (function v2 ->...(function vn -> corps_f)...) et x = v1, l'expression fonctionnelle initiale se réécrit sous la forme d'une fonction à un argument : function x -> A
    En conclusion, une fonction à plusieurs arguments peut être réécrite comme une fonction à un argument.

    Transformation de fonctions à plusieurs variables

    (Cf. Références [1], pages 120-121)

    Curryfication

    Transformation d'une fonction à plusieurs variables représentée par une fonction à un argument de type produit cartésien en fonction à plusieurs arguments.

    Curryfication
    
    # let curry = 
            function f -> 
              function x -> 
                function y -> f(x,y);;
    curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c = <fun>
    

    Exemple

    #let module (a,b) = a*a + b*b ;;
    module : int * int -> int = <fun>
    #module(3,4) ;;
    - : int = 25
    #let module' = curry module ;;
    module' : int -> int -> int = <fun>
    #module' 3 4 ;;
    - : int = 25
    

    Décurryfication

    Transformation d'une fonction à plusieurs variables représentée par une fonction à plusieurs arguments en fonction à un argument de type produit cartésien.
    Décurryfication
    
    # let uncurry = 
            function f -> 
              function (x,y) -> f x y ;;
    uncurry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c = <fun>
    

    Exemple

    #let ecart a b = a*a - b*b ;;
    ecart : int -> int -> int = <fun>
    #ecart 3 4 ;;
    - : int = -7
    #let ecart' = uncurry ecart ;;
    ecart' : int * int -> int = <fun>
    #ecart' (3,4) ;;
    - : int = -7
    

    Règles de transformation des fonctions

    Issues du lambda-calcul et des nombreuses études développées sur les langages fonctionnels, les conversions, ci-dessous, peuvent être employées pour réaliser des substitutions par équivalence dans les transformations des expressions fonctionnelles.

    Règle de conversion alpha : règle d'interchangeabilité du nom de la variable liée

    La première règle de conversion établit que le choix de l'identificateur de la variable liée (paramètre formel) de la fonction est indifférent, et par conséquent, il est permis de lui substituer n'importe quel autre identificateur, à condition d'éviter d'utiliser celui d'une variable libre du corps de la fonction.

    Règle de conversion alpha
    
    function x -> f(x)  est équivalent-alpha à  function y -> f(y)
    

    Exemple :

    function s -> 2 * s + 4 est équivalent- à function t -> 2 * t + 4
    mais, function x -> 2 * x + y n'est pas équivalent à function y -> 2 * y + y,
    en effet, lors du changement de nom de la variable liée, une ambiguïté apparaît, elle est confondue avec la variable libre y.

    Règle de conversion béta : règle de réduction - abstraction

    La deuxième règle de conversion établit que dans une application, il est permis de substituer la valeur du paramètre effectif à toutes les occurrences du paramètre formel (variable liée) de la fonction, il s'agit alors d'une réduction béta ou instanciation. La conversion inverse, qui consiste à réintroduire une variable liée dans une expression et à extraire et faire réapparaître un paramètre effectif, est une abstraction béta ou généralisation. La notation E/x signifie la substitution de E à la variable x dans le corps de la fonction. Ce qui induit la condition de typage (x:T E:T)

    Règle de conversion béta
    
    (function x -> f(x)) E  est équivalent-béta à  f(E/x)
    

    Exemple :

    (function x -> 2 * x + 4) 7 est équivalent- à à 2 * 7 + 4

    Règle de conversion éta : règle d'extensionnalité

    La troisième règle de conversion autorise simplement à substituer l'identificateur de la fonction à l'expression qui associe fonctionnellement cet identificateur à une variable liée (paramètre formel), et réciproquement. A condition que f soit une fonction, on peut écrire :

    Règle de conversion éta
    
    function x -> f(x)  est équivalent-éta à  f
    

    Exemple :

    function r -> cube r est équivalent- à à cube



    Les exceptions

    Définition d'une exception

    Le dispositif des exceptions en Caml est un mécanisme de contrôle de l'évaluation. Lorsqu'une exception est déclenchée, dans une expression Caml, elle provoque un arrêt de l'évaluation de cette expression. Avant toute utilisation une exception doit faire l'objet d'une définition. Les exceptions ont le type : exn. Dans un programme, le programmeur peut gérer la récupération des exceptions éventuellement déclenchées afin de contrôler la production des résultats.

    Syntaxe de définition d'exception

    decl_exception ::= exception déf_constructeur
    and ... and déf_constructeur

    déf_constructeur ::= constructeur
    déf_constructeur ::= constructeur of expression_type

    Règle de typage d'une exception

    E:exn

    Exemples

    #exception division_par_0
     and fin_de_programme
     and erreur of int ;;
    Exception division_par_0 defined.
    Exception fin_de_programme defined.
    Exception erreur defined.
    

    Déclenchement d'une exception

    Dans le but de contrôler l'évaluation des expressions, le programme peut déclencher une exception par utilisation de la fonction pré-définie raise : exn -> 'a. Lorsqu'une exception est déclenchée l'évaluation de l'expression est arrêtée et l'exception est propagée. Une valeur exceptionnelle est une valeur formée par le nom d'une exception complétée ou non, selon le cas, par une valeur associée.

    Syntaxe de déclenchement d'exception

    déclenchement_exception ::=
    raise valeur_exceptionnelle

    valeur_exceptionnelle ::= id_exception
    valeur_exceptionnelle ::= (id_exception val_associée)

    Règle de typage du déclenchement d'exception

    raise : exn -> 'a E:exn
    -----------------------
    (raise E):'a

    Exemples

    #raise fin_de_programme;;
    Uncaught exception: fin_de_programme
    #raise division_par_0;;
    Uncaught exception: division_par_0
    #raise (erreur 45);;
    Uncaught exception: erreur 45
    #raise (erreur 177);;
    Uncaught exception: erreur 177
    

    Gestion d'exception

    La gestion des exceptions est réalisée par l'expression de contrôle :

    Syntaxe de gestion d'exception

    gestion_exception ::= try expression with
    motif_except_1 -> expression_1
    | motif_except_2 -> expression_2
    ....
    | motif_except_n -> expression_n

    motif_except_i ::= exception

    Si l'évaluation de l'expression contrôlée expression ne déclenche aucune exception, l'expression de contrôle gestion_exception retourne la valeur de l'expression contrôlée (partie à gauche de with). Sinon, si une exception motif_except_i est déclenchée, celle-ci est filtrée (partie à droite de with) et l'expression de contrôle gestion_exception retourne la valeur de l'expression expression_i associée à l'exception motif_except_i. Sinon, si une autre exception non filtrée est déclenchée, l'évaluation de l'expression de contrôle gestion_exception est arrêtée et l'exception est propagée.

    Règle de typage de la gestion d'exception

    E:T M1:exn ... M1:exn E1:T ... En:T
    -------------------------------------
    (try E with M1 -> E1|...|Mn -> En):T

    Exemples

    #exception exemple_0
     and exemple_numero of int
     and exemple of string;;
    Exception exemple_0 defined.
    Exception exemple_numero defined.
    Exception exemple defined.
    
    #let gestion_d'exception x = try
       match x with
         0 -> raise exemple_0
       | 1 -> raise (exemple "Un")
       | 2 -> "DEUX"
       | 5 -> raise (exemple "Cinq")
       | n -> raise (exemple_numero n)
       with
         exemple_0 -> "Zero"
       | exemple s -> s
       | exemple_numero n -> string_of_int n ;;
    gestion_d'exception : int -> string = <fun>
    
    #gestion_d'exception 0 ;;
    - : string = "Zero"
    #gestion_d'exception 1 ;;
    - : string = "Un"
    #gestion_d'exception 2 ;;
    - : string = "DEUX"
    #gestion_d'exception 5 ;;
    - : string = "Cinq"
    #gestion_d'exception 3 ;;
    - : string = "3"
    

    Exercice 26

    La fonction Caml prédéfinie assoc permet de rechercher un élément dans une liste de paires, à partir de la valeur du premier terme a de la paire (a,b) selon la syntaxe assoc a liste.
    Si la fonction échoue elle déclenche l'exception Not_found.
    Selon le même principe, définir une fonction récursive assoc_r en Caml définissant et en utilisant l'exception Non_trouvé

    Solution

    Le type produit vectoriel
    Fonctions
    La récursivité
    Le filtrage
    Le type somme
    Les listes
    Les exceptions

    Exercice 27

    Dans les définitions Caml suivantes, on construit la fonction entrer_entier pour contrôler la saisie des nombres entiers dans un intervalle délimité par une borne inférieure et une borne supérieure [borne_inf, borne_sup] :
    (* affichage d'un message sur la ligne suivante *) 
    #let message m = 
      print_newline (); 
      print_string m ;; 
    message : string -> unit = <fun&fun; 
    
    (* entrée de donnée précédée de l'affichage d'un message *) 
    #let demande question = 
      message (question^" : ") ; 
      read_line () ;; 
    demande : string -> string = <fun> 
    (* entrée de donnée contrôlée *) 
    #let rec entrer_entier x (borne_inf, borne_sup)= 
      let q = x^" (min="^(string_of_int borne_inf) 
               ^", max="^(string_of_int borne_sup)^")" in 
      try 
        let n = int_of_string (demande q) in 
        if (nborne_sup) then raise erreur_bornes 
        else n 
      with 
        Failure "int_of_string" -> 
    	message "Erreur de saisie : entrer un nombre entier." ; 
    	entrer_entier x (borne_inf, borne_sup) 
      | erreur_bornes -> 
    	message "Erreur de saisie : bornes non respectées." ; 
    	entrer_entier x (borne_inf, borne_sup) ;; 
    entrer_entier : string -> int * int -> int = <fun> 
    
    a) - commenter l'utilisation de l'exception Caml prédéfinie : Failure "int_of_string".
    b) - définir les autres exceptions utilisées et indiquer leur rôle.

    Solution

    Fonctions
    La récursivité
    Le filtrage
    Les exceptions


    Programmation modulaire

    modules

    Un module est comme un ensemble de définitions et de définitions formées dans un environnement de définition afin de construire un nouvel environnement qui sera compilé et conservé séparément. Par son principe, la programmation modulaire facilitera la poursuite de plusieurs objectifs tels que :

    Réutilisabilité et partage du code

    Il est possible de mettre en place une répartition du travail autour de la conception d'ensembles de définitions et de définitions destinés à être réutilisés comme extension temporaire ou définitive d'un ou de plusieurs environnements. Ainsi les grands programmes sont découpés en modules communs à plusieurs utilisations et dont la réalisation est partageable entre les diverses équipes de programmation disponibles.

    Simplification des problèmes à traiter et amélioration de la fiabilité des programmes

    Une solution globale à un problème général peut être recherchée en considérant que le problème initial est décomposable en sous-problèmes ou fonctions plus simples dont la solution participe à la solution du problème global. Le même raisonnement est ensuite reproduit au niveau de chacun des sous-problèmes ainsi obtenus. On procède ainsi, à une décomposition fonctionnelle.

    Simplification de la gestion et de la maintenance des programmes

    Au terme d'une décomposition fonctionnelle, l'ensemble des fonctions élémentaires constitutives de la solution globale, fait apparaître des sous-ensembles de fonctions regroupées autour d'un même thème. Nous nommerons modules ces sous-ensembles de fonctions rassemblées par thème de travail. Plusieurs problèmes pourront faire naître des catégories de sous-problèmes similaires faisant appel aux mêmes fonctions ainsi créées. Ainsi les fonctions communes à plusieurs programmes seront rassemblées dans des modules et partagées entre ces programmes. La modularité va permettre une réduction notable de la taille des programmes et en outre, faciliter les corrections et les améliorations à apporter aux fonctions communes à un ensemble de programmes.
    Les modules sont formés de deux fichiers, le fichier d'interface et le fichier d'implémentation.

    Modules d'implémentation ou module de définition

    Un module de définition est une séquence de phrases d'implémentation. Il s'agit d'un fichier contenant toutes les définitions, définitions et expressions utiles, que celles-ci soient exportées vers les autres modules ou strictement internes au module source. Ce fichier est désigné par le nom du module suivi d'une extension (.ml).

    Syntaxe de module de définition

    phrase_d'implémentation ::=
    expression
    | définition_de_valeur
    | définition_de_type_non_exporté
    | définition_d'exception_non_exportée
    | directive
    définition_de_valeur ::=
    let liaison
    ... and liaison ;;
    | let rec liaison
    ... and liaison ;;
    définition_de_type_non_exporté ::=
    type def_type
    ... and def_type ;;
    def_type ::= ident_type = expression_de_type
    définition_d'exception_non_exportée ::=
    exception déf_constructeur
    ... and déf_constructeur ;;
    directive ::=
    #open nom_du_module ;;
    | #close nom_du_module ;;

    Type abstrait

    Les types abstraits sont utilisés pour cacher les définitions de certains types. Ils sont définis dans le module de définition et font l'objet d'une déclaration dans le module d'interface. Par cette technique, le programmeur autorise l'exportation du type sans révéler sa structure.

    Syntaxe de type abstrait

    déclaration_de_type_abstrait ::=
    type définition_de_type_abstrait

    définition_de_type_abstrait ::=
    ident_type
    définition_de_type_abstrait ::=
    paramètres ident_type

    Module d'interface et déclarations exportées

    Un module d'interface est constitué par une séquence de phrases d'interface. Il s'agit d'un fichier contenant les déclarations exportées du module. S'il n'existe pas de module d'interface, alors tous les objets du module d'implémentation sont exportés. Quand un module d'interface est créé, seuls les objets déclarés dans le module d'interface sont exportés. Ce fichier est désigné par le nom du module source suivi d'une extension (.mli).

    Syntaxe de module d'interface

    phrase_d'interface ::=
    déclaration_de_valeur
    | déclaration_de_type_abstrait
    | déclaration_de_type_exporté
    | déclaration_d'exception_exportée
    | directive
    déclaration_de_valeur ::=
    value ident : expression_de_type
    ... and ident : expression_de_type ;;
    déclaration_de_type_exporté ::=
    type def_type
    ... and def_type ;;
    déclaration_d'exceptions_exportées ::=
    exception déf_constructeur
    ... and déf_constructeur ;;

    Utilisation des modules

    Les fonctions de contrôle du système interactif

    La fonction include

    Syntaxe include source
    Typage string -> unit

    La fonction include lit, compile et évalue les phrases du fichier source indiqué par la chaîne de caractère fournie en argument. Cette fonction n'est pas destinée a charger des modules. Mais elle peut servir à installer des environnements de travail.

    L'insertion des phrases, lors de la lecture du fichier source, est réalisée comme une entrée faite au clavier, ou encore comme une insertion de texte en édition par les commandes d'édition Copier et Coller avec Windows.
    Les liaisons (identificateur, valeur) établies par les définitions effectuées dans le fichier source sont ajoutées à l'environnement courant. Un nouvel environnement global est construit :

    Eglobal_i = [liaisons_Emodule_appelé_par_include]><[liaisons_Eappelant]
    Exemples
    Chargement du fichier source fichier
    include fichier

    # include "progcaml" ;;
    Charge le fichier source "progcaml.ml" à partir du répertoire courant.

    # include "mon_chemin\\progcaml" ;;
    Charge le fichier source "progcaml.ml" à partir du répertoire du chemin d'accès mon_chemin. Tous les caractères <backslash> "\" (séparateur de niveau de répertoire dans un chemin d'accès) sont doublés à l'intérieur de la chaîne de caractères.

    Accès aux fonctions et valeurs déclarées dans le fichier fichier
    # alpha ;;
    Accède à la fonction "alpha" du fichier chargé "progcaml"

    La fonction load

    Syntaxe load source
    Typage string -> unit

    La fonction load charge, compile et évalue les phrases du fichier source indiqué par la chaîne de caractère fournie en argument.
    Les liaisons résultant des définitions du fichier source ne sont pas installées dans l'environnement courant et celui-ci demeure inchangé. Toutefois, le module n'est pas ouvert et les identificateurs déclarés du module chargé par load sont accessibles en les préfixant par le nom du ficher comme des identificateurs qualifiés.

    module__identificateur

    Exemples
    Chargement du module source module
    load module

    # load "progcaml" ;;
    Charge le fichier source "progcaml.ml" à partir du répertoire courant.

    # load "mon_chemin\\progcaml" ;;
    Charge le fichier source "progcaml.ml" à partir du répertoire du chemin d'accès mon_chemin.

    Accès aux fonctions et valeurs déclarées dans le module module
    module__identificateur

    # progcaml__alpha ;;
    Accède à la fonction "alpha" du module chargé "progcaml"

    La fonction load_object

    Syntaxe load_object source
    Typage string -> unit

    La fonction load_object charge le code du fichier compilé indiqué par la chaîne de caractère fournie en argument.
    Les liaisons résultant des définitions du fichier objet ne sont pas installées dans l'environnement courant et celui-ci demeure inchangé. Toutefois, les identificateurs du fichier chargé par load_object sont accessibles en les préfixant par le nom du ficher comme des identificateurs qualifiés.
    Exemples
    Chargement du module module
    load_object module

    # load_object "progcaml" ;;
    Charge le fichier de code compilé "progcaml.zo" à partir du répertoire courant. Le fichier d'interface compilé "progcaml.zi" indique les types, exceptions et valeurs exportés.

    # load_object "mon_chemin\\progcaml" ;;
    Charge le fichier de code compilé "progcaml.zo", associé à "program.zi", à partir du répertoire du chemin d'accès mon_chemin.

    Accès aux fonctions et valeurs déclarées dans le module module
    module__identificateur

    # progcaml__alpha ;;
    Accède à la fonction "alpha" du module chargé "progcaml"

    Les directives #open et #close

    Les déclarations établies par un module donné sont importées au moyen de la directive :

    #open module

    Dans le système interactif, le code doit être chargé avec les fonctions load ou load_object.

    Les déclarations importées sont ensuite oubliées au moyen de la directive :

    #close module

    Exemples
    Ouverture du module "fichier"
    # #open fichier

    # #open "progcaml" ;;
    Ouvre le module chargé "progcaml".

    Fermeture du module "fichier"
    # #close fichier

    # #close "progcaml" ;;
    Ferme le module chargé "progcaml".

    Compilation séparée des modules

    Les modules font l'objet d'une compilation séparée : Non compilés, donc directement à partir du texte de leur code source, les modules peuvent être utilisés dans les programmes, sous le système interactif.

    Exemple d'utilisation de module


    fichier exemple

    (* exemple.ml *)
    let val = 555 ;;


    On construit un module en créant un fichier exemple.mli qui exporte la valeur val définie dans le fichier exemple.ml


    (* exemple.mli *)
    value val : int ;;

    Cas du compilateur indépendant
    Compilateur indépendant
    (* prog.ml (version 1) *)
    
    ...exemple__val ...
    Module appelant, première version.Les valeurs définies dans le module sont rendues accessibles au moyen des identificateurs qualifiés par le nom du module.
    (* prog.ml (version 2) *)
    #open "exemple" ;;
    
    ... val ...
    Module appelant, deuxième version.Installation des liaisons dans l'environnement courant.Les valeurs définies dans le module sont directement accessibles.
    camlc -c exemple.ml Compilation séparée du module exemple.
    camlc -c prog.ml Compilation séparée du module prog. Les liaisons avec les objets externes tels que ceux du module exemple ne sont pas installées.
    camlc -o prog.exe exemple.zo prog.zo Edition des liens et production du programme exécutable prog.exe.
    Cas du système interactif
    Système interactif : session Caml
    include "exemple" ;;
    
    val ;;
    - : int = 555
    Lecture du texte source, compilation, évaluation, et implémentation dans l'environnement courant.Les valeurs définies dans le module sont directement accessibles.

    load "exemple" ;;
    
    exemple__val ;;
    - : int = 555
    Lecture du texte source, compilation, évaluation, et implémentation dans l'environnement propre du module exemple.Les valeurs définies dans le module et exportées sont rendues accessibles au moyen des identificateurs qualifiés par le nom du module.
    #open "exemple" ;;
    
    val ;;
    - : int = 555
    Installation des déclarations dans l'environnement courant. Les valeurs définies dans le module et exportées sont rendues directement accessibles.
    load_object "exemple" ;;
    
    exemple__val ;;
    - : int = 555
    Chargement du code préalablement compilé, et implémentation dans l'environnement propre du module exemple. Les valeurs définies dans le module et exportées sont rendues accessibles au moyen des identificateurs qualifiés par le nom du module.
    #open "exemple" ;;
    
    val ;;
    - : int = 555
    Installation des déclarations dans l'environnement courant. Les valeurs définies dans le module sont rendues directement accessibles.

    Exercice 28

    Cet exercice fait appel aux références Soit le module Caml suivant :
     
    (* pile.ml *) 
    let global_pile = ref ([]:int list);;
    let init_pile () =
    global_pile := []
    and empiler x =
    global_pile := x :: !global_pile
    and depiler () =
    match !global_pile with
    [] -> print_string "pile vide\\n"
    | x::R -> global_pile := R
    and afficher () =
    !global_pile;;
    établir son interface pour exporter uniquement les fonctions init_pile, afficher, empiler et depiler, en dissimulant la variable globale global_pile.

    Solution

    Programmation modulaire


    Le polymorphisme

    Types polymorphes

    Un type polymorphe est un type décrit par une expression de type dans laquelle figurent des paramètres de types. Un paramètre de type est représenté par un identificateur précédé d'une apostrophe.

    Syntaxe de définition de type polymorphe

    type_polymorphe ::=
    type paramètres nom_type =
    définition_type_polymorphe


    paramètres ::= 'ident
    paramètres ::= ( 'ident, ... 'ident )

    L'expression définition_type_polymorphe représente une expression définissante de type dans laquelle figurent les paramètres de type introduits dans la partie gauche de la définition et associées au nom du type défini.

    type_polymorphe ::=
    type paramètres nom_type ==
    expression_type_polymorphe

    Cette deuxième forme syntaxique est une définition de type synonyme polymorphe. L'expression expression_type_polymorphe représente une expression de type dans laquelle figurent les paramètres de type introduits dans la partie gauche de la définition et associées au nom du type défini.

    Exemples

    #type 'a couple == 'a * 'a ;;
    Type couple defined.
    #(4,85 : int couple) ;;
    - : int couple = 4, 85
    
    #type ('a, 'b) élément =
      Element_a of 'a | Element_b of 'b * int ;;
    Type élément defined.
    #let x = Element_a 45 and y = Element_b("Z",7) ;;
    x : (int, 'a) élément = Element_a 45
    y : ('a, string) élément = Element_b ("Z", 7)
    

    Exemple de définition de type récursif polymorphe :

    # type 'a arbre = 
        Feuille of 'a 
      | Fourche of 'a arbre * 'a arbre ;;
    Type arbre defined.
    
    # Feuille(4), Feuille(`A`) ;;
    - : int arbre * char arbre = Feuille 4, Feuille `A`
    # Fourche(Feuille(false),Feuille(true)) ;;
    - : bool arbre = Fourche (Feuille false, Feuille true)
    

    Contraintes de type

    Les contraintes de type servent à spécialiser des structures polymorphes pour les contraindre à être utilisées avec des expressions de typetypes particulières.
    Deux cas se présentent :
  • Contrainte totale de type : chacune des variables de type est spécialisée par une valeur particulière de type et le polymorphisme est totalement éliminé.
  • Contrainte partielle de type : certaines variables de type sont spécialisées par une valeur particulière de type, alors que d'autres variables de type conservent leur caractère polymorphe.

    Syntaxe de contrainte de type

    expression_contrainte ::=
    (expression_polymorphe : expression_de_type)

    Exemples

    Contrainte totale de type :
    #((true, false): bool couple) ;;
    - : bool couple = true, false


    Contrainte partielle de type :
    #Element_a 5;;
    - : (int, 'a) élément = Element_a 5
    #Element_b ("AZUR",100);;
    - : ('a, string) élément = Element_b ("AZUR", 100)

    Définition de fonction polymorphe

    Exemple 1 : la fonction id :

    Soit la définition suivante de la fonction identique id :

    #let id = function x -> x ;;
    id : 'a -> 'a = <fun>


    Le typage de la fonction fait apparaître un type fonctionnel comportant un paramètre de type 'a .

    Exemple 2 : la fonction echange :

    #let echange(x,y) = y,x ;;
    echange : 'a * 'b -> 'b * 'a = <fun>


    Le typage de la fonction fait apparaître un type fonctionnel comportant les paramètres de type 'a et 'b .

    Exemple 3 : la fonction bis :

    On construit une fonction bis polymorphe :

    #let bis = function x -> (x,x) ;;
    bis : 'a -> 'a * 'a = <fun>


    Le typage de la fonction fait apparaître un type fonctionnel comportant les paramètres de type 'a .

    Des fonctions telles que id (fonction Identique), bis, et echange, qui acceptent des expressions de type quelconque en arguments ou retournent des expressions de type quelconque en résultat, sont des fonctions polymorphes.

    Application de fonction polymorphe

    Lors de l'application de la fonction , le type particulier correspondant à l'expression en argument vient se substituer au paramètre de type de la fonction (instanciation).

    Exemple 1 : la fonction id :

    Expression de la fonction instanciée Typage et évaluation
    #id true ;; - : bool = true
    #id 48 ;; - : int = 48
    #id `c` ;; - : char = `c`
    #id "hello" ;; - : string = "hello"
    #id (45 , []) ;; - : int * 'a list = 45, []
    #id id;; - : 'a -> 'a = <fun>

    Exemple 2 : la fonction echange :

    Expression de la fonction instanciée Typage et évaluation
    #echange(248,false) ;; - : bool * int = false, 248
    #echange("un",1) ;; - : int * string = 1, "un"

    Exemple 3 : la fonction bis :

    Spécialisation de fonction polymorphe

    Les contraintes de types permettent de créer des instances spécialisées de la fonction polymorphe. Par exemple, nous pouvons créer les instances suivantes de fonctions spécialisées de la fonction polymorphe id :

    Définition de la fonction spécialisée Typage et évaluation
    #let id_bool = (id:bool->bool) ;; id_bool : bool -> bool = <fun>
    #let id_int = (id:int ->int ) ;; id_int : int -> int = <fun>
    #let id_char = (id:char->char) ;; id_char : char -> char = <fun>
    #let id_unit = (id:unit->unit) ;; id_unit : unit -> unit = <fun>

    Filtrage par fonction polymorphe

    let triplet_élément_1 = function (x,_,_) -> x
    and triplet_élément_2 = function (_,y,_) -> y
    and triplet_élément_3 = function (_,_,z) -> z ;;
    
    triplet_élément_1 : 'a * 'b * 'c -> 'a = <fun>
    triplet_élément_2 : 'a * 'b * 'c -> 'b = <fun>
    triplet_élément_3 : 'a * 'b * 'c -> 'c = <fun>
    
    Dans cet exemple les fonctions triplet_élément_n retournent le nième élément d'un triplet. Les applications qui suivent, illustrent le polymorphisme de ces 3 fonctions :

    Application des 3 fonctions à un triplet d'entiers :
    #triplet_élément_1 (5,6,7) ;;
    - : int = 5
    #triplet_élément_2 (5,6,7) ;;
    - : int = 6
    #triplet_élément_3 (5,6,7) ;;
    - : int = 7
    
    Application des 3 fonctions à un triplet de chaînes de caractères :
    #triplet_élément_1 ("oui","non","peut-être") ;;
    - : string = "oui"
    #triplet_élément_2 ("oui","non","peut-être") ;;
    - : string = "non"
    #triplet_élément_3 ("oui","non","peut-être") ;;
    - : string = "peut-être"
    
    Application des 3 fonctions à un triplet de valeurs de types différents :
    #triplet_élément_1 (0,`z`,"ok") ;;
    - : int = 0
    #triplet_élément_2 (0,`z`,"ok") ;;
    - : char = `z`
    #triplet_élément_3 (0,`z`,"ok") ;;
    - : string = "ok"
    

    Fonctions génériques et applications partielles

    Dans certains langages impératifs, on dispose d'un concept de généricité utilisable avec les fonctions, selon lequel on considère une fonction générique comme une structure présentant deux niveaux d'abstraction : La définition suivante propose une implémentation possible de ce type fonction générique :
    let fonction_generique = function g_i -> (* niveau externe *)
    let fonction_generique = (* niveau interne *)
    match g_i with
    v_1 -> function p_1 -> corps(v_1,p_j(v_1))
    |... -> ...
    |v_n -> function p_n -> corps(v_n,p_j(v_n))
    in fonction_generique
    L'instanciation est construite par l'application de la fonction générique aux paramètres effectifs qui lui sont fournis en arguments actuels au niveau d'abstraction externe :

    let fonction_instanciée = fonction_generique v_i

    ce qui correspond à la valeur fonctionnelle décrite par :
    (function p_i -> corps(v_i,p_i))

    Pour simplifier nous étudierons un cas particulier de la forme précédente à partir d'un exemple :

    Cas particulier

    let fonction_generique =
      function g_i ->
        let fonction_generique =
          function p_j -> corps(g_i,p_j)
        in fonction_generique ;;
    
    let fonction_instanciee = fonction_generique g_e ;;
    
    L'application de la fonction générique engendre la construction d'un environnement temporaire contenant la définition locale de la fonction interne.

    Cette fonction peut être construite, en Caml, sous la forme d'une fonction à deux arguments, sans recourir à une définition locale de fonction interne :
    let fonction_globale =
      function g_i ->
      function p_j -> corps ;;
    
    let application_partielle = fonction_globale g_e ;;
    

    Exemple

    #let add_g =  (* fonction générique *)
      function x ->
        let add_g =
          function y -> x + y
        in add_g ;;
    add_g : int -> int -> int = <fun>
    
    #let add_i_8 = add_g 8 ;;   (* fonction instanciée *)
    add_i_8 : int -> int = <fun>
    
    #add_i_8 9;;  (* application de la fonction instanciée *)
    - : int = 17
    
    
    #let g_add =   (* fonction globale *)
      function x ->
      function y -> x + y ;;
    g_add : int -> int -> int = <fun>
    
    #let i_add_8 = g_add 8 ;; (* application partielle *)
    i_add_8 : int -> int = <fun>
    
    #i_add_8 9;;  (* application totale *)
    - : int = 17
    
    On voit clairement que le concept de fonction partielle recouvre de manière simple le concept de fonction générique du type précédent :
    let f =
      function x_1 		->	(* niveau externe *)
      ... 
      function x_i 		->
      function x_(i+1) 	->	(* niveau interne *)
      ...
      function x_n 		->
    	corps_de_f
    
    Dans cette définition de la fonction f, on fait apparaître les deux niveaux d'abstraction souhaités. On comprend que cette formalisation n'apporte aucune modification de structure à la fonction f et qu'il est possible de distinguer autant de niveaux d'abstraction qu'il existe d'arguments fonctionnels pour f.

    Une autre catégorie de fonctions génériques des langages impératifs correspond aux fonctions dans lesquelles des types sont passés en arguments. En Caml, le polymorphisme des fonctions fourni une solution directe à ce genre de problème.

    Retour au début du document

    dernière modification : 06/12/96