了解 Scheme 中 Y Combinator 中的额外参数

Question

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

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

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

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

谁能帮我理解这是怎么回事？

Answer 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) 相同。如果您希望它与所有 arities 的功能一起使用，您的替换需要反映这一点。在 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) 做同样的事情。

Understanding extra arguments in the Y Combinator in Scheme