时间戳

首页 > 解决方案 > Scheme中的Y-combinator，使用惰性求值？

lambda - Scheme中的Y-combinator，使用惰性求值？

问题描述

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

我的理解是带有应用程序的 Y-combinator 如下，但是由于应用程序的顺序评估，默认情况下在 Scheme 中不起作用。

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

这是一个建议的解决方案（Z-combinator），但是它使用另一个带有参数的 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

感谢您的指导！

标签： lambdaschemey-combinator

解决方案

是的，通过严格评估，自我应用程序 (xx) 会导致发生无限循环。如果您延迟此操作，您可以使用 y-combinator，只要您还在其使用站点“强制”该延迟对象：

(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-combinator 进行变体的正常方法是 eta-expand 自我应用，这是另一种延迟它的方法，但不需要显式施加力。相反，强制是由功能应用程序完成的。

推荐阅读