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

#はじめに
Javaで実装したSchemeを[Wikipedia](https://ja.wikipedia.org/wiki/Scheme)で調べてみると、以下の３つが見つかります。

1. Jscheme
1. JAKLD - Java アプリケーション組み込み用のLISPドライバ
1. 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](http://www.geocities.jp/m_hiroi/clisp/clispb12.html)というページを見つけました。これを見ると継続のない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](https://qiita-image-store.s3.amazonaws.com/0/78427/460b85ee-fef5-8240-38f6-ec6158b26076.png)

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

[SchemeMinimum](https://github.com/saka1029/SchemeMinimum)

#継続の実装

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

```java:Cont.java
public interface Cont {

    Obj apply(Obj result);

}
```

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

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

```java: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);
    }
```

この要領で`eval`と`apply`の実装を変更していきます。

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

```java:Lisp.java
        ENV.define(symbol("call/cc"), (Procedure) (args, cont) ->
            ((Procedure)args.car()).apply(list(new Continuation(cont)), cont));
```

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

```java: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](https://github.com/saka1029/SchemeWithContinuation)

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

#実行例

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

```scm
> (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`の実行をスキップして結果が返っているのがわかります。
次に計算途中の継続をグローバル変数に保存しておいて再実行する例です。

```scm
> (define C '())
> (+ 1 (* 2 (call/cc (lambda (cont) (set! C cont) 3))))
7
> (C 10)
21
> (C 100)
201
```

`(+ 1 (* 2 3))`の`3`の部分を置き換えて再実行しているのがわかります。
次は継続を使ってループする例です。

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