Manuel : Notions de base

abstraction concrète


Commentaires

"Sans commentaire."

Bien qu’inutiles pour l’exécutant machine, et ignorés par le compilateur, les commentaires sont judicieusement utilisés par le programmeur, pour documenter les programmes. Dans le langage Caml, ils sont encadrés par les symboles "(*" au début et "*)" à la fin du commentaire et peuvent être placés à n'importe quelle position dans la ligne de programme. Tous les caractères se trouvant entre "(*" et "*)" sont ignorés par le compilateur. Enfin Caml accepte les commentaires emboîtés.

Exemple de commentaire simple
(* ceci est un commentaire en Caml *)
Exemple de commentaire emboîté
(* début de l'exemple 2
ceci est un autre commentaire en Caml
avec mise en page
et sur plusieurs lignes
(* ceci est un commentaire emboîté dans l'exemple 2 *)
(* ceci est un autre commentaire
(* emboîté à
(* plusieurs
(* niveaux d'imbrication *) *) *) *)
fin de l'exemple 2 *)




Identificateurs et expressions

"Et s'il me dit un nom
C'est celui d'un coteau
C'est celui d'une fille
Et celui d'un bateau
C'est celui d'une ville
Et celui d'un château."

Gilles Vigneault.

Identificateurs

Les identificateurs sont utilisés en Caml pour nommer des entités telles que des variables, des fonctions, des types, des éléments de structures de ces objets comme les étiquettes (noms de champs), les constructeurs (de types ou de valeurs). Le langage Caml distingue les majuscules des minuscules. Le premier caractère d’un identificateur est obligatoirement une lettre. Sa longueur, le nombre des caractères qui le composent, doit être comprise dans un intervalle de 1 à 256 caractères. Les caractères suivants peuvent être des lettres, des chiffres, des apostrophes et des tirets, à condition que deux tirets consécutifs soient séparés par au moins un autre caractère.
Exception à la règle, deux tirets sont immédiatement consécutifs (ou adjacents) quand l’identificateur désigne le nom d’une fonction d’un module de bibliothèque. Dans ce cas les deux tirets adjacents servent à séparer les deux parties du nom, en premier, celui du module, et en second, celui de la fonction.
Par exemple : sort__merge désigne la fonction merge du module sort.

Les identificateurs doivent être différents des mots-clés du langage Caml tels que :
function, if, then, else, true, false, etc.
Exemples d'identificateurs valides et distincts
un, deux, A, X', X'', ALPHA, Alpha1, alpha_1, B5, autre_exemple, autre_exemple_2, carre_d'as, FUNCTION, Then
HECTOR, Hector, hector, HecTor, heCtOr, hectoR
i_den't_if'ic_ateur12'''

Exercice 1

Rechercher pourquoi les identificateurs suivants ne sont pas valides.
1_un, _deux, 'trois, 8A, carre d'as, function, then.

Solution

Manuel : Identificateurs

Expressions



Type et valeur d'une expression

Le concept de type est à rapprocher de la notion mathématique d'ensemble. Le type d'une expression représente l'implémentation de l'ensemble auquel appartient la valeur obtenue par l'évaluation de cette expression.

Quelques types pré-définis

Le type int

Le type int implémente un sous-ensemble fini des nombres entiers dans l'intervalle [-230,230-1].
Les principales opérations pré-définies sur les entiers sont :
. l'addition +,
. la soustraction -,
. la multiplication *,
. la division entière /,
. le reste de la division entière mod
. et les comparaisons ( <, >, <=, >= ).

Le type float

Le type float implémente un sous-ensemble fini des nombres décimaux.
Les principales opérations pré-définies sur les décimaux sont :
. l'addition +.,
. la soustraction -.,
. la multiplication *.,
. la division /.
. et les comparaisons ( <., >., <=., >=. ).

Le type bool

Le type bool implémente l'ensemble des valeurs booléennes : true et false. Les opérations pré-définies sur les booléens sont : la négation not, la disjonction || (ou or) et la conjonction && (ou &).

Le type char

Le type char implémente un ensemble des caractères codés par les entiers 0 à 255, les codes 0 à 127 correspondent aux caractères ASCII. Les valeurs de ce type sont notées au moyen du caractère qu'elles représentent, placé entre quotes, ou au moyen du numéro de code à trois chiffres ASCII précédé du backslash \ et placé entre quotes, ou encore au moyen d'un symbole spécial (n = nouvelle ligne, t = tabulation) précédé du backslash \ et placé entre quotes, par exemple : `a`, `A`, `$`, `9`, `\065`, `\n`.

Le type string

Le type string implémente un sous-ensemble des chaînes de caractères de longueur [0,2 16-1]. Les chaînes de caractères sont notées entre guillemets, par exemple : "exemple de chaîne". L'opérateur de concaténation de chaînes de caractères est noté ^.
Par exemple : la concaténation des deux chaînes "bon" et "jour" : "bon" ^ "jour" donnera la chaîne "bonjour".

Le type unit

Le type unit ne possède qu'une valeur, la valeur () qui signifie «rien».
Le type unit est utilisé :

L'égalité structurelle et l'inégalité structurelle

L'égalité structurelle = et l'inégalité structurelle <> sont pré-définies pour tous les types sauf les valeurs fonctionnelles.

Déclaration de types et synthèse de types

Caml est un langage fortement typé, ce qui rend possible un contrôle rigoureux du typage des expressions permettant de déceler certaines erreurs de programmation. Pour ce faire, l'exécutant doit connaître (déclaration de types) ou reconnaître (synthèse de types) le type des objets qui lui sont proposés. La déclaration de types est la technique mise en œuvre dans le cas de certains langages tels que Pascal, C, Ada. Dans ce cas chaque objet figurant dans le programme est préalablement déclaré avec la mention explicite du type auquel il appartient.

Au contraire, la synthèse des types dispense de toute déclaration préalable du type de l'objet. En effet, dans ce second cas, le type de l'objet est déduit du contexte par l'application de règles d'inférence de types.

expressions de type et paramètres de types

Les expressions de type comprennent les expressions simples et les expressions composées de type. Les expressions simples de type sont formées par la mention d'un identificateur de type tel que float, int, char, etc. Une expression composée de type est une expression dans laquelle figurent des expressions de type combinées entre elles par des opérateurs sur les types tels que * et ->.

Les expressions de type peuvent comporter des paramètres de types. Ceux-ci peuvent être remplacés par un type ou une expression de type quelconques (opération de spécialisation). Les paramètres de types sont représentés par un identificateur précédé d’une apostrophe ('identificateur), par exemple 'a et 'b.

Exemples d'expressions de type :

(* expressions simples de type *)
int				
bool				
(* expressions composées de type *)
int * int			
int -> int 			
(char * int) -> bool	
(* expressions paramétrées de type *)
'a -> 'a	(* int -> int est une spécialisation de 'a -> 'a *)
'a -> int -> 'b	

Constructeurs de types

Les identificateurs qui servent à nommer les types tels que int, float, char, sont des constructeurs de types.



Définitions et environnement

définitions et liaisons

Une définition construit une liaison entre un nom, la valeur à laquelle il est associé et son type. La collection des liaisons ainsi créées est appelée environnement. Les définitions successives ont donc pour effet de modifier l'environnement.
Dans ce qui suit, nous simplifierons en considérant la liaison comme une paire qui sera selon le contexte de l'étude : soit une paire (nom, valeur) dans un contexte d'évaluation, soit une paire (nom, type) dans un contexte de typage.

Environnements

Dans un contexte d'évaluation, considérant un ensemble fini N d'identificateurs n et un ensemble fini V de valeurs v, une définition mathématique de la notion d'environnement peut être donnée par :
  • le graphe d'une bijection de N sur V.
    Ou encore, ce qui est équivalent, par :
  • l'ensemble des paires (n, v), telles que si cet environnement contient deux paires (n, v) et (n, v') alors v = v'.

    Une autre approche représente un environnement par une liste de paires (n, v) dans laquelle la dernière liaison créée est placée en tête de liste, et lors de la recherche d'un identificateur dans la liste, à partir de la tête, seule la première occurrence d'une liaison associée à cet identificateur est retenue.

    Le même raisonnement, dans un contexte de typage, mènera à des définitions semblables en substituant un ensemble fini T de types t à V.

    La liste des liaisons (ni, vi) formant l'environnement Eactuel sera notée :
    Eactuel = (nn, vn) ... (n2, v2) (n1, v1) liaisons_Einitial
    ou bien
    Eactuel = (nn, vn) ... (n2, v2) (n1, v1) liaisons_Einitial
    ou bien encore
    Eactuel = (nn, vn) ... (n2, v2) (n1, v1) Einitial
    si j > i alors la création de la liaison (nj, vj) est plus récente que celle de (ni, vi)

    Définitions globales

    Syntaxe : définition globale simple

    définition ::= let identificateur = expression

    Syntaxe : définition globale multiple

    définition ::=
    let identificateur_1 = expression_1
    and identificateur_2 = expression_2
    ...
    and identificateur_n = expression_n

    Exemples de définitions globales
    #let nombre_1 = 102 ;;
    nombre_1 : int = 102
    #let nombre_2 = 57 ;;
    nombre_2 : int = 57
    #let un_nom = "PAUL LEGENDRE" ;;
    un_nom : string = "PAUL LEGENDRE"
    #let autre_nom = "JULES CESAR" ;;
    autre_nom : string = "JULES CESAR"
    #let caractère = `W` ;;
    caractère : char = `W`
    #let calcul = 473 + nombre_1
    and alpha = nombre_1 * nombre_2
    and x = "ceci est une chaine de caracteres"
    and x' = `A` ;;
    calcul : int = 575
    alpha : int = 5814
    x : string = "ceci est une chaine de caracteres"
    x' : char = `A`

    définitions locales

    Les définitions locales construisent des environnements temporaires durant l'évaluation de l'expression dans laquelle elles sont incluses. Au terme de l'évaluation de l'expression contenant des définitions locales, l'environnement global n'est pas modifié.

    Syntaxe : définition locale simple

    définition_locale ::= let identificateur = expression_A
    in expression_B

    Exemple

    #let a = -7  and b = -4 in 5*a*b + 3*(a - b) - a*a - b*b ;;
    - : int = 66
    

    Syntaxe : définition locale simple (variante)

    Dans ses extensions de langage, Caml-Light procure une variante à la syntaxe précédente. Toutefois, ces extensions sont propres à Caml-Light, et seront éventuellement modifiées ou supprimées dans les versions futures du langage.

    définition_locale ::= expression_B
    where identificateur = expression_A

    Exemple

    #5*a*b + 3*(a - b) - a*a - b*b 
        where a = -7  and b = -4 ;;
    - : int = 66
    

    Syntaxe : définitions locales emboîtées et multiples

    définitions_emboitées_multiples ::=
    let ident_1 = expr_1 and...and ident_i = expr_i in
    let ident_(i+1) = expr_(i+1)
    and...and ident_j = expr_j in
    let ident_k = expr_k and...and ident_n = expr_n in expression

    Syntaxe : définitions locales emboîtées et multiples (variante)

    définitions_emboitées_multiples ::=
    expression
    where ident_1 = expr_1 and...and ident_i = expr_i
    where ident_(i+1) = expr_(i+1)
    and...and ident_j = expr_j
    where ident_k = expr_k and...and ident_n = expr_n

    Remarque : Il est important de noter que les quatre formes syntaxiques précédentes ne sont pas des définitions globales. Il s'agit d'expressions contenant des définitions locales.

    A un niveau donné d’imbrication, les définitions sont parallèles, comme le montre l’exemple suivant :

    # let a = 1 in
        let a = 2 and b = a in 
          a + b ;;
    - : int = 3			(* et non pas 4 *)
    


    Exemple de définitions emboîtées
    #let b = 27 in b + b * b - 25 ;;
    - : int = 731
    #let titre = "Software tools in Pascal"
    and auteur = "Brian W. Kernighan, P.J. Plauger" and deux_points = " : "
    in titre ^ deux_points ^ auteur ;;
    - : string = "Software tools in Pascal : Brian W. Kernighan, P.J. Plauger"
    #let h = 8 and i2 = -1 in let t = 3 * h + 7 * i2 in t * t ;; (* syntaxe avec "in" *)
    - : int = 289
    #t * t where t = 3 * h + 7 * i2 where h = 8 and i2 = -1 ;; (* syntaxe avec "where" *)
    - : int = 289
    #let delta = let a = 5 and b = 8 and c =-43 in b*b-4*a*c ;;
    delta : int = 924

    Typage d'une définition locale

    Chaque identificateur est du type de la valeur résultant de l'évaluation de l'expression à laquelle il est associé dans la définition. Si E’ est une expression du type T’ et si T est le type de l'expression évaluée avec un environnement temporaire dans lequel l’identificateur X est lié à la valeur de E’. Cette règle peut être exprimée par la notation suivante :

    Règle de typage d'une définition locale simple

    E':T' E(X:T'):T
    -----------------------
    (let X = E'in E(X)):T

    Evaluation de définition et modification de l'environnement

    Expressions
    Typage et évaluation
    Environnement global et environnements temporaires
    (* debut de session *) Einitial = E
    #let a = 8 ;;
    a : int = 8

    E1 = (a,8)E
    #let n = "Tom" ;;
    n : string = "Tom"

    E2 = (n,"Tom")(a,8)E
    #let a = 5
    in 2 * a ;;
    - : int = 10

    ...............E3_temp = (a,5)E2
    E3 = E2

    Exercice 2

    Soit une session Caml dans un environnement Ei, on effectue les définitions suivantes :
     1. # let a = 30;; 
    2. # let b = a + 20;;  
    3. # let a = b + 5;;  
    4. # a;;  
    5. # b;; 
    6. # let c = 8 in c * c + a + b;; 
    7. # let a = 2 in a * a + a * b + b;; 
    
    Décrire l'environnement à chaque définition. Quelles sont les valeurs associées aux identificateurs a, b et c, après la dernière définition ?

    Solution

    Manuel : Type et valeur des expressions
    Manuel : Définitions et environnement

    Exercice 3

    Depuis l'environnement Eo, on entre la phrase Caml suivante :
     #let taux = 2 in 
       let alpha = 5 in 
         let coef = taux * alpha + alpha in 
           taux * alpha + coef * alpha ;;  
    
    Décrire le nouvel environnement. Quel est le résultat affiché ?

    Solution

    Manuel : Type et valeur des expressions
    Manuel : Définitions et environnement

    Exercice 4

    Au cours d'une session Caml, dans un environnement Env, on effectue les deux définitions suivantes :
     1. # let a = 
           let a = 3 and b = 2 in 
             let a = a + b and b = a - b in a * a - b * b ;; 
    2. # let b = 2 in a * a + a * b + b;; 
    
    Qu'affiche le système interactif après chaque évaluation ?

    Solution

    Manuel : Type et valeur des expressions
    Manuel : Définitions et environnement


    Les modules

    La décomposition fonctionnelle est une incitation positive à la construction de programmes structurés et modulaires. Dans cette optique, le langage Caml offre la possibilité de découper les gros programmes en plusieurs modules distincts qui sont ensuite compilés séparément.



    L'expression conditionnelle

    L’expression conditionnelle délivre un résultat dépendant d’une condition exprimée par une expression booléenne. Le typage fort de Caml exige que la valeur de l’expression conditionnelle, quand la condition est vraie, et la valeur de l’expression conditionnelle, quand la condition est fausse, soient du même type.

    La syntaxe de l’expression conditionnelle met en œuvre trois expressions :

    Syntaxe, typage, évaluation de l'expression conditionnelle

    Syntaxe de l'expression conditionnelle

    expression_conditionnelle ::=
    if expression_booléenne
    then expression_alors
    else expression_sinon

    Règle de typage d'une expression conditionnelle

    E1:bool E2:T E3:T
    -------------------------
    (if E1 then E2 else E3):T

    Evaluation d'une expression conditionnelle

    Lors de l'évaluation de l'alternative if E1 then E2 else E3 dans l'environnement courant Env, E1 est une expression booléenne exprimant une condition de type bool dont l'évaluation donne une valeur booléenne. Les expressions E2 et E3 sont du même type T. Si E1 vaut true l'évaluation de E2 donne E2 : T=a, sinon l'évaluation de E3 donne E3 : T = b. Quel que soit le résultat de l’évaluation de la condition E1, une seule branche de l’expression conditionnelle est évaluée, soit E2, soit E3.
    1. Evaluation(if E1 then E2 else E3)
    2. Evaluation(if Evaluation(E1) then E2 else E3)
    - cas ou la condition est vraie, E1 : bool = true
    3. Evaluation(if true then Evaluation(E2) else E3)
    4. Evaluation(E2) = a
    - cas ou la condition est fausse, E1 : bool = false
    3. Evaluation(if false then E2 else Evaluation(E3))
    4. Evaluation(E3) = b

    Règle d'évaluation d'une expression conditionnelle

    Evaluation(if E1 then E2 else E3)
    -----------------------------------------------------------------
    [(E1=true) --> Evaluation(E2)] OU [(E1=false) --> Evaluation(E3)]

    Exemples d'expressions conditionnelles
    #let x = 0.0 in
    if x = 0.0 then 1.0 else sin(x) /. x ;;
    - : float = 1.0
    #let feu = "VERT" in
    if feu = "ROUGE" then "STOP"
    else if feu = "ORANGE" then "RALENTIR"
    else if feu = "VERT" then "PASSER"
    else "Erreur feu : "^feu ;;
    - : string = "PASSER"

    Contrôle de l'évaluation de l'expression conditionnelle

    Dans une expression, l'utilisation de failwith message déclenche une exception Failure message qui provoque l'arrêt de l'évaluation de l'expression.

    De la même façon, l'utilisation de invalid_arg message déclenche une exception Invalid_argument message qui provoque l'arrêt de l'évaluation de l'expression.

    Contrôle au moyen de la fonction failwith

    controle_d'évaluation ::=
    failwith expression_chaine_message

    Dans certaines circonstances l'évaluation d'une expression ne peut terminer, conduisant ainsi à des situations non contrôlées par l'utilisateur. Ici, par exemple, la division par zéro déclenche l'exception pré-définie du système Caml : Division_by_zero.

    #let a = 55 and x = 0
    in a / x ;;
    Uncaught exception: Division_by_zero
    Dans l'exemple suivant, la division par zéro est contrôlée par la fonction failwith qui déclenche l'exception pré-définie Failure "division par zero".
    #let a = 55 and x = 0 in
    if x = 0 then failwith "division par zero" else a / x ;;
    Uncaught exception: Failure "division par zero"

    Contrôle au moyen de la fonction invalid_arg

    controle_d'évaluation ::=
    invalid_arg expression_chaine_message

    Dans l'exemple suivant, le contrôle des valeurs admises est réalisé par l'emploi de la fonction invalid_arg qui déclenche l'exception pré-définie Invalid_argument of string.

    #let feu = "VIOLET" in
    if feu = "ROUGE" then "STOP"
    else if feu = "ORANGE" then "RALENTIR"
    else if feu = "VERT" then "PASSER"
    else invalid_arg feu ;;
    Uncaught exception: Invalid_argument "VIOLET"


    Le type construit et le type produit

    Le type construit

    Définition d'un type construit simple

    définition_type_construit ::=
    type nom_type = constructeur_de_valeur

    Exemple de type construit simple

    #type unique = MONO ;;
    Type unique defined.
    #MONO ;;
    - : unique = MONO
    
    Dans cet exemple, MONO est un constructeur de valeur et unique est un type construit. L'évaluation de l'expression MONO renvoie la valeur MONO dont le type correspond à unique. Le type unique , ainsi défini, ne comprend q'une seule valeur : la valeur MONO.

    Définition d'un type construit composé

    définition_type_construit ::=
    type nom_type = constructeur_de_valeur of type

    Exemple de type construit composé

    #type message = Message of string ;;
    Type message defined.
    #Message "fin de session" ;;
    - : message = Message "fin de session" 
    
    Dans cet exemple, Message est un constructeur de valeur et message est un type construit. L'évaluation de l'expression, Message "fin de session" renvoie la valeur Message "fin de session" dont le type est message. Le type message, ainsi défini, rassemble toutes les valeurs composées avec le constructeur Message suivi d'une chaîne de caractère quelconque.

    Le type produit cartésien : les tuples

    Les valeurs d'un type produit cartésien, appelées n-uplets ou tuples, sont formées par une juxtaposition de valeurs séparées par le constructeur de valeur virgule ",". Un tuple à deux éléments est aussi appelé paire.

    Syntaxe d'une expression de type produit

    expression_de_type_produit ::=
    expression_de_type_1 * expression_de_type_2 * ... * expression_de_type_n

    Valeur d'une expression de type produit : tuple

    valeur_tuple ::=
    expression_1 , expression_2 , ... , expression_n

    Quelques exemples d'expressions de type produit

    Une paire formée d'un entier et d'une expression de valeur entière : int * int
    #7,(9+4) ;;
    - : int * int = 7, 13
    Une paire mixte (chaîne de caractères, entier) : string * int
    #"ZERO",0 ;;
    - : string * int = "ZERO", 0
    Un triplet : int * string * bool
    #12, "Lucas", true ;;
    - : int * string * bool = 12, "Lucas", true
    Une paire de paires : (int * int) (bool * bool)
    #(1,0),(true,false) ;;
    - : (int * int) * (bool * bool) = (1, 0), (true, false)
    Un quadruplet : int * int * bool * bool
    #1,0,true,false ;;
    - : int * int * bool * bool = 1, 0, true, false

    Typage d'une expression de type produit

    E1:T1 E2:T2 ... En:Tn
    -------------------------------------
    (E1, E2, ... , En):T1 * T2 * ... * Tn

    Le type enregistrement

    Le type enregistrement est une structure composée de champs nommés par des étiquettes (noms de champs). Chaque champ peut contenir une valeur du type précisé dans la définition de la structure de l'enregistrement.

    Première approche du type enregistrement

    enregistrement ::=
    ((étiquette_1, expression_1),
    (étiquette_2, expression_2),
    ...
    (étiquette_n, expression_n))

    Dans ce cas, pour réaliser son implémentation, le type enregistrement est considéré comme un n_uplet de paires dans lequel chaque paire a pour expression de type (étiquette_i, expression_i)

    Exemple d’enregistrement selon la première approche

    #(
    ("nom_prenom", "LESCURE MARIE"),
    ("sexe", `F`),
    ("age", 10)
    ) ;;
    - : (string * string) * (string * char) * (string * int) = ("nom_prenom", "LESCURE MARIE"), ("sexe", `F`), ("age", 10)

    Deuxième approche du type enregistrement

    type t_etiq_1 = constructeur_1 of type_1
    and t_etiq_2 = constructeur_2 of type_2
    ...
    and t_etiq_n = constructeur_n of type_n

    enregistrement ::=
    (constructeur_1(expression_1_de_type_1),
    constructeur_2(expression_2_de_type_2),
    ...
    constructeur_n(expression_n_de_type_n),

    avec le typage de valeur suivant, val_i : t_etiq_i

    Dans ce cas, le type enregistrement est considéré comme un n_uplet de types construits dont le typage correspond à : t_etiq_i ou encore constructeur_i of type_i

    Exemple d'enregistrement selon la deuxième approche

    #type personne_label1 = Nom_prenom of string
    and personne_label2 = Sexe of char
    and personne_label3 = Age of int ;;
    Type personne_label1 defined.
    Type personne_label2 defined.
    Type personne_label3 defined.
    #(
    Nom_prenom("LESCURE MARIE"),
    Sexe"(`F`),
    Age(10)
    ) ;;
    - : personne_label1 * personne_label2 * personne_label3 = Nom_prenom "LESCURE MARIE", Sexe `F`, Age 10

    Syntaxe d'une définition de type enregistrement

    type_enregistrement ::=
    type nom_type = {
    étiquette_1 : type_1;
    étiquette_2 : type_2;
    ...
    étiquette_n : type_n }


    Syntaxe d'une définition d'enregistrement

    définition_enregistrement ::= {
    étiquette_1 = expression_1;
    étiquette_2 = expression_2;
    ...
    étiquette_n = expression_n }


    Remarque : L'ordre des champs est indifférent.

    Typage d'un enregistrement

    E1:T1...En:Tn {c1= v1:T1;...;cn= vn:Tn}:T
    -----------------------------------------
    {c1= v1(E1);...;cn= vn(En)}:T

    Exemples

    #type personne =
     {nom_prenom:string; sexe:char; age:int};;
    Type personne defined.
    
    (* définition de 2 enregistrements x et y 
                        du type personne
    *)
    #let x = {
      nom_prenom = "LESCURE MARIE";
      sexe = `F`;
      age = 10 } ;;
    x : personne = {nom_prenom="LESCURE MARIE"; sexe=`F`; 
     age=10}
    
    #let y = {
      age = 12; sexe = `M`;
      nom_prenom = "VALLEE JEAN"};;
    y : personne = {nom_prenom="VALLEE JEAN"; sexe=`M`; 
     age=12}
    

    Accès à un champ d'un enregistrement déterminé

    Pour retrouver la valeur associé à un champ d'un enregistrement, on le désigne par l'identificateur de l'enregistrement suivi d'un point et de l'étiquette du champ.

    accès_champ_enregistrement ::=
    identificateur_d'enregistrement.étiquette_de_champ


    Exemples

    (* accès aux champs de 2 enregistrements
                        x et y du type personne
    *)
    #x.nom_prenom ;;
    - : string = "LESCURE MARIE"
    #y.nom_prenom ;;
    - : string = "VALLEE JEAN"
    #x.sexe ;;
    - : char = `F`
    #y.age ;;
    - : int = 12
    

    Exercice 5

    Typer les expressions Caml suivantes :
    1. 	(c + 4) <= (8 - x) 
    2. 	("a" ^ "b") = c 
    3. 	(4 < 8) = ("a" = "b") 
    4. 	("a" + 5) = ("a" + 5)  
    

    Solution

    Type et valeur des expressions
    Définitions et environnement

    Exercice 6

    En utilisant les définitions emboîtées en Caml, et avec x=5, calculer l'expression mathématique :
    A = x5 - 2x4 + 3x3 - 4x2 + 5x - 6


    Solution

    Définitions et environnement

    Exercice 7

    Dans un environnement Eo, on effectue la définition :
     #let taux = 2 in 
       let alpha = 5 in 
         let coef = taux * alpha + alpha in 
           let a = taux * alpha + coef * alpha;; 
    
    Décrire le nouvel environnement. Quel est le résultat affiché ?

    Solution

    Type et valeur des expressions
    Définitions et environnement


    Les fonctions

    Fonctions à une variable et fonctions à un argument

    La variable est placée en argument de la fonction. Cet argument est du type de la variable.

    Syntaxe des fonctions à une variable

    expression_fonctionnelle ::=
    function variable -> expression

    Typage des fonctions à une variable

    V:T1 E:T2
    ----------------------
    function V->E : T1->T2

    Fonctions à plusieurs variables et fonctions à un argument

    Les variables sont réunies en un seul argument de la fonction et cet argument est du type produit cartésien composé à partir du type de chaque variable.

    Syntaxe des fonctions à plusieurs variables

    expression_fonctionnelle ::=
    function(var_1,...,var_n) -> expression

    Typage des fonctions à plusieurs variables

    V1:T1 ... Vn:Tn E:T
    ----------------------------------------
    function (V1,...,Vn)->E : (T1*...*Tn)->T

    Fonctions à plusieurs variables et fonctions à plusieurs arguments

    Les variables sont disposées comme autant d'arguments de la fonction. Chaque argument est du type de la variable qu'il représente.

    Syntaxe des fonctions à plusieurs variables

    expression_fonctionnelle ::=
    function var_1 ->
    function var_2 ->
    ...
    function var_n -> expression

    Typage des fonctions à plusieurs variables

    V1:T1 ... Vn:Tn E:T
    -------------------------------------------------
    function V1->...->function Vn->E : T1->...->Tn->T

    Exemples de définition de fonction

    On veut définir une fonction est_pair en Caml, telle qu'elle reçoive un entier n en argument et retourne en résultat, true si n est pair, sinon false.
    Type de la fonction est_pair : int -> bool

    1ère solution :
    On construit une solution au problème en faisant appel à une fonction reste(a,b) qui nous retourne le reste de la division entière de a par b.
    let reste = 
          function (a,b) -> let q = a / b in a - b * q ;;
    let est_pair = 
          function n -> if reste(n,2) = 0 then true else false ;;
    
    2ème solution :
    On utilisera de préférence l'opérateur arithmétique mod pré-défini à la place de la fonction reste.
    let est_pair = 
          function n -> if n mod 2 = 0 then true else false ;;
    
    3ème solution :
    On remarque que si
    A = (if n mod 2 = 0 then true else false)
    B = (n mod 2 = 0)
    alors, l'expression A et l'expression B sont équivalentes. En effet, si B vaut true, A retourne true, et si B est évaluée à false, alors A = false

    En conséquence, on peut réécrire la fonction est_pair en utilisant B au lieu de A.
    Cela donne la fonction simplifiée :
    let est_pair = function n -> n mod 2 = 0 ;;
    

    Fonctions anonymes

    Une fonction anonyme est une expression fonctionnelle. Ainsi l'expression fonctionnelle : function var -> expr, de type fonctionnel : T1 -> T2, est une fonction anonyme. Elle a pour valeur fonctionnelle «x~>expr(x),Edéf »

    Evaluation de l'application d'une fonction anonyme

    E étant une expression du type T1 de valeur val, on évalue l'application de cette fonction anonyme à l'expression E :

    Evaluation((function var -> expr) E)
    => Evaluation(«x~>expr(x),Edéf » val)
    => Evaluation(«expr(val),Edéf »)
    => r

    En conséquence,
    Evaluation((function var -> expr) E) : T2 = r

    Fonctions nommées

    Une fonction nommée fait l'objet d'une définition formant une liaison (identificateur, valeur fonctionnelle). Ainsi, dans la définition : let ident_f = function var -> expr , l'identificateur ident_f désigne une fonction nommée de type fonctionnel : T1 -> T2 , qui a pour valeur fonctionnelle «x~>expr(x);Edéf »

    Evaluation de l'application d'une fonction nommée

    On évalue l'application de la fonction ident_f à l'expression E

    Evaluation(ident_f E)
    => Evaluation(«x~>expr(x);Edéf » val)
    => Evaluation(«expr(val);Edéf »)
    => r

    En conséquence,
    Evaluation(ident_f E) : T2 = r

    Remarque :
    Si Evaluation((function var -> expr) E) : T2 = r
    et Evaluation(ident_f E) : T2 = r
    on en déduit que :
    (function var -> expr) = ident_f

    En conséquence, dans les expressions Caml, on peut remplacer le nom d'une fonction par une expression fonctionnelle équivalente et réciproquement.

    Définitions de fonctions nommées

    Syntaxe 1ère forme

    Fonction à un argument
    définition_fonctionnelle ::=
    let identificateur =
    function variable -> expression

    Fonction à plusieurs arguments
    définition_fonctionnelle ::=
    let identificateur =
    function var_1 ->
    function var_2 ->
    ...
    function var_n -> expression

    Syntaxe 2ème forme

    Fonction à un argument
    définition_fonctionnelle ::=
    let identificateur variable = expression

    Fonction à plusieurs arguments
    définition_fonctionnelle ::=
    let ident var_1 var_2 ... var_n = expression

    Syntaxe 3ème forme

    Fonction à un argument
    définition_fonctionnelle ::=
    let identificateur(variable)=expression

    Fonction à plusieurs arguments
    définition_fonctionnelle ::=
    let ident(var_1)(var_2)...(var_n)= expression

    Syntaxe des fonctions 4ème forme

    Fonction à un argument
    définition_fonctionnelle ::=
    let identificateur = fun variable -> expression

    Fonction à plusieurs arguments
    définition_fonctionnelle ::=
    let identificateur =
    fun var_1 var_2 ... var_n -> expression

    Exemples

    1ère forme 	let cube = function x -> x * x * x
    2ème forme 	let cube x = x * x * x
    3ème forme 	let cube(x)= x * x * x
    4ème forme 	let cube = fun x -> x * x * x
    

    Exemples (fonctions à plusieurs arguments)

    1ère forme
    	let paire =
          	function x ->
    	      function y -> (x,y)
    2ème forme 	let paire x y = (x,y)
    3ème forme 	let paire(x)(y)=(x,y)
    4ème forme 	let paire = fun x -> fun y -> (x,y)
    

    Evaluation d'une définition de fonction

    La définition d'une fonction construit une liaison (identificateur, fermeture) dans l'environnement temporaire s'il s'agit d'une définition locale ou dans l'environnement global s'il s'agit d'une définition globale.

    Variables liées et variables libres

    Soit un environnement dans lequel la liaison (y, 8) est accessible, on considère la fonction suivante : function x -> 2 * x + 5 * y, alors x est une variable liée dans la fonction, tandis que y est une variable libre dans la fonction. La variable libre y est définie par une liaison à un niveau global par rapport à la fonction.

    Exemples de typage des fonctions

    Fonction du type : int -> int -> int

    (* définition *)
    let add = function a -> function b -> a + b ;;
    (* application *)
    add 2 5 ;;
    

    Fonction du type : int -> (int -> int)

    (* définition *)
    let g = function u -> (function v -> u + v) ;;
    (* application *)
    g 2 5 ;;
    

    Fonction du type : (int -> int) -> int

    (* définition *)
    let f = function e -> 1+ e(1+ e(1)) ;;
    (* application *)
    f (add 1) ;;
    f (g 1);;
    

    Fonction du type : (int -> int) -> (int -> int)

    (* définition *)
    let h = function k -> (function a -> k(a+ 1)+ 1) ;;
    (* application *)
    h (add 1) 1;;
    h (g 1);;
    f (h (add 1) );;
    f (h (g 1) );;
    

    Evaluation d'une fonction, fermeture, valeur fonctionnelle

    Une fermeture dénote une valeur fonctionnelle c'est-à-dire un couple formé par le code de la fonction et son environnement de définition. Ainsi, pour une fonction décrite par function x -> f(x), sa fermeture sera notée : F = «x~>f(x), Ef_définition», où x~>f(x) signifie le code de la fonction (premier membre du couple), et Ef_définition est l'environnement courant au moment de la définition de la fonction (deuxième membre du couple).

    Fonctions partielles

    Les fonctions partielles sont de fonctions non totalement définies sur l'ensemble des valeurs du type correspondant à l'ensemble de définition.

    Cas de la fonction inverse

    #let inverse x = 1.0 /. x ;;
    inverse : float -> float = <fun>
    #inverse 5.0 ;;
    - : float = 0.2
    #inverse 0.0 ;;
    80387 Exception: divide by zero!
    - : float = 0.9999976515814
    
    Dans le cas traité en exemple, la fonction n'étant pas définie pour la valeur 0.0 de l'argument, l'exécution du programme conduit à une terminaison anormale de l'évaluation de l'application de la fonction à cette valeur.

    Pour éviter ce problème, le programmeur a la ressource de construire un type nouveau correspondant précisément à l'ensemble des valeurs pour lesquelles la fonction est définie. Toutefois, il n'est pas toujours possible de définir le type souhaité. Il faut alors intercepter (cf. filtrage) les valeurs pour lesquelles la fonction n'est pas définie et leur appliquer un traitement particulier (cf. exceptions). Ainsi la fonction partielle peut être transformée en fonction totale.

    Remarque : Les spécifications de Caml ne définissent pas le traitement du débordement des opérations sur le type float. Selon la machine utilisée, une division par 0.0 pourrait avoir des résultats très différents, du simple déclenchement d'une exception à l'arrêt de la machine.

    Types fonctionnels

    Les types fonctionnels sont de la forme T1->T2 dans laquelle T1 et T2 peuvent être de n'importe quel type, y compris les types fonctionnels.

    Exemples de types fonctionnels

    int -> int
    int -> int -> bool 		 (* qui est équivalent à : int -> (int -> bool)  *)
    (string -> int) -> char
    ('a -> 'b) -> ('c -> 'd)	 (* type fonctionnel polymorphe *)
    


    Les applications

    Une application est une expression formée d'une fonction associée à un ou plusieurs de ses arguments.

    Syntaxe des applications

    application d'une fonction à un argument

    expression_applicative ::=
    expression_f expression_p

    Si expression_applicative est une application d'une fonction quelconque f, alors expression_f est une expression descriptive de la valeur fonctionnelle correspondant à la fonction f et expression_p est une expression descriptive d'une valeur fournie comme paramètre effectif de la fonction f. Chacune des deux expressions peut être placée entre parenthèses pour lever toute ambiguité éventuelle.

    application d'une fonction à plusieurs arguments

    expression_applicative ::=
    expression_f expression_1 ... expression_n

    Considérant que expression_applicative est une application d'une fonction quelconque f, alors expression_f est une expression descriptive de la valeur fonctionnelle correspondant à la fonction f et les expression_i sont des expressions descriptives des valeurs fournies comme paramètres effectifs de la fonction f.

    Typage des applications

    Si E est une expression décrivant une fonction de type T1->T2, et si E' est une expression décrivant une valeur de type T1, alors l'application de E à E' (qui s'écrit E E') est correctement typée T2. Cette règle peut être exprimée par la notation suivante :

    E:T1->T2 E':T1
    ----------------
    (E E'):T2

    Evaluation d'une application

    Règle du passage des paramètres :
    les paramètres effectifs de l'application sont évalués préalablement à leur substitution aux paramètres formels de la fonction.

    L'évaluation de l'application est réalisé dans l'environnement de définition de la fonction.

    Applications partielles

    Soit la fonction à deux arguments enchaine qui concatène deux chaînes de caractères s1 et s2 pour donner une chaîne en résultat :
    #let enchaine s1 s2 = s1 ^ s2 ;;
    enchaine : string -> string -> string = <fun>

    Considérons les cas suivants :
    1) une application totale de cette fonction, quand les deux arguments sont fournis,
    #enchaine "Auteur : " "Richard E. Pattis" ;;
    - : string = "Auteur : Richard E. Pattis"

    2) une application partielle de cette fonction, quand un seul argument est fourni,
    #enchaine "Titre : " ;;
    - : string -> string = <fun>

    l'évaluation de l'application renvoie une valeur fonctionnelle dont le type correspond à une fonction à un argument.


    Ainsi, à partir de l'application partielle d'une fonction, nous pouvons définir une série de nouvelles fonctions :
    #let rubrique_titre = enchaine "Titre : " ;;
    rubrique_titre : string -> string = <fun>

    l'identificateur rubrique_titre est lié à la valeur fonctionnelle créée par l'application partielle de la fonction.
    #rubrique_titre "Karel The Robot" ;;
    - : string = "Titre : Karel The Robot"

    Exercice 8

    Au cours d'une session Caml, E est l'environnement initial.
    Typer, évaluer les phrases Caml suivantes et indiquer l'environnement résultant :
    1. # let a = 5 ;; 
    2. # let a = a + a ;; 
    3. # let v = (a = 10) ;; 
    4. # let f = function x -> x*x + a*a ;; 
    5. # f 2 ;; 
    6. # f f 2 ;; 
    7. # let rec h = function 
    		0 -> 1 
    	|	1 -> 1 
    	|	n -> (f(n-2) + 1) * f(n-1) ;; 
    8. # h 7 ;; 
    9. # let gamma = 
           function a -> function b -> a*b ;; 
    10.# let z = gamma 5 ;; 
    11.# gamma 8 4 ;; 
    12.# z (z 2) ;;  
    
    Solution

    Type et valeur des expressions
    Définitions et environnement
    Fonctions

    Exercice 9

    Typer, évaluer les phrases Caml suivantes :
    1. # let Y = function x -> function y -> function z -> y ;; 
    2. # let H = function u -> function x -> u x x ;;
    3. # H (function x -> fun y -> x+y) 4 ;;
    Solution

    Type et valeur des expressions
    Définitions et environnement
    Fonctions

    Exercice 10

    Au cours d'une session Caml, Env est l'environnement initial, et les définitions suivantes sont effectuées :
    1)#let a = 5 ;; 
    2)#let b = 3 ;; 
    3)#a,b ;; 
    4)#let alpha x   = let a = 2 in a * x + b ;; 
    5)#alpha 7 ;; 
    6)#let béta  x   = let b = 2 in a * x + b ;; 
    7)#béta 7 ;; 
    8)#let gamma a b = let x = 7 in a * x + b ;; 
    9)#gamma a b ;; 
    10)#let a,b,x = 2,1,3 ;; 
    11)#alpha x , béta x , gamma a b ;;  
    
    1) Evaluer et typer chacune des définitions
    2) Décrire l'évolution de l'environnement à chaque étape
    3) Décrire les fermetures des fonctions

    Solution

    Type et valeur des expressions
    Définitions et environnement
    Fonctions

    Exercice 11

    Typer et évaluer les définitions Caml suivantes :
    1) #let h = function f -> function g -> g f ;; 
    2) #let x = h 4 ;;
    3) #let t = h 4 (function x -> x + 2) ;;
    Solution

    Type et valeur des expressions
    Définitions et environnement
    Fonctions

    Exercice 12

    Déclarer les fonctions suivantes en Caml :
    1. Fonction suivant : à un entier n on fait correspondre l'entier (n+1)
    2. Fonction precedent : à un entier n on fait correspondre l'entier (n-1)
    3. Fonction double : à un entier n on fait correspondre l'entier 2*n

    Solution

    Définitions et environnement
    Fonctions

    Exercice 13

    Construire, en Caml, la fonction base permettant de calculer la valeur de base de décompte selon la règle de gestion :
    Si le plafond est inférieur au salaire,
    alors la base de décompte est égale au plafond,
    sinon la base de décompte est égale au salaire.
    Syntaxe = base salaire plafond
    Typage = base : int -> int -> int

    Solution

    Type et valeur des expressions
    Expressions conditionnelles
    Fonctions

    Retour au début du document

    dernière modification : 06/12/96