Camel

Assistant abstraction concrète

Construire un programme sous le système interactif Image d'écran du système interactif sous MSDOS

Une session Caml correspond à une boucle dans laquelle une lecture d'expressions est réalisée sur l'unité d'entrée standard, chaque expression lue est soumise à une analyse lexicale puis à une analyse syntaxique, ensuite elle est typée par le système d'inférence de types, avec affichage du type inféré, et pour terminer, évaluée avec affichage de .la valeur obtenue en résultat

Exemple de session Caml Light Au démarrage, le système interactif affiche la version de Caml Light active, suivie de l'invite "#" qui indique que le système est en attente d'une entrée de l'opérateur Caml Light version 0.71 >

# à ce moment, si l'opérateur veut évaluer une expression telle que "12 + 35", il entre l'expression en la terminant ";;" par un double point-virgule

>

Caml Light version 0.71

;; 35 + #12 pour valider et transmettre l'expression au système interactif, il frappe la touche d'entrée dite retour chariot ou [CR]. A la suite de quoi, le système interactif effectue et affiche le typage et l'évaluation de l'expression. Ceci fait, le .système affiche l'invite et se place, de nouveau, en attente Caml Light version 0.71 > [CR] ;; 35 + #12 int = 17 : -

# Le cycle : nouvelle entrée -> typage-évaluation -> affichage -> nouvelle entrée, se poursuit jusqu'à ce que .)(l'opérateur termine la session en entrant la commande quit Caml Light version 0.71 [CR] ;; 35 + #12

>

int = 17

: -

......# ....... [quit() ;; [CR# .Au cours d'une session Caml, l'environnement global est modifié par les déclarations globales Pour construire un programme sous le système interactif, il suffit de déclarer les types, exceptions, constantes, .variables et fonctions qui seront aussitôt évaluées et introduites dans l'environnement de travail On peut construire un fichier texte contenant la séquence des déclarations. Il suffit, alors, d'appeler ce fichier par la .commande include pour retrouver l'environnement de travail ainsi défini Il est aussi possible de charger le fichier source, avec la commande load, ou compilé, avec la commande load_object. De cette façon il sera possible de retrouver l'environnemnt de travail au moyen de la directive #open mais aussi de le libérer, au moyen de la directive #close

Charger un programme La fonction include La fonction load La fonction load_object La directive #open : Trois commandes sont utilisées pour charger les fichiers de modules Caml .(Les fonctions include et load pour charger les fichiers sources des modules (texte Caml• .La fonction load pour charger les fichiers compilés des modules• .La directive #open sert à ouvrir les modules chargés

Construire un programme exécutable indépendant Programmation modulaire Pour construire un programme exécutable indépendant, on écrit un fichier texte contenant la séquence des .déclarations. Il suffit, ensuite, de compiler ce fichier avec le compilateur camlc

Exemple : .On a produit un fichier texte nommé "progcaml.ml" qui contient le programme principal Considérons que ce fichier utilise les fonctions des modules "module1.ml", avec son interface "module1.mli", et .""module2.ml" associé à "module2.mli .On compile les modules dans l'ordre de leur appel camlc -c "module1.mli" camlc -c "module1.ml" camlc -c "module2.mli" camlc -c "module2.ml" Puis, on lance la production du code exécutable qui sera installé dans un fichier portant le nom choisi par le .(programmeur ("progcaml.exe" dans l'exemple camlc -o "progcaml.exe" "module1.zo" "module2.zo" "progcaml.ml" dernière modification : 06/12/96

La lettre de Caml, numéro 7 Les sources des programmes Caml ; interface de la bibliothèque PATRICIA; implémentation de la bibliothèque PATRICIA interface de la bibliothèque sur les séries formelles ; implémentation de la bibliothèque sur les séries formelles .Retour à la page générale de La lettre de Caml

L'interface de la bibliothèque sur les arbres compactés de recherche : type arbre_de_recherche = { chercher : string -> bool ; insérer : string -> unit ; supprimer : string -> unit } ;; value nouvel_arbre : unit -> arbre_de_recherche ;;

L'implémentation de la bibliothèque sur les arbres compactés de recherche : let rec intervalle i j = if i <= j then i :: (intervalle (i+1) j) else [] ;; let bits_of_char c = let c' = int_of_char c in it_list (fun l i -> (c' lsr i) land 1 :: l) [] (intervalle 0 7) ;; let bits_of_string s = list_it (fun i l -> bits_of_char s.[i] @ l) (intervalle 0 (string_length s - 1)) [0;0;0;0;0;0;0;0] ;; type arbre = Feuille of string | Nud of int * arbre * arbre ;; let rec skip k l = if k = 0 then l else skip (k - 1) (tl l) ;; let recherche a s = let rec aux l = function | Feuille s' -> s = s'

| Nud(k,g,d) -> try let t :: q = skip k l in aux q (if t = 0 then g else d) with _ -> false in aux (bits_of_string s) a ;; let rec suppression a s = let rec aux l = function | Feuille s' when s <> s' -> Feuille s' | Feuille _ -> failwith "Arbre vide !" | Nud(k,Feuille s',d) when s' = s -> ( match d with | Feuille _ -> d | Nud(k',g',d') -> Nud(k + k' + 1,g',d') ) | Nud(k,g,Feuille s') when s' = s -> ( match g with | Feuille _ -> g | Nud(k',g',d') -> Nud(k + k' + 1,g',d') ) | Nud(k,g,d) -> try match skip k l with t :: q -> if t = 0 then Nud(k,(aux q g),d) else Nud(k,g,(aux q d)) with _ -> Nud(k,g,d) in aux (bits_of_string s) a ;; let trouve_place s a = let rec descend = function | Feuille s' -> s' | Nud(_,g,_) -> descend g in let rec aux l = function | Feuille s' -> s' | Nud(k,g,d) -> try match skip k l with t :: q -> aux q (if t = 0 then g else d) with _ -> descend g in aux (bits_of_string s) a ;; let rec discrimine l1 l2 i = match l1,l2 with t1 :: q1,t2 :: q2 -> if t1 <> t2 then i,t1,t2 else discrimine q1 q2 (i + 1) ;; let insertion a s = let s' = trouve_place s a in if s = s' then a else let l,l' = (bits_of_string s),(bits_of_string s') in let i,c,_ = discrimine l l' 0 in let rec aux j l = function

| Feuille s' as a -> if c = 0 then Nud(j,Feuille s,a) else Nud(j,a,Feuille s) | Nud(k,g,d) as a -> if j > k then let t :: q = skip k l in if t = 0 then Nud(k,(aux (j - k - 1) q g),d) else Nud(k,g,(aux (j - k - 1) q d)) else if j < k then if c = 0 then Nud(j,Feuille s,Nud(k-j-1,g,d)) else Nud(j,Nud(k-j-1,g,d),Feuille s) else (* j = k *) failwith "Erreur irrécupérable" in aux i l a ;; (******************************************* ce type est défini dans le fichier .mli, sa définition ne doit pas être répétée ! type arbre_de_recherche = { chercher : string -> bool ; insérer : string -> unit ; supprimer : string -> unit } ;; *********************************************) let nouvel_arbre () = let a = ref (Feuille "") in { chercher = (function s -> recherche !a s) ; insérer = (function s -> a := insertion !a s) ; supprimer = (function s -> a := suppression !a s) } ;;

L'interface de la bibliothèque sur les séries formelles : #open "num" ;; type série_formelle ;; value and and and and and and and

prefix +@ : série_formelle -> série_formelle -> série_formelle prefix -@ : série_formelle -> série_formelle -> série_formelle prefix *@ : série_formelle -> série_formelle -> série_formelle prefix /@ : série_formelle -> série_formelle -> série_formelle prefix @@ : série_formelle -> série_formelle -> série_formelle prefix ^@ : série_formelle -> num -> série_formelle prefix !@ : num list -> série_formelle prefix %@ : num -> série_formelle -> série_formelle

and zéro : num and un : num and deux : num and trois : num and quatre : num and cinq : num and six : num and sept : num and huit : num and neuf : num and dix : num

and un_demi : num and moins_un : num and moins_deux : num and moins_trois : num and moins_quatre : num and moins_cinq : num and moins_six : num and moins_sept : num and moins_huit : num and moins_neuf : num and moins_dix : num and moins_un_demi : num and print_SF : série_formelle -> int -> unit and print_par_défaut : série_formelle -> unit and installe_impression : unit -> unit and crée_SF_de : (num -> num) -> série_formelle and crée_SF_expo_de : (num -> num) -> série_formelle and intégration_SF : série_formelle -> num -> série_formelle and dérivation_SF : série_formelle -> série_formelle and sinus : série_formelle and cosinus : série_formelle and sinus_h : série_formelle and cosinus_h : série_formelle and tangente : série_formelle and tangente_h : série_formelle and arctangente : série_formelle and arctangente_h : série_formelle and exponentielle : série_formelle and ln_un_plus_z : série_formelle and arcsinus : série_formelle and arcsinus_h : série_formelle and catalan : série_formelle ;;

L'implémentation de la bibliothèque sur les séries formelles : #open "num" ;; type 'a glaçon = | Gelé of unit -> 'a | Connu of 'a ;; type série_formelle = { Constante : num ; mutable Reste : série_formelle glaçon } ;; let moins_un = num_of_int (-1) and moins_deux = num_of_int (-2) ;; let [zéro;un;deux;trois;quatre;cinq;six;sept;huit;neuf;dix] = map num_of_int [0;1;2;3;4;5;6;7;8;9;10] ;; let [moins_un;moins_deux;moins_trois;moins_quatre;moins_cinq;moins_six;moins_sept;moins_huit;moins_neuf;moin s_dix] = map num_of_int [-1;-2;-3;-4;-5;-6;-7;-8;-9;-10] ;; let un_demi = un // deux and moins_un_demi = moins_un // deux ;; let reste_SF s = match s.Reste with | Gelé r -> let a = r() in s.Reste <- Connu a ; a | Connu a -> a ;; let crée_SF_de f = let rec crée n =

{ Constante = f n ; Reste = Gelé (function () -> crée (n +/ un)) } in crée zéro ;; let SF_de_poly l = let rec crée = function | [] -> { Constante = zéro ; Reste = Gelé (function () -> crée []) } | a :: q -> { Constante = a ; Reste = Gelé (function () -> crée q) } in crée l ;; let crée_SF_expo_de f = let rec crée n nn = { Constante = (f n) // nn ; Reste = Gelé (function () -> crée (n +/ un) (nn */ (n +/ un))) } in crée zéro un ;; let rec liste_des_coefficients s = function | 0 -> [] | n -> s.Constante :: (liste_des_coefficients (reste_SF s) (n-1)) ;; let rec zéro_SF () = { Constante = zéro ; Reste = Gelé zéro_SF } ;; let rec zn_SF = function | 0 -> { Constante = un ; Reste = Gelé zéro_SF } | n -> { Constante = zéro ; Reste = Gelé (function () -> zn_SF (n-1)) } ;; let rec addition_SF s t = { Constante = s.Constante +/ t.Constante ; Reste = Gelé (function () -> addition_SF (reste_SF s) (reste_SF t)) } ;; let rec soustraction_SF s t = { Constante = s.Constante -/ t.Constante ; Reste = Gelé (function () -> soustraction_SF (reste_SF s) (reste_SF t)) } ;; let rec multiplication_SF_num s n = { Constante = s.Constante */ n ; Reste = Gelé (function () -> multiplication_SF_num (reste_SF s) n) } ;; let opposé_SF s = multiplication_SF_num s moins_un ;; let rec intégration_SF s k0 = { Constante = k0 ; Reste = Gelé (function() -> intègre_SF_depuis_un_certain_rang s un) } and intègre_SF_depuis_un_certain_rang s n = { Constante = s.Constante // n ; Reste = Gelé (function () -> intègre_SF_depuis_un_certain_rang (reste_SF s) (n +/ un)) } ;; let dérivation_SF s = let rec dérivation_aux s n = { Constante = s.Constante */ n ; Reste = Gelé (function () -> dérivation_aux (reste_SF s) (n +/ un)) } in

dérivation_aux (reste_SF s) un ;; let multiplication_SF s t = let produit_de_Cauchy a b = let b' = rev b in it_list2 (fun t x y -> t +/ x */ y) zéro a b' in let rec multiplie_aux s t sl tl = let sl' = s.Constante :: sl and tl' = t.Constante :: tl in { Constante = produit_de_Cauchy sl' tl' ; Reste = Gelé (function () -> multiplie_aux (reste_SF s) (reste_SF t) sl' tl') } in multiplie_aux s t [] [] ;; let composition_SF s t = let rec intervalle i j = if i > j then [] else i :: (intervalle (i + 1) j) in let rec k_somme k s = (* k_somme 3 6 renvoie [[4; 1; 1]; [3; 2; 1]; [3; 1; 2]; ... *) if s = 0 then [] else if k = 1 then [ [ s ] ] else it_list (fun ll i -> (map (function l -> i :: l) (k_somme (k - 1) (s - i))) @ ll) [] (intervalle 1 s) in let coeff av bv = let n = vect_length av - 1 in let sbk l = it_list (fun x i -> x */ bv.(n - i)) un l in it_list (fun s k -> s +/ av.(n-k) */ (it_list (fun x l -> x +/ (sbk l)) zéro (k_somme k n))) zéro (intervalle 1 n) in let rec aux al bl s t = let al' = s.Constante :: al and bl' = t.Constante :: bl in { Constante = coeff (vect_of_list al') (vect_of_list bl') ; Reste = Gelé(function () -> aux al' bl' (reste_SF s) (reste_SF t)) } in if t.Constante <>/ zéro then failwith "La composée a(b(z)) n'existe que si v(b) > 1" ; { Constante = s.Constante ; Reste = Gelé(function () -> aux [ s.Constante ] [ t.Constante ] (reste_SF s) (reste_SF t)) } ;; let un_plus_z_puissance_a_SF a = let rec aux coef k = let k' = k +/ un in

{ Constante = coef ; Reste = Gelé (function () -> aux (coef */ (a -/ k) // k') k') } in { Constante = un ; Reste = Gelé (function () -> aux a un) } ;; let un_sur_a_plus_z_SF a = if a =/ zéro then failwith "1/z n'a pas de développement en série formelle" ; let a' = zéro -/ a in let rec aux coeff = { Constante = coeff ; Reste = Gelé (function () -> aux (coeff // a')) } in aux (un // a) ;; let rec division_SF s t = let rec Cauchy_inverse a b t0 sn = let b' = tl (rev b) in (sn -/ (it_list2 (fun s x y -> s +/ x */ y) zéro a b')) // t0 in let rec divise_aux s t ul tl t0 = let tl' = t.Constante :: tl in let u_n = Cauchy_inverse ul tl' t0 s.Constante in { Constante = u_n ; Reste = Gelé (function () -> divise_aux (reste_SF s) (reste_SF t) (u_n :: ul) tl' t0) } in if t.Constante =/ zéro then if s.Constante =/ zéro then division_SF (reste_SF s) (reste_SF t) else failwith "Division impossible : valuation du numérateur inférieure à celle du dénominateur" else divise_aux s t [] [] t.Constante ;; let puissance_SF_num s n = let a = s.Constante in try multiplication_SF_num (composition_SF (un_plus_z_puissance_a_SF n) { Constante = zéro ; Reste = Gelé(function () -> reste_SF (multiplication_SF_num s (un // a))) }) (if a =/ un then un else a **/ n) with _ -> failwith "Exponentiation impossible" ;; let rec évalue_SF s x n = if n = 0 then s.Constante else s.Constante +/ x */ (évalue_SF (reste_SF s) x (n-1)) ;;

let prefix +@ = addition_SF and prefix -@ = soustraction_SF and prefix *@ = multiplication_SF and prefix /@ = division_SF and prefix @@ = composition_SF and prefix ^@ = puissance_SF_num and prefix !@ = SF_de_poly and prefix %@ n s = multiplication_SF_num s n ;; #open "format" ;; let print_num n = print_string (string_of_num n) ;; let print_variable = function | 0 -> false | 1 -> print_string " z" ; true | n -> print_string " z^" ; print_int n ; true ;; let print_term plus degré s = let c = s.Constante in if c =/ zéro then false else if c =/ un then begin print_string plus ; print_variable degré end else if c =/ moins_un then begin print_string "- " ; print_variable degré end else begin if c >=/ zéro then print_string plus else print_string "- " ; print_num (abs_num c) ; print_variable degré end ;; let rec print_SF s until = open_hovbox 1; let c = s.Constante in if until == 0 then print_num c else let rest = ref s in let nul = ref true in if not (c =/ zéro) then (print_num c ; print_space() ; nul := false) ; for i = 1 to until do rest := reste_SF !rest; let delim = if !nul then "" else "+ " in if print_term delim i !rest then ( nul := false ; print_space()) done ; if not !nul then print_string "+ " ; print_string "O(z^"; print_int (succ until) ; print_string ")" ; close_box() ;; let print_par_défaut s = print_SF s 11 ;; let installe_impression () = install_printer "print_par_défaut" ;; let rec sinus = { Constante = zéro ; Reste = Gelé (function () -> intègre_SF_depuis_un_certain_rang cosinus un) } and cosinus = { Constante = un ; Reste = Gelé (function () -> intègre_SF_depuis_un_certain_rang (opposé_SF sinus) un) } ;;

let rec sinus_h = { Constante = zéro ; Reste = Gelé (function () -> intègre_SF_depuis_un_certain_rang cosinus_h un) } and cosinus_h = { Constante = un ; Reste = Gelé (function () -> intègre_SF_depuis_un_certain_rang sinus_h un) } ;; let tangente = sinus /@ cosinus ;; let tangente_h = sinus_h /@ cosinus_h ;; let arctangente = intégration_SF ((!@ [un]) /@ (!@ [un;zéro;deux])) zéro ;; let arctangente_h = intégration_SF ((!@ [un]) /@ (!@ [un;zéro;moins_deux])) zéro ;; let exponentielle = crée_SF_expo_de (function _ -> un) ;; let ln_un_plus_z = intégration_SF (un_plus_z_puissance_a_SF moins_un) zéro ;; let arcsinus = intégration_SF ((!@ [un;zéro;moins_deux]) ^@ moins_un_demi) zéro ;; let arcsinus_h = intégration_SF ((!@ [un;zéro;deux]) ^@ moins_un_demi) zéro ;; let catalan = ((!@ [un]) -@ ((!@ [un;moins_quatre]) ^@ un_demi)) /@ (!@ [zéro;deux]) ;; .Retour à la page générale de La lettre de Caml

Références abstraction concrète Bibliographie Internet

Bibliographie .Concepts et outils de la programmation .[1] .Accart Hardin T., Donzeau-Gouge Vigié V .Paris, InterEditions .(1993) .ISBN 2-7296-0419-7 .Introduction à la logique contemporaine .[2] .Blanché Robert .Paris, Armand Colin .(1968) .ISBN 2-200-32008-6 .The art and science of logic .[3] .Bonevac Daniel .Moutain View, Mayfield .(1990) .ISBN 0-87484-805-9 .The Caml Light system release 0.5. Documentation and user's manual .[4] .Leroy X., Mauny M .Rocquencourt, INRIA .(1992) .ISBN 2-7261-0748-6 .Manuel de référence du langage Caml .[5] .Leroy Xavier, Weis Pierre .Paris, InterEditions .(1993) .ISBN 2-7296-0492-8 .The implementation of functionnal languages .[6] .Peyton Jones S. L .Englewood Ciffs, Prentice-Hall .(1987) .ISBN 0-13-453333-9 PBK .Functionnal programming and parallel graph rewriting .[7] .Plasmeijer R., van Eekelen M .Wokingham, Addison-Wesley .(1993) .ISBN 0-201-41663-8 .Méthodes de logique .[8] .Quine Willard V.O

.Paris, Armand Colin .(1972) .ISBN 2-200-31081-1 .Elements of functionnal programming .[9] .Reade Chris .Wokingham, Addison-Wesley .(1989) .ISBN 0-201-12915-9 .Lire Lisp .[10] .Roy J.P., Kiremitdjian G .(1985) .Paris, Cedic .ISBN 2-7124-0573-0 .Le langage Caml .[11] .Weis Pierre, Leroy Xavier .Paris, InterEditions .(1993) .ISBN 2-7296-0493-6 .Approche fonctionnelle de la programmation .[12] .Guy Cousineau, Michel Mauny .Paris, Ediscience international .(1995) .ISBN 2-84074-114-8 .Option informatique : cours pour la Sup MPSI .[13] .Denis Monasse .Paris, Librairie Vuibert .(1996) .ISBN 2-7117-8831-8

Internet .INRIA .[1] http://pauillac.inria.fr/caml/index-fra.html /ftp://ftp.inria.fr/lang/caml-light dernière modification : 06/12/96

Mémento abstraction concrète

Syntaxe Caml .Les définitons syntaxiques décrivent les mecanismes de construction des expressions du langage Caml : La syntaxe des phrases du langage Caml est présentée en notation B.N.F. (Backus-Naur Form), sous la forme identificateur_de_phrase ::= forme_syntaxique : Dans la suite, la syntaxe d'une phrase Caml quelconque est décrite par une règle de réécriture selon le modèle partie gauche de la règle ::= partie droite. .Le symbole «::=» est appelé symbole de réécriture La syntaxe de la phrase désignée par un identificateur de phrase en italique dans la partie gauche est décrite par la .partie droite de la forme B.N.F : La partie droite de la règle de réécriture exprime la syntaxe de la phrase par une suite de symboles qui sont soit des identificateurs de phrase (en italique), Dans ce cas ils figurent aussi comme partie gauche• .(d'une autre description B.N.F., et parfois de la même description (définition récursive .(soit des symboles ou des mots-clés du langage Caml (en caractères gras non italique• Pour éviter les confusions et les ambiguités avec les symboles utilisés dans le langage Caml, les symboles B.N.F., autres que le symbole de réécriture, ne sont pas employés. Par conséquent, les formes syntaxiques alternatives ou .optionnelles, et les répétitions d'occurrences, seront définies de manière explicite, et parfois informelle

Exemple de syntaxe expression_fonctionnelle ::= function filtrage Dans cet exemple «expression_fonctionnelle» est l'identificateur de la forme de phrase expliquée par la .description B.N.F., «function» est un mot-clé de Caml et «filtrage» est un identificateur de phrase

Typage Caml .Règles de typage appliquées par le synthétiseur de types Caml : Le typage des expressions du langage Caml est présenté en langage Caml, sous la forme expression caml : expression de type caml L'expression Caml «expression caml» de la partie à gauche du symbole de typage : est typée par une expression de .type «expression de type caml» dans la partie droite Une expression de type en Caml est formée à partir d'identificateurs de types Caml et d'expressions de types Caml .combinés par des opérateurs sur les types

Exemples de typage "bonjour" : string `z` : char function x -> x + 8 : int -> int Dans ces exemples "bonjour", `z`, et (function x -> x+8) sont des expressions Caml, string, char et .(int -> int), sont des expressions de type en langage Caml

Règles de typage : Les règles de trypage sont données sous la forme Hypothèses ---------Conclusion Exemple de règle de typage Dans notre exemple, E1:bool, E2:T et E3:T sont les hypothèses. Tandis que )if E1 then E2 else .E3(:T est la conclusion de la règle E1:bool E2:T E3:T ------------------------)if E1 then E2 else E3(:T

Evaluation Caml .Principes d'évaluation des expressions Caml : L'évaluation des expressions du langage Caml est présentée sous la forme Evaluation)expression_caml( => valeur_caml est évaluée à la valeur qu'elle ‫ ق‬L'expression Caml (expression_caml) de la partie à gauche du symbole d'évaluation .exprime (valeur_caml) dans la partie droite

Exemple d'évaluation # let a = 40 ;; a : int = 40 Evaluation)a( => Evaluation)40( => 40

Evaluation)a + 5( => Evaluation)Evaluation)a( + Evaluation)5(( => Evaluation)Evaluation)40( + 5( => Evaluation)40 + 5( => Evaluation)45( => 45

Notation et symboles Symboles utilisés pour décrire le modèle de la machine Caml

Grammaire Caml .Les définitions syntaxiques du langage Caml rassemblées dernière modification : 06/12/96

Syntaxe Caml abstraction concrète Définition simple.1 Définition multiple.2 Définition locale simple.3 (Définition locale simple (variante.4 Définitions locales emboîtées et multiples.5 (Définitions locales emboîtées et multiples (variante.6 Expression conditionnelle.7 Type construit simple.8 Type construit composé.9 Type produit.10 Type enregistrement.11 Fonctions à une variable.12 (Fonctions à n variables (1 argument.13 (Fonctions à n variables (n arguments.14 Fonction : Syntaxe 1ère forme.15 Fonction : Syntaxe 2ème forme.16 Fonction : Syntaxe 3ème forme.17 Fonction : Syntaxe 4ème forme.18 Applications.19 Définition récursive simple.20 Définition récursive multiple.21 Définition récursive locale.22 (Définition récursive locale (variante.23 Filtrage par composants.24 Filtrage par valeurs.25 Filtrage par cas.26 Gardes.27 Conditionnelle par cas.28 Fonction définie par filtrage.29 Types synonymes.30 Type somme.31 Listes.32 Définition d'une exception.33

Déclenchement d'exception.34 Gestion d'exception.35 Module de définition.36 Directive.37 Type abstrait.38 Module d'interface.39 Types polymorphes.40 Contraintes de types.41 Syntaxe de flux.42 Syntaxe du filtrage de flux.43 dernière modification : 06/12/96 .44

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 .un, _deux, 'trois, 8A, carre d'as, function, then_1 Solution Manuel : Identificateurs

Expressions : Une expression Caml est soit une expression atomique ou expression élémentaire non décomposable en expressions plus simples.• Par exemple tous les identificateurs, ainsi que les constantes numériques (entières ou décimales), les chaînes de caractères, ou encore les valeurs caractères, telles que 9, 1.047, `H`, "Jean", sont des expressions .atomiques soit une expression composée ou expression formée par une combinaison d'expressions plus simples• .atomiques ou composées, et d'opérateurs

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,2301]. 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é : •

pour les fonctions qui ne reçoivent pas d'argument (unit -> T),

•

ou qui ne retournent aucun résultat (T -> unit).

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' ,)X,T'(E:T

)let X = E'in E)X((:T Evaluation de définition et modification de l'environnement Expressions Typage et évaluation (* debut de session *) ;; let a = 8# a : int = 8

Environnement global et environnements temporaires Einitial = E

E1 = )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 ,une condition, expression booléenne• une expression à évaluer si la condition est vraie : expression_alors de type quelconque T et• .une expression à évaluer si la condition est fausse : expression_sinon de type T•

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=E1;...;Cn=En(}:{C1:T1;...;Cn:Tn} ou bien

E1:T1 ... En:Tn T={C1:T1;...;Cn:Tn}

{C1=E1;...;Cn=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. 2. 3. 4.

)c + )"a" )4 > )"a"

4( >= )8 - x( ^ "b"( = c 8( = )"a" = "b"( + 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 variab

yntaxe 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

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 let let let let

cube = function x -> x * x * x cube x = x * x * x cube)x(= x * x * x cube = fun x -> x * x * x

Exemples (fonctions à plusieurs arguments) let paire = function x -> function y -> )x,y( let paire x y = )x,y( let paire)x()y(=)x,y( 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 bool( *( )string -> int( -> char )'a -> 'b( -> )'c -> 'd(

)* qui est équivalent à : int -> )int -> )* 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

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 ,une application totale de cette fonction, quand les deux arguments sont fournis (1 ;; "enchaine "Auteur : " "Richard E. Pattis# "string = "Auteur : Richard E. Pattis : ,une application partielle de cette fonction, quand un seul argument est fourni (2 ;; " : 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

1. 2. 3. 4. 5. 6. 7.

# # # # # # #

8. # 9. # 10.# 11.# 12.#

.Au cours d'une session Caml, E est l'environnement initial Typer, évaluer les phrases Caml suivantes et indiquer l'environnement : résultant let a = 5 ;; let a = a + a ;; let v = )a = 10( ;; let f = function x -> x*x + a*a ;; f 2 ;; f f 2 ;; let rec h = function 0 -> 1 | 1 -> 1 | n -> )f)n-2( + 1( * f)n-1( ;; h 7 ;; let gamma = function a -> function b -> a*b ;; let z = gamma 5 ;; gamma 8 4 ;; 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 ;; Evaluer et typer chacune des définitions )1 Décrire l'évolution de l'environnement à chaque étape )2 Décrire les fermetures des fonctions )3 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 )Fonction suivant : à un entier n on fait correspondre l'entier )n+1 .1 )Fonction precedent : à un entier n on fait correspondre l'entier )n-1 .2 Fonction double : à un entier n on fait correspondre l'entier 2*n .3 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 : 03/03/99