grim7reaper

Un artisan du code

Interpréteurs Brainfuck

Cet article provient de mon ancien site Internet.

Le Brainfuck c’est quoi ?

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

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 :

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