CSC4251-4252– Compilation : De l'algorithme à la porte logique

Portail informatique

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" :

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 :
Un couple de spécification pour le traducteur : et les deux fichiers de prologue et épilogue :

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 :

  • 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.
Un couple de spécification pour le traducteur compact : en utilisant les mêmes fichiers de prologue et épilogue précédents

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 :
Un couple de spécification pour le traducteur vers Java version compacte : N.B. : bf2java.jflex == bf2c.jflex et les deux fichiers de prologue et épilogue :

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.
Un couple de spécification pour l’interpréteur version compacte : N.B. : bfInterp.jflex == bf2c.jflex

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 : 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.
Les temps sont en seconde pour une machine :
Architecture : x86_64 Processeur(s) : 4 Thread(s) par cœur : 1 Cœur(s) par socket : 4 Nom de modèle : Intel(R) Xeon(R) CPU E5-1607 v3 @ 3.10GHz Vitesse du processeur en MHz : 1200.039
Chaine Traduction Compilation
gcc/javac
Exécution
ELF/JVM
Taille source
out.c/out.java
Taille exécutable
a.out/ out.class
bf2c0 non compact 0.40 0.27 18.6 390 K 86 K
bf2c compact 0.29 0.17 4.0 152 K 45 K
bf2java0 non compact 0.36 2.54 28.2 404 K 93 K
bf2java compact 0.25 2.33 15.5 163 K 35 K
bf2Interp0 non compact 56.5
bf2Interp compact 28.9
Des conclusions :
  • Le compactage des instructions PRT et VAL donne un gain très significatif dans tous les cas.
  • Java produit un surcoût important par rapport à C. A priori, c'est lié à l’interprétation par la JVM qui est ici dans une situation assez défavorable par rapport à ELF (on exécute du code très simpliste). La machine Brainfuck en Java fera aussi du contrôle de débordement sur le tableau bande[], ceci n'est pas fait en C.
  • L’interpréteur Brainfuck est largement plus lent qu'une chaîne de traduction. De façon générale, un interpréteur est plus "convivial" mais moins rapide.
La vraie conclusion : tout ceci n'est pas très grave, car en fait la vocation de notre chaîne d’exécution n'est pas d'être utilisée régulièrement, mais d'être utilisée une seule fois pour créer un Compilateur BF2ELF. Le compilateur deviendra la chaîne d’exécution performante (cf. question suivante).

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 ?
  • Les performances d’exécution du compilateur sont très dépendantes de la chaîne qui a produit le compilateur (cf question précédente).
  • La sortie du compilateur est indépendante de la chaîne de production.
    La sortie du compilateur est l'application de l'algorithme "mystérieux" codé dans BF2ELF.bf. Les résultats en sortie seront donc identiques, à condition bien sûr que les chaînes de production soient correctes, c'est-à-dire respectent la sémantique d’exécution de "Brainfuck".
Sur le modèle de la question précédente, on a les temps
Chaine Production du compilateur Compilation de mandelbrot.bf Exécution de mandelbrot
bf2c0 non compact 0.51 5.14 3.49
bf2c compact 0.36 4.55 ==
bf2java0 non compact 2.32 18.9 ==
bf2java compact 2.03 18.6 ==
bf2Interp0 non compact 38.1 ==
bf2Interp compact 35.3 ==

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 !
La génération du compilateur ultime :
"execution de BF2ELF" < BF2ELF.bf > bfComp chmod +x bfComp
Le résultat bfComp est indépendant de la chaîne qui a produit "exécution de BF2ELF". Le temps de génération du compilateur varie de 0.66 secondes pour bf2c à 5.74 secondes pour bfInterp0.
En fait, le vrai temps de génération du compilateur est le temps nécessaire pour écrire les spécifications du traducteur ou de l’interpréteur !!! C'est en gros la durée du TP, en sachant qu'une fois que l'on a notre ultime compilateur, on peut jeter le reste ! Même si l'on écrit une nouvelle version du compilateur BF2ELF_v2.bf, on utilisera le compilateur ultime de la version 1 pour créer directement le compilateur ultime de la version 2. Un schéma comparable est aussi possible si l'on veut changer de version du langage lui-même.

La chaîne ultime d’exécution est maintenant :
./bfComp < mandelbrot.bf > mandelbrot chmod +x mandelbrot ./mandelbrot
Le temps de création de l’exécutable mandelbrot est maintenant de 0.8 secondes au lieu de 4.55 secondes dans le meilleur des cas de la question précédente. L’exécutable lui-même et son temps d’exécution reste inchangé.

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.
Les deux traducteurs en JFlex Ou les variantes Yawf en JFlex L’exécution de mouton.wf imprime "ceci n'est pas un mouton!\n".
mouton.wf est généré en utilisant https://copy.sh/brainfuck/text.html
Il correspond au code Brainfuck :

CSC4251-52 (CSC 4536), TELECOM SudParis, P. Hennequin,Last modified: Juillet 2022