不動点関数(反則版)のJava実装

自分の頭の悪さを晒すようで恥ずかしいんだけど、勉強中に作ったクラスを上げるよ。

Y combinatorが分からない

HTMLテンプレートと関数型言語の接点を探るべく関数型言語の勉強を始めたのはいいけど、さっぱり要領を得ない。Java でラムダ - IT戦記のY combinatorなんかJavaで書いてあるはずなのに全然意味が分からない……。

分からないままなのもなんなので、あちこちで説明文を読んでみた……やっぱり分からない。仕方がないのでとりあえず、完全なY combinatorになる前の、不動点関数の実装(結城先生のところのhttp://www.hyuki.com/t/200508.html#i20050827064837のもの)の、さらに具象化したバージョン(具体的に型などを決め打ちしたもの)をJavaで書いてみた。

とりあえず、これを把握した後、404 Blog Not Found:TuringとChurchの狭間でを読んで、その後Java でラムダ - IT戦記を読めば少しは分かるんじゃないかと期待。

ソースコード

// 実際は別々のファイルです

/** 関数。易しくする為に、引数は1つで、引数と戻り値はintに決め打ち */
public interface Func {
    int call(int arg);
}

/** 関数を生成するもの */
public interface FuncMaker {
    Func make(Func func);
}

/** 不動点関数(反則版) */
public class FixUtils {
    public static Func fix(final FuncMaker funcMaker) {
        return funcMaker.make(new Func() {
            public int call(int n) {
                return fix(funcMaker).call(n); // 反則らしい
            }
        });
    }
}

これでフィボナッチ関数を作る

/** フィボナッチ関数を生成するFuncMaker */
public  class FibMaker implements FuncMaker {
    public Func make(final Func func) {
        return new Func() {
            public int call(int n) {
                return (n <= 1) ? 1 : (func.call(n - 1) + func.call(n - 2));
            }
        };
    }
}

実際に動かしてみる

        Func fib = FixUtils.fix(new FibMaker());
        for (int i = 1; i <= 10; i++) {
            System.err.println("fib(" + i + ") = " + fib.call(i));
        }

出力結果

fib(1) = 1
fib(2) = 2
fib(3) = 3
fib(4) = 5
fib(5) = 8
fib(6) = 13
fib(7) = 21
fib(8) = 34
fib(9) = 55
fib(10) = 89

階乗計算バージョン

/** 階乗関数を生成するFuncMaker */
public  class FactMaker implements FuncMaker {
    public Func make(final Func func) {
        return new Func() {
            public int call(int n) {
                return (n <= 1) ? 1 : (n * func.call(n - 1));
            }
        };
    }
}

出力結果

fact(1) = 1
fact(2) = 2
fact(3) = 6
fact(4) = 24
fact(5) = 120
fact(6) = 720
fact(7) = 5040
fact(8) = 40320
fact(9) = 362880
fact(10) = 3628800

さらに具体的に変更

無名クラスを使わないように変更。
このプログラムで見る限り、FactMaker内のFuncとfix()内のFuncは同じ型である必要はない。そこでfix内のFuncはBridgeというFuncとは継承関係を持たない実クラスに変更
FactMaker内のFuncはFactFuncというFuncの実装クラスに変更

/** 関数を生成するもの (引数をFuncからBridgeに変更) */
public interface FuncMaker {
    Func make(Bridge bridge);
}

/** fix内で使用するブリッジ的なもの */
public class Bridge {
    FuncMaker funcMaker;
    public Bridge(FuncMaker funcMaker) {
        this.funcMaker = funcMaker;
    }
    public int bridgeCall(int n) {
        return FixUtils.fix(this.funcMaker).call(n);
    }
}

/** 不動点関数(反則版) */
public class FixUtils {
    public static Func fix(final FuncMaker funcMaker) {
        return funcMaker.make(new Bridge(funcMaker));
    }
}

/** 再帰に利用するBridgeをコンストラクタの引数に取る階乗関数 */
public class FactFunc implements Func {
    private Bridge bridge;
    public FactFunc(Bridge bridge) {
        this.bridge = bridge;
    }
    public int call(int n) {
        return (n <= 1) ? 1 : (n * bridge.bridgeCall(n - 1));
    }
}

/** 階乗関数を生成するFuncMaker */
public  class FactMaker implements FuncMaker {
    public Func make(final Bridge bridge) {
        return new FactFunc(bridge);
    }
}

生成・呼び出し順序が分かり易いようにトレースログを出力するようにした結果
(FixUtils.fix(new FactMaker()).call(5)を実行)

[FactMaker@ef22f8]<init>
  FixUtils#fix(): FactMaker@ef22f8
  [Bridge@b4199]<init>: FactMaker@ef22f8
  [FactMaker@ef22f8]make(): Bridge@b4199
  [FactFunc@8558d2]<init>: Bridge@b4199
  [FactFunc@8558d2]call(): 5
  [Bridge@b4199]call(): 4
    FixUtils#fix(): FactMaker@ef22f8
    [Bridge@8a47e0]<init>: FactMaker@ef22f8
    [FactMaker@ef22f8]make(): Bridge@8a47e0
    [FactFunc@74cc1f]<init>: Bridge@8a47e0
    [FactFunc@74cc1f]call(): 4
    [Bridge@8a47e0]call(): 3
      FixUtils#fix(): FactMaker@ef22f8
      [Bridge@50e1f]<init>: FactMaker@ef22f8
      [FactMaker@ef22f8]make(): Bridge@50e1f
      [FactFunc@e24e2a]<init>: Bridge@50e1f
      [FactFunc@e24e2a]call(): 3
      [Bridge@50e1f]call(): 2
        FixUtils#fix(): FactMaker@ef22f8
        [Bridge@79c285]<init>: FactMaker@ef22f8
        [FactMaker@ef22f8]make(): Bridge@79c285
        [FactFunc@d1e604]<init>: Bridge@79c285
        [FactFunc@d1e604]call(): 2
        [Bridge@79c285]call(): 1
          FixUtils#fix(): FactMaker@ef22f8
          [Bridge@54172f]<init>: FactMaker@ef22f8
          [FactMaker@ef22f8]make(): Bridge@54172f
          [FactFunc@27b4d]<init>: Bridge@54172f
          [FactFunc@27b4d]call(): 1
fact(5) = 120

とりあえず、関数を生成するもの(FactMaker)を持ち回して関数(FactFunc)を呼ぶ度に作るってことってのは分かった。
道は遠い……