Scheme/Racket中letrec的含义

Question

据我所知，以下内容：let、let*、letrec 和 letrec* 是Scheme/Racket中使用的合成糖。现在，如果我有一个简单的程序：

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

It is translated into:

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

如果我有：

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

It is translated into:

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

现在，我有一个问题，我理解了letrec表达式的含义，允许在let语句中使用递归，但我不明白具体是如何实现的。 letrec被翻译成什么？

例如，下面的代码将会……

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

需要翻译成什么语言？

第二个问题与letrec*类似 - 但是对于letrec*，我不明白它与letrec有什么区别？而且，letrec*表达式将被翻译成什么？

- user4285147

---

“letrec” 没有被翻译成其他任何东西。“letrec”是该语言的基本形式。（顺带一提，在 Racket 中，“let” 也是 Racket 的原始形式，而不是在“lambda”之上的宏，但这更多地是主观的设计选择。） - Alexis King

是否翻译成另一种语言是一回事。但是是否可以有一个等效的表达式来表示letrec，就像我在示例中指定let和let*的等效表达式一样？ - user4285147

请参考这个和这个链接，它们都是我回答的关于编程的问题。最后一个链接实际上有两种可能的扩展，分别是 letrec 和 letrec*。（所以，这可能是一个重复的问题...） - Will Ness

Answer 1

请看Oscar Waddell、Dipanwita Sarkar和R. Kent Dybvig的论文“修复Letrec：Scheme递归绑定结构的忠实而高效的实现”。该论文从简单版本开始，然后解释了一个更复杂的扩展。论文链接为：https://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf。请注意，保留了HTML标签。

- soegaard

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

或者，您可以使用Z组合子使其变成纯函数：

(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的答案向后兼容并且已被一些人采用。但如果编写兼容的代码，不应该被诱惑去假设这一点。

- Sylwester