grim7reaper

A Code Craftsman

Interpréteurs Brainfuck

Cet article provient de mon ancien site Internet. Il a été rédigé le 30 décembre 2010.

Le Brainfuck c’est quoi ?

Le Brainfuck est un langage de programmation quasiment imbitable qui se résume à huit instructions.

  • > : déplace le pointeur d’une case mémoire vers la droite ;
  • < : déplace le pointeur d’une case mémoire vers la gauche ;
  • + : incrémente la valeur stockée dans la case mémoire actuellement pointée ;
  • - : décrémente la valeur stockée dans la case mémoire actuellement pointée ;
  • . : affiche le caractère ASCII correspondant à la valeur de la case mémoire actuellement pointée ;
  • , : stocke la valeur ASCII du caractère lu dans la case mémoire actuellement pointée ;
  • [ : saute à l’instruction suivant le ] correspondant si la valeur de la case mémoire actuellement pointée est égale à zéro ;
  • ] : saute à l’instruction suivant le [ correspondant si la valeur de la case mémoire actuellement pointée est différente de zéro.

Malgré ce jeu d’instructions limité, il est Turing-complet. Il est donc possible, théoriquement, de coder en Brainfuck tout ce que l’on peut coder avec d’autres langages plus « traditionnels ».

C’est un langage qui a beaucoup de petits camarades tous plus illisible les uns que les autres. Si ça vous amuse, je vous conseille de faire un tour sur Esolang

Et alors ?

La première question qui peut venir à l’esprit c’est « Pourquoi se faire chier à coder un interpréteur Brainfuck ? »

D’abord, parce que cela occupe. Ensuite, ça permet de bosser par la pratique un langage de programmation. Enfin, ça montre un peu (je dis bien un peu) comment fonctionne un interpréteur (certes très basique). Et puis, si on devait se contenter des choses utiles, on ne ferait pas grand-chose…

En fait, tout est parti de cet innocent post sur le TdCT (Topic des Couche-Tard). Par la suite, tshirtman s’est lancé dans une traduction en Python 2. Enfin, le phénomène a migré dans le TdCCT (Topic des Codeurs Couche-Tard) avec \\Ouranos// et son implémentation en Ruby. Finalement, tout le monde y est allé de sa petite implémentation.

Au final, on a eu :

  • Une version Python 2 (pas tout à fait fonctionnelle) par tshirtman ;
  • Une version C par Pylade ;
  • Une version Ruby 1.8 et 1.9 par \\Ouranos// (malgré mon ignorance totale de Ruby, j’ai contribué à son debug, surtout la version 1.9) ;
  • Une version Java par helly ;
  • Une version Perl 5 par moi ;
  • Une version C++ par moi.

Comment ça fonctionne ?

Étant donné qu’il n’existe pas de norme Brainfuck, on est assez libre au niveau de l’implémentation. La seule chose requise est une mémoire d’au moins 30 000 cases (une case faisant au moins un octet) initialisées à zéro.
Personnellement je suis parti sur cette base, mais certains ont implémentés un interpréteur avec mémoire « infinie » (Pylade en l’occurence) ou avec une mémoire circulaire.

J’ai utilisé une implémentation relativement naïve. Je commence par charger le code en mémoire. Ensuite, j’effectue une première passe pour construire une table de sauts. Enfin, je fais une seconde passe où je lis et j’exécute le code instruction par instruction.
La table de sauts est construite à l’arrache, il faut bien le dire, car j’utilise deux tables de hachage (alors que l’on pourrait s’en sortir avec une seule, mais ça demande un peu plus de lignes de codes) ce qui gaspille de la mémoire.

L’implémentation en Perl a des performances plutôt moyennes, mais bon je l’ai vraiment faite pour le fun. Le fait de tenir en 42 lignes était, ici, plus important que la performance.

En revanche, la version C++ met l’accent sur l’efficacité (enfin pas trop non plus, l’objectif principal étant d’avoir un code court) au niveau temps de calcul (je n’ai pas vraiment optimisé l’occupation mémoire, je sais que l’on peut faire mieux). Si j’ai codé cette version C++, c’est uniquement pour avoir un interpréteur plus rapide que celui de Pylade.

Édit du 13/07/2011 : Pylade a publié une nouvelle version de son interpréteur Brainfuck qui est maintenant plus rapide que ma version C++.

Édit du 06/01/2012 : J’ai développé une version C plus performante que celle de Pylade. Plus d’info ici

Téléchargements

Ayant codé ça plus pour le fun qu’autre chose, le code est loin d’être un modèle de présentation et d’optimisation (au contraire). Le but premier que je m’étais fixé étant le nombre de lignes (42 pour le Perl et 100 pour le C++). En revanche, la version C apporte un début d’intelligence en essayant d’optimiser (très basiquement) le code avant de l’interpréter.

Liens externes

  • Un article sur le Brainfuck ;
  • Des codes sources en Brainfuck. Utile pour pouvoir tester les interpréteurs (ou faire des benchmarks).
  • Une série d’articles sur l’implémentation et l’optimisation d’un interpréteur Brainfuck (implémentation en Haskell). Le cheminement de l’implémentation naïve jusqu’à la version finale est intéressant (attention, le premier article est tout en bas).
  • Un topic où vous pourrez voir diverses implémentations d’interpréteurs (mais aussi de compilateurs) Brainfuck réalisés en divers langages.