テンプレート非型メタプログラミングでコンパイル時LISPを書く
人類はちょっと窮屈な言語があったらすぐLISPとかBrainfxxkを作る
前回の記事でC++20でテンプレート非型メタプログラミングが簡単にできるようになって嬉しいねという話をした。まあ実際には型に情報を埋め込んでいるのでこの呼び名はミスリードだが。
やろうと思った直接のきっかけは、以下のライブラリだ。Twitterを見ていたら未踏・Siv3Dや最近はcppmapでも有名なRyo Suzukiさんによって紹介されていた。
これを見て、非型メタプログラミングができるな、ってことは丸括弧の代わりに山括弧を使うコンパイル時LISPが書けるなと思ったのだった。思ったその日に書き始めて、1日目にリストと簡単な関数とその評価ができるようになり、2日目に関数とループが使えるようになってFizzBuzzが動いた。最後の方で触れるが、コンパイル時に走るので実行バイナリにFizzBuzzが埋め込まれていた。その状態で満足したのでその後放置している。
一応コードはそんなに長くないので読めばわかるっちゃわかるが、どうやって動いているのか簡単に説明していこうと思う。ただ、私はLISPを常用しているわけではないので、Lisperが見ると「おいちょっとそれは……」となることをしている可能性はある。あとわかってて妥協してるものがたくさんある。とりあえず動いてはいるが。
ソースコードはこの1ファイルだけ。
lispiny/lispiny.hpp at master · ToruNiina/lispiny · GitHub
cons list
consは前回ちょっと書いたのと同じだ。全てを非型パラメータにするのが目標なので、carとcdrもインライン変数にしている。
template<auto Car, auto Cdr> struct cons_t {}; template<auto Car, auto Cdr> inline constexpr cons_t<Car, Cdr> cons; template<auto Car, auto Cdr> constexpr auto car_helper(cons_t<Car, Cdr>) {return Car;} template<auto Car, auto Cdr> constexpr auto cdr_helper(cons_t<Car, Cdr>) {return Cdr;} template<auto Cons> inline constexpr auto car = car_helper(Cons); template<auto Cons> inline constexpr auto cdr = cdr_helper(Cons);
しばらくこれでやっていたが、途中でcons<1, cons<2, ...>>と書くのがだるくなったのでエイリアスを作った。template<auto ... Elem>とするとそれぞれ異なる型の非型テンプレートパラメータを任意個取ることができる。あとはそれを再帰的に展開すればいい。
template<auto Car, auto ... Cdr> constexpr auto expand_list() { if constexpr (sizeof...(Cdr) == 0) { return cons<Car, nil>; } else { return cons<Car, expand_list<Cdr...>()>; } } template<auto ... Elem> inline constexpr auto list = expand_list<Elem...>();
再帰展開もif constexprで瞬殺できる。便利な時代になったものだ。SFINAEとオーバーロードを使っていた頃が懐かしい。
evalとoperator
関数定義や評価機の前に、足し算などの演算子をどうしたか話しておこう。実際の実装の順序も、リストを作ったあとは電卓を作った。四則演算だけでも「言語処理系感」は出るからだ。義務のない趣味プログラミングではモチベーションを下げないようにすることは重要。
目標としては、以下のコードを動かすことだ。
static_assert(eval<list<plus, 1, 2, 3>> == 6);
リストの先頭が関数の場合、評価すると関数適用が起きるということにしよう。先頭が関数ではないリストを評価しようとするとエラーになって、リストのままにするにはquoteをつけるのが普通だろうが、今回はできるだけ要素を減らしたかったので先頭が関数ではないリストを評価するとそれそのものが帰ってくることにした。結構これは怪しい気がするがなんか動いているのでﾖｼ!
で、実装だが、構造体がapplyというメンバ関数を持っていたら関数適用ができる、ということにした。evalはリストの先頭がapplyを持った構造体かどうかをチェックして、持っていればそれを呼ぶ。
昔はhas_xxxなんかを使って頑張っていたところだが、C++20にはconceptがある。conceptとオーバーロードを使えば、「引数があるメンバ関数を持っているか？」を調べる処理は一瞬で書ける。
template<auto Car, auto Cdr> requires requires {Car.template apply<Cdr>();} constexpr bool is_applicable() { return true; } template<auto Car, auto Cdr> constexpr bool is_applicable() { return false; }
というわけで、evaluateは単に以下のようになった。
- 渡されたものが
consなら、carが関数なら、cdrに適用する。- そうでないなら、
carの評価結果とcdrの評価結果をconsして返す。
- そうでないなら（数値などの場合）、そのまま返す。
template<auto Expr> constexpr auto evaluate() { if constexpr (is_cons<Expr>) { if constexpr (is_applicable<car<Expr>, cdr<Expr>>()) { return evaluate<evaluate<car<Expr>>().template apply<cdr<Expr>>()>(); } else { return cons<evaluate<car<Expr>>(), evaluate<cdr<Expr>>()>; } } else { return Expr; } } template<auto Cons> inline constexpr auto eval = evaluate<Cons>();
で、足し算はこう。apply関数は引数をバラして再帰のための関数に転送している。あとは引数をevalしながら足しつつ再帰。
struct plus_t { template<auto Cons, typename Result> constexpr auto apply_helper(Result x) const { if constexpr(is_nil<cdr<Cons>>) { return x + eval<car<Cons>>; } else { return apply_helper<eval<cdr<Cons>>>(x + eval<car<Cons>>); } } template<auto Cons> constexpr auto apply() const { return apply_helper<eval<cdr<Cons>>>(eval<car<Cons>>); } }; inline constexpr plus_t plus;
実際にはマクロを作って、四則演算とmodを同じ実装で展開している。
関数定義
さて電卓ができたので、続いて関数定義をできるようにしたいと思う。
ラムダは普通引数に名前をつけられるが、今回はダルいので引数の番号を使うことにしよう。
要は、以下のようなコードが動いてほしいわけだ。
constexpr auto plus1 = lambda<list<plus, 1, arg<0>>>; static_assert(eval<list<plus1, 1>> == 2); static_assert(eval<list<plus1, 10>> == 11);
LISPでは関数もリストなので、特別なことをする必要はない。関数適用の際は引数のプレースホルダを実際の引数に入れ替えて評価すればいい。
そのためには、リストのN番目を取ってくる関数と、リスト内のarg<N>を全て置換する関数があればよい。
置換は、
consならcarとcdrについてそれぞれ再帰argなら引数リストから探し出して置換- それ以外（数値など）ならそのまま
でよい。
置換が終わったらそのまま評価する。
// replace all the arg<N> by N-th elem of Args. template<auto Expr, auto Args> constexpr auto substitute() { if constexpr (is_cons<Expr>) { return cons<substitute<car<Expr>, Args>(), substitute<cdr<Expr>, Args>()>; } else if constexpr (is_arg<Expr>) { return find_helper<Args, Expr.value>(); } else { return Expr; } } template<auto Body> struct lambda_t { template<auto Args> constexpr auto apply() const { return eval<substitute<Body, Args>()>; } }; template<auto Body> inline constexpr lambda_t<Body> lambda;
制御構造
分岐は簡単だ。1つめの引数を評価したあと、Tなら2つめの引数を、nilなら3つめの引数を返す関数にすればいい。plusより簡単だと思う。
ループの方はすこし難しい。今回は破壊的代入ができないので、変数の環境をまるごと持ち回ってループの度に新しくする必要がある。
今回は、(while, (env), (cond) (body))というふうにして、最初に変数のリストを、次に変数を受け取ってboolを返す関数を、最後にenvをアップデートする関数を用意することにした。condがenvを受け取ってTを返している間はループが回り続ける。ループ一回につきbodyがenvが受け取って新しいenvを返す。condがnilを返したら、whileが終わってその時点でのenvが帰ってくる。
struct while_t { template<auto Env, auto Cond, auto Body> constexpr auto apply_impl() const { if constexpr (eval<cons<Cond, Env>>) { return apply_impl<eval<cons<Body, Env>>, Cond, Body>(); } else { return Env; } } template<auto Cons> constexpr auto apply() const { return apply_impl< car<Cons>, car<cdr<Cons>>, car<cdr<cdr<Cons>>> >(); } }; inline constexpr while_t while_;
FizzBuzz
上記の他に文字列と、数値を文字列にするビルトイン関数を用意したので、FizzBuzzが書けるようになった。
g++10ではまだ文字列を作るときに丸括弧が必要なのだが、g++11（HEAD）では以下のコードが動くようだ。
constexpr auto result = eval<list<while_, list<1, str<"">>, lambda<list<lt, arg<0>, 20>>, lambda<list< list<plus, arg<0>, 1>, list<plus, arg<1>, list<if_, list<eq, 0, list<modulus, arg<0>, 15>>, str<"FizzBuzz\n">, list<if_, list<eq, 0, list<modulus, arg<0>, 3>>, str<"Fizz\n">, list<if_, list<eq, 0, list<modulus, arg<0>, 5>>, str<"Buzz\n">, list<plus, list<to_string, arg<0>>, str<"\n">> >>>> >>>>; std::cout << car<cdr<result>> << std::endl;
envとしてlist<1, str<"">>を渡している。condはlist<lt, arg<0>, 20>で、envの1つめの要素が20以下であるという条件だ。
bodyは、1つめの要素は1を足したものに変更し、2つめの要素にはFizz, Buzz, FizzBuzz, 数字のどれかを足すというものだ（今回はquoteとかをガン無視して先頭が関数でないリストを評価すると全要素が評価されたリストが返ることになっているのでこれで動いている）。
とりあえずg++-10でも動くように少しだけ書き換えて、
constexpr auto result = eval<list<while_, list<1, str<"">>, lambda<list<lt, arg<0>, 20>>, lambda<list< list<plus, arg<0>, 1>, list<plus, arg<1>, list<if_, list<eq, 0, list<modulus, arg<0>, 15>>, string("FizzBuzz\n"), list<if_, list<eq, 0, list<modulus, arg<0>, 3>>, string("Fizz\n"), list<if_, list<eq, 0, list<modulus, arg<0>, 5>>, string("Buzz\n"), list<plus, list<to_string, arg<0>>, str<"\n">> >>>> >>>>; std::cout << car<cdr<result>> << std::endl;
コンパイルしたあとobjdumpしてみる。
$ objdump -d -j .rodata fizzbuzz
fizzbuzz: file format elf64-x86-64
Disassembly of section .rodata:
0000000000000bc0 <_IO_stdin_used>:
bc0: 01 00 02 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
...
0000000000000be0 <_ZN7lispiny3carIXtlNS_6cons_tIXtlNS_6stringILm73EEEtlA73_cLc49ELc10ELc50ELc10ELc70ELc105ELc122ELc122ELc10ELc52ELc10ELc66ELc117ELc122ELc122ELc10ELc70ELc105ELc122ELc122ELc10ELc55ELc10ELc56ELc10ELc70ELc105ELc122ELc122ELc10ELc66ELc117ELc122ELc122ELc10ELc49ELc49ELc10ELc70ELc105ELc122ELc122ELc10ELc49ELc51ELc10ELc49ELc52ELc10ELc70ELc105ELc122ELc122ELc66ELc117ELc122ELc122ELc10ELc49ELc54ELc10ELc49ELc55ELc10ELc70ELc105ELc122ELc122ELc10ELc49ELc57ELc10EEEELDnEEEEEEE>:
be0: 31 0a 32 0a 46 69 7a 7a 0a 34 0a 42 75 7a 7a 0a 1.2.Fizz.4.Buzz.
bf0: 46 69 7a 7a 0a 37 0a 38 0a 46 69 7a 7a 0a 42 75 Fizz.7.8.Fizz.Bu
c00: 7a 7a 0a 31 31 0a 46 69 7a 7a 0a 31 33 0a 31 34 zz.11.Fizz.13.14
c10: 0a 46 69 7a 7a 42 75 7a 7a 0a 31 36 0a 31 37 0a .FizzBuzz.16.17.
c20: 46 69 7a 7a 0a 31 39 0a 00 Fizz.19..
期待通り、実行バイナリにはFizzBuzzの答えが埋め込まれていた。実行時にこのバイナリがすることは、これを書き出すだけ。というわけでこのコードはコンパイル時に走っている。
おわりに
ずっとC++はコンパイル時計算を支援してきたが、C++20まで来るとコンパイル時計算が本当に簡単になっている。constexpr関数はもう普通の関数と見分けはつかないし（C++14）、ある条件のときしかコンパイルできないコードもconstexpr ifでわけられるのでSFINAEしつつオーバーロードする必要もない（C++17）、ある操作が可能な場合だけ、というようなコンパイル時条件分岐も、その場でコンセプトを書いてオーバーロードすればいい（C++20）。また、C++20ではstd::vectorやstd::string、仮想関数呼び出しがconstexprで使えるようになっている。知る限りまだ実装はないが、そのうち出てくるだろう。
個人的には、今回これを書いてるときは、conceptによってhas_xxxを頑張って書く必要がなくなったのがとてもうれしかった。あと、SFINAEまみれになるときやパラメータパックの再帰展開なんかにif constexprが使えるのが今回とても楽だった。fold expressionのこともあるし、パラメータパックはC++17で完成した感じがあるな。
