Exercise 2.6 · 习题

Exercise 2.6: In case representing pairs as
procedures wasn’t mind-boggling enough, consider that, in a language that can
manipulate procedures, we can get by without numbers (at least insofar as
nonnegative integers are concerned) by implementing 0 and the operation of
adding 1 as

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))

This representation is known as
Church numerals, after its inventor,
Alonzo Church, the logician who invented the λ-calculus.

Define one and two directly (not in terms of zero and

add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give

a direct definition of the addition procedure + (not in terms of

repeated application of add-1).

练习 2.6：如果说用过程表示序对还不够令人震惊，那么考虑这样一个事实：在一个可以操纵过程的语言中，我们可以完全绕过数字（至少就非负整数而言），将 0 和加 1 运算实现为

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))

这种表示被称为邱奇数 (Church numerals)，以其发明者、λ演算的创始人、逻辑学家 Alonzo Church 命名。

直接定义 one 和 two（而非用 zero 和 add-1 来定义）。（提示：用代换法求值 (add-1 zero)。）给出加法过程 + 的直接定义（而非通过反复调用 add-1 来实现）。