はじめに

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

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

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

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

SchemeMinimum

継続の実装

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

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

}

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

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