R6RS以降、仕様が巨大化、複雑化するSchemeに嫌気がさして、SchemeからISLispに移行して10年以上になります。この度、ISLispに関する書籍を執筆するにあたり、LISP1.5－MACLISPと系譜を辿ろうと思いそれぞれの互換サブセット処理系を作っています。その流れにあってSchemeを除外するわけにはいかないと思いR3RS－Schemeを作っています。メインは継続、call/ccの実装です。継続渡しスタイル（CPS)でコンパクトなインタプリタを作っています。CPSによるcall/ccについて書き記します。Scheme実装方法に関する日本語文献がほとんどないという投稿もみられましたので、ご紹介します。
call/ccの例
次のような簡単な例がcall/ccの難しさを物語っています。
$ scm3
Scheme R3RS ver 1.00
> (define f #f)
f
> (+ 1 2 (call/cc (lambda (c) (set! f c) 0)))
3
> f
<cont>
> (f 10)
13
>
1+2+...の継続を捕捉してこれを変数fに束縛しておきます。トップレベルからこれに引数１０を与えて呼び出すと1+2+10=13の計算をします。
継続の実装方法
いくつか方法が考えられています。代表的なものは２つです。
-
スタック丸ごとコピー方式
アセンブラレベルならば関数呼び出しに自前のスタックに戻り先を積んで呼び出すことも可能です。その場合にはスタックをまるごと保存し、局所変数の値をまるごと保存しておけば継続を取り出すことが可能です。 -
CPS
C言語ではスタックを直接に取り出すことはできません。上記の方法は無理です。そこで継続渡しスタイル（CPS)を通常使います。
CPSによる方法
理論的にはλ式に継続Kを渡すという連鎖を生成するものと説明されています。私はもっと直観的にわかりやすい方法をとりました。命令列変換する方法です。抽象マシンで動作するSchemeの場合にはこの方法が有用です。今回は抽象マシンを使わずにインタプリタ自身がその命令列を実行するという方法をとりました。
命令列
継続に相当する命令列は次のようにリストで生成されます。
> (transfer '(+ 1 2 (call/cc (lambda (c) (set! f c) 0))))
(1 (push) 2 (push) (quote (c)) (push) (quote (set! f c)) (push) (quote 0) (push) (apply-cps (quote lambda) (pop 3)) (push) (apply-cps (quote call/cc) (pop 1)) (push) (apply-cps (quote +) (pop 3)))
>
命令の仕様は下記のとおりです。
- 数はその値をアキュムレーターに保存します。
- シンボルはそのシンボルに束縛された値をアキュムレーターに保存します。
- (push) アキュムレーターの値をCPS用のスタックに積みます。
- (pop N) CPS用のスタックからN個をpopしてリストにします。
- (aplly-cps P D) SchemeのプリミティブPにデータDを渡します。計算結果はアキュムレーターに記憶されます。
- (bind V) 変数Vにアキュムレーターの値を束縛します。
- (unbind N) Ｎ個の局所変数を解除します。
- (exec-cont C) 継続ほ保存したオブジェクトＣから後続の命令列、局所変数、CPS用のスタックを復元して後続の命令列を実行開始します。
call/㏄の役割
call/ccは (apply-cps 'call-cc (pop 1))のように呼び出されます。引数であるλ式は事前にプッシュされています。call/ccは呼び出された時点での残り命令列（レジスタCPに束縛されてる）を取り出して継続オブジェクトに記憶させます。また、同時にその時点での局所変数、スタックの値を記憶させます。Cで記述したcall/ccは次のとおりです。
int f_call_cc(int arglist)
{
int arg1,cont;
checkarg(LEN1_TEST,"call/cc",arglist);
arg1 = car(arglist);
cont = makecont();
// (lambda (cont) continuation)
return (apply_cps(arg1,list1(cont)));
}
int makecont(void)
{
int val;
val = freshcell();
SET_TAG(val, CONT);
SET_BIND(val, cp);
SET_CAR(val,cpssp);
SET_CDR(val, ep);
return (val);
}
exec-contの役割
継続を保存したオブジェクトはexec-contにより解凍されcp,EP,sp_cpsを復元します。
int f_exec_cont(int arglist)
{
int arg1,arg2;
arg1 = car(arglist); //continuation
arg2 = cadr(arglist); //argument to cont
cp = GET_BIND(arg1); //restore continuation;
sp_csp = GET_CAR(arg1); //restore stack
ep = GET_CDR(arg1); //restore environment
acc = arg2;
return(eval_cps(NIL)); //execute CPS
}
上述の例の(f 10) は次のようにCPS命令列に変換されます。
> (transfer '(f 10))
(f (push) 10 (push) (apply-cps (quote exec-cont) (pop 2)))
>
処理系はgithubにて公開してあります。参考になれば幸いです。