Brainfuck (ou Brainf*ck, brainf***, voire BF pour les plus constipé-e-s) est un langage de programmation minimaliste créé par Urban Müller vers 1993. Son but était de créer un langage de programmation Turing-complet simple qui puisse être implémenté avec le plus petit compilateur possible. C'est ainsi un tarpit de Turing, c'est-à-dire un langage conçu pour être Turing-complet tout en minimisant le nombre d'instructions distinctes (8 commandes dans ce cas, toutes sans opérande).

Un langage de programmation est dit Turing-complet s'il permet de représenter toutes les fonctions calculables au sens de Turing (donc aussi performant qu'une machine de Turing).

Une machine de Turing est composée d'une tête de lecture/écriture se promenant en avant ou en arrière sur un ruban de longueur infinie découpé en cellules, d'un registre d'état qui enregistre l'état courant, et d'une table d'actions qui définit quoi faire dans un état donné, ou plutôt dans une combinaison état/symbole rencontré. Pour être plus précis, le ruban est de longueur finie à chaque instant, mais de nouvelles cellules sont ajoutées lorsque la tête de lecture/écriture atteint l'une des extrémités, puisqu'il était important pour Turing que cette machine puisse être construite. Elle reste cependant une machine idéale, imaginaire et abstraite, modèle épuré des ordinateurs actuels.

Speaking Code: Coding as Aesthetic and Political Expression Geoff Cox The MIT Press

Software Studies: A Lexicon Matthew Fuller The MIT Press

+	incrémente la valeur d'une cellule
-	décrémente la valeur d'une cellule
>	déplace la tête de lecture/écriture sur la cellule de droite (suivante)
<	déplace la tête de lecture/écriture sur la cellule de gauche (précédente)
[	débute une boucle (de type while)
]	termine une boucle
.	écrit un caractère ASCII sur la sortie standard
,	lit un caractère ASCII depuis l'entrée standard

Contrairement à une machine de Turing, brainfuck n'a ni tête de lecture/écriture, ni ruban, mais un pointeur et un tableau de 30.000 cellules. Ainsi, les instructions < et > déplacent le pointeur dans ce tableau. La métaphore de la machine de Turing n'est donc conservée que pour des raisons de compréhension.

Différents interprètes existent pour ce langage, dont celui de Daniel Lorch écrit en PHP et utilisé ici (voir http://daniel.lorch.cc/projects/brainfuck/).

Je vais donc ici utiliser l'interprète de Daniel Lorch pour faire mes premiers pas (et les vôtres) en Brainfuck (une copie locale est à votre disposition, mais peut-être pas à jour).
Pour utiliser cet outil, le script PHP ressemblera à ceci :

<?php
	include "brainfuck.php";
	echo brainfuck("_programme_en_Brainfuck_");
?>

Passons maintenant à la programmation Brainfuck proprement dite dans une série de courts programmes qui va aller au-delà de vos espérances les plus folles.

Nous allons utiliser un compteur incrémentiel (initialisation et unités), une cellule pour les unités, et une pour le caractère espace. La notation @nombre sert à décrire la cellule numéro nombre du ruban (rappelez-vous de la machine de Turing...), ou la cellule numéro nombre du tableau (si vous préférez vous en tenir aux tableaux et aux pointeurs).

@0 : compteur
@1 : caractère '0' (ASCII 48)
@2 : caractère espace (ASCII 32)

'0' (ASCII 48)
+++++[->++++++++++<]>--
<
' ' (ASCII 32)
+++[->>++++++++++<<]>>++
<<
----------[+>.>.<+<]

• on met 48 (= 5*10-2) dans @1
• on met 32 (= 3*10+2) dans @2
• on affiche le contenu de @1 puis de @2, et on incrémente @1, le tout 10 fois

Nous allons utiliser un compteur incrémentiel (initialisation et unités), une cellule pour la dizaine (fixe), une pour les unités, et une pour le caractère espace.

@0 : compteur
@1 : caractère '1' (ASCII 49)
@2 : caractère '0' (ASCII 48)
@3 : caractère espace (ASCII 32)

'0' (ASCII 48)
+++++[->++++++++++<]>--
<
'1' (ASCII 49)
+++++[->>++++++++++<<]>>-

<<
' ' (ASCII 32)
+++[->>>++++++++++<<<]>>>++
<<<
----------[+>>.<.>>.<<+<]

• on met 48 (= 5*10-2) dans @1
• on met 49 (= 5*10-1) dans @2
• on met 32 (= 3*10+2) dans @3
• on affiche le contenu de @2 (dizaine) puis celui de @1 (unités), et celui de @3 (espace), puis on incrémente le compteur @1, le tout 10 fois

Nous allons utiliser deux compteurs : un global (initialisation, puis boucle principale) et un pour les unités, et trois cellules : une pour les unités, une pour les dizaines et une pour l'espace.

@0: compteur global de mise à jour
@1: compteur des unités
@2: unités, initialisé au caractère '0' (ASCII 48)
@3: dizaines, initialisé au caractère '0' (ASCII 48)
@4: caractère espace (ASCII 32)

initialisation
'0' (ASCII 48)
+++++[->>++++++++++<<]>>--
<<
'0' (ASCII 48)
+++++[->>>++++++++++<<<]>>>--
<<<
' ' (ASCII 32)
+++[->>>>++++++++++<<<<]>>>>++

<<<

boucle principale : met le nombre de boucles à effectuer dans @0
<
++++++++++[->

boucle d'affichage
----------[+>>.<.+>>.<<<]
remet la cellule des unités à la valeur '0'
>
----------
ajoute 1 à la cellule des dizaines
>+

<<<]

• initialisation : on met 48 (= 5*10-2) dans @2 ('0' unité)
• initialisation : on met 48 (= 5*10-2) dans @3 ('0' dizaine)
• initialisation : on met 32 (= 3*10+2) dans @4 (' ' espace)
• boucle principale : on met 10 dans le compteur global @0
  • on affiche le contenu de @3 (dizaine) puis celui de @2 (unités), et celui de @4 (espace), puis on incrémente le compteur des unités @1, le tout 10 fois
  • on réinitialise la cellule des unités à la valeur '0'
  • et on incrémente la valeur de la cellule des dizaines

Nous arrivons maintenant à la fin de ce court tutoriel qui vous aura donné envie, je l'espère, de programmer une machine de Turing avec le langage Brainfuck.

La programmation est matière de goût et d'habitude, mais surtout d'amélioration et de rétro-actions. C'est pourquoi cette partie est une tribune libre ouverte à celles et ceux qui voudraient apporter une correction ou un complément d'information à ce tutoriel.

Daniel Cristofani nous montre comment initialiser dans la même boucle les cellules @1 (caractère '0' ou ASCII 48) et @2 (caractère espace ou ASCII 32) du premier programme (chiffres de 0 à 9), puisque 48=8*6 et 32=8*4. Le résultat se présente ainsi : ++++++++[>++++++>++++<<-]
Par ailleurs, les nombres positifs sont plus portables que les nombres négatifs. La partie concernant l'affichage (----------[+>.>.<+<]) peut se réécrire en : ++++++++++[>.+>.<<-] (la boucle décrémentielle est maintenant incrémentielle).
Et le tout peut être combiné en : ++++++++[>+>++++++>++++<<<-]>++[>.+>.<<-]
De la même façon, le second programme (les nombres de 10 à 19) peut être réécrit en :
++++++++[>+>++++++>++++++>++++<<<<-]>>+<++[>.>.+>.<<<-]
et le troisième programme (les nombres de 0 à 99) en :
>++++++++[<+>>++++++>++++++>++++<<<-]
<++[>++++++++++[>.>.+>.<<<-]>+>----------<<<-]