Question

如果你想从头开始制作苹果派，必须先创造整个宇宙。

——卡尔 · 萨根

本书中，我们一直在试图构建计算模型来理解计算。到目前为止，我们设计了想象中带有不同约束的简单机器，并看到不同的约束会产生出拥有不同计算能力的系统，以此对计算进行了建模。

第 5 章的图灵机很有意思，因为它们不依赖复杂的特性就能实现复杂的行为。只要有一条纸带、一个读写头以及一个固定的规则集合，图灵机就足以模拟拥有更好存储能力、支持非确定性执行或者任何其他奇妙特性的机器行为。这告诉我们，成熟的计算不需要机器具备大量的潜在复杂性，只需要其具备存储、检索以及使用数据进行简单决策的能力。

计算模型不一定非要看起来像机器，它们可以看起来像编程语言。第2 章的Simple 编程语言当然可以执行计算，但它的执行过程没有图灵机那么优雅。它已经有了大量语法（数字、布尔值、二进制表达式、变量、赋值、序列、条件、循环），而且我们甚至还没有开始为其增加特性，以使其适合写真正的程序：字符串、数据结构、过程调用，等等。

把Simple 转换成真正有用的编程语言将会是一项艰苦的工作，最终的设计会包含大量的细节，不会对揭示计算的本质帮助太多。从零开始创建某个最小的东西——编程语言世界的一台图灵机，这样我们就可以看到对于计算来说，哪些特性是本质的，哪些特性是偶然的噪音。

本章，我们将研究一种叫作无类型 lambda 演算（untyped lambda calculus）的极小编程语言。首先，我们将用尽可能少的语言特性写（用Ruby）一些接近lambda 演算的程序。这将仍然仅仅是在用Ruby 编程，但施加虚构的约束之后，我们便能很轻松地探索一个受限的语义，而不需要学习一门新语言。然后，我们了解到这些非常有限的特性集合能做什么以后，就将利用这些特性把它们实现为一种语言（使用它自己的解析器、抽象语法和操作语义）——使用我们在之前章节中学到的技术。