今天被老莊拉到JavaEye扯皮，扯來扯去還是lambda演算...本來應(yīng)承了老莊寫lambda演算簡介，不過看到磐石T1同學(xué)提到了Church number來勾引whl同學(xué)...于是我想還是寫一些更有意思的東西吧。

每個(gè)Church number都是一個(gè)接受兩個(gè)參數(shù)的函數(shù)，這兩個(gè)參數(shù)又都是函數(shù)，第一個(gè)參數(shù)稱為后繼函數(shù)，第二個(gè)參數(shù)則叫做零點(diǎn)函數(shù)。依據(jù)這兩個(gè)函數(shù)，我們可以定義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就是對零點(diǎn)函數(shù)應(yīng)用一次后繼函數(shù)，而two則是對零點(diǎn)函數(shù)應(yīng)用后繼函數(shù)的結(jié)果再次應(yīng)用后繼函數(shù)，依次類推可以得到Church Number n。下面我們可以通過后繼函數(shù)increase和零點(diǎn)函數(shù)f(x) = 0來看看這些Church Number的計(jì)算結(jié)果：

(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后，我們繼續(xù)定義Church number上的運(yùn)算，首先是增加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當(dāng)年發(fā)明這套東西的時(shí)候就沒有。原因是非常明顯的...因此Church number只有后繼函數(shù)，而沒有前驅(qū)函數(shù)。也就是說Church number只能往前數(shù)...不能望后數(shù)...自然不可能作出減法和除法了。當(dāng)然擴(kuò)展一下也是非常容易的：

(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同學(xué)問這樣能不能實(shí)現(xiàn)浮點(diǎn)，答案是可以實(shí)現(xiàn)有限精度的浮點(diǎn)數(shù)....因?yàn)榘凑者@個(gè)思路發(fā)展下去，我們定義浮點(diǎn)的successor和precursor函數(shù)只能在有限的位數(shù)之內(nèi)...當(dāng)然有了one,zero再結(jié)合pair，模擬0/1存儲(chǔ)實(shí)現(xiàn)浮點(diǎn)也不是不可能的事情...