嗚呼、帰りたい

プログラミングのことから日常のことまで。いわゆるごった煮というものだな。

コンパイル時brainfuckインタプリタを作った話

この記事はあくあたん工房 Advent Calendar 2021の12日目の記事です

なおこの記事が執筆されたのは12月31日です

大学の必修の課題が重かったんだ...許しておくれ...
なお年内に間に合わせるために色々妥協したのでクオリティについてはお察しください

C++コンパイル時計算

C++は広く知られた言語ですが,その機能の一つにコンパイル時計算というものがあります.読んで字のごとく,コンパイルの最中に計算する機能です.この記事はコンパイル時計算を説明する記事ではないので詳細な説明は省きますが,例えば次のような関数があったとして

// C++14
constexpr int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

次のように変数に代入したりすると

constexpr int a = fib(10);

コンパイラによって生成されたバイナリでは fib(10) の呼び出しが無くなり,その計算結果である 55 が直接埋め込まれます.

さて,このコンパイル時計算を使うと面白そうなことができそうな気がしますね.ということでコンパイル時にbrainfuckを実行するプログラムを作ってみました.

コンパイルbrainfuckインタプリタ

今回はC++17を使ってプログラムを作りました.まずはプログラム全体をお見せしましょう.

ちょっと長いので折り畳み

brainfuck::interpreter<InputPtr, ProgramPtr> がその名の通りインタプリタとなっていて,第一引数の InputPtr に入力文字列へのポインタを,第二引数の ProgramPtr にプログラムの文字列へのポインタを受け取ります.私の理解が正しければ,template引数に課せられた制約の都合上,これらの引数はグローバル変数として宣言されている必要があります.

brainfuck::interpreter<InputPtr, ProgramPtr>result に実行結果を,output に出力用の uint8_t 配列を格納します.それぞれについて詳しく見ていきましょう.

result

C++17ではconstexprの文脈でラムダ式を使うことができるのでその機能を活用しています.また,C++17から導入された std::variant (型安全なunionみたいなもの) を使って,result に出力結果かエラーコードを格納しています.出力についてコンパイル時には標準出力を利用することができないので,代わりに特定の長さで配列を確保しておいて順次そこに書き込むようにしており,エラーについてもコンパイル時に標準出力を利用できない都合上エラーコードを返すような設計としています.他に特筆するべき部分はなく,brainfuckプログラムが適格か確認したり,一個一個コマンドを解釈して実行していたりするぐらいです.

output

output は生成された result を基に,出力の余分な部分を切り詰めたり,エラーコード別にコンパイルエラーを出す処理を行ったりします.ある意味コンパイル時計算の威力が最も発揮される部分かもしれません.

static constexpr inline auto output = [] {
    if constexpr (result.index() == 0) {
        constexpr auto buf = std::get<0>(result);
        std::array<uint8_t, buf.second> ret = { };
        for (size_t i = 0; i < buf.second; i++) {
            ret[i] = buf.first[i];
        }
        return ret;
    } else {
        constexpr auto error = std::get<1>(result);
        if constexpr (error == error_reason::MISMATCHING_SQUARE_PARENTHESIS) {
            static_assert(false_v<>, "mismatching square parenthesis");
        } else if constexpr (error == error_reason::TRIED_TO_ACCESS_OUT_OF_INPUT_RANGE) {
            static_assert(false_v<>, "tried to access out of input range");
        } else if constexpr (error == error_reason::TRIED_TO_ACCESS_OUT_OF_CELLS_RANGE) {
            static_assert(false_v<>, "tried to access out of memory range");
        } else if constexpr (error == error_reason::OUTPUT_CAPACITY_IS_TOO_SMALL) {
            static_assert(false_v<>, "output capacity is too small");
        } else {
            static_assert(false_v<>, "unhandled error!");
        }
    }
}();

C++17ではconstexpr if文を使ってコンパイル時に定数式の結果に応じて処理内容を変えることができます.上に示したコードはインタプリタのコードから output の部分を抜き出してきたものですが,if constexpr (result.index() == 0) で処理を切り分けているのが分かると思います.この例では resultコンパイル時に計算されてしまっているのでその結果を利用することができ,もし result.index() == 0 が成立したら,すなわち result に出力結果が格納されている場合はバイナリには条件が真のときに実行される処理のみが残され,逆に result.index() == 0 が成立しなかったら,すなわち result にエラーコードが格納されている場合はバイナリには条件が偽のときに実行される処理のみが残されます.一見メリットが分かりにくいかもしれませんが,これを応用することで次のようなコードが実現できたりします.

template<typename T>
constexpr auto func(const T &n) {
    if constexpr (std::is_arithmetic_v<T>) { // Tが算術型かどうか
        return n * 2; // 2倍した値を返す
    } else { // 上と下とで返り値の型が違う!
        return "value is not arithmetic"; // 2倍できない旨を返す
    }
} 

int main()
{
    std::cout << func(42) << std::endl; // 84
    std::cout << func("Hello, world!") << std::endl; // value is not arithmetic
}

output の例では result.index() == 0 でない場合は値を返さずに static_assertコンパイルエラーにします.result に格納されているエラーコード別にメッセージを変えているというのがなんとなくわかると思います.

実行してみた

作ったインタプリタが実際に動くかどうかを確認してみました.実行したbrainfuckのプログラムは Hello world! を出力する次のコードです.

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

結果として次のような出力が得られました.とりあえず問題なく動作している様子が確認できました.

Hello world!

本当にコンパイル時に実行しているのか

動作している様子が確認できているとはいえ,実行されているタイミングがコンパイル時でないことを確認できないことには意味がありません.そこで g++ -Sアセンブリを出力させてみます.以下に main関数に対応する(と思われる)アセンブリを載せます.アセンブリには慣れてないので間違ってたらごめんなさい.

長いので折り畳み

main:
.LFB2057:
    .cfi_startproc
    endbr64
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq %rsp, %rbp
    .cfi_def_cfa_register 6
    subq $64, %rsp
    movq %fs:40, %rax
    movq %rax, -8(%rbp)
    xorl %eax, %eax
    movb $72, -20(%rbp)
    movb $101, -19(%rbp)
    movb $108, -18(%rbp)
    movb $108, -17(%rbp)
    movb $111, -16(%rbp)
    movb $32, -15(%rbp)
    movb $87, -14(%rbp)
    movb $111, -13(%rbp)
    movb $114, -12(%rbp)
    movb $108, -11(%rbp)
    movb $100, -10(%rbp)
    movb $33, -9(%rbp)
    leaq -20(%rbp), %rax
    movq %rax, -48(%rbp)
    movq -48(%rbp), %rax
    movq %rax, %rdi
    call _ZNKSt5arrayIhLm12EE5beginEv
    movq %rax, -56(%rbp)
    movq -48(%rbp), %rax
    movq %rax, %rdi
    call _ZNKSt5arrayIhLm12EE3endEv
    movq %rax, -40(%rbp)
.L3:
    movq -56(%rbp), %rax
    cmpq -40(%rbp), %rax
    je   .L2
    movq -56(%rbp), %rax
    movq %rax, -32(%rbp)
    movq -32(%rbp), %rax
    movzbl   (%rax), %eax
    movsbl   %al, %eax
    movl %eax, %esi
    leaq _ZSt4cout(%rip), %rdi
    call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_c@PLT
    addq $1, -56(%rbp)
    jmp  .L3
.L2:
    movl $0, %eax
    movq -8(%rbp), %rdx
    xorq %fs:40, %rdx
    je   .L5
    call __stack_chk_fail@PLT
.L5:
    leave
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc

上のアセンブリのうち,以下に示す部分

    movb $72, -20(%rbp)
    movb $101, -19(%rbp)
    movb $108, -18(%rbp)
    movb $108, -17(%rbp)
    movb $111, -16(%rbp)
    movb $32, -15(%rbp)
    movb $87, -14(%rbp)
    movb $111, -13(%rbp)
    movb $114, -12(%rbp)
    movb $108, -11(%rbp)
    movb $100, -10(%rbp)
    movb $33, -9(%rbp)

Hello world! に対応するバイト列 72 101 108 108 111 32 87 111 114 108 100 33 が即値で埋め込まれているのが確認できます.どうやら本当にコンパイル時に処理ができているようです.

制約

コンパイル時に動作する都合上,このインタプリタコンパイラの制約を受けます.特にGCCの場合は -fconstexpr-loop-limit-fconstexpr-ops-limit でループや演算の回数が縛られます.まあこれらの数値は大きくすることができますが,その分だけコンパイルにかかる時間が伸びますし,brainfuckのプログラムが無限にループしている場合は先ほどの数値を大きくしてもコンパイルできません.まあでもお遊び程度でbrainfuckのプログラムを実行させるならほとんど引っかかることはないんじゃないでしょうか.

まとめ

コンパイル時にbrainfuckを実行するインタプリタを作成しました.C++は規格が新しくなるたびにコンパイル時計算ができる処理が増えていっていることもあり,C++17の時点でもかなり楽にコンパイル時計算が書ける印象があります.実際,brainfuckインタプリタを作る過程でもそこまで悩むことはありませんでした.この記事を読んでコンパイル時計算に興味を持った人(そんな人おるんかな)がいたらまずは副作用のない関数から順次 constexpr をつけていくといいんじゃないですかね.

最後までお読みいただきありがとうございました.