Compilation : De l'algorithme à la porte logique

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

Un couple de spécification pour le traducteur :

bf2c0.jflex

bf2c0.cup

et les deux fichiers de prologue et épilogue :

pre_out.c

post_out.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.

Un couple de spécification pour le traducteur compact :

bf2c.jflex

bf2c.cup

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 :

hello.java

Un couple de spécification pour le traducteur vers Java version compacte :

bf2java.jflex

N.B. : bf2java.jflex == bf2c.jflex

bf2java.cup

et les deux fichiers de prologue et épilogue :

pre_out.java

post_out.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

Un couple de spécification pour l’interpréteur version compacte :

bfInterp.jflex

N.B. : bfInterp.jflex == bf2c.jflex

bfInterp.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.

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.

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

wf2bf.jflex

bf2wf.jflex

Ou les variantes Yawf en JFlex

wwf2bf.jflex

bf2wwf.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 :

mouton.bf

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