juillet
2012
Un article de bredelet
Le langage dodo et le langage C ne sont pas trop éloignés au niveau de la syntaxe, mais leur fonctionnement est assez différent. Là où C est un langage procédural, dodo est un langage à prototypes utilisant le passage de continuations (CPS).
Le défi pour moi, l’architecte du langage, est de faire correspondre les concepts de dodo à une implémentation pratique offrant une performance acceptable. Je me suis donc tourné vers C avec l’idée d’écrire un convertisseur automatique de programmes dodo en C.
Seulement voilà, comment traduire?
La directive switch
Comme je l’ai suggéré dans la première partie, l’appel de continuation en dodo et la directive switch de C s’apparentent tous deux à GOTO, alors on peut écrire quelque chose comme:
int choix = 0;
while (1) switch (choix)
{
case 0:
if (n == 0) choix = 1;
else choix = 2;
break;
case 1:
return c_return;
case 2:
n = n - 1;
choix = 0;
break;
default:
c_throw->event.message = "Erreur de branchement!";
return c_throw;
}
Cela correspond à une fonction dodo qui prend en paramètre un nombre n et le décrémente jusqu’à ce qu’il atteigne 0, puis retourne de la fonction:
def fzero = fun(int n) => return(), throw(Exception):
n = 0 ->
return()
|
n - 1 -> n
$fzero(n)
.
La notation à continuations
Le code dodo ci-dessus ne ressemble pas vraiment à du C vous me direz. C’est que j’ai utilisé la notation à continuations pour bien illustrer la correspondance avec le switch. En réalité, le but est bien de pouvoir écrire la fonction fzero en style C comme ceci:
def fzero(int n)
{
loop
{
case if (n = 0)
{
return()
}
.n = n - 1
}
}
À quoi bon transformer une fonction de style C en une fonction à passage de continuations, pour ensuite la transformer à nouveau en fonction C vous demandez-vous?
Hé bien pour le moment je compte implémenter juste la notation à continuations, de façon à avoir une base solide pour le langage, et ensuite m’attaquer à la transformation du style procédural en passage de continuations pour rendre le langage plus confortable à utiliser. Si un jour je trouve un langage avec continuations ou GOTO que je peux utiliser en lieu et place de C, il devrait être simple d’implémenter le langage de base de dodo avec lui. Le reste de dodo n’aura pas besoin d’être réécrit.
La boucle de continuations
Revenons à nos moutons.
Nous avons vu comment utiliser switch pour implémenter une fonction dodo simple qui se contente de décrémenter un compteur.
Pour ceux qui sont attentifs, il y a une continuation dans le switch qui n’existe pas dans la fonction dodo: celle du cas default. Un examen du code montre que ce cas n’est jamais atteint, mais il est bon de prévoir une erreur du convertisseur automatique (ou dans ce cas, du convertisseur humain puisque c’est écrit à la main!)
Si je parle du cas default c’est que ses instructions contiennent une ligne intéressante qu’il serait bon d’expliquer. C’est:
c_throw->event.message = "Erreur de branchement!";
On y voit comment passer un paramètre à une continuation. En effet, c_throw est une continuation passée en paramètre à la fonction C. Il ne serait pas viable d’utiliser la technique du switch pour toutes les continuations du programme, dans une application conséquente il y aurait des centaines de milliers de cas dans le switch, sans compter qu’il faudrait trouver comment faire passer des arguments à une continuation sans mettre tout en variables globales.
Donc on garde la boucle de continuation décrite dans un article précédent pour interagir avec les autres fonctions.
Mais la boucle de continuation utilise des fonctions qui sont appelées en boucle, comment se fait-il que l’exemple utilise la notation c_throw->event qui suggère que c_throw est une structure pas une fonction?
C’est simple, c_throw est effectivement une structure. Mais son premier champ est un pointeur de fonction qui est utilisé par la boucle de continuations. Dans l’exemple donné, event est un autre champ de la structure. La boucle de continuations ne sait rien de event, ou des autres champs ajoutés à la structure.
Il faut que la fonction appelée par la boucle de continuations puisse lire une valeur fournie comme argument par l’appelant de la continuation qui, lui, connaît la structure de c_throw.
C’est pour cela que la boucle de continuation passe la structure en argument à la fonction. Dès lors, voici comment s’écrit la boucle de continuations:
continuation suivante = premiere
while (suivante != NULL)
{
suivante = suivante->appel(suivante);
}
Gestion de la mémoire
Donc event est un champ de la structure passée en argument à la fonction C pour la continuation c_throw. Côté dodo il correspond à un argument de la continuation throw. Mais comment le programme alloue-t-il la mémoire pour les champs supplémentaires de la structure?
La boucle de continuations ne peut pas gérer cela, elle ne sait rien des champs supplémentaires et de plus elle ne saurait pas quand la mémoire n’est plus nécessaire et peut être libérée.
L’appelant pourrait utiliser malloc pour allouer la mémoire nécessaire. La mémoire pourrait être libérée au retour si elle n’est plus utilisée. C’était de fait ma première idée.
Un problème est que le contrôle ne retourne pas nécessairement à l’appelant quand la fonction termine. Un exemple courant est une fonction qui passe à une fonction appelée sa propre continuation return comme continuation de retour. Quand la fonction appelée fait return(), la fonction qui l’a appelée n’est pas informée.
Il faut donc intercepter cela pour libérer la mémoire allouée, avant que la continuation n’atteigne la boucle de continuations.
C’est alors qu’une autre idée m’est venue.
Plutôt que d’essayer de libérer la mémoire quand elle n’est plus utilisée, pourquoi n’essaierions-nous pas de préserver la mémoire qui sera encore utilisée jusqu’au retour de la fonction?
Pour cela, on dissocie la fonction dodo en deux fonctions C: l’une qui fait le travail et contient le switch, et l’autre qui préserve la mémoire utile jusqu’à la fin de la fonction et qui contient une boucle de continuations. La fonction au switch n’utilise la boucle de continuations que pour reprendre le contrôle quand une fonction appelée retourne ou pour terminer. La boucle de continuations continue tant que la continuation suivante appelle la fonction au switch (qui n’est donc pas terminée).
Il n’y a pas besoin d’utiliser malloc avec cette solution, la mémoire peut être préservée sur la pile.
Par exemple, si notre fonction fzero voulait afficher la valeur de n à chaque itération on pourrait écrire les deux fonctions:
continuation fzero(int n, continuation c_return, continuation c_throw)
{
struct c_fzero donnees = {
fzero_switch, // appel
0, // choix
n,
c_return,
c_throw
}
continuation suivante = (continuation) &donnees;
while (suivante->appel == fzero_switch)
{
suivante = suivante->appel(suivante);
}
return suivante;
}
continuation fzero_switch(continuation self)
{
struct c_fzero *donnees = (struct c_fzero*) self;
int choix = donnees->choix;
int n = donnees->n;
while (1) switch (choix)
{
case 0:
if (n == 0) choix = 1;
else choix = 2;
break;
case 1:
return donnees->c_return;
case 2:
donnees->choix = 3;
donnees->n = n;
return print_int(n, self, donnees->c_throw);
case 3:
n = n - 1;
choix = 0;
break;
default:
donnees->c_throw->event.message = "Erreur de branchement!";
return donnees->c_throw;
}
}
On voit que si print_int retourne self, la boucle de continuation appelle à nouveau fzero_switch mais avec le choix 3. Par contre si elle retourne la continuation throw, la boucle de continuation de fzero termine.
Je conclus ainsi la seconde partie de Faire dodo en C.
Vous pouvez réagir dans les commentaires ci-dessous.