C--(あるいはCmm)を中間表現とするBrainf*ckコンパイラを作成する - (1) 人力コンパイル

C--(あるいはCmm)を中間表現とするBrainf*ckコンパイラを作成する

はじめに

GHCではHaskellのソースコードをコンパイルするときに、いくつかの中間コードを経由する。

    Haskell -> Core言語 -> STG言語 -> C--(Cmm) -> アセンブリ言語 -> 機械語

C--(Cmm)を理解する第一歩として、これを中間言語とするBrainf*ckコンパイラを作成してみる。つぎのように、段階的に実装していく予定だ。

• Brainf*ckのコードを人力でCmmにコンパイルして、GHCで実行可能ファイルを作成する(この記事)
• Brainf*ckの(Cmmへの)コンパイラをGHCで作成する(現在は、ここまで)
  • テキストファイルとしてCmmのソースコードを出力する
• テキストファイルとして出力するのではなく、Cmmの(GHC内で使われる)構文木を生成して、直接、実行可能ファイルを生成する
• 生成されるCmmを最適化されたものにする
  • +や-のn個の連続を、それぞれ、値にnたす、値からnひく命令として解釈する
  • メモリへの最初の+や-、そして[-]のあとの+や-を、たし算や引き算ではなく、メモリへの代入として処理する
  • 出力のバッファリング
    • Brainf*ckの文法を拡張して、バッファをフラッシュする命令を追加する
    • 実際の出力はバッファをフラッシュするか、処理がすべて終了したときに、おこなわれることにする
  • 入力のバッファリング
    • 実際の入力を入力先のメモリが実際に使われるときまで遅延させる
    • どのメモリに何番目の入力が対応しているかの情報を保存しておく必要がある

想定される読者

• Haskellの処理系であるGHCをStackでインストールしてある
• Haskellはだいたい読める
• x86-64上で64ビットリナックスを使用している
• 言語処理系に興味がある
• 難解プログラミング言語に興味がある

C--とは

C--とは何かについては以下をごらんください。

C--で末尾再帰の最適化を試してみる

Brainf*ckとは

Brainf*ckは難解プログラミング言語(esolang)のひとつ。ジョークとして作られた言語。すくなくとも30000バイトのメモリ領域と、そのなかの1バイトを指すひとつのポインタと、つぎの8つの命令をもつ。

• : ポインタをひとつ進める

• <: ポインタをひとつもどす
• +: ポインタの指すメモリの値を1ふやす
• -: ポインタの指すメモリの値を1へらす
• .: ポインタの指すメモリの値(1バイト)を出力する
• ,: 入力された値(1バイト)をポインタの指すメモリに代入する
• [: ポインタの指すメモリの値が0ならば、対応する]にジャンプする
• ]: ポインタの指すメモリの値が0でなければ、対応する[にジャンプする

初期状態では、メモリ領域の値はすべて0であり、ポインタはメモリの先頭を指す。また、上記8つの記号以外がソースコードに含まれていた場合、それらを無視する。Brainf*ckはチューリング完全である。つまり、入出力の方法が限られていることを除けば、コンピュータにできることは何でもできるということになる。

コード例

Hello, world!

Hello, worldを出力するコードはつぎのようになる。

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

基本的に、やっていることは'H'を表す72までメモリの値をふやしていき、.でそれを表示している。ただし、上記の実装では「くりかえし」や「複数のメモリ領域を上手に利用す」ることによって、コードを短くしている。たとえば、'H'を表示するには72回、+命令を実行したあと.命令を実行すればいいけれど、ループを使って8回の+命令を9回くりかえすほうが効率がいい。そのようなやりかたで'H'を表示するコード例を示す。

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

順をおって考えてみよう。まずメモリ0を9回、インクリメントする。そしてループのなかに入る。ループのなかでは、まずはポインタを進め、メモリ1を8回インクリメントする。そしてポインタをもどし、メモリ0をデクリメントする。メモリ0の値が0より大きい(8)ので、ループを再度実行する。これは、メモリ0が0になるまで、くりかえされる。この結果、メモリ1は8インクリメントされる処理が9回行われるので、72になる。そして、ポインタを進めて、メモリ1を指すようにして、1文字出力する。これで'H'が出力される。

はじめのHello, world!を表示するコードでは、メモリ1を72に設定するループのなかで、同時にメモリ2を99に、メモリ3を45にしている。それぞれ小文字と記号を出力するために、近い値に設定しているということだ。メモリ2を2回、インクリメントすることで101として'e'を表示したり、メモリ3を1回、デクリメントすることで44として','を表示したりしている。

echo

入力をそのまま出力するコードは、つぎのようになる。

+[>,.<]

まずはメモリ0の値を1にする。それからループに入り、ループ内ではメモリ1に入力された1文字を代入し、それを表示している。ループの先頭と終わりでは、ポインタがメモリ0を指すようになっていて、これは変化せず、つねに1なので無限ループになる。

何をするか

Brainf*ckをC--にコンパイルしたうえで、実行可能ファイルに変換する。

設計

• メモリ領域を30000バイト確保する
• その領域を指すポインタにはレジスタR2を使う
• ループにはC--のブロックとjump命令を使う

たとえば、つぎのようなBrainf*ckのコードがあったとする。

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

これは、つぎのようなC--のコードにコンパイルされる。

fun()
{
        bits8[R2] = bits8[R2] + 1;
        bits8[R2] = bits8[R2] + 1;
        bits8[R2] = bits8[R2] + 1;
        call fun_1();
        bits8[R2] = bits8[R2] + 1;
        bits8[R2] = bits8[R2] + 1;
}

fun_1()
{
        if (bits8[R2] > 0) {
                R2 = R2 + 1;
                bits8[R2] = bits8[R2] + 1;
                bits8[R2] = bits8[R2] + 1;
                R2 = R2 - 1;
                bits8[R2] = bits8[R2] - 1;
                jump fun_1();
        } else {
                return();
        }
}

サンプルコード

サンプルコードは、つぎのリンクから取得できる。

GitHub: cmm/qiita/brainf-cmm/brainf-cmm-hand

人力コンパイル

小さなコードを人力コンパイルして、C--のソースコードを作成し、それを実行可能形式に変換してみる。

C--の関数を呼び出すC言語のソースコード

C--の関数を呼び出すC言語のソースコードを作成する。

call_cmm.c

# include <stdio.h>

int
main(int argc, char *argv[])
{
        unsigned int r;

        __asm__(
                "addq $-16, %%rsp\n\t"
                "movq %%rbp, 8(%%rsp)\n\t"
                "movq %%rsp, %%rbp\n\t"
                "movq $ret, (%%rbp)\n\t"
                "jmp cmm_main\n"
        "ret:\n\t"
                "movq 8(%%rsp), %%rbp\n\t"
                "addq $16, %%rsp\n"
        : "=b"(r)
        :
        : );

        printf("return value: %d\n", r);
        return 0;
}

解説は以下を参照。

C--で末尾再帰の最適化を試してみる - C言語の関数から呼び出す

つぎのサンプルのC--で試してみよう。

sample.cmm

cmm_main()
{
        return(123);
}

% stack ghc -- -no-hs-main call_cmm.c sample.cmm -o sample
% ./sample
return value: 123

ポインタやメモリの操作

メモリの確保は、つぎのようにする。

memory.cmm

section "data"
{
        memory: bits8[30000];
}

レジスタR2がこのメモリ領域の先頭を指すようにしてみよう。つぎのコードを追加する。

memory.cmm

cmm_main()
{
        R2 = memory;
        return(R2);
}

コンパイルして実行する。

% stack ghc -- -no-hs-main call_cmm.c memory.cmm -o memory
% ./memory
return value: 4903424

ここで、つぎのようなコードを人力でコンパイルしてみよう。

++>++++<

つぎのようになる。

inc.cmm

section "data"
{
        memory: bits8[30000];
}

cmm_main()
{
        R2 = memory;

        bits8[R2] = bits8[R2] + 1;
        bits8[R2] = bits8[R2] + 1;
        R2 = R2 + 1;
        bits8[R2] = bits8[R2] + 1;
        bits8[R2] = bits8[R2] + 1;
        bits8[R2] = bits8[R2] + 1;
        bits8[R2] = bits8[R2] + 1;
        R2 = R2 - 1;

        return(bits8[R2]);
}

レジスタR2の指すアドレスから1バイトの数値を取り出すのに、つぎのような記法が使われている。

bits8[R2]

結果を見るために現在ポインタが指しているメモリの値を返り値にしておいた。call_cmm.cでcmm_mainからの返り値を受けとる変数rをunsigned intからunsigned charに修正しておく。

call_cmm.c

# include <stdio.h>

int main(int argc, char *argv[])
{
        unsigned char r;
...

コンパイルして実行する。

% stack ghc -- -no-hs-main call_cmm.c inc.cmm -o inc
% ./inc
return value: 2

予想通り「2」がかえる。

ループ

つぎに、ループをどう表現するかを示す。つぎのようなコードを人力でコンパイルしてみよう。

++[>+++<-]>

つぎのようになる。

loop.cmm

section "data"
{
        memory: bits8[30000];
}

cmm_main()
{
        R2 = memory;

        bits8[R2] = bits8[R2] + 1;
        bits8[R2] = bits8[R2] + 1;
        call loop();
        R2 = R2 + 1;

        return(bits8[R2]);
}

loop()
{
        if (bits8[R2] > 0) {
                R2 = R2 + 1;
                bits8[R2] = bits8[R2] + 1;
                bits8[R2] = bits8[R2] + 1;
                bits8[R2] = bits8[R2] + 1;
                R2 = R2 - 1;
                bits8[R2] = bits8[R2] - 1;
                jump loop();
        } else {
                return();
        }
}

ループはC--のブロックで表現した。bits8[R2]が0でないあいだ、そのブロック自身にジャンプする。コンパイルして実行する。

% stack ghc -- -no-hs-main call_cmm.c loop.cmm -o loop
% ./loop
return value: 6

予想通り、6がかえる。

出力と入力

1文字出力と1文字入力については、OSのシステムコールを使用する。アセンブリ言語でputchar_syscallとgetchar_syscallを作成する。

システムコールについて

プロセスがOSの用意した機能を呼び出す場合、通常のジャンプ命令ではなくシステムコールというやりかたが使われる。たとえばコンソールに文字を表示するときなどにも、それぞれの言語の関数にラップされているにしても、最終的にはシステムコールが行われている。

システムコールは指定されたレジスタにシステムコールの番号や引数を設定したうえで、syscall命令を発行することで行われる。

putchar_syscall

putchar_syscallという手続きを作成する。システムコールwriteを呼び出す。このシステムコールの番号や引数と対応するレジスタは、つぎのようになる。

• rax: システムコール番号、writeでは1
• rdi: ファイルディスクリプタ、stdoutでは1
• rsi: 文字列を格納しているメモリの先頭番地
• rdx: 書き出す文字数

まずは、文字列を格納するメモリの領域を確保する。

io.s

        .comm ch,1

手続きputchar_syscallを作成する。

io.s

        .global putchar_syscall
putchar_syscall:
        movb %bl, ch(%rip)
        movq $1, %rax
        movq $1, %rdi
        movq $ch, %rsi
        movq $1, %rdx
        syscall
        xorq %rbx, %rbx
        jmp *(%rbp)

はじめの1行ではputchar_syscallへの引数をメモリ領域chに保存している。C--では第1引数はR1(%rbx)でわたされる。つづく5行では、システムコールwriteの番号と、それぞれの引数とを設定して、syscall命令を発行している。C--では返り値をわたすのにもR1(%rbx)が使われる。ここでは0クリア(xorq %rbx, %rbx)している。そのうえでjmp命令でSp(%rbp)で示されるスタックの先頭に保存された、もどりアドレスに処理をもどす。

getchar_syscall

getchar_syscallではシステムコールreadを使う。その番号と引数とレジスタの対応は、つぎのようになる。

• rax: システムコール番号、readでは0
• rdi: ファイルディスクリプタ、stdinでは0
• rsi: 文字列を格納するメモリの先頭番地
• rdx: 読み込む文字数

getchar_syscallを作成する。

io.s

        .global getchar_syscall
getchar_syscall:
        movq $0, %rax
        movq $0, %rdi
        movq $ch, %rsi
        movq $1, %rdx
        syscall
        xorq %rbx, %rbx
        movb ch(%rip), %bl
        jmp *(%rbp)

手続きputchar_syscallとだいたいおなじだ。システムコールを呼んだあと、入力が読み込まれたメモリ領域からレジスタ%rbxに値をコピーしている。64ビットレジスタである%rbxの下位8ビットしか使用しないので、コピーする前に%rbxを0クリアしている。

例

つぎのようなコードを人力でコンパイルしてみよう。

+[>,.<]

echo.cmm

section "data"
{
        memory: bits8[30000];
}

cmm_main()
{
        R2 = memory;

        bits8[R2] = bits8[R2] + 1;
        call loop();

        return(bits8[R2]);
}

loop()
{
        if (bits8[R2] > 0) {
                R2 = R2 + 1;
                (bits8 r) = call getchar_syscall(); bits8[R2] = r;
                call putchar_syscall(bits8[R2]);
                R2 = R2 - 1;
                jump loop();
        } else {
                return();
        }
}

getchar_syscall()の結果をbits8[R2]に代入している。つづけて、bits8[R2]の値を引数にしてputchar_syscallを呼び出している。コンパイルして実行してみよう。

% stack ghc -- -no-hs-main call_cmm.c io.s echo.cmm -o echo
% ./echo
hello
hello
world
world
(Ctrl-C)

まとめ

Brainf*ckのソースコードを、手作業でCmmにコンパイルして、GHCで実行可能ファイルに変換した。cmm_mainを呼び出すCのmain関数を作成した。また、1文字の出力/入力を担当するルーチンをアセンブリ言語で作成した。C言語の入出力関数を利用せずに、システムコールを直接呼び出した。これは、Cmmの関数とCの関数とでレジスタの使いかたなどが異なるため、CmmからのCの関数の呼び出しのときに、ときどき不具合が生じたためだ。

つぎの記事では、人力でおこなっていたBrainfckからCmmへのコンパイルの部分をHaskellで実装する。Brainfckの構文解析部分は、手作りの簡易的なパーサを使う。

「(2) コンパイラの作成」へ