让我们从转换为 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)
做同样的事情。