又是一篇lambda演算介绍:过程与数据结构(一)
λ-calculus
自从了解了lambda演算,我就觉得,每个写代码的人都应该学学它。——沃兹·基硕德
λ演算的详细介绍可以从 Wikipedia 找到。
简单来说,这是一个比图灵机早提出几个月的可计算性模型,表达优美形式简洁反正比图灵机高到不知道哪里去了,但是愚蠢的人类没办法在机器上直接实现它所以只能照着图灵机来造计算机,导致图灵那家伙小人得志真正的大神却退居二线(相对图灵来说的二线)
(为了方便表示,以下将 λV.E
记为 V -> E
)
数据
在原始的 lambda 演算中,没有直接的“数字”概念。
lambda 演算的全部规则仅有两条(其实也可以说是三条),在这种简洁的体系中没有一个容纳原生“数字”概念的空间。
但是神奇的是,仅仅只有两条“运算方法”,却能够构造出整个直觉上的“数字”体系。这种通过“过程”构造的“数字”,我们叫它“Church Numerals”,因为它正是由引入 lambda 演算的那位神人提出的。