Brainfuck - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Introduction

Brainfuck est un langage de programmation minimaliste, inventé par Urban Müller en 1993. Il tire son nom de l’union de deux mots anglais, brain (cerveau) et fuck (foutre), allusion transparente à l'expression « masturbation intellectuelle ». Ce vocabulaire peu flatteur lui a d'ailleurs valu d'être écrit sous d'autres orthographes plus prudes, telles que Brainf*ck, Brainf*** ou encore BF.

Présentation du langage

L'objectif de Müller était de créer un langage de programmation simple, destiné à fonctionner sur une machine de Turing, et dont le compilateur aurait la taille la plus réduite possible. Le langage se satisfait en effet de seulement huit instructions. La version 2 du compilateur originel de Müller, écrit pour l'Amiga, ne pesait lui-même que 240 octets, la version actuelle se contentant de 171 octets. Le brainfuck est pourtant un langage Turing-complet, ce qui signifie que, malgré les apparences, il est théoriquement possible d'écrire n'importe quel programme informatique en brainfuck.

La contrepartie est que, comme son nom ne le suggère peut-être pas pour un non-anglophone, le langage brainfuck produit des programmes difficiles à comprendre. Il suit un modèle de machine simple, consistant en un tableau d'octets initialisés à 0, d'un pointeur sur le tableau (positionné sur le premier octet du tableau) et de deux files d'octets pour les entrées et sorties.

Exemples

Hello World!

Le programme suivant affiche le traditionnel « Hello World! » et une nouvelle ligne à l'écran :

      ++++++++++      [                   Boucle initiale qui affecte des valeurs utiles au tableau         >+++++++>++++++++++>+++>+<<<<-      ]                          à la sortie de la boucle le tableau contient:      >++.                      'H'    = 72  (70  plus 2)      >+.                       'e'    = 101 (100 plus 1)      +++++++.                  'l'    = 108 (101 plus 7)      .                         'l'    = 108      +++.                      'o'    = 111 (108 plus 3)      >++.                      espace = 32  (30  plus 2)      <<+++++++++++++++.        'W'    = 87  (72  plus 15)      >.                        'o'    = 111      +++.                      'r'    = 114 (111 plus  3)      ------.                   'l'    = 108 (114 moins 6)      --------.                 'd'    = 100 (108 moins 8)      >+.                       '!'    = 33  (32  plus  1)      >.                        nouvelle ligne = 10      

Par souci de lisibilité, le code a été divisé en plusieurs lignes et des commentaires ont été ajoutés. Brainfuck considère comme étant des commentaires tous les caractères sauf +-<>[],.. Le code effectivement compilé peut donc se réduire à la ligne suivante :

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

La première ligne initialise a[0] = 10 par de simples incréments successifs à partir de 0. La boucle des lignes 2 à 4 définit de façon effective les valeurs initiales du tableau : a[1] = 70 (proche de 72, le code ASCII du caractère 'H'), a[2] = 100 (proche de 101 ou 'e'), a[3] = 30 (proche de 32, espace) et a[4] = 10 (nouvelle ligne). La boucle fonctionne en multipliant les valeurs de a[0], 10, par 7, 10, 3, et 1, qu'elle stocke dans les cellules voisines. Quand la boucle s'achève, a[0] vaut zéro. >++. déplace alors le pointeur à a[1], qui contient 70, y ajoute 2 (72 étant le code ASCII de la lettre 'H' majuscule), et l'affiche.

La ligne suivante déplace le pointeur vers a[2] et l'incrémente de 1, le résultat, 101, correspondant à 'e', qui est alors affiché.

'l' étant la septième lettre de l'alphabet après 'e', pour obtenir 'll' il faut ajouter 7 (+++++++) à a[2] et l'afficher deux fois.

'o' est la troisième lettre de l'alphabet après 'l', on incrémente donc a[2] trois fois avant d'afficher le résultat.

Le reste du programme fonctionne selon le même principe. Pour les espaces et les lettres en majuscule, ce sont d'autres cellules du tableau qui sont sélectionnées et incrémentées.

Remise à zéro de l'octet pointé

[-]

L'octet est décrémenté (boucle []) jusqu'à ce que sa valeur ait atteint 0.

Entrée/Sortie d'un caractère

,.

Affiche à l'écran un caractère entré au clavier.

Boucle simple

,[.,]

Boucle affichant les caractères entrés au clavier. La fin de la saisie est ici signalée par un 0 (les implémentations peuvent différer sur ce point).

Manipulation de pointeur

>,[.>,]

Une version améliorée de la boucle précédente, dans laquelle les caractères saisis par l'utilisateur sont stockés dans un tableau en vue d'une utilisation future, en déplaçant le pointeur à chaque fois.

Copie d'un octet

On peut distinguer deux manières de copier le contenu d'un octet dans un autre: en effaçant les données de l'octet initial ou en les conservant. Le premier cas est plus simple, le second requérant une variable intermédiaire.

Pour la copie destructive d'un octet dans l'octet suivant, en supposant que le pointeur est sur l'octet à copier:

>[-]< effacer l'octet suivant et revenir sur l'octet initial (facultatif si on sait que l'octet cible est nul)

[->+<] tant qu'il n'est pas nul, lui enlever 1 et ajouter un à l'octet suivant

Pour une copie conservative d'un octet (pointé au départ) dans l'octet suivant, nous allons utiliser l'octet encore après comme variable temporaire. Encore une fois, la première ligne est facultative si on sait que les deux octets suivant l'octet à copier sont nuls.

>[-]>[-]<< on efface les deux octets suivants l'octet à copier puis on revient sur lui

[>+>+<<-] on incrémente les deux octets suivants et on décrémente l'octet à copier jusqu'à ce qu'il soit vide. On a donc réalisé deux copies en le détruisant

>>[-<<+>>] on se place sur la deuxième copie et on la copie destructivement sur le premier octet.

Addition

Ce code ajoute l'octet courant (en le détruisant, il est donc remis à 0) à 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. La touche entrée arrête la saisie (code 10 en Brainfuck dans la plupart des compilateurs).

Au début, on récupère le premier caractère (, ) et on lui soustrait immédiatement 10 (10 fois -). Si l'utilisateur a appuyé sur entrée, on a 0 dans l'octet pointé et l'instruction de boucle ([) saute à la fin du programme. Si le caractère entré n'est pas 10, on considère que c'est une lettre minuscule et on entre dans la boucle, où on va lui soustraire le nombre 22 (22 fois -), ce qui va faire 32 en tout, 32 étant la différence numérique entre la lettre minuscule et la même lettre en majuscule en code ASCII.

Le caractère est affiché, puis un nouveau caractère est récupéré, et à nouveau on lui soustrait 10. Le programme revient alors au début de la boucle : si la touche qu'a validé l'utilisateur est entrée (10), la boucle s'arrête, sinon elle se poursuit.

If

Voici un moyen simple d'écrire un bloc « if » en Brainfuck :

      >[code<]<[>]      

Ce bloc d'instruction prend une mémoire de la forme :

      1 0 n      

Avec le curseur sur le « 0 ». Il exécute le code « code » si et seulement si n est non nul, avec le curseur sur le « 0 » à l'état final comme initial.

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 × 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. La boucle est alors exécutée 6 fois, jusqu'à ce que [1] soit égal à 0.

Ensuite, on récupère le signe + qu'on met dans [1], puis le second chiffre qui écrase le signe +.

La boucle suivante [<+>-] ajoute effectivement le nombre de la seconde cellule dans la première cellule et remet [1] à zéro. À chaque boucle, il ajoute 1 dans [0] et retire 1 de [1] ; ainsi [1] finit 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). Le pointeur est ensuite déplacé sur [1], qui contient la touche entrée, que l'on affiche. L'exécution est terminée.

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 (note : il n'y a qu'une seule boucle de 8 itérations pour soustraire 6 aux deux nombres à chaque itération !).

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 la plus simple 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] contient encore le deuxième nombre, et [2] contient le produit des 2 nombres (pour garder la valeur, il suffit de l'ajouter dans [4] à chaque itération de la boucle principale, puis 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 en ASCII et l'entrée qui vient juste d'être stockée.

Minimum

Cette section présente un code permettant de calculer le minimum de deux entiers, chose plus ardue que l'on pourrait penser.

Il prend en argument une bande de la forme

      n 1 0 m 0 0 0      

Avec le curseur sur le n, et renvoie une bande de la forme

      n' 1 0 m' M 0 0      

Avec le curseur sur le M et M = min(n,m), n' = nM et m' = mM

      [->>              On commence une boucle sur n        >[              On teste si m est nulle ou non          >>>>>+<<<<<   On remplace le 0 de la case juste après M par un 1          ->+<          On ajoute 1 au minimum tout en enlevant 1 à m        <]<[>]          Fin du If        >>>>        >[              Cette ligne fait un If après le M: ceci revient en fait à un Else du bloc If          -<<->>>>>>>   On efface le 1 en trop à la fin et on s'éloigne de la bande (ce qui permet de quitter le programme en revenant sur la place du M)        ]<[>]        <<<<<<          On revient sur le n (ou sur le 0 apès le M sinon)      ]      >[>>>>->]<<       Cette ligne permet de se placer sur la case du M que ce soit m ou n le plus petit      

On peut ensuite ajouter du code de mise en forme.

Ainsi le code suivant prend en argument une bande du type

      n m 0 0 ...      

avec un curseur sur le n et renvoie

      0 0 0 0 M 0 ...      

avec le curseur sur le M.

Voici le code : (les lignes 2 et 4 sont des lignes de mise en forme, 1 et 5 des entrées sorties)

      ,>,      [->>+<<]+<      [->>>[>>>>>+<<<<<->+<<]<[>]>>>>>[-<<->>>>>>>]<[>]<<<<<<]>[>>>>->]<<      <<<<[-]>[-]>>[-]>      .      
Page générée en 0.077 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales | Partenaire: HD-Numérique
Version anglaise | Version allemande | Version espagnole | Version portugaise