letrec/letrec*比let更好的内部定义或命名let的示例？

Question

Kent Dybvig在用于letrec和letrec*的Scheme编程语言中给出的两个例子是：

(letrec ([sum (lambda (x)
             (if (zero? x)
                 0
                 (+ x (sum (- x 1)))))])
   (sum 5))

和

(letrec* ([sum (lambda (x)
            (if (zero? x)
                    0
                (+ x (sum (- x 1)))))]
         [f (lambda () (cons n n-sum))]
         [n 15]
         [n-sum (sum n)])
  (f))

第一个也可以写成命名let：

(let sum ([x 5]) 
  ((lambda (x)
                 (if (zero? x)
                     0
                     (+ x (sum (- x 1))))) x))  

第二个可以写成带有内部定义的let：

(let ()
  (define sum  (lambda (x)
               (if (zero? x)
               0 
                   (+ x (sum (- x 1))))))
  (define f (lambda () (cons n n-sum)))
  (define n 15)
  (define n-sum (sum n))
  (f))

letrec/letrec*表单看起来并不比命名的let或带有内部定义表单的let更简洁或更清晰。

谁能给我举个例子，其中letrec/letrec*确实改进了代码，或者是必需的，而不是命名let或带有内部定义的let。

Answer 1

是的，可以使用命名let重写第一个示例，但请注意，其中不需要lambda表单：

(let sum ([x 5])
  (if (zero? x)
    0
    (+ x (sum (- x 1)))))

这种转换有点误导人--如果您正在定义一个“循环函数”(广义的不仅仅是尾递归意义上的)并立即在已知的输入上使用它，那么这样做是很好的。但通常，当您看到您给出的示例时，其目的是显示本地函数的定义和使用，因此可以执行此转换，因为它是用于演示的玩具示例。

其次，请注意，命名的let通常是原始表单而不是原始表单--实际上所有实现都使用的实现策略是将表单扩展为letrec。因此，如果您想要理解命名let，那么理解letrec仍然是一个好主意。(这是一个基本特性:能够通过递归作用域进行自我引用。)

最后，您给出的带有内部定义的示例类似于命名let：它是一种语法糖，可以扩展为letrec (可以是适当的letrec，也可以是带有R5RS的letrec*，并且必须是R6RS中的letrec* )。因此，为了理解它是如何工作的，您需要了解letrec。还要注意，一些使用严格letrec实现也会对您的第二个示例感到厌恶，并抱怨sum未定义。正是这种语法建议是R6RS中采用的letrec*语义的主要论点的背后:许多人喜欢使用内部定义，但是存在一个问题，即顶层定义允许使用以前的定义，但是内部定义以一种意想不到的方式不太方便。在letrec*中，内部定义的工作方式类似于顶层定义。(更准确地说，它们的工作方式类似于顶层禁止重新定义，这意味着它们实际上类似于模块顶层定义。)

(另请注意，(a) Chez和Chez都扩展了内部主体，以允许混合定义和表达式，这意味着扩展同样简单。)

Answer 2

我同意Eli的回答；命名let和内部define都是用letrec定义的。

不过，我将在此基础上添加一些经验和数字方面的数据。我在一家使用Scheme的公司工作。我们有981个Scheme代码文件，总计206,878行(包括注释、空行等等)。这是由一个8-16人的团队在大约8年的时间里编写的。

那么，在这个代码库中有多少个letrec的用法呢? 16.这与let和let*的大约7,000个用法相比(估计是因为我不会费心改进我使用的regexp )。而且看起来所有的letrec用法都是由同一个人写的。

因此，我不会对您发现letrec没有太多实际用途感到惊讶。

Answer 3

从肯特的一些学生那里，我学到了以下内容:根据let，使用宏扩展来实现letrec。它将letrec扩展为在内部使用set!的let。因此，您的第一个示例将扩展为：

(let
  ([sum (void)])
  (set! sum (lambda (x) (if (zero? x) 0 (+ x (sum (- x 1))))))
  (sum 5))

第二，类似的(请注意，嵌套的lets是let*的结果-而且，这可能不是完全正确的扩展，但这是我最好的猜测)：

(let
  ([sum (void)] 
  (set! sum (lambda (x) (if (zero? x) 0 (+ x (sum (- x 1))))))
  (let
    [f (void)] 
    (set! f (lambda () (cons n n-sum)))
    (let 
      [n (void)]
      (set! n 15)
      (let
        [n-sum (void)])
        (set! n-sum (sum n))
        (f))

我不是600%确定命名的let如何扩展，但Eli建议它将在letrec本身方面实现(这是有意义的，应该是非常明显的)。因此，您的命名let将从命名let移动到letrec，再移动到未命名let。而且你对第二个的重写看起来几乎和它的扩展一模一样。

如果您正在解释它并寻求良好的性能，我会倾向于letrec，因为它是一个较短的宏展开步骤。此外，let被转换为一个λ，因此您在第二个示例中使用的是defines，而不是set!s (可能更重)。

当然，如果你正在编译，它可能都会在编译器中掉出来，所以只要使用你认为更好的(我偏爱letrec，因为let循环让我想起命令式编程，但是ymmv)。也就是说，这应该取决于你，在风格上(因为它们或多或少是相同的)。

也就是说，让我提供一个你可能会觉得有价值的例子：

(letrec
 ([even? (lambda (n) (if (zero? n) #t (odd? (- n 1))))]
  [odd? (lambda (n) (if (zero? n) #f (even? (- n 1))))])
  (even? 88))   

使用内部define样式将产生以下结果：

(let ()
  (define even? (lambda (n) (if (zero? n) #t (odd? (- n 1)))))
  (define odd? (lambda (n) (if (zero? n) #f (even? (- n 1)))))
  (even? 88))

所以这里的letrec代码实际上更短。而且，老实说，如果您正在做类似后者的事情，为什么不满足于begin呢

(begin
  (define even? (lambda (n) (if (zero? n) #t (odd? (- n 1)))))
  (define odd? (lambda (n) (if (zero? n) #f (even? (- n 1)))))
  (even? 88))

我怀疑begin在更大程度上是内置的，因此不会像let那样进行宏扩展。最后，在之前的Lisp栈溢出中提出了a similar issue，这一点与此大同小异。