又是一篇lambda演算介绍：过程与数据结构（一）

λ-calculus

自从了解了lambda演算，我就觉得，每个写代码的人都应该学学它。——沃兹·基硕德

λ演算的详细介绍可以从 Wikipedia 找到。

简单来说，这是一个比图灵机早提出几个月的可计算性模型，表达优美形式简洁反正比图灵机高到不知道哪里去了，但是愚蠢的人类没办法在机器上直接实现它所以只能照着图灵机来造计算机，导致图灵那家伙小人得志真正的大神却退居二线（相对图灵来说的二线）

（为了方便表示，以下将 λV.E 记为 V -> E ）

数据

在原始的 lambda 演算中，没有直接的“数字”概念。

lambda 演算的全部规则仅有两条（其实也可以说是三条），在这种简洁的体系中没有一个容纳原生“数字”概念的空间。

但是神奇的是，仅仅只有两条“运算方法”，却能够构造出整个直觉上的“数字”体系。这种通过“过程”构造的“数字”，我们叫它“Church Numerals”，因为它正是由引入 lambda 演算的那位神人提出的。

1

所谓“道生1”，1可以说是“数字”体系的基础。

想要从“过程”中构造出“1”这个概念，要从“数字”的本质开始推演。

所谓“数字”，在现实中是用以描述“量”的概念。那么什么是量？

桌子上放了苹果。有几个？这是“数量”。

人吃苹果，咬几口？这是“次数”。

寻找一下“数量”和“次数”两个概念的共性，可以发现，“数字”的含义就是某一指称对另一指称产生作用的次数。

“桌子上有一个苹果”中的“一个”，含义是“有苹果”这个指称对“桌子”这个指称生效了一次。

“吃两口苹果”中“两”的含义是“吃”这个指称对“苹果”这个指称生效了两次。

到这一步就可以很容易从 lambda 演算的基本规则中构建出“数字”了。

所谓“1”，就是这样一个过程：它是一个过程，接受两个指称作为参数，并将其中一个指称应用在另一个指称上一次。

写成符号表示便是：ONE = s->z->s(z)

那么，很自然的疑问，“0”怎么表示？

依葫芦画瓢可以写成 ZERO = s->z->z

好了，现在已经有了“0”和“1”，只差一个“+”就可以构建出完整的自然数系统了。

+

想想“+”的含义是什么？把前一个数代表的次数全部“累积”到后一个数上。

更正规一点的说，“加”这个操作接收两个“数字”作为参数，产生另一个“数字”，这个新的“数字”等效于前两个数字的“累积”。

把这句话符号化写出来：PLUS = x->y->(s->z->x(s)(y(s)(z)))

来看看 PLUS 的效果。

PLUS(ONE, ONE)
=> (x->y->(s->z->x(s)(y(s)(z))))(s->z->s(z))(s->z->s(z))
=> (x->y->(s->z->x(s)(y(s)(z))))(n->m->n(m))(p->q->p(q))
=> (s->z->(n->m->n(m))(s)((p->q->p(q))(s)(z)))
=> (s->z->(n->m->n(m))(s)(s(z)))
=> s->z->s(s(z))

对 ONE 和 ONE 进行 PLUS ，得到 s->z->s(s(z)) ——把s应用在z上两次，不正符合“2”的邱奇数定义吗？

邱奇真tm是个天才。