Quelques informations techniques sur le système OCaml

Alain Frisch

Introduction

Ce document présente quelques informations sur le fonctionnement du système OCaml que j'ai eu l'occasion de découvrir et d'utiliser, et qui, je pense, pourraient être utiles à d'autres personnes.

Les sources d'information principales ont été:

Les sources du compilateur et du système d'execution, bien évidemment, en particulier les fichiers suivants:
- Pour le fonctionnement de la machine abstraite: bytecomp/bytegen.ml, byterun/interp.c
- Pour le fonctionnement du linker: ...
Les sorties du toplevel, lancé avec les options -dlambda, -dinstr.
La description de la machine abstraite de Zinc (ZAM), par Xavier Leroy.

J'essaie de ne pas paraphraser ces informations; au contraire, je m'efforce d'en donner une vue d'ensemble et de fournir des pistes pour les comprendre plus en détail.

1 Vue d'ensemble

2 Modèle mémoire

2.1 Aperçu

2.2 Representations

2.3 Garbage collector

3 La machine abstraite

3.1 Une machine à pile et à accumulateur

La machine abstraite est derivée de la ZAM. Son trait distinctif principal est sa capacité à executer efficacement des appels de fonctions avec plusieurs arguments (fonctions curryfiées), sans construire des fermetures inutiles.

Il s'agit d'une machine à pile, avec quelques registres spécialisés:

`pc`	pointeur d'execution
`sp`	pointeur de pile
`accu`	accumulateur
`env`	pointeur d'environnement (fermeture active)
`trapsp`	pointeur pour la gestion des exceptions
`extra-args`	nombre d'arguments supplémentaires encore sur la pile

Les registres pc , sp , accu sont classiques et n'appellent pas de commentaire particulier. La pile croît vers le bas. La valeur au sommet est donc sp [0], celle au-dessus sp [1], ...

L'évaluation d'une expression laisse son résultat dans l'accumulateur.

L'instruction Acc permet d'acceder à une valeur sur la pile, relativement à sp . L'instruction Push empile bien entendu le contenu de accu . Pop dépile et jette un certain nombre d'éléments de la tête de pile.

Assign modifie le contenu d'une valeur sur la pile, en y mettant le contenu de accu .

3.2 Schéma d'appel de fonction

Voici le scénario standard d'execution de l'application d'une valeur fonctionnelle à n arguments:

on empile d'abord les informations de retour: l'adresse et la valeur courante des registres env et extra-args ; c'est le rôle de Push-RetAddr
les n arguments sont évalués de droite à gauche et empilés dans cet ordre
la valeur fonctionnelle est evaluée, ce qui laisse une fermeture f dans l'accumulateur
l'appel est executé par l'instruction Apply: le registre env est dirigé vers f, le registre extra-args recoit le nombre d'arguments supplémentaire n-1 et on saute dans le corps de la fonction en mettant dans pc l'adresse du code de f

La pile, à l'entrée du code de la fermeture, a donc l'allure suivante:

`sp` + (n+2)	sauvegarde de `extra-args`
`sp` + (n+1)	sauvegarde de `env`
`sp` + n	adresse de retour
`sp` + (n-1)	argn
`sp` + 1	arg2
`sp`	arg1

Donc en général, le code a accès aux données suivantes (entre parenthèse, l'instruction d'accès):

les données globales (GetGlobal)
les valeurs correspondant aux variables libres de la fonction, dans l'environnement env (EnvAcc)
les arguments de la fonction sur la pile (Acc)
les variables locales, intermédiaires de calcul, également sur la pile (Acc)

Si la fonction a besoin d'utiliser des arguments suuplémentaires, elle le signale avec une instruction particulière (Grab). Le nombre d'arguments disponibles est donné par extra-args . S'il y en a suffisamment, on peut continuer l'execution de la fonction (en decrementant extra-args pour indiquer que des arguments ont été consommés). Sinon, il faut suspendre le calcul et renvoyer une fermeture. Celle-ci doit se souvenir de l'environnement courant, ainsi que de tous les arguments déjà disponibles. Son code pointe en fait vers une instruction Restart placée juste avant Grab, et dont le role est de déballer les informations de cette fermeture et de reprendre l'execution du Grab, quand la fermeture est finalement appliquée à de nouveaux arguments.

À la fin de son execution, la fonction execute l'instruction Return. Elle commence par supprimer les variables locales et les arguments consommés de la pile. S'il n'y a plus d'arguments supplémentaires (extra-args = 0), on peut revenir à l'appelant, en restaurant les registres pc , env , extra-args à partir des informations de retour stockées sur la pile. La valeur retournée est dans l'accumulateur. S'il reste des arguments, c'est que la fonction renvoie une fermeture, que l'on peut executer maintenant avec les arguments restant. Cela se fait en remplacant simplement les registres pc , et env par les données de cette fermeture (appel terminal en quelque sorte).

Les appels en position terminale (juste avant un retour) sont compilés plus efficacement: il n'y a pas besoin de garder les informations de retour, et on peut faire un simple saut à la place de l'appel. L'instruction AppTerm s'occupe de cela. Elle supprime les données inutiles de la pile (arguments consommées, variables locales) et déplace les arguments de l'appel de sorte à simuler un appel normal. S'il restait des arguments supplémentaires, ils sont ajoutés aux arguments donnés pour cet appel.

3.3 Fermetures

Outre les fermetures créées par les executions suspendues du fait d'un manque d'arguments supplémentaires en nombre suffisant (cf Grab), il y a les fermetures habituelles correspondant à des abstractions.

L'instruction Closure crée une fermeture simple. Elle prend en argument le nombre n de constituants de l'environnement, ainsi que l'adresse du code de la fermeture. Pour créer un environnement de taille n, il faut évaluer les n constituants sur la pile (sauf le dernier dans l'accumulateur). Le bloc crée est simplement placé dans l'accumulateur et les données prises sur la pile sont supprimées.

Pour créer une fermeture mutuellement recursive entre plusieurs fonctions, il faut utilise ClosureRec. Les n fonctions partagent en fait le même environnement et un seul bloc est alloué. Mais il y a bien n fermetures différentes: ce sont des pointeurs qui pointent au milieu du bloc.

Un tel bloc a donc la forme suivante:

Header 1

Code 1

Header 2 (infixe)

Code 2

...

Header n (infixe)

Code n

Environnement

...

Lorsque la fermeture k de ce bloc s'execute et qu'elle veut acceder à la fermeture p, elle doit donc calculer env + 2 * (k-p) et mettre le résultat dans accu , ce qui se fait avec la fonction OffsetClosure qui prend comme argument 2*(k-p).

3.4 Blocs

L'instruction MakeBlock s'occupe de créer un bloc dans le tas. Elle prend comme argument la taille n et le tag du bloc ) créer. Les n arguments qui vont initialiser le bloc ont été évalués et placé sur la pile (sauf le dernier, dans l'accumulateur).

Il y a aussi une instruction Atom qui renvoie un bloc atomique (un bloc de taille 0, alloué statiquement une fois pour toute).

Pour acceder à une composante d'un bloc, on utilise l'instruction GetField qui prend comme argument le rang de la composante convoitée. Le bloc est referencé par l'accumulateur.

Symétriquement, SetField permet de modifier en place un bloc.

Des instructions spéciales sont fournies pour manipuler des blocs de flottants: MakeFloatBlock, GetFloatField, SetFloatField.

3.5 Branchements

3.6 Exceptions

3.7 Primitives C

3.8 Objects

3.9 Opérations sur les entiers, booléens, chaines, tableaux

3.10 Instructions dérivées

Les opcodes de la machine abstraite sont codés sur 32 bits; cela laisse de la place ! Un certain nombre d'instructions courantes, qui acceptent un argument, ont des versions spécialisées pour les petites valeurs de l'argument. Par exemple, Acc0, Acc1, ..., Acc7.

Attention aux instructions Apply1, Apply2, Apply3 ! Elles ont une sémantique différente de ce que l'on pourrait s'imaginer. En fait, elles se chargent d'empiler les informations de retour (ce que fait normalement Push-RetAddr), en décalant les arguments pour laisser de la place.

Il est courant d'empiler le contenu de accu avant de le remplir avec autre chose. Il y souvent des instructions composées "Push + autre chose": PushAcc, PushEnvAcc, PushOffsetClosure, ...

4 L'interpreteur de bytecode

This document was translated from L^AT_EX by H^EV^EA.