# Programmation Brainfuck/Version imprimable

* Si vous imprimez cette page, choisissez « Aperçu avant impression » dans votre navigateur, ou cliquez sur le lien Version imprimable dans la boîte à outils, vous verrez cette page sans ce message, ni éléments de navigation sur la gauche ou en haut.
* Cliquez sur Rafraîchir cette page pour obtenir la dernière version du wikilivre.
* Pour plus d'informations sur les version imprimables, y compris la manière d'obtenir une version PDF, vous pouvez lire l'article Versions imprimables.
Une version à jour et éditable de ce livre est disponible sur Wikilivres, une bibliothèque de livres pédagogiques, à l'URL : https://fr.wikibooks.org/wiki/Programmation_Brainfuck

# Introduction

Brainfuck est un langage de programmation minimaliste, inventé par Urban Müller en 1993. Le nom est anglais, il vient de la contraction de brain, cerveau, et fuck, niquer. Il a d'ailleurs d'autres noms comme Brainf*ck, Brainf*** ou encore BF. Auraient-ils honte ?
L'objectif de Müller était de créer un langage de programmation simple pour une machine de Turing qu'il pourrait implémenter avec le compilateur le plus petit possible. Le langage consiste en 8 instructions. La version 2 de son compilateur original, écrit pour l'Amiga, faisait 240 octets en taille.
Comme son nom ne le suggère pas pour un anglophobe, les programmes Brainfuck sont difficiles à comprendre, peut-être même dangereux pour la santé mentale des programmeurs. Cependant, une machine de Turing et donc Brainfuck, peut accomplir n'importe quelle tâche. En ne tenant pas compte de la difficulté apparente à programmer certaines tâches en Brainfuck, c'est certainement possible de le faire.
Le langage est basé sur un modèle de machine simple consistant en un tableau d'octets initialisés à 0, d'un pointeur sur le tableau (pointant sur le premier octet du tableau) et de 2 files d'octets pour les entrées et les sorties.

# Les 8 instructions du langage

Les 8 instructions du langage, chacune codée par un caractère, sont les suivantes :
| Caract. | Signification |
| > | incrémente (augmente de 1) le pointeur. |
| < | décrémente (diminue de 1) le pointeur. |
| + | incrémente l'octet du tableau pointé par le pointeur (l'octet pointé). |
| - | décrémente l'octet pointé. |
| . | sortie de l'octet pointé (valeur ASCII). |
| , | entrée d'un octet dans le tableau à l'endroit du pointeur (valeur ASCII). |
| [ | saute à l'instruction après le ] correspondant si l'octet pointé est à 0. |
| ] | retourne à l'instruction après le [ si l'octet pointé est différent de 0. |
Remarques :
* Alternativement, ] peut être défini par "retourne au [ correspondant". C'est plus court, mais moins symétrique et moins efficace en temps. Les deux versions produisent des programmes avec le même comportement.
* Une troisième version équivalente, quoique moins considérée, est que [ signifie "saute après l'instruction ] correspondante", et ] signifie "retourne à l'instruction après le [ correspondant si l'octet pointé est différent de 0".

## Commentaires

Tout autre caractère que les 8 correspondant aux instructions est ignoré et considéré comme un commentaire, ce qui inclut les lettres et les chiffres.

# Compilateurs et interpréteurs
## Compilation en C

Les programmes Brainfuck peuvent être traduits en C en utilisant les substitutions suivantes, en considérant que ptr est du type char*:
| Brainfuck | C |
| > | ++ptr; |
| < | --ptr; |
| + | ++*ptr; |
| - | --*ptr; |
| . | putchar(*ptr); |
| , | *ptr = getchar; |
| [ | while (*ptr) { |
Le programme en C ci-dessous génère un code source en C à partir d'un programme source en Brainfuck. Cependant, le programme généré a une limite de taille mémoire, et le débordement de pointeur n'est pas vérifié.

## Interpréteur en Javascript

Le code source ci-dessous est un interpréteur du langage Brainfuck. Il effectue une précompilation facilitant l'interprétation du code, en particulier pour les sauts d'instruction pour éviter de rechercher le caractère crochet correspondant. Il a la particularité d'autoriser tous les mouvements de pointeur de données, en allouant et décalant le buffer de données quand nécessaire. La seule limite étant la capacité mémoire du système.
L'exemple ci-dessous montre comment utiliser la classe :
L'interpréteur permet de spécifier les données à lire, soit au constructeur, soit au fur et à mesure par exécution pas à pas :

## Optimisations

Certaines optimisations sont possibles :
* Regrouper plusieurs instructions d'incrémentation ou décrémentation + - en une instruction de synthèse ajoutant directement la valeur voulue,
* Même principe pour les instructions de déplacement du pointeur de données < >,
* Supprimer certaines séquences d'instructions qui s'annulent :
* Supprimer les séquences entre crochets (boucle) quand il est certain que l'octet pointé vaut zéro (aucune itération) :
** Une boucle en début de programme, car l'octet pointé vaut initialement zéro ;
** Une boucle suivant immédiatement une autre paire de crochets, car à la sortie de la première boucle, l'octet pointé vaut zéro ;
    [ __A__ ][ __B__ ] → [ __A__ ]
** Une boucle incluse dans une autre paire de crochets sans opérations entre les crochets des deux boucles, car après que toutes les itérations ont été effectuées par la boucle interne, l'octet pointé vaut zéro ;
    [[ __A__ ]] → [ __A__ ]
* Pré-calculer la position du crochet correspondant de chaque paire de la boucle (comme dans l'interpréteur en Javascript de la section précédente),
* Pour un interpréteur : retirer tous les caractères ignorés (commentaire),
* Optimiser les séquences de déplacement et incrémentation/décrémentation en calculant les opérations effectuées sur chaque case au cours du déplacement.
    Exemple : <+<+<+>-<- simplifié : <+<<

# Comment effectuer les opérations courantes
### Hello World!

Un programme qui affiche "Hello World!" sur l'écran est :
Brainfuck est intéressant dans ce cas, un programme "Hello World!" n'est pas facile à écrire ! Et à lire !
Avec un commentaire :
Ou avec des commentaires expliquant le code, en anglais :

### Remise à zéro de l'octet pointé

Tant que l'octet est différent de 0, on le décrémente. On arrête donc la boucle () quand il est à 0.

### Entrée/Sortie d'un caractère

Prend un caractère du clavier pour l'afficher à l'écran.

### Boucle simple

Une boucle qui prend une entrée du clavier et l'affiche à l'écran. Notez qu'on s'attend à avoir un 0 pour marquer la fin de l'entrée (les implémentations peuvent être différentes à ce niveau là).

### Manipulation de pointeur

Une version améliorée de la boucle précédente dans laquelle on stocke les caractères entrés dans le tableau pour une future utilisation, en déplaçant le pointeur à chaque fois.

### Addition

Ce code ajoute l'octet courant (en le détruisant, il sera à 0 à la fin) à l'octet suivant.
Soit Tableau[0] = 2 et Tableau[1] = 8, "[" débute la boucle, "-" et Tableau[0] = 1, ">" on pointe sur l'octet 1, "+" et Tableau[1] = 9, "]" on recommence. À la fin, on aura bien Tableau[0] = 0 ce qui arrête la boucle, et Tableau[1] = 10.

### Instructions conditionnelles

Ce programme prend un caractère minuscule en entrée et le met en majuscule. Pour arrêter, on tape la touche entrée (code 10 en Brainfuck dans la plupart des compilos).
Au début, on récupère le premier caractère (,) et on lui soustrait immédiatement 10 (10 fois -). Si l'utilisateur a tapé entrée, on a 0 dans l'octet pointé et l'instruction de boucle ( sautera à la fin du programme. Si le caractère entré n'est pas 10, on assume qu'il est en minuscule et on entre dans la boucle, où on va lui soustraire le nombre 22 (22 fois -), ce qui va faire 32 en tout, et 32 est la différence en ASCII entre la lettre minuscule et la même lettre en majuscule.
On va donc l'afficher, puis on en récupère une nouvelle, et à nouveau on lui soustrait 10. Et on repart au début de la boucle. Si le caractère entrée est un Entrée (10), la boucle s'arrêtera comme on l'a déjà vu, sinon on continue.

### Addition

Ce programme additionne 2 nombres à un seul chiffre et affiche le résultat si celui-ci n'a aussi qu'un seul chiffre :
4+3
7
(Maintenant les choses vont être un peu plus compliquées. Nous allons nous référer aux octets du tableau ainsi : [0], [1], [2], etc.)
Le premier nombre est entré dans [0], et on lui soustrait 48 pour avoir sa valeur décimale (les codes ASCII pour les chiffres 0-9 sont 48-57). Cela est fait en mettant 6 dans [1] et en utilisant une boucle pour soustraire 8 de [0] autant de fois que dans [1], soit 6 x 8 = 48. C'est une méthode plus commode pour ajouter ou soustraire des grands nombres que de mettre 48 fois "-" dans le programme. Le code qui fait cela est :
>++++++ pour mettre 6 dans [1], puis on attaque la boucle, "<" pour revenir sur [0], on soustrait 8, ">" on repasse sur [1], qu'on décrémente et on retourne dans la boucle. On va bien l'exécuter 6 fois, jusqu'à ce que [1] soit à 0.
Ensuite, on récupère le signe plus qu'on met dans [1] ; puis le second chiffre qui va écraser le signe plus.
La boucle suivante [<+>-] fait le vrai boulot, ajoutant le second nombre dans le premier et remettant à zéro [1]. À chaque boucle, il ajoute 1 dans [0] et retire 1 de [1] ainsi [1] va finir par être à 0 tout ce qui a été ajouté à [0] a été retiré de [1]. Ensuite la touche entrée est mise dans [1]. (Note : il n'y a eu aucun contrôle des entrées.)
Puis le pointeur est remis sur [0], qui est affiché ([0] est maintenant a + (b + 48), puisqu'on n'a pas corrigé b ; ce qui est identique à (a + b) + 48, qui est ce que l'on veut). Maintenant, le pointeur est ramené sur [1], qui contient la touche entrée ; que l'on affiche, et le boulot est fait.

### Multiplication

Comme le précédent, mais effectue une multiplication, pas une addition.
Le premier nombre est entré dans [0], l'astérisque et le deuxième nombre dans [1] et les 2 nombres sont corrigés en leur soustrayant 48 (notez qu'il n'y a qu'une seule boucle de 8 itérations pour soustraire 6 à chaque itération aux 2 nombres !).
Ensuite on entre dans la boucle de multiplication principale. L'idée de base est qu'à chaque boucle on soustrait 1 de [0] et on ajoute [1] dans le total cumulé gardé en [2] (3 * 2 = 2 + 2 + 2). En particulier : la première boucle cumule [1] dans [2] et [3], tout en remettant [1] à 0 (C'est la manière basique de dupliquer un nombre). La deuxième boucle remet [3] dans [1], en remettant à 0 [3]. Puis on décrémente [0] et on est à la fin de la boucle principale. À la sortie de cette boucle, [0] contient 0, [1] a encore le 2e nombre, et [2] a le produit des 2 nombres. (Si on veut garder le premier nombre, on peut l'ajouter dans [4] à chaque itération de la boucle principale, puis à la fin de déplacer la valeur de [4] dans [0].)
Exemple : 3 * 2
| [0] | [1] | [2] | [3] |
| 3 | 2 | 0 | 0 |
| 1re boucle : >[>+>+<<-] ||||
| 3 | 1 | 1 | 1 |
| 3 | 0 | 2 | 2 |
| 2e boucle : >>[<<+>>-] ||||
| 3 | 1 | 2 | 1 |
| 3 | 2 | 2 | 0 |
| Fin boucle princ : <<<-] ||||
| 2 | 2 | 2 | 0 |
| 1re boucle : >[>+>+<<-] ||||
| 2 | 1 | 3 | 1 |
| 2 | 0 | 4 | 2 |
| 2e boucle : >>[<<+>>-] ||||
| 2 | 1 | 4 | 1 |
| 2 | 2 | 4 | 0 |
| Fin boucle princ : <<<-] ||||
| 1 | 2 | 4 | 0 |
| 1re boucle : >[>+>+<<-] ||||
| 1 | 1 | 5 | 1 |
| 1 | 0 | 6 | 2 |
| 2e boucle : >>[<<+>>-] ||||
| 1 | 1 | 6 | 1 |
| 1 | 2 | 6 | 0 |
| Fin boucle princ : <<<-] ||||
| 0 | 2 | 6 | 0 |
Ensuite, il ne reste plus qu'à ajouter 48 au produit, récupérer la touche entrée dans [3], et afficher le produit ASCII et l'entrée qu'on vient juste de stocker.

# Variantes

Le langage Brainfuck a inspiré plusieurs variantes du langage en le modifiant de différentes façons :
* Codage différent pour les 8 instructions du langage,
* Extension du langage par ajout d'instructions,

## Ook

Le langage Ook est une variante de brainfuck, Turing-complet, conçu pour être parfaitement lisible par un orang-outan, faisant référence au personnage du bibliothécaire de l'univers du Disque-monde de Terry Pratchett. Les instructions sont celles du langage Brainfuck codées par deux onomatopées "Ook" suivies chacune par une ponctuation parmi les 3 possibles : point, point d’interrogation, point d'exclamation.
| Ook | Brainfuck | Signification |
| Ook. Ook? | > | incrémente (augmente de 1) le pointeur. |
| Ook? Ook. | < | décrémente (diminue de 1) le pointeur. |
| Ook. Ook. | + | incrémente l'octet du tableau sur lequel est positionné le pointeur (l'octet pointé). |
| Ook! Ook! | - | décrémente l'octet pointé. |
| Ook! Ook. | . | sortie de l'octet pointé (valeur ASCII). |
| Ook. Ook! | , | entrée d'un octet dans le tableau à l'endroit où est positionné le pointeur (valeur ASCII). |
| Ook! Ook? | [ | saute à l'instruction après le Ook? Ook! correspondant si l'octet pointé est à 0. |
| Ook? Ook! | ] | retourne à l'instruction après le Ook! Ook? si l'octet pointé est différent de 0. |
| Ook? Ook? | | fin du programme. |
Il y a neuf possibilités : les 8 instructions, et l'instruction supplémentaire indiquant la fin du programme.
L'exemple du Hello World codé en Ook :

## f*ckf*ck

Le langage f*ckf*ck modifie le codage des instructions en les remplaçant par des mots de 4 lettres censurés, et permettant d'insérer des commentaires utilisant la syntaxe du langage C. Les 2ème et 3ème lettres des mots peuvent être remplacées par n'importe quel caractères ASCII.
| f*ckf*ck | Brainfuck | Signification |
| f**k | > | incrémente (augmente de 1) le pointeur. |
| s**g | < | décrémente (diminue de 1) le pointeur. |
| b**b | + | incrémente l'octet du tableau sur lequel est positionné le pointeur (l'octet pointé). |
| t**s | - | décrémente l'octet pointé. |
| c**k | . | sortie de l'octet pointé (valeur ASCII). |
| k**b | , | entrée d'un octet dans le tableau à l'endroit où est positionné le pointeur (valeur ASCII). |
| a**e | [ | saute à l'instruction après le b**t correspondant si l'octet pointé est à 0. |
| b**t | ] | retourne à l'instruction après le a**e si l'octet pointé est différent de 0. |
Signification particulière :
| f*ckf*ck | Signification |
| ! | Répéter la commande précédente. |
| /* | Début de commentaire. |
| */ | Fin de commentaire. |

## Spoon

Le langage spoon est équivalent au langage brainfuck mais avec des mots constitués de 0 et 1, utilisant un codage de Huffman.
| Spoon | Brainfuck | Signification |
| 010 | > | incrémente (augmente de 1) le pointeur. |
| 011 | < | décrémente (diminue de 1) le pointeur. |
| 1 | + | incrémente l'octet du tableau sur lequel est positionné le pointeur (l'octet pointé). |
| 000 | - | décrémente l'octet pointé. |
| 0010110 | , | entrée d'un octet dans le tableau à l'endroit où est positionné le pointeur (valeur ASCII). |
| 001010 | . | sortie de l'octet pointé (valeur ASCII). |
| 00100 | [ | saute à l'instruction après le 0011 correspondant si l'octet pointé est à 0. |
| 0011 | ] | retourne à l'instruction après le 00100 si l'octet pointé est différent de 0. |
Il possède deux instructions supplémentaires :
| Spoon | Signification |
| 00101110 | sortie de tout le tableau mémoire. |
| 00101111 | fin immédiate du programme. |
Hello world en spoon :
Les espaces peuvent être supprimés. On obtient alors un fichier binaire (exécutable) décodable sans ambiguïté :
Hello world en spoon sans espace :

## SegFaultProg

Le langage Segfaultprog est une variante du brainfuck, enrichie, extensible, destinée à être exécutée en machine virtuelle, sur de petites architectures (AVR, PIC, MIPS...). Son développement a débuté en mai 2010. Ce langage propose une simplification de la syntaxe du brainfuck (par exemple, avec l'adressage direct, et en évitant les répétitions), et rétro-compatibilité avec celui-ci.
Les commandes peuvent être suivie d'un argument sous la forme d'un octet (un caractère), représenté dans le tableau ci-dessous sous cette forme : argument.
| Commande | Description |
| > nb | Incrémente le pointeur de nb cases. |
| < nb | Décrémente le pointeur de nb cases. |
| * pos | Place le pointeur à la position pos. |
| + nb | Incrémente l'octet pointé de nb unités. |
| - nb | Décrémente l'octet pointé de nb unités. |
| [ | Début de boucle, saute après le crochet fermant correspondant si l'octet pointé vaut zéro. |
| ] | Fin de boucle, retourne après le crochet ouvrant correspondant si l'octet pointé ne vaut pas zéro. |
| . | Affiche la valeur de l'octet pointé. |
| , | Demande la saisie de la valeur de l'octet pointé. |
Les quatre dernières instructions du tableau ci-dessus correspondent exactement à celles du brainfuck. Il y a deux versions de la variante qui diffèrent pour la spécification des arguments :

### SegFaultProg V1

    Chaque argument est donné sous la forme d'un caractère.

### SegFaultProg V2

    Chaque argument est optionnel (1 par défaut) et spécifié sous l'une des deux formes suivantes :
   * Sous la forme d'un caractère, précédé de la lettre c (Caractère) ;
   * Sous la forme d'un nombre en décimal (ex : 7) ou en hexadécimal (ex : 0x2f) entre deux caractères dollar.
Hello world en SegFaultProg V1 :
Hello World en SegFaultProg V2 :

## Whitespace

Dans le langage Whitespace, les instructions sont plus nombreuses que dans le langage Brainfuck. Elles sont codés par des espaces, tabulations et retour à la ligne. Le code est donc invisible dans un texte.

## Pi

Pi est un langage de programmation ésotérique basé sur des erreurs de chiffre du nombre pi. Les 8 instructions du brainfuck sont codées par les chiffres de 0 à 8, en sautant le chiffre de pi correspondant à la position de l'instruction.
Si le chiffre est 8 ou 9 :
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Si le chiffre est 4 :
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Si le chiffre est correct, il est ignoré.
Exemple : Hello world

## Références

* ↑ https://web.archive.org/web/20050318095341/http://www.chilliwilli.co.uk/ff/
* ↑ http://compsoc.dur.ac.uk/whitespace/
* ↑ Pi

# Conclusion

À part pour des raisons pédagogiques, ce langage n'est pas utilisable, car concurrencé par de nombreux langages plus faciles (C, BASIC), ou ayant d'autres qualités (Assembleur...).
Il montre cependant qu'une machine peut faire des opérations complexes avec peu d'instructions de base, comme les processeurs RISC (Reduced Instruction Set Computing en anglais) dont le nombre réduit d'instructions facilite la conception des circuits de décodage permettant de réduire le coût. Cependant, comme le montre ce livre, coder à partir de peu d'instructions élémentaires engendre plus de code, augmentant la quantité de mémoire nécessaire pour le stockage des programmes. Cette quantité accrue de mémoire signifie également plus d'accès mémoire pour lire les instructions, donc des performances moindres.