nat*_*ate 6 lisp scheme sicp lazy-sequences racket
SICP练习3.57：当我们根据加流过程使用fib的定义来计算第n个斐波那契数时，要执行多少次加法运算？证明如果不使用3.5.1中描述的备忘录过程提供的优化而简单地将（delay？exp？）实现为（lambda（）？exp？），加法运算的数量将成倍增加。
在线上有许多解决方案。大多数人声称，fib序列的非优化备忘-proc序列版本与计算非存储的常规fib函数相同。当跟踪未优化的备忘版本时，我看到了一个不同的故事。
令A（n）为（stream-ref fibs n）执行的加法数
当在非优化（非存储流）上使用替换和函数定义时，我可以确切地看到这些加法是什么以及为什么会发生这些加法，但是我很难提出一个好的方程式来回答实际上是指数的。
例如，针对A（4）跟踪的加法为：
这是一些伪代码，用于显示（stream-ref fibs 4）的替换，其中“。” 代表中缀流约束，{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跟踪的输出讲述了一个不同的故事
小智 2
[ 2021-05-05注意：这与之前的有很大不同，注意：这与该答案的2019 年版本有很大不同。实际结果是一样的！]
\n使用某种传统的数学符号，而不是在方案中表达一切，因为我发现斐波那契数流更容易思考，f看起来像这样：
\n\n\n
f = (0, 1, f(0) + f(1), f(1) + f(2), ..., f(n-1) + f(n-2), ...)
在这个表达式中我扩展了add-streams在这个表达式中，我以明显的方式
所以现在，如果没有记忆化，只需通过计数来计算计算中涉及的加法次数f(n)。那么添加的数量就是流本身中的添加数量 \xc2\xa0+\xc2\xa0 我们要添加的两个组件流中的添加数量。
0if n <= 1else n - 1，您可以通过查看上面的流并计算 \' 来看到这一点+ \' 符号就可以看到这一点；0if n <= 1（无组件流） else 要计算的添加数量f(n-1)之和f(n-2)。或者：
\n\n\n\n
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是
0的n <= 1话n - 1；或者：
\n\n\n\n
a = (0, 0, 1, 2, ..., n-1, ...)
这是线性的n。
下面是一些 Racket 代码，它实现了足够多的危险流，具有对delay(called retard) 和force(used advance) 的记忆控制，以及调用计数支持：有了这个，您可以轻松地凭经验检查上述结果。 fc计算nth fib 并计算对 的调用+，a并且b是 的非记忆化和记忆化版本a。
#lang racket\n\n;;;; advance and retard are force & delay\n;;; memoization can be controlled\n;;;\n\n(define advance-memoizes? (make-parameter #t))\n\n(define not-memoized (cons #f #f))\n\n(define-syntax-rule (retard form)\n (let ([memo not-memoized])\n (thunk\n (if (advance-memoizes?)\n (begin\n (when (eq? memo not-memoized)\n (set! memo form))\n memo)\n form))))\n\n(define (advance retarded)\n (retarded))\n\n;;;; m\xce\xbb is a restricted memoizing \xce\xbb\n;;; Again memoization can be controlled\n;;;\n\n(define m\xce\xbb-memoizes? (make-parameter #t))\n\n(define-syntax-rule (m\xce\xbb (arg) form)\n (let ([memos (make-hash)])\n (\xce\xbb (arg)\n (if (m\xce\xbb-memoizes?)\n (hash-ref! memos arg (thunk form))\n form))))\n\n\n;;;; Streams\n;;; functions are prefixed with s\n\n(define-values (snull snull?)\n (values \'() null?))\n\n(define-syntax-rule (scons this that)\n (cons this (retard that)))\n\n(define scar car)\n\n(define (scdr stream)\n (advance (cdr stream)))\n\n(define (sref s n)\n (if (= n 0)\n (scar s)\n (sref (scdr s) (- n 1))))\n\n(define (smap p . streams)\n (let smap* ([ss streams])\n (if (memf snull? ss)\n snull\n (scons\n (apply p (map scar ss))\n (smap* (map scdr ss))))))\n \n;;;; Counting function calls\n;;;\n\n(define (call/counted f . gs)\n ;; call f with 2 arguments for each function in gs:\n ;; - a function which is equivalent to the element of g\n ;; - and a function which will return the call count of that function.\n ;; Recursive calls to the gs are not counted\n (let cc-loop ([gt gs]\n [fs \'()])\n (match gt\n [\'() (apply f (reverse fs))]\n [(cons g gtt)\n (let ([gc 0])\n (cc-loop gtt (list*\n (thunk gc)\n (\xce\xbb args\n (set! gc (+ gc 1))\n (apply g args))\n fs)))])))\n\n;;;; Counting fibs\n;;;\n\n(define (fc n #:memoize? (memoize? #t))\n ;; Return nth fib and number of calls to +\n (parameterize ([advance-memoizes? memoize?])\n (call/counted\n (\xce\xbb (+/counted +-count)\n (define fibs\n (scons 0\n (scons 1\n (smap +/counted (scdr fibs)\n fibs))))\n (values (sref fibs n)\n (+-count)))\n +)))\n \n(define a\n ;; unmemoized count (but this needs to be memoized!)\n (m\xce\xbb (m)\n (cond\n [(or (= m 0) (= m 1)) 0]\n [(> m 1)\n (+ (- m 1)\n (a (- m 1))\n (a (- m 2)))]\n [else\n (error \'a "negative creep")])))\n\n(define (b m)\n ;; memoized count\n (floor (- m 1)))\n