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" :
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.
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.
- ...
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).
#include "stdio.h"
int main() {
char BANDE[33333]={0};
char *ptr=BANDE;
/* traduction de la séquence d'instructions Brainfuck */
return(0);
}
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);
}
| 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.
Éventuellement le petit "Hello World" :
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.
- 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 :
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; |
Un exemple de résultat pour le programme hello.bf :
- 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 :
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.
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.
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 : 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
- 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" |
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.
Exécuter le source Whitefuck mouton.wf.
CSC4251-52 (CSC 4536), TELECOM SudParis, P. Hennequin,Last modified: Juillet 2022
