Scheme中如何使用惰性求值实现Y组合子？

Question

有人知道如何在Scheme中实现Y组合器，特别是使用惰性求值和额外参数吗？据我了解，Scheme的(promise?)(delay)和(force)提供了惰性求值支持。

我理解的带应用的Y组合器如下，但由于默认采用应用序求值，因此在Scheme中不起作用。

((lambda (f)
   ((lambda (x) (f (x x)))
    (lambda (x) (f (x x)))))
 (lambda (r) (r)))

这是一个建议性的解决方案（Z组合器），但它使用另一个带有参数的lambda函数作为解决方案:

;; Z-combinator
(define Z
  (lambda (f)
    ((lambda (g) (f (g g)))
     (lambda (g) (f (lambda args (apply (g g)
                                        args)))))))
;Value: z

((Z (lambda (r)
      (lambda (x)
        (if (< x 2)
            1
            (* x (r (- x 1))))))) 5)
;Value: 120

;; end Z-combinator

解决方案更新

Y组合子的表达式如下：

;; Y-combinator
(define Y
  (lambda (f)
      ((lambda (x) (f (delay (x x))))
       (lambda (x) (f (delay (x x)))))))
;Value: y

;; end Y-combinator

;; Non tail recursive
((Y (lambda (r)
      (lambda (x)
        (if (< x 2)
            1
            (* x ((force r) (- x 1)))))))
   5)
;Value: 120

;; Tail - recursive
((Y (lambda (r)
      (lambda (x acc)
        (if (< x 2)
            acc
            ((force r) (- x 1) (* x acc))))))
   5 1)

;Value: 120

感谢您的指导！

- user9405153

Answer 1

是的，在严格评估下，自应用（xx）会导致无限循环。如果你延迟它，你可以使用y组合子，只要你也在使用它的地方“强制”该延迟对象:

最初的回答：

在严格的评估中，自应用（xx）会导致无限循环。如果你延迟它，你就能够使用y组合子，只需要在使用该延迟对象时进行“强制”即可。

(define (test)
  (((lambda (f)
      ((lambda (x) (f (delay (x x))))
       (lambda (x) (f (delay (x x))))))
    (lambda (r)
      (lambda (x)
        (if (< x 2)
            1
            (* x ((force r) (- x 1)))))))
   5))

在严格模式下制作可变形的Y组合器的正常方法是对自我应用进行ETA扩展，这是另一种延迟它的方式，但不需要显式地应用力。相反，强制是通过函数应用完成的。

"Original Answer"的翻译是"最初的回答"。

- river

---

谢谢！我发布了一个尾递归等效版本，但是这种范例不起作用。非常感谢这里的任何指导。 - user9405153

Answer 2

在Lazy Racket中计算(ack 3 6)的正常顺序Y组合子：

最初的回答

#lang lazy

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

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

Scheme不像Lazy Racket那样是一种惰性语言，因此Y组合子需要有所不同。现在它被称为Z组合子：

最初的回答

#!r6rs
(import (rnrs base))

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

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

使用delay和force并不能真正使其变得更好：

最初的回答：

#!r6rs
(import (rnrs base)
        (rnrs r5rs))

(define DY
  (lambda (f)
    ((lambda (g) (g g))
     (lambda (g) (f (delay (g g)))))))


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

通常情况下，Y和Z允许我们为递归过程命名，但在最后一个递归过程中，我们得到了一个需要解决的承诺，因此我们泄漏了实现细节，使用起来更加困难。通常涉及承诺时，我们希望避免不必要的执行，但是调用应该返回一个承诺。"最初的回答"

- Sylwester

---

谢谢。我尝试了您的最后一个解决方案，使用MIT-Scheme，但我认为它缺少(delay)。它输出：;The object #[compound-procedure 15], passed as an argument to force, is not a promise. - user9405153

@Nick 我在mit-scheme 9.1.1中试过了，返回了预期的 509。由于它是R5RS，您不需要前三行。 - Sylwester