Kashiwa Schemeで階乗の計算ができるようになりました
「え？ 今まで出来なかったの！？」という感じですが、
はい。今まで出来ませんでした。
(define (fact n)
(if (= n 0)
1
(* n (fact (- n 1)))))
(write (fact 5)) ; => 120
(newline)
(write (fact 10)) ; => 3628800
(newline)
何故、今まで出来なかったかというと、
可変長引数の手続き(ここでは*と-)を放置してきたからです。
簡単そうに見えて、意外と考えさせられたのが、この可変長引数でした。
—
Kashiwa Schemeでは組み込み手続きを呼び出すコードは
builtin_cons(continuation, foo, bar);
といったように、C言語の関数呼び出しの形に変換されます。
そのため、組み込み関数の側(つまりC言語)で、
stdarg.hに含まれるva_startやva_argなどを用いると、
可変長引数の組み込み手続きを作ることができます。
ここまでは簡単です。
しかし、Scheme側でapplyを用いて、
可変長引数の組み込み手続きを呼び出す場合はどうでしょうか。
引数はリストの形でやって来ます。
こうなると、C言語の可変長引数の仕組みを利用することはできなくなります。
対応策として、手続き呼び出しの式
(proc arg1 arg2 ...)
のprocに組み込み手続きが現れた場合と、argNに組み込み手続きが現れた場合で、
それぞれ違う関数を用いるという方針を取りました。
procの位置に手続きが現れた場合は、C言語の可変長引数の仕組みを使う関数を利用して、
argNの位置に手続きが現れた場合は、リストを処理する別の関数を使うということです。
組み込み手続きは、引数として渡されることよりも、
直接呼び出すことの方が多いと仮定すると、
このように2種類の関数を用意して、
直接の呼び出しの場合を少しでも速くするということは、
それなりに価値があると思っています。
—
話は変わりますが、組み込み手続きではない手続き、
つまりユーザ定義の手続きには、
また別の問題が色々とあります。
Kashiwa Schemeは、まずCPS変換を行うため、
ユーザ定義の手続きは大量に生まれ、それらの大半は引数を通して渡されます。
つまり、(型推論でもしない限り)コンパイル時点で関数の型が分からなくなります。
そのため、クロージャ(手続きオブジェクト)には、関数ポインタや環境の他に、
「引数の数」を覚えさせておき、引数の数が正しいかチェックする必要があります。
Schemeなのだから、引数の数を実行時にチェックするのは当たり前なのですが、
意外と面倒なのが、関数ポインタを適切な型にキャストするということです。
引数が1つの場合、1引数関数へのポインタにキャスト、
引数が2つの場合、2引数関数へのポインタにキャスト、
引数が3つの場合、3引数関数へのポインタにキャスト、
……
このようにすべてを列挙するという方法が無理なのは言うまでもありません。
それならば、(C言語の)可変長引数の仕組みを使ってみてはどうでしょうか。
キャストの種類は常に1種類にして、
呼び出される側の関数はva_argを使って引数を取り出すようにする。
これだとうまく行きそうです。
しかし、この方法はスタックに対するGCが起こると問題が生まれます。
スタックに対するGCが起こると、直前に呼ばれた関数の関数ポインタと引数を保存して、
スタックからヒープに必要なものをコピーした後に、longjmpでスタックを縮め、
保存した情報を用いて、関数を再度呼び出します。
問題となる点は「関数を再度呼び出す」というところです。
再度呼び出すというプログラムは一体どう書けばいいのでしょうか。
C言語ではN個の引数を付けて関数を呼ぶ場合は
f(a1, a2, ..., aN)
といったように、すべての引数を括弧の中に書かないといけません。
しかし、引数の数が実行時まで分からない場合は、これができません。
さて、この問題への対応策として、
引数が閾値より少ない場合(今のところ4個まで)は、力技(すべての場合を列挙)で対応して、
引数が閾値より多い場合は、実引数をすべて構造体の中に放り込み、
関数にはその構造体だけを渡す(つまり1引数関数にキャストする)方針を取りました。
イメージとしては
f(1, 2, 3, 4, 5)
と書く代わりに、
args->v[0] = 1; ... args->v[4] = 5; f(&args);
と書くような感じです。
もちろん、常にこの構造体を中継して引数を渡すという方針を取ることもできますが、
「引数が少ない手続き」の方が「引数が多い手続き」よりも多いと仮定すると、
引数が少ない場合を特別扱いして速くすることに価値はあると思います。
—
その場その場で考えてコードを書いているため、
これらの手法が本当に適切かは分かりません。
どなたか、もっといい方法をご存知であれば教えて下さい。