SICP 3.57的真正答案是什么?

Question

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

网上有很多解决方案。大多数人声称fib序列的非优化memo-proc序列版本与计算非记忆正则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)的替换，其中'.'代表中缀stream-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))}

这是实际的球拍代码：

#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。 跟踪的输出讲述了一个不同的故事。

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其他n - 1，则流本身的添加数量是0的，你可以从上面的流中看出，并计算'+'符号;
• 如果n <= 1(无组件流(，则组件流中的添加数0计算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), ...)

当然，这在n是指数级的。 检测代码以计算添加次数并编写此a函数以检查它们是否同意很容易，他们确实这样做了。

我发现很难推理f被记住的情况(这实际上意味着force在记忆时(，因为所有黑暗的角落都隐藏着状态。 但我认为，诀窍是要记住流是线性访问的：要计算f(n)我必须已经计算了f(n-1)。 一旦完成，那么再次计算它是一个查找：不涉及添加。 所以这次a是

• 流本身的添加数量，如果像以前一样n - 1n <= 10;
• 加上组件流中的添加数，该数为零，因为它们已经计算出来。

或：

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

这显然是线性的n。

---

下面是一些Racket代码，它实现了足够多的危险流，对delay(称为retard(和force(称为advance(进行记忆控制，以及呼叫计数支持：有了这个，您可以轻松地凭经验检查上述结果。fc计算第nFIB 并计算对+的调用，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)))