KOTET'S PERSONAL BLOG

#dlang Brainfuckを出力する自作言語を作ってAtCoderに参加する

Created: , Last modified:
#dlang #brainfuck #tech

これは1年以上前の記事です

ここに書かれている情報、見解は現在のものとは異なっている場合があります。

Brainfuckはしばしば難解言語と呼ばれます。 Brainfuckをまともに書こうと思う人は少なく、 多くの場合既存のプログラムをコピペしてきて楽しむだけで終わります。 Brainfuck派生言語とかもかなりの割合でHelloWorldしか実行してないんじゃないでしょうか。

そんな世の中でもBrainfuckを使い、それなりにクリエイティビティあふれるプログラムを書く人は存在します。 そういった人々と並ぶことはできなくても、 なにかAtCoderの問題を解いてみるくらいしたいなと思いました。 しかしBrainfuckを手書きできるほど狂人猛者ではないので、 なにか別の言語から変換したいです。

変換ツールはググればいっぱい出てきます。 ELVMなんかはCコンパイラをまるごとBrainfuck化できるらしいので、 これらのツールを使えば一発でしょう。 しかし他人の作ったツールでBrainfuckと関係ない言語を書いているなら、 それは自分の実力でBrainfuckを書いたとは言えないんじゃないかと思ったんです。

そこでBrainfuckを出力するコンパイラを自作して、それでAtCoderの問題を解くことにしました。

Brainfuckを書くために

以下のスライドがわかりやすいです。 というかこのスライドがなかったら自分はこんなことやろうとは思いませんでした。

実用Brainf*ckプログラミング

スライドのなかで触れられているように、Brainfuckはスタックと相性が良い言語です。 スタックマシン向けのコンパイラの書き方はわかっているので、 スタック操作のBrainfuckコードを書くことができれば自動生成ができそうです。

スタック

今回生成するコードでは以下のようなデータ構造を使うことにしました。 0番地から9番地までにスタック構造を構築した図です。

インデックス01234567891011
値001値1値1値1値00

スタック1要素あたり2バイトを使っています。 上のテーブルを元に説明します。 まず、偶数番目はスタック操作のために必要な情報です。 ここが1の場合「前に要素が存在する」という意味になります。 これによってスタックの先頭とスタックの根本を自由に行き来できるようになります。

以下、スタックの操作に必要な情報が入っている部分を操作部、要素の値が入っている部分を値部と呼びます。

0番地からスタックの先頭要素の値部に行くには以下のようにします。 0番地にある0番要素はスタックの根本を表すための番兵要素で、0番要素の値部（1番地）の値に意味はありません。

>> 1番要素の操作部に移動
[>>] スタックの外側（上の例では10番地）まで移動。使っていない番地には0が入っていると仮定している
< 行き過ぎたので戻る

逆にスタック先頭の値部から0番地に行くには以下のようにします。

< 操作部に移動
[<<] 0番地まで移動

とてもシンプルですね。 スタックの根本と先頭を自由に行き来できるようになったので、 スタックの根本より手前にスタックと干渉しない領域を作ることもできます。 つまり、生成するコードでは自由に伸びるスタックと固定長の変数領域の2つが利用できます。

ややこしくなるのでこの記事ではこれ以降出てきませんが、スタックを複数本作ることもできます。 以下は2本のスタックにそれぞれ3、4,5と値が入っている図です。

インデックス012345678910111213
値00001134010500

移動は以下のように>や<の数をスタックの本数分増やして行います。 今自分がどのスタックにいるか見失うと操作ができなくなるので、 操作を行った後は必ず0番スタックに戻ります。

>>>>[>>>>]<< 0番スタックの根本(0番地)から先頭(6番地)に移動
<<[<<<<] 0番スタックの先頭から根本に移動
> 1番スタックの根本に移動
>>>>[>>>>]<< 1番スタックの根本から先頭に移動
<<[<<<<] 0番スタックの先頭から根本に移動
< 0番スタックの根本に戻る

Push & Pop

プログラムの実行中は0番スタックの先頭がホームポジションです。 スタックの先頭で以下の操作を行うとスタックに値を追加したり、取り出したりできます。

ポインタ*
値1値1値1値00000

3を追加します。

>+ 操作部を1にする
> 値部に移動
+++ 3をセット
ポインタ*
値1値1値1値13000

削除します。

[-] 値部をゼロにする
<- 操作部をゼロにする
< 前の要素の値部に移動
ポインタ*
値1値1値1値00000

加減乗算

除算はまだ作ってないです……

加算

4 + 5を計算します。 アルゴリズムはこんな感じになります。

int add(int a, int b)
{
    while (a)
    {
        a--;
        b++;
    }
    return b;
}
ポインタ*
値1415000
[<<+>>-] 前の要素に先頭の値を足す
<-<スタックを1戻す
ポインタ*
値1900000
減算

5 - 2を計算します。 基本は加算と同じです。

ポインタ*
値1512000
[<<->>-]
<-<
ポインタ*
値1300000
乗算

3 * 2を計算します。 スタックの先頭よりも大きい番地を作業領域に使います。 ビジュアライザで動作を見る とカチャカチャ動いて楽しい。

Cで同じことをするとこんな感じになります。

int mul(int a,int b)
{
    int c = 0;
    int d = 0;
    while(a){
        a--;
        while(b)
        {
            b--;
            c++;
            d++;
        }
        while(c)
        {
            c--;
            b++;
        }
    }
    while(d)
    {
        d--;
        a++;
    }
    return a;
}
ポインタ*
値1312000
<<[
    >>[>+>+<<-] 先頭の値を2つの作業領域に移動
    >[<+>-] 1つめだけ書き戻す
    <<<- カウンタ
]
>>>>[<<<<+>>>>-] 2つ目の作業領域に結果が入っているので移動させる
<<[-]<-< 先頭の要素を消去
ポインタ*
値1600000

比較

==しか作ってないです。 スタックの先頭2要素を取り出して、値が同じなら1をPush、違えば0をPushという機能を持ちます。

[<<->>-]<-< 減算
>+ フラグをセット
<[>-<[-]] 差がゼロでない=違う時はフラグをリセットしてゼロにする
>[<+>-]< フラグが立っている=同じ時は1にする

if文

ここで条件式を評価しスタックにPushする
[
    if文の中身。先頭要素をPopしてしまわないように気をつける
[-]] if文終了。スタックの値をゼロにすることで1回でループを抜ける
<-< スタックを縮める

while文

Brainfuckにデフォルトで付属している唯一の制御構文です。 言語機能として組み込まれているだけあって楽にかけます。 条件式の評価をするコードが2箇所に現れます。

ここで条件式を評価しスタックにPushする
[
    [-]<-< スタックから条件式の結果をPop
    while文の中身
    ここで条件式を評価しスタックにPushする
]
<-< スタックを縮める

bflang: DSL for brainf*ck

上のように独立した「部品」をたくさん作ることができたので、 あとはそれを適宜呼び出すコンパイラを作れば完成です。 というわけで完成したものがこちらになります。

kotet/bflang: DSL for brainf*ck

完成と言ってもAtCoderのABCのA問題がなんとか解ける程度の機能しかありません。 まず文字列がないのがつらい……

しかしともかくプログラミングのようなことができる程度の機能があるので、コードを書いてみます。 以下は連続でYと入力された回数を出力するプログラムです。

n = 0;
while (getc() == 'Y')
{
    n = n + 1;
}
putc(n + '0');

そして以下が出力されるコードです。 最適化を全くしていないのでかなり非効率なコードになっています。

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

Pegged: A Parsing Expression Grammar (PEG) module, using the D programming language.

このコンパイラをつくるにあたって、Peggedというパーサジェネレータを使いました。 Cコンパイラを作った時は手書きパーサだったので、初めてのパーサジェネレータということになります。

このように構文をDのソースコードに直接書くと、それを元にしたパーサが使えるようになります。

import pegged.grammar;

mixin(grammar(`
Arithmetic:
    Term     < Factor (Add / Sub)*
    Add      < "+" Factor
    Sub      < "-" Factor
    Factor   < Primary (Mul / Div)*
    Mul      < "*" Primary
    Div      < "/" Primary
    Primary  < Parens / Neg / Pos / Number / Variable
    Parens   < "(" Term ")"
    Neg      < "-" Primary
    Pos      < "+" Primary
    Number   < ~([0-9]+)

    Variable <- identifier
`));

渡された構文の文字列をコンパイル時に解析して、コンパイル時に生成したコードを使います。 やっぱりライブラリとして整備されたパーサは便利でした。 writelnするだけで構文木全体がわかりやすく出力される機能には助けられた……

問題を解いてみる

そういうわけでできたコンパイラを使って問題を1問解いてみました。

提出 #4023935 - AtCoder Beginner Contest 115

計算量とか一切気にしないでとりあえず動くことだけを目標に作った割には実行時間が短いです。 高速なBrainfuck処理系の作者に感謝。

文字列とか除算とか多倍長整数とか欲しい機能はいっぱいありますが、 気力が尽きてきたので生成されたコードの動きをビジュアライザで眺めて余生を過ごそうと思います。