1

在 SICP 中,(ex 2.6)以下功能被描述为“无数字生活”的方式。我正在努力理解这一点。作为起点,如何调用这些函数?我真的可以以某种方式应用它们,输出为 1 吗?(或任何其他数字?)

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

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

我最初的尝试没有成功:

Welcome to DrScheme, version 4.1.5 [3m].
Language: Simply Scheme; memory limit: 128 megabytes.
> (add-1 (zero))
. . procedure zero: expects 1 argument, given 0
> (add-1 zero)
#<procedure>
> (add-1 1)
#<procedure>
> ((add-1 1))
. . #<procedure>: expects 1 argument, given 0
> 
4

3 回答 3

9

这些表示数字的函数称为Church 数字(如 SICP 所述)。它们的存在意味着您可以定义一个计算系统(例如 lambda 演算),而无需将数字作为一等对象——您可以将函数用作原始对象。这个事实主要是理论上的兴趣;教堂数字不是实际计算的好选择。

您可以通过将它们与其他对象一起应用作为参数来查看您对 Church 数字的定义的正确性。当您将表示 n 的 Church 数字应用于函数 f 时,您会得到另一个函数,该函数将 f 应用于其参数 n 次,例如,对于 n=3,f(f(f(x)))。

> (define (double x) (* 2 x))
> (zero double)
#<procedure>
> ((zero double) 1)
1
> ((zero double) 100)
100
> (define one (add-1 zero))
> ((one double) 1)
2
> ((one double) 100)
200
> (define (cons-a x) (cons 'a x))
> ((zero cons-a) '())
()
> (((add-1 one) cons-a) '(1 2 3))
(a a 1 2 3)
于 2009-05-05T20:53:03.157 回答
3

这是原始的lambda 演算,它不产生数字,它完全用函数替换了数字类型。

所以,你有一个“零”函数,如果你调用add-1它,你不会得到 1,你会得到另一个代表 1 的函数。关键是产生的函数符合基本的算术公理,所以它们是等价于自然数

于 2009-05-05T20:52:33.000 回答
0
(define (as-primitive-num church-num)
    (define (inc a) (+ a 1))
    ((church-num inc) 0))

;testing:
(define one (add-1 zero))
(define two (add-1 one))

(display (as-primitive-num one)) (newline)
(display (as-primitive-num two)) (newline)

和输出:

    1
    2
于 2012-09-06T10:32:43.580 回答