コンパイル時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
をつけていくといいんじゃないですかね.
最後までお読みいただきありがとうございました.