Skyduino:~#
Articles
arduino, Autre, programmation

[Arduino] Interpréteur de BrainFuck

Bonjour tout le monde !

Aujourd’hui il fait chaud et j’ai donc un peu (beaucoup) la flemme de rédiger mon article de test sur l’arduino leonardo (version olimex).
Du coup je vous ai préparé un article qui va à coup sure tuer toute productivité jusqu’en fin d’aprés-midi (ou pas).

Le sujet du jour : le langage BrainFuck !
Sur plateforme arduino bien sur 😉

BrainFuck késako ?

Si on en crois ce que dit wikipedia :
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.

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.
Source : http://fr.wikipedia.org/wiki/Brainfuck

Comme en plus c’est l’anniversaire des 100 ans de la machine de turing je ne pouvais pas trouver un meilleur article pour débuter la semaine 😉

Pour ceux qui n’auraient pas compris, le brainfuck est un langage de programmation encore plus démoniaque et incompréhensible que l’assembleur.
Après une séance de programmation en BrainFuck votre cerveau devrait normalement avoir perdu 95% de ses capacités intellectuelle …

Bon ok restons sérieux 🙂

Le brainfuck est un langage de programmation minimaliste qui ce compose de seulement 8 instructions et d’un pointeur :

>​	incrémente l'adresse du pointeur.
<​	décrémente l'adresse du pointeur.
+​	incrémente l'octet pointé.
-​	décrémente l'octet pointé.
.​	affiche (sur la sortie standard) l'octet pointé (valeur ASCII).
,​	récupère un octet depuis l'entrée standard
[​	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.

Pour ceux qui ne voient pas trop à quoi correspondent les différentes instructions voici leurs correspondances en langage C :

>​	ptr++;​
< ​	ptr--;​
+​	(*ptr)++;​
-​	(*ptr)--;​
.​	putchar(*ptr);​
,​	(*ptr) = getchar();​
[​	while(*ptr) {​
]​	}

Ok … et maintenant ?

Vous avez désormais une vision sommaire de ce qu’est le langage BrainFuck, maintenant comment exécuter un programme BrainFuck ?

Il existe plein de solutions :
– compiler un programme en langage C avec des macro permettant d’inclure des portions de programme BF,
– utiliser un interpréteur de langage BF,
– utiliser un compilateur de langage BF,
– …

J’ai choisi la seconde option, avec une petite particularité : mon interpréteur BF est écrit pour tourner sur une carte arduino 🙂

Autre petite particularité, contrairement aux « vrai » interpréteurs de BF, mon interpréteur prend tout caractéres autre qu’une instruction comme la fin du programme.
(Normalement tout caractéres autre qu’une instrcution BF est considéré comme un commentaire)

Cela est du au faite que j’utilise le port série pour communiquer avec la carte arduino et que par conséquent je n’est pas vraiment de notion de « fin de fichier ».

Le programme :

/*
 * Interpréteur BrainFuck pour plateforme arduino 
 */

/* Espace mémoire du programme (ROM) */
#define PROGRAM_BUFFER 6144 // arduino mega2560
//#define PROGRAM_BUFFER 1024 // arduino UNO
char program[PROGRAM_BUFFER];

/* Espace mémoire des données (RAM) */
#define MEMORY_BUFFER 1024 // arduino mega2560
//#define MEMORY_BUFFER 512 // arduino UNO
uint8_t memory[MEMORY_BUFFER] = {0};

/* Variables divers */
uint16_t memory_pointer = 0;
uint16_t program_length = 0;

/* setup() */
void setup() {

  /* Initialisation du port série */
  Serial.begin(115200);  
  Serial.println("BrainFuck Interpreter");

  /* Demande à l'utilisateur de saisir sont programme */
  Serial.println("BF code :");
  char c;
  do {
    while(Serial.available() < 1); // Attend un octet sur le port série
    c = Serial.read();
    if(c != '>' && c != '<' && c != '+' && c != '-' && c != ',' && c != '.' && c != '[' && c != ']') 
      break; // Si ce n'est pas une instruction on quitte la boucle (!! pas en accord avec le standard BF)
    program[program_length++] = c; // Stocke l'instruction
  } 
  while(program_length < PROGRAM_BUFFER); // Boucle tant que l'utilisateur entre des instructions et qu'il reste de la place en mémoire

  process(0); // Lance le programme
  Serial.println("\n-- FIN"); // Fin du programme
}

/* Interprétation du langage BF (fonction récursive) */
void process(uint16_t program_pointer) {

  /* Tant que des instructions BF sont disponible */
  while(program_pointer < program_length) {
  
    /* Interpréte l'instruction courante et passe à la suivante */
    switch(program[program_pointer++]) {
    
    case '>': // Incrémente l'adresse du pointeur
      if(memory_pointer < (MEMORY_BUFFER - 1));
        ++memory_pointer; // Action protégé contre le buffer overflow
      break;

    case '<': // Décrémente l'adresse du pointeur
      if(memory_pointer > 0);
        --memory_pointer; // Action protégé contre le buffer overflow
      break;

    case '+': // Incrémente la valeur pointé
      ++memory[memory_pointer];
      break;

    case '-': // Décrémente la valeur pointé
      --memory[memory_pointer];
      break;

    case ',': // Récupére un caractére depuis le port série
      Serial.print("\n>");           // Affiche la ligne de prompt
      while(Serial.available() < 2); // attend que l'utilisateur entre une donnée + \n
      Serial.write(Serial.peek());   // Affiche la donnée 
      Serial.write('\n');            // + un retour ligne
      memory[memory_pointer] = Serial.read(); // Stocke l'octet recu en mémoire
	  Serial.read(); // Ignore le \n en fin de ligne
      break;

    case '.': // Affiche un caractére sur le port série
      Serial.write(memory[memory_pointer]);
      break;

    case '[': // Boucle tant que la valeur pointé est non nulle
      if(memory[memory_pointer]) {
        process(program_pointer--); // Appel récursif de fonction
      } 
      else {
        byte loop_count = 0;
        while(program[program_pointer] != ']' || loop_count > 0) { // Saut vers le ] fermant
          if(program[program_pointer] == '[') // Ignore le prochain ] si l'instruction courante est [
            ++loop_count;
          if(program[program_pointer] == ']') // N'ignore pas le prochain ] (Le précédent [ est maintenant fermé)
            if(loop_count-- == 0)
              return; // Protection anti "roll-over"
          if(++program_pointer == program_length) 
            return; // Action protégé contre le buffer overflow
        }
        ++program_pointer;
      }
      break;

    case ']':
      return; // Retour à l'appel de fonction parent
      break;
    } 
  }
}

/* loop() */
void loop() {
  // Rien à faire ici
}

Le résultat :

Un petit « Hello World ! » sa vous tentent ? 😉

Le code du « Hello World » en BrainFuck :
++++++++++[>+++++++>++++++++++>+++>+<<<++.>+.+++++++..+++.>++.<.+++.------.--------.>+.>.

Ce qui donne sur le Serial Monitor une fois le code BraiFuck entré aprés le « BF code : » :
BrainFuck Interpreter
BF code :
Hello World!

-- FIN

Remarque : pour que ce code fonctionne correctement il faut configurer les fins de lignes du Serial Monitor en mode « Newline » (\n).

Enjoy 🙂

Discussion

3 réflexions sur “[Arduino] Interpréteur de BrainFuck

  1. Je me demande si le langage FORTH est pas encore plus minimaliste…

    Publié par Barbudor | 26 juin 2012, 22 h 07 min
  2. Je crois que je viens de trouver quelqu’un de plus fou que moi, quel etait le but ? Incroyable motivation et incroyuable effort, ça fait au moins 2 heures que je lis vos articles, mais la ca ma retourné.

    En tous cas bravo pour le site super riche en article, (sur le cout je pensais que c’était un blog communautaire avec plusieurs auteurs)

    @+

    Publié par admin | 16 mai 2013, 2 h 27 min

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

Skyduino devient Carnet du Maker

Le site Carnet du Maker remplace désormais le blog Skyduino pour tout ce qui touche à l'Arduino, l'informatique et au DIY.