続・不動点関数のJava実装

fix()からのfix()への言及を無くす

前回のでほぼ完成していた。
Bridgeから呼んでいるFixUtils.fix()を展開してやるだけ

/** ブリッジ的なもの */
public class Bridge {
    private FuncMaker funcMaker;
    public Bridge(FuncMaker funcMaker) {
        this.funcMaker = funcMaker;
    }
    public int bridgeCall(int n) {
        return funcMaker.make(new Bridge(funcMaker)).call(n);
    }
}

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

funcMaker.make(new Bridge(funcMaker))が二箇所に現れているのがさっぱり美しくないだべさ(そうか？)
のでクラスFix0にくくり出す

/** コンストラクタの引数をFuncMakerからFix0に変更 */
public class Bridge implements Func {
    private Fix0 fix0;
    public Bridge(Fix0 fix0) {
        this.fix0 = fix0;
    }
    public int call(int n) {
        return fix0.make0(fix0).call(n);
    }
}
/** funcMaker.make(new Bridge(funcMaker))をくくり出す */
public class Fix0 {
    private FuncMaker funcMaker;
    public Fix0(FuncMaker funcMaker) {
        this.funcMaker = funcMaker;
    }
    public Func make0(final Fix0 fix0) {
        return funcMaker.make(new Bridge(fix0));
   }
}

/** 不動点関数 */
public class FixUtils {
    /** funcMaker.make(new Bridge(funcMaker))をくくり出した残り */
    public static Func fix(final FuncMaker funcMaker) {
        return new Fix0(funcMaker).make0(new Fix0(funcMaker));
    }
}

なんとなくそれっぽい形が見えて来た

BridgeとFuncのインタフェースを揃える

不動点としての体裁を整える為に、BridgeをFuncの実装クラスに変更。
(あと見やすいように全体を1ファイルで書けるようにクラスをstaticに変更)

public class FixUtils {
    /** 関数。易しくする為に、引数は1つで、引数と戻り値はintに決め打ち */
    public interface Func {
        int call(int arg);
    }
    /** 関数を生成するもの */
    public interface FuncMaker {
        Func make(Func func);
    }

    /** 呼び出される際に本物の関数を生成して呼び出すブリッジ的なもの */
    static class Bridge implements Func {
        private Fix0 fix0;
        Bridge(Fix0 fix0) {
            this.fix0 = fix0;
        }
        public int call(int n) {
            return fix0.make0(fix0).call(n);
        }
    }
    
    static class Fix0 {
        private FuncMaker funcMaker;
        Fix0(FuncMaker funcMaker) {
            this.funcMaker = funcMaker;
        }
        public Func make0(final Fix0 fix0) {
            return funcMaker.make(new Bridge(fix0));
       }
    }
    
    /** 不動点関数 */
    public static Func fix(final FuncMaker funcMaker) {
        return new Fix0(funcMaker).make0(new Fix0(funcMaker));
    }


    /* 使用例  */

    /** 階乗関数 */
    public static class FactFunc implements Func {
        private Func next;
        public FactFunc(Func next) {
            this.next = next;
        }
        public int call(int n) {
            return (n <= 1) ? 1 : (n * next.call(n - 1));
        }
    }

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

    public static void main(String[] args) {
        FactMaker fm = new FactMaker();

        // fixしたもの
        Func factFixed = FixUtils.fix(fm);		// どんな大きな数にも使える階乗関数
        System.out.println("factFixed(10) = " + factFixed.call(10));
        Func factFixed2 = fm.make(FixUtils.fix(fm));	// もう一度繰り返しても同じ挙動の関数ができる(不動点？)
        System.out.println("factFixed2(10) = " + factFixed2.call(10));
        
        // fixしていないもの
        Func fact4 = fm.make(fm.make(fm.make(fm.make(null))));
        System.out.println("fact4(4) = " + fact4.call(4));	// 4までなら使える
        System.out.println("fact4(5) = " + fact4.call(5));	// ぬるぽ        
    }
}

不動点っていうことがなんとなく分かったような気がする。

無名クラスの形に戻してみる

FactMaker/FactFuncを無名クラスで書いてみる

    public static void main(String[] args) {
        // fixしたもの
        Func factFixed = FixUtils2.fix(
                new FuncMaker() {		// 元FactMaker
                    public Func make(final Func next) {
                        return new Func() {	// 元FactFunc
                            public int call(int n) {
                                return (n <= 1) ? 1 : (n * next.call(n - 1));
                            }
                        };
                    }
                }
            ); // どんな大きな数にも使える階乗関数
        System.out.println("factFixed(5) = " + factFixed.call(5));
    }

当然ちゃんと動く

そしてFix0内のBridgeを無名クラス化

    static class Fix0 {
        private FuncMaker funcMaker;
        Fix0(FuncMaker funcMaker) {
            this.funcMaker = funcMaker;
        }
        public Func make0(final Fix0 fix0) {
            return funcMaker.make(new Func() {	// 元Bridge
                public int call(int n) {
                    return fix0.make0(fix0).call(n);
                }
            });
       }
    }

さらにFix0をインタフェース化し、無名クラスとして書き下ろす

    interface Fix0 {
        Func make0(Fix0 fix0);
    }
    
    /** 無名クラスを使った不動点関数 */
    public static Func fix(final FuncMaker funcMaker) {
        return new Fix0(){				// 元Fix0クラス
            public Func make0(final Fix0 fix0) {
                return funcMaker.make(new Func() {	// 元Bridge
                    public int call(int n) {
                        return fix0.make0(fix0).call(n);
                    }
                });
           }
        }.make0(new Fix0(){				// 元Fix0クラス
            public Func make0(final Fix0 fix0) {
                return funcMaker.make(new Func() {	// 元Bridge
                    public int call(int n) {
                        return fix0.make0(fix0).call(n);
                    }
                });
           }
        });
    }

こうするとJava でラムダ - IT戦記のy combinatorや"「どう書く？org」の不動点演算子の回答例とほぼ同じ形になる。
あとはFuncをlambda関数化して、Fix0をFuncに置き換えればより一致するのではないかと思う。

無名クラスにする前のものをGenerics化

int->int以外でも使えるようにGenerics化してみた。
Dが引数の型、Rが戻り値の型

    /**
     * 関数
     * @param <D> 引数の型
     * @param <R> 戻り値の型
     */
    interface Func<D, R> {
        R call(D arg);
    }

    /** 関数を作るもの*/
    interface FuncMaker<D, R> {
        Func<D, R> make(Func<D, R> func);
    }

    /** 呼び出される際に本物の関数を呼び出すブリッジ的なもの */
    static class Bridge<D, R> implements Func<D, R> {
        Fix0<D, R> fix0;
        public Bridge(Fix0<D, R> fix0) {
            this.fix0 = fix0;
        }
        public R call(D arg) {
            return this.fix0.make0(this.fix0).call(arg);
        }
    }
    
    /** funcMaker.make(new Bridge(funcMaker))をくくり出したもの */
    static class Fix0<D, R> {
        FuncMaker<D, R> funcMaker;
        Fix0(FuncMaker<D, R>funcMaker) {
            this.funcMaker = funcMaker;
        }
        public Func<D, R> make0(final Fix0<D, R> fix0) {
            return funcMaker.make(new Bridge<D, R>(fix0));
       }
    }
    
    /** 不動点関数 */
    public static <D, R> Func<D, R> fix(final FuncMaker<D, R> funcMaker) {
        return new Fix0<D, R>(funcMaker).make0(new Fix0<D, R>(funcMaker));
    }

使用例1. 階乗

    /** 階乗関数(Integer->Integer) */
    public static class FactFunc implements Func<Integer, Integer> {
        private Func<Integer, Integer> next;
        public FactFunc(Func<Integer, Integer> next) {
            this.next = next;
        }
        public Integer call(Integer n) {
            return (n <= 1) ? 1 : (n * next.call(n - 1));
        }
    }

    /** 階乗関数をつくるもの */
    public static class FactMaker implements FuncMaker<Integer, Integer> {
        public Func<Integer, Integer> make(Func<Integer, Integer> next) {
            return new FactFunc(next);
        }
    }

    public static void main(String[] args) {
        Func<Integer, Integer> fact = FixUtils.fix(new FactMaker());
        System.out.println("fact(5) = " + fact.call(5));
    }

使用例2. 数字文字列を数値に変換

    /** 再帰的に文字列を数値に変換関数(String->Integer)  */
    public static class AtoiFunc implements Func<String,Integer> {
        private Func<String,Integer>  next;
        public AtoiFunc(Func<String,Integer> next) {
            this.next = next;
        }
        /**
         * 長さが0ならば0を、そうでなければ末尾の文字を対応する0から9の数に変換したものと
         * 末尾を除いた文字列を数値化したものを10倍したものを足した値を戻す
         * @param rep 数字文字列
         */
        public Integer call(String rep) {
            return (rep == null || rep.length() == 0)
                 ? 0
                 : digitToInteger(rep.charAt(rep.length() - 1))		   // 末尾一桁
                     + 10 * next.call(rep.substring(0, rep.length() - 1)); // 末尾を除いたものを10倍
        }
        /** '0'~'9'を0~9に変換 */
        private static Integer digitToInteger(char c) {
            return ('0' <= c && c <= '9') ? (c - '0') : 0;
        }
    }

    /** 変換関数をつくるもの */
    public static class AtoiMaker implements FuncMaker<String, Integer> {
        public Func<String, Integer> make(Func<String, Integer> next) {
            return new AtoiFunc(next);
        }
    }

    public static void main(String[] args) {
        Func<String, Integer> atoi = FixUtils.fix(new AtoiMaker());
        System.out.println("atoi(\"12345\") = " + atoi.call("12345"));

    }

感想など

最初の例から見て行けば、全て無名クラス(あるいはlambdaっぽいもの)で書かれたものと比べて意味は分かり易いかと思う。
苦し紛れにくくり出したFix0とmake0()が意味的にどういうものなのかがよく分からないのが痛い。

そもそもはfaceletsでdecorate/define/insertする際にYコンビネータ的なテンプレートファイルが作れたら面白いなあと思って調べ出したんだけど、結局そっちは上手くいか無そう。insertするパーツをdecorate側でdefineして渡した場合、パーツ内部の評価時はinsertしている側のスコープで動いているっぽいので、クロージャなんかとはまた違う動きになりそう。insertタグはdefineもparamも渡せないし。(そういうtaglibを作るというのはありかも。)

define/insertは十分eval/apply的な存在だと思うのだけど……もう少し考えてみたい。

(追記1.) 無名クラス版 + Generics化

Schemeでの実装例などを見ていると、Fix0の部分がどうやらfact-makerなどに当たる部分のようだ。
Fix0をFuncMakerという型名にし、元のFuncMakerは内容にあわせてFuncFactoryと名前を変えた。

package sample.fix;

public class FixUtils {
    /** 関数 */
    public interface Func<D, R> {
        R call(D arg);
    }
    /** 個々のFuncインスタンスを生成するためのもの */
    public interface FuncFactory<D,R> {
        Func<D, R> newInstance(Func<D, R> nextFunc);
    }
    /** 自己適用により逐次、関数を生成して返す */
    private interface FuncMaker<D, R> {
         Func<D, R> makeFunc(FuncMaker<D, R> funcMaker);
    }

    /** 不動点関数 */
    public static <D, R> Func<D, R> fix(final FuncFactory<D,R> factory) {
        return new FuncMaker<D, R>() {
            public Func<D, R> makeFunc(final FuncMaker<D, R> funcMaker) {
                return factory.newInstance(new Func<D, R>() {
                    public R call(D arg) {
                        return funcMaker.makeFunc(funcMaker).call(arg);
                    }
                });
            }
        }.makeFunc(new FuncMaker<D, R>(){
            public Func<D, R> makeFunc(final FuncMaker<D, R> funcMaker) {
                return factory.newInstance(new Func<D, R>() {
                    public R call(D arg) {
                        return funcMaker.makeFunc(funcMaker).call(arg);
                    }
                });
            }
        });
    }
}

使用サンプル

import sample.fix.FixUtils;
import sample.fix.FixUtils.Func;
import sample.fix.FixUtils.FuncFactory;
public class FixSample {
    /** 階乗を計算 */
    public static void main(String[] args) {
        Func<Integer, Integer> fact = FixUtils.fix(new FuncFactory<Integer, Integer>() {
            public Func<Integer, Integer> newInstance(final Func<Integer, Integer> next) {
                return new Func<Integer, Integer>() {
                    public Integer call(Integer n) {
                        return (n <= 1) ? 1 : (n * next.call(n - 1));
                    }
                };
            }
        });
        System.out.println("fact(5) = " + fact.call(5));
    }
}

単に不動点を作るという意味なら、これで完成版じゃないだろうか。

(追記2.) インタフェースをFuncで統一

折角なので定義をFuncのみにしてみたい。
FuncFactoryはFunc,Func>として書く事も出来る。

    /** 不動点関数(FuncFactory使わない版) */
    public static <D, R> Func<D, R> fix(final Func<Func<D, R>, Func<D, R>> factory) {
        return new FuncMaker<D, R>() {
            public Func<D, R> makeFunc(final FuncMaker<D, R> funcMaker) {
                return factory.call(new Func<D, R>() {
                    public R call(D arg) {
                        return funcMaker.makeFunc(funcMaker).call(arg);
                    }
                });
            }
        }.makeFunc(new FuncMaker<D, R>(){
            public Func<D, R> makeFunc(final FuncMaker<D, R> funcMaker) {
                return factory.call(new Func<D, R>() {
                    public R call(D arg) {
                        return funcMaker.makeFunc(funcMaker).call(arg);
                    }
                });
            }
        });
    }

    /** 階乗を計算 */
    public static void main(String[] args) {
        Func<Integer, Integer> fact = FixUtils.fix(new Func<Func<Integer, Integer>, Func<Integer, Integer>>() {
            // メソッド名をnewInstanceからcallに変更
            public Func<Integer, Integer> call(final Func<Integer, Integer> next) {
                return new Func<Integer, Integer>() {
                    public Integer call(Integer n) {
                        return (n <= 1) ? 1 : (n * next.call(n - 1));
                    }
                    
                };
            }
        });
        System.out.println("fact(5) = " + fact.call(5));
    }

FuncMakerをFuncで置き換えられないか。FuncMakerはFunc,Func>であり、定義側にもFuncMakerが出てくるのでうまくいかない。あえて型安全を捨ててキャストすれば下のような感じ

    /** 不動点関数(Funcのみで記述) */
    @SuppressWarnings("unchecked")
    public static <D, R> Func<D, R> fix(final Func<Func<D, R>, Func<D, R>> factory) {
        return new Func<Func<Func, Func<D, R>> , Func<D,R>>(){
            public Func<D, R> call(final Func<Func, Func<D, R>> funcMaker) {
                return factory.call(new Func<D, R>() {
                    public R call(D arg) {
                        return funcMaker.call(funcMaker).call(arg);
                    }
                });
            }  /*↓↓ここでキャスト発生↓↓*/
        }.call((Func<Func, Func<D, R>>) new Func<Func<Func, Func<D, R>> , Func<D,R>>(){
            public Func<D, R> call(final Func<Func, Func<D, R>> funcMaker) {
                return factory.call(new Func<D, R>() {
                    public R call(D arg) {
                        return funcMaker.call(funcMaker).call(arg);
                    }
                });
            }
        });
    }

プログラムを自動検証したりするならともかく、普通に使う分には読みにくくなるばかりであまり意味があるとは思えない。