sequenceを線形時間でfoldする
Cプリプロセッサ上で値の列を表現するためのデータ構造の一つとしてsequenceというのがある(Boost.Preprocessorの用語)。
他の言語でいうリストや配列に似たもので、以下のような形をとる。
(0)(1)(2)(3) /* 0から3までの整数のsequence */ (signed char)(short)(int)(long) /* C++の符号付き整数型のsequence */
なお、空のsequenceは扱いがいろいろ面倒なのでこの記事では無視する。
リスト風のデータ構造ならばもちろんfold演算が欲しい。Cプリプロセッサ上のプログラミングは関数型プログラミングであることを考えればなおさらだ。
このためにBoost.PPにはBOOST_PP_SEQ_FOLD_LEFTとBOOST_PP_SEQ_FOLD_RIGHTというマクロが用意されている。問題はこれがO(n^2)の時間を使うこと*1で、大きなsequenceをまともに扱えない。
実はこれには理由があって、Cプリプロセッサの独特な性能上の振る舞いに関係している。すなわち、Cプリプロセッサはマクロを展開する度に、その引数を一回走査する。これには引数のトークン数に比例する時間が掛かる。だから、大きさnのデータ構造をまるごとマクロに渡すと、それだけでO(n)のオーバーヘッドが発生する。BOOST_PP_SEQ_FOLD_LEFTは繰り返しの1ステップごとに毎回「sequenceの残りの部分」を補助マクロに渡すので、O(n^2)の時間がかかるのが避けられない。*2
以下ではこのfold(ただし左foldのみ)をO(n)の時間で行う方法について書く。これは、CPP上で動くBrainfuckインタプリタを書いていたときに見つけたもの。
以下のマクロを定義しておく。
# define LPAREN() ( # define PCAT(x, y) x##y # define CAT(x, y) PCAT(x, y) # define EMPTY() # define EAT(x) # define EAT2(x, y) # define IS_NIL(x) TEST((PCAT(IS_NIL_, x), 0)) /* xがnilならば1、それ以外の英数字トークンならば0 */ # define IS_NIL_nil ~, 1)EAT2(~ # define TEST(x) IF_0 x # define IF(x) PCAT(IF_, x) /* IF(bool)(true_branch, false_branch) のように使う */ # define IF_0(x, y) y # define IF_1(x, y) x # define AND(x, y) IF(x)(y, 0) # define NOT(x) IF(x)(0, 1) # define XOR(x, y) IF(x)(NOT(y), y)
sequential iteration
まず、sequenceに対する単純なmap操作ならばO(n)で可能。以下のようにする。
# define DOUBLE_EACH(seq) CAT(DOUBLE_EACH_A seq, END) # define DOUBLE_EACH_A(x) (x*2)DOUBLE_EACH_B # define DOUBLE_EACH_B(x) (x*2)DOUBLE_EACH_A # define DOUBLE_EACH_AEND # define DOUBLE_EACH_BEND DOUBLE_EACH((a)(b)(c)) /* => (a*2)(b*2)(c*2) */
このテクニックはsequential iterationと呼ばれている(Chaos PPの用語)。
DOUBLE_EACH_AとDOUBLE_EACH_Bというほとんど同じマクロが二つ必要なのは、「あるマクロの展開中にそのマクロ名を示すトークンが出現したら、そのトークンを展開不能にする」という謎の規則を回避するため。なお、この規則はマクロの再帰を禁止する規則とは別。DOUBLE_EACH_A自体はDOUBLE_EACH_Bを呼んでいる訳ではなく、それを返しているだけなので再帰には当たらない*3。
sequential iterationでは、元のsequenceを構成する括弧がそのままmap処理を行うマクロ(ここではINC_EACH_A)の呼び出し括弧として使われる。このため、map処理マクロに追加の引数を渡すことはできないし、fold演算もできない。
邪魔な開き括弧を消す
仮にsequenceに開き括弧がなければ、マクロ側で自由に引数を追加できるので、fold演算も可能になる。例えば、次のような形式で二進整数が与えられたとする。
1)1)1)0)0)1)nil) /* 左が下位ビット */
すると、これに1を足すマクロは次のように書ける。
# define INC INC_ITER_A(1, # define INC_ITER_A(carry, bit) INC_ITER_DO(carry, bit, B) # define INC_ITER_B(carry, bit) INC_ITER_DO(carry, bit, A) # define INC_ITER_DO(carry, bit, next) IF(IS_NIL(bit))(IF(carry)((1)EAT2, EAT2), (IF(carry)(IF(bit)(0, 1), bit))INC_ITER_NEXT)(IF(carry)(bit, 0), next) # define INC_ITER_NEXT(carry, next) PCAT(INC_ITER_, next)(carry, INC 1)1)1)0)0)1)nil) /* => (0)(0)(0)(1)(0)(1) */ INC 0)1)nil) /* => (1)(1) */ INC 1)nil) /* => (0)(1) */
sequenceに対する通常のsequential iterationと違って、この形式では列の終端を明示的に示す必要がある。
sequenceからこういう形式にO(n)で変換できれば、foldも全体としてO(n)で終わる。具体的には、(a)(b)(c)というsequenceを次のように表現する。
a, 1))b, 1))c, 1))0, 0))
上の「左括弧なしsequence」との違いは、終端を明示するために特殊なnilトークンでなく0または1の追加データを使っていることと、走査マクロが書き易いように閉じ括弧が二重になっていること。この形式をguideと呼ぶことにする。
変換は以下のSEQ_TO_GUIDEで行う。
# define SEQ_TO_GUIDE(seq) SEQ_TO_GUIDE_A seq(EAT LPAREN()LPAREN()LPAREN()))0, 0)) # define SEQ_TO_GUIDE_A(x) x, 1))SEQ_TO_GUIDE_B # define SEQ_TO_GUIDE_B(x) x, 1))SEQ_TO_GUIDE_A SEQ_TO_GUIDE((a)(b)(c)) /* => a, 1))b, 1))c, 1))0, 0)) */
この実装はこれ自体sequential iterationを使っていて、O(n)で動作する。上のDOUBLE_EACHの場合のように終端をCATで処理することができないのでややトリッキーなことになっている。
これを使ってfoldを書くことができる。
# define FOLD(f, z, seq) FOLD_GO(f, z, SEQ_TO_GUIDE(seq)) # define FOLD_GO(f, z, g) FOLD_ITER(f, z, g # define FOLD_ITER(f, z, x, cont) IF(cont)(FOLD_ITER_NEXT, z EAT2)(f, f(z, x) # define FOLD_ITER_NEXT(f, z) FOLD_ITER(f, z, FOLD(macro, z, (a)(b)(c)) /* => macro(macro(macro(z, a), b), c) */
ただし、このfoldはfを直接コールバックするのでリエントラントでない*4。これを使うよりもSEQ_TO_GUIDEを直接使った方がきれいで、オーバーヘッドも少く書けると思う。例えば、sequenceで表現された二進自然数のインクリメントは次のように書ける。
# define SEQINC(seq) SEQINC_GO(SEQ_TO_GUIDE(seq)) # define SEQINC_GO(g) SEQINC_ITER(g # define SEQINC_ITER(x, cont) IF(cont)((NOT(x))SEQINC_NEXT, (1)EAT)(x # define SEQINC_NEXT(carry) IF(carry)(SEQINC_ITER, ID_ITER)( # define ID_ITER(x, cont) IF(cont)((x)ID_NEXT, EMPTY)( # define ID_NEXT() ID_ITER( SEQINC((1)(1)(1)(0)(0)(1)) /* => (0)(0)(0)(1)(0)(1) */
右fold
左foldは以上のようにO(n)のものが実現できるが、右foldはどうか。おそらく、もっとも良い方法は反転してから左foldするというものだろう。sequenceの左右反転は普通に書くとどうしてもO(n^2)掛かるように思えるが、Order PPには芸術品のようなreverseマクロがあって、O(n log n)で動作する。プリプロセッサプログラミングは奥が深い。
