2

我正在阅读Friedman 和 Felleisen的 The Seasoned Schemer，但我对他们的一些最佳实践感到有些不安。作者特别推荐：

  • 用于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 的动机。

我的问题是：Friedman 和 Felleisen 是否为了教育而过度复杂化了这个示例，还是出于性能原因我应该习惯于使用充满letccs 和s 的方案代码？letrec对于大型列表，我的幼稚代码是否会变得不切实际？

4

1 回答 1

1

I'm not an expert on Scheme implementations, but I have some ideas about what's going on here. One advantage the authors have via their let/cc that you don't have is early termination when it's clear what the entire result will be. Suppose someone evaluates

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

Your IA will transform this to

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

which is reasonable enough. The innermost intersection will be computed first, and since gigantic-list is not nil, it will traverse the entirety of gigantic-list, for each item checking whether that item is a member of '(). None are, of course, so this results in '(), but you did have to walk the entire input to find that out. This process will repeat at each nested intersect call: your inner procedures have no way to signal "It's hopeless, just give up", because they communicate only by their return value.

Of course you can solve this without let/cc, by checking the return value of each intersect call for nullness before continuing. But (a) it is rather pretty to have this check only occur in one direction instead of both, and (b) not all problems will be so amenable: maybe you want to return something where you can't signal so easily that early exit is desired. The let/cc approach is general, and allows early-exit in any context.

As for using letrec to avoid repetition of constant arguments to recursive calls: again, I am not an expert on Scheme implementations, but in Haskell I have heard the guidance that if you are closing over only 1 parameter it's a wash, and for 2+ parameters it improves performance. This makes sense to me given how closures are stored. But I doubt it is "critical" in any sense unless you have a large number of arguments or your recursive functions do very little work: argument handling will be a small portion of the work done. I would not be surprised to find that the authors think this improves clarity, rather than doing it for performance reasons. If I see

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

I will be rather less happy than if I see

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

because I have to discover that actually p is just another name for x, etc., check that the same x, y, and z are used in each case, and confirm that this is on purpose. In the latter case, it is obvious that x continues to have that meaning throughout, because there is no other variable holding that value. Of course this is a simplified example and I would not be thrilled to see four literal applications of g regardless, but the same idea holds for recursive functions.

于 2020-10-13T23:36:31.270 回答