Y Combinator 实现方案

Question

我对方案函数式编程真的很陌生。我最近在 lambda 演算中遇到了 Y-combinator 函数，像这样 Y ≡ (λy.(λx.y(xx))(λx.y(xx)))。我想在方案中实现它，我搜索了很多但我没有找到与上面给定结构完全匹配的任何实现。我发现的其中一些如下：

(define Y
(lambda (X)
  ((lambda (procedure)
     (X (lambda (arg) ((procedure procedure) arg))))
   (lambda (procedure)
     (X (lambda (arg) ((procedure procedure) arg)))))))

和

(define Y
  (lambda (r)
    ((lambda (f) (f f))
     (lambda (y)
       (r (lambda (x) ((y y) x)))))))

如您所见，它们与此 Y ≡ (λy.(λx.y(xx))(λx.y(xx))) 组合函数的结构不匹配。我怎样才能以完全相同的方式在方案中实现它？

Answer 1

在像 Lazy Racket 这样的惰性语言中，您可以使用普通顺序版本，但不能在任何像 Scheme 这样的应用顺序编程语言中使用。他们只会进入无限循环。

Y 的应用版本通常称为 Z 组合器：

(define Z
  (lambda (f)
    ((lambda (g) (g g))
     (lambda (g)
       (f (lambda args (apply (g g) args)))))))

现在应用此函数时发生的第一件事是 (g g) 并且由于您始终可以用扩展的主体替换整个应用程序，因此函数主体可以重写为：

(define Z
  (lambda (f)
    ((lambda (g)
       (f (lambda args (apply (g g) args))))
     (lambda (g)
       (f (lambda args (apply (g g) args)))))))

我真的没有改变任何东西。只是多了一点代码，功能完全一样。请注意，此版本使用 apply 来支持多参数函数。想象一下阿克曼函数：

(define ackermann
  (lambda (m n)
    (cond
      ((= m 0) (+ n 1))
      ((= n 0) (ackermann (- m 1) 1))
      (else (ackermann (- m 1) (ackermann m (- n 1)))))))

(ackermann 3 6) ; ==> 509

这可以通过 Z 来完成，如下所示：

((Z (lambda (ackermann)
      (lambda (m n)
        (cond
        ((= m 0) (+ n 1))
        ((= n 0) (ackermann (- m 1) 1))
        (else (ackermann (- m 1) (ackermann m (- n 1))))))))
 3
 6) ; ==> 509

请注意，实现完全相同，不同之处在于如何处理对自身的引用。

编辑

所以你问的是评估是如何延迟的。好吧，正常订单版本看起来像这样：

(define Y
  (lambda (f)
    ((lambda (g) (g g))
     (lambda (g) (f (g g))))))

如果你看看这将如何与一个参数一起应用，你会注意到 Y 从来没有 returns 因为在它可以在 (f (g g)) 中应用 f 之前它需要评估 (g g) 依次评估 (f (g g)) 等。为了挽救我们没有立即应用 (g g) 的情况。我们知道 (g g) 成为一个函数，所以我们只给 f 一个函数，当应用它时将生成实际函数并应用它。如果你有一个函数add1，你可以制作一个包装器(lambda (x) (add1 x))，你可以使用它来代替，它会起作用。以同样的方式 (lambda args (apply (g g) args)) 与 (g g) 相同，您可以通过应用替换规则看到这一点。这里的线索是，这有效地停止了每一步的计算，直到它真正投入使用。

Y Combinator 实现方案

Y Combinator implementation Scheme

scheme

lambda-calculus

y-combinator