CSC4536– Compilation : De l'algorithme à la porte logique

Portail informatique
Paradoxe du bootstrap, Compilation d'un compilateur. Comparaison compilateur/interpreteur, Exemple de langage esotérique Le but de l'exercice est de pouvoir éxecuter des programmes écrits dans le langage esotérique Brainfuck.
On cherchera en particulier à comparer différentes stratégies:
  • utilisation d'un compilateur
  • écriture d'un intétpréteur
  • traduction vers un autre langage

On dispose d'un compilateur Brainfuck. Chouette ! mais l'exercice n'est pas très interessant ? 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'éxecuter le compilateur pour faire une version éxecutable du compilateur ? l'oeuf 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éfiniton et les différents concepts liés au paradoxe du bootstrap.

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 wikipedia(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 :
CodeNomSignificationTraduction CTraduction Java
>PTR_INCIncrémenter le pointeur de donnéesptr++;ptr++;
<PTR_DECDécrémenter le pointeur de donnéesptr--;ptr--;
+VAL_INCIncrémenter l'octet pointé(*ptr)++;bande[ptr]++;
-VAL_DECDécrémenter l'octet pointé(*ptr)--;bande[ptr]--;
.PUTCHARÉcrire l'octet pointé sur stdoutputchar(*ptr);System.out.write(bande,ptr,1)
,GETCHARLire un octet sur stdin et l'écrire
sur la bande à l'octet pointé
(*ptr)=getchar();System.in.read(bande,ptr,1);
[LOOP_INSi l'octet pointé est nul, sauter en avant
après l'instruction LOOP_OUT correspondante
while(*ptr){while(bande[ptr]!=0){
]LOOP_OUTSi 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'éxecution 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 !!

L'archive 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",
  • Un programme de démo plus gourmand en temps d'éxecution,
  • Le fameux Compilateur
Ne pas essayer de comprendre les sources Brainfuck. Enfin c'est vous qui voyez !
Eventuellement le petit "Hello World!" :

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 tard Écrire un traducteur de Brainfuck vers C en utilisant Jflex et Cup. Tester sur les exemples.
Pour executer un fichier C "out.c", faire gcc out.c; ./a.out; rm a.out;
  • Utiliser "Memento Cup/Code Utilisateur" pour l'utilisation des actions en milieut de règle ou la réalisation d'actions finales ou initiales.
  • Un exemple de resultat pour le programme "hello.bf"


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

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 :
CodeNomTraduction CTraduction Java
>NPTR(N)ptr+=N;ptr+=N;
<NPTR(-N)ptr+=-N;ptr+=-N;
+NVAL(N)(*ptr)+=N;bande[ptr]+=N;
-NVAL(-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 resultat 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 rétourner un token PTR avec une valeur sémantique égale à la taille de la séquence (methode 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 proloque et épilogque précédents

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

Pour executer rapidement une classe Java "out.java", faire javac out.java; java out; rm out.class;

Un exemple de resultat pour le programme "hello.bf"
Un couple de spécification pour le traducteur vers Java version compacte : NB: bf2java.jflex == bf2c.jflex et les deux fichiers de proloque et épilogque :
La question est un peu plus difficile. On pourra éventuellement se contenter d'analyser le corrigé et de l'uitiliser 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'éxecution sur l'arbre.
On donne un squelette de code pour réaliser la machine Brainfuck et la structure d'AST dans la spécification Cup. Un couple de spécification pour l'interpreteur version compacte : NB: bfInterp.jflex == bf2c.jflex

Sur l'exemple (ou d'autres exemples), comparer les performances des différentes chaînes d'éxecutions produites dans les questions précédentes :
  • "bf2c" : Traduction vers C (compact ou non) / gcc / execution ELF
  • "bf2java": Traduction vers java (compact ou non) / javac / execution JVM
  • "bfInterp": Interprétation (avec execution 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'execution.
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 executable de l'analyseur construit sur les spécifications spec/xxx.cup et spec/xxx.jflex. L'analyseur s'execute alors avec java -jar xxx.jar (ou time java -jar xxx.jar)
  • la commande make runc pour executer et tracer un fichier "out.c",
  • la commande make runjava pour executer 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
java -jar xxx.jar <mandelbrot.bf
Compilation
gcc / javac
Execution
ELF / JVM
Taille source
out.c / out.java
Taille exec
a.out / out.class
bf2c0 non compact0.400.2718.6 390K86K
bf2c compact0.290.174.0 152K45K
bf2java0 non compact0.362.5428.2 404K93K
bf2java compact0.252.3315.5 163K35K
bf2Interp0 non compact56.5
bf2Interp compact28.9
Des conclusions :
  • Le compactage des instructions "PRT" et "VAL" donne un gain très significatif dans tout les cas
  • Java produit un surcoût important par rapport à C. A priori, c'est lié à l'interpretation par la JVM qui est içi dans une situation assez défavorable par rapport à ELF (on éxecute du code très simpliste). La machine Brainfuck en Java fera aussi du contrôle de debordement sur le tableau "bande", ceci n'est pas fait en C.
  • L'interpreteur 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'éxecution 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'éxecution performante. (cf. question suivante)

Créer une execution du compilateur Vous pouver utiliser les différentes chaînes d'éxecution précédentes. Selon la chaîne, l'éxecution 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'éxecution pour brainfuck, sous la forme : "execution 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'execution du compilateur dépend t'il de la chaîne d'éxecution utilisée pour produire le compilateur ? Pourquoi ?
  • La sortie du compilateur (i.e. mandel.elf) dépend t'elle de la chaîne d'éxecution utilisée pour produire le compilateur ? Pourquoi ?
  • Les performances d'éxecution 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'éxecution de "Brainfuck".

Sur le modèle de la question précédente, on a les temps
Chaine Production du compilateur Compilation de mandelbrot.bf Execution de mandelbrot
bf2c0 non compact0.515.143.49
bf2c compact0.364.55==
bf2java0 non compact2.3218.9==
bf2java compact2.0318.6==
bf2Interp0 non compact38.1==
bf2Interp compact35.3==

Créer un éxecutable 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'"éxecution pas terrible" de la question précédente. Quelque soit le chemin suivi, on obtient le même éxecutable 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 "execution de BF2ELF". Le temps de génération du compilateur varie de 0.66s (bf2c) à 5.74s (bfInterp0).
En fait, le vrai temps de génération du compilateur est le temps nécéssaire pour écrire les spécifications du traducteur ou de l'interpreteur !!! 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 changer de version du langage lui-même.

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

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'éxecution est conservée.

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 huits instructions Brainfuck est codée par une séquence de trois caractères blancs en suivant la table de conversion :
BrainfuckNomWhiteFuck
>PTR_INC" "
<PTR_DEC" \t"
+VAL_INC" \t "
-VAL_DEC"\t "
[LOOP_IN"\t\t "
]LOOP_OUT"\t \t"
.PUTCHAR" \t\t"
,GETCHAR"\t\t\t"

Écrire avec Jflex seul, un traducteur Whitefuck vers Brainfuck et un traducteur Brainfuck vers Whitefuck.
Executer le source Whitefuck . Les deux traducteurs en Jflex L'execution 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 :