Le Brainfuck

Qu’est-ce que le Brainfuck ?

 

Le Brainfuck est un langage de programmation, inventé par Urban Müller en 1993.

Son nom est l’association des mots anglais Brain (« cerveau ») et Fuck (« niquer »), vous allez vraiment avoir le  cerveau qui fume si vous vous y essayez !

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.

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.

La contrepartie est que, comme son nom l’indique, le Brainfuck produit des programmes difficiles à écrire et à comprendre !

Au début du programme, un tableau de 30 000 cellules est créé, toutes ces cellules sont des variables d'un octet initialisés à 0. Le programmeur dispose d'un pointeur, qui se déplace sur les différentes cellules et de huit instructions.

Tous les autres caractères sont ignorés et considérés comme des commentaires.

Avec ces huit instructions, le Brainfuck possède cependant la faculté d'être Turing-complet, ce qui signifie que vous pouvez en théorie créer n'importe quel programme avec ce langage.

 

Son fonctionnement

 

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 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.

Le Brainfuck est un langage très intéressant pour comprendre le fonctionnement de la mémoire et des pointeurs !

 

 

 

Le seul format de données que l'on va pouvoir stocker et manipuler va être des entiers.

Pas de nombres à virgules ou de caractères.

La table ASCII va donc être votre meilleure amie !

 

 

Exemples de codes réalisés en Brainfuck

 

Écrire CampusID en Brainfuck

 

On va créer un programme pour afficher « CampusID » (67 97 109 112 117 115 73 68 en valeurs ASCII)

Pour ne pas à avoir à répéter X fois le symbole + pour incrémenter ou le symbole – pour décrémenter on va créer des cases repères dans le tableau.

On désire stocker les résultats suivants :

10 70 100 110

 (ce tableau servira de repère pour la suite)

 

++++++++++

On initialise la première case à 10 pour pouvoir obtenir des multiples de 10 dans les cases suivantes

 

 [>+++++++

On démarre la boucle sur la seconde case du tableau et on stock la valeur 70

 

>++++++++++

On passe à la deuxième case pour y stocker 100

 

>+++++++++++

On ajoute la valeur 110 à la troisième case

 

<<<-]

On retourne à la première case du tableau et on la décrémente de 1 pour terminer le programme lorsque la case aura la valeur 0 (la boucle se répétera donc 10 fois)

 

0 70 100 110

 

>---.

Pour afficher le « C » nous allons donc décrémenter la deuxième case du tableau de 3 puis ajouter un « » qui permet d’afficher le contenu de la case.

 

0 67 100 110

 

 

 

Pour afficher le « a » il faut maintenant que l'on se déplace sur la case contenant la valeur 100 pour la décrémenter de 3 également puis on affiche le résultat.

>---.

0 67 97 110

 

Puis le « m »

>-.

0 67 97 109

 

Ensuite on va afficher le « p » on reste sur la même case et on incrémente de 3 et on affiche

+++.

0 67 97 112

 

Je vous épargne les explications pour la suite du code

« u »

+++++.

0 67 97 117

 

« s »

--.

0 67 97 115

 

« I »

<<++++++.

0 73 97 115

 

« D »

-----.

0 68 97 115

 

Le code brut :

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

 

 

L’exemple suivant est un peu plus poussé, il permet de réaliser une calculatrice

 

>,                                On laisse un zéro puis on lit un caractère

[>+++++++[-<------>]+<            On lui enlève 42 et on met un 1 après (indicateur de symbole)

[                                             Cas "tout sauf l'étoile"

-                                           On enlève encore 1

[                                           Cas "ni étoile ni plus"

--                                        On enlève encore 2

[                                         Cas "barre oblique ou chiffre"

--                                      On enlève encore 2

[                                       Cas "chiffre uniquement"

>-<                                 On passe l'indicateur de symbole à false

-                                     On enlève encore 1 pour avoir la valeur numérique du chiffre

<[->++++++++++<]>;     On lui ajoute 10 fois le nombre précédent (lecture en base 10)

[-<+>]                             On le déplace sur la cellule précédente

]                                       Fin du cas "chiffre uniquement" et retour au cas "barre oblique ou chiffre"

>                                      On passe sur l'indicateur de symbole

[                                       Cas "barre oblique uniquement"

-                                     0 sera le code de la division et on passe l'indicateur de symbole à false

>>                                  On saute deux cases pour passer au nombre suivant

]                                       Fin du cas "barre oblique uniquement" et retour au cas "barre oblique ou chiffre"

<                                      On revient sur l'octet de lecture (cas d'un chiffre) ou après l'indicateur de symbole (cas de la barre oblique)

]                                         Fin du cas "barre oblique ou chiffre" et retour au cas "ni étoile ni plus"

>                                        On passe sur l'indicateur de symbole (ou deux cases après dans le cas de la barre oblique)

[                                         Cas "moins uniquement"

<++>-                               2 sera le code de la soustraction et on passe l'indicateur de symbole à false

>>                                    On saute deux cases pour passer au nombre suivant

]                                         Fin du cas "moins uniquement" et retour au cas "ni étoile ni plus"

<                                        On revient sur l'octet de lecture (cas d'un chiffre) ou après l'indicateur de symbole (cas de la barre oblique ou du moins)

]                                           Fin du cas "ni étoile ni plus" et retour au cas "tout sauf étoile"

>                                          On passe sur l'indicateur de symbole (ou deux cases après dans le cas de la barre oblique ou du moins)

[                                           Cas "plus uniquement

<+++>-                               3 sera le code de l'addition et on passe l'indicateur de symbole à false

>>                                      On saute deux cases pour passer au nombre suivant

]                                           Fin du cas "plus uniquement" et retour au cas "tout sauf étoile"

<                                          On revient sur l'octet de lecture (cas d'un chiffre) ou après l'indicateur de symbole (cas d'un symbole sauf étoile)

]                                             Fin du cas "tout sauf étoile"

>                                            On passe sur l'indicateur de symbole (cas d'un chiffre ou étoile) ou deux cases après dans les autres cas

[                                             Cas "étoile uniquement"

<+>-                                     1 sera le code de la multiplication et on passe l'indicateur de symbole à false

>>                                        On saute deux cases pour passer au nombre suivant

]                                             Fin du cas "étoile uniquement"

<                                            On revient sur l'octet de lecture (cas d'un chiffre) ou après l'indicateur de symbole (cas d'un symbole)

,                                             Lecture du caractère suivant

]                               <<                                            Tout est lu et on revient sur le code opérateur

[->>+<<]>[-<+>]>[-<+>]            On permute le code opérateur et le second opérande

+<                                            On met le "bit else" à 1 et on se place sur l'operateur

[                                               Cas "addition/soustraction/multiplication"

-                                              On ôte un au code

[                                             Cas "addition/soustraction"

-                                           On ôte un au code

[                                           Cas "addition"

-                                         On ôte un au code (qui vaut 0 maintenant normalement)

>-<                                     Réinitialisation du "bit else"

<                                        On passe sur le second opérande

[-<+>]                                 On réalise l'addition

>                                        On repasse sur le "bit else"

]                                           Fin du cas "addition"

>                                          On passe sur le "bit else"

[                                           Cas "soustraction"

-                                         Réinitialisation du "bit else"

<<                                      On passe sur le second opérande

[->+<]<[->+<]                      On décale les deux opérandes d'un cran à droite

>                                        On passe sur le premier opérande

[                                         Cas où le premier opérande n'est pas nul

>>>+<<<                          On ajoute un autre "bit else" pour le signe du résultat

>[-<-[<]>>]>                      On réalise la soustraction et on va voir si on est sur le bit de signe

[                                       Cas négatif ou nul

<<                                  On regarde le résultat

[                                     Cas négatif

>>                                On revient sur le bit de signe

>++++                          On accélère un peu le calcul du symbole "moins"

[-<+++++++++++>]<.    On affiche le symbole "moins"

[-]                                 On réinitialise le bit de signe

<<[-<+>]                       On copie le résultat "négatif" en résultat "positif"

]                                     Fin du cas négatif

>                                    On revient avant le bit de signe

]                                       Fin du cas négatif ou nul

>[-]                                   On vide le bit de signe

<<<[-<+>]                         Copie du résultat en première position

]                                         Fin du cas où le premier opérande n'est pas nul

>>+<                                  Cas où le premier opérande est nul avec un bit else pour le cas où la seconde l'est aussi

[                                                        Si la seconde est non nulle

>-<                                                  On vire le bit else

<<+++++[->+++++++++<]>.            On affiche "moins"

[-]                                                     On vide le symbole "moins"

>[-<<+>>]>>                                    On copie le résultat en première position et on revient au bon endroit

]                                         Fin du cas où la seconde est non nulle

>[->>]<                               Si les deux opérandes sont nuls on revient au bon endroit

<                                        On repasse sur le "bit else"

]                                           Fin du cas "soustraction"

<                                          On repasse sur l'opérateur

]                                             Fin du cas "addition/soustraction"

>                                                           On passe sur le "bit else"

[                                                            Cas "multiplication"

-                                                          Réinitialisation du "bit else"

<<<                                                     On passe sur le premier opérande

[->[->+>+<<]>>[-<<+>>]<<<];              On réalise la multiplication

>[-]>[-<<+>>]                                       On nettoie et on déplace le résultat en première position

>                                                         On repasse sur le "bit else"

]                                                            Fin du cas "multiplication"

<                                                           On repasse sur l'opérateur

]                                                              Fin du cas "addition/soustraction/multiplication"

>                                                             On passe sur le "bit else"

[                                                              Cas "division"

-                                                            Réinitialisation du "bit else"

<+<<                                                     On passe sur le premier opérande avec un "bit else" après les opérandes pour un dividende nul

[                                                            Tant que la division n'est pas finie

>>[-]<<                                                On reset le "bit else" du dividende nul

>[->+>+<<]                                          On duplique le diviseur

>                                                         On passe sur la première copie

[                                                          Tant que la copie n'est pas nulle

-<<-[>]>>>                                         On la soustrait au premier opérande

[                                                        Cas ou le dividende est devenu nul (cas "division terminée")

>+<<                                               On place un "bit else" pour le cas où la copie est nulle (division "sans reste")

[>>-<<[->-<]]                                    S'il y a un reste on le calcule (différence entre la seconde copie du second opérande et ce qu'il reste de la première copie)

>>[-<[-]>>+<]                                   S'il n'y a pas de reste on ajoute 1 au résultat

]                                                        Fin du cas "division terminée"

<<                                                     On revient sur la copie

]                                                          La copie a été soustraite au premier opérande

>>>+<<                                               On ajoute 1 au résultat (en trop après la dernière boucle)

[-<<+>>]                                              On recrée le second opérande

<<<                                                     On se replace sur le premier opérande

]                                                            Fin de la division

>>[<[-]>->>>+<<<]                                 Cas du dividende nul: on ajuste

>>>[-<<<<<+>>>>>]<<<<<- ;                On recopie le résultat en première position et on lui ôte 1

>>>                                                       On se repositionne au même endroit que pour les autres calculs

]                                                              Fin du cas division

<<<[->>>+<<<]>>>                                  Décalage du résultat de 3 cases (en cas de "double résultat" :division avec reste et quotient)

+<                                                         "Bit else" pour un résultat nul

[                                                              Tant que le résultat n'est pas nul

>[-]<                                                      On réinitialise le "bit else" au besoin

>++++++++++<                                     On écrit "10" (pour faire une division et afficher le résultat en base 10)

[                                                            Tant que la division n'est pas finie

>[->+>+<<]                                          On duplique le diviseur

>                                                         On passe sur la première copie

[                                                          Tant que la copie n'est pas nulle

-<<-[>]>>>;                                       On la soustrait au premier opérande

[                                                        Cas ou le dividende est devenu nul (cas "division terminée")

>+<<                                               On place un "bit else" pour le cas où la copie est nulle (division "sans reste")

[>>-<<[->-<]]                                    S'il y a un reste on le calcule (différence entre la seconde copie du second opérande et ce qu'il reste de la première copie)

>>[-<[-]>>+<]                                   S'il n'y a pas de reste on ajoute 1 au résultat

]                                                        Fin du cas "division terminée"

<<                                                     On revient sur la copie

]                                                          La copie a été soustraite au premier opérande

>>>+<<                                               On ajoute 1 au résultat (en trop après la dernière boucle)

[-<<+>>]                                              On recrée le second opérande

<<<                                                     On se replace sur le premier opérande

]                                                                            Fin de la division

>>++++++[-<++++++++>]                                     On ajoute 48 au reste (pour afficher un chiffre)

<[-<+>]                                                                 On copie le reste en première position

>>>>[-<<<<+>>>>]<<<<-                                      On recopie le quotient en seconde position et on lui ôte 1

]                                                                              On divise le quotient à son tour par 10 (pour avoir un résultat en base 10)

[+++++[-<++++++++>]>]<                                     Cas du "bit else" à 1 (résultat nul): on ajoute 48 pour avoir le caractère 0

<[.[-]<]                                                                    On affiche le résultat en base 10

<                                                                             On se place sur le reste (éventuel)

[                                                                              S'il y a un reste

>>>++++++++[-<++++<++++>>]                           On commence par un peu de formatage

<++++++++++++.<.                                                              (affichage d'une virgule puis ' reste '

>++++++[->++>++<<]              >++++++++++++++.>+.<+.+.>.    ;  [-]<[-]<<.[-]<                                                           Fin du formatage

[                                                                             Tant que le résultat n'est pas nul

>++++++++++<                                                   On écrit "10" (pour faire une division et afficher le  résultat en base 10)

[                                                                           Tant que la division n'est pas finie

>[->+>+<<]                                                        On duplique le diviseur

>                                                                        On passe sur la première copie

[                                                                         Tant que la copie n'est pas nulle

-<<-[>]>>>                                                       On la soustrait au premier opérande

[                                                                       Cas ou le dividende est devenu nul (cas "division terminée")

>+<<                                                              On place un "bit else" pour le cas où la copie est     nulle (division "sans reste")

[>>-<<[->-<]]                                                 S'il y a un reste on le calcule (différence entre la seconde copie du second opérande et ce qu'il reste de la première copie)

>>[-<[-]>>+<]                                                S'il n'y a pas de reste on ajoute 1 au résultat

]                                                                      Fin du cas "division terminée"

<<                                                                   On revient sur la copie

]                                                                         La copie a été soustraite au premier opérande

>>>+<<                                                             On ajoute 1 au résultat (en trop après la dernière  boucle)

[-<<+>>]                                                           On recrée le second opérande

<<<                                                                   On se replace sur le premier opérande

]                                                                          Fin de la division

>>++++++[-<++++++++>]                                   On ajoute 48 au reste (pour afficher un chiffre)

<[-<+>]                                                               On copie le reste en première position

>>>>[-<<<<+>>>>]<<<<-                                    On recopie le quotient en seconde position et on lui ôte 1

]                                                                            On divise le quotient à son tour par 10 (pour avoir un résultat en base 10)

<[.[-]<]                                                                  On affiche le résultat en base 10

>                                                                          On revient à la position initiale

]                                                                              Fin du cas avec un reste

<                                                                             On remet le curseur à 0 parce que c'est plus propre

 

Code sans commentaires :

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

Source : http://www.prise2tete.fr  (Auteur : Scarta)

 

Tenter l’aventure Brainfuck !

 

Si l’expérience vous tente, vous pouvez vous essayer au Brainfuck sur le site suivant :

 

https://copy.sh/brainfuck/

 

Une vidéo expliquant les bases de la programmation en Brain fuck :

 

https://www.youtube.com/watch?v=8GRm_uBpHDY

 

 

Les différentes « commandes » adaptées en Brainfuck :

 

Mettre à 0 un octet pointé :

 

[     boucle

-     enlever 1 à la case courante

]     jusque à ce que la case soit à zéro

 

Enregistrer une chaîne de caractères :

 

,[.>,]

 

Copie d’un octet :

 

>[-]>[-]<< 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.

 

 

If :

 

>[code<]<[>]

 

If / else :

 

>[-]>[-]<<                   Mise à zéro des 2 variables suivantes (facultatif si connues pour être nulles)

[>+>+<<-]                    Double copie de V dans C et T

>>[-<<+>>]<                  Restauration de V à partir de T (T = 0) / retour sur la copie de la variable

        >[-]+                Initialisation du témoin (T = 1)

        <                    Retour sur la copie de la variable

        [                    Si la copie de la variable = true

               code_if

        [-]>-<]              Destruction de la copie de la variable / destruction du témoin

        >                    Déplacement sur le témoin

        [<                   Si le block if ne s'est pas exécuté (témoin = 1) / Retour sur la (copie de la) variable

               code_else   

        >-<]                  Destruction du témoin (dans ce cas (la copie de) la variable est déjà nulle vu que if ne s'est pas exécuté)

                            Retour sur la (copie de la) variable détruite

 

Addition :

 

++>++++++++<    index0 = 2 / index1 = 8 / retour sur index 0

 

>[<+>-]<        Additionne index1 avec index0 en détruisant index1

 

Soustraction :

++++++++>++++<   V = 8 / S = 4 /  retour sur V

 

>[-<->]<        Détruit S et le soustrait à V

 

 

Multiplication :

 

                                     Initialisation

[-]                                  R = 0

>[-]                                 T = 0

>[-]+++                              O = 0 / O = 3 (changez ici le nombre d'incrémentation pour modifier le résultat)

>[-]+++++                            M = 0 / M = 5 (changez ici le nombre d'incrémentation pour modifier le résultat)

 

<                                    Reviens à O

[                                    Tant que O différent de 0

        >                                Passe à M

        [                                Tant que M différent de 0

                <<+                          Reviens à T / Incrémenter T

                <+                           Reviens à R / Incrémenter R

                >>>-                         Passe à M / Décrémenter M

        ]                                Retour boucle

        <<[>>+<<-]                 Reinitialise M / Détruit T     

        >-                          Décrémente O

]                                    Retour boucle

>[-]                               Retourne à M / M = 0

<                                   Retourne O déjà = 0

<[-]                                 Retourne à T / T = 0

<                                    Retourne à R

(Source : https://fr.wikipedia.org/wiki/Brainfuck)

 

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *