8

据我了解,以下内容:let、、let*和是 Scheme/Racketletrecletrec*使用的合成糖。

现在,如果我有一个简单的程序:

(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*表达式会被翻译成什么?

4

2 回答 2

5

请参阅 Oscar Waddell、Dipanwita Sarkar 和 R. Kent Dybvig 的论文“Fixing Letrec: A Faithful Yet Efficient Implementation of Scheme's Recursive Binding Construct”。

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

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

于 2018-05-31T15:55:35.240 回答
4

由于您的示例没有任何程序,也没有真正的表达式,我想说您可以将其实现为:

(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是为了让 lambdas 能够通过名称来称呼自己。所以想象一下:

(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模仿递归但实际上是 aa goto。

对于不会从letrec绑定中生成闭包的变量,它们的工作方式let和后来更像是let*因为 Soegaards 关于修复的回答是向后兼容的,并且有些人已经对其进行了调整。如果您编写兼容的代码,但您不应该试图假设这一点。

于 2018-06-01T22:10:06.250 回答