什么是 SICP 3.57 的真正答案？

Question

SICP练习3.57：使用基于“add-streams”程序的“fibs”定义计算第n个斐波那契数时，执行了多少次加法？证明如果我们仅将"(delay ⟨exp⟩)"实现为"(lambda () ⟨exp⟩)"而不使用3.5.1中描述的"memo-proc"过程的优化，则加法数量将呈指数增长。

许多解决方案在线上。大多声称非优化的“memo-proc”序列版本的“fib”序列与计算非存储器的常规“fib”函数相同。跟踪非优化的“memo-proc”版本的加法时，我看到了另一个故事。

设A(n)为执行（stream-ref fibs n）的加法次数。

- A(0)=0 - A(1)=0 - A(2)=1 - A(3)=3 - A(4)=7 - A(5)=14 - A(6)=26

使用替换和非优化（未存储器化的流）的函数定义，我可以看到这些加法是什么，为什么会发生但我很难想出一个好的方程来回答问题，实际上它是呈指数级增长的。

例如，对于A(4)，跟踪的添加如下:

- 1+0 - 1+0 - 1+1 - 1+0 - 1+1 - 1+0 - 2+1

以下是一些伪代码，用于显示(stream-ref fibs 4)的替换，其中“。”表示中缀流-cons，"{e}"代表承诺执行"e":

(cddddr fibs)
(cddr (add-streams (cdr fibs) fibs))
(cddr (stream-map + (cdr fibs) fibs)))
(cddr ((+ 1 0) . {stream-map + (cddr fibs) (cdr fibs)}))
(cdr (stream-map + (cddr fibs) (cdr fibs)))
(cdr (stream-map + ((+ 1 0) . {stream-map + (cddr fibs (cdr fibs)}) (cdr fibs))
(cdr (+ 1 1) . {stream-map + (stream-map + (cddr fibs) (cdr fibs)) (cddr fibs)})
(stream-map + (stream-map + (cddr fibs) (cdr fibs)) (cddr fibs))
(stream-map + (stream-map + ((+ 1 0) . {stream-map + (cddr fibs) (cdr fibs)}) (cdr fibs)) (cddr fibs)
(stream-map + (stream-map + ((+ 1 0) . {stream-map + (cddr fibs) (cdr fibs)}) (1 . {stream-map + (cdr fibs) fibs)})) (cddr fibs))
(stream-map + ((+ 1 1) . {stream-map + (stream-map + (cddr fibs) (cdr fibs)) (stream-map + (cdr fibs) fibs)}) ((+ 1 0) . {stream-map + (cddr fibs) (cdr fibs)})
(+ 2 1) . {stream-map + (stream-map + (stream-map + (cddr fibs) (cdr fibs)) (stream-map + (cdr fibs) fibs))) (stream-map + (cddr fibs) (cdr fibs))}

以下是实际的 Racket 代码：

#lang racket
(define-syntax-rule (delay f) (lambda () f))
(define (force f) (f))

(define stream-null? null?)
(define the-empty-stream '())

(define-syntax-rule (cons-stream a b)
  (cons a (delay b)))
(define stream-car car)
(define (stream-cdr stream) (force (cdr stream)))

(define (add-streams s1 s2)
  (define (add x y)
    (begin
      (display "Adding ")
      (display x)
      (display " + ")
      (display y)
      (newline)
      (+ x y)))
  (stream-map add s1 s2))

(define (stream-map proc . argstreams)
  (if (stream-null? (car argstreams))
      the-empty-stream
      (cons-stream
       (apply proc (map stream-car argstreams))
       (apply stream-map
              (cons proc 
                    (map stream-cdr 
                         argstreams))))))

(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(define fibs 
  (cons-stream 
   0 (cons-stream
      1 (add-streams 
         (stream-cdr fibs) fibs))))

(stream-ref fibs 4)

大部分在线答案都说类似于 a(n) = a(n - 1) + a(n - 2) + 1。

跟踪的输出却有不同的解释。

- nate

Answer 1

[2021-05-05 注意：这与早期的 2019 版本答案有很大不同。实际结果是相同的！]

使用一些传统的数学符号而不是将所有内容都表达为Scheme，我发现这样更容易思考，斐波那契数列的流，f，看起来像这样：

f = (0, 1, f(0) + f(1), f(1) + f(2), ..., f(n-1) + f(n-2), ...)

在这个表达式中，我已经按照显而易见的方式展开了add-streams函数。

因此，如果没有记忆化，只需计数即可计算计算f(n)所涉及的加法次数。好吧，在计算中涉及的加法次数是流本身中的加法次数+我们要添加的两个组成流中的加法次数。

• 如果n <= 1，则流本身中的加法次数为0，否则为n-1，您可以从上面的流中仅计算'+'符号来看到这一点；
• 组成流中的加法次数为0，如果n <= 1（没有组成流），则为计算f(n-1)和f(n-2)的加法次数之和。

或者：

a = (0, 0, 1 + a(0) + a(1), 2 + a(1) + a(2), ..., n-1 + a(n-1) + a(n-2), ...)

当然，这是指数级的。可以轻松地对代码进行仪器化以计算加法次数，并编写此a函数以检查它们是否一致，它们确实一致。

我发现很难推断出f记忆化的情况（这实际上意味着force正在进行记忆化），因为所有黑暗角落都隐藏着状态。但是，我认为诀窍在于记住流线性访问：要计算f(n)，我必须已经计算了f(n-1)。而且一旦完成了这个步骤，再次计算它就是一个查找：没有涉及任何加法。因此，这一次a是

• 如果 n <= 1，则流本身中的加法次数为0，否则为n - 1，与以前相同；
• 加上组件流中的加法次数，因为它们已经被计算过，所以这个数字是零。

或者：

a = (0, 0, 1, 2, ..., n-1, ...)

这显然是线性的，与n成比例。

---

以下是一些Racket代码，实现了足够的流控制，可以对delay（称为retard）和force（称为advance）进行记忆化控制，以及调用计数支持：通过这些功能，您可以轻松地经验性地检查上述结果。fc计算第n个斐波那契数并计算+的调用次数，a和b是上面a的未记忆化和记忆化版本。

#lang racket

;;;; advance and retard are force & delay
;;; memoization can be controlled
;;;

(define advance-memoizes? (make-parameter #t))

(define not-memoized (cons #f #f))

(define-syntax-rule (retard form)
  (let ([memo not-memoized])
    (thunk
     (if (advance-memoizes?)
         (begin
           (when (eq? memo not-memoized)
             (set! memo form))
           memo)
         form))))

(define (advance retarded)
  (retarded))

;;;; mλ is a restricted memoizing λ
;;; Again memoization can be controlled
;;;

(define mλ-memoizes? (make-parameter #t))

(define-syntax-rule (mλ (arg) form)
  (let ([memos (make-hash)])
    (λ (arg)
      (if (mλ-memoizes?)
          (hash-ref! memos arg (thunk form))
          form))))


;;;; Streams
;;; functions are prefixed with s

(define-values (snull snull?)
  (values '() null?))

(define-syntax-rule (scons this that)
  (cons this (retard that)))

(define scar car)

(define (scdr stream)
  (advance (cdr stream)))

(define (sref s n)
  (if (= n 0)
      (scar s)
      (sref (scdr s) (- n 1))))

(define (smap p . streams)
  (let smap* ([ss streams])
    (if (memf snull? ss)
        snull
        (scons
         (apply p (map scar ss))
         (smap* (map scdr ss))))))
                
;;;; Counting function calls
;;;

(define (call/counted f . gs)
  ;; call f with 2 arguments for each function in gs:
  ;; - a function which is equivalent to the element of g
  ;; - and a function which will return the call count of that function.
  ;; Recursive calls to the gs are not counted
  (let cc-loop ([gt gs]
                [fs '()])
    (match gt
      ['() (apply f (reverse fs))]
      [(cons g gtt)
       (let ([gc 0])
         (cc-loop gtt (list*
                       (thunk gc)
                       (λ args
                         (set! gc (+ gc 1))
                         (apply g args))
                       fs)))])))

;;;; Counting fibs
;;;

(define (fc n #:memoize? (memoize? #t))
  ;; Return nth fib and number of calls to +
  (parameterize ([advance-memoizes? memoize?])
    (call/counted
     (λ (+/counted +-count)
       (define fibs
         (scons 0
                (scons 1
                       (smap +/counted (scdr fibs)
                             fibs))))
       (values (sref fibs n)
               (+-count)))
     +)))
            
(define a
  ;; unmemoized count (but this needs to be memoized!)
  (mλ (m)
    (cond
      [(or (= m 0) (= m 1)) 0]
      [(> m 1)
       (+ (- m 1)
          (a (- m 1))
          (a (- m 2)))]
      [else
       (error 'a "negative creep")])))

(define (b m)
  ;; memoized count
  (floor (- m 1)))

- user5920214

---

@nate：我不知道。我认为真正的计算机科学家必须有一些处理这类问题的方法。我最终只能靠猜测和检查是否与实际计数相符来解决问题，这太可怕了。 - user5920214

首先感谢您花费时间和精力回答这个问题。不幸的是，现在回过头来看，我必须取消接受该答案，因为实际上没有证据表明您的方程式是正确的。我们只是证明了这似乎是正确的。因此，SICP 3.57 在这里仍然没有得到答案。如果您或其他人能够提供清晰的方程式证明，并且最好还有信号处理图表，我将接受该答案。我可能会回到这个问题并尝试自己回答它，因为这是我无法满意回答的唯一一个 SICP 问题。 - nate

@nate：如果你想要的是证明而不仅仅是答案，你应该说清楚...但是显然我的回答并不是证明：它只是答案。 - user5920214

不，我的答案是当delay没有被记忆化时的答案。我想我回答了错误的问题... - user5920214

@nate 我要重新回答你的问题，因为我现在觉得我可以更容易地看到它了。不幸的是，这个答案会完全不同，所以你可能需要再次查看它。 - user5920214