プリプロセッサで再帰しましょう！
みなさまいかがお過ごしでしょうか？さて、今日のテーマは「再帰」です。プリプロセッサでは再帰が扱えないので、例えば、
#define PP_APPLY(f, x) f(x) #define HOGE(x) PP_APPLY(PIYO, x)
という定義があったとして、
PP_APPLY(HOGE, FUGA)
とか書いてあるとPIYO(FUGA)にはならないわけです。でもなってほしいのです。なってほしいのでなんとかやってみましょう、というのが今回の主旨です。では始めましょう。
#define PP_APPLY(f, x) f(x)
これは一度しか展開できません。f(x)を展開した結果、PP_APPLY(なんたら)になっても、もう二度と展開はしてくれないのです…なので、
#define PP_APPLY_1(f, x) f(x) #define PP_APPLY_2(f, x) f(x) #define PP_APPLY_3(f, x) f(x) #define PP_APPLY_4(f, x) f(x)
こういう風にすると1, 2, 3, 4で1回ずつ、計4回展開できます。これで、
#define HOGE(x) PP_APPLY_1(PIYO, x) PP_APPLY_2(HOGE, FUGA)
とかやれば再帰っぽくできるでしょ？終わり。
んなわけがないでしょう…なんてhuman unfriendly。これではいけません。PP_APPLYが自動的にPP_APPLY_nになればいいのですから、やってみましょう。
「おいぃだから関数マクロは一度展開したらその中では展開できないというのをさっきの例で見ただろうこのbird-brainが！」などというのは早計です。自分の展開結果に自分がでてこなければいいのです。
#define PP_APPLY PP_LOOKUP_UNEXPANDED_APPLY_1() #define PP_LOOKUP_UNEXPANDED_APPLY_1() PP_IF(PP_CAT(PP_CHECK_APPLY_, PP_APPLY_1(PP_CHECK_APPLY_F, PP_NIL)), PP_APPLY_1, PP_LOOKUP_UNEXPANDED_APPLY_2()) #define PP_LOOKUP_UNEXPANDED_APPLY_2() PP_IF(PP_CAT(PP_CHECK_APPLY_, PP_APPLY_2(PP_CHECK_APPLY_F, PP_NIL)), PP_APPLY_2, PP_LOOKUP_UNEXPANDED_APPLY_3()) #define PP_LOOKUP_UNEXPANDED_APPLY_3() PP_IF(PP_CAT(PP_CHECK_APPLY_, PP_APPLY_3(PP_CHECK_APPLY_F, PP_NIL)), PP_APPLY_3, PP_LOOKUP_UNEXPANDED_APPLY_4()) #define PP_LOOKUP_UNEXPANDED_APPLY_4() PP_IF(PP_CAT(PP_CHECK_APPLY_, PP_APPLY_4(PP_CHECK_APPLY_F, PP_NIL)), PP_APPLY_4, PP_LOOKUP_ERROR) #define PP_CHECK_APPLY_F(_) PP_UNEXPANDED_APPLY #define PP_CHECK_APPLY_PP_UNEXPANDED_APPLY 1 #define PP_CHECK_APPLY_PP_APPLY_1(f, x) 0 #define PP_CHECK_APPLY_PP_APPLY_2(f, x) 0 #define PP_CHECK_APPLY_PP_APPLY_3(f, x) 0 #define PP_CHECK_APPLY_PP_APPLY_4(f, x) 0 #define PP_APPLY_1(f, x) f(x) #define PP_APPLY_2(f, x) f(x) #define PP_APPLY_3(f, x) f(x) #define PP_APPLY_4(f, x) f(x) #define PP_CAT(a, b) PP_CAT_I(a, b) #define PP_CAT_I(a, b) a ## b #define PP_IF(c, t, f) PP_IF_I(c, t, f) #define PP_IF_I(c, t, f) PP_IF_ ## c(t, f) #define PP_IF_0(t, f) f #define PP_IF_1(t, f) t #define F(x) PP_APPLY(x, x) #define G(_) SUCCEEDED! PP_APPLY(F, G)
最後の一行、PP_APPLY(F, G)がどのように展開されるのか見ていきましょう。まず、PP_APPLYは関数形式ではないマクロです。PP_APPLYの展開中にPP_APPLYという名前が再度現れることもないので、このマクロは常に必ず展開できます。では次のポイントです。
PP_IF(
PP_CAT(PP_CHECK_APPLY_,
PP_APPLY_1(PP_CHECK_APPLY_F,
PP_NIL)),
PP_APPLY_1,
PP_LOOKUP_UNEXPANDED_APPLY_2())PP_LOOKUP_UNEXPANDED_APPLY_1の本体です（改行を適当に入れました）。PP_CATは二つの引数を連結しますが、連結前に引数を全て展開します。PP_CATの二つ目の引数、PP_APPLY_1(CHECK_PP_APPLY_F, PP_NIL)を展開すると、途中省略して、PP_UNEXPANDED_APPLYとなります。そのあとで結合されて、PP_CHECK_APPLY_PP_UNEXPANDED_APPLYとなり、最後は1と展開されます。よってPP_IFはPP_APPLY_1と展開されます。なのでPP_APPLYもPP_APPLY_1になります。ということで、PP_APPLY(F, G)は、PP_APPLY_1(F, G)となり、いい塩梅に展開されています。PP_APPLY_1(F, G)はちょっと中略して、PP_APPLY(G, G)と展開されます。PP_APPLYは常に展開できるので、PP_LOOKUP_UNEXPANDED_APPLY_1()となって、またPP_CAT(PP_CHECK_APPLY〜を展開するわけですが、PP_APPLY_1は既に展開済みなので、展開されないままPP_CATが結合してしまいます。つまりPP_CHECK_APPLY_PP_APPLY_1(PP_CHECK_APPLY_F, PP_NIL)と展開されます。PP_CHECK_APPLY_PP_APPLY_1(f, x)は0です。そう、PP_APPLY_1が展開できれば1、そうでなければ0となるのです！これを考えた人はとても紳士ですね。結局、PP_UNEXPANDED_APPLY1()はPP_UNEXPANDED_APPLY_2()の結果に展開されて、あとはだいたい同じでPP_APPLY_2(G, G)となり、途中省略してSUCCEEDED!と展開されます。つまりまPP_APPLYは、まだ展開されていない番号のPP_APPLY_nが見つかるまでPP_UNEXPANDED_nを繰り返します。ただし、PP_APPLY_4が展開できなければもうそれ以上書いてなくて無理なので、残念マークを結果とします。
では早速展開してみましょう。
http://codepad.org/cn07cWah
はい、見事に再帰っぽい現象が起きていますね。ついでにこの、未展開な関数マクロ探索システムだけ取り出して、使い回せるようにしてみましょう。
#define PP_AUTO_REC(p) PP_LOOKUP_UNEXPANDED_1(p) #define PP_LOOKUP_UNEXPANDED_1(p) PP_IF(p(1), 1 PP_EAT, PP_LOOKUP_UNEXPANDED_2)(p) #define PP_LOOKUP_UNEXPANDED_2(p) PP_IF(p(2), 2 PP_EAT, PP_LOOKUP_UNEXPANDED_3)(p) #define PP_LOOKUP_UNEXPANDED_3(p) PP_IF(p(3), 3 PP_EAT, PP_LOOKUP_UNEXPANDED_4)(p) #define PP_LOOKUP_UNEXPANDED_4(p) PP_IF(p(4), 4, PP_LOOKUP_LOOKUP_ERROR) #define PP_EAT(_) #define PP_APPLY PP_CAT(PP_APPLY_, PP_AUTO_REC(PP_CHECK_APPLY)) #define PP_APPLY_1(f, x) f(x) #define PP_APPLY_2(f, x) f(x) #define PP_APPLY_3(f, x) f(x) #define PP_APPLY_4(f, x) f(x) #define PP_CHECK_APPLY(n) PP_CAT(PP_CHECK_APPLY_, PP_APPLY_ ## n(PP_CHECK_APPLY_OP, PP_NIL)) #define PP_CHECK_APPLY_OP(_) PP_NIL #define PP_CHECK_APPLY_PP_NIL 1 #define PP_CHECK_APPLY_PP_APPLY_1(f, x) 0 #define PP_CHECK_APPLY_PP_APPLY_2(f, x) 0 #define PP_CHECK_APPLY_PP_APPLY_3(f, x) 0 #define PP_CAT(a, b) PP_CAT_I(a, b) #define PP_CAT_I(a, b) a ## b #define PP_IF(c, t, f) PP_IF_I(c, t, f) #define PP_IF_I(c, t, f) PP_IF_ ## c(t, f) #define PP_IF_0(t, f) f #define PP_IF_1(t, f) t #define F(x) PP_APPLY(x, x) #define G(_) SUCCEEDED! PP_APPLY(F, G)
PP_EATまでが取り出したコードです。全然関係ないですが、今回はパフォーマンス向上のため、PP_IFの評価後のPP_LOOKUP_UNEXPANDED_nが展開されるようにしてみました。PP_IFの2,3個目の引数にPP_LOOKUP_UNEXPANDED_n(p)と、そのまま書いてしまうと、PP_IFの条件が真であるか偽であるかに関わらず、PP_LOOKUP_UNEXPANDED_n(p)が展開されてしまいます。しかし、上のように書くことによって、PP_IFの展開後まで展開を遅らせることができます。結果、余計な展開が発生せずに、パフォーマンスが上がる可能性があります。もっとも、これだけの回数ではあまり意味がありませんね。そのためにはもっともっとマクロ展開しましょう。ただし今回は、PP_LOOKUP_UNEXPANDED_nの各PP_IFが真の場合は関数マクロではなく、ただの数なので、後ろの(p)を消す必要があります。そこで、1とか2の後ろにPP_EATと書いておけば、PP_IFの条件が真だった場合、その展開結果は、n PP_EAT(p)となり、PP_EAT(p)の結果は何も残りませんので、結局nだけを残すことができます。
で、本題に戻って、PP_CHECK_APPLY(n)は、nを受けとって、PP_APPLY_nが展開済みかどうかを調べる関数マクロです。展開済みであれば0を返し、そうでなければ1を返します。この識別の方法は、もともとのコードと同じ方法です（PP_UNEXPANDED_nのPP_IFの第一引数に似た式がありましたね）。ただし、番号を指定して調べられるように引数を追加しています。
以下が展開結果です。
http://codepad.org/drcJGmsx
いかがでしたでしょうか？今回は今一つ説明しにくいし、おまけにピンとこなかったかも知れませんが、使いどころが限られているものではあるので、致し方ありません。ちなみにこれは遅いです。なぜなら展開していない名前の探索が線形探索だからです。これを二分探索にすればもっと高速化できます。そのへんのこととか、もっと深く知りたければ、BOOST_PP_AUTO_RECを調べてみてください。
ではごきげんよう。
追記：色々修正したので、元の版はこちらに置いておきます。
