Cプリプロセッサメタプログラミングで、文字列系泥沼関数型プログラミング

今年の文化祭で書いた記事です。

• • • -

C言語といえば、いやなイメージ、過去の遺産といった感じがあるかもしれません。

C言語のネガティブな側面というと、やはりポインタやメモリ管理などが難しい、ということが思いつくかもしれません。

しかし、C言語のポインタは表記に騙されやすいだけで、仕組み自体は全く難しくありません。

文法も、どこぞのPerlやC++と比べたら屁でもない単純さです。

実のところ、仕様が煩雑で難しいのは、Cプリプロセッサなのであります。

普段からあまり複雑な使いかたをしないから気づかないかもしれませんが、Cプリプロセッサの置換処理は、欺瞞と裏切りに満ちた世界なのです。

これが進化するとテンプレートなどといったもっと面白いものになるのですが、今回はCプリプロセッサで計算をしちゃったりするところまで試しにやってみましょう。

(なお、GCCにより実験的に調べた記事なので、他のCコンパイラでは挙動が違う可能性があります。)

Cプリプロセッサの起動方法

Cプログラムをコンパイルすれば、Cプリプロセッサはその処理の途中で起動しますが、今回はCプリプロセッサの出力を直接見るので、Cコンパイラは起動しません。

GCCでは、以下のようにするとプリプロセッサのみを起動できます。

% gcc -E test.c
# 1 "test2.c"
# 1 "<built-in>"
# 1 "<command-line>"
# 1 "test2.c"

(#で始まる出力は、コンパイルエラー等の発生箇所を正しく元ファイルと対応づけるためのマークなので無視してください。)

基本

Cプリプロセッサは大きくいって次のような処理を行います。

• 行の結合
• コメントの除去
• 条件分岐
• ソースの結合
• 単語の置換

行の結合

バックスラッシュ*1の後に改行文字が続くと、それは最初に除去されます。
なので次のようなソースはOKです。

# de\
fi\
ne /\
* comment *\
/ EOF (-1)

コメントの除去

コメントを除去します。

条件分岐

以下のソースのように、環境要因などによってソースの断片を挿入したりしなかったりします。

#ifdef __cplusplus
extern "C" {
#endif

ソースの結合

いわゆるincludeです。あまり知られてませんが、include_nextというものもあるらしいです。

単語の置換

下記のソースでEOFが-1と見做されるのは、プリプロセッサがEOFを(-1)に置き換えているからです。

#define EOF (-1)
EOF

上記のような処理をされたコードはそのままCコンパイラに渡され、構文解析を行います。

Cプリプロセッサでプログラムを書く方法(1)

以下のようなコードは、無限再帰となり、終了しません。(正確にはスタックオーバーフローで異常終了します)

#include "test.c" /* 自分自身をinclude */

これと、#ifによる条件分岐を上手に使えば、様々な計算が行えそうです。#ifにはCと似た文法で計算を行う方法があるので、これを使えば手続き的に計算を行えそうです。しかしこれは無謀です。

なぜならば、計算結果を代入する手段が無いからです。代入といえば、#defineが使えそうと思うでしょう。しかし#defineは定義を変更することはできても、既存の定義からの計算結果を保存することはできません。以下の例を見てください。

#define X 2
#define Y (X+5)
Y /* この時点ではYは(2+5) */
#undef X
#define X 3 /* Xを再定義 */
Y /* Yは(3+5) */

このように、define内の記号はその場では置換されないので、計算結果を保存することはできません。そのため、手続き的にプログラムを書くのは無謀です。

Cプリプロセッサでプログラムを書く方法(2)

それでは、どのように書けばいいのでしょうか。

答えは、「項の置き換え、すなわちdefineのみを使って、関数型言語のようにプログラムを書く」です。

ここでは、この非常に強力かつ欺瞞に満ちた項の置き換え機能を中心に据えてプログラムを書きます。

defineの基本

defineによる定義方法は2種類あります。

#define A_VALUE (5+6)
#define A_FUNC(x,y) (x+y)
A_VALUE /* (5+6) */
A_FUNC(3,4) /* (3+4) */

つまり、単語単体で置換されて、あたかも変数であるかのように振る舞うものと、括弧つきで置換されて、あたかも関数であるかのように振る舞うものがあります。

再帰

この置き換えは一度だけ行われるわけではありません。先のソースのように

#define X 2
#define Y (X+5)
Y /* (X+5)が再度展開されて(2+5)になる！ */

という風に、多段的に展開されます。

では、次のコードはどうでしょうか。

#define X Y
#define Y X
X /* X -> Y -> X -> Y ... 無限ループ？ */

無限ループになりそうに見えますね。
しかし実際は、Xと出力されて終了してしまいます。

これは、ANSI Cの規格で、Xの展開の中でXが出てきたので、それ以上展開するのを止める、という仕様になっているためです。

これのせいで普通に再帰が書けず、非常に苦労します。

ただし、以下のような書き方では正常に動作します。

#define test(x) a x /* 引数の直前に「a」を付加する */
test(test(x)) /* a a x になる */

これは、先に内側の関数が「a x」に展開されるためです。この評価順序がまた話をややこしくします。

文字列化

文字列化という機能があります。

#define str_2(x) #x
str_2(google) /* "google" という文字列になる */

これは、例えば次のように活用できます。

#define pf(fmt, val) fprintf(stderr, #val " = " fmt ";\n", val);
pf("%d", i); /* これは */
fprintf(stderr, "i" " = " "%d" ";\n", i); /* に展開され、デバッグ用に便利。 */

ただし、良い子のみんなはデバッガを使いましょう。

また、これを利用して、以下のコードで自分自身を出力することができます(このようなコードをQuineと言います。)

#define t(u)v=#u;u
t(main(){printf("#define t(u)v=#u;u\nt(%s)",v);})

どのようにして自分自身が出力されるか考えてみると面白いかもしれません。

トークンの結合

文字列化より知られていませんが、文字列化と並んで、トークンの結合という機能があります。

#define deftype(t) const char* typename_##t = #t;
deftype(int); /* const char* typename_int = "int"; */
deftype(char); /* const char* typename_char = "char"; */

ここでは、トークン「typename」と引数tの中身を結合して、「typename_int」という別のものを作ってしまっています。
次のようなことも可能です。

#define cat(a,b) a##b
cat(+,=) /* += になる */
cat(0x, 190) /* 0x190 になる */
cat(value_, 100) /* value_100 になる */
cat(20, 0777) /* 200777 になる */

ここらへんから気味が悪くなってきますね。

文字列化とトークン結合の罠

次のような文字列化には注意が必要です。

#define str_2(x) #x
#define EOF (-1)
str_2(EOF) /* これは"EOF" */

このように、文字列化は引数を展開しません。(トークン結合も同様)
これを回避するため、以下のように中間となるマクロを挟みます。

#define str_2(x) #x
#define str(x) str_2(x)
#define EOF (-1)
str(EOF) /* これは"(-1)" */

条件分岐

ではプログラムの始めとして、条件分岐を書いてみましょう。

#define D_if(b) D_if_2(b)
#define D_if_2(b) D_if_##b
#define D_if_0(x,y) y
#define D_if_1(x,y) x

D_if(1)(a,b) /* a */
D_if(0)(a,b) /* b */

これで条件分岐ができます。

これはどのような仕組みかといいますと

D_if(1)(a,b)
D_if_2(1)(a,b)
D_if_1(a,b)
a

というように、与えられた値が0か1かで、別々の関数を返すような仕組みになっています。

条件分岐ができたので、ブール演算子は簡単に定義できますね。次はandの例です。

#define D_Band(a,b) D_if(a)(b,0)

リスト

単一の値はこれで定義できましたが、値の集合、つまり配列のようなものが定義できてませんね。

ここでは「リスト」を定義してみましょう。

Cプリプロセッサでリスト構造を作る方法は、僕は次の2つを思いつきました。

(a, (b, (c, ) ) ) /* a,b,cというリスト */

または

(a) (b) (c) /* a,b,cというリスト */

リストであるのに必要なのは次の条件です。

• リストが空か判定できる。(nil判定)
• リストが空でない場合、リストの先頭を取りだせる。(headまたはcar)
• リストが空でない場合、リストの先頭以外のリストを取りだせる。(tailまたはcdr)
• 値をリストの先頭に追加して新しいリストを作れる。(cons)

今回は、用途が限定されたリストなので、次のような構造にしました。

1 0 0 1 0 1

簡単でいいですね。

このリストを取り出すために、次のマクロが必要です。

#define D_addcomma_0 0,
#define D_addcomma_1 1,

他のトークンをリストで扱う場合は、必ずこれを定義しなければいけません。後で十進法の桁を扱うので、2から9までは登録しておきました。

このリストを操作する基本の関数は以下です。

#define D_head(list) D_head_2(D_cat(D_addcomma_,list))
#define D_head_2(x) D_head_3(x)
#define D_head_3(a,b) a
#define D_tail(list) D_tail_2(D_cat(D_addcomma_,list))
#define D_tail_2(x) D_tail_3(x)
#define D_tail_3(a,b) b

#define D_____EOL ,0
#define D_____SOL_D_____EOL ,1
#define D_nil_p(list) D_nil_p_2(list D_____EOL)
#define D_nil_p_2(list) D_nil_p_3(D_____SOL_##list)
#define D_nil_p_3(x) D_nil_p_4(x)
#define D_nil_p_4(a,b) b

headとtailは、D_addcomma_というトークンと与えられたリストを結合することで、最初の項目とそれ以外をコンマで分離します。
それを引数として渡せばコンマの前後の値を別々に取り出せます。
D_head_2,D_tail_2というマクロをクッションしていますが、これがないとコンマを引数区切りとして見做せません。

nil判定は、D_____SOL_とD_____EOLをlistを挟んで結合します。もし値がnilであれば、D_____SOL_D_____EOLができ、そうでなければD_____EOLになります。
これをコンマで分離して同様に取り出せばnilかどうかが分かるという仕組みです。

リストの結合は、単にトークンを並べればいいだけですね。いいですね。

また補助マクロとして以下を定義します。これは値がnilの場合に別のリストで代替するものです。

#define D_Lor(list1,list2) D_if(D_nil_p(list1))(list2,list1)
#define D_tail_or(list1,list2) D_tail(D_Lor(list1,list2))
#define D_head_or(list1,list2) D_head(D_Lor(list1,list2))

ループ

ループは非常に厄介です。なんといっても、再帰が厳密に禁止されているので、うまいこと回避しなければいけません。
そこで以下のようにしました。

#define D_whileZ0(p,f,x) D_if(p x)(f x, x)
#define D_whileZ1(p,f,x) D_if(p x)(D_whileZ0(p,f,D_whileZ0(p,f,x)),x)
#define D_whileZ2(p,f,x) D_if(p x)(D_whileZ1(p,f,D_whileZ1(p,f,x)),x)

これは、p xが1のあいだ、xにf xを代入して、最終的な結果を返します。
D_whileZ0は、「p xが1ならf x,そうでなければxを返す」となりますね。これは「上限1回のwhile」と言えます。
D_whileZ1は、「p xが1ならp xが成立する間xにf xを代入して、もう一回それをする。さもなければxを返す」なので、これは「上限2回のwhile」と言えます。
数を大きくしていくと上限回数は指数的に増えるので、D_whileZ32では約40億回まで繰り返すことができます。またこれはループが短く終わったときも比較的短時間で終了するようで、効率が良いです。

なお、p(x)ではなくp xとなっているのは、x=(a,b,c)のようにして多値を簡単に扱うためです。

このwhileで気をつけなくてはいけないのは、pやfの内部で同じwhileを呼ぶと再帰になって停止してしまうので、同じ内容のwhileを大量に用意して使いわけないといけないということです。さすがにこの辺りは面倒だったので、Rubyでループを回してwhileAからwhileZまで自動生成しました。

ループを使ったプログラムの最初の例として、リストの順番を逆にするプログラムを作ってみましょう。

#define D_reverse_p(list1,list2) D_Bnot(D_nil_p(list1))
#define D_reverse_f(list1,list2) (D_tail(list1),D_head(list1) list2)
#define D_reverse(list) D_tuple2_2(D_whileZ(D_reverse_p, D_reverse_f, (list,)))

listを受けとってループを回し、list1の先頭から値を取ってlist2の先頭に付け加えていきます。list1がnilになったらlist2を返します。

数値

今回は非負整数のみを扱ってみます。

数値は0,1の値のリスト、つまり可変長の2進数で表現することにします。
先頭のほうが小さい桁とします。つまり「0 0 1 1」は、12を意味します。このようにすると、桁が足りないとき、0を簡単に補うことができますし、計算順序に合致しています。

今回は加算と比較だけ定義してみましょう。

数値の加算

#define D_Nplus_p(a,b,c,r) D_Bor(c,D_Bnot(D_Band(D_nil_p(a),D_nil_p(b))))
#define D_Nplus_f(a,b,c,r) D_Nplus_f_2(D_head_or(a,0),D_head_or(b,0),c,r,D_tail_or(a,0),D_tail_or(b,0))
#define D_Nplus_f_2(ha,hb,c,r,ta,tb) (ta,tb,D_Nplus_cn(ha,hb,c),r D_Nplus_dig(ha,hb,c))
#define D_Nplus(a,b) D_tuple4_4(D_whileZ(D_Nplus_p, D_Nplus_f, (a,b,0,)))
#define D_Nplus_dig(a,b,c) D_Bxor(D_Bxor(a,b),c)
#define D_Nplus_cn(a,b,c) D_if(D_Bxor(a,b))(c,a)

貼っても正直わかりづらいと思いますが、概要だけ説明します。
aとbが加算したい数、cが桁の繰り上がりです。aとbから一番下の桁を取り出してそれと桁の繰り上がりの3つの数の和を求めます(D_Nplus_digとD_Nplus_cn)
これを繰り返して新しい数を構成し、もう足すものが無くなったら終了です。

数値の比較

#define D_Nlt_p_p(a,b,r) D_Bnot(D_Band(D_nil_p(a),D_nil_p(b)))
#define D_Nlt_p_f(a,b,r) (D_tail_or(a,0),D_tail_or(b,0),D_Nlt_p_dig(D_head_or(a,0),D_head_or(b,0))(r))
#define D_Nlt_p_dig(a,b) D_Nlt_p_dig_2(a,b)
#define D_Nlt_p_dig_2(a,b) D_Nlt_p_dig##a##b
#define D_Nlt_p_dig00(r) r
#define D_Nlt_p_dig11(r) r
#define D_Nlt_p_dig01(r) 1
#define D_Nlt_p_dig10(r) 0
#define D_Nlt_p(a,b) D_tuple3_3(D_whileZ(D_Nlt_p_p, D_Nlt_p_f, (a,b,0)))
#define D_Nlteq_p(a,b) D_tuple3_3(D_whileZ(D_Nlt_p_p, D_Nlt_p_f, (a,b,1)))
#define D_Neq_p(a,b) D_Band(D_Nlteq_p(a,b),D_Nlteq_p(b,a))

aとbの大きさを比較します。下の桁から順番に捜査します。
現時点での大小をrに記憶しておきます。ある桁の大小によってrを書き換えます(D_Nlt_p_dig)。具体的には、その桁でa=bならrは変更なし、その桁でaとbが異なるならその桁の大小をrとします。

これを繰り返していき、最終的に処理する桁が無くなった時点のrが答えになります。

十進化

今までで求めてきた数値を十進数表記に変換します。

#define D_ND_Dbl_p(a,r,c) D_Bor(c,D_Bnot(D_nil_p(a)))
#define D_ND_Dbl_f(a,r,c)(D_tail_or(a,0),r D_N_toD_s(D_head_or(a,0),c))
#define D_ND_Dbl(a,c) D_tuple3_2(D_whileZ(D_ND_Dbl_p, D_ND_Dbl_f, (a,,c)))
#define D_N_toD_s(a,c) D_N_toD_s_(a,c)
#define D_N_toD_s_(a,c) D_N_toD_s##a##c
#define D_N_toD_s00 0,0
#define D_N_toD_s01 1,0
#define D_N_toD_s10 2,0
(中略)
#define D_N_toD_s81 7,1
#define D_N_toD_s90 8,1
#define D_N_toD_s91 9,1
#define D_N_toDlst_p(a,r) D_Bnot(D_nil_p(a))
#define D_N_toDlst_f(a,r) (D_tail(a), D_ND_Dbl(r,D_head(a)))
#define D_N_toDlst(a) D_Lor(D_tuple2_2(D_whileY(D_N_toDlst_p, D_N_toDlst_f, (D_reverse(a),))),0)
#define D_N_toDstr_p(a,r) D_Bnot(D_nil_p(a))
#define D_N_toDstr_f(a,r) (D_tail(a), D_cat(r,D_head(a)))
#define D_N_toDstr(a) D_tuple2_2(D_whileZ(D_N_toDstr_p, D_N_toDstr_f, (D_reverse(D_N_toDlst(a)),)))

まず、十進数に対して「2倍もしくは2倍+1を求める」という計算を定義(D_ND_Dbl)します。
2倍を求める過程で桁の繰り上がりを使うので、これを再利用すれば2倍+1も求まります。
二進数を上位の桁から順番に処理し、桁によって2倍もしくは2倍して1を加算します。
つまり2進法の「1010」だと、「((((0*2+1)*2)*2+1)*2)」という計算を十進法で行います。
このようにして十進法の数値に直した(D_N_toDlst)ものに対して、トークンの結合を行います(D_N_toDstr)。これが十進表記になります。

フィボナッチ

最後にフィボナッチの計算を行ってみましょう。

#define D_fib_p(a,b,c,i) D_Nlt_p(i,c)
#define D_fib_f(a,b,c,i) (b,D_Nplus(a,b),c,D_Nplus(i,D_N1))
#define D_fib(c) D_tuple4_2(D_whileY(D_fib_p, D_fib_f, (D_N0,1,c,D_N0)))

必要な計算は全て定義したのでだいぶ簡単になりましたね。
iは現在のループ回数です。aはフィボナッチ数列の(i-1)番目、bはフィボナッチ数列のi番目です。(a,b)のペアから(b,a+b)を求めていきます。
ループカウンタのiが指定した回数c以上になったら終了し、bを返します。

最終的なソース

以下がソース全文です。これでフィボナッチ数がコンパイル時に計算されます。

main.c

#define D_same(x) x
#define D_str(x) D_str_2(x)
#define D_str_2(x) #x
#define D_cat(a,b) D_cat_2(a,b)
#define D_cat_2(a,b) a##b
#define D_cat3(a,b,c) D_cat3_2(a,b,c)
#define D_cat3_2(a,b,c) a##b##c

#define D_tuple1_1__(a) a
#define D_tuple2_1__(a,b) a
#define D_tuple2_2__(a,b) b
#define D_tuple3_1__(a,b,c) a
#define D_tuple3_2__(a,b,c) b
#define D_tuple3_3__(a,b,c) c
#define D_tuple4_1__(a,b,c,d) a
#define D_tuple4_2__(a,b,c,d) b
#define D_tuple4_3__(a,b,c,d) c
#define D_tuple4_4__(a,b,c,d) d
#define D_tuple1_1(a) D_tuple1_1__ a
#define D_tuple2_1(a) D_tuple2_1__ a
#define D_tuple2_2(a) D_tuple2_2__ a
#define D_tuple3_1(a) D_tuple3_1__ a
#define D_tuple3_2(a) D_tuple3_2__ a
#define D_tuple3_3(a) D_tuple3_3__ a
#define D_tuple4_1(a) D_tuple4_1__ a
#define D_tuple4_2(a) D_tuple4_2__ a
#define D_tuple4_3(a) D_tuple4_3__ a
#define D_tuple4_4(a) D_tuple4_4__ a

#define D_if(b) D_if__2(b)
#define D_if__2(b) D_if_##b
#define D_if_0(x,y) y
#define D_if_1(x,y) x
#define D_ifB(b) D_ifB__2(b)
#define D_ifB__2(b) D_ifB_##b
#define D_ifB_0(x,y) y
#define D_ifB_1(x,y) x

#define D_Bnot(b) D_if(b)(0,1)
#define D_Bor(a,b) D_if(a)(1,b)
#define D_Band(a,b) D_if(a)(b,0)
#define D_Bxor(a,b) D_if(a)(D_Bnot(b),b)
#define D_Beq(a,b) D_if(a)(b,D_Bnot(b))

#define D_N0
#define D_N1 1
#define D_N2 0 1
#define D_N3 1 1
#define D_N4 0 0 1
#define D_N5 1 0 1
#define D_N6 0 1 1
#define D_N7 1 1 1
#define D_N8 0 0 0 1
#define D_N9 1 0 0 1
#define D_NA 0 1 0 1
#define D_NB 1 1 0 1
#define D_NC 0 0 1 1
#define D_ND 1 0 1 1
#define D_NE 0 1 1 1
#define D_NF 1 1 1 1

#define D_addcomma_0 0,
#define D_addcomma_1 1,
#define D_addcomma_2 2,
#define D_addcomma_3 3,
#define D_addcomma_4 4,
#define D_addcomma_5 5,
#define D_addcomma_6 6,
#define D_addcomma_7 7,
#define D_addcomma_8 8,
#define D_addcomma_9 9,
#define D_addcomma_A A,
#define D_addcomma_B B,
#define D_addcomma_C C,
#define D_addcomma_D D,
#define D_addcomma_E E,
#define D_addcomma_F F,
#define D_addcomma_m m,

#define D_head(list) D_head_2(D_cat(D_addcomma_,list))
#define D_head_2(x) D_head_3(x)
#define D_head_3(a,b) a
#define D_tail(list) D_tail_2(D_cat(D_addcomma_,list))
#define D_tail_2(x) D_tail_3(x)
#define D_tail_3(a,b) b

#define D_____EOL ,0
#define D_____SOL_D_____EOL ,1
#define D_nil_p(list) D_nil_p_2(list D_____EOL)
#define D_nil_p_2(list) D_nil_p_3(D_____SOL_##list)
#define D_nil_p_3(x) D_nil_p_4(x)
#define D_nil_p_4(a,b) b

#define D_Lor(list1,list2) D_if(D_nil_p(list1))(list2,list1)
#define D_tail_or(list1,list2) D_tail(D_Lor(list1,list2))
#define D_head_or(list1,list2) D_head(D_Lor(list1,list2))

#include "d_while.h"

#define D_reverse_p(list1,list2) D_Bnot(D_nil_p(list1))
#define D_reverse_f(list1,list2) (D_tail(list1),D_head(list1) list2)
#define D_reverse(list) D_tuple2_2(D_whileZ(D_reverse_p, D_reverse_f, (list,)))

#define D_Nplus_p(a,b,c,r) D_Bor(c,D_Bnot(D_Band(D_nil_p(a),D_nil_p(b))))
#define D_Nplus_f(a,b,c,r) D_Nplus_f_2(D_head_or(a,0),D_head_or(b,0),c,r,D_tail_or(a,0),D_tail_or(b,0))
#define D_Nplus_f_2(ha,hb,c,r,ta,tb) (ta,tb,D_Nplus_cn(ha,hb,c),r D_Nplus_dig(ha,hb,c))
#define D_Nplus(a,b) D_tuple4_4(D_whileZ(D_Nplus_p, D_Nplus_f, (a,b,0,)))
#define D_Nplus_dig(a,b,c) D_Bxor(D_Bxor(a,b),c)
#define D_Nplus_cn(a,b,c) D_if(D_Bxor(a,b))(c,a)

#define D_Nlt_p_p(a,b,r) D_Bnot(D_Band(D_nil_p(a),D_nil_p(b)))
#define D_Nlt_p_f(a,b,r) (D_tail_or(a,0),D_tail_or(b,0),D_Nlt_p_dig(D_head_or(a,0),D_head_or(b,0))(r))
#define D_Nlt_p_dig(a,b) D_Nlt_p_dig_2(a,b)
#define D_Nlt_p_dig_2(a,b) D_Nlt_p_dig##a##b
#define D_Nlt_p_dig00(r) r
#define D_Nlt_p_dig11(r) r
#define D_Nlt_p_dig01(r) 1
#define D_Nlt_p_dig10(r) 0
#define D_Nlt_p(a,b) D_tuple3_3(D_whileZ(D_Nlt_p_p, D_Nlt_p_f, (a,b,0)))
#define D_Nlteq_p(a,b) D_tuple3_3(D_whileZ(D_Nlt_p_p, D_Nlt_p_f, (a,b,1)))
#define D_Neq_p(a,b) D_Band(D_Nlteq_p(a,b),D_Nlteq_p(b,a))

#define D_ND_Dbl_p(a,r,c) D_Bor(c,D_Bnot(D_nil_p(a)))
#define D_ND_Dbl_f(a,r,c)(D_tail_or(a,0),r D_N_toD_s(D_head_or(a,0),c))
#define D_ND_Dbl(a,c) D_tuple3_2(D_whileZ(D_ND_Dbl_p, D_ND_Dbl_f, (a,,c)))
#define D_N_toD_s(a,c) D_N_toD_s_(a,c)
#define D_N_toD_s_(a,c) D_N_toD_s##a##c
#define D_N_toD_s00 0,0
#define D_N_toD_s01 1,0
#define D_N_toD_s10 2,0
#define D_N_toD_s11 3,0
#define D_N_toD_s20 4,0
#define D_N_toD_s21 5,0
#define D_N_toD_s30 6,0
#define D_N_toD_s31 7,0
#define D_N_toD_s40 8,0
#define D_N_toD_s41 9,0
#define D_N_toD_s50 0,1
#define D_N_toD_s51 1,1
#define D_N_toD_s60 2,1
#define D_N_toD_s61 3,1
#define D_N_toD_s70 4,1
#define D_N_toD_s71 5,1
#define D_N_toD_s80 6,1
#define D_N_toD_s81 7,1
#define D_N_toD_s90 8,1
#define D_N_toD_s91 9,1
#define D_N_toDlst_p(a,r) D_Bnot(D_nil_p(a))
#define D_N_toDlst_f(a,r) (D_tail(a), D_ND_Dbl(r,D_head(a)))
#define D_N_toDlst(a) D_Lor(D_tuple2_2(D_whileY(D_N_toDlst_p, D_N_toDlst_f, (D_reverse(a),))),0)
#define D_N_toDstr_p(a,r) D_Bnot(D_nil_p(a))
#define D_N_toDstr_f(a,r) (D_tail(a), D_cat(r,D_head(a)))
#define D_N_toDstr(a) D_tuple2_2(D_whileZ(D_N_toDstr_p, D_N_toDstr_f, (D_reverse(D_N_toDlst(a)),)))

#define D_fib_p(a,b,c,i) D_Nlt_p(i,c)
#define D_fib_f(a,b,c,i) (b,D_Nplus(a,b),c,D_Nplus(i,D_N1))
#define D_fib(c) D_tuple4_2(D_whileY(D_fib_p, D_fib_f, (D_N0,1,c,D_N0)))

D_N_toDstr(D_fib(D_N0));
D_N_toDstr(D_fib(D_N1));
D_N_toDstr(D_fib(D_N2));
D_N_toDstr(D_fib(D_N3));
D_N_toDstr(D_fib(D_N4));
D_N_toDstr(D_fib(D_N5));
D_N_toDstr(D_fib(D_N6));
D_N_toDstr(D_fib(D_N7));
D_N_toDstr(D_fib(D_N8));
D_N_toDstr(D_fib(D_N9));
D_N_toDstr(D_fib(D_NA));
D_N_toDstr(D_fib(D_NB));
D_N_toDstr(D_fib(D_NC));
D_N_toDstr(D_fib(D_ND));
D_N_toDstr(D_fib(D_NE));
D_N_toDstr(D_fib(D_NF));

d_while.h

#define D_whileY0(p,f,x) D_if(p x)(f x, x)
#define D_whileY1(p,f,x) D_if(p x)(D_whileY0(p,f,D_whileY0(p,f,x)),x)
#define D_whileY2(p,f,x) D_if(p x)(D_whileY1(p,f,D_whileY1(p,f,x)),x)
#define D_whileY3(p,f,x) D_if(p x)(D_whileY2(p,f,D_whileY2(p,f,x)),x)
#define D_whileY4(p,f,x) D_if(p x)(D_whileY3(p,f,D_whileY3(p,f,x)),x)
#define D_whileY5(p,f,x) D_if(p x)(D_whileY4(p,f,D_whileY4(p,f,x)),x)
#define D_whileY6(p,f,x) D_if(p x)(D_whileY5(p,f,D_whileY5(p,f,x)),x)
#define D_whileY7(p,f,x) D_if(p x)(D_whileY6(p,f,D_whileY6(p,f,x)),x)
#define D_whileY8(p,f,x) D_if(p x)(D_whileY7(p,f,D_whileY7(p,f,x)),x)
#define D_whileY D_whileY8

#define D_whileZ0(p,f,x) D_if(p x)(f x, x)
#define D_whileZ1(p,f,x) D_if(p x)(D_whileZ0(p,f,D_whileZ0(p,f,x)),x)
#define D_whileZ2(p,f,x) D_if(p x)(D_whileZ1(p,f,D_whileZ1(p,f,x)),x)
#define D_whileZ3(p,f,x) D_if(p x)(D_whileZ2(p,f,D_whileZ2(p,f,x)),x)
#define D_whileZ4(p,f,x) D_if(p x)(D_whileZ3(p,f,D_whileZ3(p,f,x)),x)
#define D_whileZ5(p,f,x) D_if(p x)(D_whileZ4(p,f,D_whileZ4(p,f,x)),x)
#define D_whileZ6(p,f,x) D_if(p x)(D_whileZ5(p,f,D_whileZ5(p,f,x)),x)
#define D_whileZ7(p,f,x) D_if(p x)(D_whileZ6(p,f,D_whileZ6(p,f,x)),x)
#define D_whileZ8(p,f,x) D_if(p x)(D_whileZ7(p,f,D_whileZ7(p,f,x)),x)
#define D_whileZ D_whileZ8

これを実行すると以下のようになります。

# 1 "main.c"
# 1 "<built-in>"
# 1 "<command-line>"
# 1 "main.c"
# 98 "main.c"
# 1 "d_while.h" 1
# 99 "main.c" 2
# 160 "main.c"
1;
1;
2;
3;
5;
8;
13;
21;
34;
55;
89;
144;
233;
377;
610;
987;

感動的ですね…いやいまいち感動が薄いですね…

*1:Windowsでは円記号