6.5 Compilation du l-calcul
Cette section décrit une machine à environnement pour l'évaluation paresseuse, appelée
machine de Krivinne, qui est le modèle le plus simple pour la compilation du l-calcul.
6.5.1 Évaluateur de l-calcul
Le schéma d'évaluation d'un l-terme est le suivant :
| env |
terme |
pile |
env |
terme |
pile |
| e |
c |
S |
e |
c |
S |
| e |
MN |
S |
e |
M |
(N.e::S) |
| er |
l x.M |
s::S |
(e,s)r,x |
M |
S |
| (e,(M.e2))r,x |
x |
S |
e2r |
M |
S |
| (e,a)r,y |
x |
S |
er |
x |
S |
où l'environnement contient des couples (termes,environnement), c'est à dire des valeurs
calculables.
Le type Caml suivant correspond aux termes ou expressions de ce l-calcul étendu :
type expr =
*
Kapp of expr * expr
*
Kid of string
*
Klambda of string * expr
*
;;
*
Type expr defined.
6.5.2 Instructions de la machine
La machine suivante (dérivée de la machine de Krivinne) comporte 3
instructions la compilation du l-calcul et un étiquetage.
-
Grab : met le sommet de pile dans l'environnement
- Push label : met le label et l'environnement dans la pile
- Acces n : accès à la n-ième variable de l'environnement
- Label label : étiquetage
Les types Caml suivants :
type instr =
*
Grab (*met le sommet de la pile dans l'environnement *)
*
Push of int (* *)
*
Access of int (*acces à la n-ieme variable de l'environnement *)
*
Label of int (*etiquetage d'une partie de code *)
*
;;
*
Type instr defined.
type instrI =
*
GrabI (*met le sommet de la pile dans l'environnement *)
*
PushI of int (* *)
*
AccessI of int (*acces à la n-ieme variable de l'environnement *)
*
;;
*
Type instrI defined.
correspondent respectivement aux instructions de l'assembleur et aux instructions machine
(après assemblage).
6.5.3 Schéma de compilation
On note [M]r la compilation du terme M dans l'environnement r.
-
[MN]r = Push l; [M]r; Label l; [N]r
- [l x.M]r = Grab; [M]r,x
- [x]r = Acces n (où n est la position de x dans r)
Les deux fonction new_label et reset_label manipulent
le compteur des nouveaux numéros de label.
let new_label,reset_label =
*
let c = ref 0 in
*
( function () ® (incr c)!c),(function () ® c:=0!c)
*
;;
*
reset_label : unit ® int = áfunñ
*
new_label : unit ® int = áfunñ
La variable globale aCompiler contient des morceaux de code à compiler par la suite.
let aCompiler = ref ([ ]:instr list);;
*
aCompiler : instr list ref = ref [ ]
Les deux fonctions principales de ce compilateur sont
mk_lab pour la création et le placement de nouveaux labels et la fonction
compiler qui traduit les l-termes en instructions machine.
let rec mk_lab env term = let lab = new_label() in
*
(aCompiler := ( Label lab)::((compiler env term)@(!aCompiler))
*
lab)
*
and
*
compiler env = function
*
Kid v ® [ Access ((index v env)+1) ]
*
Klambda (v,e) ® Grab::(compiler (v::env) e)
*
Kapp (f,a) ® let u = (mk_lab env a) in
*
Push u :: (compiler env f)
*
;;
*
mk_lab : string list ® expr ® int = áfunñ
*
compiler : string list ® expr ® instr list = áfunñ
Enfin la fonction cc initialise les variables globales de compilation
et compile un terme à partir d'un environnement vide.
let cc e = reset_label()
*
aCompiler :=[ ]
*
let sub_code = (compiler [ ] e)
*
in sub_code @ (!aCompiler)
*
;;
*
cc : expr ® instr list = áfunñ
6.5.4 Schéma d'évaluation
Une fois les l-termes traduits en instructions machine, il est nécessaire
d'avoir un interprète de cette machine virtuelle. Voici le schéma d'évaluation
des instructions de cette machine :
| env |
code |
pile |
env |
code |
pile |
| e |
Push l;C |
S |
e |
C |
(l.e)::S |
| e |
Grab; C |
s::S |
(e,s) |
C |
S |
| e |
(*)Grab;C |
() |
arrêt |
sur |
(e,*) |
| (e,(l.e2)) |
Acc 0;C;Label l; C2 |
S |
e2 |
C2 |
S |
Un des points importants est le critère d'arrêt. L'instruction Grab
correspond à une abstraction. S'il n'y a pas d'argument sur la pile, cette abstraction
ne trouve donc pas d'argument et le calcul s'arrête. Il n'y a pas de réduction sous le l.
Le programme Caml suivant effectue une passe d'assemblage des instructions de type instr
et évalue le résultat, une liste d'instructions instrI.
Pour faire disparaître les labels, il est nécessaire de connaître la longueur de chaque instruction :
let longueur_code = function
*
Grab ® 1
*
Push ® 1
*
Access ® 1
*
Label ® 0
*
;;
*
longueur_code : instr ® int = áfunñ
La fonction pass_one associe à chaque label l'adresse de
l'instruction étiquetée.
let pass_one =
*
let rec pass_rec pc = function
*
[ ] ® [ ]
*
Label n :: rest ® (n,pc):: pass_rec pc rest
*
instr :: rest ® pass_rec (pc+(longueur_code instr)) rest
*
in pass_rec 1
*
;;
*
pass_one : instr list ® (int * int) list = áfunñ
La fonction assemble traduit du code assembleur (intsr list)
en code machine (instrI list).
let assemble code =
*
let list_label = pass_one code
*
in
*
let rec asm = function
*
[ ] ® [ ]
*
Label n :: rest ® asm rest
*
Push l:: rest ® PushI (assoc l list_label) :: asm rest
*
Grab :: rest ® GrabI :: asm rest
*
Access n :: rest ® AccessI n :: asm rest
*
in
*
asm code
*
;;
*
assemble : instr list ® instrI list = áfunñ
type closure = C of int * (closure list) ref
*
;;
*
Type closure defined.
let rec nth l a = match l with
*
[ ] ® failwith ``nth''
*
h::t ® if a=1 then h else nth t (a-1)
*
;;
*
nth : a list ® int ® a = áfunñ
La fonction interprete exécute le code machine
passé comme argument et retourne une fermeture (closure).
let interprete code =
*
let rec interp env pc stack = match (nth code pc) with
*
AccessI n ® (try
*
let u = nth env n
*
in
*
match u with
*
(C (n,e)) ® interp !e n stack
*
with
*
x ® (C (pc, ref env)))
*
PushI n ® interp env (pc+1) ((C (n,ref env))::stack)
*
GrabI ® (match stack with
*
[ ] ® (C (pc,ref env))
*
so::S ® interp (so::env) (pc+1) S)
*
in
*
interp [ ] 1 [ ]
*
;;
*
interprete : instrI list ® closure = áfunñ
Enfin la fonction Kall interprète le code compilé et assemblé
d'un l-terme.
let Kall exp = interprete (assemble (cc exp))
*
;;
*
Kall : expr ® closure = áfunñ
6.5.5 Exemples
let EX1 =
*
(Kapp
*
((Kapp
*
((Klambda (``f'',(Klambda (``x'',(Kapp ((Kid ``f''),(Kid ``x''))))))),
*
(Klambda (``x'',(Kid ``x''))))),
*
(Klambda (``x'',(Kid ``x'')))))
*
;;
*
EX1 : expr = Kapp (Kapp (Klambda (``f'', Klambda (``x'', Kapp (Kid ``f'', Kid ``x''))),
*
Klambda (``x'', Kid ``x'')), Klambda (``x'', Kid ``x''))
cc EX1;;
*
- : instr list = [ Push 1 Push 2 Grab Grab Push 3 Access 2 Label 3 Access 1
*
Label 2 Grab Access 1 Label 1 Grab Access 1 ]
assemble (cc EX1);;
*
- : instrI list = [ PushI 10 PushI 8 GrabI GrabI PushI 7 AccessI 2
*
AccessI 1 GrabI AccessI 1 GrabI AccessI 1 ]
interprete (assemble(cc EX1));;
*
- : closure = C (10, ref [ ])
6.5.6 Exercices
-
Ajouter un mode debug pour la fonction interprète qui
trace l'état de la pile, de l'environnement et du compteur ordinal.
- Étendre le l-calcul traité
par le compilateur aux déclarations locales
let in et let rec in.
Décrire l'évaluation de ces nouveaux termes, les instructions machines correspondantes,
leur schéma de compilation et d'évaluation, et le nouveau compilateur et interprète
associés.
6.5.7 Bibliographie
-
S. L. Peyton Jones. ``The implementation of Functional Programming Languages''
Prentice Hall - 1987
Ce livre a été traduit par Michel Mauny et éditer chez Masson.