CSC4251_4252 — Compilation : du langage de haut niveau à l'assembleur

TP Bonus : Bootstrapping et Brainfuck

Paradoxe du bootstrap, compilation d'un compilateur, comparaison compilateur/interpréteur, exemple de langage ésotérique.

Le but de ce TP est de pouvoir exécuter des programmes écrits dans le langage ésotérique Brainfuck.
On cherchera en particulier à comparer différentes stratégies :

utilisation d'un compilateur,
écriture d'un interpréteur,
traduction vers un autre langage.

Préliminaire : Paradoxe du Bootstrap (en compilation)

On dispose d'un compilateur Brainfuck. Chouette ! mais l'exercice n'est pas très intéressant ? on a la solution dès le départ !
Ce compilateur Brainfuck est écrit en Brainfuck. Oups !! Il y a un paradoxe ? Que faire avec ce compilateur ? J'ai besoin d’exécuter le compilateur pour faire une version exécutable du compilateur ? l’œuf ou la poule ?...

On peut penser que le fait d'écrire un compilateur d'un langage L en utilisant le langage L lui-même est un exercice ésotérique au même titre que le langage Brainfuck. En fait, dans la "vraie vie" :

Quel langage pour les sources de gcc ? C bien sur !
Quel langage pour les sources du compilateur javac ? Sans doute Java.
Quels outils de compilation pour les sources de JFlex ? JFlex, CUP et javac.
Quels outils de compilation pour les sources de CUP ? JFlex, CUP et javac.
Quel langage pour écrire un compilateur de Minijava vers MIPS ? Pourquoi pas Java ?
Quel est le langage préféré du créateur d'un nouveau langage ? Le nouveau langage est bien sûr le meilleur langage pour écrire le premier compilateur du langage.
...

Il doit donc exister des solutions pratiques pour résoudre le problème du bootstrapping et utiliser efficacement un "compilateur du langage L écrit en L".
Lire ou parcourir les pages Wikipédia Bootstrapping et Bootstrapping(compilers) pour l'étymologie, la définition et les différents concepts liés au paradoxe du bootstrap.

Brainfuck et Bootstrap sont dans une galère...

Le langage Brainfuck

Brainfuck est un langage de programmation ésotérique qui s'apparente à une machine de Turing. Il est donc très minimaliste, très puissant, et très incompréhensible en terme de programmation. On trouvera une description étendue et des liens autour de Brainfuck dans Wikipédia(fr)/Brainfuck.
L'exercice ne se préoccupe pas de la fucking programmation en Brainfuck, mais cherche uniquement à fournir un environnement d'exécution pour des programmes déjà écrits en Brainfuck.

Brainfuck utilise un modèle simple de machine comportant :

une "bande" de données infinie (= au moins 30000 octets) initialisée à zéro,
un "pointeur" de données initialisé sur le premier octet de la "bande",
un programme qui est une suite d'instructions, exécutées sauf exception en séquence, le programme termine après la dernière instruction,
huit instructions, chacune codée par un caractère (cf. plus loin),
2 flots d'entrée/sortie utilisant le codage ASCII (stdin, stdout).

En C, on peut par exemple produire une machine Brainfuck avec le canevas :

#include "stdio.h"
int main() { 
    char BANDE[33333]={0}; 
    char *ptr=BANDE; 
    /* traduction de la séquence d'instructions Brainfuck  */ 
    return(0); 
}

Ou en Java :

class out {
    public static void main(String[] args) throws java.io.IOException {
    int ptr = 0;
    byte bande[] = new byte[33333];
    /* traduction de la séquence  d'instructions Brainfuck  */ 
    System.exit(0);
}

Les huit instructions Brainfuck sont :

Code	Nom	Signification	Traduction C	Traduction Java
>	PTR_INC	Incrémenter le pointeur de données	ptr++;	ptr++;
<	PTR_DEC	Décrémenter le pointeur de données	ptr--;	ptr--;
+	VAL_INC	Incrémenter l'octet pointé	(*ptr)++;	bande[ptr]++;
-	VAL_DEC	Décrémenter l'octet pointé	(*ptr)--;	bande[ptr]--;
.	PUTCHAR	Écrire l'octet pointé sur stdout	putchar(*ptr);	System.out.write(bande,ptr,1);
,	GETCHAR	Lire un octet sur stdin et l'écrire sur la bande à l'octet pointé	(*ptr)=getchar();	System.in.read(bande,ptr,1);
[	LOOP_IN	Si l'octet pointé est nul, sauter en avant après l'instruction LOOP_OUT correspondante	while(*ptr){	while(bande[ptr]!=0){
]	LOOP_OUT	Si l'octet pointé est non nul, sauter en arrière après l'instruction LOOP_IN correspondante	}	}

La syntaxe suppose une correspondance usuelle de type paire de parenthèses pour [ et ].
A part les 8 caractères réservés, les autres caractères sont ignorés et peuvent servir de commentaires ou pour la "lisibilité !!!" du code source Brainfuck.
Par rapport à une machine de Turing, on retrouve le même mécanisme pour la mémoire, mais l'on remplace l’exécution d'un automate par une mécanique algorithmique plus classique avec une boucle et les 2 opérations arithmétiques +1 et -1. On a aussi 2 entrées/sorties pour le "confort" d'utilisation !!!

Exemples de code Brainfuck

L'archive BF.tar contient des exemples de programmes de test ou de démonstration écrits en Brainfuck. On utilisera plus particulièrement :

Un petit programme de test "Hello World", hello.bf.
Un programme de démo plus gourmand en temps d’exécution, mandelbrot.bf.
Le fameux Compilateur BF2ELF.bf.

Ne pas essayer de comprendre les sources Brainfuck. Enfin c'est vous qui voyez !
Éventuellement le petit "Hello World" :

hello.bf

Traducteur Brainfuck vers C

Pour cette question et la suivante, vous pouvez remplacer C par Java. Le travail est identique dans les 2 cas, mais la version avec C est plus performante ! Le corrigé de la version Java sera donné plus loin.

Écrire un traducteur de Brainfuck vers C en utilisant JFlex et CUP. Tester sur les exemples.
Pour exécuter un fichier C out.c, faire gcc out.c; ./a.out; rm a.out;

On choisit de produire le résultat du traducteur dans un fichier (défaut out.c) plutôt que sur la sortie standard. On se donne la classe utilitaire BFTrad.java (à placer dans le répertoire src du projet CUP) pour générer rapidement la sortie du traducteur. Cette classe permet d'écrire la sortie dans un fichier avec :

un fichier préambule inséré au début,
impression au milieu ligne à ligne avec indentation éventuelle,
un fichier postface inséré à la fin.

BFTrad.java

Utiliser "Memento CUP/Code Utilisateur" pour l'utilisation des actions en milieu de règle ou la réalisation d'actions finales ou initiales.
Un exemple de résultat pour le programme hello.bf :

hello0.c

Traducteur compact Brainfuck vers C

Pour améliorer notre traducteur, on décide de compacter N opérations +1 consécutives en une seule opération +N. On modifie ainsi le schéma de traduction pour les instructions PTR_INC, PTR_DEC, VAL_INC et VAL_DEC sous la forme :

Code	Nom	Traduction C	Traduction Java
>^N	PTR(N)	ptr+=N;	ptr+=N;
<^N	PTR(-N)	ptr+=-N;	ptr+=-N;
+^N	VAL(N)	(*ptr)+=N;	bande[ptr]+=N;
-^N	VAL(-N)	(*ptr)+=-N;	bande[ptr]+=-N;

Modifier les spécifications JFlex et CUP précédentes pour obtenir une version améliorée du traducteur vers C.

Un exemple de résultat pour le programme hello.bf :

hello.c

Créer un Token PTR avec une valeur sémantique de type Integer. La valeur peut être positive ou négative. Le token PTR remplace PTR_INC et PTR_DEC.
Reconnaître dans JFlex, les séquences de PTR_INC consécutifs et retourner un token PTR avec une valeur sémantique égale à la taille de la séquence (méthode yylength()).
Idem avec PTR_DEC mais en changeant de signe.
Adapter la spécification CUP pour la traduction du token PTR.
Idem avec VAL, VAL_INC et VAL_DEC.

Traducteur Brainfuck vers Java (optionnel)

Faire les deux questions précédentes, en remplaçant C par Java.

Pour exécuter rapidement une classe Java out.java, faire javac out.java; java out; rm out.class;

Un exemple de résultat pour le programme hello.bf :

hello.java

Interpréteur Brainfuck (difficile)

La question est un peu plus difficile. On pourra éventuellement se contenter d'analyser le corrigé et de l’utiliser dans les questions suivantes

Écrire un interpréteur de Brainfuck en utilisant JFlex et CUP. Pour pouvoir traiter la boucle de Brainfuck, le choix est de construire explicitement un Arbre de Syntaxe Abstraite ; et de réaliser l'interprétation ou l’exécution sur l'arbre.
On donne un squelette de code pour réaliser la machine Brainfuck et la structure de l'AST dans la spécification CUP.

bfInterp.cup.part

Comparer les chaines d’exécution

Sur l'exemple mandelbrot.bf (ou d'autres exemples), comparer les performances des différentes chaînes d’exécutions produites dans les questions précédentes :

bf2c : Traduction vers C (compact ou non) / gcc / exécution ELF,
bf2java : Traduction vers java (compact ou non) / javac / exécution JVM,
bfInterp : Interprétation avec exécution Java.

Comparer en particulier les tailles des fichiers produits (out.c, a.out, out.java, out.class), les temps de génération (traducteur, gcc, javac), et les temps d’exécution.
Conclusions ?

Pour mesurer les temps, on utilise la commande UNIX time avec par exemple un alias
alias time '/bin/time --format="User Time = %U"'
Pour simplifier les manipulations, on peut aussi rajouter dans le fichier Makefile les lignes suivantes :

Makefile.add

On aura alors :

la commande make xxx.jar pour créer un jar exécutable de l'analyseur construit sur les spécifications spec/xxx.cup et spec/xxx.jflex. L'analyseur s’exécute alors avec java -jar xxx.jar (ou time java -jar xxx.jar),
la commande make runc pour exécuter et tracer un fichier out.c,
la commande make runjava pour exécuter et tracer un fichier out.java.

Exécuter le compilateur Brainfuck

Créer une exécution du compilateur BF2ELF.bf. Vous pouvez utiliser les différentes chaînes d’exécution précédentes. Selon la chaîne, l’exécution sera un ./a.out ou un java out ou un java -jar bfInterp.jar BF2ELF.bf

On a donc maintenant une nouvelle chaîne d’exécution pour Brainfuck, sous la forme :

"exécution de BF2ELF" < mandelbrot.bf > mandel.elf
chmod +x mandel.elf
./mandel.elf

Tester et comparer les performances sur différents exemples.

Questions Importantes :

Le temps d’exécution du compilateur dépend t'il de la chaîne d’exécution utilisée pour produire le compilateur ? Pourquoi ?
La sortie du compilateur (i.e. mandel.elf) dépend t'elle de la chaîne d’exécution utilisée pour produire le compilateur ? Pourquoi ?

L'ultime combat : Rendre le compilateur performant

Créer un exécutable plus performant pour BF2ELF.bf (plus rapide pour le même résultat en sortie) et tester ce nouveau compilateur sur des exemples.
Compiler le compilateur BF2ELF.bf avec l'"exécution pas terrible" de la question précédente. Quelque soit le chemin suivi, on obtient le même exécutable ELF pour le compilateur. Il est supposé performant dans la mesure où l'algorithme codé dans BF2ELF.bf serait performant !

Conclusion

Le bootstrap n'est un problème ou un paradoxe que pour réaliser "la première fois".
On peut choisir une solution très simpliste et peu optimale pour cette "première fois". Cela n'a aucune influence sur le résultat final. De faîte, la meilleure solution sera la plus rapide à écrire.
La solution doit surtout être correcte, c'est-à-dire assurer que la sémantique d’exécution est conservée.

Un petit moment de détente : Whitefuck

Pour réduire le caractère trop "lisible !" des sources Brainfuck, on définit le langage Whitefuck qui utilise la même machine que Brainfuck, mais code les instructions en utilisant uniquement les caractères espaces et tabulations. Chacune des huit instructions Brainfuck est codée par une séquence de trois caractères blancs en suivant la table de conversion :

Brainfuck	Nom	Whitefuck	YaWf
>	PTR_INC	" "	" "
<	PTR_DEC	" \t"	"\t\t"
+	VAL_INC	" \t "	"\t "
-	VAL_DEC	"\t "	" \t"
[	LOOP_IN	"\t\t "	" \n"
]	LOOP_OUT	"\t \t"	"\n "
.	PUTCHAR	" \t\t"	"\n\t"
,	GETCHAR	"\t\t\t"	"\t\n"

N.B. : YaWf (Yet another Whitefuck) est juste une variante plus compacte de Whitefuck

Ticket aller-retour

Écrire avec JFlex seul, un traducteur Whitefuck vers Brainfuck et un traducteur Brainfuck vers Whitefuck.
Exécuter le source Whitefuck mouton.wf.

CSC4251_4252, TELECOM SudParis, P. Hennequin,Last modified: Juillet 2022