#はじめに
Javaで実装したSchemeをWikipediaで調べてみると、以下の３つが見つかります。
- Jscheme
- JAKLD - Java アプリケーション組み込み用のLISPドライバ
- Kawa - GNUプロジェクトのひとつ。Scheme プログラムを Java 仮想機械用にコンパイル可能。
これらはいずれも継続(Continuation)の実装に制限があるようです。
##Jschemeの場合
Continuations can only be used as escape procedures; that is they can only be called while the surrounding try/catch is still in scope.
（継続は手続きからの脱出にのみ使用できる。すなわち try/catch で囲まれたスコープの中からだけ呼び出すことができる）（拙訳）
##JAKLDの場合
継続は，組込み関数の call/cc が生成する．call/cc は１引数の関数を受け取り，生成した継続を引数として呼び出す．２節で述べたように，本処理系では，IEEE Scheme の継続を完全に実現することは断念し，
escape procedure としての機能を実現する．つまり，
(call/cc f)
によって生成された継続 c は，関数 f の実行中に限り，呼び出すことができる．継続 c が呼び出されると，f の実行は直ちに終了し，c への引数が，call/cc の値として返される．f の実行中に c が呼び出されないで， f が正常にリターンしたときは，f の返す値が，call/cc の値となる．いずれの場合も，call/cc がリターンした後では，継続を呼び出すことはできない．
##Kawaの場合
Also,
call-with-current-continuationis only "upwards" (?). I.e. once a continuation has been exited, it cannot be invoked. These restricted continuations can be used to implement catch/throw (such as the examples in R4RS), but not co-routines or backtracking.
（call-with-current-continuationは「上向き」のみである（？）。すなわち継続を終了すると、それを呼び出すことはできない。この継続の制約は（R4RSの例のように）catch/throwの実装で使用できるが、コルーチンやバックトラッキングには使えない。）（拙訳）
いずれも例外を使って実装しているようで、tryブロックを外れると継続を呼び出すことはできないようです。
Javaでは継続(Continuation)を実装することはできないのでしょうか？ いろいろ調べていたらCommon Lisp で作る micro Schemeというページを見つけました。これを見ると継続のないCommon Lispを使って継続を実装しています。Common LispにはC言語のsetjmp/longjmpのようなスタック操作はないし、この実装でも特殊なことはやっていないように見えます。
Common LispでできるならJavaでもできるはず。
というのがこの記事の趣旨です。
まず手始めに継続のないSchemeを実装してみます。
#継続のないScheme
継続の実装方法を確認するためのものなので、できるだけ単純な仕様とします。
- 扱えるオブジェクトはリスト、シンボル、真理値、32bit整数のみです。文字列は使えません。
- 組み込み関数はquote, car, cdr, cons, list, eq?, equal?, lambda, define, set!, let, let*, letrec, begin, 整数の大小比較, 四則演算だけです。
- Java8を使います。組み込み関数の定義でラムダ式を使っています。
- print関数はJavaの
toString()メソッドで実現します。 - チェックは最小限にします。
- 末尾再帰は最適化しません。
- 確認のためのプログラムなので名前空間は適当です。コメントもありません。Java標準のコーディングルールにも従っていません。
クラスの構成は以下のようになります。
完成したプログラムは以下の場所にあります。
#継続の実装
ここに継続を実装するために、まず継続関数をインタフェースとして実装します。
public interface Cont {
Obj apply(Obj result);
}
次にeval(Env env)に継続関数を引数として追加します。評価の結果を継続関数に渡すようにします。
default Obj eval(Env env) { this; }
->
default Obj eval(Env env, Cont cont) { return cont.apply(this); }
apply(Obj args, Env env)の中でeval(Env env)を呼び出すことがあるので、applyにも継続関数を引数として渡すようにします。
default Obj apply(Obj args, Env env) {
throw new RuntimeException("Cannot apply " + args + " to " + this);
}
->
default Obj apply(Obj args, Env env, Cont cont) {
throw new RuntimeException("Cannot apply " + args + " to " + this);
}
この要領でevalとapplyの実装を変更していきます。
@Override
public Obj eval(Env env) {
return car.eval(env).apply(cdr, env);
}
->
@Override
public Obj eval(Env env, Cont cont) {
return car.eval(env,
x -> x.apply(cdr, env, cont));
}
call/ccの実装を追加します。
ENV.define(symbol("call/cc"), (Procedure) (args, cont) ->
((Procedure)args.car()).apply(list(new Continuation(cont)), cont));
ここに登場するContinuationというクラスは継続を保持するためのクラスです。
public class Continuation implements Procedure {
final Cont cont;
Continuation(Cont cont) {
this.cont = cont;
}
@Override
public Obj apply(Obj args, Cont cont) {
return this.cont.apply(args.car());
}
}
書き換えた後のプログラムは以下の場所にあります。
継続にかかわるところだけを変更しているので差分を取れば、継続の実装に必要な個所がわかります。（上記のコードだけでなくあちこち書き換えています）
#実行例
継続を使った処理の中断を試してみます。
> (define (bar1 cont) (display 'bar1))
> (define (bar2 cont) (display 'bar2) (display 'bar2-2) (cont 'exit))
> (define (bar3 cont) (display 'bar3))
> (define (test cont) (bar1 cont) (bar2 cont) (bar3 cont))
> (call/cc (lambda (cont) (test cont)))
bar1
bar2
bar2-2
exit
bar3の実行をスキップして結果が返っているのがわかります。
次に計算途中の継続をグローバル変数に保存しておいて再実行する例です。
> (define C '())
> (+ 1 (* 2 (call/cc (lambda (cont) (set! C cont) 3))))
7
> (C 10)
21
> (C 100)
201
(+ 1 (* 2 3))の3の部分を置き換えて再実行しているのがわかります。
次は継続を使ってループする例です。
> (define (fact n)
(let ((r 1))
(let ((k (call/cc (lambda (c) c))))
(set! r (* r n))
(set! n (- n 1))
(if (= n 1) r (k k)))))
> (fact 6)
720
#まとめ
IEEE Schemeの継続を完全に実装しているかどうかは確認していません。
また、末尾再帰の最適化はしていません。コードを見るとわかる通り、いたるところで再帰呼び出しをしています。このまま不足している関数を実装していっても実用的なSchemeにはなりません。
しかしJavaを使って継続のあるSchemeをとりあえず実装できることがわかりました。