Compilation
Programmer l’ENIAC (1946), c’est connecter des câbles.
Programmer un ordinateur, c’est entrer un programme en mémoire.
Par définition ou presque (machine de Von Neumann), un ordinateur est :
Il s’agit d’un détail technique. Par exemple…
Années 80, « amateur » fauché | Aujourd’hui, assembleur | |
Il n’existe pas d’ordinateur qui exécutent les programmes PCF directement.
Car PCF s’addresse d’abord aux être humains (sisi).
Deux techniques pour exécuter PCF.
Traduire PCF vers une vraie machine, c’est trop compliqué.
Car la vraie machine est un peu trop simple, et il y aura des complications pour les fonctions.
À la place, nous traduisons vers une machine abstraite. Puis…
Imaginons que PCF est le seul langage L (informatique) de l’humanité, qui vient d’inventer son premier ordinateur M. Pour pouvoir exécuter un programme écrit en L, il faut :
Ensuite…
C’est en gros ce qui s’est passé (mais avec Fortran.)
L’écriture d’un compilateur dans son propre langage est le bootstrap (auto-amorçage).
Soit un langage informatique L déjà compilable (et bootstrapé) sur une machine M.
Je note L →L M le source et L →M M l’exécutable (du compilateur).
Une nouvelle machine M′ arrive sur le marché.
Si L →L M est buggé, il est parfois difficile de corriger.
Une instruction :
L’instruction (dite load ou move immédiat) range une constante entière dans un registre.
Un registre est une case de mémoire disponible à l’intérieur de l’unité de contrôle.
%eax
, %ebx
…Inteprétation de t1 + t2
Autrement dit,
t1
, ranger le résultat dans n1
,
t2
, ranger le résultat dans n2
,
n1+n2
.
Comment faire, avec la machine qui ne connaît, ni la liaison let, ni l’appel de fonction (et encore moins l’appel récursif).
Le code est une séquence d’instructions.
Remplacer « Interpréter t
» par,
executer le code qui calcule la valeur de t
(dans l’accu),
noté C(t).
t1
, sauver l’accu dans la pile.
t2
.
Soit compilation de t1 + t2.
C(t1) ; Push ; C(t2) ; Add |
NB : C est la fonction de compilation, des termes PCF vers le code.
État de la machine : un triplet accu × pile × code, noté (A,S,C)
Effet des instructions : sémantique à petit pas (système de transitions).
|
Le résultat du calcul est un état de la forme (n,∅,∅).
Simple :
C(1+2) = Ldi 1; Push; Ldi 2; Add |
Simple :
C(3+4) = Ldi 3; Push; Ldi 4; Add |
Plus compliqué :
|
À la fin, l’accumulateur contient 10 et la pile est comme au début.
Il est assez facile de réaliser une pile en machine.
Si la machine donne directement les instructions push et pop.
L’addresse du sommet de la pile est dans un
registre particulier dit pointeur de pile (%esp
).
Push
subl $4,%esp Pop
movl %eax,0(%esp) movl 0(%esp),%eax addl $4,%eax |
État de la vraie machine :
subl $4,%esp movl %eax,0(%esp) |
addl %eax,0(%esp) popl %eax |
Comme une définition de la fonction C.
|
En Caml.
Ou encore (éviter les concaténations).
(compile t @ c
= compile_k t c
, pour tout terme t
et tout code c)
Interprétation.
|
|
La compilation semble évidente :
On se donne une instruction Test(C2,C3) qui va exécuter C2 ou C3 selon la valeur de l’accumulateur. Genre
|
Et on compile :
C(Ifz t1 Then t2 Else t3) = C(t1); Test(C(t2),C(t3)) |
Considérer :
On aura un code du genre
C(t1); Test(C(t2),C(t3)); Push; Ldi 3; Add |
C’est à dire que les transitions de la machine abstraite sont plutôt :
|
Dans une implémentation Caml, on écrira malheureusement:
Mais on peut éviter la concaténation avec un peu de reflexion.
Dans la vraie machine, pas de liste d’instruction en argument des instructions !
Une seule séquence, et des instructions de saut.
Les règle de la variable et du Let.
|
|
(Tiens nous sommes en appel par valeur).
On ajoute donc:
Si Search appelle List.assoc
,
on a pas compilé grand chose.
Considérons :
Au moment d’interpréter t, l’environnement est de de la forme :
Au vu du programme la position des variables dans l’environnement à l’exécution (E) est connue (pour z, c’est 0,…, pour x c’est 2).
On peut donc simplifier E: c’est une liste de valeurs.
|
Compilation, CE(t) où E donne les positions des variables (liste de variables suffit ici).
|
Il faut après le code C[x](Let x = 1 In x+x) redonner sa valeur d’origine à l’environnement.
Une solution simple est de sauver/restaurer l’environnement à l’aide de la pile S.
|
Et compilation complète du Let.
|
Différence essentielle entre pile et environnement :
Il fait donc ajouter du code supplémentaire au code compilé, qui gère l’allocation mémoire (facile) et la récupération (plus dur). Ce code supplémentaire s’appelle parfois un environnement d’exécution (argl) ou encore le support à l’exécution.
Mais le principe de changer les noms de variables en positions est typique.
On utilise la gestion mémoire de Caml.
On utilise donc le support à l’exécution de Caml, sans se poser plus de questions.
Mais si on écrit une machine abstraite en assembleur (en C), il faudra se
poser des questions (réponse malloc
+ écrire un GC).
Interprétation de la fonction.
|
La fermeture en machine est une paire <C•E> (t compilé, et plus besoin du nom de la variable).
Par exemple :
La fermeture suivante représente f.
<Search 0; Push; Search 1; Add•vy> |
Une nouvelle instruction pour fabriquer les fermetures :
|
On ose à peine préciser :
Compilation, seuls les environnements sont (un peu) subtils.
|
Noter quand même qu’une fermeture est la valeur d’une fonction, et se retrouve donc logiquement dans l’accumulateur.
La règle d’inteprétation.
|
Soit il faut :
Donc une instruction Apply fait tout ça
|
Et compilation :
|
Mais une fois de plus c’est un peu trop simple…
On a donc, par compilation, un code du genre:
Ldi 2; Push; Search 0; Apply; CE(x); Add |
(ou E est [f; x; ⋯])
Il faut donc retrouver l’état de la machine après le retour de la fonction.
Un état de machine est normalement (A,S,E,C), mais
|
|
Avec Apply qui sauve l’état de la machine, c’est simple.
|
Compte tenu de ce qui vient d’être vu, à la fin de la séquence ci dessus.
Sauvegarde et restauration explicite de l’environnement par l’appelant.
CE(t1 t2) = PushEnv; CE(t2); Push; CE(t1); Apply; PopEnv |
Avec un Apply moins puissant :
|
N.B. La compilation du poly, produit toujours Apply suivi de PopEnv.
Le modèle du poly n’a pas de règle spéciale pour le retour de fonction (mais il triche un peu dans la règle de Apply).
Soit une fonction à deux arguments:
Soit Let k = tk In t. Le code de tk est :
MakeClo [MakeClo [Search 1; Push; Search 0; Add]] |
Son exécution construit la fermeture c = <MakeClo C•∅>, avec C = [Search 1; ⋯].
Et le code de t est :
|
Au moment du premier Apply.
(<MakeClo [C]•∅>, (1;2), E, (Apply; Apply; ∅)) |
(Où E est l’environnement donne sa valeur à k.)
Transition Apply
(_, ((Apply; ∅); E; 2), (1;E), MakeClo C) |
Exécution de MakeClo C.
(<C•(1;E)>, ((Apply; ∅); E; 2), (1;E), ∅) |
Retour de fonction.
(<C•(1;E)>, (2), E, (Apply; ∅)) |
Nouvel Apply :
(_, ((∅);E), (2;1;E), C) |
C’est à dire que le code C=[Search 1; Push; Search 0; Add] s’exécute dans l’environnement approprié (x=1 en seconde position, y=2 en première).
À la fin du code C.
(3, ((∅);E), (2;1;E), ∅) |
Et retour de fonction.
(3, ∅, E, ∅) |
Nous ne considérons que le point fixe de fonctions Fix f -> Fun x -> t.
Interprétation par une fermeture bouclée.
On invente une nouvelle instruction MakeCloRec qui construit ce style de fermeture bouclée, mais pour la machine.
Avec donc la règle d’exécution :
(_,S,E,(MakeCloRec [C];C′)) → (c,S,E,C′), où c graphe c = <C•c;E> |
À comparer avec :
(_,S,E,(MakeClo [C]; C′)) → (<C•E>,S,E,C′) |
Exécution en Caml.
Compilation, seuls les environnements sont (un peu) subtils.
|
N.B. La transition Apply ne change pas.
Évidemment rien n’empèche de se passer de MakeClo.
|
|
|
État final de la machine :
(v, ∅, _, ∅) |
(Pile et code vides). Le résultat est v, le contenu de l’accumulateur.
|
Sauf erreur, bien entendu.
Ce document a été traduit de LATEX par HEVEA