Brainfuck にコンパイル可能な高水準言語を作った話

少し前に Bigbrain という自作言語を作ったので紹介します。この言語は Brainfuck にコンパイルされます。ソースコードは GitHub で公開されています。

https://github.com/dqn/bigbrain

Bigbrain という名前は、知的であることを意味する「Big brain」というスラングが由来です。

次のような Bigbrain のコードをコンパイルすると、

x = 30;

for (i = 1; i <= x; ++i) {
  if (i % 3 == 0 && i % 5 == 0) {
    putchar(102);
    putchar(105);
    putchar(122);
    putchar(122);
    putchar(98);
    putchar(117);
    putchar(122);
    putchar(122);
  } else if (i % 3 == 0) {
    putchar(102);
    putchar(105);
    putchar(122);
    putchar(122);
  } else if (i % 5 == 0) {
    putchar(98);
    putchar(117);
    putchar(122);
    putchar(122);
  } else {
    print(i);
  }
  putchar(10);
}

次のような Brainfuck のコードが出力されます。

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

このコードを任意の Brainfuck インタプリタで実行すると、次のような結果が得られます。

1
2
fizz
4
buzz
fizz
7
8
fizz
buzz
11
fizz
13
14
fizzbuzz
16
17
fizz
19
buzz
fizz
22
23
fizz
buzz
26
fizz
28
29
fizzbuzz

細かい言語仕様の解説はここでは割愛します。パッと見で理解しづらいのは putchar(102)print(i) のような部分でしょう。

putchar は引数に与えられた数値を文字コードとして出力します。どの文字コードの規格で扱われるかは Brainfuck の処理系に委ねられますが、大抵の場合は ASCII コードとして扱われるはずです。例えば 102 は ASCII コードで f を指すので、putchar(102)f を出力します。

print は引数に与えられた数値を 10 進数表記で出力します。例えば print(102)102 を出力します。余談ですが、すごく単純な関数のように見えて実は 1、0、2 をそれぞれ出力するのは大変で、内部ではかなり重めの処理をしています。

実装

字句解析、構文解析、コード生成まですべて自前で実装しています。Bigbrain のプログラムは再帰下降構文解析によって AST にパースされます。Bigbrain はインタプリタではなくコンパイラなので、「AST を評価する」のではなく、「AST から Brainfuck のコードを出力する」必要があります。

ここからはある程度 Brainfuck の知識があることを前提に解説します。

例えば、次のような Bigbrain のコードは、

2 * 3;

次のようにコンパイルされる必要があります。

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

このコードを分かりやすく整形したものが次になります。

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

Brainfuck で 2 * 3 は、「0 に 2 を加算するのを 3 回繰り返す」ことで表現できます。

まず、元となる 2 と 3 をそれぞれメモリ上の 0 番目、1 番目(0-indexed)につくります。

++
>+++

このとき、メモリは次のようになっています。

[2][3][0][0]

次に、0 番目の 2 を 2 番目、3 番目に移動します。0 番目の値が 0 になるまで、2 番目、3 番目を加算することで実現できます。なぜ 2 つのメモリに加算する必要があるのかは、次の操作で分かります。

  [
    >+
    >+
    <<-
  ]

このとき、メモリは次のようになっています。

[0][3][2][2]

次に、3 番目の 2 を 0 番目に移動します。

  >>[
    <<+
    >>-
  ]

このとき、メモリは次のようになっています。

[2][3][2][0]

初期のメモリと今のメモリを見比べると、「0 に 2 を加算するのを 1 回繰り返した」状態になっていることが分かります。これをあと 2 回繰り返せば、2 * 3 が達成できるでしょう。1 番目の 3 をデクリメントし、次のループに入ります。

<<-
[2][2][2][0]

メモリの状態は次のように移り変わるはずです。

2 ループ目:

[0][2][4][2]
[2][2][4][0]
[2][1][4][0]

3 ループ目:

[0][1][6][2]
[2][1][6][0]
[2][0][6][0]

ここで、メモリの 1 番目が 0 になったのでループが終了します。これで 2 * 3 を達成できました。

このようなアルゴリズムを +-/%><if-elsefor などで同様に実装していくことで、様々な Brainfuck のコードを生成できるようになります。このあたりのアルゴリズムは Brainfuck algorithms - Esolang が参考になりました。

機能の紹介

Bigbrain でできることを簡単に紹介します。

変数

foo = 42;

input

Brainfuck の , にあたります。

foo = input();

input() は式なので、次のように演算子と組み合わせることもできます。

foo = input() * 10;

putchar

Brainfuck の . にあたります。

putchar(65); // A

print

Brainfuck で表せる数の最大値は 255 が一般的なようなので、3 桁までしか対応していません。

print(65); // 65

block

block は式になっています。ブロック内の最後の文にセミコロンがない場合、その値がブロックを評価した値になります。

x = { 12 };
// x => 12

y = {
  print(10);
  putchar(65);

  20 + 15 + 7
};
// y => 42

if、if-else

if、else の本体は block である必要があります。また、if、if-else は式として扱われます。

x = 20;

if (x > 10) {
  print(65);
}

if (x > 10) {
  print(65);
} else {
  print(66);
}

if (x > 10) {
  print(65);
} else if (x < 10) {
  print(66);
} else {
  print(67);
}

y = if (x > 10) {
  1
} else {
  2
};
// y => 1

for

for (i = 0; i < 10; i++) {
  print(i % 3);
}

演算子

よく使う演算子はだいたい実装してあります。

print(1 + +1); // => 2
print(1 + -1); // => 0
print(1 + 2); // => 3
print(4 - 1); // => 3
print(2 * 4); // => 8
print(2 ** 3); // => 8
print(13 / 3); // => 4
print(13 % 3); // => 1
print(2 * (3 + 4)); // => 14
print(!0); // => 1
print(1 == 2); // => 0
print(1 != 2); // => 1
print(1 < 2); // => 1
print(1 > 2); // => 0
print(1 <= 1); // => 1
print(1 >= 1); // => 1
print(1 && 0); // => 0
print(1 || 0); // => 1

x = 5;
print(++x); // => 6
print(x++); // => 6
print(x--); // => 7
print(--x); // => 5

あとがき

自作言語も Brainfuck も TypeScript も楽しいのでおすすめです。