1929年，数学家阿隆佐·丘奇（Alonzo Church）发明了一套符号系统，当时还没有计算机，没人想到这会成为所有编程语言的底层骨架。这套系统叫λ演算，后来证明与图灵机完全等价——也就是说，它能计算任何可计算的问题。
λ演算只有三种表达式：变量引用、匿名函数、函数调用。匿名函数写成(λ v . e)，意思是接受参数v，返回表达式e的值。函数调用就是把两个表达式并排放在一起，(f e)表示把e传给f。
打开网易新闻 查看精彩图片
看起来极简，甚至让人怀疑：没有循环、没有条件判断、没有数字和布尔值，这怎么算通用语言？秘密藏在两个技巧里：丘奇编码（Church encoding）和Y组合子（Y combinator）。前者能把任何数据类型都编码成函数，后者能实现递归。丘奇的学生艾伦·图灵后来定义了图灵机，两人体系被证明完全等价。
打开网易新闻 查看精彩图片
一个有趣的例子是Omega程序：((λ f . (f f)) (λ f . (f f)))。这行代码会无限执行下去，永不终止——用如此简洁的语法就能表达无限循环，正是λ演算的力量所在。
今天，λ演算活在Haskell、Scheme、ML的核心，也藏在JavaScript、Python、Ruby甚至Java的底层。如果你写过箭头函数或高阶函数，其实已经摸到了它的边缘。
打开网易新闻 查看精彩图片
最惊人的是，实现一个λ演算解释器只需要7行代码，3分钟就能写完。这种极简与强大的反差，或许正是它穿越近百年仍然重要的原因。
热门跟贴