十分钟魔法练习：Y 组合子

By 「玩火」

前置技能：Java 基础，λ 演算，λ 演算编码

递归

在 Java 里面实现递归非常简单，只需要在函数内调用函数本身就好了，比如下面的求和程序：

int sum(int n) {
    if (n == 0) return 0;
    else return n + sum(n - 1);
}

这时候就会注意到看起来递归必须要函数有名字，不然怎么调用时表示自己呢？实际上有个很显然的例子：

(λ x. x x) (λ x. x x)

这个表达式无论怎么求值都会得到它自身，实际上这就是个无限递归的例子。而在它的基础上稍加修改就可以得到 Y 组合子（Y Combinator）：

Y = λ f. (λ x. f (x x)) (λ x. f (x x))

而往 Y 组合子上应用一个函数就会得到：

Y g = (λ x. g (x x)) (λ x. g (x x))
    = g ((λ x. g (x x)) (λ x. g (x x)))
    = g (Y g)

这样 g 就拿到了 Y g 也就是它自己的函数作为参数，那么就可以递归了，比如上面的 sum 就可以写成：

sum' = λ self. λ n.
    isZero n
        n
        (+ n (self (prev n)))
sum = Y sum'

n 是个丘奇数， isZero 判断数字是不是 0 并得到一个 λ 演算编码的布尔值， + 函数把两个丘奇数相加， prev 函数得到比 n 小一的数。 sum 在递归到 n 为 0 时停止递归。

求值策略

很显然如果直接使用严格求值会无限展开 Y 算子而得不到结果，如果使用惰性求值会得不到易于阅读的结果。这时候就要用一种介于两者之间的求值策略：

// class Fun
public Expr fullReduce() {
    return new Fun(x, e.fullReduce());
}
// class App
public Expr fullReduce() {
    Expr fr = f.reduce();
    if (fr instanceof Fun) {
        Fun fun = (Fun) fr;
        return fun.e.apply(fun.x, x).fullReduce();
    }
    return new App(fr.fullReduce(), x.fullReduce());
}

它只有在尝试应用函数失败的时候才会进行完全展开，这样每次只展开一点就可以避免陷入无限递归。

循环

在编码那期中介绍了如何在 λ 演算中构造分支结构，而循环循环可以用递归来表示，每个循环都可以写成循环变量作为参数的尾递归函数，实际上如下的循环：

State state;
while (needLoop(state)) {
    doSomething();
    state = update(state);
}

都可以写成如下的递归函数：

State While(State state) {
    if (needLoop(state)) 
        return While(update(state));
    else return state;
}

这样就可以把任意的循环改写成 λ 演算的形式了。