Créer un compilateur/interpréteur Brainfuck

Tous langages

a marqué ce sujet comme résolu.

Lu'!

Une petite version C++ d'un interpréteur très légèrement optimisé sur les branchements (mais vraiment très légèrement, d'autant que les maps, c'est pas l'idée du siècle). J'ai choisi une bande circulaire pour rendre la partie interprétation noexcept.

J'ai essayé de rendre l'ensemble le plus robuste possible aux erreurs d'exécution (c'est ce qui m'a pris le plus de temps au pifomètre) et de trouver les endroits qui peuvent encore poser problème (signalé en annotations dans le code), tout en écrivant des contrats basiques sur les fonctions (et en mettant des indices sur les raisons qui font que le contrat est valide). L'ensemble me semble const-correct.

(Petite note : un fichier qui contiendrait des caractères pas trop catholiques ne passerait pas forcément bien dans la moulinette, vous êtes prévenus :P ).

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <cassert>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <iterator>
#include <array>
#include <stdexcept>
#include <map>

using str_citer = std::string::const_iterator;
using jumps = std::map<str_citer, str_citer>;

/* 
   Returns : true if c is a BF instruction false otherwise
   Exception : noexcept
*/   
inline bool is_an_inst(char c) noexcept {
  return c == '+' || c == '-' || c == '>' || c == '<' || 
         c == '.' || c == ',' || c == '[' || c == ']';
}

str_citer compute_jumps(std::string const& prg, str_citer start, jumps& from_to, jumps& to_from);
void extract_program(std::ifstream& ifs, std::string& program);
void interpret(std::string const& program, jumps const& from_to, jumps const& to_from) noexcept;

int main(int argc, char* argv[]){
  if(argc != 2)
    throw std::invalid_argument{ "use : ./exec file_name" };

  std::ifstream ifs{ argv[1], std::ios::in };
  //warning ! remaining exception : std::string allocation (x2)
  if(!ifs) throw std::runtime_error{ std::string{ argv[1] } + " does not exists" };

  //at this point :
  // - ifs is valid
  
  std::string prg{};
  extract_program(ifs, prg);

  //at this point :
  // - ifs is not valid anymore
  // - prg is a pure BF program
  
  jumps from_to, to_from;
  //exception : unmatched ]
  if(compute_jumps(prg, std::begin(prg), from_to, to_from) != std::end(prg))
    throw std::runtime_error{ "This program is not valid (unbalanced braces)." };
  
  //at this point :
  // - prg is a pure BF program
  // - from_to contains jumps from [ to ] and no occurrence of std::end(prg)
  // - to_from contains jumps from ] to [ and no occurrence of std::end(prg)

  interpret(prg, from_to, to_from);

  return 0;
}

/*
  Pre  : - ifs valid
  Post : - prg is pure BF
         - ifs is not valid anymore
  Exceptions : - IO exceptions on getline (unlikely)
               - allocation exception on program += and line allocation
               - remove_if cannot raise exception here
               - clear is noexcept
               - resize should not allocate (size is inferior)
*/
void extract_program(std::ifstream& ifs, std::string& program){
  using std::begin;
  using std::end;

  program.clear();
  for(std::string line{}; getline(ifs, line); ) program += line;

  //we only keep BF instructions
  auto e = std::remove_if(begin(program), end(program), [](char c){ return !is_an_inst(c); });

  //remove final moved characters
  program.resize(e - begin(program));
}

/*
  Pre  : - prg is pure BF
         - std::begin(prg) <= it <= std::end(prg)
  Post : - from_to contains jumps from [ to ] * and no occurrence of std::end(prg)
         - to_from contains jumps from ] to [ * and no occurrence of std::end(prg)
         * between Pre(it) and Return value
  Returns : - iterator to ] or std::end(prg) (if this last happens in a rec call it is an error)
  Exceptions : - runtime_error (parsing)
               - allocation error on inserting in the map
               - recursive call exceptions
*/
str_citer compute_jumps(std::string const& prg, str_citer it, jumps& from_to, jumps& to_from)
{
  //invariant : - std::begin(prg) <= it <= std::end(prg)
  //            - from_to and to_from contains all visited jumps
  while(it != std::end(prg)){
    if(*it == '['){
      str_citer begin { it };
      it = compute_jumps(prg, it+1, from_to, to_from);

      //exception : unmatched [
      if(it == std::end(prg))
        throw std::runtime_error{ "This program is not valid (unbalanced braces)." };

      assert(begin != std::end(prg)); //obvious
      assert(it    != std::end(prg)); //obvious

      //guarantee : from_to an to_from does not contain std::end(prg)
      from_to[begin] = it;
      to_from[it]    = begin;
    }
    else if(*it == ']') return it;
    
    ++it;
  }

  return std::end(prg);
}

/*
  Pre : - prg is a pure BF program
        - from_to contains jumps from [ to ] and no occurrence of std::end(prg)
        - to_from contains jumps from ] to [ and no occurrence of std::end(prg)
  Post: - nothing special : standard output as been updated with output
  Exceptions : noexcept
*/
void interpret(std::string const& program, jumps const& from_to, jumps const& to_from) noexcept{
  using std::begin;
  using std::end;

  std::array<char, 30000> data;
  data.fill(0);
  decltype(data)::iterator dp { begin(data) };

  str_citer pc { begin(program) };

  // Invariant : - std::begin(program) <= pc <= std::end(program) (== causes end loop)
  //             - std::begin(data)    <= dp <  std::end(program)
  while(pc != end(program)){
    char const byte { *dp };
    
    switch(*pc){
    case '+': ++(*dp); break;
    case '-': --(*dp); break;
    case '>': ++dp;    break;
    case '<': --dp;    break;
    case '.': std::cout<<byte; break;
    case ',': *dp = static_cast<char>(getchar()); break;
    case '[': if(!*dp)    pc = (*from_to.find(pc)).second; break;
    case ']': if( *dp)  pc = (*to_from.find(pc)).second; break;
    default : assert(false && "Something really bad happened");
    }
    if(dp == end(data)) dp = begin(data);

    ++pc;
  }
}

Le tout compile avec tout ce tas d'options :

1
2
3
4
CXXFLAGS=-Wall -Wextra -Werror -pedantic-errors -Wold-style-cast -Woverloaded-virtual -Wfloat-equal 
-Wwrite-strings -Wpointer-arith -Wcast-qual -Wcast-align -Wconversion -Wshadow -Weffc++ -Wredundant-decls 
-Wdouble-promotion -Winit-self -Wswitch-default -Wswitch-enum -Wundef -Wlogical-op -Winline -Wunused 
-Wuninitialized -std=c++1y -O2 -DNDEBUG

Sur ma machine, ça affiche Mandelbrot en 34s (en même temps c'est de l'interprété pur à La RacheTM ). Et l'exécution en DEBUG marche aussi évidemment ;) .

Voilà, voilà ^^ .

Tes performances sont assez bonnes pour un interpréteur. Par contre quand je le lance chez moi, le programme va de plus en plus lentement au cours de l'exécution (comme je le lance sur un netbook, j'ai bien le temps de noter la différence :-° ).

Après, parce que je suis obsessionnel compulsif :

1
2
3
4
int main(int argc, char* argv[]){
  if(argc != 2)
    throw std::invalid_argument{ "use : " + std::string{ argv[0] } + " file_name" };
    /* ... */

Sinon, pourquoi te contenter de -O2 pour la compilation? Il y a -O3 (c'est une vraie question : tu ne connais pas l'option ou il y a une raison précise?).

J'ai fais un code en Ruby. Mais j'ai le boules, c'est long, mais loooooooooooong ! Je n'ai aucune idée de comment optimiser mon code…

Actuellement, avant d'interpréter le brainfuck, je minimise le code (suppression des caractères non bf) puis je mémorise les début et fin des boucles pour ne pas avoir besoin de chercher les ']' correspondant aux '['.

il y a deux fichiers : brainfuck.rb et stack.rb. Le premier contient l'interpreteur, le second une stack brainfuck.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
require_relative 'stack'

class BfParser
  ACTIONS = { 
    '>' => :incr,
    '<' => :decr,
    '+' => :plus,
    '-' => :minus,
    '.' => :out,
    ',' => :in,
    '[' => :loop,
    ']' => :end_loop
  }

  def initialize(stack_size = 1000)
    @stack = BfStack.new stack_size
    @loop_stack = []
    @loops = {}
    @cursor = 0
  end

  def eval(bf_code)
    @tokens = minimize(bf_code).split ''
    init_loops

    same_action_counter = 0
    while @cursor < @tokens.size
      t = @tokens[@cursor]

      if t =~ /\d/
        same_action_counter = same_action_counter * 10 + t.to_i
      else
        # Call the method assigned to t
        send ACTIONS[t], same_action_counter == 0 ? 1 : same_action_counter
        same_action_counter = 0
      end
      @cursor += 1
    end
  end

  private

  def out(many)
    many.times { print @stack.get.chr }
  end

  def in(many)
    many.times do
      input = STDIN.getc
      @stack.set input.ord
    end
  end

  def plus(many)
    @stack.add many
  end

  def minus(many)
    @stack.add -many
  end

  def incr(many)
    @stack.jump many
  end

  def decr(many)
    @stack.jump -many
  end

  def loop(*args)
    if @stack.get == 0
      @cursor = @loops[@cursor]
    else
      @loop_stack << @cursor
    end
  end

  def end_loop(*args)
    if @stack.get == 0
      @loop_stack.pop
    else
      @cursor = @loop_stack.last
    end
  end

  def minimize(bf_code)
    bf_code.gsub(/[^<>,\.\-\+\[\]]/, '').gsub(/([^\[\]])\1+/) do |m|
      "#{m.size}#{m[0]}"
    end
  end

  def init_loops
    @tokens.each_with_index do |t, i|
      case t.to_sym
      when :'['
        @loop_stack << i
      when :']'
        @loops[@loop_stack.pop] = i
      end
    end

    raise "Invalid code: missing '[' or ']'" if not @loop_stack.empty?
  end
end

bf_code = IO.read(ARGV[0])

p = BfParser.new
p.eval bf_code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class BfStack
  attr_reader :cursor
  
  def initialize(stack_size)
    @stack = Array.new stack_size, 0
    @cursor = 0
  end

  def get
    @stack[@cursor]
  end

  def set(value)
    @stack[@cursor] = value
  end

  def jump(offset)
    @cursor = (@cursor + offset) % @stack.size
  end

  def add(value)
    @stack[@cursor] += value
  end
end

Tes performances sont assez bonnes pour un interpréteur. Par contre quand je le lance chez moi, le programme va de plus en plus lentement au cours de l'exécution (comme je le lance sur un netbook, j'ai bien le temps de noter la différence :-° ).

En fait il suit plutôt ça : début rapide, milieu lent, fin rapide. Je pense que la partie centrale nécessite plus de calcul (avec la version C d'@Alex j'ai le même comportement en plus rapide parce que pas de map pour les crochets, juste des appels récursifs).

Après, parce que je suis obsessionnel compulsif :

1
2
3
4
int main(int argc, char* argv[]){
  if(argc != 2)
    throw std::invalid_argument{ "use : " + std::string{ argv[0] } + " file_name" };
    /* ... */

J'y ai pensé aussi mais on introduit (comme aux lignes juste en dessous) un risque de jet d'exception pendant la construction de l'exception et je ne connais pas trop la sémantique de ce machin.

Sinon, pourquoi te contenter de -O2 pour la compilation? Il y a -O3 (c'est une vraie question : tu ne connais pas l'option ou il y a une raison précise?).

Bibibye

Parce qu'O3 est autorisé à casser. C'est une habitude. les optimisations sont autorisées à utiliser les comportements indéfinis pour optimiser quel que soit le niveau (ça, ce n'est pas un mystère), mais j'ai fait attention à ne pas en introduire. O3 lui est beaucoup plus agressif pour un gain généralement très faible (voir inverse) mais ne préserve pas forcément la sémantique du programme même sans comportement indéterminé. Donc je compile en O2 :) .

Tes performances sont assez bonnes pour un interpréteur. Par contre quand je le lance chez moi, le programme va de plus en plus lentement au cours de l'exécution (comme je le lance sur un netbook, j'ai bien le temps de noter la différence :-° ).

En fait il suit plutôt ça : début rapide, milieu lent, fin rapide. Je pense que la partie centrale nécessite plus de calcul (avec la version C d'@Alex j'ai le même comportement en plus rapide parce que pas de map pour les crochets, juste des appels récursifs).

Ksass`Peuk

C'est exactement ça : pour chaque point du plan, le calcul consiste a regarder si une certaine suite mathématique converge ou diverge. Lorsqu'on est à l'extérieur de la fractale, la suite diverge, et ce d'autant plus rapidement que l'on est loin de l'ensemble de Mandelbrot : le programme repère donc la divergence au bout d'un faible nombre d'itérations. Lorsqu'on s'approche du bord de la fractale, le nombre d'itérations avant de détecter la divergence est plus important (il tend vers l'infini en fait). On se limite donc à un nombre maximal d'itérations (typiquement 100), mais dans toute la zone centrale il faut faire ces 100 itérations pour se rendre compte que l'on ne diverge en fait pas, ce qui explique que le calcul est plus long dans cette zone.

(un peu HS, désolé)

+2 -0

Re!

Une autre version C++ inspirée de l'algo d'@Alex (les contrôles d'erreur du programme BF en plus), donc pas de système diablement intelligent pour les branchements, juste de la récursion et la pile est vachement plus rapide :) . Hormis la réduction du programme à du pur BF, on reste sur de l'interprété pur (pas de factorisation / simplification).

A priori, pas de memory fault possible (modulo alloc), les exceptions sont normalement toutes chopées sauf la runtime_error que je laisse passer pour la fin d'un programme invalide, hésitez pas à dire si vous voyez des endroits potentiels, j'ajouterai des annotations.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <iostream>  //std::cout
#include <fstream>   //std::ifstream

#include <cassert>   //assert
#include <stdexcept> //std::runtime_error

#include <array>     //std::array
#include <string>    //std::string
#include <algorithm> //std::remove_if

//program iterator type
using piter = std::string::const_iterator;
//memory type
using memory = std::array<char, 30000>;
//data iterator type
using diter = memory::iterator;

/* 
   Returns : true if c is a BF instruction false otherwise
   Exception : noexcept
*/   
inline bool is_an_inst(char c) noexcept {
  return c == '+' || c == '-' || c == '>' || c == '<' || 
         c == '.' || c == ',' || c == '[' || c == ']';
}

void extract_program(std::ifstream& ifs, std::string& program);
piter interpret(piter pc, piter const& end, memory& mem, diter& dp);

int main(int argc, char* argv[]){
  if(argc != 2)
    throw std::invalid_argument{ "use : ./exec file_name" };
  
  std::string prg{};
  try{
    std::ifstream ifs{ argv[1], std::ios::in };
    //warning ! remaining exception : std::string allocation (x2)
    if(!ifs) throw std::runtime_error{ std::string{ argv[1] } + " does not exists" };

    //at this point :
    // - ifs is valid
    extract_program(ifs, prg);
  } catch(std::runtime_error const& e){
     std::cerr<<e.what()<<std::endl;
     throw;
  } catch(std::exception const& e){
    std::cerr<<"program extraction failed"<<std::endl;
    std::cerr<<"reason : "<<e.what()<<std::endl;
    throw std::runtime_error{ "extraction failed" };
  }

  //at this point :
  // - prg is a pure BF program

  memory m;
  m.fill(0);
  diter begin_mem{ std::begin(m) };
  
  //at this point :
  // - m is a memory storage initialized to 0
  // - begin_mem is a valid iterator on m

  if(interpret(std::begin(prg), std::end(prg), m, begin_mem) != std::end(prg))
    throw std::runtime_error{ "incorrect brace balance (] without matching [)" };

  //at this point :
  // - program execution terminated
  // - m has been updated according to prg
  // - begin_mem is on the last memory cell reached

  return 0;
}

/*
  Pre  : - ifs valid
  Post : - prg is pure BF
         - ifs is not valid anymore
  Exceptions : - IO exceptions on getline (unlikely)
               - remove_if cannot raise exception here
               - clear is noexcept
               - resize should not allocate (size is inferior)
*/
void extract_program(std::ifstream& ifs, std::string& program){
  using std::begin;
  using std::end;

  program.clear();
  for(std::string line{}; getline(ifs, line); ) program += line;

  //we only keep BF instructions
  auto e = std::remove_if(begin(program), end(program), [](auto c){ return !is_an_inst(c); });

  //remove final moved characters
  program.resize(e - begin(program));
}

/*
  Pre : - start is a valid iterator on the first instruction after the [
          we want to match
        - pend is the end of the range where we want to search
  Post: no side-effect
  Returns: - an iterator on the matching ']'
           - start <= return < pend
  Exceptions: - runtime_error if no matching ']' is found
*/
inline piter find_closing(piter start, piter const& pend){
  if(start == pend)
    throw std::runtime_error{ "incorrect brace balance (] not found)" };

  unsigned eq{ 1 };
  while(*start != ']' || eq){
    ++start;
    if(start == pend)
      throw std::runtime_error{ "incorrect brace balance (] not found)" };

    if(*start == '[') ++eq;
    else if(*start == ']') --eq;
  }
  return start;
}

/*
  Pre: - pc is a valid iterator on the first instruction of the block to interpret
       - the pointed instruction sequence must be a pure BF program
       - pend is the past-the-end of the **program**
       - std::begin(mem) <= dp < std::end(mem)
  Post: - mem has been updated by the program
        - std::begin(mem) <= dp < std::end(mem)
  - dp is on the last memory cell reached
  Returns: a pointer to past-the-end of the block
           if the block is the program : pend
           otherwise an iterator to the final ']'*

     *Note : this case may happen if the program as a unmatched ']'
                   the return value must be controled
  Exception: runtime_error if the program is invalid
  Termination: may not terminate if the PF program is not terminating
*/
piter interpret(piter pc, piter const& pend, memory& mem, diter& dp){
  piter const begin_block{ pc };

  /*
    Invariant : begin_block <= pc <= pend
                std::begin(mem) <= dp < std::end(mem)
  */
  while(pc < pend){
    switch(*pc){
    case '+': (*dp)++; break;
    case '-': (*dp)--; break;
    case '>': ++dp;    break;
    case '<': --dp;    break;
    case '.': std::cout<<*dp; break;
    case ',': *dp = static_cast<char>(getchar()); break;
    case '[': pc = (*dp) ? interpret(std::next(pc), pend, mem, dp) : find_closing(pc, pend); break;
    case ']': if(*dp){ pc = begin_block; continue; } return pc;
    default : assert(false && "Something really bad happened");
    }
    if(dp == std::end(mem)) dp = std::begin(mem);

    //may be caused by interpret recursive call
    //signification : unmatched [
    if(pc == pend)
      throw std::runtime_error{ "incorrect brace balance (] not found)" };

    ++pc;
  }
  return pend;
}

J'ai une nouvelle fois détaillé à mort les contrats pour la compréhension du bousin et de sa validité.

Et au lieu de 34s sur mandelbrot, ça en prend 23, après pour aller plus vite, il faut passer par de la simplification tel qu'expliqué par @SpaceFox.

Voilou ^^ .

EDIT - Note : passer par un pré-calcul des branchements n'apporte rien ici. Si on veut pas exploser en mémoire, il faut passer par un conteneur associatif au minimum, parcourir la map n'est pas plus rapide que parcourir directement le programme (indirection powa), accéder à l'unordered_map n'apporte rien non plus (là je sais moins l'expliquer mais le hash est sûrement en cause). Il est également possible que je m'y prenne comme une grosse tâche.

Voici ma participation à ce sujet, avec mon interpréteur Brainfuck écrit en Vala. Ne vous attendez pas à des performances exceptionnelles par contre (notamment pour la fractale de Mandelbrot, le programme n'a pas fini), je ne l'ai pas spécialement étudié pour. Par contre, il y a pas mal de code annexe pour gérer le chargement du programme depuis l'entrée standard ou depuis un fichier avec un système d'options.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
/*
  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/>.
 */

namespace Valafuck
{
  public class Valafuck
  {
      private uint8[] memory;
      private uint16[] ip_stack;
      
      private uint8[] program;
      
      private uint16 mp;
      private uint16 ip;
      private uint8 ip_stack_index;
      
      private static string? filename = null;
      
      private const OptionEntry[] options = 
      {
          { "file", 'f', 0, OptionArg.FILENAME, ref filename, "File containing the program", "FILE..."},      
          { null }
      };
      
      public Valafuck ()
      {
          this.memory = new uint8[32768];
          this.ip_stack = new uint16[256];
          
          //Filling memory with zeroes
          for (int i = 0; i < this.memory.length; i++)
              this.memory[i] = 0;
      }
      
      public uint8[] read_file (string filename)
      {
          uint8[] data;
          try
          {
              File file = File.new_for_path (filename);
              FileInputStream fis = file.read ();
              
              //Getting file size
              int64 filesize = 0;
              fis.seek (0, SeekType.END);
              filesize = fis.tell ();
              fis.seek (0, SeekType.SET);
              
              data = new uint8[filesize];
              size_t bytes_read;
              fis.read_all (data, out bytes_read);
          }
          catch(Error e)
          {
              error ("%s", e.message);
          }
          
          return data;
      }
      
      public uint8[] read_stdin ()
      {
          print ("Enter your program below. Finish by typing Enter twice. \n\n");
          
          var program = new StringBuilder ();
          var buffer = new char[32768];
          
          while (true)
          {
              string read = stdin.gets (buffer);
              if (read != "\n")
                  program.append (read.strip ());
              else
                  break;
          }
          
          return program.data;
      }
      
      public void execute (string[] args)
      {
          try
          {
              var opt_context = new OptionContext ("Brainfuck parser");
              opt_context.set_help_enabled (true);
              opt_context.add_main_entries (Valafuck.options, null);
              opt_context.parse (ref args);
          }
          catch (OptionError e)
          {
              print ("Error: %s\n", e.message);
              print ("Run %s --help to see a full list of available options.\n", args[0]);
          }
          
          if (Valafuck.filename == null)
              this.program = read_stdin ();
          else
              this.program = read_file (Valafuck.filename);
          
          this.ip = 0;
          this.mp = 0;
          this.ip_stack_index = 255;
          while (this.ip < this.program.length)
          {
              this.exec_instruction (this.program[ip]);
              ip++;
          }
      }
      
      public void exec_instruction (uint8 inst)
      {
          switch (inst)
          {
              case '+':
                  this.memory[this.mp]++;
                  break;
              case '-':
                  this.memory[this.mp]--;
                  break;
              case '>':
                  this.mp++;
                  if (this.mp == this.memory.length)
                      this.mp = 0;
                  break;
              case '<':
                  if (this.mp > 0)
                      this.mp--;
                  else if (this.mp == 0)
                      this.mp = (uint16) (this.memory.length - 1);
                  break;
              case '[':
                  this.ip_stack_index++;
                  this.ip_stack[this.ip_stack_index] = this.ip;
                  break;
              case ']':
                  if (this.memory[this.mp] != 0)
                      this.ip = this.ip_stack[this.ip_stack_index];
                  else
                      this.ip_stack_index--;
                  break;
              case '.':
                  print ("%c", this.memory[this.mp]);
                  break;
              case ',':
                  this.memory[this.mp] = (uint8) stdin.getc ();
                  stdin.read_line ();
                  break;
          }
      }
      
      static int main (string[] args)
      {
          var valafuck = new Valafuck ();
          valafuck.execute (args);
          
          return 0;
      }
  }
}

Pour compiler tout ça (en assumant que le fichier du programme s'appelle valafuck.vala) :

1
valac --pkg gio-2.0 valafuck.vala

EDIT: J'en profite également pour vous poster un lien vers un interpréteur que j'avais codé en C pour un langage relativement similaire : le SNUSP. Voir l'interpréteur.

+0 -0

Bonsoir,

Ci-dessous, pas une mais deux implémentations d'un interpréteur de Brainfuck en C++. La première implémentation est minimaliste (~50 lignes de code) tandis que pour la seconde j'ai plus ou moins vainement essayé d'optimiser l'interpréteur au maximum en suivant les principes de SpaceFox.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iterator>
#include <string>
#include <stack>
#include <vector>
#include <array>
#include <map>
#include <cstdlib>
#include <cassert>

// Simple Brainfuck interpreter written in C++
template <typename BufferIterator, typename ProgramIterator>
// requires: 
// - BufferIterator is a bidirectionnal iterator type
// - ProgramIterator is a forward iterator type
void brainfuck(BufferIterator ptr, ProgramIterator first, ProgramIterator last) {
    // Preconditions:
    // - ptr points to a valid buffer location
    // - [first, last) is a valid range
    // - [first, last) is a valid brainfuck program that maintains the ptr validity (no check performed internaly)

    // Build the jump table
    auto  loop_begin   = std::stack<ProgramIterator>{};
    auto  mloop        = std::map<ProgramIterator, ProgramIterator>{};
    auto  it           = first;
    while(it != last) {
        if(*it == '[') {
            loop_begin.push(it);
        }
        else if(*it == ']') {
            mloop[it] = loop_begin.top();
            mloop[loop_begin.top()] = it;
            loop_begin.pop();
        }
        ++it;
    }
    
    // Execute the Brainfuck program
    while(first != last) {
        switch(*first) {
            case '+': ++(*ptr); break;
            case '-': --(*ptr); break;
            case '>': ++ptr; break;
            case '<': --ptr; break;
            case '.': std::cout << *ptr; break;
            case ',': std::cin >> *ptr; break;
            case '[': if(!*ptr) first = mloop[first]; break;
            case ']': if(*ptr) first = mloop[first]; break;
        }
        ++first;
    }
}

// Optimized Brainfuck interpreter 
enum op_type {
    PLUS = 0,
    MOVE = 2,
    ZERO = 4,
    OUT = 8,
    IN = 16,
    BEGIN = 32,
    END = 64,
  ADD = 128
};

struct op {
    op() = default;
    constexpr op(op_type type) : type(type), val(0), jump_dst(nullptr) {}
    op(op_type type, char val) : type(type), val(val),  jump_dst(nullptr) {}
    op(op_type type, op* jump_dst) : type(type), val(0),  jump_dst(jump_dst) {}
    op_type type;
    char val;
    op* jump_dst;
};

template <typename ProgramIterator>
char compress_val(ProgramIterator& first, ProgramIterator last, char value) {
    char count = 0;
    while(first != last && *first == value) {
        ++first;
        ++count;
    }
    --first;
    return count;
}

template <typename ProgramIterator1, typename ProgramIterator2>
ProgramIterator2 compress(ProgramIterator1 first, ProgramIterator1 last, ProgramIterator2 out) {
    while(first != last) {
        switch(*first) {
            case '+': *out++ = op(PLUS,  compress_val(first, last, *first)); break;
            case '-': *out++ = op(PLUS, -compress_val(first, last, *first)); break;
            case '>': *out++ = op(MOVE,  compress_val(first, last, *first)); break;
            case '<': *out++ = op(MOVE, -compress_val(first, last, *first)); break;
            case '.': *out++ = op{OUT}; break;
            case ',': *out++ = op{IN}; break;
            case '[': *out++ = op{BEGIN}; break;
            case ']': *out++ = op{END}; break;
        }
        ++first;
    }
  return out;
}

struct zero_matcher {
  template <typename ProgramIterator>
  bool operator()(ProgramIterator first, ProgramIterator) {
      ++first;
      return first->val == -1;
  }
  
  op value;
  const std::array<op, 3> pattern;
  zero_matcher() : value{ZERO}, pattern{op{BEGIN}, op{PLUS}, op{END}} 
  {}
};

struct add_matcher {
  template <typename ProgramIterator>
  bool operator()(ProgramIterator first, ProgramIterator) {
      ++first;
      char val = first++->val;
      value.val = first++->val;
      return (-val == first++->val && -value.val == first++->val);
  }
  
  op value;
  const std::array<op, 6> pattern;
  add_matcher() : value{ADD}, pattern{op{BEGIN}, op{PLUS}, op{MOVE}, op{PLUS}, op{MOVE}, op{END}} 
  {}
  
};

template <typename ProgramIterator, typename Matcher>
ProgramIterator replace_pattern(ProgramIterator first, ProgramIterator last, Matcher matcher) {
  ProgramIterator pos = first;
  while((pos = std::search(pos, last, std::begin(matcher.pattern), std::end(matcher.pattern), [](op a, op b) {return a.type == b.type;})) != last) {
      ProgramIterator pos_end = std::next(pos, std::distance(std::begin(matcher.pattern), std::end(matcher.pattern)));
      if(matcher(pos, pos_end)) {
          *pos = matcher.value;
          last = std::copy(pos_end, last, ++pos);
      }
      else {
          ++pos;
      }
  }
  return last;
}

template <typename ProgramIterator>
void make_jump_table(ProgramIterator first, ProgramIterator last) {
    auto  loop_begin   = std::stack<ProgramIterator>{};
    while(first != last) {
        if(first->type == BEGIN) {
            loop_begin.push(first);
        }
        else if(first->type == END) {
          assert(!loop_begin.empty());
            first->jump_dst = &*loop_begin.top();
            loop_begin.top()->jump_dst = &*first;
            loop_begin.pop();
        }
        ++first;
    }
}

template <typename BufferIterator, typename ProgramIterator>
// requires: 
// - BufferIterator is a bidirectionnal iterator type
// - ProgramIterator is a forward iterator type
void brainfuck_optimized(BufferIterator ptr, ProgramIterator first, ProgramIterator last) {
    // Preconditions:
    // - ptr points to a valid buffer location
    // - [first, last) is a valid range
    // - [first, last) is a valid brainfuck program that maintains the ptr validity (no check performed internaly)

  // Optimize the program
    std::vector<op> optimized(std::distance(first, last));
    optimized.erase(compress(first, last, std::begin(optimized)), std::end(optimized));
    optimized.erase(replace_pattern(std::begin(optimized), std::end(optimized), zero_matcher{}), std::end(optimized));
    optimized.erase(replace_pattern(std::begin(optimized), std::end(optimized), add_matcher{}), std::end(optimized));
  
    // Build the jump table
    make_jump_table(std::begin(optimized), std::end(optimized));
    
    // Execute the Brainfuck program
    auto inst = &*std::begin(optimized);
  auto end = &*std::end(optimized);
    while(inst != end) {
        switch(inst->type) {
            case PLUS: *ptr += inst->val; break;
            case MOVE: std::advance(ptr, inst->val); break;
            case ZERO: *ptr = 0; break;
            case ADD: 
              *std::next(ptr, inst->val) += *ptr;
              *ptr = 0;
              break;
            case OUT: std::cout << *ptr; break;
            case IN: std::cin >> *ptr; break;
            case BEGIN: if(!*ptr) inst = inst->jump_dst; break;
            case END: if(*ptr) inst = inst->jump_dst; break;
        }
        ++inst;
    }
}

int main(int argc, char* argv[])
{
    std::array<unsigned char, 30000> buffer{0};
  if(argc > 1) {
      char const* program_filename = argv[1];
      auto&& program_file = std::ifstream(program_filename);
      std::string program{std::istreambuf_iterator<char>(program_file), std::istreambuf_iterator<char>()};
      if(argc > 2) {
          brainfuck(std::begin(buffer), std::begin(program), std::end(program));
      }
      else {
          brainfuck_optimized(std::begin(buffer), std::begin(program), std::end(program));
      }
  }
  else {
      std::cout << "usage : " << argv[0] << " brainfuckprogramfile.bf [any_characher].\nIf 'any character' is present : use slow interpreter version." << std::endl;
  }
}

1
2
g++ -W -Wall -std=c++11 -O3 -pedantic brainfuck.cpp -o brainfuck.exe
brainfuck.exe mandelbrot.b

Par défaut la version optimisée de l'interpréteur est utilisée. En terme de performance, compter une dizaine de secondes pour mandelbrot et 2 secondes pour hanoi!

Je ne suis malheureusement pas parvenu à implémenter d'autres optimisation (multiplication et division en priorité). :(

Après coup il semblerait que la première de mes implémentation ressemble beaucoup à ce que propose Ksass`Peuk plus au sur cette page.

+0 -0

Intéressant, si l'implémentation est exactement la même, on peut s'amuser à faire un comparatif de performances entre Java et C++. Ici sous Linux, avec OpenJDK7 (la 8 est un poil plus rapide, IBM J9 v7 est sensiblement plus rapide) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
$time java -jar BrainfuckOptimized7.jar mandelbrot.b
real    0m20.360s
user    0m20.136s
sys 0m0.136s

$time ./brainfuck mandelbrot.b
real    0m5.546s
user    0m5.540s
sys 0m0.000s

$time java -jar BrainfuckOptimized7.jar hanoi.b 
real    0m2.781s
user    0m2.660s
sys     0m0.248s

$time ./brainfuck hanoi.b
real    0m0.413s
user    0m0.396s
sys 0m0.004s

On a donc un facteur 3.63 sur mandelbrot et 6.71 sur hanoi.

Je m'attendais à pire ; le programme des tours de Hanoï a en proportion beaucoup plus de sorties, je suppose que c'est ce qui explique la différence (afficher un caractère en C++ doit être sensiblement plus rapide qu'en Java).

Étant allergique au Java je n'avais pas ouvert ton code jusque là. :)

Après vérification, les correspondances des boucles sont implémentées avec un conteneur associatif chez moi, tandis que ton implémentation utilise deux tableaux ayant chacun la taille du programme.

Sinon, les trois patterns (reset, copie et addition) sont présents sous la même forme dans les deux implémentations. Les algorithmes pour reconnaitre ces patterns sont certainement différents mais l'exécution à proprement parler est nécessairement équivalente de ce côté là.

Sinon pour savoir si c'est l'affichage qui explique la différence il suffirait de retirer les '.' de ces deux programmes.

Me revoilà encore sur l'interpréteur Brainfuck, avec un nouvel interpréteur en Vala, mais cette fois-ci beaucoup plus dégueulasse.

Je me suis mis comme défi de réaliser un interpréteur Brainfuck snas utiliser aucune des instructions suivantes : if, else, do, while, for, foreach, switch (en gros, aucune structure de contrôle).

Voilà le code, qui utilise massivement l'optimisation d'expression (le truc qui fait que si la première partie d'un "&&" est FALSE, alors la deuxième n'est pas exécutée), pourrait être beaucoup plus court en C je pense, mais le compilateur Vala est un peu chiant, donc on doit passer par plusieurs détours pour arriver à ce que l'on veut. Niveau performance, j'ai absolument pas essayé mais ça doit être catastrophique, je suis déjà content qu'il exécute un additionneur sans se tromper.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
uint8[] program;
uint8[] memory;
uint16[] ip_stack;

uint16 mp = 0;
uint16 ip = 0;
uint8 ipsi = 0;
size_t psize;

bool die ()
{
    Process.exit (0);
    return true;
}

bool pci ()
{
    print ("%c", memory[mp]);
    return true;
}

bool gci ()
{
    memory[mp] = (uint8) stdin.getc ();
    stdin.read_line ();
    return true;
}

void exec ()
{
    bool r;
    r = ip >= program.length && die ();
    r = program[ip] == '+' && (memory[mp]++ == 0 || true);
    r = program[ip] == '-' && (memory[mp]-- == 0 || true);
    r = program[ip] == '>' && (mp++ == 0 || true);
    r = program[ip] == '<' && (mp-- == 0 || true);
    r = program[ip] == '.' && (pci ());
    r = program[ip] == ',' && (gci ());
    r = program[ip] == '[' && ((ip_stack[++ipsi] = ip) == 0 || true);
    r = program[ip] == ']' && ((memory[mp] != 0 && (ip = ip_stack[ipsi]) == 0) || (memory[mp] == 0 && (--ipsi == 0)));
    ip++;
    exec ();
}

int main (string[] args)
{
    memory = new uint8[32768];
    ip_stack = new uint16[256];
    
    File file = File.new_for_path (args[1]);
    FileInputStream fis = file.read ();

    //Getting file size
    int64 filesize = 0;
    fis.seek (0, SeekType.END);
    filesize = fis.tell ();
    fis.seek (0, SeekType.SET);

    program = new uint8[filesize];
    fis.read_all (program, out psize);
    
    exec ();
    return 0;
}

+0 -0

J'ai commencé à bosser sur un mode d'édition pour emacs permettant d'évaluer du bf. L'idée était surtout de voir comment modifier les menus et ouvrir de nouvelles fenêtres dans emacs. Le code est le suivant :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
(defvar brainfuck-mode-hook nil)

(defvar brainfuck-mode-map
  (let ((map (make-keymap)))
    (define-key map (kbd "C-c C-c") 'brainfuck-eval-line)
    (define-key map (kbd "C-c C-b") 'brainfuck-eval-buffer)
    (define-key map (kbd "C-c C-r") 'brainfuck-reset-machine)
    map)
  "Keymap for Brainfuck major mode")

(add-to-list 'auto-mode-alist '("\\.bf\\'" . brainfuck-mode))

(defconst brainfuck-font-lock-keywords nil)

;; Machine definition

(defvar brainfuck-memory nil)
(defvar brainfuck-pointer 0)
(defvar brainfuck-stack nil)

(defun brainfuck-reset-machine ()
  (interactive)
  (setq brainfuck-memory (make-vector 30000 0))
  (setq brainfuck-pointer 0)
  (setq brainfuck-stack nil))

;; Brainfuck evaluation

(defun brainfuck-display-output ()
  (let ((out-buf (get-buffer-create "*brainfuck-output*"))
  (out-win (display-buffer "*brainfuck-output*")))
    (select-window out-win)))

(defun brainfuck-change-value (new-value)
  (aset brainfuck-memory brainfuck-pointer new-value))

(defun brainfuck-stack-push (p)
  (setq brainfuck-stack (cons p brainfuck-stack)))

(defun brainfuck-stack-pop ()
  (setq brainfuck-stack (cdr brainfuck-stack)))

(defun brainfuck-stack-top ()
  (car brainfuck-stack))

(defun brainfuck-end-loop (code pc)
  (let ((origin pc))
    (setq pc (1+ pc))
    (while (not (and
       (= (elt code pc) ?\])
       (or (eq nil (brainfuck-stack-top))
           (eq origin (brainfuck-stack-top)))))
      (cond
       ((= ?\[ (elt code pc)) (brainfuck-stack-push pc))
       ((= ?\] (elt code pc)) (brainfuck-stack-pop))
       (t nil))
      (setq pc (1+ pc)))
    pc))

(defun brainfuck-eval-code (code)
  (interactive)
  (let ((pc 0))
    (while (> (string-width code) pc)
      (let ((inst (elt code pc))
      (curr (elt brainfuck-memory brainfuck-pointer)))
  (cond
   ((= ?\+ inst) (brainfuck-change-value (1+ curr)))
   ((= ?\- inst) (brainfuck-change-value (1- curr)))
   ((= ?\> inst) (setq brainfuck-pointer (1+ brainfuck-pointer)))
   ((= ?\< inst) (setq brainfuck-pointer (1- brainfuck-pointer)))
   ((= ?\. inst) (insert-char curr))
   ((= ?\! inst) (insert-string (int-to-string curr)))
   ((= ?\, inst) (brainfuck-change-value (read-char "Input: ")))
   ((= ?\? inst) (brainfuck-change-value (floor 
                      (string-to-number 
                      (read-string "Input: ")))))
   ((= ?\] inst) (if (= curr 0)
             (brainfuck-stack-pop)
           (setq pc (brainfuck-stack-top))))
   ((= ?\[ inst) (if (= curr 0)
             (setq pc (brainfuck-end-loop code pc))
           (brainfuck-stack-push pc)))
   (t nil))
  (setq pc (1+ pc)))))
  nil)

(defun brainfuck-eval (code)
  (interactive)
  (let ((sw (selected-window)))
    (brainfuck-display-output)
    (brainfuck-eval-code code)
    (select-window sw)))

(defun brainfuck-eval-line ()
  (interactive)
  (let ((code (buffer-substring-no-properties
         (line-beginning-position)
         (line-end-position))))
    (brainfuck-eval code)))

(defun brainfuck-eval-buffer ()
  (interactive)
  (let ((code (buffer-string)))
    (brainfuck-eval code)))

;; Menu bar
;; See : http://ergoemacs.org/emacs/elisp_menu.html
;; for more infos

(defun brainfuck-init-menu-bar ()
  (define-key-after
    global-map
    [menu-bar bf-menu]
    (cons "Brainfuck" (make-sparse-keymap "foo"))
    'tools)
  (define-key
    global-map
    [menu-bar bf-menu bf-rm]
    '("Reset Machine" . brainfuck-reset-machine))
    (define-key
    global-map
    [menu-bar bf-menu bf-eb]
    '("Eval Buffer" . brainfuck-eval-buffer))
  (define-key
    global-map
    [menu-bar bf-menu bf-el]
    '("Eval Line" . brainfuck-eval-line)))

(define-derived-mode brainfuck-mode fundamental-mode "Brainfuck"
  "Major mode for editing Brainfuck code."
  (set (make-local-variable 'font-lock-defaults) '(brainfuck-font-lock-keywords))
  (brainfuck-init-menu-bar)
  (brainfuck-reset-machine))

(provide 'brainfuck-mode)

Le mode est assez facile à utiliser (et s'active par défaut pour les fichiers d'extension .bf) :

  • C-c C-c pour évaluer la ligne.
  • C-c C-b pour évaluer le buffer.
  • C-c C-r pour reinitialiser la machine bf.

J'ai réussi à faire fonctionner ça plus ou moins bien (le hello world passe, ainsi que des programmes avec des boucles multiples), mais Mandelbrot n'affiche rien. J'imagine que j'ai dû me planter dans une condition d'arret de boucle, mais comme il est tard, je verrai ça demain (ou plus tard).

Bonjour,

Je vous propose une nouvelle version de mon interpréteur Brainfuck en C++. Je me suis efforcé d'optimiser au maximum les boucles les plus simples c'est à dire celles qui sont équilibrées (><), sans remise à zéro ([-]) de la case de départ et sans IN/OUT (.,).

Cela se révèle particulièrement payant pour Hanoi dont le temps d'exécution descend chez moi à 46 ms (si sortie redirigée vers un fichier, jusqu'à 900ms si sortie dans la console windows), ce qui correspond à un gain d'un facteur 10. Par contre, aucun effet (ou légèrement négatif) pour Mandelbrot, c'est assez triste vu les efforts déployés.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iterator>
#include <string>
#include <stack>
#include <vector>
#include <array>
#include <map>
#include <chrono>
#include <cstdlib>
#include <cassert>

// Simple Brainfuck interpreter written in C++
template <typename BufferIterator, typename ProgramIterator>
// requires: 
// - BufferIterator is a bidirectionnal iterator type
// - ProgramIterator is a forward iterator type
void brainfuck(BufferIterator ptr, ProgramIterator first, ProgramIterator last) {
    // Preconditions:
    // - ptr points to a valid buffer location
    // - [first, last) is a valid range
    // - [first, last) is a valid brainfuck program that maintains the ptr validity (no check performed internaly)

    // Build the jump table
    auto  loop_begin   = std::stack<ProgramIterator>{};
    auto  mloop        = std::map<ProgramIterator, ProgramIterator>{};
    auto  it           = first;
    while(it != last) {
        if(*it == '[') {
            loop_begin.push(it);
        }
        else if(*it == ']') {
            mloop[it] = loop_begin.top();
            mloop[loop_begin.top()] = it;
            loop_begin.pop();
        }
        ++it;
    }
    
    // Execute the Brainfuck program
    while(first != last) {
        switch(*first) {
            case '+': ++(*ptr); break;
            case '-': --(*ptr); break;
            case '>': ++ptr; break;
            case '<': --ptr; break;
            case '.': std::cout << *ptr; break;
            case ',': std::cin >> *ptr; break;
            case '[': if(!*ptr) first = mloop[first]; break;
            case ']': if(*ptr) first = mloop[first]; break;
        }
        ++first;
    }
}

// Optimized Brainfuck interpreter 
enum op_type {
    PLUS = 0,
    MOVE = 2,
    ZERO = 4,
    OUT = 8,
    IN = 16,
    BEGIN = 32,
    END = 64,
    ADDZ = 128,
    ADD = 256,
    MUL = 512,
    SET = 1024,
    IF = 2048,
};

struct op_val {
    int val;
    int mul;
};

struct op {
    op() = default;
    constexpr op(op_type type) : type(type), jump_dst{nullptr} {}
    op(op_type type, int val) : type(type), o{val, 0} {}
    op(op_type type, int val, int mod) : type(type), o{val, mod} {}
    op(op_type type, op* jump_dst) : type(type), jump_dst(jump_dst) {}
    op_type type;
    union {
        op_val o;
        op* jump_dst;
    };
};

template <typename ProgramIterator>
int compress_val(ProgramIterator& first, ProgramIterator last, char value) {
    int count = 0;
    while(first != last) {
        if(*first == value) {
            ++first;
            ++count;
        }
        else if(*first == '\n' || *first == '\r') {
            ++first;
        }
        else {
            break;
        }
    }
    return count;
}

template <typename ProgramIterator1, typename ProgramIterator2>
ProgramIterator2 compress(ProgramIterator1 first, ProgramIterator1 last, ProgramIterator2 out) {
    while(first != last) {
        switch(*first) {
            case '+': *out++ = op(PLUS,  compress_val(first, last, *first)); break;
            case '-': *out++ = op(PLUS, -compress_val(first, last, *first)); break;
            case '>': *out++ = op(MOVE,  compress_val(first, last, *first)); break;
            case '<': *out++ = op(MOVE, -compress_val(first, last, *first)); break;
            case '.': *out++ = op{OUT}; ++first; break;
            case ',': *out++ = op{IN}; ++first; break;
            case '[': *out++ = op{BEGIN}; ++first; break;
            case ']': *out++ = op{END}; ++first; break;
            default: ++first;
        }
    }
  return out;
}

struct zero_matcher {
  template <typename ProgramIterator>
  bool operator()(ProgramIterator first, ProgramIterator) {
      ++first;
      return first->o.val == -1 || first->o.val == 1;
  }
  
  op value;
  const std::array<op, 3> pattern;
  zero_matcher() : value{ZERO}, pattern{op{BEGIN}, op{PLUS}, op{END}} 
  {}
};

struct addz_matcher {
  template <typename ProgramIterator>
  bool operator()(ProgramIterator first, ProgramIterator) {
      ++first;
      int val = first++->o.val;
      value.o.val = first++->o.val;
      return (-val == first++->o.val && -value.o.val == first++->o.val);
  }
  
  op value;
  const std::array<op, 6> pattern;
  addz_matcher() : value{ADDZ}, pattern{op{BEGIN}, op{PLUS}, op{MOVE}, op{PLUS}, op{MOVE}, op{END}} 
  {}
  
};

template <typename ProgramIterator, typename Matcher>
ProgramIterator replace_pattern(ProgramIterator first, ProgramIterator last, Matcher matcher) {
  size_t pattern_lenght = std::distance(std::begin(matcher.pattern), std::end(matcher.pattern));
  while((first = std::search(first, last, std::begin(matcher.pattern), std::end(matcher.pattern), [](op a, op b) {return a.type == b.type;})) != last) {
      ProgramIterator pattern_end = std::next(first, pattern_lenght);
      if(matcher(first, pattern_end)) {
          *first = matcher.value;
          last = std::copy(pattern_end, last, ++first);
      }
      else {
          ++first;
      }
  }
  return last;
}

template <typename ProgramIterator>
ProgramIterator find_simple_loop(ProgramIterator first, ProgramIterator last) {
    while(first != last) {
        if(first->type == BEGIN) {
            ProgramIterator it = std::next(first, 1);
            int move_count = 0;
            while(it->type == MOVE || it->type == PLUS || it->type == ZERO) {
                if(it->type == MOVE) {
                    move_count += it->o.val;
                }
                ++it;
            }
            if(it->type == END && move_count == 0) {
                return first;
            }
            else {
                first = it;
                continue;
            }
        }
        ++first;
    }
    return last;
}

template <typename ProgramIterator>
std::pair<ProgramIterator, ProgramIterator> replace_simple_loop(ProgramIterator first, ProgramIterator last) {
    assert(first->type == BEGIN);
    ProgramIterator it = std::next(first, 1);
    int move_count = 0;
    std::vector<op> insts(1, op{IF});
    while(it->type != END) {
        if(it->type == MOVE) {
            move_count += it->o.val;
        }
        else {
            auto inst_it = std::find_if(insts.rbegin(), insts.rend(), [=](op const& i) {return i.o.val == move_count && i.type != IF;});
            switch(it->type) {
                case PLUS:
                    if(inst_it != insts.rend()) {
                        if(inst_it->type != SET) {
                            assert(inst_it->type == ADD);
                            inst_it->o.val = move_count;
                            inst_it->o.mul += it->o.val;
                            if(inst_it->o.mul == 1) {
                                inst_it->type = ADD;
                            }
                            else {
                                inst_it->type = MUL;
                            }
                        }
                        else {
                            assert(inst_it->o.val == move_count);
                            assert(inst_it->type == SET);
                            inst_it->o.mul += it->o.val;
                        }
                    }
                    else {
                        if(it->o.val == 1) {
                            insts.emplace_back(ADD, move_count);
                        }
                        else {
                            insts.emplace_back(MUL, move_count, it->o.val);
                        }
                    }
                    break;
                case ZERO:
                    if(!move_count) {
                        return {++first, last};
                    }
                    if(inst_it != insts.rend()) {
                        inst_it->type = SET;
                        inst_it->o.val = move_count;
                        inst_it->o.mul = 0;
                    }
                    else {
                        insts.emplace_back(SET, move_count, 0);
                    }
            
                    break;
                default:
                    assert(0);
            }
        }
        ++it;
    }
    assert(!move_count);
    auto base = std::find_if(std::begin(insts), std::end(insts), [](op const& i) {return (i.o.val == 0 && ((i.type == MUL && i.o.mul == -1)));});
    if(insts.size() < 2 || base == std::end(insts) || (base->type == MUL && base->o.mul != -1)) {
        return {++first, last};
    }
    
    auto other = std::find_if(std::next(base, 1), std::end(insts), [](op const& i) {return (i.o.val == 0 && (i.type == MUL) && i.o.mul == -1);});
    if(other != std::end(insts)) {
        return {++first, last};
    }
    insts.erase(base);

    auto ifstart = first;
    first = std::copy(std::begin(insts), std::end(insts), first);
    *first = op{ZERO};
    assert(ifstart->type == IF);
    ifstart->jump_dst = &*first;
    last = std::copy(++it, last, ++first);
    return {first, last};
}

template <typename ProgramIterator>
ProgramIterator replace_simple_loops(ProgramIterator first, ProgramIterator last) {
    while((first = find_simple_loop(first, last)) != last) {
        std::tie(first, last) = replace_simple_loop(first, last);
    }
    return last;
}

template <typename ProgramIterator>
void make_jump_table(ProgramIterator first, ProgramIterator last) {
    auto  loop_begin   = std::stack<ProgramIterator>{};
    while(first != last) {
        if(first->type == BEGIN) {
            loop_begin.push(first);
        }
        else if(first->type == END) {
            assert(!loop_begin.empty());
            first->jump_dst = &*loop_begin.top();
            loop_begin.top()->jump_dst = &*first;
            loop_begin.pop();
        }
        ++first;
    }
}

template <typename BufferIterator, typename ProgramIterator>
// requires: 
// - BufferIterator is a bidirectionnal iterator type
// - ProgramIterator is a forward iterator type
void brainfuck_optimized(BufferIterator ptr, ProgramIterator first, ProgramIterator last) {
    // Preconditions:
    // - ptr points to a valid buffer location
    // - [first, last) is a valid range
    // - [first, last) is a valid brainfuck program that maintains the ptr validity (no check performed internaly)

    // Optimize the program
    std::vector<op> optimized(std::distance(first, last));
    optimized.erase(compress(first, last, std::begin(optimized)), std::end(optimized));
    optimized.erase(replace_pattern(std::begin(optimized), std::end(optimized), zero_matcher{}), std::end(optimized));
    optimized.erase(replace_pattern(std::begin(optimized), std::end(optimized), addz_matcher{}), std::end(optimized));
    optimized.erase(replace_simple_loops(std::begin(optimized), std::end(optimized)), std::end(optimized));

    // Build the jump table
    make_jump_table(std::begin(optimized), std::end(optimized));
    
    // Execute the Brainfuck program
    auto inst = &*std::begin(optimized);
    auto end = &*std::end(optimized);
    while(inst != end) {
        switch(inst->type) {
            case PLUS: *ptr += inst->o.val; break;
            case MOVE: std::advance(ptr, inst->o.val); break;
            case ZERO: *ptr = 0; break;
            case ADDZ: 
                *std::next(ptr, inst->o.val) += *ptr;
                *ptr = 0;
                break;
            case ADD: 
                *std::next(ptr, inst->o.val) += *ptr;    
                break;
            case MUL:
                *std::next(ptr, inst->o.val) += (inst->o.mul * *ptr);
                break;
            case SET:
                *std::next(ptr, inst->o.val) = inst->o.mul;
                break;
            case OUT: 
                std::cout << *ptr; break;
            case IN: std::cin >> *ptr; break;
            case BEGIN: if(!*ptr) inst = inst->jump_dst; break;
            case END: if(*ptr) inst = inst->jump_dst; break;
            case IF: if(!*ptr) inst = inst->jump_dst; break;
            default:assert(0);
        }
        ++inst;
    }
}

// easily-measure-elapsed-time: http://stackoverflow.com/questions/2808398/easily-measure-elapsed-time
template<typename TimeT = std::chrono::milliseconds>
struct measure
{
    template<typename F, typename ...Args>
    static typename TimeT::rep execution(F func, Args&&... args)
    {
        auto start = std::chrono::system_clock::now();

        // Now call the function with all the parameters you need.
        func(std::forward<Args>(args)...);

        auto duration = std::chrono::duration_cast< TimeT> 
                            (std::chrono::system_clock::now() - start);

        return duration.count();
    }
};

int main(int argc, char* argv[])
{
    std::cout << measure<>::execution([&]() {  
        std::array<unsigned char, 30000> buffer;
        std::fill(std::begin(buffer), std::end(buffer), 0);
        if(argc > 1) {
            char const* program_filename = argv[1];
            auto&& program_file = std::ifstream(program_filename);
            std::string program{std::istreambuf_iterator<char>(program_file), std::istreambuf_iterator<char>()};
            if(argc > 2) {
                brainfuck(std::begin(buffer), std::begin(program), std::end(program));
            }
            else {
                brainfuck_optimized(std::begin(buffer), std::begin(program), std::end(program));
            }
        }
        else {
            std::cout << "usage : " << argv[0] << " brainfuckprogramfile.bf [any_characher].\nIf 'any character' is present : use slow interpreter version." << std::endl;
        }
        std::cout << "\n";
    }) << " ms" << std::endl;
}

Cette fois ci il faut compiler avec -std=c++1y: Toujours à compiler en C++11 avec -std=c++11

1
2
g++ -W -Wall -std=c++11 -O3 -pedantic brainfuck.cpp -o brainfuck
.\brainfuck mandelbrot.b
+0 -0

Oui effectivement, passer au C++14 juste pour ça, c'est un peu dommage. J'ai été emporté par la frénésie de l'annonce du C++14 DIS (dernière étape avant l'officialisation l'impression du nouveau standard). J'ai légèrement modifié le code pour qu'il reste en C++11.

Hello,

j'avais un peu de temps libre, alors j'ai codé un interpréteur en Lua. Il n'y a aucune optimisation et le seul prétraitement du code est de constituer une table des positions des crochets. Les exemples fonctionnent (mais évidemment, comme il n'y a rien d'optimisé, Mandelbrot prend un bon moment ^^ ).

Je voulais faire le code le plus simple possible, et du coup j'ai construit une table qui permet d'interpréter le code Brainfuck en assimilant chaque instruction à un pointeur sur fonction (les commentaires étant liés à une fonction neutre grâce à la métatable).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
bf={ptr = 1,
    pos = 0,
    code = '',
    ['>'] = function () bf.ptr = bf.ptr+1 end,
    ['<'] = function () bf.ptr = bf.ptr-1 end,
    ['+'] = function () bf[bf.ptr] = bf[bf.ptr]+1 end,
    ['-'] = function () bf[bf.ptr] = bf[bf.ptr]-1 end,
    ['.'] = function () io.write(string.char(bf[bf.ptr])) end,
    [','] = function () bf[bf.ptr] = string.byte(io.read()) end,
    ['['] = function () if bf[bf.ptr]==0 then bf.pos=bf.lEnd[bf.pos] end end;
    [']'] = function () if bf[bf.ptr]~=0 then bf.pos=bf.lBeg[bf.pos] end end;

    setCode = function (userCode)
        bf.code = userCode
        local posOp = {}
        bf.lEnd = {}
        bf.lBeg = {}
        for i = 1, #bf.code do
            c = bf.code:sub(i,i)
            if c=='[' then posOp[1+#posOp]=i
            elseif c==']' then
                if #posOp == 0 then error('Missing [')
                else
                    bf.lEnd[posOp[#posOp]] = i
                    bf.lBeg[i] = posOp[#posOp]
                    posOp[#posOp] = nil
                end
            end
        end
        if #posOp~=0 then error('Missing ]') end
    end,

    execute = function () 
        while bf.pos<=#bf.code do
            bf.pos = bf.pos+1
            bf[bf.code:sub(bf.pos, bf.pos)]()
        end
    end,}

setmetatable(bf, {__index = function (t, k)
        return type(k)=='string' and function () end or 0
    end})

local file = arg[1]
local code = [[++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>
               ++.<<+++++++++++++++.>.+++.------.--------.>+.>.]]
if file then
    local f = io.open(file, "r")
    code = f:read("*all")
    f:close()
end
bf.setCode(code)
bf.execute()

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte