Javaでチャーチ数

「関数型のテンプレートエンジンで計算 - terazzoの日記」でテンプレートエンジン上でチャーチ数を使って計算してみる際に、どうにも内容が理解できずに詰まったので、Javaで実装してみた。

プログラムとしての動きをつかむことが目的なので全部をλで書き下したりはしていない。

下のサイトがとても参考になった。しかし型があるって素晴らしい。

• ex2.6 Church数 - tszの日記
• http://igeta.cocolog-nifty.com/blog/2009/04/pred.html

チャーチ数を表すインタフェース

まず、チャーチ数の定義だけど、

直感的には、数 n はラムダ式では f という関数をもらってそれを n 回適用したものを返す関数である。つまり、チャーチ数は1引数関数を受け取り、1引数関数を返す高階関数である。

ラムダ計算 - Wikipedia

とあるけど関数を戻すのは面倒なので関数fと中身xを引数にとり、xにfをn回適用した結果を戻す形で定義する。

public interface Church {
    <T> T apply(Function<T, T> f, T x);
}

Functionは例によってGoogle guavaの奴です。自分で定義してもいい。

最初インタフェースに型パラメータを付けていたけど、それだとべき乗やデクリメントで困るので、型パラメータはメソッドに付けている。

zeroおよび数値の直接実装例

インタフェース Churchを使って、まず0を実装する。
fとxを取り、xにfを0回適用したって事は、つまり適用せずにxそのままが値になる。

    Church zero = 
        new Church() {
            public <T> T apply(Function<T, T> f, T x) {
                return x;
            }
        };

次に、1と2を直接実装してみる。

    Church one = 
        new Church() {
            public <T> T apply(Function<T, T> f, T x) {
                return f.apply(x);
            }
        };
    Church two = 
        new Church() {
            public <T> T apply(Function<T, T> f, T x) {
                return f.apply(f.apply(x));
            }
        };

ちゃんと定義できたかを確認する。
fに「渡された値に1を足す」という処理を指定し、xに「0」を指定すれば、ChurchをIntegerに変換できる。

    // Church nをIntegerに変換する。
    public static Integer toInteger(Church n) {
        Function<Integer, Integer> inc =
            new Function<Integer, Integer>() {
                public Integer apply(Integer n) {
                    return n + 1;
                }
            };
        return n.apply(inc, 0);
    }

zero, one, twoを表示してみる。

    @Test
    public void testNums() {
        Integer zeroNum = toInteger(zero);
        Integer oneNum = toInteger(one);
        Integer twoNum = toInteger(two);

        assertEquals(0, zeroNum.intValue());
        assertEquals(1, oneNum.intValue());
        assertEquals(2, twoNum.intValue());

        System.out.printf("zero = %d\n", zeroNum);
        System.out.printf("one = %d\n", oneNum);
        System.out.printf("two = %d\n", twoNum);
    }

結果

zero = 0
one = 1
two = 2

succの実装

数をインクリメントするメソッドsuccを実装する。
n回fを適用したものに、もう一回fを適用すればよい。

    Church succ(final Church n) {
        return new Church() {
            public <T> T apply(Function<T, T> f, T x) {
                return f.apply(n.apply(f, x));
            }
        };
    }

適用してみる。

    Church three = succ(two);
    Church four = succ(three);
    Church five = succ(four);

中身を表示して確認してみる

    @Test
    public void testSucc() {
        Integer threeNum = toInteger(three);
        Integer fourNum = toInteger(four);
        Integer fiveNum = toInteger(five);

        assertEquals(3, threeNum.intValue());
        assertEquals(4, fourNum.intValue());
        assertEquals(5, fiveNum.intValue());

        System.out.printf("three = %d\n", threeNum);
        System.out.printf("four = %d\n", fourNum);
        System.out.printf("five = %d\n", fiveNum);
    }

表示

three = 3
four = 4
five = 5

plusの実装

数同士を足し合わせるplusを定義してみる。
「fをn回適用したものに、fをm回適用する」機能を持つChurchを戻す。

    Church plus(final Church m, final Church n) {
        return new Church() {
            public <T> T apply(Function<T, T> f, T x) {
                return m.apply(f, n.apply(f, x));
            }
        };
    }

足してみる。

    Church six = plus(two, four);
    Church seven = plus(four, three);
    Church eight = plus(three, five);

中身を表示して確認してみる

    @Test
    public void testPlus() {
        Integer sixNum = toInteger(six);
        Integer sevenNum = toInteger(seven);
        Integer eightNum = toInteger(eight);

        assertEquals(6, sixNum.intValue());
        assertEquals(7, sevenNum.intValue());
        assertEquals(8, eightNum.intValue());

        System.out.printf("six = %d\n", sixNum);
        System.out.printf("seven = %d\n", sevenNum);
        System.out.printf("eight = %d\n", eightNum);
    }

表示

six = 6
seven = 7
eight = 8

multiplyの実装

数同士を足し合わせるmultiplyを定義してみる。
「fをn回適用する」という処理をxにm回適用する。一応変数名をyに変えているが特に必要はない

    Church multiply(final Church m, final Church n) {
        return new Church() {
            public <T> T apply(final Function<T, T> f, T x) {
                return m.apply(new Function<T, T>() {
                    public T apply(T y) {
                        return n.apply(f, y);
                    }
                }, x);
            }
        };
    }

結果を確認

    @Test
    public void testMultiply() {
        Integer oneByZeroNum = toInteger(multiply(one, zero));
        Integer threeByTwoNum = toInteger(multiply(three, two));

        assertEquals(6, threeByTwoNum.intValue());
        assertEquals(0, oneByZeroNum.intValue());

        System.out.printf("three x two = %d\n", threeByTwoNum);        
        System.out.printf("one x zero = %d\n", oneByZeroNum);        
    }

three x two = 6
one x zero = 0

powerの実装

べき乗の計算を実装する。
ここから急に難しくなる。fにnをm回適用し、その結果をxに適用するらしい。
戻り値や引数の型から、Function型の型パラメータを推測しながら当てはめていく。

    //  (lambda (f) (lambda (x) (((m n) f) x))) )
    Church power(final Church n, final Church m) {
        return new Church() {
           public <T> T apply(Function<T, T> f, T x) {
                return m.<Function<T, T>>apply(
                        new Function<Function<T, T>, Function<T, T>>(){
                            public Function<T, T> apply(final Function<T, T> _f) {
                                return new Function<T, T>() {
                                    public T apply(T _x) {
                                        return n.apply(_f, _x);
                                    }
                                };
                            }
                        },
                        f
                    ).apply(x);
            }
        };
    }

内側の_fと_xはどの値か明確にしたかっただけで、特に名前を変える必要はないです。
動かしてみる。

    @Test
    public void testPower() {
        Integer fourPowerOfThreeNum = toInteger(power(four, three));
        Integer fivePowerOfZeroNum = toInteger(power(five, zero));

        assertEquals(64, fourPowerOfThreeNum.intValue());
        assertEquals(1, fivePowerOfZeroNum.intValue());

        System.out.printf("four ^ three = %d\n", fourPowerOfThreeNum);        
        System.out.printf("five ^ zero = %d\n", fivePowerOfZeroNum);        
    }

出力

four ^ three = 64
five ^ zero = 1

predの実装

succの逆、つまり一つ小さい数(predecessor)を戻す処理を考える。
いや、考えても分からないので戻り値や引数の型から、型を推測しながら写経していく。

    Church pred(final Church n) {
        return new Church() {
            public <T> T apply(final Function<T, T> f, final T x) {
                return
                    (n.<Function<Function<T, T>,T>>apply(
                        new Function<Function<Function<T, T>, T>, Function<Function<T, T>, T>>() {
                            public Function<Function<T, T>, T> apply(final Function<Function<T, T>, T> g) {
                                return new Function<Function<T, T>, T>(){
                                    public T apply(Function<T, T> h) {
                                        return h.apply(g.apply(f));
                                    }
                                };
                            }
                         },
                        new Function<Function<T, T>,T>() {
                            public T apply(Function<T, T> f) {
                                return x;
                            }
                        }
                    ))
                    .apply(new Function<T, T>() {
                        public T apply(T u) {
                            return u;
                        }});
                }

            };
    }

動かしてみる。

    @Test
    public void testPred() {
        Integer predOfThreeNum = toInteger(pred(three));
        Integer predOfZero = toInteger(pred(zero));
        assertEquals(2, predOfThreeNum.intValue());
        assertEquals(0, predOfZero.intValue());
        System.out.printf("pred(three) = %d\n", predOfThreeNum);
        System.out.printf("pred(zero) = %d\n", predOfZero);
        
        Integer predOfSuccOfSixNum = toInteger(pred(succ(six)));
        assertEquals(toInteger(six), predOfSuccOfSixNum);
        
    }

出力。

pred(three) = 2
pred(zero) = 0

負の数はなくpred(zero)はzeroになる。

minusの実装

引き算を実装する。
mからnを引くには、mにn回predを適用すればよい。

    // n pred m
    Church minus(final Church m, final Church n) {
        return n.apply(new Function<Church, Church>() {
            public Church apply(Church c) {
                return pred(c);
            }
        }, m);
    }

実行してみる。

    @Test
    public void testMinus() {
        Integer fiveFromEightNum = toInteger(minus(eight, five));
        Integer threeFromTwoNum = toInteger(minus(two, three));

        assertEquals(3, fiveFromEightNum.intValue());
        assertEquals(0, threeFromTwoNum.intValue());

        System.out.printf("eight - five = %d\n", fiveFromEightNum);
        System.out.printf("two - three = %d\n", threeFromTwoNum);       
    }

出力

eight - five = 3
two - three = 0

負の数はなくmよりnが大きい場合はzeroになる。

割り算などの他の計算

ラムダ計算の範囲でいけるらしい。
今回は主旨から外れるので深入りしない。