今天被老莊拉到JavaEye扯皮，扯來扯去還是lambda演算...本來應承了老莊寫lambda演算簡介，不過看到磐石T1同學提到了Church number來勾引whl同學...于是我想還是寫一些更有意思的東西吧。
每個Church number都是一個接受兩個參數的函數，這兩個參數又都是函數，第一個參數稱為后繼函數，第二個參數則叫做零點函數。依據這兩個函數，我們可以定義Church number zero, one, two：
(define zero? (lambda (successor?zero)?zero))
(define one （lambda (successor?zero)?(successor?zero)))
(define two?? (lambda (successor?zero)?(successor?(successor?zero))))
可以看出，所謂one就是對零點函數應用一次后繼函數，而two則是對零點函數應用后繼函數的結果再次應用后繼函數，依次類推可以得到Church Number n。下面我們可以通過后繼函數increase和零點函數f(x) = 0來看看這些Church Number的計算結果：
(define?(increase?x)?(+?x?1))
(zero increase 0)
> 0
(one increase 0)
>1
(two increase 0)
>2
an approximate Java version:
public interface Function<T> {
??? T apply(Object... parameters);
}
public interface ChurchNumber {
??? Integer apply(Function<Integer> successor, Function<Integer> zero);
}
ChurchNumber zero = new ChurchNumber() {
?? public Integer apply(Function<Integer> successor,? Function<Integer> zero) {
????? return zero.apply();
?? }
};
ChurchNumber one = new ChurchNumber() {
?? public Integer apply(Function<Integer> successor, Function<Integer> zero) {
????? return successor.apply(zero);
?? }
};
ChurchNumber two = new ChurchNumber() {
?? public Integer apply(Function<Integer> successor, Function<Integer> zero) {
? ? ? return successor.apply(successor.apply(zero));
?? }
};
Function increase = new Function<Integer>() {
?public Integer apply(Object... parameters) {
?? if (parameters[0] instanceof Function) {
????? return ((Function<Integer>) parameters[0]).apply() + 1;
?? }
?? return (Integer) parameters[0] + 1;
?}
};
Function numberZero = new Function<Integer>() {
?? public Integer apply(Object... parameters) { return 0;}
};
System.out.println(zero.apply(increase, numberZero));
>0
System.out.println(one.apply(increase, numberZero));
>1
System.out.println(two.apply(increase, numberZero));
>2
定義了Church number后，我們繼續定義Church number上的運算，首先是增加1：
(define?(inc?x)?(lambda (successor?zero) (successor (x successor zero))))
(define three (inc two))
(three increase 0)
>3
an approximate Java version:
static ChurchNumber inc(final ChurchNumber churchNumber) {
?? return new ChurchNumber() {
????? public Integer apply(Function<Integer> successor, Function<Integer> zero) {
??? ???? return successor.apply(churchNumber.apply(successor, zero));
??? ?? }
?? };
}
ChurchNumber three = inc(two);
System.out.println(three.apply(increase, numberZero));
>3
然后是加法：
(define?(add?x y)?(lambda (successor?zero)? (x successor (y successor zero))))
(define five (add three two))
(five increase 0)
>5
an approximate Java version:
static ChurchNumber add(final ChurchNumber x, final ChurchNumber y) {
??? ??? return new ChurchNumber() {
??? ??? ??? public Integer apply(final Function<Integer> successor,
??? ??? ??? ??? ??? final Function<Integer> zero) {
??? ??? ??? ??? return x.apply(successor, new Function<Integer>() {
??? ??? ??? ??? ??? public Integer apply(Object... parameters) {
??? ??? ??? ??? ??? ??? return y.apply(successor, zero);
??? ??? ??? ??? ??? }
??? ??? ??? ??? });
??? ??? ??? }
??? ??? };
}
ChurchNumber five = add(two, three);
System.out.println(five.apply(increase, numberZero));
>5
最后是乘法：
(define?(multiply?x?y) (lambda (successor?zero)? (x? (lambda (z) (y successor z)) zero)))
(define four (multiply two two))
(four increase 0)
>4
an approximate Java version:
static ChurchNumber multiply(final ChurchNumber x, final ChurchNumber y) {
??? ??? return new ChurchNumber() {
??? ??? ??? public Integer apply(final Function<Integer> successor,
??? ??? ??? ??? ??? Function<Integer> zero) {
??? ??? ??? ??? return x.apply(new Function<Integer>() {
??? ??? ??? ??? ??? public Integer apply(final Object... parameters) {
??? ??? ??? ??? ??? ??? return y.apply(successor, new Function<Integer>() {
??? ??? ??? ??? ??? ??? ??? public Integer apply(Object... ignoredParameters) {
??? ??? ??? ??? ??? ??? ??? ??? if (parameters[0] instanceof Function) {
??? ??? ??? ??? ??? ??? ??? ??? ??? return ((Function<Integer>) parameters[0]).apply();
??? ??? ??? ??? ??? ??? ??? ??? }
??? ??? ??? ??? ??? ??? ??? ??? return (Integer) parameters[0];
??? ??? ??? ??? ??? ??? ??? }
??? ??? ??? ??? ??? ??? });
??? ??? ??? ??? ??? }
??? ??? ??? ??? }, zero);
??? ??? ??? }
??? ??? };
}
ChurchNumber four = multiply(two, two);
System.out.println(four.apply(increase, numberZero));
沒有減法和除法，Church當年發明這套東西的時候就沒有。原因是非常明顯的...因此Church number只有后繼函數，而沒有前驅函數。也就是說Church number只能往前數...不能望后數...自然不可能作出減法和除法了。當然擴展一下也是非常容易的：
(define?negative-one?(lambda?(successor?precursor?zero)?(precursor?zero)))
(define?one?(lambda?(successor?precursor?zero)?(successor?zero)))
(define?(add?x?y)?(lambda?(successor?precursor?zero)?(x?successor?precursor?(?y?successor?precursor?zero)?)))
(define?(inc?x)?(+?x?1))
(define?(dec?x)?(-?x?1))
(define?zero?(add?one?negative-one))
(zero?inc?dec?0)
>0
whl同學問這樣能不能實現浮點，答案是可以實現有限精度的浮點數....因為按照這個思路發展下去，我們定義浮點的successor和precursor函數只能在有限的位數之內...當然有了one,zero再結合pair，模擬0/1存儲實現浮點也不是不可能的事情...