Scheme/Racket 中 letrec 的含义

Question

据我了解，let、let*、letrec 和 letrec* 是 Scheme/Racket 中使用的合成糖。

现在，如果我有一个简单的程序：

(let ((x 1)
      (y 2))
     (+ x y))

翻译成：

((lambda (x y) (+ x y)) 1 2)

如果我有：

(let* ((x 1)
      (y 2))
     (+ x y))

翻译成：

((lambda (x) ((lambda (y) (+ x y))) 2) 1)

现在，对于我的第一个问题，我理解 letrec 表达式的含义，它使人们能够在 let 中使用递归，但我不明白它是如何完成的。 letrec 翻译成什么？

例如，什么会

(letrec ((x 1)
      (y 2))
     (+ x y))

被翻译成?

第二个问题与 letrec* 类似 - 但是对于 letrec* 我不明白它与 letrec 有何不同？还有，letrec* 表达式会被翻译成什么？

Answer 1

请参阅论文“修复 Letrec：可靠而高效的实现 Scheme 的递归绑定构造”，作者：Oscar Waddell、Dipanwita Sarkar，以及 R. 肯特·戴布维格。

本文从一个简单的版本开始，然后解释一个更复杂的扩展：

https://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf

Answer 2

由于您的示例没有任何过程，也没有真正的表达式，我想您可以将其实现为：

(let ((x 1) (y 2))
  (+ x y))

但是为了支持表单的意图，一个基本的实现可能会做这样的事情：

(let ((x 'undefined) (y 'undefined))
  (let ((tmpx 1) (tmpy 2))
    (set! x tmpx)
    (set! y tmpy))
  (+ x y))

现在。 letrec 是为了让 lambda 能够通过名称来调用自己。想象一下：

(let ((fib (lambda (n) 
             (if (< n 2) n 
                 (+ (fib (- n 1)) (fib (- n 2)))))))
      (fib 10))

了解这是行不通的以及原因很重要。将其转换为 lambda 调用可以很容易地看到：

((lambda (fib)
   (fib 10))
 (lambda (n) 
   (if (< n 2) n 
       (+ (fib (- n 1)) (fib (- n 2))))))

创建 fib 后，您需要以某种方式计算 lambda。假设我们这样做：

(let ((fib 'undefined))
  (set! fib (lambda (n) 
              (if (< n 2) n 
                  (+ (fib (- n 1)) (fib (- n 2))))))
  (fib 10))

或者，您可以使用使其变得纯净：

(let ((fib (Z (lambda (fib)
                (lambda (n) 
                  (if (< n 2) n 
                      (+ (fib (- n 1)) (fib (- n 2)))))))))  
  (fib 10))

这需要执行更多的工作，但至少你没有改变。要使其与多个相互递归绑定一起工作可能需要做更多的工作，但我相信它是可行的。

只有两种方法可以正确执行此操作。我知道 clojure 有一个 recur 模仿递归但实际上是一个 goto。

对于不从 letrec 绑定中创建闭包的变量，它们作为 let 工作，后来更像 let* 因为 Soegaards 关于 fix 的回答是向后兼容的，有些人已经对其进行了调整.如果您编写兼容的代码，您不应该假设这一点。

Scheme/Racket 中 letrec 的含义

Meaning of letrec in Scheme/Racket

scheme

racket

let

letrec