题

我正在通过SICP和 问题2.6 让我陷入困境。在处理教会数字时，编码零的概念和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)))))

浏览Wikipedia条目 lambda演算, ，我发现Plus的定义是Plus：=λmnfx.mf（nfx）。使用该定义，我能够制定以下过程。

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

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

有帮助吗？

解决方案

实际上很简单。这可能会被视为火焰饵，但是帕伦斯使得很难看到 - 看到发生的事情的更好方法是想象您是一种咖喱语言，或者只是使用方案具有多重题目功能和拥抱那个...这是一个使用lambdas和多个参数的解释，在方便的地方：

  • 每个数字n都编码为

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

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

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

    在哪里 f^N 是功能指数。

  • 说这句话的一种简单方法（假设咖喱）：编码数字为

    (lambda (f) f^N)

    所以n实际上是一个 “提高n的力量” 功能

  • 现在以您的表情（看着 lambda在这里）：

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

    自从 n IS是一个数字的编码，这是该指数，因此实际上是：

    ((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))))

    （嗯，这不太有趣，因为这个可能更明显。）

其他提示

（确保您了解 高阶功能). 在 阿隆佐教堂' 未型的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 cyculus编码它：

  • 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的数字？我们看到教会数字中的模式总是从 λf.λx. 在您重复使用有限的应用之后 F, ，所以我们需要以某种方式进入 λf.λx. 并将其包裹成另一个 f. 。您如何在不减少的情况下更改抽象的身体？好吧，您可以应用功能，将身体包裹在功能中，然后将新身体包裹在旧的Lambda抽象中。但是您不希望参数更改，因此您将抽象应用于同名的值： ((λ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.. 锻炼： 也看到它是真的，快速学习 β减少 并减少 (λ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。如果你可以 代替 它的 x 有3个身体，即 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 一起，两者都表示为教会数字，您想 代替 x 在 a 与身体 b, ， 以便 f (f x) + f (f (f x)) = f (f (f (f (f x)))). 。要实现这一目标，请应用 a 至 f, ，然后 b f x.

埃利的答案在技术上是正确的，但是由于问这个问题 #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))))
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top