Brainfuck - Définition

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
>	ptr++;
<	ptr--;
+	(*ptr)++;
-	(*ptr)--;
.	putchar(*ptr);
,	(*ptr) = getchar();
[	while(*ptr) {
]	}

Commentaire

On peut noter que, dans la version initiale, comme chaque cellule du tableau est un octet, l'instruction « - » est superflue et peut-être remplacée par 255 « + ». De la même manière, les 30 000 cellules formant un tableau circulaire, « < » peut-être remplacé par 29 999 « > ». Cela réduirait le langage à six instructions.

Cependant, la taille du tableau, la taille des cellules et les possibilités de "wrapping" (i.e. que faire > sur la dernière case ramène à la première ou que + sur un octet plein le met à 0) ne font pas partie des spécifications du langage et sont laissées à la liberté des compilateurs. Ainsi, cette réduction à six instructions n'est pas toujours possible. Quand bien même, il peut nuire à la portabilité de jouer sur le wrapping.

La seule contrainte imposée par le concepteur du langage est au moins 30 000 cellules et au moins un octet par cellule. Certaines implémentations proposent deux, quatre ou huit octets par cellule, voire aucune limitation!

Macro-définition Brainfuck

Les macros-définitions ci-dessous définissent des techniques permettant de retrouver des structures ou des instructions utilisées habituellement en algorithmique ou dans les langages de programmation. Elles facilitent la création de programmes Brainfuck. Il existe des implémentations de Brainfuck acceptant la définition de macros.

Les symboles comme a, b ou s représentent chacun un octet différent dans le tableau mémoire. Le symbole t indique un octet utilisé temporairement pour les besoins de la macro. Le symbole s représente un octet utilisé comme source et d un octet utilisé comme destination.

• Déplacement du pointeur

La macro to(a) consiste à déplacer le pointeur dans le tableau mémoire au niveau de l'octet a. Elle s'obtient avec une série de < ou de >.

• Ajout d'une constante

La macro addCst(n) ajoute à l'octet pointé la valeur n. Elle s'obtient avec une série de + ou de - selon le signe de n.

• Mise à zéro d'un octet

zero(m): to(m) [-]

• Déplacer un octet

move(s d): to(s) [- to(d)+ to(s)]

• Déplacer un octet vers deux autres octets

move2(s d1 d2): to(s) [- to(d1)+ to(d2)+ to(s)]

• Copie d'un octet vers un autre

copy(s d t): move2(s d t) move(t s)

• Structure conditionnelle simple

if(a)  : to(a) [

endif(a): zero(a) ]

• Structure conditionnelle avec alternative

ifelse(a t): to(t)+ to(a) [ to(t)-

else(a t)  : zero(a) ] to(t) [

endelse(t) : to(t)- ]

• Structure répétitive

for(s) : to(s) [

next(s): to(s)- ]

• Échange de deux octets

swap(a b t): move(a t) move(b a) move(t b)