1

根据RosettaCode，Scheme 中的 Y Combinator 实现为

(define Y
  (λ (h)
    ((λ (x) (x x))
     (λ (g)
       (h (λ args (apply (g g) args)))))))

当然，传统的 Y Combinator 是λf.(λx.f(xx))(λx.f(xx))

那么，我的问题是 abouth和args，它没有出现在数学定义中，以及 about apply，它似乎应该在 Combinator 的两半中，或者都不在。

有人可以帮我理解这里发生了什么吗？

4

1 回答 1

1

让我们从转换为 Scheme 的 lambda 演算版本开始：

(λ (f) 
 ((λ (x) (f (x x)))
  (λ (x) (f (x x)))))

我想简化这一点，因为我看到(λ (x) (f x x))重复了两次。您可以将那里的开头替换为：

(λ (f) 
 ((λ (b) (b b))
  (λ (x) (f (x x)))))

Scheme 是一种急切的语言，因此它会陷入无限循环。为了避免我们做一个代理。假设你有两个数字，你可以在不改变结果的情况下+替换它。(λ (a b) (+ a b))让我们用代码做到这一点：

(λ (f) 
 ((λ (b) (b b))
  (λ (x) (f (λ (p) ((x x) p))))))

实际上这有它自己的名字。它被称为 Z 组合子。(x x)仅在应用提供的代理时才f应用。耽误了一步。它可能看起来很奇怪，但我知道它变成了一个函数，所以这与我上面的替换(x x)完全相同。+

在 Lambda 演算中，所有函数都接受一个参数。如果您看到f x y它实际上与 Scheme 中的相同((f x) y)。如果您希望它与所有元素的功能一起使用，您的替换需要反映这一点。在 Scheme 中，我们有休息参数并apply可以做到这一点。

(λ (f) 
 ((λ (b) (b b))
  (λ (x) (f (λ p (apply (x x) p))))))

如果您只打算使用 lambda 演算中的一个元函数，则不需要这样做。

请注意，在您的代码中，您使用h而不是f. 你怎么称呼变量并不重要。这是具有不同名称的相同代码。所以这是一样的：

(λ (rec-fun) 
 ((λ (yfun) (yfun yfun))
  (λ (self) (rec-fun (λ args (apply (self self) args))))))

不用说(yfun yfun)，(self self)做同样的事情。

于 2017-12-17T20:08:59.307 回答