问

为什么Scheme需要应用于Y-combinator实现,但是Racket没有？

青春脸001 发布于 2022-12-19 06:07

这是Racket中的Y-combinator:

#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-combinator:

(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没有？

1 个回答

对于大多数用途,球拍非常接近普通方案,对于这个例子,它们是相同的.但两个版本之间的真正区别在于需要一种延迟包装器,这种包装器需要严格的语言(Scheme和Racket),而不是懒惰的(Lazy Racket,一种不同的语言).

那个包装器被放在(x x)或者(g g)- 我们对这个东西的了解是评估它会让你进入一个无限循环,我们也知道它将是结果(递归)函数.因为它是一个函数,我们可以用lambda:而不是(x x)使用来延迟它的评估(lambda (a) ((x x) a)).这工作正常,但它有另一个假设 - 包装函数只需一个参数.我们也可以用两个参数的函数来包装它:(lambda (a b) ((x x) a b))但是在其他情况下也不行.解决方案是使用rest参数(args)并使用apply,因此使包装器接受任意数量的参数并将它们传递给递归函数.严格地说,它并不总是必需的,如果你想要能够产生任何arity的递归函数,它是"唯一的".

另一方面,你有Lazy Racket代码,正如我上面所说,它是一种不同的语言 - 一种是需要语义调用的语言.由于这种语言是懒惰的,所以不需要包装无限循环(x x)表达式,它是按原样使用的.并且由于不需要包装器,因此不需要处理参数的数量,因此不需要apply.实际上,懒惰版本甚至不需要假设您正在生成函数值 - 它可以生成任何值.例如,这个:
```
(Y (lambda (ones) (cons 1 ones)))
```
工作正常,返回无限的1s 列表.要看到这一点,试试吧
```
(!! (take 20 (Y (lambda (ones) (cons 1 ones)))))
```
(注意,!!需要递归地"强制"结果值,因为Lazy Racket默认情况下不会递归计算.另外,请注意使用take- 如果没有它,Racket将尝试创建无限列表,这将无法获得任何地方.)
2022-12-19 06:44 回答

优美rosner_704

撰写答案

今天，你开发时遇到什么问题呢？

立即提问

热门标签