est un langage de programmation exotique, inventé par Urban Müller en 1993. Il tire son nom de l’union de deux mots anglais, (« cerveau ») et (« niquer »), et joue sur les mots, puisque ce langage est volontairement simpliste, et parce que l'expression Brain Fuck évoque, en argot, ce qui met le cerveau dans un état de confusion par sa complexité apparente. 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 Preuve de la Turing-complétude de brainfuck en anglais, 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 les programmes produits sont inefficaces et 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.
En théorie de la calculabilité, le brainfuck est considéré comme une version en miroir du langage de programmation , où P′′ est défini avec un alphabet de taille . P′′, inventé en 1964 par Corrado Böhm, n'est pas conçu comme un langage ésotérique, mais comme un langage simple servant de base à des théorèmes mathématiques. En raison de cet isomorphisme, le brainfuck hérite de toutes ses propriétés.
Implémentation
Structure du brainfuck Le brainfuck utilise un tableau de 30 000 cases dans lequel il stocke des valeurs. Chacune de ces cases prend une valeur entière codée sur 8 bits, ce qui permet des valeurs entre 0 et 255 ou entre -128 et 127. Il utilise également un pointeur, c'est-à-dire une variable qui prend des valeurs entières positives indiquant l'indice de la case du tableau que l'on modifie actuellement. Par convention, on attribue en informatique l'indice 0 à la première case du tableau.
Au lancement du code brainfuck, le pointeur est initialisé à 0 et toutes les cases du tableau sont nulles.
Dans les nouvelles implémentations du brainfuck, la taille du tableau n'est pas restreinte à 30 000 cases et celles-ci peuvent prendre des valeurs plus élevées. Le pointeur, lui, peut prendre des valeurs négatives, c'est-à-dire que le tableau peut s'étendre à gauche de la case d'indice nul.
Instructions Les huit instructions du langage, chacune codée par un seul 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 sur lequel est positionné 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 où est positionné le 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. (Alternativement, peut être défini par « retourne au correspondant ». La formulation est plus courte, mais moins symétrique et moins efficace en temps. Le choix de l'une ou l'autre de ces deux syntaxes n'influe pas sur le comportement final du programme.)
(Une troisième version équivalente, quoique moins considérée, est : signifie « saute à l'instruction correspondante », et signifie « retourne à l'instruction après le correspondant si l'octet pointé est différent de 0 ».)
Les programmes brainfuck peuvent être traduits en C en utilisant les substitutions suivantes, en considérant que ptr est du type unsigned char* : Brainfuck C }
Entrées / Sorties
Entrées Les différents interpréteurs de brainfuck gèrent les entrées différemment. Prenons pour exemple le programme suivant :,[>,] ',' : prend une première entrée, puis '[>,]': se déplace à droite, demande une nouvelle entrée et continue tant que l'entrée n'est pas nulle.Celui-ci se charge d'inscrire les entrées les unes à la suite des autres dans le tableau jusqu'à ce qu'une des entrées soit 0.
Certains interpréteurs demanderont à l'utilisateur à chaque fois qu'ils rencontrent la commande "," une entrée. Par exemple, l'utilisateur rentrera 12, puis 15, puis 2, puis 36, puis 0, et obtiendra le tableau [12,15,2,36,0,0, etc.]
D'autres ne demanderont qu'une seule entrée à plusieurs chiffres, comme 1215236, et la découperont chiffre par chiffre pour obtenir toutes les entrées requises: 1, puis 2, puis 1, puis 5 ... Dès qu'il n'y a plus de chiffres à mettre en entrée, l'interpréteur les remplace automatiquement par des 0. Ainsi dans notre exemple, on obtiendra le tableau [1,2,1,5,2,3,6,0,0, etc.]. Si l'utilisateur rentre un nombre avec un 0 à l'intérieur, le programme s'arrêtera comme prévu à ce 0 sans copier le reste du nombre. Par exemple, 12150236 donnera [1,2,1,5,0,0, etc.]
En général, comme on vient de le faire, les entrées sont des nombres, mais peuvent être également des caractères ASCII, l'interpréteur se charge de les remplacer par leur code équivalent. Par exemple, si l'on rentre "Hello World" avec le code précédent, on obtient alors : [72,101,108,108,111,32,87,111,114,108,100,0,0,...].
Sorties Comme pour les entrées, les sorties peuvent soit être exprimées en ASCII, soit directement numériquement.
Exemples Hello World! - Exemple #1 Le programme suivant affiche le traditionnel « Hello World! » et une nouvelle ligne à l'écran :
++++++++++ Affecte 10 à la case 0 [ Boucle initiale qui affecte des valeurs utiles au tableau > avance à la case 1 +++++++ affecte 7 à la case 1 > avance à la case 2 ++++++++++ affecte 10 à la case 2 > avance à la case 3 +++ affecte 3 à la case 3 > avance à la case 4 + affecte 1 à la case 4 <<<< retourne à la case 0 - enlève 1 à la case 0 ] jusqu'à ce que la case 0 soit = à 0 la boucle initialise le tableau selon les valeurs suivantes : Case : Valeur 0 : 0 1 : 70 2 : 100 3 : 30 4 : 10
>++ ajoute 2 à la case 1 (70 plus 2 = 72) . imprime le caractère 'H' (72) >+ ajoute 1 à la case 2 (100 plus 1 = 101) . imprime le caractère 'e' (101) +++++++ ajoute 7 à la case 2 (101 plus 7 = 108) . imprime le caractère 'l' (108) . imprime le caractère 'l' (108) +++ ajoute 3 à la case 2 (108 plus 3 = 111) . imprime le caractère 'o' (111) >++ ajoute 2 à la case 3 (30 plus 2 = 32) . imprime le caractère ' '(espace) (32) << revient à la case 1 +++++++++++++++ ajoute 15 à la case 1 (72 plus 15 = 87) . imprime le caractère 'W' (87) > repart à la case 2 . imprime le caractère 'o' (111) +++ ajoute 3 à la case 2 (111 plus 3 = 114) . imprime le caractère 'r' (114) ------ enlève 6 à la case 2 (114 moins 6 = 108) . imprime le caractère 'l' (108) -------- enlève 8 à la case 2 (108 moins 8 = 100) . imprime le caractère 'd' (100) > repart à la case 3 + ajoute 1 à la case 3 (32 plus 1 = 33) . imprime le caractère '!' (33) > va à la case 4 . imprime le caractère '\n'(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 = 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 = 70 (proche de 72, le code ASCII du caractère 'H'), a = 100 (proche de 101 ou 'e'), a = 30 (proche de 32, espace) et a = 10 (nouvelle ligne). La boucle fonctionne en multipliant les valeurs de a, 10, par 7, 10, 3, et 1, qu'elle stocke dans les cellules voisines. Quand la boucle s'achève, a vaut zéro. >++. déplace alors le pointeur à a, 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 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 et l'afficher deux fois.
'o' est la troisième lettre de l'alphabet après 'l', on incrémente donc a 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.
Exemple #2 ++++++++++[>+>+++>+++++++>++++++++++<<<<-]>>>++++++++++++++.>+++++++++++++++++.<<++.>+++++++++++++.>--.<<.>+++.+.--.>----.++++++.+.<++.>----.++.<<.>>+.-------.<<.>>++.<.>+++++.<<.>-.+.<.>---.>---.<-.++++++++.>----.<---.>+++++++.<---.++++++++.
Remise à zéro de l'octet pointé , ciblage de l’octet [ boucle - enlever 1 à la case courante ] jusqu'à ce que la case soit à zéro
L'octet est décrémenté (boucle [ ]) jusqu'à ce que sa valeur ait atteint 0.
Entrée/Sortie d'un caractère , saisit un caractère de la ligne de commande dans la case courante . imprime le caractère correspondant à la valeur de la case courante
Affiche à l'écran un caractère entré au clavier.
Boucle simple [,.] ou ,[.,]
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 Enregistrer une chaîne de caractères ,[.>,]
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.
Utilisation de bloc de mémoire (taille quelconque, mais ne contenant pas de valeur nulle)
En notant P le pointeur, - - - - un bloc de données quelconques non nulles et 0 un octet dont la valeur est nulle, si la mémoire est organisée de la manière suivante :
0P- - - -00- - - -00- - - -00- - - -00- - - ... avec les blocs - - - - numérotés de 1 à n Alors nous pouvons nous déplacer de bloc en bloc de la manière suivante (avec le pointeur initialement sur P ) :
[-[-[>]>+<<[<]>]] Par exemple, si P=3, à chaque exécution de la boucle principale, la mémoire sera organisée de cette façon :
0P- - - -00- - - -00- - - -00- - - -00- - - ... avec P = 3 00- - - -0P- - - -00- - - -00- - - -00- - - ... avec P = 2 00- - - -00- - - -0P- - - -00- - - -00- - - ... avec P = 1 00- - - -00- - - -00- - - -0P- - - -00- - - ... avec P = 0 Arrivée à ce point, la boucle s'arrête, et nous sommes arrivés sur le bloc pointé. Cette technique permet de manipuler des blocs de taille quelconque, à condition qu'ils ne contiennent pas de valeurs nulles.
Utilisation de bloc de mémoire (taille fixe, pouvant contenir des valeurs nulles) En reprenant la technique précédente, mais cette fois avec des blocs de tailles constantes (par exemple 4, on obtient) : 0P- - - -00- - - -00- - - -00- - - -00- - - ... avec les blocs - - - - numérotés de 1 à n [-[->>>>>>+<<<<<<]] Il faut 4 (taille des blocs) + 2 (les séparateurs) décalages Cette technique permet d'avoir des données nulles dans les blocs, mais est plus longue à écrire pour des blocs de grande taille.
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: