Brainfuck にコンパイル可能な高水準プログラミング言語を作った
はじめに
少し前ですが、Brainfuck にコンパイル可能な Bigbrain という言語を作ったので紹介します。Brainfuck はチューリング完全であることが知られていますが、Brainfuck で演算や制御命令を表現するのは難易度が高いです。Bigbrain はその複雑さを隠蔽し、人間にやさしい構文でプログラムを書き Brainfuck にコンパイルすることができる言語です。
Bigbrain のコンパイラは TypeScript で書かれており、0 dependencies かつランタイム依存な API も使用していないので、Node.js や Deno、ブラウザ上などで動かすことも可能です。
Bigbrain は Web アプリ上、もしくは GitHub からリポジトリを clone して試すことができます。実用されることは考えてないので npm には publish していません（もし要望があればします）。
Getting started
Bigbrain で 1 から 30 までの値を出力する FizzBuzz を書くと次のようになります。
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
if や for は C-like なシンタックスの言語を書いたことがある方は見慣れていると思うので説明は省きます。
putchar は引数に与えられた値が指す文字を出力する built-in 関数で、Brainfuck の . 命令に該当します。例えば 102 は f を指すので、putchar(102) は f を出力します。同様に、105 は i、122 は z… のように出力されるので、次のコードでは fizzbuzz が出力されることになります。
putchar(102); // f
putchar(105); // i
putchar(122); // z
putchar(122); // z
putchar(98); // b
putchar(117); // u
putchar(122); // z
putchar(122); // z
// 10 は改行
putchar(10); // \n
print は引数に与えられた値をそのまま 10 進数表記で出力する built-in 関数です。例えば print(102) は 102 を出力します。このような命令は Brainfuck にはありませんが、102 という値から 1、0、2 とそれぞれ出力するのは大変なので便利関数として提供しています。
print(102); // 102
シンタックスのすべては README に記載していますが、簡単に紹介すると Brainfuck の , 命令に該当する input 関数や、基本的な算術演算子、比較演算子、論理演算子などが使えます。関数の定義、構造体、配列などはサポートしていません（関数は欲しいところですが、Brainfuck で表現するのがかなり困難だったので諦めました）。
実装の話
普通のコンパイラと同じように、字句解析、構文解析、コード生成をしています。特筆すべきなのは、Bigbrain のコンパイラは C などのコンパイラと違いアセンブリではなく Brainfuck のコードを出力する必要がある点です。Brainfuck には便利な演算子や制御命令はなく、8 種類の命令だけでこれらの機能を実装する必要があります。Brainfuck での演算のアルゴリズムは Esolang の記事が参考になりました。
実装の簡単さを優先しているので最適化はあまりされていませんが、出力するコードのサイズを抑える工夫は少ししていて、例えば 23 のようなリテラルから値をつくるときには + を 23 回繰り返すのではなく、4 * 6 - 1 という演算をするコードに置き換えるようにしています。Brainfuck では 0 から 255 までの値を扱うことができるので、それぞれの値で最もコードのサイズが小さくなるような算出方法をあらかじめ列挙しています。
+++++++++++++++++++++++ // 23
>++++[<++++++>-]<- // 4 * 6 - 1
おわり
Bigbrain の名前の由来は海外のスラングです。「賢い」「天才」みたいな意味だと思います。
Discussion