计划：“`letrec`”和“`letcc`”对效率至关重要吗？

Question

我正在阅读弗里德曼和费莱森的经验丰富的阴谋家，但我对他们的一些最佳做法感到有点不安。特别是，提交人建议：

applications;

• using

• 使用letrec删除不更改递归letrec letrec以隐藏的参数，并保护letrec letcc突然、及时地返回值。

让我们来看看这些规则的一些后果。例如，考虑计算列表列表的交集的代码：

#lang scheme

(define intersectall
  (lambda (lset)
    (let/cc hop
      (letrec
          [[A (lambda (lset)
                (cond [(null? (car lset)) (hop '())]
                      [(null? (cdr lset)) (car lset)]
                      [else (I (car lset) (A (cdr lset)))]))]
           [I (lambda (s1 s2)
                (letrec
                    [[J (lambda (s1)
                          (cond [(null? s1) '()]
                                [(M? (car s1) s2) (cons (car s1) (J (cdr s1)))]
                                [else (J (cdr s1))]))]
                     [M? (lambda (el s)
                           (letrec
                               [[N? (lambda (s)
                                      (cond [(null? s) #f]
                                            [else (or (eq? (car s) el) (N? (cdr s)))]))]]
                             (N? s)))]]
                  (cond [(null? s2) (hop '())]
                        [else (J s1)])))]]
        (cond [(null? lset) '()]
              [else (A lset)])))))

这个例子出现在第13章(不完全是这样:我粘合了上一段中单独定义的成员资格测试代码)。

我认为下面的替代实现(对letrec和letcc的使用非常有限)更加可读性更强，理解起来也更简单：

(define intersectall-naive
  (lambda (lset)
    (letrec
        [[IA (lambda (lset)
              (cond [(null? (car lset)) '()]
                    [(null? (cdr lset)) (car lset)]
                    [else (intersect (car lset) (IA (cdr lset)))]))]
         [intersect (lambda (s1 s2)
                      (cond [(null? s1) '()]
                            [(M? (car s1) s2) (cons (car s1) (intersect (cdr s1) s2))]
                            [else (intersect (cdr s1) s2)]))]
         [M? (lambda (el s)
               (cond [(null? s) #f]
                     [else (or (eq? (car s) el) (M? el (cdr s)))]))]]
    (cond [(null? lset) '()]
          [else (IA lset)]))))

我是个新手，我的背景不是计算机科学，但我突然想到，对于一个简单的列表交叉问题，我们必须得到如此复杂的代码。这让我想知道人们是如何管理现实世界应用程序的复杂性的。经验丰富的阴谋家是否每天都在深深地嵌套letcc和letrec表达式？

这就是询问stackexchange的动机。

我的问题是:出于教育的考虑，弗里德曼和费莱森是否过于复杂了这个例子?还是出于性能原因，我是否应该习惯于充斥着letcc和letrec的方案代码？对于大列表，我的天真代码会不会慢到实际呢？

Answer 1

我不是Scheme实现方面的专家，但我对这里发生了什么有一些想法。作者通过他们的let/cc所拥有的一个优势是，当明确了整个结果时，就会提前终止。假设有人评估

(intersectall-naive (list big-list
                          huge-list
                          enormous-list
                          gigantic-list
                          '()))

您的IA将将此转换为

(intersect big-list
           (intersect huge-list
                      (intersect enormous-list
                                 (intersect gigantic-list
                                            '()))))

这是很合理的。将首先计算最内部的交集，因为gigantic-list不是零，它将遍历整个gigantic-list，以检查该项是否是'()的成员。当然没有，所以这会导致'()，但是您必须遍历整个输入才能找到这个结果。这个过程将在每一个嵌套的intersect调用中重复:您的内部过程无法发出“它没有希望，请放弃”的信号，因为它们只通过返回值进行通信。

当然，您可以在不使用let/cc的情况下解决这个问题，方法是在继续之前检查每个intersect调用的空值。但是(a)这种检查只发生在一个方向而不是两个方向是相当好的，而且(b)并不是所有的问题都是那么容易解决的:也许你想返回一些你不能轻易发出信号的东西，以便尽早退出。let/cc方法是通用的，允许在任何上下文中提前退出。

至于使用letrec来避免重复递归调用的常量参数:同样，我不是Scheme实现方面的专家，但在Haskell中，我已经听说过这样的指导:如果只结束一个参数，这是一次清洗，对于2+参数，它可以提高性能。考虑到闭包是如何存储的，这对我来说是有意义的。但是，我怀疑它在任何意义上都是“关键的”，除非您有大量的参数，或者您的递归函数所做的工作很少:参数处理将是完成工作的一小部分。我不会惊讶地发现，作者认为这提高了清晰度，而不是出于性能原因。如果我看到

(define (f a x y z)
  (define (g n p q r) ...)
  (g (g (g (g a x y z) x y z) x y z) x y z))

如果我看到了，我就不会那么高兴了。

(define (f a x y z)
  (define (g n) ...)
  (g (g (g (g a)))))

因为我必须发现，实际上p只是x等的另一个名称，所以检查是否在每种情况下都使用了相同的x、y和z，并确认这是故意的。在后一种情况下，很明显，x始终具有这一意义，因为没有其他变量保存该值。当然，这是一个简化的示例，不管怎么看g的四个文字应用程序，我都不会感到兴奋，但是对于递归函数来说，同样的想法是成立的。