怪怪的程式語言名稱：Brainfuck

若您覺得文章寫得不錯，請點選網誌上的廣告，來支持小編，謝謝。

最近在 ptt Gossiping 版的jserv 的一篇回文
https://www.ptt.cc/bbs/Gossiping/M.1555612071.A.14C.html

得知 Brainfuck 也是個程式語言，於是小編自己也來寫一個 Brainfuck interpreter。先來了解 Brainfuck 的指令吧。

Brainfuck指令說明
============底下文字從 https://en.wikipedia.org/wiki/Brainfuck 節錄出來：============
CharacterMeaning
>increment the data pointer (to point to the next cell to the right).
<decrement the data pointer (to point to the next cell to the left).
+increment (increase by one) the byte at the data pointer.
-decrement (decrease by one) the byte at the data pointer.
.output the byte at the data pointer.
,accept one byte of input, storing its value in the byte at the data pointer.
[if the byte at the data pointer is zero, then instead of moving the instruction pointer forward to the next command, jump it forward to the command after the matching ] command.
]if the byte at the data pointer is nonzero, then instead of moving the instruction pointer forward to the next command, jump it back to the command after the matching [ command.
brainfuck指令與C語言對照表：
brainfuck commandC equivalent
(Program Start)char array[30000] = {0};
char *ptr=array;
>++ptr;
<--ptr;
+++*ptr;
---*ptr;
.putchar(*ptr);
,*ptr=getchar();
[while (*ptr) {
]}
============以上文字從 https://en.wikipedia.org/wiki/Brainfuck 節錄出來：============
其中，[ 與 ] 這兩個指令需要注意有巢狀的情況，而測試的 Brainfuck 程式碼如下：

hello.bf (https://github.com/pablojorge/brainfuck/blob/master/programs/hello.bf)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
+++++ +++++             initialize counter (cell #0) to 10
[                       use loop to set the next four cells to 70/100/30/10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
]                   
> ++ .                  print 'H'
> + .                   print 'e'
+++++ ++ .              print 'l'
.                       print 'l'
+++ .                   print 'o'
> ++ .                  print ' '
<< +++++ +++++ +++++ .  print 'W'
> .                     print 'o'
+++ .                   print 'r'
----- - .               print 'l'
----- --- .             print 'd'
> + .                   print '!'
> .                     print '\n'

費式數列 fibonacci.bf (https://github.com/pablojorge/brainfuck/blob/master/programs/fibonacci.bf)
1
2
3
4
5
6
7
8
9
>++++++++++>+>+[
    [+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[
        [-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-
            [>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>
    ]<<<
]
This program doesn't terminate; you will have to kill it.
Daniel B Cristofani (cristofdathevanetdotcom)
http://www.hevanet.com/cristofd/brainfuck/

圓周率 pi.bf (https://copy.sh/brainfuck/prog/yapi.b)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
[ yet another pi calculation program in bf

  Just like for pi16.b the accuracy of the result depends on the cellsize:
 
   - using  8 bit cells causes an overflow after 4 digits
   - using 16 bit cells causes an overflow after 537 digits
   - using 32 bit cells causes an overflow after several millions of digits
  
  It's about ~38 times shorter than pi16.b, ~364 times faster and works with
  not-wrapping (bignum) implementations. 
 
  by Felix Nawothnig (felix.nawothnig@t-online.de) ]

>  +++++ +++++ +++++ (15 digits)

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

自然數 e.bf (http://www.hevanet.com/cristofd/brainfuck/e.b)
 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
[e.b -- compute e
(c) 2016 Daniel B. Cristofani
http://brainfuck.org/]

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

This program computes the transcendental number e, in decimal. Because this is
infinitely long, this program doesn't terminate on its own; you will have to
kill it. The fact that it doesn't output any linefeeds may also give certain
implementations trouble, including some of mine.

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
#include <stdlib.h>
#include <stdio.h>

static int cells[30000] = {0};
unsigned int dp = 0;      // data pointer

void bfExe(char *cmds)
{
    int i, nestedLoop, curCmd;

    for(i = 0; cmds[i] != 0; i++)
    {
        curCmd = cmds[i];
        switch(curCmd)
        {
        case '>':
            ++dp;
            break;
        case '<':
            --dp;
            break;
        case '+':
            ++cells[dp];
            break;
        case '-':
            --cells[dp];
            break;
        case '.':
            putchar(cells[dp]);
            break;
        case ',':
            cells[dp] = getchar();
            break;
        case '[':
            if(!cells[dp])
            {
                nestedLoop = 1;
                while(nestedLoop)
                {
                    i++;
                    if(cmds[i] == '[') nestedLoop++;
                    if(cmds[i] == ']') nestedLoop--;
                }
            }
            break;
        case ']':
            if(cells[dp])
            {
                nestedLoop = 1;
                while(nestedLoop)
                {
                    i--;
                    if(cmds[i] == ']') nestedLoop++;
                    if(cmds[i] == '[') nestedLoop--;
                }
            }
            break;
        }
    }
}

int main(int argc, char* argv[]) {
    if(argc < 2) exit(1);
    FILE *f = fopen(argv[1], "r");
    fseek(f, 0, SEEK_END);
    long fsize = ftell(f);
    fseek(f, 0, SEEK_SET);

    int *bfCmd = malloc(fsize + 1);
    fread(bfCmd, 1, fsize, f);
    fclose(f);
    bfCmd[fsize] = 0;

    bfExe(bfCmd);
    return 0;
}

而在 stackoverflow 上有高手寫了底下的C程式碼(https://stackoverflow.com/questions/9147357/brainfuck-interpreter)：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#include <stdlib.h>
char m[9999], *n[99], *r = m, *p = m + 5000, **s = n, d, c;
main()
{
   for (read(0, r, 4000); c = *r; r++)
          c - ']' || (d > 1 ||
          (r = *p ? *s : (--s, r)), !d || d--), c - '[' || d++ ||
          (*++s = r), d || (*p += c == '+', *p -= c == '-', p += c == '>',
          p -= c == '<', c - '.' || write(2, p, 1), c - ',' || read(2, p, 1));
}

C語言果然很特別！！！

底下為其他語言實作出來的 brainfuck interpreters 與模擬實驗資料。
https://github.com/pablojorge/brainfuck

Labels: ,