Brainfuck, une machine de Turing

Comme son nom l’indique, ce langage fait des nœuds au cerveau, mais il oblige à un minimum d’organisation si on veut écrire un programme même tout simple. Pour quoi faire ? Vous pouvez répéter la question ? Bon, d’accord : pour que Bolosse 31 puisse parler avec Toto, son petit robot iDiot qui ne comprend que ce langage. Pas de chance, Toto ne comprend pas le Python ni même le C, mais vous pouvez aider Bolosse 31 et simuler son comportement histoire de ne pas l’envoyer dans les limbes d’une boucle infinie.

1. Présentation du langage

Brainfuck (ou BF) est un langage de programmation minimaliste qui contient exactement huit instructions. Nous allons utiliser un dialecte qui en comprend quatre complémentaires, deux pour manipuler les nombres entiers et deux pour déboguer. BF est un langage Turing-complet, ce qui veut dire que théoriquement, vous pouvez coder ce que vous voulez avec. En pratique, c’est une tout autre affaire.

1.1 Le cadre

Brainfuck est une variété de machine de Turing simplifiée constituée :

• d’un ruban de cellules fini, mais non nécessairement borné (des deux côtés dans cet article) sur lequel se déplace une tête de lecture/écriture. Les cellules contiennent des nombres entiers, ici relatifs et sans limites a priori ;
• d’un programme, le code BF exécuté pas à pas ;
• d’une entrée et d’une sortie standards.

 

Certains dialectes de BF comportent en plus une pile (et deux instructions pour empiler et dépiler) ou quelques autres raffinements, parfois des interdictions qui lui enlèvent son caractère Turing-complet. Le langage n’est pas standardisé même s’il existe un paquet pour Debian (hsbrainfuck) ou un autre pour insérer du code BF dans Perl (libacme-brainfck-perl).

1.2 Les instructions

Les huit premières instructions sont celles de BF « standard », les deux suivantes viennent du dialecte BF++ [3] et les deux dernières de la littérature. Oui, Toto ne sait faire que ça.

Pour les exemples, on se basera sur le schéma de la figure 1 :

• , (virgule) : Insère le code ASCII de l’entrée standard dans la cellule courante.
• . (point) : L’inverse du précédent, affiche donc « * » (42 en ASCII correspond au caractère *).
• + : Ajoute 1 à la cellule courante (qui deviendra 43). Toto dépose un petit clou sur la cellule.
• − : L’inverse (41, donc).
• > : Déplace le pointeur d’une cellule vers la droite, donc vers la cellule qui contient 2. Toto avance d’une case.
• < : L’inverse, vers le 0 immédiatement à gauche.
• [ : Si la cellule courante est nulle, va juste après le ] correspondant, sinon passe à l’instruction suivante. Toto déroule son rouleau d’instructions.
• ] : Retourne au [ correspondant. Les boucles sont construites avec ces deux seules instructions.
• ; (point virgule) : Insère la valeur du nombre (entre deux espaces) de l’entrée standard dans la cellule courante en écrasant la valeur présente.
• : (deux points) : L’inverse, affiche « 42 ». Toto répond à LA question. Formidable !
• ! (point d’exclamation) : Affiche l’état de la bande et la position du pointeur par des crochets, utile pour déboguer.
• # : Commentaire, ce qui suit n’est pas interprété jusqu’à la fin de la ligne.

Les deux commandes ; et : permettent de coder plus rapidement des programmes d’arithmétique élémentaire et de s’initier aux subtilités du langage sans devoir comprendre comment utiliser la table ASCII pour traduire une entrée standard numérique en nombres. Nous verrons comment, finalement, nous en passer.

2. L’interpréteur en Python

Le code est un énorme switch, plus quelques traitements préliminaires qui vérifient l’emboîtement des crochets ou suppriment les commentaires éventuels.

Le programme en Python utilisera en entrée deux fichiers : le premier sera le code en BF et le suivant, les données éventuelles de l’entrée standard.

2.1 Les vérifications préliminaires

On commence par vérifier si un code en BF est bien envoyé en entrée :

On continue par une petite analyse syntaxique du code : les crochets doivent être correctement emboîtés et on teste la présence de commandes nécessitant un fichier de données ligne 26. On supprime aussi tous les caractères inutiles, que ce soit ce qui est écrit après un # ligne 23 ou les caractères qui ne sont pas des instructions. Les instructions sont stockées dans code.

S’il y a plus de crochets fermants qu’ouvrants en cours de route ligne 32 ou l’inverse à la fin du traitement ligne 36, on arrête tout.

Si le code nécessite des entrées, on les stocke dans entrees s’il y en a, sinon on s’arrête :

2.2 Toto fait ce qu’on lui demande

Le code est maintenant nettoyé et prêt à être exécuté par Toto, il reste donc à écrire le switch géant.

dp est la position de Toto sur la memoire. Si Toto cherche à dépasser les bornes du ruban à droite ligne 63 ou à gauche ligne 68, on ajoute un 0 où il faut : on ne bloque pas l’exécution du code, on crée ad hoc la memoire nécessaire.

p est la position de l’instruction courante sur son rouleau. Noter que l’instruction virgule ligne 81 ne prend qu’un caractère de l’entrée alors que le point virgule ligne 87 vide les séparateurs éventuels puis construit le nombre jusqu’au séparateur suivant avec l’algorithme de Horner qu’on reverra plus loin.

J’ai ajouté le compteur c pour ne pas planter Toto dans une boucle infinie.

Le code en Python est du type âne qui trotte, mais même Toto ne le comprend pas. Essayons néanmoins de communiquer avec lui.

3. Quelques exemples de codes en BF

L’interpréteur est en Python, on utilise donc son arithmétique, ce qui veut dire que les entiers sont relatifs et sans limites a priori. Attention, BF n’a aucun moyen de savoir si un nombre sur le ruban est positif ou négatif, c’est à vous de prévenir Toto.

Les codes en BF seront expliqués par des commentaires au bout de chaque ligne.

3.1 Arithmétique élémentaire

Ce code écrira le nombre 3 en sortie.

Ce code effectue 4+6=10. En détail :

• dans la première cellule, on part de 0 et on effectue ++++ donc on stocke la valeur 4 ;
• > : on se déplace d'une cellule vers la droite ;
• ++++++ : on stocke le nombre 6. On a donc la cellule précédente qui contient 4 et la suivante (cellule courante) qui contient 6 ;
• [ : début de boucle qui s'arrête si la cellule est nulle, ce qui n'est pas le cas pour l'instant. La boucle effectue :
• < : retour à la case précédente et ajout de 1 (+). Donc les cellules valent 5 et 6 ;
• > : passage à la cellule suivante et on soustrait 1 (-) . Les cellules valent 5 et 5 ;
• ] : retour au début de la boucle.
• < : retour sur la première cellule qui contient le résultat ;
• : : affiche le contenu de la cellule.

On vide la cellule de droite petit à petit, regardez la sortie de ce code, c’est le même avec un point d’exclamation qui affiche l’état du ruban et la position de Toto :

Et voici comment multiplier 6 par 7 :

C’est presque le même code, mais on ajoute 7 à la deuxième cellule chaque fois qu’on décrémente la première. Avec le point d’exclamation pour afficher l’état de la bande, on a :

Toto donne LA réponse, sans tricher et en moins d’un million d’années.

Mais comment multiplier deux nombres qui viennent de l’entrée standard ? Commençons par les additionner :

Si l’entrée contient deux nombres, ce code les ajoute et affiche leur somme.

C’est le même code que pour ajouter sauf qu’on ajoute deux nombres de l’entrée standard et non deux nombres codés en dur. Pas de chance, le code précédent de la multiplication ne fonctionnera pas à cause du multiplicande dans la boucle.

Pour multiplier, on a besoin de planifier l’occupation du ruban pour Toto, c’est malheureux, mais il ne le fera pas pour nous ni même pour son maître, Bolosse 31. Voici :

Premier facteur

Stockage du deuxième

Copie temporaire du deuxième

Produit

Nous allons utiliser la technique de la duplication :

Ce code déplace deux fois la première cellule dans les deux suivantes :

Il faut veiller à anticiper la position de Toto sur le ruban pour qu’il arrive où il faut avant le crochet fermant. En gros, entre une paire de crochets, sauf exception, on veillera à avoir autant de > que de < et surtout, Toto doit arriver à la cellule qu’on teste avant le crochet fermant. Il faut absolument contrôler à tout moment la position de Toto, sinon il va tourner en rond ou partir dans le décor. Usez et abusez de la commande !

Regardez ce que fait ce code :

Toto avance, puis dépose un petit clou sur la cellule courante. Elle n’est donc pas nulle, il recommence et ne s’arrête jamais. Vous avez intérêt à prévoir un ruban jusqu’à la Galaxie d’Andromède voire jusqu’à Zotra plus une réserve de clous qui entre dans le TARDIS.

La division est plus complexe, vous commencez à deviner pourquoi. On le verra plus loin.

3.2 Bonjour tout le monde

Comment faire parler Toto, par exemple lui faire dire « Bonjour ! » ? Il suffit de lire une table ASCII et de construire les nombres qui vont bien. Cela dit, sans l’astuce précédente pour multiplier, c’est vite infernal.

Les codes ASCII sont, respectivement 66, 111,110,106,110,117, 114, 32 et 33. Nous allons donc construire 32=4×8, 64=2×32 et 96=3×32, puis décliner le reste en fonction de ces trois-là.

C’est plus simple avec une ou deux astuces, non ?

3.3 Les carrés

On peut utiliser l’idée du code erroné de la fin de la section 3.1. pour faire recopier le même nombre autant de fois que l’entrée standard le dit. Observez ce code sachant que l’entrée est 7 :

La cellule n°2 est en fait la cellule qui contient initialement 7. [>] oblige Toto à aller à la première cellule nulle tout à droite. La suite lui ajoute 1, retourne juste une cellule à gauche de là où il y a le 7, revient sur le 7 et décrémente. On recommence jusqu’à ce que la cellule 2 soit nulle.

Avec ceci et l’identité remarquable (n+1)²=n²+(2n+1), on peut construire la suite des carrés par récurrence.

Voici ce que ça donne si on remplace les deux points par un point d’exclamation :

On pourrait sûrement factoriser le code (on a deux fois >[++>]<[<]>), mais le code fonctionne et Bolosse 31 est déjà bien content de s’être fait comprendre par Toto.

3.4 Factorielle

La factorielle de 7 est 7!=1×2×3×4×5×6×7=5040.

Reprenons l’astuce précédente pour écrire la suite décroissante des entiers de 5 à 1 (si l’entrée vaut 5) :

Nous allons utiliser deux cellules à droite pour le stockage temporaire, comme dans la multiplication.

Regardez comme Toto fait de belles choses :

Étonnant, non ? Remplacez chaque ! par un : et vous obtenez la suite des factorielles. Remarquez le résidu des deux cellules à gauche de Toto qu’on supprime avec [-] à l’avant-dernière ligne.

Notez qu’avec des additions au lieu de multiplications, on peut calculer les nombres triangulaires.

3.5 La suite de Fibonacci

Je rappelle qu’une suite de Fibonacci est une suite linéaire récurrente d’ordre 2, c’est-à-dire que si les deux premiers termes sont uO=1 et u₁=3, u₂=uO+u₁=4 et u₃=u₁+u₂=3+4=7. De manière plus générale, si n est un nombre entier positif, u_n+2=u_n+1+u_n ; on a besoin des deux premiers termes uO et u₁ de la suite pour calculer les autres de proche en proche, autrement dit, par récurrence.

L’entrée contient le rang du dernier terme à afficher, le premier terme uO et le deuxième u₁ de la suite. Voici le tableau du ruban :

n

Tampon

Tampon

un

un+1

Et le code :

Voici :

Comme d’habitude, remplacez le point d’exclamation par les deux points pour afficher les termes de la suite.

La longueur de ce code n’est pas optimisée, on peut la ramener à 31 instructions.

3.6 La division

Commençons par la division euclidienne par 3, qui affiche le quotient entier et le reste. Voici la disposition des variables dans la memoire :

Dividende

Accumulateur borné par le diviseur

Copie de cet accumulateur

A-t-on soustrait le diviseur (booléen) ?

Quotient

La cellule appeléeaccumulateur est décrémentée de 1 à chaque fois que le dividende l’est. Dès que l’accumulateur atteint 0, le quotient augmente de 1 et l’accumulateur revient à 3.

Voici ce que cela donne :

Le quotient de la division euclidienne de 7 par 3 est 2 et le reste vaut 1 car 7=2×3+1.

Oui, mais si on veut que le diviseur vienne aussi de l’entree ? Bolosse 31 sait comment faire : il lui faut une copie de sauvegarde du diviseur (par exemple une cellule à gauche du dividende) qu’il dupliquera à chaque fois qu’apparaissent dans le code des +++ ou des ++ (auquel cas il soustraira 1 immédiatement). Il n’oubliera pas de rétablir la copie de sauvegarde à sa place, car la duplication la vide. Je vous laisse faire.

3.7 Pour aller plus loin

Autrement dit, comment revenir au BF pur, sans : ni ; ?

Voici, en pseudo-code pythonique, l’algorithme qui remplace les deux points, il s’agit de l’algorithme de Horner pour l’évaluation des polynômes :

Le code ASCII des dix chiffres est 48+chiffre.

Voyons ce que ça donne en BF. Il sera déjà bon de sauvegarder quelque part les valeurs de 32 et de 16, pour ne pas saturer le code d’un nombre illisible de + successifs. Voici la disposition des cellules :

32

16

Code ACSII du caractère courant

Tampon à sauvegarde

Nombre voulu

Voici le code :

Voici le résultat :

Et pour l’affichage avec le point, c’est l’algorithme réciproque, on a besoin de la division euclidienne par 10.

Voici l’algorithme en pseudo-code :

Il peut se terminer par l’affichage d’un espace.

Il s’agit à peu de choses près de l’algorithme de division, mais emboîté dans la boucle de stockage. Vous savez aussi comment stocker un nombre à la fin d’une file de nombres non nuls (ils le seront, car on a ajouté 48). Faites-le vous-même !

Conclusion

Voilà, Bolosse 31 a quelques techniques pour rendre Toto utile. Il aura du mal à lui faire résoudre un sudoku, mais il pourra tout de même lui faire faire quelques tâches élémentaires.

Si vous voulez écrire des programmes en BF plus élaborés, vous pouvez écrire votre propre langage [4] constitué de macros ajoutées au BF. Vous accélérerez l’écriture du code en utilisant par exemple :

• DUP(a,b,c) qui duplique la cellule a sur les cellules b et c,
• MUL2(a,b)=DUP(a,b,b),
• PLUS(a,b) qui déplace la cellule a sur la cellule b (si b=0), sinon qui ajoute a sur b,
• MUL(a,b,c,d) qui multiplie les cellules a et b, stocke le résultat en c et utilise comme tampon la cellule d.

Et ainsi de suite. Le code ainsi créé sera probablement moins joli qu’un autre écrit à la main, préparé aux petits oignons. Attention, les lettres dans les macros désignent des coordonnées relatives à la position de Toto au début de la macro.

Voici quelques algorithmes en BF que j’ai vu passer sans les avoir codés moi-même (je ne suis pas fou à ce point) : la factorisation en produit de facteurs premiers d’un entier, l’algorithme de Syracuse, des quines (code qui écrit son propre code sur la sortie standard), rot13 et même un décodeur de DVDCSS et interpréteur de BF en BF. À quand Nethack ?

Et pour finir, voici un cadeau de saison sur Ideone [5].

Références

[1] Prcovic N., « Les machines de Turing », GNU/Linux Magazine n° 174, septembre 2014, p. 24 à 31.

[2] Raynaud M., « Apprenez à programmer avec une machine de Turing ! », Bulletin vert de l’APMEP n°510, septembre-octobre 2014, p. 471 à 484. Voir aussi le site http://www.machinedeturing.org/ où l’auteur présente sa machine physique fonctionnelle.

[3] Page sur BF++ de Code Abbey : http://www.codeabbey.com/index/wiki/brainfuck.

[4] Colombo T., « Créez votre langage de programmation », GNU/Linux Magazine n° 175, octobre 2014, p. 24 à 36.

[5] Programme en Brainfuck : http://ideone.com/nLwtdt. Ne le lancez pas depuis Ideone, mais dans une console. La version commentée est ici : http://ideone.com/L5lJjP.