Créer un compilateur/interpréteur Brainfuck

Tous langages

a marqué ce sujet comme résolu.

Reprise du dernier message de la page précédente

Cette réponse a aidé l’auteur du sujet

On peut voir Brainfuck comme un jeu d'instructions d'un processeur. Et comme je n'ai plus de quoi programmer en VHDL sous la main (et que de toutes façons je ne sais plus faire), j'ai décidé de faire autrement.

J'ai décidé de simuler un processeur. Objet. En Java.

Eh bien croyez-le ou non, ça marche. C'est complètement inefficace, mais ça marche… J'arrive même à sortir la fractale !

 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
AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDEGFFEEEEDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS  X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY   ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ         UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP           KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR        VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK   MKJIJO  N R  X      YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O    TN S                       NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN                                 Q     UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT                                     [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU                                     QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN                                            JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR                                           UQ L HFEDDDDCCCCCCCCCCCCCCBB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR                                               YNHFEDDDDDCCCCCCCCCCCCCBB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU  O O   PR LLJJJKL                                                OIHFFEDDDDDCCCCCCCCCCCCCCB
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR              RMLMN                                                 NTFEEDDDDDDCCCCCCCCCCCCCB
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ                QPR                                                NJGFEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ                   VX                                                 HFFEEDDDDDDCCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS                                                                      HGFEEEDDDDDDCCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY                                                                        TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
A                                                                                                 PLJHGGFFEEEDDDDDDDCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY                                                                        TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS                                                                      HGFEEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ                   VX                                                 HFFEEDDDDDDCCCCCCCCCCCCCC
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ                QPR                                                NJGFEEDDDDDDCCCCCCCCCCCCCC
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR              RMLMN                                                 NTFEEDDDDDDCCCCCCCCCCCCCB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU  O O   PR LLJJJKL                                                OIHFFEDDDDDCCCCCCCCCCCCCCB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR                                               YNHFEDDDDDCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR                                           UQ L HFEDDDDCCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN                                            JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU                                     QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT                                     [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN                                 Q     UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O    TN S                       NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK   MKJIJO  N R  X      YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR        VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP           KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ         UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY   ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS  X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB


399396 ms

Bon OK, il lui faut quand même plus de 6 minutes 30… par contre, il ne prends que 15 Mo de RAM.

Comme du coup il y a beaucoup de classes (la plupart ne font à peu près rien), je vous ai mis le code ici : https://github.com/SpaceFox/brainfuck-vm/

À quoi sert ton truc ?

A rien. J'avais envie de m'amuser :D

Le programme fonctionne comme un processeur :

  • On crée un processeur, avec un jeu d'instructions défini (chacune d'entre elles est une classe)
  • On crée 2 mémoires (Brainfuck est une machine de Harvard)
  • On charge le programme dans la mémoire programme, qui est donc représenté par une suite d'instructions
  • On crée deux registres : le pointeur-mémoire et le pointeur-programme, tous deux initialisés à 0
  • On exécute l'instruction courante, puis on incrémente le pointeur-mémoire, jusqu'à arriver au bout de la mémoire-programme
  • Chaque instruction peut modifier l'état des registres ou des mémoires

Le programme est fonctionnel mais crade : programme en dur dans la classe CLI, aucun commentaire (cela dit, ils ne devraient pas être très importants pour commencer, il faut juste savoir qu'on part de la classe nommée CLI.java), classes limitées aux concepts réellement utilisés, etc.

J'avais une version super-optimisée en Java aussi, que j'avais fait pour ce même topic sur le SdZ. Si je la retrouve, je vous la poste et on verra la différence de perfs :D

Bonsoir,

Autrement, quelqu'un a déjà tenté le compilateur inverse ? Je veux dire, générer le BrainFuck correspondant à un code écrit en Pascal (ou autre langage relativement simple) ?

Ça ne correspond pas exactement à ce que tu décris, mais j'ai une fois utilisé un algorithme génétique pour générer du BF, c'était foireux, mais j'arrivais à générer un code qui affichait "Salut !" en assez peu de temps. Ma plus grande réussite, générer le code suivant en BF :

1
2
scanf("%d %d", &a, &b);
printf("%d %d", a, b);

Ce qui n'est pas si évident que ça en fin de compte.

Je me garde de vous montrer mon code (en rust), cette chose étant une abommination truffée de multiples et obscurs hacks. Si j'ai la motivation de 1. mettre à jour le code avec la dernière version de Rust 2. le nettoyer…

:)

P.S : lesmon, tu es fou. Dinosaure, tu es génial.

Edit : Ne parlons pas de SpaceFox.

Édité par paraze

+0 -0

Cette réponse a aidé l’auteur du sujet

Ma version en C++

 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
#include <fstream>
#include <array>
#include <stack>
#include <vector>
#include <cstdint>
#include <cstdio>

int main(int argc, char** argv)
{
    if(argc != 2)
    {
        return 0;
    }
    
    std::vector<char> program;
    unsigned int progPtr = 0;
    std::array<uint8_t, 30000> memory;
    memory.fill(0);
    unsigned int pointer = 0;
    std::stack<unsigned int> loops;
    
    std::ifstream file(argv[1]);
    while(!file.eof())
    {
        program.push_back(file.get());
    }
    file.close();
    
    while(progPtr < program.size())
    {
        char c = program[progPtr++];
        
        switch(c)
        {
            case '+':
                memory[pointer]++;
                break;
            case '-':
                memory[pointer]--;
                break;
            case '<':
                pointer--;
                if(pointer < 0)
                    pointer += 30000;
                break;
            case '>':
                pointer = (pointer + 1) % 30000;
                break;
            case '[':
                if(memory[pointer] == 0)
                {
                    int counter = 1;
                    while(counter > 0)
                    {
                        c = program[progPtr++];
                        if(c == '[')
                            counter++;
                        else if(c == ']')
                            counter--;
                    }
                }
                else
                {
                    loops.push(progPtr);
                }
                break;
            case ']':
                if(memory[pointer] == 0)
                {
                    loops.pop();
                }
                else
                {
                    progPtr = loops.top();
                }
                break;
            case '.':
                std::putchar(memory[pointer]);
                break;
            case ',':
                memory[pointer] = std::getchar();
                break;
            default:
                /* comment */;
        }
    }
    
    return 0;
}

Édité par minirop

+0 -0

Cette réponse a aidé l’auteur du sujet

Voici mon code complet, gérant les boucles. Comme annoncé, j’ai dû reprendre en profondeur la structure du programme. L’interpréteur utilise son ruban de données en entrelaçant, dans cet ordre :

  • un ruban contenant le code,
  • un ruban de « circulation » permettant de passer du code aux données et vice-versa (un va-et-vient incessant qui plombe sérieusement les performances),
  • un ruban temporaire,
  • et le ruban de données du programme interprété.

Comme les spécifications du Brainfuck sont très flottantes, les miennes figurent dans le code source.

L’interpréteur fonctionne sur des exemples comme le « Hello world », mais pas avec ceux de ctcp et Alex qui affichent des listes de carrés. Je ne sais vraiment pas d’où vient le problème, ayant vérifié tout le code et celui-ci marchant pour d’autre exemples avec boucles (y-compris imbriquées).

  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
#!/chemin/vers/un/interpréteur/brainfuck

________________________________________________________________________________

This is a Brainfuck interpreter written in Brainfuck⋅

Thus it requires a Brainfuck implementation to be run correctly⋅

The following assumptions are made on the Brainfuck implementation used
to run this interpreter:
  — the tape does not wrap and is initialized with zeros;
  — either negative numbers or integer wrapping is supported;
  — EOF is traduced by either −1 or the “no change” policy⋅

The specifications of the interpreted language are drawn from those of the
implementation running this interpreter; with the following alterations:
  — the tape memory is a quarter of that of this interpreter;
  — there shall be less instructions than a quarter of the number of cells
    in the interpreter’s tape;
  — there shall be less nested loops than the maximal value of a cell;
  — EOF is traduced by −1;
  — the source code follows an ASCII‐compatible charset;
  — each opening bracket must match a single closing bracket; otherwise
    an error “out of tape” will be issued if the implementation running
    this interpreter produces this kind of errors⋅
________________________________________________________________________________


structure of the tape: ( code | ptr | tmp | data )*

codes:
  −1 = “marked” rbracket (ie⋅ which has to be translated back to code 2)
   0 = end or “active” lbracket (ie⋅ beginning of a loop currently being executed)
   1 = lbracket
   2 = rbracket
   3 = rmove
   4 = lmove
   5 = dot
   6 = minus
   7 = comma
   8 = plus

LEXING

>>>>
>
-,+[-
  <+>
  >+++++++++++++[-<------->]< (91 decrementations)
  [<+> :not a lbracket
      --
      [<+> :not a rbracket
          >++++++[-<+++++>]<+ (31 incrementations)
          [<+> :not a rmove
              ++
              [<+> :not a lmove
                  ++++++++++++++
                  [<+> :not a dot
                      +
                      [<+> :not a minus
                          +
                          [<+> :not a comma
                              +
                              [<[-]> :not a plus (ie⋅ nothing)
                                  [-]<<<<
                              ]
                          ]
                      ]
                  ]
              ]
          ]
      ]
  ]
  >>>>
-,+]

rewind:
<
<<<<[<<<<]
init first cells:
+ > 0 > 0 > 0 >
_ > +

PARSING

<
[
switch instruction code:
  
“marked” rbracket?
  +
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      <+++> :set code 2 (accounting for the current parsing state)
  -]+<
  
lbracket?
  --
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
      ->+>
      [<-]<[<]> (test data=0 in tmp with ptr=0)
      <+
      {>[->>>>+<<<<]<}>>>>[[{>[->>>>+<<<<]<}>>>>]{>[->>>>+<<<<]<}>>>>]
      {>[-<<<<+>>>>]<}<<<<[{>[-<<<<+>>>>]<}<<<<]{>[->>>>+<<<<]<}>>>>-
      [+{>[-<<<<+>>>>]<}<<<<{>[-<<<<+>>>>]<}<<<<-]+ (switch position & transfer tmp)
      if data was =0:
      >[-
          <<+>> :restore code 1 for the lbracket
          + :init the nested loops counter (stored in tmp) to 1
          jump to the matching rbracket:
          [
              [->>>>+<<<<] :transfer counter
              <
              >>>>[<<<<->>>>-]+ (move right)
              >
              +<-<             :ptr=0 & counter augmented by 1
              if code≠1 → decrement counter:
              -[>>-<]>[<]<
              >>-<<            :counter restored
              if code≠2 → increment counter:
              -[>>+<]>[<]<
              ++
              >+>              :ptr=1
          ]
          <<---->> :set code −1 for a marked rbracket (accounting for the
                    current parsing state); this prevents the rbracket from
                    being evaluated during this very parsing loop 
      <->]<
      else:
      [
          <-> :mark the lbracket as active
      -]+
  -]+<
  
rbracket?
  -
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
      ->+>
      [<-]<[<]> (test data=0 in tmp with ptr=0)
      <+
      {>[->>>>+<<<<]<}>>>>[[{>[->>>>+<<<<]<}>>>>]{>[->>>>+<<<<]<}>>>>]
      {>[-<<<<+>>>>]<}<<<<[{>[-<<<<+>>>>]<}<<<<]{>[->>>>+<<<<]<}>>>>-
      [+{>[-<<<<+>>>>]<}<<<<{>[-<<<<+>>>>]<}<<<<-]+ (switch position & transfer tmp)
      if data was =0:
      >[-
          <<
          - :mark the current rbracket to jump back to it
          jump to the last active lbracket:
          [
              >
              <<<<[>>>>-<<<<-]+ (move left)
              <
          ]
          + :set code 1 for a normal lbracket
          jump back to the rbracket:
          +[-
              >
              >>>>[<<<<->>>>-]+ (move right)
              <
          +]
          >>
      <->]<
      else:
      [
          <
          ++ :restore code 2 for the rbracket
          jump to the last active lbracket:
          [
              >
              <<<<[>>>>-<<<<-]+ (move left)
              <
          ]
          -- :account for the current parsing state in the lbracket’s code
          >
      -]+
  -]+<
  
rmove?
  -
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
      >>>>[<<<<->>>>-]+ (move right)
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
  -]+<
  
lmove?
  -
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
      <<<<[>>>>-<<<<-]+ (move left)
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
  -]+<
  
dot?
  -
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
      >>.<<
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
  -]+<
  
minus?
  -
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
      >>-<<
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
  -]+<
  
comma?
  -
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
      >>[-]-,<< :enforce −1 for EOF
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
  -]+<
  
plus?
  -
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
      >>+<<
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
  -]+<
  
  ++++++++
  >
  >>>>[<<<<->>>>-]+ (move right)
  <
]


@ lesmon,

Oui oui, en TI-BASIC.

C’est une excellente idée. Interpréter du Brainfuck avec du TI-Basic (soit un langage presque aussi pourri), j’aime. :D En fait, en oubliant les langages ésotériques, le TI-Basic est le plus proche du Brainfuck que je voie (même en assembleur, on peut appeler des fonctions…).

Étant donné que les caractères en nombre, ça n'existe pas vraiment sur une calculatrice, à la place, la liste L1 fait office d'entrée standard.

Il est possible de convertir un caractère en nombre, et réciproquement. C’est même toi qui choisit les codes des caractères, du coup tu peux prendre l’ASCII au lieu de la page de code bizarre de la calculatrice !

D'ailleurs, si vous avez d'autres micro-optimisations, je suis preneur.

  • Les lignes 7-8, 9-10, 26-27 et 35-36 se condensent avantageusement en une seule à chaque fois.
  • La variable Ans rend souvent des services appréciables, par exemple lignes 25-27 et 34-36.
  • 0= se remplace par not(.

;)

Testé sur ma feu TI-82 Stat et fonctionnel.

Comment as-tu fait avec une calculatrice DCD ?

écrire français sous Windows : fr-oss (azerty++) ou bépo (étudié pour le français) | <insérer un truc spirituel ici>

+4 -0

le TI-Basic est le plus proche du Brainfuck que je voie (même en assembleur, on peut appeler des fonctions…).

Ah non ! On peut tout de même appeler des sous-programmes en TI-BASIC.

C’est même toi qui choisit les codes des caractères, du coup tu peux prendre l’ASCII au lieu de la page de code bizarre de la calculatrice !

Après, ça prend beaucoup trop de place dans le programme, et puis, manipuler directement des nombres, c'est plus marrant :°

  • Les lignes 7-8, 9-10, 26-27 et 35-36 se condensent avantageusement en une seule à chaque fois.

Mince, je me demande encore comment j'ai fait pour passer à côté.

  • La variable Ans rend souvent des services appréciables, par exemple lignes 25-27 et 34-36.

Ben du coup, oui, ça devient pratique.

  • 0= se remplace par not(.

J'ai toujours pensé que 0= me fait économiser un octet par rapport à not(…j'avais tort.

Comment as-tu fait avec une calculatrice DCD ?

J'ai changé les piles.


Merci encore :)

+0 -0

Cette réponse a aidé l’auteur du sujet

J'ai codé ma petite implémentation rapide (non optimisée et code fait à la va-vite). Il se peut qu'il y ait des bugs… (si vous pouviez me les signaler, merci).

J'ai défini un petit langage (appelé LBL (langage Brainfuck lisible)) où chaque instruction Brainfuck est traduit par un mot. C'est plus simple à lire ; ce langage a aussi quelques autres améliorations. Il peut ensuite être compilé en Brainfuck, qui est ensuite lui-même compilé par mon compilateur Brainfuck écrit en C++. Il est assez performant et peut afficher un ensemble de Mandelbrot en une dizaine de secondes…

Ceci est en quelque sorte une version bêta. Je pense après l'améliorer, donc si vous trouvez des bugs ou avez des idées d'améliorations, je suis preneur…

Voici le code en C++ multiplateforme (nécessite d'être compilé => qt5.3.1 avec mingw ou g++) : https://drive.google.com/file/d/0B5eGJmWOd6U2N2w5Rk5seXJnVGc/edit?usp=sharing

Un petit screen :

Image utilisateur

"Easy is right. Begin right and you are easy. Continue easy and you are right. The right way to go easy Is to forget the right way And forget that the going is easy." Chuang Tzu

+0 -0

Cette réponse a aidé l’auteur du sujet

Pour commencer, quelques programmes en Brainfuck : http://esoteric.sange.fi/brainfuck/bf-source/prog/

J'avais une version super-optimisée en Java aussi, que j'avais fait pour ce même topic sur le SdZ. Si je la retrouve, je vous la poste et on verra la différence de perfs :D

SpaceFox

Chose, promise, chose due ! J'ai retrouvé cette version, que je vous livre à l'identique, sans retouche aucune :

  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
package info.kisai.brainfuck;

import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

/**
 * Interpréteur BrainFuck
 * @author SpaceFox
 */
public class BrainFuck {

  // Paramètres de la machine
  private int tailleMemoire;
  private int tailleValeur;

  // Variables
  private char[] programme;
  private StringBuilder sortie = new StringBuilder();
  private char[] memoireTab;
  private int pointeurMaxMemoire;

  private char[] programmeCompile;
  private int[] parametresCompile;

  /**
   * Constructeur unique.<br/>
   * Initialise la mémoire et les tailles maximales.
   * @param tailleMemoire la taille max de la mémoire, en cases. Aucune taille max si <code>null</code>.
   * @param tailleValeur la taille max d'une case. Aucune taille max si <code>null</code>.
   */
  public BrainFuck(Integer tailleMemoire, Integer tailleValeur) {
      if (tailleMemoire == null) {
          this.tailleMemoire = Integer.MAX_VALUE;
          initMemoire(30000); // Purement arbitraire, sera augmenté si besoin
      } else {
          this.tailleMemoire = tailleMemoire;
          initMemoire(tailleMemoire);
      }

      if (tailleValeur == null) {
          this.tailleValeur = Character.MAX_VALUE;
      } else {
          this.tailleValeur = tailleValeur;
      }
  }

  public void setProgramme(char[] programme) {
      this.programme = programme;
  }

  public void setProgramme(String programme) {
      setProgramme(programme.toCharArray());
  }

  /**
   * Pour debug. Utile pour les versions étendues (verif de la transformation).
   * @return le programme en brainfuck.
   */
  public String getProgramme() {
      return String.valueOf(programme);
  }

  /**
   * Exécute le programme et renvoie le résultat sous forme de chaîne. Les entrées sont lues sur l'entrée passée en
   * paramètre.
   * @param entreeStream un flux d'entrée quelconque.
   * @return le résultat du programme.
   */
  public String execute(InputStream entreeStream) {

        compile();

      int longueurProgramme = programmeCompile.length;
      int iInstruction = 0;
      int pointeur = 0;
        do {
          switch (programmeCompile[iInstruction]) {
              case '+':
              case '-':
                  memoireTab[pointeur] = incrementeMemoire(pointeur, parametresCompile[iInstruction]);
                  break;
              case '>':
              case '<':
                  pointeur = incrementePointeur(pointeur, parametresCompile[iInstruction]);
                  break;
              case '0':
                  resetMemoire(pointeur);
                  break;
              case 'a':
                  addition(pointeur);
                  break;
              case 'm':
                  copie(pointeur);
                  break;
              case '.':
//                    sortie.append(getMemoireAt(pointeur));
                  System.out.print(getMemoireAt(pointeur));
                  break;
              case ',':
                  memoireTab[pointeur] = litEntree(entreeStream);
                  break;
              case '[':
                  iInstruction = sautConditionnelComp(iInstruction, pointeur);
                  break;
              case ']':
                  iInstruction = retourConditionnelComp(iInstruction, pointeur);
                  break;
              default:
                  // Autres cas --> ignorés (commentaires)
                  break;
          }
          // Pour debug
//            System.out.println(
//                    "   instruction n°" + iInstruction
//                + " " + programmeCompile[iInstruction]
//                + " (" + parametresCompile[iInstruction]
//                + ") ==> pointeur " + pointeur
//                + " --> valeur " + Integer.valueOf(memoireTab[pointeur]));

          iInstruction++;
      } while (iInstruction < longueurProgramme);

      return sortie.toString();
  }


  private void compile() {

      char[] progSansComm = preProcesseur(supprimeCommentaires());

      final int tailleProg = progSansComm.length;
      char[] progTmp = new char[tailleProg];
      int[] paramTmp = new int[tailleProg];

      // Compilation
      int iProg = 0;
      int tailleProgComp = 0;
      int compteur = 0;
      char instr;
      char instrPrec = '\u0000';

      while (iProg < tailleProg) {

          instr = progSansComm[iProg];

          // Instructions cumulables
          if (    (instr != instrPrec)
              &&  (instrPrec == '+' || instrPrec == '-' || instrPrec == '>' || instrPrec == '<')
          ) {
              progTmp[tailleProgComp] = instrPrec;
              paramTmp[tailleProgComp] = compteur;
              tailleProgComp++;
              compteur = 0;
          }

          // Instructions à ajouter direct
          if (    instr == '['|| instr == ']' || instr == '.' || instr == ','
              ||  instr == '0' || instr == 'a' || instr == 'm') {
              progTmp[tailleProgComp] = instr;
              tailleProgComp++;
              compteur = 0;
          }

          // Modif du compteur si besoin
          if (instr == '+' || instr == '>') {
              compteur++;
          }
          else if (instr == '-' || instr == '<') {
              compteur--;
          }
          instrPrec = instr;
          iProg++;
      }

      // Correspondances
      for (int iCrochetOuvrant = 0; iCrochetOuvrant < tailleProgComp; iCrochetOuvrant++) {
          if (progTmp[iCrochetOuvrant] == '[') {
              int nbCrochets = 1;
              int iCrochetFermant = iCrochetOuvrant;
              while (nbCrochets > 0) {
                  iCrochetFermant++;
                  if (progTmp[iCrochetFermant] == '[') {
                      nbCrochets++;
                  } else if(progTmp[iCrochetFermant] == ']') {
                      nbCrochets--;
                  }
              }
              // Correspondance [ --> ]
              paramTmp[iCrochetOuvrant] = iCrochetFermant;
              // Correspondance ] --> [
              paramTmp[iCrochetFermant] = iCrochetOuvrant;
          }
      }

      // Copie dans les tableaux généraux
      programmeCompile = new char[tailleProgComp];
      parametresCompile = new int[tailleProgComp];
      System.arraycopy(progTmp, 0, programmeCompile, 0, tailleProgComp);
      System.arraycopy(paramTmp, 0, parametresCompile, 0, tailleProgComp);
//        System.out.println("Taille compilée : " + tailleProgComp);
  }

  /**
   * Récupère le caractère dans la mémoire. Initialise la mémoire jusqu'à ce pointeur si besoin.
   * @param pointeur l'adresse de la case à récupérer.
   * @return le contenu de cette case.
   */
  private char getMemoireAt(int pointeur) {
      if (pointeur > pointeurMaxMemoire) {
          initMemoire(pointeur);
      }
      return memoireTab[pointeur];
  }

  /**
   * Incrémente le pointeur de manière sécurisée.
   * @param pointeur la valeur actuelle du pointeur.
   * @return <code>pointeur + 1</code> ou <code>0</code> en cas de dépassement de la taille max de la mémoire.
   */
  private int incrementePointeur(int pointeur, int i) {
      return ((pointeur + i) % tailleMemoire);
  }

  /**
   * Incrémente la valeur de la case mémoire de manière sécurisée.
   * @param pointeur l'adresse de la case à incrémenter.
   * @return <code>valeur + 1</code> ou <code>0</code> en cas de dépassement de la taille max d'une case.
   */
  private char incrementeMemoire(int pointeur, int i) {
      return (char) ((getMemoireAt(pointeur) + i) % tailleValeur);
  }

  /**
   * Lit un caractère sur l'entrée.<br/>
   * Un problème de lecture ne provoque pas d'erreur mais le caractère <code>0x0000</code>
   * @param entreeStream le flux d'entrée sur lequel lire le caractère.
   * @return le premier caractère de l'entrée, ou <code>0x0000</code> en cas d'erreur.
   */
  private char litEntree(InputStream entreeStream) {
      InputStreamReader entreeReader = new InputStreamReader(entreeStream);
      char[] entree = new char[1];
      try {
          entreeReader.read(entree);
      } catch (IOException e) {
          entree[0] = 0;
      }
      return entree[0];   // La seule qui existe
  }

  /**
   * Donne l'index de l'instruction suivante, selon le résultat du saut conditionnel.
   * @param iInstruction l'index de l'instruction courante.
   * @param pointeur le pointeur pour la condition
   * @return l'index de l'instruction courante si la valeur à la case indiquée par le pointeur est différente de
   * <code>0x0000</code>.<br/>
   * L'index de l'instruction suivant le crochet fermant correspondant sinon.
   */
  private int sautConditionnelComp(int iInstruction, int pointeur) {
      if (getMemoireAt(pointeur) == 0) {
          return parametresCompile[iInstruction];
      }
      return iInstruction;
  }


  /**
   * Donne l'index de l'instruction suivante, selon le résultat du saut conditionnel.
   * @param iInstruction l'index de l'instruction courante.
   * @param pointeur le pointeur pour la condition
   * @return l'index de l'instruction courante si la valeur à la case indiquée par le pointeur est égale à
   * <code>0x0000</code>.<br/>
   * L'index de l'instruction suivant le crochet ouvrant correspondant sinon.
   */
  private int retourConditionnelComp(int iInstruction, int pointeur) {
      if (getMemoireAt(pointeur) != 0) {
          return parametresCompile[iInstruction];
      }
      return iInstruction;
  }

  /**
   * Initialise la mémoire (remplissage par des 0) jusqu'à la taille indiquée.<br/>
   * Seule la partie entre la taille courante et la taille spécifiée est initialisée, pour pouvoir agrandir la mémoire
   * en cas de "mémoire infinie".<br/>
   * Cette méthode ne fait rien si la taille voulue est plus petite que la taille actuelle.
   * @param taille la taille voulue pour la mémoire.
   */
  private void initMemoire(int taille) {
      char[] newMemoireTab = new char[taille];

      if (memoireTab == null) {
          memoireTab = new char[taille];
      }
      System.arraycopy(memoireTab, 0, newMemoireTab, 0, memoireTab.length);
      // Initialisation du reste
      for (int i = memoireTab.length; i < taille; i++) {
          newMemoireTab[i] = 0;
      }
      memoireTab = newMemoireTab;
      pointeurMaxMemoire = memoireTab.length - 1;
  }

  private char[] supprimeCommentaires() {
//        System.out.println("Taille avec commentaires : " + programme.length);
      char[] tmp = new char[programme.length];
      int progTailleSansComm = 0;
      for (char c : programme) {
          if (c == '+' || c == '-' || c == '>' || c == '<'  || c == '[' || c == ']' || c == '.' || c == ',') {
              tmp[progTailleSansComm++] = c;
          }
      }
      char[] retour = new char[progTailleSansComm];
      System.arraycopy(tmp, 0, retour, 0, progTailleSansComm);
//        System.out.println("Taille sans commentaires : " + progTailleSansComm);
      return retour;
  }

  private char[] preProcesseur(char[] supprimeCommentaires) {
      String str = new String(supprimeCommentaires);
//        System.out.println("Avant préprocesseur : " + str);

      // RAZ cellule
      str = str.replaceAll("\\[-\\]", "0");
      // Addition
      str = str.replaceAll("\\[->\\+<\\]", "a");
      // Déplacement
      str = str.replaceAll(">\\[-\\]<\\[->\\+<\\]", "m");

//        System.out.println("Après préprocesseur : " + str);
      return str.toCharArray();
  }

  private void resetMemoire(int pointeur) {
      memoireTab[pointeur] = 0;
  }

  private void addition(int pointeur) {
      memoireTab[pointeur + 1] += memoireTab[pointeur];
      memoireTab[pointeur] = 0;
  }

  private void copie(int pointeur) {
      memoireTab[pointeur + 1] = memoireTab[pointeur];
      memoireTab[pointeur] = 0;
  }
}

Et puis parce que c'est vous, un bout de code pour lancer le programme. Comme d'hab, la flemme, vous collez directement le code Brainfuck dans le 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
25
26
27
28
29
package info.kisai.brainfuck;


/**
 *
 * @author SpaceFox
 */
public class CLI {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {

      long debut = System.currentTimeMillis();

      /*
       * Test BrainFuck
       */
      BrainFuck bf = new BrainFuck(30000, 65536);

      bf.setProgramme("++++++++++[ >+++++++>+++++++        +++>+++>+<<<<-]>++.>+.+++    ++++..+++.>++.<<+++++++++++++++.> .+++.------         .-        -------.>+.>.");

      String sortie = bf.execute(System.in);
      System.out.println(sortie);
      System.out.println("Temps : " + (System.currentTimeMillis() - debut) + " ms");
    }

}

Alors on commence par remarquer que c'est programmé en français… passons.

Que fait ce programme ?

Bonne question, dont voici la réponse (honteusement repiquée et recompilée de ce que j'avais écris il y a environ 4 ans sur le Site du Zéro) :

Où perds-on du temps ?

Toutes ces optimisations sont validées à grand coups de profiler !

Des optimisations efficaces :
  • On perds un temps monstrueux à chercher le crochet correspondant à chaque fois qu'on en trouve un. C'est ridicule, puisque brainfuck n'est pas auto-modifiant (vu que programme et données sont dans deux espaces mémoire séparés) ; donc la correspondance entre crochets est fixe. Y'a qu'à la calculer avant de lancer le programme, et hop ! ça va beaucoup plus vite !
  • Les listes et maps pour gérer la mémoire et le programme, c'est très "objet", mais quand on passe son temps à ne se servir que de ça (des millions d'appels, j'exagère pas) c'est pas très rapide. Donc, on remplace la gestion par des tableaux, et hop c'est plus rapide ! En plus c'est pas vraiment plus compliqué, sauf peut-être la fonction d'initialisation de la mémoire (et encore).

Là on arrive un peu à la limite de la chose : le profiler me dit que je passe surtout du temps (environ la moitié) dans la méthode principale, qui contient surtout un switch…
Comment améliorer ça ?

En tirant partie des propriétés du langage.On va transformer un peu le truc : au lieu d'avoir une série d'instructions, on va avoir une série d'instructions avec un paramètre chacune.
Au lieu d'écrire + n fois de suite, on va avoir une instruction + avec comme paramètre n : au lieu d'ajouter 1 n fois, on ajoute n une fois, ce qui prends approximativement n fois moins de temps ^^

Seules les instructions + - > et < peuvent se chaîner. Par contre on profite aussi des paramètres pour les crochets [ et ] : quand on est dans ce cas, le paramètre n'est plus le nombre de fois où il faut répéter l'opération, mais l'emplacement du crochet correspondant. On évite une structure en plus (mais ça ne change pas grand-chose en fait). On remarque que du coup, on a plus besoin que de 6 symboles au lieu de 8 : -(n) revient à faire +(-n) <(n) revient à faire >(-n)

On gagne pratiquement rien en performances, mais un peu en simplicité dans le code du "compilateur". La perte de temps à compiler est très largement compensée par le gain en rapidité : sur un programme très lourd comme celui qui affiche la GPL (plus d'1Mo de code BF…) on gagne encore du temps.

Plus d'optimisations ?

Là, je pense qu'on arrive au bout de ce qu'on peut faire en restant sur un interpréteur Java. On peut encore gagner quelques pourcents en supprimant la gestion de la mémoire circulaire (environ 10 %) et des cases de mémoire circulaires (environ 10% aussi)

Des optimisations qui n'en sont pas
  • On peut sans doute faire mieux avec le "compilateur", mais en même temps on s'en fout : il n'est appelé qu'une fois, et est déjà très très rapide : ~ 3 ms sur Mandelbrot, et 35 ms pour les Mo de code source du programme qui affiche la GPL.
  • Les astuces à la con comme coller des "final" partout, ça sert strictement à rien (dans ce genre de programme en tous cas)
  • Les "inline" en Java non plus (c'est pour ça que j'ai laissé les méthodes dans le switch de la version optimisée : on ne gagne rien à déplacer le corps des méthodes dans le switch) [Avec la JVM Java 8, il semblerait même qu'on perde quelques pourcentages en performances].
  • Les "modulo" au lieu des "if" pour gérer la mémoire circulaire. J'ai mis des modulo parce que avec +n c'est plus simple à gérer qu'avec un if.

Et partant de là, est-ce qu'on peut encore plus optimiser ?

Oui ! En implémentant ceci :

  • Nettoyage du code avant compilation (pour éviter les interférences avec les caractères de commentaires).
  • Les tableaux programmes "compilés" font maintenant la taille réelle, et pas la taille du programme d'origine avec plein de cases vides.
  • Détection de la remise à 0 d'une case, pattern [-]
  • Détection de l'addition : m[1] = m[0] + m[1] et m[0] = 0 ; pattern [->+<]
  • Détection de la copie d'octet : m[1] = m[0] et m[0] = 0 ; pattern >[-]<[->+<]

Et les performances ?

J'ai testé sur deux programmes calculatoires :

  • La fractale, qui passe de 6 minutes 30 à 17.5 secondes, soit un facteur 22.
  • Les tours de Hanoï, qui passe de 142 à 1.7 secondes, soit un facteur 83 !

Ce dernier programme utilise massivement des structures qui sont fortement optimisées à la compilation (la réinitialisation d'une case, en particulier, est appelée plusieurs dizaines de millions de fois) ; d'où le résultat.

Édité par SpaceFox

Bon alors après avoir laissé ça en suspens quelques jours, je reviens et il y a déjà plein de monde …

Je répète ce que j'ai dit dans le topic sur le tuto BF : je suis en train (mais doucement hein …) de créer un compilateur BF. Mais un "vrai" compilateur. C'est-à-dire que je ne passe pas par un langage intermédiaire type C/C++, mais je crée direct du code assembleur.

Pour accélérer un peu les choses (parce que sinon on ne gagne strictement rien par rapport à un BF->C->executable), j'utilise les registres comme cellule.

Du coup, je suis limité en cellule.

La taille des cellules en BF étant celle d'un octet, j'utilise donc les registres 8 bits. Donc pour l'instant, j'ai 8 cellules. Avec des rotations sur les registres, je peux monter à 16 (mais ça sera un peu plus tard, parce que ça va être un peu le boxon). Je suis donc très loin du "tableau infini".

Après ce long préambule viens ma question : suis-je dans le coup ? Dit autrement : est-ce que vous allez me hurler dessus parce que je n'ai que 16 cases ?

En fait, théoriquement je peux monter au dessus de 16, comme en C, en utilisant de la mémoire. Sauf qu'à ce moment là les registres ne serviront que comme "zone tempon" pour accélérer le programme. Or, dire que je ne serais pas capable de rivaliser en terme d'optimisation avec un compilateur qui date d'avant ma naissance, ce n'est pas de la modestie, c'est du réalisme.

Donc, mon compilateur, une fois fini, est-ce que ça vous intéresse ?

Bonne soirée

Édité par dosmpm

There is no place like /home.

+0 -0

@Maëlan : Tu as des '-' et des '.' dans tes commentaires, tu les as pris en compte?

Que nenni ! Unicode est fantastique !

Du coup, ça me donne une idée : pourquoi ne pas écrire un programme Brainfuck dissimulé dans un texte? Un code entre Brainfuck et Shakespeare.

Bibibye

J’avais eu des idées comme ça aussi. Un code bilingue, ce serait rigolo.


@ SpaceFox : Les premières optimisations que tu présentes sont déjà faites (de façon plus ou moins automatique) par un certain nombre d’implémentations, par exemple le code de ctcp. Par contre, la détection de motif est nettement plus intéressante. Je pense que ça peut encore s’améliorer en ajoutant des motifs reconnus, en particulier celui de la duplication ([->+>+<<]), et en rendant tout ça plus générique (par exemple, si je déplace une valeur de deux cases vers la droite ou de trois cases vers la gauche, ça serait chouette que ça soit reconnu quand même — je me sers massivement de déplacements de quatre cases dans mon propre code).

Autre idée, on peut aussi faire de l’élimination de branches mortes (utile pour du code généré entre autres), mais je ne suis pas certain que le gain soit significatif. Par exemple, on sait qu’en sortant d’une boucle, la cellule actuelle est nulle (du coup […][Ce code ne sera jamais exécuté, ça fait un super-commentaire.]).

En tout cas, tes résultats sont assez impressionnants.

écrire français sous Windows : fr-oss (azerty++) ou bépo (étudié pour le français) | <insérer un truc spirituel ici>

+0 -0

Cette réponse a aidé l’auteur du sujet

J'ai un petit peu optimisé la génération en C++. Je reposte l'archive contenant le code que vous pouvez compiler pour tester.

Niveau performance, le Mandelbrot s'exécute en 2.5s et les tours de Hanoi en 5.5s.

Archive : https://drive.google.com/file/d/0B5eGJmWOd6U2Q2xiY1EwYlIxUEU/edit?usp=sharing

"Easy is right. Begin right and you are easy. Continue easy and you are right. The right way to go easy Is to forget the right way And forget that the going is easy." Chuang Tzu

+0 -0

Cette réponse a aidé l’auteur du sujet

N'étant un développeur ASM expérimenté, j'ai modifié mon code précédent pour générer de l'assembleur (nasm). La seule optimisation qu'il y a, c'est la fusion lorsqu'il y a plusieurs +, -, > ou < à la suite. inc ecx devenant add ecx, 5

  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
#include <fstream>
#include <array>
#include <stack>
#include <vector>
#include <cstdint>
#include <cstdio>

int main(int argc, char** argv)
{
    if(argc != 2)
    {
        return 0;
    }
    
    std::vector<char> program;
    
    std::ifstream file(argv[1]);
    while(!file.eof())
    {
        program.push_back(file.get());
    }
    file.close();
    
    std::ofstream output("output.asm");
    output << "section .data\n"
            << "buffer: times 30000 db 0\n"
            << "\n"
            << "section .text\n"
            << "    global _main\n"
            << "    extern _putchar\n"
            << "\n"
            << "_main:\n"
            << "    mov ecx, 0\n";
    
    std::vector<std::pair<char, int>> instructions;
    for(char c : program)
    {
        switch(c)
        {
            // smashable instructions
            case '+':
            case '-':
            case '<':
            case '>':
                if(instructions.size() > 0 && instructions.back().first == c)
                    instructions.back().second++;
                else
                    instructions.push_back(std::make_pair(c, 1));
                break;
            // non-smashable instructions
            case '[':
            case ']':
            case '.':
            case ',':
                instructions.push_back(std::make_pair(c, 1));
                break;
            default:
                /* comment */;
        }
    }
    
    int loopCount = 0;
    std::stack<int> currentLoops;
    for(auto const & pair : instructions)
    {
        switch(pair.first)
        {
            case '+':
                if(pair.second == 1)
                    output << "    inc byte [buffer+ecx]\n";
                else
                    output << "    add byte [buffer+ecx], " << pair.second << "\n";
                break;
            case '-':
                if(pair.second == 1)
                    output << "    dec byte [buffer+ecx]\n";
                else
                    output << "    sub byte [buffer+ecx], " << pair.second << "\n";
                break;
            case '<':
                if(pair.second == 1)
                    output << "    dec ecx\n";
                else
                    output << "    sub ecx, " << pair.second << "\n";
                break;
            case '>':
                if(pair.second == 1)
                    output << "    inc ecx\n";
                else
                    output << "    add ecx, " << pair.second << "\n";
                break;
            case '[':
                output << "    cmp byte [buffer+ecx], 0\n";
                output << "    je .loopend" << loopCount << "\n";
                output << " .loopstart" << loopCount << ":\n";
                currentLoops.push(loopCount);
                loopCount++;
                break;
            case ']':
                output << "    cmp byte [buffer+ecx], 0\n";
                output << "    jne .loopstart" << currentLoops.top() << "\n";
                output << " .loopend" << currentLoops.top() << ":\n";
                currentLoops.pop();
                break;
            case '.':
                output << "    push ecx\n";
                output << "    push dword [buffer+ecx]\n";
                output << "    call _putchar\n";
                output << "    add esp, 4\n";
                output << "    pop ecx\n";
                break;
            case ',':
                output << "    push ecx\n";
                output << "    call _putchar\n";
                output << "    mov byte [buffer+ecx], eax\n";
                output << "    pop ecx\n";
                break;
            default:
                /* comment */;
        }
    }
    output << "    ret\n";
    output.close();
    
    return 0;
}

Voilà par exemple le code généré pour “Hello World” :

  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
section .data
buffer: times 30000 db 0

section .text
    global _main
    extern _putchar

_main:
    mov ecx, 0
    add byte [buffer+ecx], 10
    cmp byte [buffer+ecx], 0
    je .loopend0
 .loopstart0:
    inc ecx
    add byte [buffer+ecx], 7
    inc ecx
    add byte [buffer+ecx], 10
    inc ecx
    add byte [buffer+ecx], 3
    inc ecx
    inc byte [buffer+ecx]
    sub ecx, 4
    dec byte [buffer+ecx]
    cmp byte [buffer+ecx], 0
    jne .loopstart0
 .loopend0:
    inc ecx
    add byte [buffer+ecx], 2
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    inc ecx
    inc byte [buffer+ecx]
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    add byte [buffer+ecx], 7
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    add byte [buffer+ecx], 3
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    inc ecx
    add byte [buffer+ecx], 2
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    sub ecx, 2
    add byte [buffer+ecx], 15
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    inc ecx
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    add byte [buffer+ecx], 3
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    sub byte [buffer+ecx], 6
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    sub byte [buffer+ecx], 8
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    inc ecx
    inc byte [buffer+ecx]
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    inc ecx
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    ret

J'imagine qu'il y a moyen d'améliorer ça (notamment le push/pop d'ecx lors de l'appelle d'une fonction de la libc voire se passer de libc ?).

+0 -0

J'imagine qu'il y a moyen d'améliorer ça (notamment le push/pop d'ecx lors de l'appelle d'une fonction de la libc voire se passer de libc ?).

Pour remplacer le putchar et le getchar, tu peux passer par les appels système du noyau linux. Inconvénient : tu n'es plus cross-platform.

L'appel système se fait avec int 0x80, et il utilise les 4 registres généraux.

Dans les 2 cas (puchar et getchar), tu dois mettre:

  • l'adresse (= pointeur vers) de la chaîne à afficher/utiliser pour écrire dans ecx
  • la taille de cette chaîne dans edx

Ensuite, on met dans eax le numéro de l'appel système, qui est:

  • 3 pour getchar
  • 4 pour putchar

Et enfin, tu mets dans ebx le descripteur de fichier à utiliser, soit:

  • 1 (sortie standard) pour putchar
  • 0 (entrée standard) pour getchar

Voilà !

Bonne soirée.

There is no place like /home.

+1 -0

Cette réponse a aidé l’auteur du sujet

Vous me faites peur avec vos codes ultra longs O_o

J'ai une solution rapide (et probablement pas super propre) en Haskell. Je précise que ça fait vraiment pas longtemps que j'ai commencé à apprendre le langage et je suis très loin d'avoir tout compris.

 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
import Data.Char

main = do
   code <- readFile "mandelbrot.bf"
   putStr $ bf code mem [] "" ""

mem = (repeat 0, 0, repeat 0)

bf :: String -> ([Int], Int, [Int]) -> [String] -> String -> String -> String
bf [] _ _ out _ = reverse out
bf c@(tc:qc) mem@(l@(tl:ql), cur, r@(tr:qr)) b out inp =
   case tc of
       '+' -> bf qc (l, cur+1, r) b out inp
       '-' -> bf qc (l, cur-1, r) b out inp
       '<' -> bf qc (ql, tl, cur:r) b out inp
       '>' -> bf qc (cur:l, tr, qr) b out inp
       '[' ->
           if cur == 0 then
               bf (skipb c 0) mem b out inp
           else
               bf qc mem (qc:b) out inp
       ']' ->
           if cur == 0 then
               bf qc mem (tail b) out inp
           else
               bf (head b) mem b out inp
       '.' -> bf qc mem b ((chr cur):out) inp
       ',' -> bf qc (l, ord (head inp), r) b out (tail inp)
       _   -> bf qc mem b out inp

skipb [] _ = []
skipb (t:q) n
   | n == 0 = q
   | t == '[' = skipb q (n+1)
   | t == ']' = skipb q (n-1)
   | otherwise = skipb q n

Par contre, j'arrive pas à faire tourner l'exemple de Mandelbrot. Pourtant, toutes mes fonctions sont récursives terminales, donc je suppose que c'est lié à la paresse du haskell. Si c'est bien le cas, j'aimerais bien savoir s'il y a une bonne solution pour résoudre le problème.

+0 -0

Je me suis posé une question débile : puisqu'on peut voir Brainfuck comme un processeur, combien d'opérations par secondes l'interpréteur construit peut-il traiter ?

Réponse : entre 60 et 90 millions d'opérations / seconde selon les instructions et l'OS sur mon PC (Core i5 3570 à 3.6/3.7 Ghz pendant le test). Soit entre 40 et 60 cycles par instruction Brainfuck (ça vous donne une idée de la quantité d'opérations traitées par les programmes de fractale ou de résolution des tours de Hanoï).

Le compteur d'instructions ne ralentit pas vraiment (environ 1/30ème de ralentissent, ce qui est cohérent avec les chiffres ci-dessus).

Plus surprenant, je voulais voir ce que ça donnait dans ma VM Linux (à la base pour voir le vrai rendu des tours de Hanoï)… eh bien c'est 10 à 15 % plus rapide !

Édité par SpaceFox

Cette réponse a aidé l’auteur du sujet

Bon, voici ma version en Haskell qui génère le code C équivalent (sans faire d'optimisations…)

 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
import Text.Parsec hiding (token,tokens)
import Text.Parsec.String
import System.Environment (getArgs)

data Token = Incr
           | Decr
           | Fwd
           | Bwd
           | Get
           | Put
           | Loop [Token]
           | Comment
           deriving (Show)

token :: Parser Token
token = do (noneOf "+-.,<>[]" >> return Comment)
     <|>   (char '+' >> return Incr)
     <|>   (char '-' >> return Decr)
     <|>   (char '>' >> return Fwd)
     <|>   (char '<' >> return Bwd)
     <|>   (char ',' >> return Get)
     <|>   (char '.' >> return Put)
     <|>   (char '[' >> do c <- bf ; char ']' ; return (Loop c))

bf :: Parser [Token]
bf = many token

gen :: [Token] -> String
gen []     = []
gen (t:ts) = case t of
                Incr    -> "++*ptr;\n"                             ++ gen ts
                Decr    -> "--*ptr;\n"                             ++ gen ts
                Fwd     -> "++ptr;\n"                              ++ gen ts
                Bwd     -> "--ptr;\n"                              ++ gen ts
                Get     -> "*ptr=getchar();\n"                     ++ gen ts
                Put     -> "putchar(*ptr);\n"                      ++ gen ts
                Loop tk -> ("while (*ptr) {\n" ++ gen tk ++ "}\n") ++ gen ts
                Comment -> ""                                      ++ gen ts

main :: IO ()
main = do (file:_) <- getArgs
          res      <- parseFromFile bf file
          case res of
            Left err     -> print err
            Right tokens -> putStr $ "#include <stdio.h>\n" ++
                                     "char array[30000];\n" ++
                                     "char *ptr=array;\n"   ++ 
                                     "int main (void) {\n"  ++
                                     gen tokens             ++
                                     "return 0;\n}"

Édité par olzd

+0 -0

Cette réponse a aidé l’auteur du sujet

J’ai un code ocaml qui optimise certaines boucles.

  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
type optimization_token =
  MoveAdd of int * int
(* AddTo n m ajoute m fois la valeur de la cellule courante à la cellule de distance n *)
 | AddTo of int * int

type token = 
   Add of int
 | Move of int
 | Print
 | Read
 | Assign of int
 | Loop of token list
 | Macro of optimization_token

let string_of_t (ops : token) : string =
 let open Printf in
 let rec to_string indent = function
   | Move x -> sprintf "%sMove(%d)" indent x
   | Add i -> sprintf "%sAdd(%d)" indent i
   | Print -> sprintf "%sPrint" indent
   | Read -> sprintf "%sRead" indent
   | Assign x -> sprintf "%sAssign(%d)" indent x
   | Loop nodes ->
       sprintf "%sLoop <<\n%s\n%sLoop >>"
         indent
         (String.concat "\n" (List.map (to_string ("| "^indent)) nodes))
         indent
   | Macro (MoveAdd (x,y)) -> sprintf "%sMoveAdd(%d, %d)" indent x y
   | Macro (AddTo (x,y)) -> sprintf "%sAddTo (%d, %d)" indent x y
 in to_string "" ops

(* Afin d’implémenter une mémoire circulaire (faute d’avoir une mémoire 
  infinie :-() *)
let rec new_pos (key : int) (p : int) (len : int) : int =
 if (p + key) >= 0 then (p + key) mod len
 else len + (p+key) mod len

(* optimiser les boucles dans lesquelles la somme des mouvements égale zéro, où la cellule de départ de 
boucle est décrémentée de -1 et qui ne contiennent que des instructions Move et Add. *)
let optimize_simple_loop (instruction : token) : token list =
 let rec aux (content : token list) (count_move : int) : token list =
   match content with
   | [] -> Assign 0 :: []
   (* On ignore les incrémentations sur la cellule d’entrée de la boucle, que l’on remet à
     zéro à la fin (voir deux lignes plus haut). *)
   | Macro(MoveAdd (x, y)) :: xs when x + count_move = 0 -> aux xs 0
   | Add x :: xs -> aux xs 0
   | Macro(MoveAdd (x, y)) :: xs -> Macro(AddTo (count_move + x, y)) :: aux xs(count_move + x)
   | Move x :: xs -> aux xs (count_move + x)
   
   | other :: xs -> failwith ( string_of_t (other) ^ "optimize_simple_loop isnt applied to a simple-loop statement")
 in match instruction with
    | Loop xs -> aux xs 0
    | _  -> failwith "optimize_simple_loop isnt applied to a loop statement"

let is_simple_loop (instruction : token) : bool =
 let rec aux (content : token list) (count_move : int) (count_add : int) =
   match content with
  | [] -> count_move = 0 && count_add = (-1)
   (* count_add permet de compter le nombre le nombre d’incrémentations qui sont faites
      sur la cellule d’entrée de la boucle *)
   | Macro(MoveAdd (x, y)) :: xs when x + count_move = 0 -> aux xs 0 (count_add + y)
   (* Un Add x isolé est forcément devant toute instruction < ou >, on est donc sur 
      la cellule d’entrée de la boucle *)
   | Add x :: xs -> aux xs 0 (count_add + x)
   | Macro(MoveAdd (x, y)) :: xs -> aux xs (count_move + x) count_add
   | Move x :: xs -> aux xs (count_move + x) count_add
   | _ -> false
 in match instruction with
    | Loop content -> aux content 0 0
    | _ -> false

let rec optimize (instructions : token list) : token list =
 match instructions with
 | [] -> []
 | Move x :: Add y :: xs -> Macro(MoveAdd (x, y)) :: optimize xs
 | Loop xs :: ys -> 
   let min_optimized = Loop (optimize xs) in
   if is_simple_loop min_optimized then (optimize_simple_loop min_optimized) @ optimize ys (* pas joli joli :/ *)
   else min_optimized :: optimize ys
 | Assign 0 :: Add x :: xs -> Assign x :: optimize xs
 | other :: xs -> other :: optimize xs

let len = 30000
let memory = Array.make len 0
let cursor = ref 0
let rec eval (program : token list) : unit =
 let aux' = function
   | Macro(MoveAdd (x, y)) -> cursor := new_pos x !cursor len; memory.(!cursor) <- memory.(!cursor) + y;
   | Move x -> cursor := new_pos x !cursor len
   | Add x -> memory.(!cursor) <- memory.(!cursor) + x
   | Print -> print_char (Char.chr memory.(!cursor))
   | Read -> let c = Scanf.scanf " %c" (fun x -> x) in memory.(!cursor) <- Char.code c
   | Assign x -> memory.(!cursor) <- x;
   | Macro(AddTo (x, y)) -> let i = new_pos x !cursor len in memory.(i) <- memory.(i) + y * memory.(!cursor);
   | Loop ys -> while memory.(!cursor) <> 0 do eval ys done
 in List.iter aux' program

let parse (channel : in_channel) : token list =
 let rec parse_increments (stream : char Stream.t) (acc : int) : char Stream.t * int =
   match stream with parser
   | [< ''+'; r >] -> parse_increments r (acc + 1)
   | [< ''-'; r >] -> parse_increments r (acc - 1)
   | [< 'l; r >] -> ([< 'l; r >], acc)
   | [< >] -> ([< >], acc) in
 let rec parse_movements (stream : char Stream.t) (acc : int) : char Stream.t * int =
   match stream with parser
   | [< ''>'; r >] -> parse_movements r (acc + 1)
   | [< ''<'; r >] -> parse_movements r (acc - 1)
   | [< 'l; r >] -> ([< 'l; r >], acc)
   | [< >] -> ([< >], acc) in
 let rec aux (stream : char Stream.t) : token list =
   match stream with parser
   | [< ''+'; r >] -> let (s, n) = parse_increments r 1 in Add n :: aux s 
   | [< ''-'; r >] -> let (s, n) = parse_increments r (-1) in Add n :: aux s 
   | [< ''>'; r >] -> let (s, n) = parse_movements r 1 in Move n :: aux s
   | [< ''<'; r >] -> let (s, n) = parse_movements r (-1) in Move n :: aux s
   | [< ''.'; r >] -> Print :: aux r
   | [< '','; r >] -> Read :: aux r
   | [< ''['; r >] ->    
     let content = aux r in 
     if content = [Add (-1)] then Assign 0 :: aux r else Loop content :: aux r
   | [< '']'; r >] -> []
   | [< 'l; r >] -> aux r
   | [< >] -> []
 in aux (Stream.of_channel channel)

let _ = 
 let tokens = parse (open_in Sys.argv.(1)) in 
 let optimized = optimize tokens in
(* List.iter (fun x -> print_endline(string_of_t x)) optimized; *) (*afficher l’ast*)
 eval optimized

Il a affiché Mandelbrot en ~1m13s…

+1 -0

Cette réponse a aidé l’auteur du sujet

Un peu dans l'idée de ce qu'a fait Guiloo : le code suivant permet d'imiter au plus proche le comportement du Brainfuck en Haskell, sauf pour les crochets qui sont remplacés par la fonction loop. Pour utiliser le Brainskell (ie le sous ensemble de Haskell qui équivaut au BF) , il suffit de changer la définition de codeBF et de compiler. Celle donnée actuellement correspond à ,[-+-].>+<. J'écrirais probablement un petit convertisseur BF -> Brainskell pour voir un peu les performances.

 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
import Control.Monad.Trans.State.Lazy
import Data.Char
import Data.List
import Control.Monad.Trans.Class
import Control.Monad

type Zip a = ([a],[a])

type BF = StateT (Zip Int) IO ()

currentlyPointed = head . snd

next :: BF
next = modify $ \(l, x:xs) -> (x:l, xs)

prev :: BF
prev = modify $ \(x:xs, l) -> (xs, x:l)

incr :: BF
incr = modify $ \(l, x:xs) -> (l, (x+1):xs)

decr :: BF
decr = modify $ \(l, x:xs) -> (l, (x-1):xs)

output = do s <-get
            lift (putChar . chr . currentlyPointed $ s)
            put s
                          

input :: BF 
input = do (l, _:xs) <- get
           inp <- lift $ (liftM ord) getChar
           put (l, inp:xs)

  
loop :: BF -> BF
loop code = do s <- get
               if currentlyPointed s == 0 then put s else code >> (loop code)


runBF code = evalStateT code (repeat 0, repeat 0)

main = do runBF codeBF

codeBF = do
  input
  loop $ do decr
            incr
            decr
  output
  next
  incr
  prev

Édité par NougatRillettes

+0 -0

Cette réponse a aidé l’auteur du sujet

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

Édité par Ksass`Peuk

First : Always RTFM - "Tout devrait être rendu aussi simple que possible, mais pas plus." A.Einstein [Tutoriel Frama-C WP]

+2 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

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