18

我正在通过 SICP 工作，问题 2.6让我陷入了困境。在处理 Church 数字时，将零和 1 编码为满足某些公理的任意函数的概念似乎是有意义的。此外，使用零的定义和 add-1 函数推导出单个数字的直接公式是有意义的。我不明白如何形成加号运算符。

到目前为止，我有这个。

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

(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))

查看lambda calculus的维基百科条目，我发现 plus 的定义是 PLUS := λmnfx.mf (nfx)。使用该定义，我能够制定以下程序。

(define (plus n m)
  (lambda (f) (lambda (x) ((m f) ((n f) x)))))

我不明白的是，如何仅使用先前派生过程提供的信息直接派生该过程。谁能以某种严格的类似证明的形式回答这个问题？直觉上，我想我明白发生了什么，但正如理查德·费曼曾经说过的，“如果我不能建造它，我就无法理解它……”

4

3 回答 3

14

其实很简单。这可能会被视为火焰诱饵，但括号使其更难看到 - 了解发生了什么的更好方法是想象您使用的是 curried 语言，或者只是使用 Scheme 具有多参数功能和拥抱它......这是一个使用 lambdas 和多个参数的解释：

  • 每个数字 N 都被编码为

    (lambda (f x) ...apply (f (f (f ... (f x)))) N times...)

  • 这意味着N的编码实际上是

    (lambda (f x) (f^N x))

    哪里f^N是函数取幂。

  • 一种更简单的说法（假设柯里化）：数字 N 被编码为

    (lambda (f) f^N)

    所以 N 实际上是一个“提高 N 的幂”函数

  • 现在用你的表情（看lambda这里的 s ）：

    ((m f) ((n f) x))

    因为nis 是一个数字的编码，它就是指数，所以这实际上是：

    ((m f) (f^n x))

    和同样的m：

    (f^m (f^n x))

    其余的应该是显而易见的......你有m应用f应用在n应用上的f应用x。

  • 最后，留下一些乐趣——这是另一种定义方式plus：

    (define plus (lambda (m) (lambda (n) ((m add1) n))))

    （好吧，不是很有趣，因为这个可能更明显。）

于 2010-10-12T07:53:34.253 回答
3

（确保您了解高阶函数）。在Alonzo Church的无类型 lambda 演算中，函数是唯一的原始数据类型。没有数字、布尔值、列表或其他任何东西，只有函数。函数只能有 1 个参数，但函数可以接受和/或返回函数——不是这些函数的值，而是函数本身。因此，要表示数字、布尔值、列表和其他类型的数据，您必须想出一种巧妙的方法让匿名函数代表它们。教会数字是表示自然数的方式。无类型 lambda 演算中三个最原始的构造是：

  1. λx.x，一个身份函数，接受一些函数并立即返回它。
  2. λx.x x，自行申请。
  3. λf.λx.f x, 函数应用，接受一个函数和一个参数，并将一个函数应用于一个参数。

您如何将 0、1、2 编码为函数？我们需要以某种方式将数量的概念构建到系统中。我们只有函数，每个函数只能应用于 1 个参数。我们在哪里可以看到类似数量的东西？嘿，我们可以多次将函数应用于参数！一个函数的 3 次重复调用显然有一种量感：f (f (f x)). 所以让我们用 lambda 演算对其进行编码：

  • 0 =λf.λx.x
  • 1 =λf.λx.f x
  • 2 =λf.λx.f (f x)
  • 3 =λf.λx.f (f (f x))

等等。但是你如何从 0 到 1，或从 1 到 2？你将如何编写一个函数，给定一个数字，返回一个加 1 的数字？我们在 Church 数字中看到了该术语始终以f开头λf.λx.和之后的模式，因此我们需要以某种方式进入 of 的主体并将其包装到另一个中。如何在不减少的情况下更改抽象体？好吧，您可以应用一个函数，将主体包装在一个函数中，然后将新主体包装到旧的 lambda 抽象中。但是您不希望参数改变，因此您将抽象应用于同名的值：, 但是，这不是我们需要的。λf.λx.f((λf.λx.f x) f) x → f x((λf.λx.f x) a) b) → a b

add1这就是为什么λn.λf.λx.f ((n f) x)：你应用n到f然后x将表达式减少到身体，然后应用f到那个身体，然后再用 抽象它λf.λx.。练习：也看到它是真的，快速学习β-reduction并将(λn.λf.λx.f ((n f) x)) (λf.λx.f (f x))2 减为 1。

现在了解将主体包装到另一个函数调用背后的直觉，我们如何实现 2 个数字的加法？我们需要一个函数，给定λf.λx.f (f x)(2) 和λf.λx.f (f (f x))(3)，将返回λf.λx.f (f (f (f (f x))))(5)。看 2。如果你可以用 3 的主体替换它x，那是f (f (f x))什么？要获得 3 的主体，很明显，只需将其应用于f然后x。现在将 2 应用于f，然后将其应用于 3 的主体，而不是x。然后再把它包λf.λx.起来：λa.λb.λf.λx.a f (b f x).

结论：要将 2 个数字和加a在一起b，这两个数字都表示为 Church 数字，您想用 的主体替换 xin ，这样+ = 。要做到这一点，请先申请，然后申请。abf (f x)f (f (f x))f (f (f (f (f x))))afb f x

于 2014-12-26T19:29:34.533 回答
2

Eli 的回答在技术上是正确的，但由于在提出这个问题时#apply尚未介绍该程序，我认为作者并不打算让学生了解该问题或诸如柯里化之类的概念来回答这个问题问题。

他们几乎通过建议一个人应用替换方法来引导一个人找到答案，然后从那里人们应该注意到加法的效果是一个数字与另一个数字的组合。组合是练习 1.42 中引入的一个概念；这就是了解附加程序如何在该系统中工作所需的全部内容。

; The effect of procedure #add-1 on `one`, and `two` was the composition of `f` 
; onto `one` and `f` onto `two`.
;
; one   : (λ (f) (λ (x) (f x)))
; two   : (λ (f) (λ (x) (f (f x))))
; three : (λ (f) (λ (x) (f (f (f x)))))
;
; Thus one may surmise from this that an additive procedure in this system would
; work by composing one number onto the other.
;
; From exercise 1.42 you should already have a procedure called #compose.
;
; With a little trial and error (or just plain be able to see it) you get the
; following solution.

(define (adder n m)
  (λ (f)
    (let ((nf (n f))
          (mf (m f)))
      (compose nf mf))))
于 2014-05-12T23:52:10.100 回答