Javaで継続渡し

id:carbuncle:20060317を見て面白そうだったので、Javaで継続渡しを書いてみた。

public interface Continuable
{
    public Object applyN(Continuable cont, Object[] args);
}

public class NullContinuation implements Continuable
{
    private static NullContinuation instance;

    public static NullContinuation getInstance()
    {
        if (instance == null) {
            instance = new NullContinuation();
        }
        return instance;
    }

    // This class cannot be instantiated from outer classes.
    private NullContinuation() {}

    public Object applyN(Continuable cont, Object[] args)
    {
        return args;
    }
}

public class Fibonacci implements Continuable
{
    public Object applyN(Continuable cont, Object[] args)
    {
        int n = (Integer) args[0];
        if ((n == 1) || (n == 2)) {
            return cont.applyN(NullContinuation.getInstance(),
                               new Object[] { 1 });
        } else {
            final Fibonacci fib = this;
            final Continuable _cont = cont;
            final int _n = n;
            return fib.applyN(new Continuable() {
                    public Object applyN(Continuable cont, Object[] args) {
                        final int v1 = (Integer) args[0];
                        return fib.applyN(new Continuable() {
                                public Object applyN(Continuable cont, Object[] args) {
                                    final int v2 = (Integer) args[0];
                                    return _cont.applyN(NullContinuation.getInstance(),
                                                        new Object[] { v1 + v2 });
                                }
                            }, new Object[] { _n - 2 });
                    }
                }, new Object[] { _n - 1 });
        }
    }

    public static void main(String[] args)
    {
        NullContinuation nullCont = NullContinuation.getInstance();
        Fibonacci fib = new Fibonacci();

        for (int n = 1; n < 10; n++) {
            Object[] fibN = (Object[]) fib.applyN(nullCont, new Object[] { n });
            System.out.println("Fibonacci(" + n + ") = " + (Integer) fibN[0]);
        }
    }
}

こんな感じかな。なんかNullContinuationの辺りが一部怪しい気もするけど。
いやーJavaで無名クラスをこんな風に使いまくるコードは初めて書いた(笑)。

• 実行結果:

% java Fibonacci
Fibonacci(1) = 1
Fibonacci(2) = 1
Fibonacci(3) = 2
Fibonacci(4) = 3
Fibonacci(5) = 5
Fibonacci(6) = 8
Fibonacci(7) = 13
Fibonacci(8) = 21
Fibonacci(9) = 34

ちなみに、こんなコードをいきなり書けるわけはないので、以下のようなSchemeプログラムを書いて、それからJavaに変換した。

(define (fib n)
  (if (or (= n 1) (= n 2))
      1
      (+ (fib (- n 1))
         (fib (- n 2)))))

(define (fib_cps n k)
  (if (or (= n 1) (= n 2))
      (k 1)
      (fib_cps (- n 1)
               (lambda (v1)
                 (fib_cps (- n 2)
                          (lambda (v2)
                            (k (+ v1 v2))))))))

Schemeを知らない人にも、少しは分かってもらえたかな？（逆に分かりにくくなっているという噂も）