今天被老庄拉到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存储实现浮点也不是不可能的事情...