2

这是Racket 中的 Y 组合器：

#lang lazy

(define Y (λ(f)((λ(x)(f (x x)))(λ(x)(f (x x))))))

(define Fact
  (Y (λ(fact) (λ(n) (if (zero? n) 1 (* n (fact (- n 1))))))))
(define Fib
  (Y (λ(fib) (λ(n) (if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2))))))))

这是Scheme 中的 Y 组合器：

(define Y
  (lambda (f)
    ((lambda (x) (x x))
     (lambda (g)
       (f (lambda args (apply (g g) args)))))))

(define fac
  (Y
    (lambda (f)
      (lambda (x)
        (if (< x 2)
            1
            (* x (f (- x 1))))))))

(define fib
  (Y
    (lambda (f)
      (lambda (x)
        (if (< x 2)
            x
            (+ (f (- x 1)) (f (- x 2))))))))

(display (fac 6))
(newline)

(display (fib 6))
(newline)

我的问题是：为什么 Scheme 需要该apply功能而 Racket 不需要？

4

2 回答 2

11

在大多数情况下，Racket 非常接近普通的 Scheme，在这个例子中，它们是相同的。但是两个版本之间的真正区别在于需要一个延迟包装器，这是在严格的语言（Scheme 和 Racket）中需要的，而不是在惰性语言（Lazy Racket，另一种语言）中需要的。

这个包装器放在(x x)or周围(g g)——我们知道的是，评估它会让你进入一个无限循环，而且我们也知道它将是结果（递归）函数。因为它是一个函数，我们可以用lambda: 而不是(x x)use来延迟它的求值(lambda (a) ((x x) a))。这很好用，但它有另一个假设——被包装的函数接受一个参数。我们也可以用两个参数的函数包装它：(lambda (a b) ((x x) a b))但这在其他情况下也不起作用。解决方案是使用休息参数 ( args) 并使用apply，因此使包装器接受任意数量的参数并将它们传递给递归函数。严格来说，它并不总是需要，如果您希望能够产生任何数量的递归函数，它是“仅”需要的。

另一方面，您有 Lazy Racket 代码，正如我上面所说，它是一种不同的语言——一种具有按需调用语义的语言。由于这种语言是惰性的，因此无需包装无限循环(x x)表达式，它按原样使用。而且由于不需要包装器，因此不需要处理参数的数量，因此不需要apply. 事实上，惰性版本甚至不需要假设您正在生成函数值——它可以生成任何值。例如，这个：

(Y (lambda (ones) (cons 1 ones)))

工作正常并返回一个无限的1s 列表。要查看此内容，请尝试

(!! (take 20 (Y (lambda (ones) (cons 1 ones)))))

（请注意，!!需要递归“强制”结果值，因为 Lazy Racket 默认情况下不会递归评估。另外，请注意使用take-- 没有它，Racket 将尝试创建该无限列表，这将不会得到任何地方。）

于 2014-09-30T11:33:41.960 回答
0

方案不需要apply功能。您使用 apply 来接受多个参数。

在阶乘情况下，这是我不需要的实现apply

;;2013/11/29

(define (Fact-maker f)
  (lambda (n)
    (cond ((= n 0) 1)
          (else (* n (f (- n 1)))))))

(define (fib-maker f)
  (lambda (n)
    (cond ((or (= n 0) (= n 1)) 1)
          (else
            (+ (f (- n 1))
               (f (- n 2)))))))
(define (Y F)
  ((lambda (procedure)
     (F (lambda (x) ((procedure procedure) x))))
   (lambda (procedure)
     (F (lambda (x) ((procedure procedure) x))))))
于 2014-10-04T13:35:37.023 回答