Java でラムダ

λ... λ... ちょっととおりますよ

はじめに

C++ Template の勉強をしていて、気がついた。

• ネストした（内側から外側が見える）名前-値の空間が存在し
• 値から名前-値の空間を生成することが可能で
• その空間を生成するための情報を値として扱え
• 名前-値の空間の中の一つ以上の値を取り出せると

ラムダが出来る。

という訳で Java でラムダを作ってみた

import static java.lang.System.out;

public class Hoge {
    public static void main (String args[]) {

        // チャーチ数 0
        final λ zero = new λ () { λ call (final λ f) {
            return new λ () { λ call (final λ x) {
                return x;
            }};
        }};

        // チャーチ数の succ
        final λ succ = new λ () { λ call (final λ n) {
            return new λ () { λ call (final λ f) {
                return new λ () { λ call (final λ x) {
                    return f.call(n.call(f).call(x));
                }};
            }};
        }};

        // チャーチ数の plus
        final λ plus = new λ () { λ call (final λ n) {
            return new λ () { λ call (final λ m) {
                return new λ () { λ call (final λ f) {
                    return new λ () { λ call (final λ x) {
                        return m.call(f).call(n.call(f).call(x));
                    }};
                }};
            }};
        }};

        out.println(
            // ((0++)++)+((0++)+((0++)++))
            // 2+(1+2)
            // 2+3
            // 5
            plus.call(succ.call(succ.call(zero)))
                .call(
                    plus.call(succ.call(zero))
                    .call(succ.call(succ.call(zero))))

                    // int 化
                    .call(new λ () { λ call (final λ b) { 
                        return new V () { int v() { return b.v() + 1; }};
                     }})
                    .call(new V() { int v() { return 0; }})
        );

        // y combinator
        final λ y = new λ () { λ call (final λ f) {
            return new λ () { λ call (final λ g) {
                return new λ () { λ call (final λ m) {
                    return f.call(g.call(g)).call(m);
                }};
            }}.call(new λ () { λ call (final λ g) {
                return new λ () { λ call (final λ m) {
                    return f.call(g.call(g)).call(m);
                }};
            }});
        }};

        // fibonatti
        final λ fib = y.call(new λ () { λ call (final λ fib) {
            return new λ () { λ call (final λ a) {
                return (a.v() < 2) ? a : new V () { int v() {
                    return fib.call(new V() {int v() {
                            return a.v() - 1;
                        }}).v() + 
                        fib.call(new V() { int v() {
                            return a.v() - 2;
                        }}).v();
                }};
            }};
        }});

        out.println(
            // fib(10) = 55
            fib.call(new V () { int v() { return 10; }})
        );
    }
}

abstract class λ {
    abstract λ call(λ a);
    λ call(V a) { return this.call((λ)a); }
    int v() { throw new RuntimeException(); }
}

abstract class V extends λ {
    λ call(λ a) { throw new RuntimeException(); }
    abstract int v();
    public String toString() {
        return "" + this.v();
    }
}

Java のλの特徴

見ての通り、無名クラスはそのスコープの final な変数を扱えるのでそれを使ってネストした名前-値の空間が出来る。
しかも、 final しか扱えないのでインスタンスフィールドを使わなければ参照透明だ。
ただ、 a = λx.a(x -1) のように再帰的なことを書こうと思うと、コンパイル時に「a がまだ初期化されてない」と怒られるので y コンビネータが必要。

(追記) 更なる勉強

コメント欄で id:alohakun に教えて貰った 結論：結局、Javaはクロージャを使えるの？ - lethevert is a programmer のコメント欄がめちゃめちゃ面白いです。