6.1 Modèles de Compilation des Langages Fonctionnels
La principale difficulté de la mise en oeuvre d'un langage fonctionnel vient
de la traduction du contrôle implicite de l'exécution dans un modèle de calcul où il devient
explicite.
La première méthode consiste à réécrire le programme
avec un contrôle explicite. La transformation CPS (Continuation Passing Style [],[])
réécrit toutes les
expressions en expressions closes (sans variables libres) et indique, en le passant comme argument supplémentaire, la
continuation (reprise de calcul) à appliquer en fin de calcul d'une fonction.
La deuxième méthode consiste à utiliser une machine abstraite. Il existe deux grandes familles
de machines abstraites pour les langages fonctionnels :
-
Les machines à environnements construisent des couples (code,environnement)
pour les fermetures. La partie code peut contenir des variables libres et
la partie environnement les valeurs de ces variables.
La machine SECD (Stack Environment Control Dump) a été un des premiers représentants de cette stratégie.
Les machines FAM (Functional Abstract Machine) et CAM ([]) (Categorical Abstract Machine) reprennent ce type d'architecture avec des variantes sur la représentation de l'environnement. La
CAM chaîne les environnements alors que la FAM les duplique.
- Les machines à réduction de graphes représentent les expressions par un graphe.
Les noeuds des graphes sont des noeuds d'application, et les feuilles sont
des combinateurs ou des constantes. La SK machine a été
un des premiers représentants. On en rencontre d'autres comme la G-machine ou la TIM .
Les machines à pile et environnement sont plutôt utilisées pour la stratégie
d'évaluation stricte et les
nmachines à réduction de graphes pour les stratégies paresseuses.
Ce n'est pas une conséquence théorique mais une habitude comme
le montre le choix de la machine de Krivinne pour compiler
le l-calcul.
L'exécution des instructions de ces machines virtuelles repose sur deux modèles : interpréteur ou compilateur.
-
Un interpréteur exécute les instructions de cette machine.
Cette méthode est, en règle générale,
assez peu efficace. On tombe dans les travers des émulations.
Néanmoins, certaines mises en oeuvre, comme Caml-light ([]),
donnent des temps de calcul raisonnables.
- Un compilateur traduit directement les instructions de la
machine virtuelle par une série d'instruction du processeur cible (compilateur natif). Cette
solution donne des résultats bien supérieurs à la précédente. La
difficulté des compilateurs
natifs est d'avoir un générateur de
code spécifique à chaque processeur. Elle subsiste même en simplifiant
cette traduction par l'emploi d'un langage intermédiaire plus simple .
La figure 6.1 montre les différentes voies de traduction
d'un langage fonctionnel.
modeles.ps
Figure 6.1 : Compilation d'un langage fonctionnel
Nous étudierons une transformation de programme : le l-lifting ([]) pour la gestion des environnements des déclarations locales, la transformation de programmes CPS (Constinuation Passing Style (CPS[]))
pour le contrôle de l'exécution, et une machine abstraite
la CAM (Categorical Abstract machine) qui est la machine d'implantation de CAML V3.1 et
non de Caml-light comme son nom ne l'indique pas. D'autres points importants
seront abordés au cours Lisp la gestion automatique de mémoire (Garbage Collector ou Glaneur de Cellules (GC)).