Introduction au Brainfuck

Développement informatique

Depuis les débuts de l’informatique, les développeurs s’attèlent à créer des langages informatiques de haut niveau, c’est à dire plus proche des langues naturelles que du langage machine (par opposition aux langages bas niveaux qui sont eux extrêmement proche du langage machine, donc moins facilement compréhensible par un humain). L’idée étant de simplifier au maximum le travail du développeur et ainsi de produire plus en moins de temps et moins d’efforts. Mais il arrive que les développeurs, s’ennuyant entre deux tâches, s’amusent à se lancer des défis fous qui vont à l’encontre même de l’évolution. C’est ainsi qu’en 1993, et en s’inspirant du FALSE (dont le but était selon son auteur « d’embrouiller les gens avec une syntaxe obscure »), Urban Müller se lance le défi de créer un langage de programmation simple dont le compilateur (une sorte de traducteur entre le langage de programmation et le langage machine) aurait la taille la plus réduite possible: le Brainfuck.

"Hello World!" écrit en Brainfuck: ++++++++++[>+>+++>+++++++>++++++++++<<<<-]>>>++.>+.+++++++..+++.<<++.>+++++++++++++++.>.+++.------.--------.<<+.<.
« Hello World! » écrit en Brainfuck (notez que les retours à la ligne sont optionnels, ils permettent juste une meilleure lisibilité)

Qu’est-ce que le Brainfuck ?

Le Brainfuck est un langage de programmation composé uniquement de 8 instructions (ce qui est très peu). Pour le visualiser simplement, imaginez un calendrier de l’avent contenant des chocolats… à 30.000 cases (initialement le Brainfuck n’acceptait que 30.000 mémoires, ce qui n’est plus le cas de certains compilateurs récents). Au début vous commencez sur la case 1 et les cases ne contiennent aucun chocolat, les différentes instructions sont:

  • > qui permet de vous déplacer vers la case du jour suivant;
  • < qui permet de vous déplacer vers la case du jour précédent;
  • + qui permet d’ajouter un chocolat dans la case sur laquelle vous êtes;
  •  qui permet de retirer un chocolat dans la case sur laquelle vous êtes;
  • . qui permet d’afficher le nombre de chocolats dans la case;
  • , qui permet d’entrer directement le nombre de chocolats;
  • [ qui permet de commencer une boucle si la case sur laquelle vous êtes n’est pas vide;
  • ] qui permet de fermer la boucle.

J’aimerai apporter des précisions sur les 4 dernières instructions. Le point ne permet pas d’afficher directement la valeur de la case mais le caractère ASCII correspondant au nombre de chocolats dans la case, par exemple pour afficher le caractère « a », il faudra 97 chocolats dans la case (cf. tableau suivant).

Table des valeurs ASCII
Sur cette table on peut voir que pour afficher « 0 », il faut la valeur ASCII 48 et que pour afficher « A » il faut la valeur 65.

La virgule permet d’entrer la valeur ASCII du caractère tapé par l’utilisateur (donc le très court programme « ,. » vous permet d’afficher le symbole entré par l’utilisateur). Quant à la boucle elle a un fonctionnement particulier: le code entre les deux crochets va s’exécuter jusqu’à ce que la case sur laquelle vous êtes au moment où vous croisez le « ] » ne contienne plus aucun chocolat. Si la case sur laquelle vous êtes au moment où vous arrivez sur le « [ » est vide, vous ignorez tout ce qui se trouve entre les deux crochets.

Petit exemple pratique: on veut remplir une case avec 20 chocolats. Plusieurs options s’offrent à nous ! Tout d’abord, on pourrait se contenter d’écrire 20 fois le symbole « + » pour ajouter les 20 chocolats. Le soucis c’est que non seulement c’est relativement long mais surtout on peut se tromper assez facilement dans les quantité et devoir recompter plusieurs fois. Alors imaginez avec des nombres plus longs encore !

Pour aller plus vite et éviter trop d’erreurs nous allons plutôt essayer d’ajouter 5 fois une série de 4 chocolats, pour cela nous allons nous servir d’une boucle, voici le raisonnement étape par étape:

Tout d’abord visualisez un calendrier à deux cases (nous n’auront pas besoin des 29.998 autres), au début vous serez sur la première case, et le calendrier ressemblera à ceci: [0, 0].

Ajouter 5 chocolats à votre case et vous obtiendrez [5, 0].

C’est là que la boucle commence. Vous allez vous déplacer dans la case suivante, ajouter 4 chocolats, retourner dans la case précédente et en retirer un. Vous obtiendrez alors le calendrier suivant: [4, 4] et vous serez de nouveau sur la première case.

Or vous arrivez à la fin de la boucle mais la case sur laquelle vous êtes contient encore des chocolats, vous devez donc retourner au début de la boucle et recommencer. Vous allez vous déplacer à nouveau dans la case suivante, ajouter 4 chocolats, retourner dans la case précédente et en retirer un. Vous allez donc obtenir le calendrier suivant: [3, 8].

Puis à force de répéter vous allez obtenir petit à petit [2, 12], [1, 16] et [0, 20]. Et là comme la case sur laquelle vous êtes ne contient plus aucun chocolat vous pouvez sortir de la boucle.

En Brainfuck, le programme ressemblerait à ça:

+++++[>++++<-]

Si vous voulez essayer ce petit code, vous pouvez utiliser cet outil en ligne. Il vous suffit de:

  • coller le code dans le champs de texte en haut de page puis de cliquer sur « Run ».
  • une fois le message « Finished in x ms. » affiché, de cliquer sur « view memory » qui permet de voir l’état de toutes les cases.
  • choisir enfin « final dump » (qui sera normalement votre seul choix) qui permet de dire que vous voulez voir l’état des cases à la fin de l’exécution de votre code.

Vous verrez toutes les cases apparaître sous la forme « 000 » sauf la seconde qui aura la valeur « 020 ».

Si j’ai réussi à ne pas vous perdre, félicitation à vous: vous avez compris les bases d’un algorithme. Et c’est tout l’intérêt d’un langage tel que le Brainfuck malgré son apparence peu attirante au premier regard.

La pertinence du Brainfuck: l’aspect pédagogique

En effet, même si le projet Brainfuck n’est pas sérieux à la base (c’est à dire qu’il n’est pas réellement destiné à être utilisé pour créer de vrais projets) il possède un fort potentiel pédagogique ! Pour les non-initiés c’est un parfait moyen de s’initier à la logique algorithmique en créant par exemple des calculateurs simples (nous avons fait au dessus un multiplicateur, mais on pourrait imaginer de faire des additions, des soustractions, des divisions, …). Pour ceux qui ont envie de pousser un peu plus, ils peuvent s’amuser à créer des programmes plus complexes.

Additionneur Brainfuck
Exemple d’un additionneur simple en Brainfuck, cet exemple-ci ne marche que si le résultat est inférieur à 10

Un des aspects que j’ai toujours aimé avec l’informatique c’est justement cette capacité de faire du tout avec du rien. Je me souviens des journées passées sur ma Ti 83+ à développer des jeux en TiBasic au lycée. En apparence, les calculatrices ne semblent pas être un outil des plus performants mais avec un outil simple et un langage simple on peut arriver à créer des choses géniales (j’avais par exemple créé un démineur, un battleship, un Flappy Bird lent et moche, …). Le Brainfuck c’est pareil, l’interface en moins. Avec seulement 8 instructions on peut créer des petits programmes très sympathiques !

Et enfin pour les plus intéressés d’entre vous, l’avantage de la simplicité du Brainfuck c’est que c’est le terrain de jeu idéal pour s’essayer au développement d’un interpréteur, voire d’un compilateur. L’interpréteur permettant simplement d’exécuter le code que vous écrivez alors que le compilateur va permettre de transformer votre code en langage machine. Ici vous n’avez que 8 instructions à gérer, ce qui est l’idéal pour s’échauffer avant de se lancer sur un langage plus complet.

Je me suis moi-même prêté au jeu et vous pouvez trouver l’interpréteur que j’ai créé en Python sur mon Github.

Créons notre premier « mini-jeu » en Brainfuck

Bon, soyons honnêtes: vous ne vous amuserez pas en jouant à ce jeu. Et surtout le système est très loin d’être efficace, mais l’interêt est ici de pousser un peu plus loin la logique Brainfuck afin de créer quelque chose d’interactif. Nous allons donc essayer ensemble de jouer un mini jeu du « Plus ou Moins ». L’idée étant ici que l’ordinateur « devine » un nombre entre 1 et 10 auquel nous pensons.

Tout d’abord, nous allons avoir besoin d’utiliser 3 mémoires:

  • la première qui contiendra l’entrée de l’utilisateur (1 pour « moins », 2 pour « plus » et 0 pour indiquer que l’ordinateur a gagné);
  • la seconde qui servira juste pour les différentes boucles (on y reviendra);
  • la troisième qui contiendra la réponse que l’ordinateur voudra proposer.

Pour que la recherche de la réponse soit plus courte, on décide que l’ordinateur commencera par proposer 5, afin qu’il prenne autant de temps à remonter jusqu’à 10 qu’à descendre jusqu’à 0. Le caractère 5 correspondant à la valeur 53 en ASCII, nous allons utiliser une boucle comme précédemment pour faire l’opération 8*7 (c’est donc par exemple ici que vous aurez besoin de la seconde variable) puis nous retirerons 3 afin d’arriver à 53. Le code ressemble donc pour l’instant à ceci:

>++++++++[>+++++++<−]>−−−

À ce stade, nos mémoires ressemblent donc à ça:  [0, 0, 54].

Ensuite nous voulons créer une boucle qui va s’activer tant que l’utilisateur ne tape pas 0 (puisqu’une boucle s’arrête quand la valeur de la case est vide), pour cela nous devons demander à l’utilisateur d’entrer une valeur avec « , » puis pour savoir de quel chiffre il s’agit, il faut convertir la valeur ASCII en valeur réelle. Or le 0 en ASCII vaut 48, nous devons donc soustraire 48 à une entrée pour savoir de quel chiffre il s’agit (et là encore vous l’avez deviné: pour atteindre la valeur 48 nous allons passer par une boucle et donc passer par la seconde variable). La boucle va donc ressembler à ceci:

[,>++++++++[<−−−−−−>−]<]

On récupère la valeur, on soustrait 48 et on arrive à la fin de la boucle. Si l’utilisateur a tapé « 0 », la mémoire contiendra 0 et la boucle s’arrêtera, sinon elle recommencera.

Il faut ensuite augmenter ou diminuer la prédiction de l’ordinateur en fonction de l’entrée de l’utilisateur qui si la boucle reprend vaudra soit 1, soit 2. Afin d’éviter d’utiliser des conditions j’ai choisi une méthode simple: en retirant 1 à l’entrée de l’utilisateur on se retrouve avec 0 ou 1. On va donc lancer une boucle qui ne s’effectuera donc que si la variable vaut 1, cette boucle correspondra au comportement que l’on veut effectuer si l’utilisateur a tapé 2, donc si la prédiction doit être augmentée. Et à l’intérieur de cette boucle on ajoute 2 à la prédiction puis on transforme notre 1 en 0 afin de sortir de la boucle, puis à l’extérieur de la boucle on retire 1 et on affiche le résultat avec « . » ! Comme ça si l’utilisateur a tapé 2, la boucle va s’exécuter ajouter 2 puis retirer 1 (donc la variable sera plus grande de 1) et s’il a tapé 1, la boucle ne s’exécutera pas et la variable se verra simplement diminuée de 1. Cette partie de code va alors ressembler à ça, et devra être placée en début de boucle:

−[>>++<<−]>>−.

À ce stade nous avons donc notre initialisation des mémoires, notre boucle et notre condition. Il ne reste plus qu’à tout assembler, mais il faut encore prendre en compte un détail: non seulement la boucle ne va s’exécuter que si la mémoire d’origine ne vaut pas 0, mais en plus notre code part du principe que l’utilisateur a entré une valeur dans la mémoire. Nous allons donc ajouter 1 à notre première variable pour entrer dans la boucle et ajouter 1 à la prédiction puisque notre code va s’exécuter une première fois avant de demander à l’utilisateur d’entrer une valeur. J’ai également affiché le résultat final à la sortie de la boucle. Voici donc le code final de notre premier mini jeu en Brainfuck:

+>++++++++[>+++++++<−]>−−<<[−[>>++<<−]>>−.<<,>++++++++[<−−−−−−>−]<]>>.

 


Le Brainfuck n’est donc pas un langage pertinent dans le monde du travail mais il n’en reste pas moins extrêmement intéressant à étudier que ce soit pour des néophytes de la programmation qui voudraient s’initier à la logique ou pour des développeurs plus expérimentés qui voudraient pousser leur logique, s’entraîner à développer un interpréteur avant de passer à des langages complexes ou même simplement pour s’amuser. Ce qui fut mon cas au moment où j’ai décidé de me pencher dessus, mais ce qui fut surtout le cas de M. Müller au moment de sa création.

 

Ne manquez aucun article: inscrivez-vous à notre Newsletter:

2 thoughts on “Introduction au Brainfuck”

  1. Pingback: Création d'icons 100% en CSS - le Blog de Steloria

  2. Pingback: Introduction au langage de programmation Red - Blog de Steloria

Laisser un commentaire