Partage
  • Partager sur Facebook
  • Partager sur Twitter

[Atelier tous langages] Codez un interpréteur de Brainfuck

étudier, contribuer, discuter

    21 août 2008 à 15:04:49

    Après un peu de débat avec d'autres membres du forum, on a décidé de relancer un "Atelier multi-langages".

    Le premier, improvisé, était Différents algorithmes de compression. Ça c'est très bien passé et je vous invite à aller voir le topic pour avoir une idée du but de l'exercice.

    Le sujet qui a été choisi est un interpréteur de Brainfuck. Le Brainfuck est un langage de programmation très simple, très chiant à utiliser mais pour lequel il est relativement facile de coder un interpréteur. C'est à la portée même des débutants dans le domaine.

    edit : je viens d'avoir un retour "oh non le BrainFuck on comprend rien". Les codes écrits en BF sont effectivement crytpiques, mais si on l'a choisi c'est parce qu'il est simple à interpréter : pas de gestion de variables, etc. Donc du point de vue de l'implémenteur (qui est le votre sur ce topic) il est simple. N'ayez pas peur, allez lire un document décrivant le langage au calme (la page wikipédia suffit largement), et ça ira très bien.

    Le sujet est volontairement assez libre. Vous devez faire un programme qui lit en entrée un code Brainfuck, et qui permet de produire le résultat attendu. Plusieurs voies d'explorations sont possibles (par exemple on peut essayer de gérer un ruban infini), et on ne vous en voudra pas de faire quelque chose de simple dans un premier temps.


    Il n'y a pas de règles formelles (c'est pas un concours ou quoi, pas besoin de s'inscrire, etc), mais voici quelques points de bon sens :

    On veut le code, on veut tripoter



    Publiez toujours la source de votre programme (normalement vous n'avez besoin de donner rien d'autre); il faudrait, dans la mesure du possible, que chacun puisse l'essayer chez soi (donc évitez les langages propriétaires, les machins pas portables du tout, etc.).

    Essayez de présenter votre source de la manière la plus lisible et la plus claire possible (pas de "oh j'ai pas eu le temps de mettre des vrais noms de variables"); sinon, vous vous exposez aux commentaires du public, et ça peut vous poursuivre pendant longtemps (hein delroth ?).

    Les autres participants peuvent reprendre la source, la modifier, l'améliorer, etc. On n'impose pas de licence ou quoi (et si vous précisez une licence libre elle sera respectée, enfin j'espère), mais si vous n'êtes pas prêts à vous faire tripoter, ne postez rien.


    Éviter les répétitions



    Si vous avez fait un programme dans votre langage préféré, mais qu'il existe déjà une proposition pour ce langage (ou un langage quasiment identique) et que le votre n'apporte visiblement rien, vous pouvez vous retenir de poster. Cherchez plutôt un aspect intéressant à explorer (une optimisation, etc.).

    Le but c'est surtout d'avoir un certain nombre de versions intéressantes à comparer, et de pouvoir voir par exemple les forces ou les faiblesses de certains langages ou styles de programmation. Pas de montrer à tout le monde qu'on est le meilleur programmeur de la planète (même si c'est cool aussi).




    Si vous êtes débutant, n'hésitez pas à poser des questions si vous ne comprenez pas ou n'arrivez pas à faire quelque chose.

    Pour lancer le topic, voici un premier code écrit très serviablement par coucou47. C'est en PHP (on se moque pas, le but c'était que tout le monde puisse comprendre), et il n'est pas du tout optmisé, le but étant d'être clair et accessible. Je poste ici la deuxième version, mais vous pouvez trouver le tout à cette adresse. Si vous trouvez cela douloureusement commenté, c'est parce qu'on l'a forcé.

    <?php
    /**
     * @brief fonction qui interprete un code brainfuck
     * solution sans preprocessing
     * @param $code le code a interpreter
     */
    function brainfuck_verbeux($code){
      $code_len = strlen($code);
      $mem = array();
      $indice_memoire = 0;
      for ($i=0;$i<$code_len;$i++){
        if (!isset($mem[$indice_memoire])) $mem[$indice_memoire]=0;
        else {
           // les valeurs sont comprises entre 0 et 256.
          $mem[$indice_memoire] = (256 + $mem[$indice_memoire] ) % 256;
        }
        switch($code[$i]){
          case '>': $indice_memoire++; break;
          case '<': $indice_memoire--; break;
          case '.': echo chr($mem[$indice_memoire]); break; // on affiche la valeur
          case ',': $mem[$indice_memoire]=prompt(); break;
          case '+': $mem[$indice_memoire]++; break; // on incremente la valeur
          case '-': $mem[$indice_memoire]--; break; // on decremente la valeur
          case ']':
            $n = 1; // on doit remonter $n [ en arriere
            while ($n){
              $i --; // on cherche en arriere
              if ($code[$i]==']') $n++; // si on rencontre un ], alors on attend un [ de plus
              else if ($code[$i]=='[') $n--; // si on trouve un [. alors on en attend un de moins
            } $i--; // on "jump" devant le [ correspondant.
            break;
          case '[':
            if ( $mem[$indice_memoire] == 0 ){
              $n = 1; // on doit monter $n ] en avant
              while ($n){
                $i ++;
                if ($code[$i]=='[') $n++; // si on rencontre un [, alors on attend un ] de plus
                else if ($code[$i]==']') $n--; // si on trouve un ]. alors on en attend un de moins
              } // ici, on a pas de $i-- parce-qu'on jump apres le ]
          } break;
        }
      }
    }
    
    
    brainfuck_verbeux(
    '++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.');
    brainfuck_verbeux(',>,<+>+<.>.');
    
    ?>
    


    • Partager sur Facebook
    • Partager sur Twitter
      21 août 2008 à 15:34:13

      Je viens de coder une version Python pas trop moche qui utilise des générateurs pour l'I/O du programme Brainfuck, et qui fonctionne plutôt bien :
      #!/usr/bin/env python
      #-*- encoding: utf-8 -*-
      """
      bf.py
      Brainfuck intepretor
      """
      
      import sys
      
      def brainfuck(code, inchan):
          """
          Read the brainfuck code from "code", input data from inchan, and yields
          output.
          """
          jumpstable = [] # List of tuples (from, dest)
      
          # Loop on the whole code in order to fill the jump table
          for startpos, instruction in enumerate(code):
              if instruction == '[':
                  n = 1
                  for offset, endinstruction in enumerate(code[startpos:]):
                      if endinstruction == '[':
                          n += 1
                      elif endinstruction == ']':
                          n -= 1
                          if n == 1:
                              jumpstable.append((startpos, startpos + offset))
                              break
          memory = 30000 * [0] # The memory is 30000 cases wide.
          memindex = 0 # Start at position 0
      
          codepos = 0 # Position in the code
          while codepos < len(code): # Main loop
              inst = code[codepos]
              if inst == '<': memindex -= 1
              elif inst == '>': memindex += 1
              elif inst == '+': memory[memindex] += 1
              elif inst == '-': memory[memindex] -= 1
              elif inst == '.': yield memory[memindex]
              elif inst == ',': memory[memindex] = inchan.next()
              elif inst == '[' and memory[memindex] == 0:
                  endpos = filter(lambda (s, e): s == codepos, jumpstable)[0][1]
                  codepos = endpos
              elif inst == ']':
                  stpos = filter(lambda (s, e): e == codepos, jumpstable)[0][0]
                  codepos = stpos - 1
              codepos += 1
              memory[memindex] = (255 if memory[memindex] < 0
                                      else memory[memindex] % 256)
      
      def stdinchan():
          """
          Read the input data from stdin. If EOF encountered, always return 0.
          """
          while True:
              try:
                  yield ord(sys.stdin.read(1))
              except EOFError:
                  break
          while True:
              yield 0
      
      code = '''>++++++++++>+>+[
          [+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[
              [-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-
                  [>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>
          ]<<<
      ]'''
      
      for char in brainfuck(code, stdinchan()):
          sys.stdout.write(chr(char))
          sys.stdout.flush()
      
      """
      Copyright (c) 2008 Pierre "wgmpgp" Bourdon <root@wgmpgp.is-a-geek.org>
      
      This program is free software: you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published by
      the Free Software Foundation, either version 3 of the License, or
      (at your option) any later version.
      
      This program is distributed in the hope that it will be useful,
      but WITHOUT ANY WARRANTY; without even the implied warranty of
      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      GNU General Public License for more details.
      
      You should have received a copy of the GNU General Public License
      along with this program.  If not, see <http://www.gnu.org/licenses/>.
      """
      


      Ça utilise d'ailleurs le fait très pratique que tableau[-1] accède à la dernière case d'un tableau en Python pour gérer les indexs négatifs ;) .
      • Partager sur Facebook
      • Partager sur Twitter
        21 août 2008 à 17:10:40

        Cool, j'essaierai de m'y coller ce soir...

        Thierry
        • Partager sur Facebook
        • Partager sur Twitter
          Admin 21 août 2008 à 17:14:38

          Voici une version en C.

          Elle est fonctionelle mais il reste plein de petite fioriture a faire :

          La gestion d' un code mal foutu ( évité les dépassement de memoire, les boucles non fermante)

          Alors deja voila le main:

          main.c:
          #include "brainfuck.h"
          
          int main(void)
          {
          
          	brainfuck("++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.");
          	brainfuck(",>,<+>+<.>.");
          
          	return (0);
          }
          


          Ensuite voila brainfuck.h

          #include <stdlib.h>
          #include <stdio.h>
          #include <string.h>
          
          #define FAILLURE 0
          #define SUCCESS 1
          
          /*Structure de donnée contenant la memoire de l' intérpreteur*/
          typedef struct Bf_mem{
          	char * memory;
          	int memorySize;
          	int currentMemPosition;
          }Bf_mem;
          
          /*Calcul l'espace memoire nécéssaire au programme*/
          int necessaryMemorySize(char * code);
          /*Initialise la structure de donnée*/
          int init(char * code, Bf_mem * mem);
          /*Fonction principal du module*/
          int brainfuck(char * code);
          /*L' interpréteur en lui meme*/
          int bf_interpreteur(char * code, Bf_mem * memory);
          /*Liberation de la memoire*/
          void freeMem(Bf_mem * mem);
          


          Et voila brainfuck.c
          #include "brainfuck.h"
          
          /*Fonction Principal:
          Initialisation et appel de l' interpréteur
          */
          int brainfuck(char * code)
          {
          	int r = FAILLURE;
          	Bf_mem memory;
          
          	if(init(code, &memory) == SUCCESS)
          	{
          		r = bf_interpreteur(code, &memory);
                                          freeMem(&memory);
          	}
          
          	return (r);
          }
          
          /*L' interpréteur en lui même
          TODO: Gestion d' un code mal écrie*/
          int bf_interpreteur(char * code, Bf_mem * memory)
          {
          	unsigned int i = 0;
          	int r = SUCCESS;
          
          	for(i = 0; i < strlen(code); i++)
          	{
          		switch (code[i])
          		{
          		case '>':
          			/*TODO Gestion des indices hors memoire*/
          			memory->currentMemPosition++;
          			break;
          		case '<':
          			/*TODO Gestion des indices or memoire*/
          			memory->currentMemPosition--;
          			break;
          		case '+':
          			memory->memory[memory->currentMemPosition]++;
          			break;
          		case '-':
          			memory->memory[memory->currentMemPosition]--;
          			break;
          		case '.':
          			putchar(memory->memory[memory->currentMemPosition]);
          			break;
          		case ',':
          			memory->memory[memory->currentMemPosition] = getchar();
          			break;
          		case '[':
          			/*Si la case memoire pointé est a zero on saute a son crochet fermant*/
          			if(memory->memory[memory->currentMemPosition] == 0)
          			{
          				int numOfBrackets = 1;
          				while(numOfBrackets != 0)
          				{
          					i++;
          					if(code[i] == '[')
          						numOfBrackets++;
          
          					else if( code[i] == ']')
          						numOfBrackets--;
          				}
          			}
          			break;
          		case ']':
          			/*On doit remonté a son crochet ouvrant*/
          			if(1)
          			{
          				int numOfBrackets = 1;
          				while(numOfBrackets != 0)
          				{
          					i--;
          					if(code[i] == '[')
          						numOfBrackets--;
          
          					else if( code[i] == ']')
          						numOfBrackets++;
          				}
          				/*On passe un caractere en arriere pour retourné sur l' evaluation du caractere '['*/
          				i--;
          			}
          			break;
          		default:
          			break;
          		}
          	}
          
          	return (r);
          }
          
          /*initialisation de la structure memoire*/
          int init(char * code, Bf_mem * mem)
          {
          	int r = FAILLURE;
          	mem->currentMemPosition = 0;
          	mem->memorySize = necessaryMemorySize(code);
          
          	mem->memory = 0;
          	mem->memory = calloc(1,mem->memorySize);
          
          	if(mem->memory != 0)
          		r = SUCCESS;
          
          	return (r);
          }
          
          /*Retourne l'espace memoire maximal nécéssaire au programme*/
          
          int necessaryMemorySize(char * code)
          {
          	unsigned int i = 0;
          	int maxSize = 1;
          	int tmpSize = 1;
          
          	for( i = 0; i < strlen(code); i++)
          	{
          		switch(code[i])
          		{
          		case '>':
          			tmpSize++;
          			if(tmpSize > maxSize)
          				maxSize++;
          			break;
          		case '<':
          			tmpSize--;
          			break;
          		default: 
          			break;
          		}
          	}
          
          	return (maxSize);
          }
          void freeMem(Bf_mem * mem)
          {
          	mem->currentMemPosition = 0;
          	mem->memorySize = 0;
          	free(mem->memory);
          
          	mem->memory = 0;
          }
          


          La fonction intéréssente etant bien sur : int bf_interpreteur(char * code, Bf_mem * memory)

          Edit: Oublier la liberation de la memoire :D , Algo de calcul de l' éspace memoire
          • Partager sur Facebook
          • Partager sur Twitter
            21 août 2008 à 17:50:16

            J'ai aussi fait une version C, mais plus simple (et plus naïve), qui se rapproche fortement de la version PHP, donc il n'y a pas vraiment d'intérêt à la poster ici.
            Par contre je vais tenter une version C++ avec une approche un peu différente.
            • Partager sur Facebook
            • Partager sur Twitter
              21 août 2008 à 18:19:09

              int necessaryMemorySize(char * code)
              ta fonction est totalement fausse...

              a part ca, c'est la traduction de mon code...
              • Partager sur Facebook
              • Partager sur Twitter
                21 août 2008 à 18:33:53

                Effectivement, brainfuck("<") devrait normalement faire planter ton code joliement (haha, allocation de UINT_MAX octets).
                • Partager sur Facebook
                • Partager sur Twitter
                  21 août 2008 à 18:41:43

                  Bonjour !
                  J’apporte moi aussi ma pièce à l’édifice. Je crois que c’est la première faites dans un langage de programmation fonctionnel, en l’occurence en Erlang. Alors pour les petites différences par rapports aux autres versions : on a ni tableaux, ni pointeurs. À la place on se sert de listes. Et plus précisement un Zipper. Le principe est très simple, on découpe une liste en 3 parties :
                  1. ce qu’il y a avant le curseur
                  2. le curseur
                  3. ce qu’il y a après le curseur

                  Ce qui nous permet ainsi facilement d’attendre l’élément précédent ou l’élément suivant de la liste sans avoir à tout parcourir. :) Vous verrez dans mon code que grace à la syntaxe [Tête|Queue] offerte par erlang pour représenter les listes on peut réduire ce découpage à deux listes, bref… Seulement l’utilisations de deux zippers simultanéments (un pour les instructions, un pour la mémoire) rend le code assez difficile à lire. :(

                  Mais voyez plutôt :
                  -module(brainfuck).
                  -export([start/1]).
                  
                  start(Str) -> brainfuck([], Str, [], [0]).
                  
                  brainfuck(_, [], _, _) -> ok;
                  brainfuck(A, B, [], C) -> brainfuck(A, B, [0], C);
                  brainfuck(A, B, C, []) -> brainfuck(A, B, C, [0]);
                  brainfuck(Prevs, [Act|Next], [CPrev|CPrevs], [CAct|CNext]) ->
                      case [Act] of
                  	">" -> brainfuck([Act|Prevs], Next, [CAct, CPrev|CPrevs], CNext);
                  	"<" -> brainfuck([Act|Prevs], Next, CPrevs, [CPrev, CAct|CNext]);
                  	"+" -> brainfuck([Act|Prevs], Next, [CPrev|CPrevs], [(CAct + 1)|CNext]);
                  	"-" -> brainfuck([Act|Prevs], Next, [CPrev|CPrevs], [(CAct - 1)|CNext]);
                  	"." -> 
                  	    io:put_chars([CAct]),
                  	    brainfuck([Act|Prevs], Next, [CPrev|CPrevs], [CAct|CNext]);
                  	"," ->
                  	    [NewCAct|_] = io:get_line("> "),
                  	    brainfuck([Act|Prevs], Next, [CPrev|CPrevs], [NewCAct|CNext]);
                  	"[" when CAct == 0 ->
                  	    {A, B, C, D} = skip([Act|Prevs], Next, [CPrev|CPrevs], [CAct|CNext]),
                  	    brainfuck(A, B, C, D);
                  	"["  -> brainfuck([Act|Prevs], Next, [CPrev|CPrevs], [CAct|CNext]);
                  	"]" when CAct == 0 -> brainfuck([Act|Prevs], Next, [CPrev|CPrevs], [CAct|CNext]);
                  	"]" -> 
                  	    {A, B, C, D} = back(Prevs, [Act|Next], [CPrev|CPrevs], [CAct|CNext]),
                  	    brainfuck(A, B, C, D)
                      end.
                  
                  skip(_, _, _, []) -> exit("Boucle non fermée");
                  skip(Prevs, [Act|Next], [CPrev|CPrevs], [CAct|CNext]) ->
                      case [Act] of
                  	"]" -> {Prevs, [Act|Next], [CPrev|CPrevs], [CAct|CNext]};
                  	"[" ->
                  	    {A, B, C, D} = skip([Act|Prevs], Next, [CPrev|CPrevs], [CAct|CNext]),
                  	    skip(A, B, C, D);
                  	_ -> skip([Act|Prevs], Next, [CPrev|CPrevs], [CAct|CNext])
                      end.
                  
                  back(_, _, [], _) -> exit("Boucle non fermée");
                  back([Prev|Prevs], [Act|Next], [CPrev|CPrevs], [CAct|CNext]) ->
                      case [Prev] of
                  	"[" -> {[Prev|Prevs], [Act|Next], [CPrev|CPrevs], [CAct|CNext]};
                  	"]" ->
                  	    {A, B, C, D} = back([Prev|Prevs], [Act|Next], [CPrev|CPrevs], [CAct|CNext]),
                  	    back(A, B, C, D);
                  	_ -> back(Prevs, [Prev, Act|Next], [CPrev|CPrevs], [CAct|CNext])
                      end.
                  


                  Pour tester :
                  $ erl
                  ...
                  1> c(brainfuck).
                  {ok,brainfuck}
                  2> brainfuck:start("votre code").

                  Si vous avez des questions n’hésitez ps à les poser !
                  • Partager sur Facebook
                  • Partager sur Twitter
                    21 août 2008 à 19:03:08

                    Intéressant la version Erlang, ça change un peu, par contre c'est effectivement assez difficile à lire.

                    Voilà ma version C++ :

                    #include <iostream>
                    #include <string>
                    #include <vector>
                    #include <stack>
                    
                    using namespace std;
                    
                    int main(int argc, char *argv[])
                    {
                        if (argc < 2) {
                    	cout << "Specifiez un code Brainfuck !" << endl;
                            return -1;
                        }
                    	
                        string code = argv[1];
                    
                        vector<char> memory; //Tableau d'octets
                        vector<char>::iterator memPtr = memory.begin(); //Represente le pointeur 
                        vector<int> brackets(code.length()); //Correspondance des positions de '[' et ']'
                        stack<char,vector<char>> bracketStack; //Pile pour stocker la position des '['
                    
                        memory.push_back(0);
                        memPtr = memory.begin();
                    	
                        //On parcourt une premiere fois le code pour noter les correspondances entre '[' et ']'
                        //(a chaque [ correspond un ] et vice versa)
                        for (size_t i = 0; i < code.length(); i++) {
                    	if (code[i] == '[')
                                bracketStack.push(i);
                    	    if (code[i] == ']') {
                    		if (bracketStack.empty()) {
                    		    cerr << "] inattendu en position" << i << endl;
                    		    return 1;
                    		}
                    		else {
                    		    int pos = bracketStack.top(); //On cherche le '[' correspondant
                    		    bracketStack.pop();
                    		    brackets[i] = pos; //Il correspond au ']' trouvé
                    		    brackets[pos] = i; //et inversement
                    		}
                    	    }
                    	}
                        if (!bracketStack.empty()) {
                            cerr << "[ non fermé en position" << bracketStack.size() << endl;
                            return 1;
                        }
                    
                        //Deuxieme parcourt du code : execution
                        for (size_t i = 0; i < code.length(); i++) {
                            switch (code[i]) {
                           	    case '<' : if (memPtr != memory.begin()) memPtr--; break;
                    	    case '>' :
                                    if (memPtr == memory.end() - 1) {
                    	            memory.push_back(0);
                    		    memPtr = memory.end() - 1;
                    		}
                    		else 
                                        memPtr++; 
                    		break;
                    	    case '+' : (*memPtr)++; break;
                                case '-' : (*memPtr)--; break;
                    	    case '.' : cout.put(*memPtr); break;
                    	    case ',' : *memPtr = cin.get(); break;
                    	    case '[' : if (!(*memPtr)) i = brackets[i]; break;
                    	    case ']' : if (*memPtr) i = brackets[i]; break;
                    	}
                        }
                        return 0;
                    }
                    


                    Je pense que les commentaires expliquent à peu près bien.

                    [EDIT] Modifié le code pour gérer un tableau de taille infini.
                    • Partager sur Facebook
                    • Partager sur Twitter
                      21 août 2008 à 19:19:03

                      Et une version en caml, tirant partie des foncteurs.
                      La version est assez longue et son but est d'être modulaire.

                      J'ai découpé le code en plusieurs modules :
                      • La structure de donnée utilisée pour stocker la mémoire
                      • Le type des données
                      • Le flux du code

                      Pour chacun de ces modules j'ai défini une interface et j'apporte une implémentation.

                      La mémoire


                      La structure de donnée utilisée pour la mémoire doit contenir plusieurs élements, et être infinie (s'aggrandissant quand il faut). De plus, elle doit garder un "pointeur" vers un élement particulier de la mémoire (la case actuelle) et permettre de déplacer ce pointeur facilement.
                      Voilà l'interface :
                      module type Memory = sig
                        type 'a t
                        val update : ('a -> 'a) -> 'a t -> 'a t
                        val get : 'a t -> 'a
                        val forward : 'a t -> 'a t
                        val backward : 'a t -> 'a t
                        val single : 'a -> 'a t
                      end
                      

                      update permet de modifier l'élement qui est pointé, et single retourne une mémoire contenant un seul élément, et dont le pointeur pointe sur cet élement.

                      Mon implémentation repose également sur un Zipper, qui s'aggrandit en remplissant avec l'élément passé à single :
                      module Zipper : Memory = struct
                        type 'a t = {
                          before : 'a list;
                          current : 'a;
                          after: 'a list;
                          default : 'a;
                        }
                        let update f ({current = a} as zipper) = {zipper with current = f a}
                        let get {current = a} = a
                        let forward zipper = match zipper.after with
                          | [] -> { zipper with current = zipper.default; 
                      		before = zipper.current :: zipper.before;  }
                          | t :: q -> {zipper with before = zipper.current :: zipper.before; current = t; 
                      		   after = q}
                      
                        let swap zipper =  { zipper with after = zipper.before; before = zipper.after }
                        let backward z = swap (forward (swap z))
                        let single a = {
                          before = []; after = []; current = a; default = a
                        }
                      end
                      



                      Le type des données


                      Les données contenues dans notre mémoire doivent supporter l'incrémentation, la décrémentation, et doivent posséder un zéro(qui sert pour les boucles), ainsi que la lecture et l'écriture à l'écran :
                      module type Data = sig 
                        type t
                        val zero : t
                        val incr : t -> t
                        val decr : t -> t
                        val print : t -> unit
                        val read : unit -> t
                      end
                      

                      L'implémentation pour les entiers :
                      module Int : Data = struct
                        type t = int
                        let incr = (+) 1 and decr x = x - 1 and zero = 0
                        let print = Printf.printf "%c" |< char_of_int
                        let read () = int_of_char (input_line stdin).[0]
                      end
                      


                      Le flux de code


                      Le flux de code doit permettre de se déplacer aussi bien en avant qu'en arrière (pour les boucles) et doit permettre l'accès rapide à un élement courant. On retrouve quasiment les mêmes contraintes que pour le Zipper, ceci dit il y a quelques différentes : le flux est en lecture seule (pas de modification) et sa taille est fixée. Voici l'interface et son implémentation basée sur un char array :

                      module Stream = struct
                        type 'a t = 'a array * int
                      
                        let at (array, n) = array.(n)
                        let prev (array, n) = (array, n-1)
                        let next (array, n) = (array, n + 1)
                        let of_chan chan = 
                          let buffer = Buffer.create 100 in
                          let rec loop () = 
                            match (try Some (input_line chan) with _ -> None) with
                      	| Some l -> Buffer.add_string buffer l; loop ()
                      	| None -> ()
                          in loop ();
                            let s = Buffer.contents buffer in
                            (Array.init (String.length s) (String.get s), 0)
                      
                      end
                      



                      Here we are, nous avons nos trois modules, on peut commencer à coder l'interpréteur en lui même. Il s'agit donc d'un foncteur, paramétré avec nos trois signatures. L'implémentation est assez naïve et rejoint celle d'eelte :
                      module Brainfuck (Stream : Stream) (Mem : Memory) (Data : Data) = struct
                        type mem = Data.t Mem.t
                        type operator = 
                          | Simple of (mem -> mem)
                          | Complex of (char Stream.t -> mem -> (char Stream.t * mem))
                      
                        let jump move incr_char decr_char = 
                          let rec aux n st = 
                            if Stream.at st = incr_char then
                      	aux (n+1) (move st)
                            else if Stream.at st = decr_char then
                      	if n = 1 then
                      	  st
                      	else
                      	  aux (n - 1) (move st) 
                            else
                      	aux n (move st)
                          in move >| aux 1 >| Stream.next
                      
                        let incr_char = '+'
                        let decr_char = '-'
                        let forward_char = '>'
                        let backward_char = '<'
                        let prompt_char = ','
                        let print_char = '.'
                        let jump_forward_char = '['
                        let jump_backward_char = ']'
                        let jump_forward st mem = 
                          (if Mem.get mem = Data.zero then
                            jump Stream.next jump_forward_char jump_backward_char st
                          else
                            Stream.next st), mem
                      
                        let jump_backward st mem =
                          (if Mem.get mem <> Data.zero then
                            jump Stream.prev jump_backward_char jump_forward_char st
                          else
                            Stream.next st), mem
                      
                        let exec = function
                          | Simple f -> (fun st mem -> (Stream.next st, f mem))
                          | Complex f -> f
                      
                        let operators = [
                          incr_char, Simple (Mem.update Data.incr);
                          decr_char, Simple (Mem.update Data.decr);
                          forward_char, Simple Mem.forward;
                          backward_char, Simple Mem.backward;
                          prompt_char, Simple (fun mem -> Mem.update (const (Data.read ())) mem);
                          print_char, Simple (fun mem -> Data.print (Mem.get mem); mem);
                          jump_forward_char, Complex jump_forward;
                          jump_backward_char, Complex jump_backward;
                        ]
                        let exec_chan chan = 
                          let st = Stream.of_chan chan in
                          let rec loop (st, mem) = 
                            let c = Stream.at st in
                      	loop 
                      	  (try
                      	     (exec (List.assoc c operators) st mem)
                      	   with Not_found -> (Stream.next st, mem))
                          in loop (st, Mem.single Data.zero)
                      end
                      


                      Et enfin la boucle principale :
                      let () = 
                        let module MyBrainfuckInterpreter = Brainfuck(Stream)(Zipper)(Int) in
                          if Array.length Sys.argv > 1 then begin
                            let fd = open_in Sys.argv.(1) in
                      	(try MyBrainfuckInterpreter.exec_chan fd with _ -> ());
                      	close_in fd
                          end
                      

                      Et voilà, le tour est joué :p

                      Le code utilise l'opérateur >| qui compose deux fonctions, dans le sens suggéré par la flèche. Son implémentation est laissée au lecteur :-°
                      Code pasté.
                      • Partager sur Facebook
                      • Partager sur Twitter
                        21 août 2008 à 19:29:28

                        'Soir,

                        Ma version en C, finie il y'a quelques jours (après d'autres jours de réflexion :p). Par rapport à l'autre elle fait:
                        > Lecture du code BF dans un fichier - Allocation Dynamique du tableau nécessaire.
                        > Allocation directe de la pile BF de 30 000 cases
                        > Elle utilise deux tableaux de correspondance ( Un pour les [ et un pour les ] ) construit une seule fois.
                        > Pour gérer les boucles, un troisième tableau dynamique est utilisé (enfin, réutilisé), en tant que pile.
                        > De fait, aucune structure n'est déclarée. Le code n'est pas non plus séparé en fonctions, j'n'en voyais pas l'utilité directe.

                        Je vous laisse découvrir :) Si vous avez des questions, n'hésitez pas. Le code est en secret pour 140 lignes à ceux que ca n'intéresserais pas. Si vous trouvez des bugs, vous pouvez aussi faire remonter :)

                        #include <stdio.h>
                        #include <stdlib.h>
                        
                        #define Debu /* Set to Debug to enter debbuging Mode */
                        #define StackS 30000
                        
                        int main(int argc, char **argv) {
                        
                            FILE *f = NULL;
                            int Stack[StackS] = {0};
                            char *Bf=NULL;
                            int *BStack=NULL,*FStack=NULL,*CStack=NULL;
                            int SIdx = 0;
                            int i=0,j=0,l=0,o=0;
                            int Len = 0,NbB=0;
                        
                            if (argc < 2)
                                printf("BFInt - by RedoX, 2008\n\n"\
                                       "Usage: ./BfInt /path/to/file\n"),exit(0); /* Aucun Fichier */
                            if (!(f = fopen(argv[1], "r")))
                                printf("Can't open the file %s.\n", argv[1]), exit(-1); /* Erreur */
                            do {
                                getc(f); /* On Lit l'char */
                                Len++;  /* On Incremente la longeur */
                            } while (!feof(f)); /* Tant qu'il en reste */
                            Len--; /* On corrige le depassement */
                            rewind(f); /* On r'vient au debut */
                            Bf = malloc((unsigned)Len*sizeof(char)); /* On alloue assez d'place */
                            if (!Bf) printf("Malloc Error 1.Aborting!"),exit(-1);
                        
                            for (i=0;i<Len;i++) {
                                Bf[i] = (char)getc(f); /* On place le char lu dans Bf */
                                if (Bf[i] == '[') { /* On compte les [ */
                                    NbB++; /* Compte Final */
                                    SIdx++; /* Verif Nb Paires de [ ] Ok */
                                }
                                if (Bf[i] == ']') SIdx--; /* Verif Nb paires */
                            }
                        
                            if (SIdx) /* Erreur */
                                printf("Unmatching Square Brackets." \
                                       "Sum of [ - Sum of] = %d.Aborting!\n",SIdx), exit(-1);
                        
                            BStack = malloc((unsigned)NbB*sizeof(int)); /* Stack Index des [ */
                            if (!BStack) printf("Malloc Error 2.Aborting!"),exit(-1);
                            FStack = malloc((unsigned)NbB*sizeof(int)); /* Stack Index des ] */
                            if (!FStack) printf("Malloc Error 3.Aborting!"),exit(-1);
                            CStack = malloc((unsigned)NbB*2*sizeof(int)); /* Stack Temporaire */
                            if (!CStack) printf("Malloc Error 4.Aborting!"),exit(-1);
                        
                            for (i=0;i<2*NbB;i++)
                                CStack[i] = -1;   /* On Init la Stack */
                        
                            i=0;
                            while (i<Len) {
                                if (Bf[i] == '[') {
                                    BStack[j] = i; /* On met l'index du [ dans la BStack */
                                    CStack[l] = j++; /* On l'met aussi dans la CStack */
                                    l += 2; /* On laisse un vide pour le ] correspondant */
                                } else if (Bf[i] == ']') {
                                    o=l-1; /* On s'init a l'index courant -1 pour l'decalage */
                                    while (CStack[o] != -1) /* On remonte jusqu'au premier -1 libre*/
                                        o -= 2;
                                    CStack[o] = i; /* On y met l'index courant du ] */
                                }
                                i++;
                            }
                        
                            for (i=0;i<NbB;i++)
                                FStack[i] = CStack[1+2*i]; /* On Remplis la Stack des ] */
                        
                            for (j=0;j<NbB;j++)
                                CStack[j] = 0; /* On vide la Stack pour la reutiliser */
                        
                        #ifdef Debug
                            for (j=0;j<NbB;j++)
                                printf("J: %d B: %d F: %d - B: %c F: %c\n",
                                        j,BStack[j],FStack[j],Bf[BStack[j]],Bf[FStack[j]]);
                            getchar();
                        #endif
                        
                            i=0; /* Index dans Bf */
                            j=0; /* Index dans CStack */
                            SIdx=0;
                            while (i<Len) {
                                if (Bf[i] == '+')
                                    Stack[SIdx]++; /* Incremente Case */
                                else if (Bf[i] == '-')
                                    Stack[SIdx]--; /* Decremente */
                                else if (Bf[i] == '>')
                                    SIdx++;        /* Incremente Pointeur */
                                else if (Bf[i] == '<')
                                    SIdx--;        /* Decremente */
                                if (SIdx > StackS)
                                    SIdx = 0;      /* Retour Index 1 */
                                if (SIdx < 0)
                                    SIdx = StackS-1; /* Avance Dernier Index */
                                else if (Bf[i] == '.') {
                                    putchar(Stack[SIdx]); /* Affichage case */
                                } else if (Bf[i] == ',')
                                    Stack[SIdx] = (char)getchar(); /* Modif Case */
                                else if (Bf[i] == '[') {
                                    o=0; /* Nombre de [ */
                                    l=i; /* Index pour remonter chaine */
                                    while (l > BStack[0]) /* avant le premier [ */
                                        if (Bf[l--] == '[')
                                            o++; /* On compte les [ */
                                    CStack[j] = o; /* On Update l'index */
                        #ifdef Debug
                                    printf("\nStack, J: %d I: %d O: %d :: ",j,i,o);
                                    for (l=0;l<NbB;l++)
                                        printf("%d ",CStack[l]);
                        #endif
                                    if (Stack[SIdx] == 0) { /* Si jump */
                                        i = FStack[CStack[j--]]; /* On Jump au ] correspondant */
                                        CStack[j+1] = 0;  /*On Delete l'index courant */
                                    }
                                    j++;
                                } else if (Bf[i] == ']')
                                    i = BStack[CStack[--j]]-1; /* On retourne au [ correspondant */
                                i++;
                            }
                        #ifdef Debug
                            printf("\nLast O: %d, Last J: %d\n",o,j);
                            for (j=0;j<NbB;j++)
                                printf("J: %d B: %d F: %d - B: %c F: %c\n",
                                        j,BStack[j],FStack[j],Bf[BStack[j]],Bf[FStack[j]]);
                            for (l=0;l<NbB;l++)
                                printf("%d ",CStack[l]);
                            getchar();
                        #endif
                        
                            /* On libere la memoire allouee */
                            free(Bf);
                            free(BStack);
                            free(FStack);
                            free(CStack);
                            return 0;
                        }
                        


                        Si vous voulez un p'tit détail, pas forcément plus clair que le code, vous pouvez jetter un oeil ici : http://plume.redox.ws/?17-and-counting

                        'nne soirée,
                        RedoX
                        • Partager sur Facebook
                        • Partager sur Twitter
                          21 août 2008 à 19:53:10

                          Je sais, il y a beaucoup de code en C, mais vu qu'aucun ne montre la véritable beauté du C, je vais poster le miens.

                          Je l'ai codé il y a bien un an et demi, et pas dans le but d'un atelier quelconque donc j'ai mis des tests de sureté
                          ( malloc != NULL, fopen != NULL, etc). On peut lire un fichier bf et obtenir l'input d'un autre fichier ou de stdin.

                          La mémoire est un tableau, qui grossit de 256 si besoin est.
                          Les conditions sont géré par une pile qui garde l'index de la condition entrante ( '[' ) pour pouvoir y revenir au niveau du ']'.
                          C'est du C ANSI.

                          Ah, et j'ai codé ça pour moi il y a longtemps, donc il y a peu de commentaires, et ils sont en anglais.

                          #include <stdio.h>
                          #include <stdlib.h>
                          #include <string.h>
                          
                          #define MAPSTEP 256
                          
                          struct world {
                              unsigned char *map;
                              size_t size;
                              unsigned char *p;
                              struct stack *cond;
                          };
                          
                          struct stack {
                              struct stack *prev;
                              int value;
                          };
                          
                          static void grow(struct world *, int);
                          static void cond_add(struct world *, int);
                          static void cond_del(struct world *);
                          
                          static inline void *xmalloc(size_t);
                          static inline FILE *xfopen(const char *);
                          
                          int
                          main(int argc, char *argv[])
                          {
                              long len, i;
                              FILE *fpin, *fpget;
                              char *p;
                              int c;
                              struct world w;
                          
                              memset(&w, 0, sizeof w);
                          
                              if (argc >= 3) {
                                  fpin = xfopen(argv[1]);
                                  fpget = xfopen(argv[2]);
                              } else if (argc == 2) {
                                  fpin = xfopen(argv[1]);
                                  fpget = stdin;
                              } else {
                                  fpin = stdin;
                                  fpget = stdin;
                              }
                          
                              fseek(fpin, 0, SEEK_END);
                              len = ftell(fpin); /* get the length of the script */
                          
                              if (len == -1) {
                                  fprintf(stderr, "Nothing to read, exiting\n");
                                  return EXIT_FAILURE;
                              }
                          
                              fseek(fpin, 0, SEEK_SET);
                              p = xmalloc(len * sizeof *p);
                              for (i = 0; i < len; i++) {
                                  c = getc(fpin);
                                  if (c == EOF) { /* something really weird append. We quit cleanly */
                                      fprintf(stderr, "EOF received but not expected. Exit.\n");
                                      free(p);
                                      return EXIT_FAILURE;
                                  }
                                  p[i] = (unsigned char) c;
                              }
                          
                              /* allocate the map */
                              grow(&w, 1);
                              w.p = w.map;
                              /* now we execute the code */
                              for (i = 0; i < len; i++) {
                                  switch(p[i]) {
                                  case '>':
                                      w.p++;
                                      if (w.p > &w.map[w.size - 1]) /* grow the map */
                                          grow(&w, 1);
                                      break;
                                  case '<':
                                      if (w.p > w.map)
                                          w.p--;
                                      else /* grow the map */
                                          grow(&w, 0);
                                      break;
                                  case '+':
                                      if (255 == (*w.p))
                                          *w.p = 0;
                                      else
                                          (*w.p)++;
                                      break;
                                  case '-':
                                      if (0 == (*w.p))
                                          *w.p = 255;
                                      else
                                          (*w.p)--;
                                      break;
                                  case '.':
                                      putchar((int) (*w.p));
                                      break;
                                  case ',':
                                      (*w.p) = (unsigned char) getc(fpget);
                                      break;
                                  case '[':
                                      if (0 == (*w.p)) { /* skip the code between [] */
                                          int k = 1;
                          
                                          while (k && i < w.size) {
                                              i++;
                                              if (p[i] == '[')
                                                  k++;
                                              else if (p[i] == ']')
                                                  k--;
                                          }
                                      } else
                                          cond_add(&w, i);
                                      break;
                                  case ']':
                                      if (!w.cond)
                                          break;
                                      if (0 != (*w.p)) /* jump back to the matching [ */
                                          i = w.cond->value;
                                      else
                                          cond_del(&w);
                                      break;
                                  default:
                                      break;
                                  }
                              }
                              while (w.cond) {
                                  fprintf(stderr, "%s: carac %d: No matching ']'\n",
                                          (argc < 2) ? "stdin" : argv[1], w.cond->value);
                                  /* print the context 5 lignes before and after */
                                  for (i = (w.cond->value < 5) ? 0 : w.cond->value - 5;
                                       i < w.cond->value + 5 && i < w.size; i++)
                                      putchar(p[i]);
                                  cond_del(&w);
                              }
                          
                              free(w.map);
                              free(p);
                          
                              fclose(fpget);
                              fclose(fpin);
                          
                              return EXIT_SUCCESS;
                          }
                          
                          static void
                          grow(struct world *w, int after)
                          {
                              size_t oldsize = w->size;
                          
                              w->size += MAPSTEP;
                              w->map = realloc(w->map, w->size * sizeof *w->map);
                          
                              if (after) {
                                  memset(&w->map[oldsize], 0, MAPSTEP * sizeof *w->map);
                                  w->p = &w->map[oldsize];
                              } else { /* move the old map in the new map's end */
                                  memmove(&w->map[MAPSTEP], w->map, oldsize);
                                  memset(w->map, 0, MAPSTEP * sizeof *w->map);
                                  w->p = &w->map[w->size - oldsize - 1];
                              }
                          }
                          
                          static void
                          cond_add(struct world *w, int val)
                          {
                              struct stack *s;
                          
                              s = xmalloc(sizeof *s);
                              s->prev = w->cond;
                              s->value = val;
                              w->cond = s;
                          }
                          
                          static void
                          cond_del(struct world *w)
                          {
                              struct stack *s;
                          
                              if (w->cond) {
                                  s = w->cond;
                                  w->cond = s->prev;
                                  free(s);
                              }
                          }
                          
                          static inline void *
                          xmalloc(size_t n)
                          {
                              void *p;
                          
                              p = malloc(n);
                              if (!p) {
                                  fprintf(stderr, "Can't allow more memory. Exiting...\n");
                                  exit(EXIT_FAILURE);
                              }
                          
                              return p;
                          }
                          
                          static inline FILE *
                          xfopen(const char *file)
                          {
                              FILE *fp;
                          
                              fp = fopen(file, "r");
                              if (!fp) {
                                  perror(file);
                                  exit(EXIT_FAILURE);
                              }
                          
                              return fp;
                          }
                          
                          • Partager sur Facebook
                          • Partager sur Twitter
                            21 août 2008 à 20:29:57

                            Dark-Side : comment tu gères une mémoire circulaire avec un zipper ?
                            • Partager sur Facebook
                            • Partager sur Twitter
                              21 août 2008 à 20:45:31

                              Citation : bluestorm

                              Dark-Side : comment tu gères une mémoire circulaire avec un zipper ?


                              Elle est pas circulaire, elle est infinie (du moins je ne trouve pas de meilleur dénomination).
                              En fait l'idée c'est que quand j'arrive au bout de la mémoire je rajoute des cases, c'est d'ailleurs à ça que servent les deux premières clauses de la « fonction brainfuck/4 ». :)
                              • Partager sur Facebook
                              • Partager sur Twitter
                                21 août 2008 à 20:49:25

                                Un code C++ ayant déjà été proposé, je tiens quand même à apporter ma pierre à l'édifice. Voici un compilateur BF écrit en BF.

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


                                Il n'est pas de moi. Il vient d'ici : http://esoteric.sange.fi/brainfuck/bf-source/prog/
                                • Partager sur Facebook
                                • Partager sur Twitter
                                Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
                                  21 août 2008 à 20:57:19

                                  J'ai rédigé une autre implémentation en OCaml. À la différence de celle d'asmanur, elle utilise un parseur (ce qui simplifie grandement le code) et va un peu plus loin que la simple interprétation (avec un prototype de compilateur pour brainfuck).

                                  Comme le texte est un peu long, je l'ai mis sur internet : Implémentation d'un Brainfuck en OCaml. À priori, le programme est suffisamment commenté pour être lisible par quelqu'un qui ne connaît pas l'OCaml (à ce stade, c'est même du literate programming :-° ). Si vous avez des suggestions ou des remarques en tout genre, merci de me le faire savoir :) .
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    21 août 2008 à 20:58:17

                                    C'est là qu'on voit pourquoi ce langage s'appelle Brainfuck...
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                    Anonyme
                                      21 août 2008 à 21:01:38

                                      Comme le lien de lastsseldon est intéressant, je me permets de le redonner afin qu'il ne passe pas inaperçu dans le reste du topic.

                                      http://lasts.no-ip.org/brainfuck.html

                                      De rien, lasts.
                                      Ton agent de presse qui t'aime.
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        21 août 2008 à 21:59:47

                                        Dark-Side : comment tu gères une mémoire circulaire avec un zipper ?
                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          21 août 2008 à 22:36:05

                                          une version assez marrante en C:

                                          gcc brainfuck.c --pedantic --ansi -O2 -O3 -Wall
                                          valgrind ./a.out -c helloworld.bf
                                          

                                          elle passe valgrind, -Wall --pedantic et --ansi sans probleme apparent.

                                          pour lancer un programme :

                                          ./a.out -c fichier_source

                                          on peut faire -o fichier output pour rediriger la sortie
                                          on peut faire -i fichier input pour rediriger l'entree


                                          #include <ctype.h>
                                          #include <stdio.h>
                                          #include <stdlib.h>
                                          #include <unistd.h>
                                          #include <getopt.h>
                                          
                                          
                                          
                                          #define BOUCLE_ERROR 1
                                          #define MALLOC_ERROR 2
                                          #define READING_ERROR 3
                                          #define OPT_ERROR 4
                                          
                                          #define F_DEBUG  1
                                          /* stack */
                                          struct stack {
                                            struct stack *prev;
                                            int content;
                                          };
                                          
                                          struct stack * newStack(){
                                            struct stack *s = malloc(sizeof(struct stack));
                                            if (!s){
                                              fputs("malloc error\n", stderr);
                                              exit(MALLOC_ERROR);
                                            }
                                            return s;
                                          }
                                          
                                          void stack_push(struct stack **s, int content){
                                            struct stack *s2 = newStack();
                                            s2->prev = *s;
                                            s2->content = content;
                                            *s=s2;
                                          }
                                          
                                          int stack_pop(struct stack **s){
                                            struct stack *s2 = (*s);
                                            int c = s2->content;
                                            *s=s2->prev;
                                            free(s2);
                                            return c;
                                          }
                                          
                                          /* liste doublement chainee */
                                          struct mem {
                                            struct mem *prev, *next;
                                            unsigned char content;
                                          };
                                          
                                          struct mem * newMem(){
                                            struct mem *m = malloc(sizeof(struct mem));
                                            if (!m){
                                              fputs("malloc error\n", stderr);
                                              exit(MALLOC_ERROR);
                                            }
                                            m->prev = NULL;
                                            m->next = NULL;
                                            m->content = 0;
                                            return m;
                                          }
                                          
                                          void link_listes(struct mem * prev, struct mem *next){
                                            prev->next = next;
                                            next->prev = prev;
                                          }
                                          
                                          struct mem * prev(struct mem *m){
                                            struct mem *p;
                                            if (m->prev) return m->prev;
                                            p = newMem();
                                            link_listes(p, m);
                                            return p;
                                          }
                                          
                                          struct mem * next(struct mem *m){
                                            struct mem *n;
                                            if (m->next) return m->next;
                                            n = newMem();
                                            link_listes(m, n);
                                            return n;
                                          }
                                          
                                          void freeMem(struct mem *m){
                                            struct mem *m2, *m3;
                                            m3=m->next;
                                            while (m3){
                                              m2 = m3->next;
                                              free(m3);
                                              m3 = m2;
                                            }
                                            m3=m->prev;
                                            while (m3){
                                              m2 = m3->prev;
                                              free(m3);
                                              m3 = m2;
                                            }
                                            free(m);
                                          }
                                          
                                          
                                          int brainfuck(char * code, int len, int flags, FILE *out, FILE * in){
                                            int i, j;
                                            struct mem *m = newMem();
                                            struct stack *s = newStack();
                                            int * jmps;
                                            jmps = malloc(len * sizeof(int));
                                            if (!jmps){
                                              freeMem(m);
                                              fputs("malloc error\n", stderr);
                                              exit(MALLOC_ERROR);
                                            }
                                            s->content = -1;
                                            for(i=0;i<len;i++){
                                              if (code[i]=='['){
                                                stack_push(&s, i);
                                              }else if(code[i]==']'){
                                                j=stack_pop(&s);
                                                if ( j == -1 ) return BOUCLE_ERROR;
                                                jmps[i]=j-1; jmps[j]=i;
                                              }
                                            }
                                            if ( s->content != -1 ) return BOUCLE_ERROR;
                                            free(s);
                                            for(i=0;i<len;i++){
                                              if (flags & F_DEBUG) fprintf(out, "\t %c %d\n", code[i], i);
                                              switch(code[i]){
                                                case 0: goto fin;
                                                case '+': m->content++; break;
                                                case '-': m->content--; break;
                                                case '<': m = prev(m); break;
                                                case '>': m = next(m); break;
                                                case '.': fputc(m->content, out); break;
                                                case ',': m->content = fgetc(in); break;
                                                case '[': if (m->content) break;
                                                  case ']': i=jmps[i]; break;
                                              }
                                            }
                                            fin:
                                            freeMem(m);
                                            free(jmps);
                                            return 0;
                                          }
                                          
                                          int main(int argc, char **argv){
                                          
                                            int flags = 0;
                                            int c;
                                            FILE *out = stdout;
                                            FILE *in = stdin;
                                            FILE *code = NULL;
                                            size_t length;
                                            int err;
                                            char * content;
                                            while ( (c=getopt(argc, argv, "do:i:c:")) != -1 ){
                                              switch (c){
                                                case 'd':
                                                  flags = flags | F_DEBUG;
                                                  break;
                                                case 'o':
                                                  out = fopen(optarg, "w");
                                                  if (out == NULL){
                                                    fprintf(stderr, "output error (%s)\n", optarg);
                                                    return READING_ERROR;
                                                  }
                                                  break;
                                                case 'i':
                                                  in = fopen(optarg, "r");
                                                  if (in == NULL){
                                                    fprintf(stderr, "input error (%s)\n", optarg);
                                                    return READING_ERROR;
                                                  }
                                                  break;
                                                case 'c':
                                                  code = fopen(optarg, "r");
                                                  break;
                                                case '?':
                                                  if (isprint (optopt))
                                                    fprintf (stderr, "Unknown option `-%c'.\n", optopt);
                                                  else
                                                    fprintf (stderr, "Unknown option character `\\x%x'.\n", optopt);
                                                  return OPT_ERROR;
                                                default:
                                                  abort ();
                                              }
                                            }
                                            if (code == NULL){
                                              fputs("code file error\n", stderr);
                                              exit(1);
                                            }
                                            fseek(code, 0, SEEK_END);
                                            length=ftell(code);
                                            content=malloc(length);
                                            if (!content){
                                              fputs("malloc error\n", stderr);
                                              return MALLOC_ERROR;
                                            }
                                            fseek(code, 0, SEEK_SET);
                                            c = fread (content,1,length,code);
                                            fclose(code);
                                            if (c != length) {
                                              fputs("Reading error\n", stderr);
                                              return READING_ERROR;
                                            }
                                            if ( (err=brainfuck(content, length, flags, out, in)) ){
                                              fprintf(stderr, "erreur (%d)\n", err);
                                              return err;
                                            }
                                            free(content);
                                            return 0;
                                          }
                                          
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            21 août 2008 à 23:09:05

                                            Citation : bluestorm

                                            Dark-Side : comment tu gères une mémoire circulaire avec un zipper ?


                                            Elle est pas circulaire, elle est infinie (du moins je ne trouve pas de meilleur dénomination).
                                            En fait l'idée c'est que quand j'arrive au bout de la mémoire je rajoute des cases, c'est d'ailleurs à ça que servent les deux premières clauses de la « fonction brainfuck/4 ». :)

                                            Une impression de déjà vu ? Mais non vous vous faites des idées.
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              22 août 2008 à 0:01:01

                                              Hey hey ! Super topic !

                                              Bon, j'ai fait une version Ruby qui n'est rien de plus qu'une pâle copie de la version PHP (avec moins de "$"...). Comme ça n'a que peu d'intérêt, je la colle .

                                              Edit : version buggée. Nouvelle version ici.

                                              J'ai essayé de voir s'il y avait moyen d'avoir une approche OO là-dessus, mais j'avoue ne pas être arrivé à quelque chose d'acceptable (quel intérêt de plus sur un code aussi court ?). Ce qui est intéressant par contre c'est qu'on constate une réelle différence entre les versions procédurales et les versions fonctionnelles.

                                              L'article de Lasts me paraît aussi très enrichissant.

                                              PS : dis donc Dark, comment tu gères une mémoire circulaire avec un zipper ?

                                              Encore bravo pour le topic les gars !
                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                22 août 2008 à 0:18:01

                                                Bonjour à tous,

                                                Désolé, je ne suis pas capable de faire quelque chose, je n'ai pas le niveau. En revanche, il y a un code que je n'arrive pas à faire fonctionner ou j'ai mal compris un truc, ce qui est fort possible. C'est le code Python de wgmpgp.

                                                À wgmpgp : Que doit-il se passer une fois qu'on a lancé le script en ligne de commande. Personnellement, j'ai des nombres grandissant qui s'affichent indéfiniment. J'imagine que ce n'est pas le comportement voulu pour un interpréteur, non ?

                                                Merci d'avance.
                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                  22 août 2008 à 0:28:46

                                                  Citation : sisco

                                                  Bonjour à tous,

                                                  Désolé, je ne suis pas capable de faire quelque chose, je n'ai pas le niveau. En revanche, il y a un code que je n'arrive pas à faire fonctionner ou j'ai mal compris un truc, ce qui est fort possible. C'est le code Python de wgmpgp.

                                                  À wgmpgp : Que doit-il se passer une fois qu'on a lancé le script en ligne de commande. Personnellement, j'ai des nombres grandissant qui s'affichent indéfiniment. J'imagine que ce n'est pas le comportement voulu pour un interpréteur, non ?

                                                  Merci d'avance.


                                                  Sisi, le code Brainfuck interprété affiche la suite de Fibonacci. C'est tout à fait voulu.
                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                    22 août 2008 à 0:31:36

                                                    Ah mille excuses. Charge à moi de changer le contenu de variable code pour qu'elle fasse autre chose (mettre un "Hello World" par exemple). C'est bien ça ?

                                                    Merci pour la réponse rapide.
                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                      22 août 2008 à 0:33:18

                                                      Exactement. J'aurais pu lire le code depuis un fichier ou depuis stdin, mais j'ai choisi la solution de facilité, a.k.a. le code en dur dans le script (en même temps, ça rajoute pas non plus une complexité extrème de lire depuis un fichier).
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        22 août 2008 à 0:36:25

                                                        euh... la gestion des options, c'est un truc assez chiant au final...
                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                          22 août 2008 à 0:37:53

                                                          Ok merci. J'ai juste un petit souci en mettant le code du "Hello world".

                                                          C'est bien ceci, non ? Chez moi, ça plante... [edit] Soyons précis : si je remplace le contenu de la variable code par ce qui est ci-dessous dans le code bf.py, ça plante.

                                                          code = '''++++++++++
                                                          [                 
                                                             >+++++++>++++++++++>+++>+<<<<-
                                                          ]
                                                                           
                                                          >++.                     
                                                          >+.                     
                                                          +++++++.                
                                                          .                         
                                                          +++.                      
                                                          >++.                      
                                                          <<+++++++++++++++.        
                                                          >.                        
                                                          +++.                      
                                                          ------.                   
                                                          --------.                 
                                                          >+.                       
                                                          >.      
                                                          ]'''
                                                          • Partager sur Facebook
                                                          • Partager sur Twitter
                                                            22 août 2008 à 0:57:49

                                                            Bah... en même temps ton code est pas valide. T'as une fin de boucle louche à la dernière ligne, qui correspond à aucun début de boucle.
                                                            • Partager sur Facebook
                                                            • Partager sur Twitter
                                                              22 août 2008 à 1:01:12

                                                              Mais oui ! Quel idiot je suis. Je ne sais pas ce que j'ai fichu.

                                                              C'est bon ça marche impeccable. Merci encore et désolé d'avoir mis en cause injustement ton code python. :)

                                                              A+

                                                              Edit

                                                              Pour plus de lisibilité voici le code correct d'un "Hello World! en BrainFuck :
                                                              ++++++++++
                                                              [                 
                                                                 >+++++++>++++++++++>+++>+<<<<-
                                                              ]
                                                                               
                                                              >++.                     
                                                              >+.                     
                                                              +++++++.                
                                                              .                         
                                                              +++.                      
                                                              >++.                      
                                                              <<+++++++++++++++.        
                                                              >.                        
                                                              +++.                      
                                                              ------.                   
                                                              --------.                 
                                                              >+.                       
                                                              >.
                                                              </span>
                                                              • Partager sur Facebook
                                                              • Partager sur Twitter

                                                              [Atelier tous langages] Codez un interpréteur de Brainfuck

                                                              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                                              × Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
                                                              • Editeur
                                                              • Markdown