Posted at

Javaで継続の使えるSchemeを実装する

More than 3 years have passed since last update.


はじめに

Javaで実装したSchemeをWikipediaで調べてみると、以下の3つが見つかります。


  1. Jscheme

  2. JAKLD - Java アプリケーション組み込み用のLISPドライバ

  3. 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 は1引数の関数を受け取り,生成した継続を引数として呼び出す.2節で述べたように,本処理系では,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-continuation is 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標準のコーディングルールにも従っていません。

クラスの構成は以下のようになります。

Model.png

完成したプログラムは以下の場所にあります。

SchemeMinimum


継続の実装

ここに継続を実装するために、まず継続関数をインタフェースとして実装します。


Cont.java

public interface Cont {

Obj apply(Obj result);

}


次にeval(Env env)に継続関数を引数として追加します。評価の結果を継続関数に渡すようにします。


Obj.java

    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にも継続関数を引数として渡すようにします。


Obj.java

    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);
}

この要領でevalapplyの実装を変更していきます。


Pair.java

    @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の実装を追加します。


Lisp.java

        ENV.define(symbol("call/cc"), (Procedure) (args, cont) ->

((Procedure)args.car()).apply(list(new Continuation(cont)), cont));

ここに登場するContinuationというクラスは継続を保持するためのクラスです。


Continuation.java

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());
}

}


書き換えた後のプログラムは以下の場所にあります。

SchemeWithContinuation

継続にかかわるところだけを変更しているので差分を取れば、継続の実装に必要な個所がわかります。(上記のコードだけでなくあちこち書き換えています)


実行例

継続を使った処理の中断を試してみます。

> (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をとりあえず実装できることがわかりました。