Ateliers

abstraction concrète


Fonctions d'ordre supérieur

Fonction : définitions

Fonction

Une fonction f est une relation entre deux ensembles A et B qui à tout élément x (antécédent) de A fait correspondre un élément unique (image) de B noté f(x).

On exprime cette définition par la notation,

f : A -> B, avec x A, f : x -> f(x) et f(x) B


dans laquelle, A est l'ensemble de définition de la fonction f,
et B, l'ensemble des éléments f(x), est l'ensemble d'arrivée de la fonction f.
L'ensemble des couples (x, f(x)) forme le graphe de la fonction f.

Une fonction x -> f(x) sera décrite, en Caml, par l'expression fonctionnelle :

function x -> f(x)

On remarquera la ressemblance des écritures entre la syntaxe Caml et la notation mathématique.

Fonction identique

La fonction identique est définie par Id : x -> x.
En Caml, sous la forme de fonction anonyme, elle correspond à l'expression fonctionnelle :

function x -> x

On peut aussi la définir comme une fonction nommée "id", par exemple :

let id(x) = x

Composition de fonctions : les fonctionnelles

Composition de fonctions

Etant donné deux fonctions f et g telles que g : A -> B et f : B -> C, la fonction composée h = f o g : A -> C est définie par h : x -> f(g(x))

On définit une nouvelle fonction k comme la fonction qui à deux fonctions f et g telles que g : A -> B et f : B -> C, fait correspondre la fonction composée f o g : x -> f(g(x)).

Définissons : La fonction h est la fonction composée de f et g, avec k(f,g) = h où h = f o g : x -> h(x) = f(g(x)), h est une fonction de A dans C. Alors, f F, g G et h H.

Et la fonction k est une fonction de composition de fonction, avec k : (f,g) -> k(f,g), k est une fonction du produit de l'ensemble F par G dans l'ensemble H.

fonction composée h : A -> C, où h : x -> h(x) = f(g(x))
fonction de composition k : F x G -> H, où k : (f,g) -> h = k(f,g)

Définition de la fonction de composition k, en Caml :

let k(f,g)= function x -> f(g(x));;
k : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b = <fun>
Dans ce cas, la fonction composée h s’obtient par l’application partielle de la fonction k, en fournissant le couple d’expressions (f,g) comme paramètre, en argument de la fonction k.

exemple :

#let f = function x -> x.[0]
 and g = function x -> string_of_int(x*2) ;;
f : string -> char = <fun>
g : int -> string = <fun>
#let h = k(f,g);;
h : int -> char = <fun>
#h 15 ;;
- : char = `3`
On peut aussi définir une fonction de composition w à un argument, telle que w : FxFxA -> C, où w(f,g,x) = f(g(x))

Définition de la fonction de composition w, en Caml :

let w(f,g,x)= f(g(x));;
w : ('a -> 'b) * ('c -> 'a) * 'c -> 'b = <fun>
Dans ce cas, la fonction composée h s’obtient par application de la règle d’abstraction à la fonction w, en construisant le triplet, argument de la fonction w, à partir des expressions de f et g, comme premier et second éléments, et en utilisant une variable liée comme troisième élément. En effet, la règle de conversion béta nous autorise à écrire que w(f,g,e) est équivalent à (function x -> w(f,g,x)) e, ce qui met en évidence l’expression fonctionnelle function x -> w(f,g,x), correspondant à la fonction h.

exemple :

(* avec les fonctions f et g de l’exemple précédent *)
#let h = function x -> w(f,g,x);;
h : int -> char = <fun>
#h 2 ;;
- : char = `4`
La fonction k apparaît alors comme une version partiellement curryfiée de la fonction w précédente. Il est simple de construire une forme totalement curryfiée de la fonction w, la fonction q.

Définition de la fonction de composition q, en Caml :

let q = function f -> function g -> function x -> f(g(x));;
q : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
Dans ce cas, la fonction composée h s'obtient par l'application partielle de la fonction q, en fournissant, consécutivement, les expressions de f et de g comme paramètres, aux arguments de la fonction q.

exemple :

(* avec les fonctions f et g de l'exemple précédent *)
#let h = q f g;;
h : int -> char = <fun>
#h 77 ;;
- : char = `1`

Typage de la fonction de composition k :

(T1 -> T2) -> (T3 -> T1) -> T3 -> T2

Si T1, T2 et T3 étant des types définis, F et G sont deux fonctions définies et correspondent au typage suivant : F : T1 -> T2 et G : T3 -> T1, alors la fonction composée h de deux fonctions F et G, correspond à l'application de la fonction k à F et à G comme il suit : let h = k F G, et en conséquence, h répond au typage : h : T3 -> T2.

Les fonctions, qui, telles que la fonction k, w ou q, reçoivent des fonctions en arguments et retournent des fonctions en résultat, sont appelées fonctions d'ordre supérieur ou fonctionnelles.

Exemples de fonctionnelles

La fonctionnelle compose

Il s'agit de la fonction q, renommée compose (Cf. Références [11], pages 78-79), en raison de la signification qui lui est attachée.
On appréciera la richesse et la souplesse du langage Caml qui offre une grande diversité de formes syntaxiques pour écrire des expressions fonctionnelles équivalentes. Par exemple, la fonction compose s'écrit indifféremment, sous les formes suivantes : On peut préférer la dernière écriture qui distingue clairement les deux arguments correspondant aux deux fonctions en les séparant du dernier argument.

Exemple avec deux fonctions à composer add_5 et mul_2 :
#let add_5 x = x+5 and mul_2 x = x*2;;
add_5 : int -> int = <fun>
mul_2 : int -> int = <fun>
#let compose f g = function x -> f(g(x));;
compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
#let u = compose add_5 mul_2 in u 3 ;;
- : int = 11

La fonctionnelle sigma

#let rec sigma = function f -> function
	0 -> f 0
   |	n -> (f n) + sigma f (n-1) ;;
sigma : (int -> int) -> int -> int = <fun>
#let somme_carrés = 
  function n ->
    let carré = function x -> x*x
    in sigma carré n;;
somme_carrés : int -> int = <fun>
#somme_carrés 10 ;;
- : int = 385

La fonctionnelle pi

#let rec pi = function f -> function
	1 -> f 1
   |	n -> (f n) * pi f (n-1) ;;
pi : (int -> int) -> int -> int = <fun>
#let produit_pairs = 
  function n ->
    let double = function x -> x+x
    in pi double n;;
produit_pairs : int -> int = <fun>
#produit_pairs 5;;
- : int = 3840

Transformation de fonctions logiques

En employant les fonctions de transformation de fonctions curry et uncurry, nous allons appliquer la transformation de fonctions à un argument et plusieurs variables, en fonctions à plusieurs arguments, aux fonctions logiques.

Les fonctions de transformation de fonctions

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

L’implication

Définition de la fonction à un argument :
let implique_paire = function 
   (true,false) -> false
 | (true,true) -> true 
 | (false,true) -> true 
 | (false,false) -> true ;;
ou bien plus simplement, ce qui est équivalent :
let implique_paire = function 
  (true,false) -> false
 | _ -> true ;;
implique_paire : bool * bool -> bool = <fun> 
Définition de la fonction transformée :
let implique = curry implique_paire ;;
implique : bool -> bool -> bool = <fun>
Application de la fonction transformée :
implique true true;;
- : bool = true
implique true false;;
- : bool = false
implique false true;;
- : bool = true
implique false false;;
- : bool = true

L’incompatibilité

Définition de la fonction à un argument :
let incompatible_paire = function
   (true,true) -> false
 | (true,false) -> true 
 | (false,true) -> true 
 | (false,false) -> true ;;
ou bien plus simplement, ce qui est équivalent :
let incompatible_paire = function
   (true,true) -> false
 | _ -> true ;;
incompatible_paire : bool * bool -> bool = <fun>
Définition de la fonction transformée :
let incompatible = curry incompatible_paire ;;
incompatible : bool -> bool -> bool = <fun>
Application de la fonction transformée :
incompatible true true;;
- : bool = false
incompatible true false;;
- : bool = true
incompatible false true;;
- : bool = true
incompatible false false;;
- : bool = true


Langages

Longueur d'une chaîne

Etant donné un ensemble fini non vide de symboles, nommé alphabet. Une chaîne formée de n symboles est dite de longueur n. L'ensemble des chaînes de longueur n est désigné par l'ensemble puissance n (n = x ... n fois... x ).
Ainsi, par exemple, 9 désigne l'ensemble des chaînes de longueur 9 (formées de neuf symboles appartenant à ).

L'ensemble 0 désigne l'ensemble contenant la chaîne de longueur 0 (chaîne nulle, formée d'aucun symbole). La chaîne nulle est notée .

0 = {}

Langage

L'ensemble * = 0 + 1 + ... + n + ... est l'ensemble de toutes les chaînes formées à partir de .

Un langage L est un sous ensemble quelconque de *.

1 désigne l'ensemble des chaînes de longueur 1 (formées d'un symbole unique appartenant à ), et par conséquent, 1 = . Ceci revient à dire qu'un symbole quelconque de est une chaîne de longueur 1.

Notation :

Une chaîne de n symboles identiques au même symbole a est notée an.

Concaténation de chaînes

Si a et b sont deux symboles de l'alphabet , alors la concaténation de a et b donne ab et la concaténation de b et de a donne ba, ab et ba sont deux chaînes de 2.
Si k est une chaîne de m et h est une chaîne de n, alors la concaténation de k et h donne kh et la concaténation de h et de k donne hk, kh et hk sont deux chaînes de m+n.
Si k est une chaîne de m et est la chaîne nulle, alors la concaténation de k et donne k et la concaténation de et de k donne k, k = k et k = k.

Exemple

Soit l'alphabet = {a; b; g}
et le langage L tel que : L = {ambng(ab)p ,
avec m >= 0 , n > 0 , et p >= 0},
alors, "bg" et "aaaabbbgababab" sont des chaînes du langage L ainsi défini, cependant que "aagab" , "abab" , et "bagba" n'appartiennent pas à L.

Automates

Automate

Dans son état initial l’automate reçoit une chaîne de symboles à reconnaître. A chaque état «pre» (pre : état avant transition), l’automate lit le symbole suivant de la chaîne en reconnaissance. Après lecture du symbole, si sa fonction de transition le permet, l’automate bascule dans l’état «post» (post : état après transition) résultant de la transition. Sinon l’automate est bloqué. L’automate réussit sa reconnaissance de la chaîne, quand il atteint un état final lors de la transition après lecture du dernier symbole.

Un automate fini A est défini par un quintuplet : A = (, Q, S0, F, ), dans lequel : La fonction de transition de l'automate décrit ses changements d'état. Quand celui-ci étant dans un état «pre» Si, reconnaît un symbole aj, sa fonction de transition le bascule dans le nouvel état «post» Sk.

Le répertoire d'instructions définit la fonction de transition de l’automate.

Définition d'une fonction de transition généralisée à l'ensemble des chaînes

On transforme la fonction : Q x -> Q en une fonction ' : Q x * -> Q, définie par :

1) a : '(Sk, a) = (Sk, a)
2) 0 : '(Sk, ) = Sk
3) m,h * : '(Sk, mh) = '('(Sk, m), h)

Exemple : l'automate A

Soit l'automate A défini par :

Répertoire d'instructions de l'automate A

  1. (S0 , ) -> S0
  2. (S0 , ) -> S1
  3. (S0 , ) -> S4
  4. (S1 , ) -> S4
  5. (S1 , ) -> S1
  6. (S1 , ) -> S2
  7. (S2 , ) -> S4
  8. (S2 , ) -> S4
  9. (S2 , ) -> S4
  10. (S3 , ) -> S4
  11. (S3 , ) -> S2
  12. (S3 , ) -> S4
  13. (S4 , ) -> S4
  14. (S4 , ) -> S4
  15. (S4 , ) -> S4
La construction de l’expression Caml de la fonction de transition de l’automate est immédiate :
let transition = function
    (S0 , ) -> S0
  | (S0 , ) -> S1
  | (S0 , ) -> S4
  |  ...
  | (S4 , ) -> S4
  | (S4 , ) -> S4

Matrice de transition de l'automate A

La matrice de transition de l’automate indique l’état final de la transition en fonction des l’état initial de l’automate, indiqué en colonne, et du symbole reconnu en entrée, indiqué en ligne.

S0S1S2S3S4
S0S4S3S4S4
S1S1S4S2S4
S4S2S4S4S4

Représentation du graphe de l'automate A

Dans la représentation graphique de l'automate, les cercles correspondent aux états de l'automate, les flèches matérialisent les transitions telles que : (état de départ de la flèche, symbole associé à la flèche) -> état d'arrivée de la flèche. La notation a1 +...+ an associée à une flèche T entre deux états Su et Sv signifie que chaque symbole ai regroupé par l'opération + est relié à une flèche Ti entre Su et Sv et orientée dans le sens de T.

L'état initial de l'automate est indiqué par le triangle noir.

L’état final S2 est marqué d’un double cercle.

Reconnaissance d'une chaîne du langage L par l'automate A

Soit la chaîne "" à reconnaître par l'automate A.

Forme impérative

Etat «pre» Phrase Transition Etat «post»
S0 "()" (S0,) -> S0 S0
S0 "()" (S0,) -> S1 S1
S1 "()" (S1,) -> S2 S2
S2 "()" (S2,) -> S3 S3
S3 "()" (S3,) -> S2 S2
S2 "( )" Chaîne reconnue S2

Dans l'approche impérative, le traitement de la chaîne par l'automate A est étudié comme l'exécution d'une séquence d'instructions.

Forme fonctionnelle

Dans l’approche fonctionnelle, le traitement de la chaîne par l’automate A est étudié comme l’évaluation de l’application de la fonction de transition généralisée à l’ensemble des chaînes ', à la chaîne à reconnaître.

E = '(S0, "") = '('(S0, ), "") = '( (S0, ), "")
comme (S0, ) = S0, on a
E = '(S0, "") = '('(S0, ), "") = '( (S0, ), "")
comme (S0, ) = S1, on a
E = '(S1, "") = '('(S1, ), "") = '( (S1, ), "")
comme (S1, ) = S2, on a
E = '(S2, "") = '('(S2, ), "") = '( (S2, ), "")
comme (S2, ) = S3, on a
E = '(S3, "") = '('(S3, ), "") = '( (S3, ), "")
comme (S3, ) = S2, on a
E = '(S2, ""), fin.
La chaîne est reconnue par l'automate A.

Diagrammes syntaxiques

Les diagrammes syntaxiques sont quelquefois utilisés dans la description des grammaires des langages. Les techniques de programmation des automates leur sont facilement applicables.

Exemple de diagramme syntaxique des expressions arithmétiques

Il s’agit d’un exemple restreint au sous-ensemble des expressions arithmétiques limitées à 3 opérations (+,- et *).

Représentation des grammaires au moyen de diagrammes syntaxiques

Les expressions sont lues de gauche à droite et les flèches suivent le parcours de lecture. Les rectangles représentent le vocabulaire non terminal de la grammaire, et les rectangles à bords arrondis ou les cercles, le vocabulaire terminal. En rapprochant cette représentation graphique de celle des automates, les points de jonction des flèches correspondent aux états de l'automate (non représentés dans le dessin).

Automate équivalent au diagramme "expression_arith"

Exemple d’expression Caml de la fonction de transition

(* Déclaration des types état et vocabulaire *)
#type état = S0 | S1
 and vocabulaire = PLUS | MOINS | TERME of terme ;;
Type état defined.
Type vocabulaire defined.

(* Déclaration des exceptions *)
#exception erreur_de_syntaxe ;;
Exception erreur_de_syntaxe defined.

(* Fonction de transition *)
#let expression_arith = function
    S0, TERME _ -> S1
  | S1, (PLUS | MOINS) -> S0 
  | _ -> raise erreur_de_syntaxe ;;
expression_arith : état * vocabulaire -> état = <fun>


Grammaires

Grammaire

Les langages de programmation sont décrits par des grammaires rigoureuses. Pour chaque langage les règles de grammaire permettent de décider si une phrase quelconque est bien exprimée dans le langage considéré.

Une grammaire formelle G est définie par un quadruplet : G = (t, n, S, R), dans lequel :

Notation BNF (Backus - Naur form)

La notation BNF est le métalangage le plus souvent utilisé dans la description des langages informatiques.

La grammaire de la notation BNF est définie par :

Exemple de grammaire décrivant les expressions arithmétiques simples

Garith = (t, n, S, R)

Exemple d'automate associé à une grammaire

Nous étudierons l’automate A_arith associé à la grammaire G_arith décrivant les expressions arithmétiques simples.

Aarith = (, Q, S0, F, )

Représentation du graphe de l'automate :

Pour simplifier, le mécanisme de la constante entière (Cste) n'est pas détaillé. Sur le graphe de l'automate, pour chaque état, les flèches de sorties ne sont pas toutes tracées. En effet, chaque état devrait être affecté du même nombre de sorties qu'il y a de symboles dans le vocabulaire du langage. Les sorties qui ne figurent pas sur le graphe peuvent être mentalement rajoutées comme entrées d'un état supplémentaire S6 (non représenté) dont toutes les sorties bouclent sur lui-même. Toutefois, dans la fonction de transition en Caml, les sorties des états sont traitées de manière exhaustive par le dernier motif de filtrage, et l'état fictif S6 y est traduit par le déclenchement de l'exception erreur_de_syntaxe.

Répertoire d’instructions de Aarith

1. (S0 ,Cste) -> S2
2. (S0 ,"(" ) -> S1
3. (S1 ,Cste) -> S3
4. (S2 , "+") -> S0
5. (S2 , "-") -> S0
6. (S2 , "*") -> S4
7. (S3 , ")") -> S2
8. (S3 , "+") -> S1
9. (S3 , "-") -> S1
10. (S3 , "*") -> S5
11. (S4 ,Cste) -> S2
12. (S4 ,"(" ) -> S5
13. (S5 ,Cste) -> S3

Définition de la fonction de transition en Caml

Dans notre exemple la chaîne des symboles lus par l’automate prend la forme d’une liste du type somme vocabulaire. Le type vocabulaire est composé des valeurs PLUS, MOINS et MULT (opérateurs +, - et *), des valeurs GPAR (parenthèse gauche) et DPAR (parenthèse droite), et de valeurs CSTE of int (constantes entières).
(* Déclaration des types état et vocabulaire *)
#type état = S0 | S1 | S2 | S3 | S4 | S5
 and vocabulaire = 
    PLUS|MOINS|MULT|GPAR|DPAR
  | CSTE of int ;;
Type état defined.
Type vocabulaire defined.
L'exception erreur_de_syntaxe est déclarée afin de récupérer les états bloqués de l’automate, ce qui revient à filtrer toutes les paires (état, symbole entré) résiduelles (celles qui conduisent à l’état fictif S6).
(* Déclaration des exceptions *)
#exception erreur_de_syntaxe ;;
Exception erreur_de_syntaxe defined.
La fonction de transition expression_arith filtre les paires formées à partir de l’état courant de l’automate «pre» et du symbole lu, et retourne le nouvel état «post». Le filtrage est établi sur le modèle (état, symbole) -> état, comme le montre le typage de la fonction. Les 13 instructions du répertoire de l’automate définissent les différents cas de filtrage, rendu exhaustif par la dernière ligne : _ -> erreur_de_syntaxe, correspondant aux transitions bloquantes.
(* Fonction de transition *)
#let expression_arith = function
    S0, CSTE _	-> S2
  | S0, GPAR	-> S1
  | S1, CSTE _	-> S3
  | S2, PLUS	-> S0
  | S2, MOINS	-> S0
  | S2, MULT	-> S4
  | S3, DPAR	-> S2
  | S3, PLUS	-> S1
  | S3, MOINS	-> S1
  | S3, MULT	-> S5
  | S4, CSTE _	-> S2
  | S4, GPAR	-> S5
  | S5, CSTE _	-> S3
  | _ -> raise erreur_de_syntaxe ;;
expression_arith : état * vocabulaire -> état = <fun>
L'automate A_arith est défini à partir de l’application d’une fonction récursive locale eval à la paire constituée de l’état courant s de l’automate et de la liste des symboles à reconnaître e::r. L’arrêt de la récursion se produit quand l’automate atteint l’état final et que la liste des symboles à lire est épuisée, alors, la paire prend la valeur (S2 ,[]). L’application de la fonction eval est évaluée avec l’état initial S0 et la liste entière des symboles à reconnaître liste_arith. Si une expression inachevée est donnée à lire, la liste des symboles se termine alors que l’automate est dans un état différent de l’état final, ce qui correspond au motif filtrant ( _, []). Par ailleurs, les états bloqués de l’automate sont détectés et récupérés par la gestion d’erreur try ... with erreur_de_syntaxe.
(* Automate A_arith *)
#let A_arith = function liste_arith ->
    let rec eval = function
       (S2, []) -> "expression reconnue"  (* S2=état final *)
     | ( _, []) -> "expression inachevée"
     | ( s, e::r) -> eval(expression_arith(s,e),r)
    in try eval (S0, liste_arith)       (* S0=état initial *)
    with erreur_de_syntaxe -> "expression erronée" ;;
A_arith : vocabulaire list -> string = <fun>

(* Test de l’automate *)
Expression à reconnaître : « 5 * ( 8 + 3 ) »
#A_arith [CSTE 5;MULT;GPAR;CSTE 8;PLUS;CSTE 8;DPAR] ;;
- : string = "expression reconnue"
Expression à reconnaître : « 5 + »
#A_arith [CSTE 5;PLUS] ;;
- : string = "expression inachevée"
Expression à reconnaître : « 5 8 + »
#A_arith [CSTE 5;CSTE 8;PLUS] ;;
- : string = "expression erronée"

Exemple de grammaire decrivant un langage L

GL = (t, n, S, R)

Représentation du graphe de la grammaire G

Reconnaissance d'une chaîne du langage L par la grammaire G

Soit la chaîne "" donnée à reconnaître par la grammaire G :
S = "" axiome .
S = "" application de la régle R0 S -> S
S = "" application de la régle R1 S -> T
S = "" application de la régle R3 T -> U
Chaîne reconnue application de la régle R6 U ->

Analyseur d’expressions du Langage L

Il s’agit, ici, d’analyser les expressions du langage L et d’en faire apparaître les structures. La grammaire du langage L révèle trois symboles non terminaux S, T et U. Ces structures vont servir de base de définition de l’analyseur syntaxique.

Il est facile de voir que les phrases de ce langage sont de la forme SnTkU, dans lesquelles n est un nombre entier positif ou nul quelconque, et k a la valeur 0 ou 1. Et, par conséquent, toutes les phrases se terminent par .

On déclare un type symbole qui regroupe les terminaux (constructeur Alpha), (constructeur Beta) et (constructeur Gamma), et les non terminaux S (constructeur S of symbole), T (constructeur T of symbole) et U (constructeur U).
#type symbole = Alpha|Beta|Gamma
   |U
   |T of symbole
   |S of symbole ;;
Type symbole defined.

#exception erreur_de_syntaxe ;;
Exception erreur_de_syntaxe defined.
La fonction analyser utilise les flux. Le filtrage des structures U fait intervenir la fonction de flux end_of_stream qui retourne la valeur () si le flux testé est vide et, sinon déclenche l’exception Parse_failure. Cette fonction est utilisée, dans le cas présent, pour déterminer si le flux est vide, après le succès du filtrage des valeurs consécutives Alpha, puis Beta.

A l’intérieur des motifs de flux filtrants, on trouve des expressions telles que, par exemple, analyser U dans [<'Gamma;analyser U>]. Ces expressions, sous forme de binôme, sont constituées d’une fonction (ici analyser) qui est appliquée au flux courant dont le résultat attendu est mentionné par la deuxième partie du binôme (ici U). Si le résultat de l’application de la fonction au flux courant est bien égal au résultat indiqué dans la deuxième partie du binôme, le filtrage réussit.

Il ne faut surtout pas confondre le binôme fonction résultat d’un motif de filtrage de flux avec l'expression d'une application fonction argument. L’argument de l’application de la fonction du binôme n’est pas apparent dans l’expression. Il a la valeur du flux à la position de la fonction dans le motif.
#let rec analyser = function
    [<'Beta;analyser (T y)>] -> S(T y) 
  | [<'Gamma;analyser U>] -> T(U) 
  | [<'Alpha ; s>] -> 
    match s with
        [<'Beta;flux>] ->
        begin try match (end_of_stream flux) 
                  with () -> U 
              with Parse_failure -> 
                      S(analyser [<'Beta;flux>])
        end
      | [] -> S(S y) ;;
analyser : symbole stream -> symbole = <fun>

(* test de l’analyseur syntaxique *)
Expression analysée : «», elle appartient au langage L.
#analyser [<'Alpha;'Alpha;'Alpha;'Beta;'Gamma;'Alpha;'Beta>] ;;
- : symbole = S (S (S (S (T U))))
Expression analysée : «», elle n’appartient pas au langage L.
#analyser [<'Alpha;'Alpha;'Beta>] ;;
Uncaught exception: Parse_failure


Etude du polymorphisme des fonctions

Définition des fonctions

Pour notre développement, nous utiliserons deux fonctions à passer comme arguments à la fonction étudiée g : La fonction g (on aurait aussi bien pu la nommer fonction appliquer) a pour définition :
let g = function h -> function x -> h x
g : ('a -> 'b) -> 'a -> 'b
Dans l'expression (g f x), que l'on peut traduire par « appliquer f à x », la fonction g applique son premier argument, une fonction quelconque f, à son deuxième argument x, ainsi que le montrent les exemples suivants d'application de la fonction g :

Application Typage Evaluation
#bis 3 ;; - : int * int = 3, 3
#g bis 3 ;; - : int * int = 3, 3
#bis id ;; - : ('a -> 'a) * ('a -> 'a) = <fun>, <fun>
#g bis id ;; - : ('a -> 'a) * ('a -> 'a) = <fun>, <fun>

Inférence de types et fonctions polymorphes

On crée la fonction f_2 qui applique deux fois, de façon cumulative, une fonction f passée en argument :
#let f_2 = function f -> function x -> f (f x)
f_2 : ('a -> 'a) -> 'a -> 'a = <fun>
Puis on applique la fonction f_2 à la fonction id
#f_2 id ;;
- : 'a -> 'a = <fun>
et ensuite, on applique la fonction f_2 à la fonction bis
#f_2 bis ;;
> Toplevel input:
>f_2 bis ;;
>    ^^^
> Expression of type 'a -> 'a * 'a
> cannot be used with type 'a -> 'a
Le type du premier argument f de la fonction f_2, soit ('a -> 'a) est d'un type incompatible avec celui de la fonction bis, soit 'a -> 'a * 'a. Cependant la fonction id est acceptée car son type est compatible avec celui de l'argument. Pour faire admettre n'importe quelle fonction en argument, il faut que le typage de la fonction fasse apparaître un premier argument du type ('a -> 'b) au lieu de ('a -> 'a).
Le type inféré par la fonction f_2 pour son premier argument est induit par son utilisation dans le corps de la fonction : quelquesoit la fonction f, celle-ci est instanciée une seule fois, au niveau de l'argument de la fonction f_2, et utilisée plusieurs fois dans le corps de la fonction (f (f x)), générant ainsi un système d'équations de types dont la solution est ('a -> 'a).

Pour contourner le problème, on définit une fonction f2 qui accepte deux arguments fa et fb pour permettre de créer deux instances différentes de fonctions ayant des types généralement différents.
#let f2 =
  function fa ->  
  function fb ->  
  function  x  -> fa (fb x) ;;
f2 : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>

L'application de la fonction f2 à la fonction bis donne : 
#f2 bis;; 
- : ('_a -> '_b) -> '_a -> '_b * '_b = <fun>
Exemple : on applique la fonction f2 à la fonction bis et à la valeur 3
#f2 bis bis 3 ;;
- : (int * int) * (int * int) = (3, 3), (3, 3)

Un exemple de typage

Comparons les expressions suivantes g :
#g;;
- : ('a -> 'b) -> 'a -> 'b = <fun>
#g g;;
- : ('a -> 'b) -> 'a -> 'b = <fun>
#g g g;;
- : ('a -> 'b) -> 'a -> 'b = <fun>
#g g g g g g g ...(* n fois *)... g;;
- : ('a -> 'b) -> 'a -> 'b = <fun>
Soient E une expression fonctionnelle quelconque et E' une expression quelconque. Rappelons la règle de typage des applications que nous désignerons par RTA dans la suite :
E:T1->T2 et E':T1
-----------------
(E E'):T2

Considérons la fonction g de l'étude précédente. Nous désignons par (E1) une expression du type de la fonction g.
Ainsi, on a g : ('a -> 'b) -> 'a -> 'b (E1).
Examinons le typage de l'application partielle de g exprimée par (g g). Pour faciliter la compréhension nous placerons un indice afin de différencier les deux instances de la fonction g dans (gf ga) = (g g). De cette façon, gf correspond à l'instance «fonction» de la fonction g et ga correspond à l'instance «argument» de la fonction g. De la même manière, afn correspond à un paramètre de type de l'instance «fonction» et aan correspond à un paramètre de type de l'instance «argument». Ce que nous traduisons par les égalités suivantes :
gf=g , af1='a , af2='a , bf1='b , bf2='b (E2)
ga=g , aa1='a , aa2='a , ba1='b , ba2='b
Alors, nous pouvons réécrire les types des instances gf et ga de g sous la forme suivante :
gf :(af1 -> bf1) -> af2 -> bf2 (E3)
ga :(aa1 -> ba1) -> aa2 -> ba2 (E4)
Par utilisation de la règle RTA dans l'application (gf ga) le type du paramètre ga est identique à celui de l'argument de gf.
Selon la règle (E4), le type de ga est :(aa1 -> ba1) -> aa2 -> ba2 (a)
Selon de la règle (E3), le type de l'argument de gf est :(af1 -> bf1) (b)

Alors, d'après (a) et (b), on peut écrire,
(af1 -> bf1) = (aa1 -> ba1) -> aa2 -> ba2 (E5)
ce qui donne le système d'équations :

Selon la règle (E5), af1 = (aa1 -> ba1 ) -> aa2 (E6)
Selon la règle (E5), bf1 = ba2 (E7)

D'autre part, selon RTA, le type de l'application (gf ga) est celui du résultat de la fonction gf c'est-à-dire,
d'après RTA, (gf ga) : af2 -> bf2 (E8)
et d'après (E2), af1 = af2 et bf1 = bf2 en remplaçant dans (E8)
on a, (gf ga) : af1 -> bf1 (E9)

A partir de (E6) et (E7) en remplaçant af1 et bf1 par les expressions de types équivalentes dans (E9)on obtient :
(gf ga) : (aa1 -> ba1) -> aa2 -> ba2 .
En conclusion d'après (E2), nous avons,
(gf ga) : ('a -> 'b) -> 'a -> 'b ,
ce qui signifie que le type de (g g) est égal au type de g.

On peut reproduire le raisonnement de typage précédent en substituant (g g) à g comme argument dans l'application (g g), puisqu'ils ont le même type. Cela entraîne que (g (g g)) est du même type que (g g) et par conséquent que g. On pose que ceci est vrai pour
(1 g (2 g ...(n g g)n ...)2 )1.
Alors, on peut construire une nouvelle application à partir de (g g) en substituant
(1 g (2 g ...(n g g)n ...)2 )1 à g comme argument dans l'application, puisqu'ils ont le même type, et cela entraîne que la nouvelle application ainsi obtenue :
( g (1 g (2 g ...(n g g)n ...)2 )1 ) est du même type que (g g) et par conséquent que g.

Les applications évaluent d'abord leurs arguments situés le plus à droite (associativité à droite), alors :
type( g (1 g (2 g ...(n g g)n ...)2 )1 ) = type(g g ...n fois... g)
et donc, type(g g ...n fois... g) = type(g)

ExpressionTypage
g('a -> 'b) -> 'a -> 'b
(g g)('a -> 'b) -> 'a -> 'b
(g g g)('a -> 'b) -> 'a -> 'b
(g g g g ...(n fois)... g)('a -> 'b) -> 'a -> 'b

Evaluation de l'application d'une fonction polymorphe

On évalue l'application (g g) avec le système de notation indicée mis en place lors de l'étude du typage de cette application au moyen de la relation (gf ga) = (g g).

Evaluation(g) (1)
=> Evaluation((function f -> function x -> f x)
=> «f~>x~>f x;Edéf »
(2)
en conclusion, (1) = (2) :
Evaluation(g) = «f~>x~>f x;Edéf » (3)
Comme gf = (function ff -> function xf -> ff xf),
et ga = (function fa -> function xa -> fa xa), par substitution dans (gf ga), nous obtenons :
Evaluation(gf ga) (4)
=> Evaluation(
(function ff -> function xf -> ff xf)
(function fa -> function xa -> fa xa )) (5)
appliquons la règle de conversion béta,
avec E/x = (function fa -> function xa -> fa xa )/ff , dans (5),
=> Evaluation((function xf ->
(function fa ->
function xa -> fa xa ) xf)) (6)
appliquons la règle de conversion béta, avec E/x = xf/fa , dans (6),
=> Evaluation((function xf ->
(function xa -> xf xa ))) (7)
appliquons la règle de conversion alpha, en changeant le nom de la variable liée, dans (7), xf en la renommant f
=> Evaluation((function f -> (function xa -> f xa )))
(8)

appliquons la règle de conversion alpha, en changeant le nom de la variable liée, dans (8) xa en la renommant x
=> Evaluation((function f -> (function x -> f x)))
(9)

dans (9), appliquons la règle d'associativité à droite de l'opérateur fonctionnel ->
=> Evaluation(function f -> function x -> f x) (10)
=> «f~>x~>f x;Edéf » (11)
en conclusion, (4) = (11) :
Evaluation(g g) = «f~>x~>f x;Edéf » (12)
en comparant (3) et (12) on tire le résultat :

Evaluation(g g) = Evaluation(g)

Réflexion à propos de quelques fonctions polymorphes

Que pensez vous de la composition des fonctions f2 et id ? Comparez (f2 id) et g de l'étude précédente :
(* application totale : 3 arguments *)
#f2 id id 6;;
- : int = 6
(* application partielle : 2 arguments *)
#f2 id id;;
- : 'a -> 'a = <fun>
(* application partielle : 1 argument *)
#f2 id ;;
- : ('a -> 'b) -> 'a -> 'b = <fun>
#(f2 id) (f2 id) (f2 id);;
- : ('a -> 'b) -> 'a -> 'b = <fun>

ExpressionTypage
g('a -> 'b) -> 'a -> 'b
f2 id('a -> 'b) -> 'a -> 'b



Transformation de fonctions

Exemple de transformations de fonctions

Fonction append

A la manière du langage Lisp, on veut écrire une fonction append (concaténation de listes), en Caml, en utilisant la fonction cons (construction de listes) :

Fonction renverse

Comme dans l'exercice précédent, on veut écrire une fonction renverse en Caml en utilisant la fonction @ (append en Caml).

Transformation des fonctions récursives

En Caml, la définition des fonctions récursives par la syntaxe « let rec id_fonction ... » nécessite la déclaration de leur nom. Le problème qui nous intéresse alors est de déterminer s'il est possible de construire des fonctions récursives anonymes dans notre langage préféré ?

Considérons la définition générale d'une fonction récursive donnée f :
(1) let rec f = function x -> (... f ...)

Par la règle d'abstraction-réduction béta, la définition de la fonction f en (1) se transforme en celle d'une application récursive (2) :
(2) let rec f = (function u -> (fun x -> (... u ...))) f

L'application (2) est de la forme ((function u ->...) f). La partie gauche de l'application fait apparaître une expression fonctionnelle dans laquelle le nom de la fonction f a été remplacé par la variable liée u, et figure en argument dans la partie droite de l'application. Pour la clarté du développement, nous désignerons cette expression fonctionnelle comme la fonction H :
(3) let H = function u -> (function x -> (... u ...))

Reprenons l'application (2), celle-ci peut être exprimée par une équation de la forme f = H f dans laquelle f est un point fixe de la fonction H,
(4) let rec f = H f (de là à penser que rec = H !)

A partir de là, notre objectif est maintenant de trouver un point fixe de la fonction H pour définr f. Pour cela nous construisons une fonction Y qui reçoit une fonction en argument et retourne un point fixe de cette fonction en résultat :
(5) let rec Y H = H (Y H)

Comparant (4) et (5), la fonction f qui nous intéresse doit être égale à Y H, alors
(6) let rec f = H f <=> let rec Y H = H (Y H)

L'équivalence (6) révèle que (Y H) est substituable à f et nous en concluons que si nous disposons d'une fonction Y satisfaisant (5), nous pourrons alors redéfinir f comme :
(7) let f = Y H

Le lambda-calcul permet d'établir l'existence d'une telle fonction Y que nous traduisons en Caml par :

let Y = fun h -> (fun x -> h(x x))(fun x -> h(x x))

Vérifions si cette définition satisfait (5) :


  • (5a) Y H = (fun h -> (fun x -> h(x x))(fun x -> h(x x))) H
    Avec la règle de conversion béta, effectuons une réduction de l’application, en substituant l’argument H à chaque occurrence de la variable liée h dans l’expression fonctionnelle de Y.
  • (5b) Y H = (fun x -> H(x x))(fun x -> H(x x))
    Avec la règle de conversion béta, effectuons une réduction de l'application, en substituant l'argument (fun x -> H(x x)) à chaque occurrence de la variable liée x dans l'expression fonctionnelle (fun x -> H(x x)) .
  • (5c) Y H = H((fun x -> H(x x))(fun x -> H(x x)))
    En examinant l’application décrite par (5c), on remarque que l’argument à droite de la fonction H, dans l’application, est la même expression que celle qui représente Y H dans (5b), donc on peut écrire (5d), et (5) est vérifiée.
  • (5d) Y H = H(Y H)

Cette définition, bien que valable pour un langage non typé tel que Lisp, conduit à un problème de typage dans l'application (x x) ou x doit avoir simultanément le type 'a, dans son rôle d'argument, et le type 'a -> 'b, dans son rôle de fonction, ce qui est interdit en Caml.

#let Y = fun h -> (fun x -> h(x x))(fun x -> h(x x));;
> Toplevel input:
>let Y = fun h -> (fun x -> h(x x))(fun x -> h(x x));;
>                              ^
> Expression of type 'a -> 'b
> cannot be used with type 'a
Alors on a recours à la définition d'un nouveau type. L'objectif consiste à utiliser un type fonctionnel polymorphe 'a -> 'a, que nous nommerons r_type, à la place du type 'a, et une version de Y, que nous nommerons F, adaptée au nouveau type.
(8) type 'a r_type = TFun of (('a r_type) -> 'a)
(9) let F = fun h -> let g(TFun f) = h(f(TFun f)) in g(TFun g)
F : ('a -> 'a) -> 'a = <fun>


Cette fonction convient pour les langages à évaluation paresseuse tels que Miranda. Mais, en Caml, un autre problème surgit, l'exécution de (F H) ne termine pas.
Ce qui nous conduit à une nouvelle adaptation F' de F. Il s'agit, pour un langage à évaluation stricte tel que Caml, de forcer le paramètre de type polymorphe 'a de F à être reconnu comme un type fonctionnel.
(10) let F' = fun h -> let g(TFun f) x = h(f(TFun f)) x in g(TFun g)
F' : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>


Appliquons ce raisonnement à la fonction factorielle
(resp. 1) let rec fact = function 0 -> 1 | x -> x*fact(x-1)
(resp. 2) let rec fact = (function u -> (function 0 -> 1 | x -> x*u(x-1))) fact
(resp. 3) let H = function u -> (function 0 -> 1 | x -> x*u(x-1))
(resp. 4) let rec fact = H fact
(resp. 5) let rec F' H = H (F' H)
(resp. 6) let fact = F' H

#type 'a r_type = Code of (('a r_type) -> 'a);; 
Type r_type defined. 
#let F' = fun h -> 
   let g(Code f) x = h(f(Code f)) x 
    in g(Code g);; 
F' : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun> 
#let H = function u -> 
             (function 0 -> 1
                     | x -> x*u(x-1));; 
H : (int -> int) -> int -> int = <fun> 
#let fact = F' H ;; 
fact : int -> int = <fun>
#fact 0, fact 2, fact 3, fact 5, fact 7 ;;
- : int * int * int * int * int = 1, 2, 6, 120, 5040


Maintenant, nous pouvons construire une fonction factorielle anonyme, en remplaçant F' et H par leurs expressions fonctionnelles.
(* factorielle anonyme selon le modèle (F' H) 8 *)
#((* <- debut de la fonction *)
     (* debut expr fonctionnelle de F' *) 
     (function h -> 
         let g(TFun f) x = h(f(TFun f)) x 
          in g(TFun g))  	  (* fin de F' *)

      (* debut expr fonctionnelle de H  *)
      (function u -> 
           (function 0 -> 1 
                   | x -> x*u(x-1)))   (* fin de H *)

               (* fin de la fonction -> *))   8 ;;
- : int = 40320


Le lambda-calcul

Les règles de transformation présentées précédement sont issues d'un modèle de calcul automatique intitulé le "lambda-calcul" ou "-calcul".

Le lambda-calcul définit des expressions simples, les lambda-expressions, pour réaliser les calculs. La syntaxe des lambda-expressions est décrite par trois formes d'expressions, les atomes, les lambda-abstractions et les lambda-applications.

Syntaxe des expressions du lambda-calcul

lambda_expression ::=
atome
| lambda_application
| lambda_abstraction
atome ::= constante | variable
lambda_application ::= (fonction argument_actuel)
lambda_abstraction ::=
(argument_formel.lambda_expression)
fonction ::= lambda_abstraction
argument_actuel ::= lambda_expression
argument_formel ::= variable

Exemples de fonction anonymes

(lx.5), La fonction constante 5
(lx.x), La fonction identique
(lx.((+ 1) x)), La fonction successeur d'un entier
(lx.+ 1 x), forme simplifiée équivalente
(lx.(ly.((+ x) y))), La fonction addition
(lx.ly.+ x y), forme simplifiée équivalente
(lx.((* 2) x)), La fonction double
(lx.* 2 x), forme simplifiée équivalente

Exemples d'applications

((lx.((+ 1) x)) 7), application successeur de 7
((lx.+ 1 x) 7 ), forme simplifiée équivalente
(((lx.(ly.((+ x) y))) 8) 3), application addition de 8 et 3
((lx.ly.+ x y) 8 3), forme simplifiée équivalente
((lx.((* 2) x)) 5), application double de 5
((lx.* 2 x) 5), forme simplifiée équivalente

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

La première règle de conversion établit que le choix de l'identificateur de la variable liée (paramètre formel) de la fonction est indifférent. Par conséquent, il est permis de lui substituer n'importe quel autre identificateur, à condition que le nouvel identificateur choisi pour la variable liée soit différent de tout autre identificateur dans la lambda-expression. La notation e[y/x] signifie la substitution de la variable y à toutes les occurrences de la variable x dans l'expression e.

Règle : lx.e est équivalent- à lx.e[y/x]

Exemple

(lx.(* 2) x) est équivalent- à (ly.(* 2) y)

Contre-exemple

(lx.y x) n'est pas équivalent- à (ly.y y) car y est utilisé comme variable libre dans (lx.y x)

Contre-exemple

(lx.(ly.(y x))) n'est pas équivalent- à (ly.(ly.(y y))) car y est déja utilisé pour une autre variable liée dans (lx.(ly.(y x)))

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

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

La notation e[E/x] signifie la substitution de E à la variable x dans l'expression e.

Règle : ((lx.e) E) est équivalent- à e[E/x]

Exemple

(lx.(* 2) x) 3 est équivalent- à ((* 2) 3)

Règle d'extensionnalité : conversion éta

Si e est une lambda-expression décrivant une fonction, la troisième règle de conversion établit une équivalence fonctionnelle entre l'expression e et la lambda-abstraction formée par (lx.(e x)), à condition que x ne soit pas une variable libre de e.

Règle : (lx.(e x)) est équivalent- à e

Exemple

(lx.(ly.(y 2)) x) est équivalent- à (ly.(y 2))

Contre-exemple

(lx.(ly.(y x)) x) n'est pas équivalent- à (ly.(y x)) (conflit de noms)

Contre-exemple

(lx.4 x) n'est pas équivalent- à 4 (4 n'est pas une fonction, c'est une constante)

La transformation des expressions Caml en lambda-expressions

Syntaxe concrète des expressions Caml :

Notre étude se limitera à la transformation d'expressions Caml très simples, réduites aux atomes (constantes et variables), aux fonctions anonymes et aux applications, selon modèle suivant :
expression_Caml ::=
    variable | constante 
  | ( expression_Caml expression_Caml )
  | ( function variable -> expression_Caml )
Selon cette grammaire, très restreinte, une expression quelconque sera représentée par :

Syntaxe abstraite des expressions Caml :

Dans la machine, les expressions du modèle de syntaxe concrète précédent seront représentées, comme une arborescence de syntaxe abstraite, par la déclaration du type fun_expression :
type fun_arg = Function of string
 and fun_expression =
   VarCaml of string | NumCaml of int | StrCaml of string
 | AppCaml of fun_expression * fun_expression
 | FctCaml of fun_arg * fun_expression ;;
La transformation des phrases de syntaxe concrète Caml en expressions de syntaxe abstraite est réalisée en deux phases : l'analyse lexicale (fonction lexemes_of_string) et l'analyse syntaxique (fonction analyser).

Syntaxe concrète des lambda-expressions :

La syntaxe concrète des lambda-expressions est décrite par le modèle suivant :
lambda_expression :=
    variable | constante
  | ( expression_Caml  expression_Caml )
  | ( l variable . expression_Caml )

Syntaxe abstraite des lambda-expressions :

Le modèle de représentation en machine correspond à la déclaration du type lambda_expression :
type lambda_abstraction = Lambda of string
 and lambda_expression = S | K | I
 | Var of string | Num of int | Str of string
 | App of lambda_expression * lambda_expression
 | Fct of lambda_abstraction * lambda_expression ;;
Remarque : les constructeurs S, K et I sont introduits dans la déclaration du type lambda_expression, dès maintenant, mais ne seront exploités que dans la partie suivante concernant les combinateurs.

Le transformateur fun_to_lambda :

La fonction fun_to_lambda , réalise la conversion des expressions Caml en lambda-expressions.
fun_to_lambda : fun_expression -> lambda_expression

let rec fun_to_lambda = function
   VarCaml v -> Var v | NumCaml n -> Num n | StrCaml s -> Str s
 | AppCaml (e1,e2) -> App (fun_to_lambda e1,fun_to_lambda e2)
 | FctCaml (Function x,e) -> Fct (Lambda x,fun_to_lambda e) ;;


Analyse lexicale d'une chaîne de caractères contenant une expression

La chaîne de caractère définissant l'expression Caml est découpée en liste de valeurs du type lexeme. On distingue quatre sortes de valeurs du type lexeme, Sym of string pour les symboles tels que "->", Id of string pour les identificateurs, Ent of string pour les constantes nombres entiers, et Chn of string pour les constantes chaînes de caractères. Le contrôle des cas d'erreur est réalisé au moyen d'une exception numérotée erreur_lexicale num. L'analyse lexicale effectuée par la fonction principale analex fait intervenir un filtrage associant des fonctions prédicats et des fonctions secondaires d'analyse lexicale. Certaines fonctions sont utilisées en commun par plusieurs autres fonctions, elles ont été regroupées comme fonctions auxiliaires.

Types, exceptions et prédicats

(* Types *) 
type lexeme =
   Sym of string | Id of string | Ent of string | Chn of string ;;

(* Exceptions *) 
exception erreur_lexicale of int ;;

(* Fonctions prédicats *) 
let separateur x = mem x [" ";"\n";"\t"]
and chaine  x    = mem x ["\""]
and special x    = mem x [">";"-";"(";")"]
and symbole x    = mem x ["function";"add";"sub";"mul";"div";
                          "eq";"inf";"sup";"->";"(";")"] ;;

Fonctions auxiliaires

(* Fonctions auxiliaires *) 
let sym_ou_id x = if symbole x then Sym x else Id x ;;
let intervalle (deb,fin) = function s ->
  let n = int_of_char (nth_char s 0) in
  (n >= int_of_char deb)&(n <= int_of_char fin) ;;
let lettre  c = (intervalle (`a`,`z`) c) or (intervalle (`A`,`Z`) c)
and chiffre c =  intervalle (`0`,`9`) c ;;
let rec enchaine = function [] -> "" | x::R -> x^(enchaine R) ;;
let hd_str s = if s = "" then "" else sub_string s 0 1
and tl_str s = if s = "" then "" else sub_string s 1 (string_length s - 1) ;;

Fonctions d'analyse lexicale

(* Fonction principale d'analyse lexicale *) 
let rec analex s =
  match (hd_str s,tl_str s) with
    ("","") -> []
  | ( x, R) ->
    if separateur x  then analex R  else
    if lettre  x     then mot x  R  else
    if chiffre x     then num x  R  else
    if chaine  x     then str "" R  else
    if special x     then sym x  R  else
    raise(erreur_lexicale 0)

(* Fonctions secondaires d'analyse lexicale *) 
and str c s =
  match (hd_str s,tl_str s) with
    ("","") -> [Chn c]
  | ( x, R) -> if chaine x then (Chn c)::(analex R)
            else str (c^x) R
and num n s =
  match (hd_str s,tl_str s) with
    ("","") -> [Ent n]
  | ( x, R) -> if chiffre x then num (n^x) R
            else (Ent n)::(analex (x^R))
and sym z s =
  match (hd_str s,tl_str s) with
    ("","") -> if symbole z then [Sym z] else raise(erreur_lexicale 1)
  | ( x, R) -> if symbole z then (Sym z)::(analex (x^R))
            else if special x then mot (z^x) R
            else raise(erreur_lexicale 2)
and mot m s =
  match (hd_str s,tl_str s) with
    ("","") -> [sym_ou_id m]
  | ( x, R) -> if (lettre x) or (chiffre x) then mot (m^x) R
            else (sym_ou_id m)::(analex (x^R)) ;;


Analyse syntaxique d'une liste de chaînes de caractères exprimant une expression

La fonction principale d'analyse syntaxique anasyn traite une liste de lexèmes et retourne l'expression Caml abstraite correspondante comme valeur du type fun_expression. Lorsqu'une parenthèse ouvrante est détectée par anasyn, la fonction parenthese traite la liste de lexèmes qui lui est fourni en argument, et retourne une paire constitué d'une expression Caml abstraite du type fun_expression correspondant à l'expression entre parenthèses comme premier élément de la paire, et de la liste de lexèmes résiduelle comme deuxième élément de la paire. La fonction parenthese tient compte des niveaux de parenthèses imbriquées.

Fonctions d'analyse syntaxique

(* Exceptions *) 
exception erreur_de_syntaxe of int ;;

(* Fonctions d'analyse syntaxique *) 
let rec parenthese n a = function
    [] -> raise (erreur_de_syntaxe 3)
  | (Sym "(")::R ->
    if n=0 then a,R else parenthese (n-1) (a@[Sym "("]) R
  | (Sym ")")::R -> parenthese (n+1) (a@[Sym ")"]) R
  | x::R -> parenthese n (a@[x]) R ;;

let rec anasyn = function
    [] -> raise (erreur_de_syntaxe 0)
  | (Sym "function")::(Id v)::(Sym "->")::R ->
      FctCaml(Function v,anasyn R)
  | ((Sym "(")::R) as lexliste -> app lexliste
  | [(Sym x)] -> VarCaml x
  | [(Id  v)] -> VarCaml v
  | [(Ent n)] -> NumCaml (int_of_string n)
  | [(Chn x)] -> StrCaml x
  | lexliste -> app lexliste

and app lexliste =
  match rev lexliste with
    [] -> raise (erreur_de_syntaxe 1)
  | (Sym ")")::R ->
      let (paren,reste) = parenthese 0 [] R in
        if reste = [] then anasyn (rev paren)
        else AppCaml(anasyn (rev reste),anasyn (rev paren))
  | der::Deb -> if Deb = [] then raise (erreur_de_syntaxe 2)
      else AppCaml(anasyn (rev Deb),anasyn [der]) ;;
Avec (rev lexliste) on inverse la liste de lexemes pour traiter l'associativité à gauche, en commençant avec le dernier élément, puis on rétablit l'ordre initial de la liste résiduelle avec (rev Deb).

let analyser s = anasyn(analex s) ;;

L'imprimeur de lambda-expressions :

La fonction lambda_string assure la construction d'une chaîne de caractères représentant une lambda_expression donnée comme argument en syntaxe lambda concrète. Le symbole lambda "l" est représenté par "L_". Alors nous pouvons construire la fonction de conversion d'une chaîne de caractères de syntaxe concrète Caml en une chaîne de caractères de syntaxe concrète lambda.
let rec lambda_string = function
    Fct(Lambda x,Var y) -> ("(L_"^x^"."^y^")")
  | Fct(Lambda x,K) -> ("(L_"^x^".K)")
  | Fct(Lambda x,I) -> ("(L_"^x^".I)")
  | Fct(Lambda x,S) -> ("(L_"^x^".S)")
  | Fct(Lambda x,App(e1,e2) ) ->
      ("(L_"^x^".("^(lambda_string e1)^" "^(lambda_string e2)^"))")
  | Fct(Lambda x,e) ->
      ("(L_"^x^"."^(lambda_string e)^")")
  | App(e1,e2) -> ("("^(lambda_string e1)^" "^(lambda_string e2)^")")
  | K -> "K" | S -> "S" | I -> "I"
  | Var x -> x | Str x -> x | Num x -> string_of_int x ;;
let caml_to_lambda s =
  lambda_string(fun_to_lambda(analyser s)) ;;

Exemple de conversion d'une chaîne Caml en lambda-expression

L'expression Caml à convertir en lambda-expression sera la chaîne :

"(((function x -> (function y -> y x)) 1) 2)"
(* chaine initiale : syntaxe concrète fun *)

(* la fonction f permute deux arguments  f x y = y x *)
let s1 = "(function x -> (function y -> y x))" ;;

(* application de la fonction permute 2 arguments *)
let s2 = "(((function x -> (function y -> y x)) 1) 2)" ;;

(* liste des lexemes *)
let lex_1 = analex s1 ;;
lex_1 : lexeme list = [Sym "("; Sym "function"; Id "x"; Sym "->"; Sym "("; Sym "function"; Id "y"; Sym "->"; Id "y"; Id "x"; Sym ")"; Sym ")"]

let lex_2 = analex s2 ;;
lex_2 : lexeme list = [Sym "("; Sym "("; Sym "("; Sym "function"; Id "x"; Sym "->"; Sym "("; Sym "function"; Id "y"; Sym "->"; Id "y"; Id "x"; Sym ")"; Sym ")"; Ent "1"; Sym ")"; Ent "2"; Sym ")"]

(* chaine initiale : syntaxe abstraite fun_expression *)

let fun_e1 = anasyn(lex_1) ;;
fun_e1 : fun_expression = FctCaml (Function "x", FctCaml (Function "y", AppCaml (VarCaml "y", VarCaml "x")))

let fun_e2 = anasyn(lex_2) ;;
fun_e2 : fun_expression = AppCaml (AppCaml (FctCaml (Function "x", FctCaml (Function "y", AppCaml (VarCaml "y", VarCaml "x"))), NumCaml 1), NumCaml 2)

(* conversion fun_expression -> lambda_expression *)

let lam_e1 = fun_to_lambda fun_e1 ;;
lam_e1 : lambda_expression = Fct (Lambda "x", Fct (Lambda "y", App (Var "y", Var "x")))

let lam_e2 = fun_to_lambda fun_e2 ;;
lam_e2 : lambda_expression = App (App (Fct (Lambda "x", Fct (Lambda "y", App (Var "y", Var "x"))), Num 1), Num 2)

(* chaine finale : syntaxe concrete lambda *)

lambda_string lam_e1 ;;
- : string = "(L_x.(L_y.(y x)))"

lambda_string lam_e2 ;;
- : string = "(((L_x.(L_y.(y x))) 1) 2)"


Les combinateurs

Les combinateurs K, C, W, B, S, T, I, S', B' et C'

Les combinateurs K, C, W, B, S, T, I, S', B' et C' sont des fonctions d'ordre supérieur utilisées dans l'implémentation du lambda-calcul, et leur définition en Caml peut être décrite par :
let K x y = x ;;	(* K élimine son dernier argument y *)
let C f x y = f y x ;;	(* C applique f à la permutation de ses deux arguments x et y *)
let W f x = f x x ;;	(* W applique f à la duplication de x *)
let B f g x = f (g x) ;;	(* B compose f et g *)
let S f g x = f x (g x) ;;	(* S distribue x par rapport à f et g *)
let T x f = f x ;;	(* T échange les roles de la fonction et de l'argument *)
let I x = x ;;	(* I est la fonction identique *)
let S' c f g x = c (f x) (g x) ;;	
let B' c f g x = c f (g x) ;;	
let C' c f g x = c (f x) g ;;	
Parmi les combinateurs présentés, deux ont un rôle essentiel, les combinateurs S et K. A partir des définitions de S et K, il est aisé de montrer que (S K K) est équivalent à la fonction identique I. En effet, S K K x = K x (K x), d'autre part, K x (K x) retourne son premier argument x, ce qui revient à dire que : S K K x = x.

Exercice :

La transformation lambda_to_iks : La lambda-machine

Traduisons la définition Caml des combinateurs I, K et S en lambda-expressions :

La fonction anonyme Caml (function x -> x) définit la fonction identique. La lambda-abstraction équivalente s'écrit (L_x.x). Le combinateur correspondant est I. Ceci nous donne notre première règle de conversion IKS selon laquelle (L_x.x) se réécrit I.

La lambda-expression équivalente à K = (function x -> (function y -> x)), s'écrit (L_x.(L_y.x)). L'application partielle de la fonction K à u donne ((L_x.(L_y.x))u), équivalente- à (L_y.u). Nous pouvons donc écrire une deuxième règle de conversion où (L_y.u) se réécrit (K u).

La lambda-expression équivalente à :
S = (function f -> 
    (function g -> (function x -> f x (g x))))
s'écrit, (L_f.(L_g.(L_x.((f x) (g x))))). L'application partielle de la fonction S à (Ly.e1) et (Ly.e2) donne (((L_f.(L_g.(L_x.((f x) (g x))))) (Ly.e1)) (Ly.e2)), équivalente- à (L_x.(((Ly.e1) x) ((Ly.e2) x))), dans cette nouvelle expression, l'application ((Ly.e1) x) est équivalente- à e1 avec substitution de x à y, dans toutes ses occurences, dans l'expression e1. En reproduisant le même raisonnement pour l'application, ((Ly.e2) x) est équivalente- à e2. Nous obtenons une troisième règle de conversion, (L_x.(e1 e2)) se réécrit (S (Lx.e1)(Lx.e2)).

Règles de conversion trans

A partir des trois règles de conversion précédentes, il s’agit ici de réaliser une transformation des lambda-expressions en expressions de combinateurs I, K ou S, selon les relations lambda -> IKS suivantes :

Conversion (lambda -> IKS)
trans(Lx.x) -> I
trans(Lx.u) -> K u
trans(Lx.(e1 e2)) -> (S trans(Lx.e1)) trans(Lx.e2)
trans(Lx.e) -> trans(Lx. trans(e))
trans(e1 e2) -> trans(e1) trans(e2)
trans(e) -> e

Introduisons, en Caml, les définitions des règles de conversion trans :

lambda_to_iks : lambda_expression -> lambda_expression

let rec lambda_to_iks = function
    Fct(Lambda x,Var y) -> if x=y then I else App(K,Var y)
  | Fct(_,Str y) -> App(K,Str y)
  | Fct(_,Num y) -> App(K,Num y)
  | Fct(_,K) -> App(K,K)
  | Fct(_,I) -> App(K,I)
  | Fct(_,S) -> App(K,S)
  | Fct(x,App(e1,e2) ) ->
      App(App(S,lambda_to_iks (Fct(x,e1)) ),
                lambda_to_iks (Fct(x,e2))   )
  | Fct(x,e) -> lambda_to_iks (Fct(x, lambda_to_iks (e)))
  | App(x,y) -> App(lambda_to_iks x, lambda_to_iks y)
  | x -> x ;;
Ainsi nous pouvons construire la fonction de conversion d'une chaîne de caractères de syntaxe concrète Caml en chaîne de caractères de syntaxe concrète lambda exprimée au moyen des combinateurs S, K et I.
let caml_to_iks s =
  lambda_string(lambda_to_iks(
    fun_to_lambda(analyser s))) ;;

Optimisation opt

On remarque que ((S (K e1)(K e2)) a) se développe en (((K e1) a)((K e2) a)), puis se réduit à l'application (e1 e2). D'autre part, (K(e1 e2) a) se réduit aussi à l'application (e1 e2). Alors, (S (K e1)(K e2)) est équivalent à K(e1 e2).

D'autre part, ((S (K e) I) a) se développe en (((K e) a) (I a)), puis se réduit à l'expression (e a). Alors,(S (K e) I) se réduit en e.

Optimisation
opt(S (K e1) (K e2)) -> K (opt(e1) opt(e2))
opt(S (K e) I) -> e

Donnons une définition Caml de la réduction opt :

reduction_ski : lambda_expression -> lambda_expression

(* version optimisee *)

let rec lambda_to_iks_opt = function
    Fct(Lambda x,Var y) -> if x=y then I else App(K,Var y)
  | Fct(_,Str y) -> App(K,Str y)
  | Fct(_,Num y) -> App(K,Num y)
  | Fct(_,K) -> App(K,K)
  | Fct(_,I) -> App(K,I)
  | Fct(_,S) -> App(K,S)
  | Fct(x,App(e1,e2) ) -> optimise_ski(
      App(App(S,lambda_to_iks_opt (Fct(x,e1)) ),
                lambda_to_iks_opt (Fct(x,e2))   )     )
  | Fct(x,e) -> lambda_to_iks_opt (Fct(x, lambda_to_iks_opt (e)))
  | App(x,y) -> App(lambda_to_iks_opt x, lambda_to_iks_opt y)
  | x -> x

and optimise_ski = function
  App( App(S, App(K,x)), App(K,y)) ->
       App(K, App(optimise_ski x,optimise_ski y))
| App( App(S, App(K,x)), I) -> optimise_ski x
| x -> x  ;;

let caml_to_opt s =
  lambda_string(lambda_to_iks_opt(
    fun_to_lambda(analyser s))) ;;

Exemples :

lambda_to_iks lam_e1;;
- : lambda_expression = App (App (S, App (App (S, App (K, S)), App (K, I))), App (App (S, App (K, K)), I))

lambda_string (App (App (S, App (App (S, App (K, S)), App (K, I))), App (App (S, App (K, K)), I))) ;;
- : string = "((S ((S (K S)) (K I))) ((S (K K)) I))"

lambda_to_iks( lam_e2;;
- : lambda_expression = App (App (App (App (S, App (App (S, App (K, S)), App (K, I))), App (App (S, App (K, K)), I)), Var "1"), Var "2")

lambda_string (App (App (App (App (S, App (App (S, App (K, S)), App (K, I))), App (App (S, App (K, K)), I)), Var "1"), Var "2")) ;;
- : string = "((((S ((S (K S)) (K I))) ((S (K K)) I)) 1) 2)"

Règles de réduction red (IKS -> SKI)

Il s'agit, ici, de traiter les réductions dans le cas des applications des combinateurs S, K et I.
Réduction (IKS -> SKI)
red(S a b c) -> red(red(a c) red(b c))
red(K a b) -> a
red(I a) -> a

définition Caml de la réduction red :

reduction_ski : lambda_expression -> lambda_expression

let rec reduction_ski = function
  App(App(App(S, x), y), z) ->
  reduction_ski(App(App((reduction_ski x),(reduction_ski z)),
  (reduction_ski(App((reduction_ski y),(reduction_ski z)))) ) )
| App(App(K, x), y) -> (reduction_ski x)
| App(I, x)-> (reduction_ski x)
| App(x, y)-> let u = App((reduction_ski x),(reduction_ski y))
    in if u=App(x, y) then u else reduction_ski u
| x -> x  ;;
Nous pouvons construire la fonction d'évaluation d'une chaîne de caractères de syntaxe concrète Caml convertie en lambda-expression exprimée au moyen des combinateurs S, K et I et réduite.
let caml_to_ski s =
  lambda_string(reduction_ski(lambda_to_iks_opt(
    fun_to_lambda(analyser s)))) ;;

Exemples

reduction_ski(App (App (App (App (S, App (App (S, App (K, S)), App (K, I))), App (App (S, App (K, K)), I)), Var "1"), Var "2"));;
- : lambda_expression = App (Var "2", Var "1")

lambda_string (App (Var "2", Var "1"));;
- : string = "(2 1)"

Exemples récapitulés

(* fonction permute deux arguments  f x y = y x *)
let s1 = "(function x -> (function y -> y x))" ;;
caml_to_lambda s1;;
- : string = "(L_x.(L_y.(y x)))"
caml_to_iks s1;;
- : string = "((S ((S (K S)) (K I))) ((S (K K)) I))"
caml_to_opt s1;;
- : string = "((S (K (S I))) K)"
caml_to_ski s1;;
- : string = "((S (K (S I))) K)"

(* application de la fonction permute deux arguments *)
let s2 = "(((function x -> (function y -> y x)) 1) 2)" ;;
caml_to_lambda s2;;
- : string = "(((L_x.(L_y.(y x))) 1) 2)"
caml_to_iks s2;;
- : string = "((((S ((S (K S)) (K I))) ((S (K K)) I)) 1) 2)"
caml_to_opt s2;;
- : string = "((((S (K (S I))) K) 1) 2)"
caml_to_ski s2;;
- : string = "(2 1)"

Retour au début du document

dernière modification : 06/12/96