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