En 1993, un étudiant allemand nommé Urban Müller a créé un langage de programmation minimaliste pouvant fonctionner sur une machine de petite capacité. N'utilisant que huit instructions, son créateur lui-même doutait que quiconque puisse programmer quoi que ce soit d'utile avec ce langage...
De part son aspect exotique et sa difficulté d'utilisation, ce langage a été nommé Brainfuck (inutile de traduire...). On en présente ici une version spécifique à CodEx.
Description du langage
Un interpréteur de Brainfuck est une machine constituée des éléments suivants :
Une chaîne de caractères pour le programme, qui contient les instructions à exécuter ;
Un tableau de mémoire qui permet de stocker des informations et de les modifier au besoin ;
Un flux d'entrée, qui permet à l'utilisateur d'entrer des données dynamiques au cours de l'exécution du programme ;
Un flux de sortie, qui permet d'afficher le résultat des exécutions.
La mémoire est donc modélisée par un tableau. Dans sa description classique, Brainfuck utilise un tableau de 30 000 cases, mais dans le cadre de cet exercice on limite la taille du tableau à 10 cases.
Les cases du tableau peuvent stocker des nombres entiers codés sur un octet. On considère dans cet exercice que les valeurs sont des nombres positifs entre 0 et 2551. Si jamais une opération a pour résultat une valeur sortant de cet intervalle, on « boucle » sur celui-ci. Ainsi, dans la mémoire, 255+1=0 et 0-3=253.
L'interpréteur utilise un pointeur, sous forme d'un nombre entier, lui permettant de conserver l'indice de la case mémoire actuellement utilisée. Initialement ce pointeur désigne la première case du tableau (d'indice 0).
Le programme est une simple chaîne de caractères, chacun d'entre eux correspondant à une instruction. L'interpréteur utilise un compteur lui permettant de garder trace de l'indice dans la chaîne de caractères de l'instruction en cours. Initialement ce compteur désigne la première instruction du programme (d'indice 0). L'exécution s'arrête lorsque ce compteur se retrouve en dehors du programme (et donc lorsque le compteur devient égal à la longueur du programme).
Le langage utilise huit instructions s'écrivant avec les symboles ><+-.,[] et qui sont décrites ci-dessous :
Instruction
Rôle
>
Ajoute 1 au pointeur. On passe donc à la case de droite dans la mémoire
<
Soustrait 1 au pointeur. On passe à la case de gauche dans la mémoire
+
Ajoute 1 à la valeur de la case mémoire pointée actuellement
-
Soustrait 1 à la valeur de la case mémoire pointée actuellement
.
Ajoute à la sortie le caractère ASCII correspondant à la valeur de la case mémoire pointée actuellement
,
Lit un caractère sur le flux d'entrée et stocke son code ASCII dans la case mémoire pointée actuellement
[
Incrémente le compteur jusqu'au prochain crochet fermant correspondant à celui à la position actuelle si la valeur de la case pointée est nulle
]
Décrémente le compteur jusqu'au précédent crochet ouvrant correspondant à celui à la position actuelle si la valeur de la case pointée est non nulle
Le flux de sortie est modélisé par une chaîne de caractères qui regroupe l'ensemble des caractères affichés au fil de l'exécution.
Le flux d'entrée sera mis en place à l'aide de la fonction builtininput qui demande à l'utilisateur de taper un caractère durant les exécutions.
La chaîne de caractères "++>---." est donc un exemple de programme Brainfuck. Ce programme incrémente deux fois la première case de la mémoire (elle contient alors la valeur 2), décale le pointeur d'une case à droite, décrémente la valeur de celle-ci trois fois (elle contient la valeur 253) puis affiche le caractère "ý" correspondant à ce code ASCII.
L'ensemble de ces instructions permettent, entre autres choses, de simuler une machine de Turing. Brainfuck est donc turing-complet ce qui signifie qu'il est possible d'y coder tout ce que peut coder Python !
Rôle des crochets: [ et ]
Cette partie n'est pas nécessaire pour réaliser l'exercice, mais elle apporte des éclairages sur le fonctionnement du langage Brainfuck.
On voit ci-dessus que lorsqu'il rencontre une instruction de type crochet dans le programme, le comportement de l'interpréteur dépend de la valeur de la cellule mémoire pointée actuellement. Si cela peut paraître surprenant à première vue, ce comportement est néanmoins très important car il est à la base de nombreuses « constructions » (au sens de syntaxes) qui permettent de recréer des éléments algorithmiques essentiels : conditions (if) et boucles (while) notamment :
au moment où le compteur est sur un crochet ouvrant [ :
si la cellule mémoire pointée actuellement est non nulle, l'interpréteur va exécuter les instructions entre ce crochet et son fermant correspondant ;
sinon, ces instructions ne seront pas exécutées.
Ceci permet donc de construire un test ifcellule!=0: ;
dans le cas où le code entre crochets est exécuté, si à l'issue de cette exécution la même cellule mémoire est pointée et qu'elle contient une valeur non nulle, l'interpréteur revient au crochet ouvrant correspondant. Cette construction permet donc de mettre en place une boucle whilecellule!=0:.
L'objectif de cet exercice est d'écrire un interpréteur de Brainfuck (et pas d'écrire des programmes dans ce langage ). Le site https://brainfuck.net/ permet néanmoins de faire quelques essais.
De façon générale, on garantit que dans toutes les questions :
tous les programmes proposés dans les tests sont bien formés :
les instructions ne font pas sortir de la mémoire (on ne fera jamais 11 décalages consécutifs sur la droite par exemple) ;
les crochets sont cohérents (on ne rencontre pas de cas tels que "[]]") ;
les valeurs saisies par l'utilisateur ont toutes des codes ASCII compris entre 0 et 255.
Pour représenter l'état de l'interpréteur on utilise un dictionnaire. Celui-ci contient plusieurs couples {clé:valeur} détaillés ci-dessous :
Clé
Valeur à l'initialisation
Rôle
"programme"
le programme à exécuter
Permet de récupérer l'instruction à exécuter
"compteur"
0
Indice de la prochaine instruction à exécuter dans le programme
"mémoire"
[0]*10
Tableau de mémoire
"pointeur"
0
Indice de la case de la mémoire actuellement manipulée
"sortie"
""
Chaîne de caractères reprenant l'ensemble des caractères ajoutés à la sortie
On insiste sur le fait que l'on manipule deux indices. Si bf est le dictionnaire décrivant l'état de l'interpréteur :
bf["compteur"] est l'indice de l'instruction étudiée dans le programme. Lors de l'exécution, cet indice évolue entre 0 et len(programme) (le plus souvent en passant à l'instruction suivante sauf dans le cas des crochets qui peuvent décaler le compteur vers l'avant ou l'arrière de plus d'une unité). Lorsque la fin du programme est atteinte, si bf["compteur"]==len(programme), l'exécution s'arrête ;
bf["pointeur"] est l'indice de la case de la mémoire considérée. Celle-ci comportant toujours 10 cases, bf["pointeur"] prend des valeurs comprises entre 0 et 9 (inclus).
De plus, bf["sortie"] permet de stocker l'ensemble des caractères affichés au fil de l'exécution. Ainsi, si un programme affiche successivement "a" puis "b", bf["sortie"] vaudra "ab" à la fin de l'exécution.
Exemple de dictionnaire
À la fin de l'exécution du programme "++>---.", le dictionnaire bf décrivant l'interpréteur aura les valeurs suivantes :
On pourra remarquer que le "compteur" a pour valeur 7 qui est la longueur du programme. La sortie contient quant à elle le caractère 'ý' dont le code ASCII est 253.
Le codage d'un interpréteur complet nécessitant plusieurs étapes, nous allons découper l'ensemble du programme en plusieurs fonctions.
Mis à part la fonction interpreteur, toutes ces fonctions renvoient le dictionnaire décrivant l'état de l'interpréteur. Ce choix permet de simplifier les test mais n'est pas indispensable. En effet, le dictionnaire d'état passé en paramètre des fonctions est mutable : celles-ci manipulent toutes le même objet et les modifications effectuées par l'une sont toujours visibles par les autres.
Fonction
Paramètre
Rôle
creation
Le programme à exécuter programme
Crée le dictionnaire décrivant l'interpréteur
incremente
Le dictionnaire décrivant l'interpréteur bf
Augmente de 1 la valeur de la case mémoire pointée
decremente
Le dictionnaire décrivant l'interpréteur bf
Diminue de 1 la valeur de la case mémoire pointée
droite
Le dictionnaire décrivant l'interpréteur bf
Augmente de 1 la valeur du pointeur
gauche
Le dictionnaire décrivant l'interpréteur bf
Diminue de 1 la valeur du pointeur
sortie
Le dictionnaire décrivant l'interpréteur bf
Ajoute le caractère correspondant à la valeur de la case mémoire pointée à la sortie
entree
Le dictionnaire décrivant l'interpréteur bf
Donne à la case pointée le code ASCII correspondant au caractère saisi par l'utilisateur
fermant_correspondant
Le dictionnaire décrivant l'interpréteur bf
Incrémente compteur jusqu'à l'instruction "]" correspondante
ouvrant_correspondant
Le dictionnaire décrivant l'interpréteur bf
Décrémente compteur jusqu'à l'instruction "[" correspondante
interpreteur
Le programme à exécuter programme
Exécute le programme passé en paramètre
Les questions ci-dessous demandent de coder ces différentes fonctions. Elles sont indépendantes. Seule la dernière question qui demande de coder l'interpréteur complet utilise les fonctions précédentes.
Fonction creation
La fonction creation prend en paramètre un programme à exécuter et renvoie le dictionnaire décrivant l'interpréteur dans son état initial.
La fonction incremente prend en paramètre un dictionnaire décrivant l'état de l'interpréteur et incrémente
la valeur de la case pointée.
Cette fonction renvoie le dictionnaire modifié.
On rappelle que les valeurs de la mémoire sont des entiers compris entre 0 et 255. Si la valeur obtenue après l'incrémentation dépasse 255, on la remet à 0.
La fonction droite prend en paramètre un dictionnaire décrivant l'état de l'interpréteur et décale le pointeur d'une case vers la droite. Sa valeur est donc augmentée de 1.
On garantit que cette action ne fera pas sortir de pointeur de l'intervalle \([\,\)0\(\,;\,\)9\(\,]\).
La fonction gauche prend en paramètre un dictionnaire décrivant l'état de l'interpréteur et décale le pointeur d'une case vers la gauche. Sa valeur est donc diminuée de 1.
On garantit que cette action ne fera pas sortir de pointeur de l'intervalle \([\,\)0\(\,;\,\)9\(\,]\).
La fonction sortie prend en paramètre un dictionnaire décrivant l'état de l'interpréteur et ajoute à la sortie le caractère correspondant à l'entier dans la case pointée actuellement.
On rappelle que la sortie stocke l'ensemble des caractères affichés. À l'issue de l'exécution cette variable contient l'ensemble des caractères affichés dans leur ordre d'affichage.
On rappelle que la fonction chr renvoie le caractère dont le code ASCII est passé en paramètre. On a ainsi
chr(97)=='a'.
La fonction entree prend en paramètre un dictionnaire décrivant l'état de l'interpréteur,
demande à l'utilisateur de saisir un caractère ASCII et donne à la case pointée actuellement le code ASCII de ce caractère.
On rappelle que la fonction ord renvoie le code ASCII du caractère passé en paramètre. On a ainsi
ord('a')==97.
De plus, la fonction input permet de demander à l'utilisateur de saisir une chaîne de caractères et renvoie celle-ci.
Les entrées saisies dans les tests automatiques sont valides :
elles ne comportent qu'un unique caractère ;
le code ASCII de celui-ci est compris entre 0 et 255.
Lors de vos tests, vous devrez aussi respecter ces contraintes et ne pas saisir d'emoji par exemple ou de chaînes de deux caractères ou plus.
Cette fonction renvoie le dictionnaire modifié.
Exemple
>>> bf={'programme':',','compteur':0,'mémoire':[0,0,0,0,0,0,0,0,0,0],'pointeur':0,'sortie':''}>>> entree(bf)# l'utilisateur saisit 'a' dont le code ASCII est 97{'programme': ',', 'compteur': 0, 'mémoire': [97, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'pointeur': 0, 'sortie': ''}
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
La fonction fermant_correspondant prend en paramètre un dictionnaire décrivant l'état de l'interpréteur et modifie le compteur afin de lui donner la valeur de l'indice dans le programme du crochet fermant correspondant.
Cette fonction recherche l'indice du crochet fermant et correspondant et pas celui de l'instruction suivante. C'est la fonction interpreteur qui se chargera de décaler cette valeur d'une unité.
Cette fonction renvoie le dictionnaire passé en paramètre.
Attention, les programmes Brainfuck utilisent beaucoup de crochets et bien souvent ceux-ci sont imbriqués comme dans "[->[+<]]"2. Dans cet exemple :
si on appelle la fonction fermant_correspondant alors que l'interpréteur désigne le premier crochet ouvrant, elle doit renvoyer l'indice du dernier ;
si on appelle la fonction fermant_correspondant alors que l'interpréteur désigne le deuxième crochet ouvrant, elle doit renvoyer l'indice de l'avant-dernier.
On garantit que lorsque la fonction fermant_correspondant est appelée, le compteur de l'interpréteur désigne une instruction "[".
On garantit de plus que les programmes proposés sont bien formés (les crochets sont bien structurés et l'on ne rencontre pas de cas tels que "[[]" ou "][").
Aide
Une approche consiste à utiliser une variable, que l'on pourra nommer pile, qui tient le compte des crochets rencontrés. On initialise cette variable à la valeur +1 puis on progresse dans le programme. Si l'instruction lue est un crochet ouvrant on incrémente pile, si c'est un crochet fermant on la décrémente.
Lorsque pile vaut 0 on a trouvé le crochet fermant correspondant à l'ouvrant de départ.
On conseille d'avoir bien compris la question précédente avant d'aborder celle-ci.
La fonction ouvrant_correspondant prend en paramètre un dictionnaire décrivant l'état de l'interpréteur et modifie le compteur afin de lui donner la valeur de l'indice dans le programme du crochet ouvrant correspondant.
Comme dans la fonction précédente, cette fonction fonction décale le pointeur jusqu'au crochet correspondant, pas jusqu'à l'instruction qui le suit.
Cette fonction renvoie le dictionnaire passé en paramètre.
On garantit que lorsque la fonction ouvrant_correspondant est appelée, le compteur de l'interpréteur désigne une instruction "]".
On garantit de plus que les programmes proposés sont bien formés (les crochets sont bien structurés et l'on ne rencontre pas de cas tels que "[[]" ou "][").
À ce stade, nous avons écrit la fonction permettant d'initialiser l'interpréteur et celles correspondants à chacune des instructions. Nous pouvons donc écrire l'interpréteur, enfin !
La fonction interpreteur prend en paramètre un programme Brainfuck, crée le dictionnaire décrivant son état puis exécute le programme. Elle renvoie l'état final de la sortie.
Une version valide de chacune des différentes fonctions étudiées plus haut est déjà chargée dans l'éditeur. Vous pouvez donc les utiliser directement, sans avoir à les importer.
Une fois l'initialisation de l'interpréteur effectuée, cette fonction s'organise autour d'une boucle Tant que :
Algorithme simplifié
Fonction interpreteur(programme):
Initialiser l'état de l'interpréteur
Tant que le compteur n'a pas atteint la fin du programme:
Lire l'instruction à effectuer
Effectuer cette instruction en envisageant les 8 cas possibles
Incrémenter le compteur
Renvoyer la sortie de l'interpréteur
On n'oubliera pas de relire les définitions des instructions, en particulier celles relatives aux crochets.
Exemples
Comme son nom l'indique, le premier programme testé effectue l'addition 3+2 et affiche le résultat. Le caractère résultant, de code ASCII 5, n'est pas affichable dans la console (il s'agit du caractère ENQ). Python l'affiche donc en hexadécimal '\x05' (en effet \(05_{16}=5_{10}\)).
). Le site https://brainfuck.net/ permet néanmoins de faire quelques essais.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)