Compilation de Mini-Scheme/Mini-ML en instructions pour une machine à environnement

Projet de Langages Fonctionnels et Programmation Fonctionnelle

avril 1995

Le but de ce projet est d’écrire, en Caml-Light, un compilateur pour, au choix, le noyau du langage Scheme, appelé pour l’occasion Mini-Scheme, ou, un ML restreint, appelé Mini-ML. Pour Mini-Scheme comme pour Mini-ML les liaisons seront lexicales et l’ordre d’évaluation par valeur de gauche à droite (à l’exception, bien sûr, des conditionnelles).

Le langage cible ne sera pas le langage machine de tel ou telle machine mais un langage de bas niveau portable (dit aussi bytecode) constitué d’instructions pour une machine d’exécution abstraite.

Le compilateur devra accepter des programmes Mini-Scheme (fichiers d’extension .miniscm) ou Mini-ML (fichiers d’extension .miniml) et produire des fichiers exécutables.

Il sera nécessaire d’écrire un interpréteur pour exécuter les instructions de la machine abstraite. Cet interpréteur sera écrit aussi en Caml-Light et sera invoqué en première ligne des fichiers exécutables produits par le compilateur.

La compilation procèdera en plusieurs étapes. La première étape traduira un flux de caractères en un arbre de syntaxe abstraite pour le langage considéré. Pour cette étape, on utilisera soit les outils camllex et camllyacc (documentés par exemple dans le manuel de référence de Caml-Light), soit le filtrage sur les flux (dont des exemples d’application courent les rues). Dans le cas de Mini-Scheme, cette première étape sera suivie d’une étape intermédiaire traduisant la syntaxe des listes en une syntaxe mettant plus en avant la spécificité de chaque instructions.

La deuxième étape traduira la forme abstraite de programme en une suite d’instructions assembleur, qu’il conviendra ensuite de recopier dans un fichier exécutable.

La machine abstraite décrite repose sur l’hypothèse qu’à chaque étape de la réduction, une fonction à n arguments est appelée avec exactement n arguments. C’est donc au programmeur de veiller à appliquer chaque fonction avec le nombre d’arguments qu’elle attend, et, lorsqu’un argument est fonctionnel, de veiller à ce que son arité soit exactement celle demandée dans la fonctionnelle qui utilise cette fonction. Par exemple, le programme Mini-Scheme ((lambda (x) (x x)) (lambda (y y) y)) termine alors qu’il devrait boucler ; le programme (display ((lambda (x y) (x y 1)) (lambda (x) x))) s’exécute avec un mauvais résultat

et le programme ((lambda (x y) (x y)) (lambda (x y) x) 1) échoue à l’exécution.

Dans le cas de Mini-ML, un algorithme de typage (non demandé), permettrait, à l’aide d’un mécanisme d’η-expansion automatique, de décharger le programmeur de cette contrainte.

1 Les syntaxes de Mini-Scheme et Mini-ML

On décrit ici la syntaxe des programmes Mini-Scheme ou Mini-ML que le compilateur devra être à même de comprendre. On utilise la notation BNF. Les { } autour d’une catégorie syntaxique signifient un nombre arbitraire d’occurrences d’un élément de cette catégorie.

1.1 Définitions communes aux syntaxes de Mini-Scheme et Mini-ML

entier  : := entier positif
| - entier positif
entier positif  : := chiffre {chiffre}
flottant  : := entier.{chiffre} lettre exposant entier positif
| entier.{chiffre}
lettre exposant : := e | E | e+ | E+ | e- | E-
chaîne  : := " {caractère littéral} "

En résumé, un entier est une suite de un ou plusieurs chiffres de 0 à 9, éventuellement précédée par un signe moins. Un flottant est un entier suivi d’un point, puis, éventuellement, d’une partie fractionnaire consistant en une suite de chiffres, puis, éventuellement encore, d’un exposant constitué de la lettre e ou de la lettre E, suivie, éventuellement, d’un signe + ou -, puis d’un entier.

1.2 La syntaxe de Mini-Scheme

La syntaxe de Mini-Scheme est donnée en figure 1.

Un symbole est une suite de caractères littéraux ne commençant ni par un espace, ni par un caractère de contrôle, ni par les caractères “\”, “(”, “)”, “.”, “,”, “'”, “`”, “@” et “#”.

Les symboles suivants sont des symboles prédéfinis et non redéfinissables : if, define, let, letrec, lambda, set! et begin. Pour chacun d’entre eux, le compilateur devra spécifier le comportement que l’on attend d’eux. De plus, dans le cas de define et set!, les versions avec un seul argument devront aussi être implémentées.

Plus précisément, les syntaxes possibles pour ces symboles seront :

( if expr expr )
( if expr expr expr )
( define symbole )
( define symbole {expr} expr )
( define ( symbole {symbole} ) {expr} expr )
( let ( {( symbole expr )} ) {expr} expr )
( letrec ( {( symbole expr )} ) {expr} expr )
( lambda ( {symbole} ) {expr} expr )
( set! symbole expr )
( set! symbole )
( begin {expr} expr )

Les opérateurs +, -, *, /, = devront être accessibles dans l’environnement initial de compilation. On se contentera, pour ces opérateurs, de leurs versions à deux arguments. La commande display devra elle aussi être disponible dans l’environnement initial.

1.3 Syntaxe de Mini-ML

La syntaxe de Mini-ML est donnée en figure 2.

Un identificateur (abrégé ident) est une suite de lettres, chiffres, contenant éventuellement le caractère de soulignement, mais ne commençant pas par un chiffre.

Les opérations arithmétiques +, -, *, / associeront à gauche. Les opérations + et - lieront plus fort que les opérations * et /.

programme : := {expr}
expr : := symbole
| caractère
| chaîne
| entier
| flottant
| booléen
| ' expr
| ( liste expr )
liste expr : := expr liste expr
| expr . expr
| expr

caractère : := #\caractère littéral
booléen : := #!true

                                                   | #!false
                                                   | ()
                                                   | #!T
                                                   | #!t
                                                   | #!F
                                                   | #!f

Figure 1: Syntaxe de Mini-Scheme

programme : := {phrase;;}
phrase  : := expr
| let ident {ident} = expr
| letrec ident {ident} = expr
expr  : := expr1
| atom {atom}
| fun ident {ident} -> expr
| if expr then expr else expr
| let ident {ident} = expr in expr
| let rec ident {ident} = expr in expr
| do {expr ;} expr return expr
| ident := expr
expr1  : := expr2
| expr2 = expr2

expr2  : := expr2 + expr2
| expr2 - expr2
| expr2 * expr2
| expr2 / expr2
atom  : := ident
| caractère
| chaîne
| entier
| flottant
| booléen
| ( expr )
caractère : := `caractère littéral`
booléen : := true | false

Figure 2: Syntaxe de Mini-ML

La juxtaposition d’atomes correspondra à l’application d’une fonction à ses arguments. Aussi la construction do...return... correspond à une séquence d’expressions à évaluer dans l’ordre et dont seul le résultat de l’évaluation de la dernière expression est retourné.

La fonction print devra aussi être disponible dans l’environnement initial.

2 La syntaxe abstraite des programmes

2.1 La syntaxe abstraite des programmes Mini-Scheme

Le résultat de l’analyse syntaxique d’un programme Mini-Scheme fournira un objet du type programme_lisp :

type atome_lisp =
  True
| Nil
| SInt of int
| SFloat of float
| SString of string
| SChar of char
| Symbole of string
;;
type arbre_lisp =
  Cons of arbre_lisp * arbre_lisp
| Atome of atome_lisp
;;
type programme_lisp == arbre_lisp list
;;

Le premier travail consistera à transformer un programme_lisp en un simple arbre_lisp à l’aide de l’instruction begin.

2.2 La syntaxe abstraite des programmes Mini-ML

Le résultat de l’analyse syntaxique d’un programme Mini-ML fournira un objet du type programme_miniml suivant :

type constante =
  Bool of bool
| Int of int
| Float of float
| String of string
| Char of char
| Indefini       (* Utilise plus tard pour mini-scheme *)
| Nom of string  (* Utilise plus tard pour mini-scheme *)
;;
type primitive =
  Plus
| Fois
| Moins
| Divise

| Egal
| Affiche
;;
type expr_miniml =
  MLApp of expr_miniml * expr_miniml list
| MLFun of string list * expr_miniml
| MLVar of string
| MLCst of constante
| MLIf of expr_miniml * expr_miniml *expr_miniml
| MLSet of string * expr_miniml
| MLLetIn of (string * expr_miniml) list * expr_miniml
| MLLetRecIn of (string * expr_miniml) list * expr_miniml
| MLSeq of expr_miniml list * expr_miniml
| MLPrim of primitive
;;
type phrase_miniml =
  MLExpr of expr_miniml
| MLLet of (string * expr_miniml) list
| MLLetrec of (string * expr_miniml) list
;;
type programme_miniml == phrase_miniml list
;;

Les fonctions devront être mises sous une forme commençant par un fun.

Comme pour Mini-Scheme, un premier travail sera de transformer un programme de type programme_miniml en un terme de type expr_miniml, en remplaçant les MLLet par des MLLetIn et les MLExpr, par exemple, par des séquences.

2.3 La traduction des programmes Mini-Scheme et Mini-ML en une syntaxe commune

On va définir une syntaxe interne commune pour Mini-Scheme et Mini-ML. Les objets de cette syntaxe commune auront le type expr. Ce type dépend des types constante et primitive utilisés pour représenter abstraitement les programmes Mini-ML.

type expr =
  App of expr * expr list
| Abs of string list * expr
| Var of string
| Cst of constante
| LetIn of string list * expr list * expr
| LetRecIn of string list * expr list * expr
| If of expr * expr *expr
| Set of string * expr
| Prim of primitive
;;

Une fois obtenu un objet de type arbre_scheme ou expr_miniml, on effectuera une traduction en un objet de type expr.

Dans cette traduction, les séquences (begin ou bien la construction do...return ...) seront traduites avec des let...in... bidon (i.e. des let...in... liant une variable arbitraire inutilisée par la suite).

C’est l’objet obtenu de type expr qui sera, à proprement parler, compilé.

2.4 Le remplacement des noms par des indices

Une traduction supplémentaire consiste à traduire un objet de type expr en un objet de type debruijn_expr où les noms de variables ont été remplacés par des indices. Un indice (n, p) pour les constructeurs DVar et Dset indique qu’il faut remonter n groupes d’abstractions dans l’environnement local, puis chercher le terme d’ordre p dans ce n-ième groupe.

type debruijn_expr =
  DApp of debruijn_expr * debruijn_expr list
| DAbs of int * debruijn_expr
| DVar of int * int
| DCst of constante
| DLetRecIn of int * debruijn_expr list * debruijn_expr
| DLetIn of int * debruijn_expr list * debruijn_expr
| DIf of debruijn_expr * debruijn_expr * debruijn_expr
| DSet of (int * int) * debruijn_expr
| DPrim of primitive
;;

Pour les constructeurs DAbs, DLetRecIn et DLetIn, l’entier indique l’arité de l’abstraction.

3 Les instructions pour la machine abstraite

3.1 Forme structurée des instructions

Les instructions pour la machine abstraite sont décrites par le type ML suivant :

type asm =
  Applique
| Lambda of int
| Fonction of asm list
| Retour of int
| Accede of int * int
| Constante of constante
| Depile of int
| Reserve of int
| Lambdarec of int
| Select of asm list * asm list
| Modifie of int * int
| Primitive of primitive
;;

Ce sont des instructions pour une machine à environnement avec 4 registres. Ces quatres registres sont : la pile de données (s), l’environnement (e), le code (c), la pile de retour de sous-programme (d).

La pile de donnée contiendra des valeurs. Celles-ci consisteront, soit en des constantes, soit en des fermetures (une fermeture est la paire une fonction (i.e. du code) et de l’environnement de définition de cette fonction). La pile de retour de sous-programme contiendra des fermetures. L’environnement contiendra des listes de vecteurs de valeurs. Quant au code, il consistera en une suite d’instructions pour la machine abstraite.

Les opérations correspondant à ces instructions sont les suivantes :

Pile données  Environnement  Pointeur d’instruction

Pile retour

(c′, e′), s  e  Applique; c  d
s  e′  c′  (c, e), d
s  e  F onction c; c′  d
(c, e), s  e  c′  d
v_{1}, ..., v_{n}, s  e  Lambda n; c  d
v_{1}, ..., v_{n}, s  (v_{1}, ..., v_{n}), e  c  d
v_{0}, v_{1}, ..., v_{n}, s  e  Retour n; c  (c′, e′), d
v_{0}, s  e′  c′  d
s  l_{1}, ..., \overbrace{(v_{1}, ..., v_{n_{m}})}^{l_{m}}, ...  Accede (m, p); c  d
v_{p}, s  l_{1}, ..., l_{m}, ...  c  d
s  e  Constante v; c  d
v, s  e  c  d
v_{0}, v_{1}, ..., v_{n}, s  l_{1}, l_{2}, ...  Depile n; c  d
v_{0}, s  l_{2}, ...  c  d
s  e  Reserve n; c  d
s  (?_{1}, ...,?_{n}), e  c  d
v_{1}, ..., v_{n}, s  (?_{1}, ...,?_{n}), e  Lambdarec n; c  d
v_{1}, ..., v_{n}, s  (v_{1}, ..., v_{n}), e  c  d
true, s  e  Select (c_{1}, c_{2}); c  d
s  e  c_{1}  (c, e), d
false, s  e  Select (c_{1}, c_{2}); c  d
s  e  c_{2}  (c, e), d
v, s  l_{1}, ..., \overbrace{(v_{1}, ..., v_{p}, ..., v_{n_{m}})}^{l_{m}}, ... Modifie (m, p); c  d
v, s  l_{1}, ..., (v_{1}, ..., v, ..., v_{n_{m}}), ...  c  d
v_{1}, ..., v_{p}, s  e  P rim op; c  (c′, e′), d
op(v_{1}, ..., v_{p}), s  e′  c′  d

Remarque : Pour Scheme, false doit être compris comme () et true comme différent de (). Lorsque la pile de retour est vide et l’instruction est Retour, alors l’exécution s’arrête.

3.2 La compilation en instructions de la machine abstraite

Le mécanisme de la compilation est simple. Si on appelle C l’opération de compilation, alors :

• Une application n-aire (e e_{1} ... e_{n}) sera compilée en C(e_{1}); ...; C(e_{n}); C(e); Applique

• Une abstraction n-aire, (lambda (x_{1} ... x_{n}) e) en Scheme, ou fun x_{1} ... x_{n} − > e en Mini-ML sera compilée en F onction(Lambda n; C(e); Retour n)

• Les (let ((x_{1} e_{1}) ... (x_{n} e_{n})) e) de Scheme et let x_{1} = e_{1} and ... and x_{n} = e_{n} in e de ML devront être compilés en

C(e_{1}); ...; C(e_{n}); Lambda n; C(e); Depile n

• Les (letrec ((x_{1} e_{1}) ... (x_{n} e_{n})) e) de Scheme et let rec x_{1} = e_{1} and ... and x_{n} = e_{n} in e de ML devront être compilés en

Reserve ‘n; C(e_{1}); ...; C(e_{n}); Lambdarec n; C(e); Depile n • L’accès à une variable locale sera compilé en Accede(m, p) où m est le nombre d’abstraction à retrouver

et p l’indice de la variable dans la m-ième abstraction (les abstractions sont n-aires).

• Un test de la forme if e then e_{1} else e_{2} sera compilé en

C(e); Select((C(e_{1}); Retour 0), (C(e_{1}); Retour 0))

• Une opération primitive “op” sera compilée en F onction(P rimitive op).

• Une opération d’affectation, (set! f e) en Scheme, f := e en Mini-ML, sera compilée en

C(e); Modifie (m, p),

où p est l’indice de la place de f dans la fenêtre m de l’environnement.

3.3 Forme séquentialisée des instructions

type seqasm =
   SApplique
 | SLambda of int
 | SFonction of int
 | SRetour of int
 | SAccede of int * int
 | SConstante of constante
 | SDepile of int
 | SReserve of int
 | SLambdarec of int
 | SSelect of int * int
 | SModifie of int * int
 | SPrimitive of primitive
;;
type machine == seqasm vect
;;

Le passage de la forme structurée (un programme de type asm ist) à la forme séquentialisée machine du code pour la machine abstraite consiste à remplacer les suites d’instructions, arguments de Fonction et de Select par leur adresse. Cette adresse sera une adresse dans le tableau là où on aura trouvé une zone libre pour y déplacer le code argument des instructions Fonction et de Select.

4 La production de l’exécutable

Pour obtenir un fichier exécutable, on se contentera d’effectuer un output_value sur le type seqasm vect et de mettre une ligne de la forme #!interprete en tête du fichier.

L’interprète devrait donc ainsi être invoqué par la première ligne de commande du fichier exécutable. Cependant, les shells s’attendent, pour l’invocation #!interprete, à ce que interprete soit un vrai exécutable binaire (ce qui n’est pas le cas des exécutables Caml-Light qui eux-mêmes sont des fichiers de données dont la première ligne est justement une invocation à l’interpréteur Caml-Light camlrun). On remplacera donc l’invocation #!interprete par une invocation #!lanceur où lanceur sera le nom de l’exécutable C obtenu à partir du code suivant. L’exécutable Caml-Light pourra alors sans problème se nommer interprete.

/* Fichier lanceur.c */
main(int argc,char **argv)
{execl("interprete","interprete",argv[1],0);}

5 L’interprète

L’interprète récupèrera le programme à l’aide d’un input_value sur le type seqasm vect.

Voici quelques idées à retenir pour concevoir l’interprète. Les piles seront représentées par des vecteurs d’une taille raisonnablement grande. De même pour le code qui sera chargé à partir du fichier exécutable.

L’environnement pourra être représenté par une liste de pointeurs vers des “fenêtres” de la pile de données. Le type des valeurs pourra être celui-là :

type valeur = Const of constante | Fermeture of adresse * env
and adresse == int
and env == fenetre list
and fenetre == int
;;

6 Et si le temps ou le cœur vous en dit...

On pourra envisager diverses extensions.

Une priorité sera d’ajouter un typeur à Mini-ML (avec η-expansion automatique du code).

On pourra sinon étendre la syntaxe de manière à autoriser la manipulation de données structurées. Ceci se fera en permettant l’instruction quote et en autorisant les macro-caractères “`”, “`”, “,” et “,@”.

On pourra parallèlement songer à étendre la syntaxe de Mini-ML avec des objets de bases structurés comme des listes à la Lisp.