Каков реальный ответ на SICP 3.57?

[2021-05-05 Примечание. Это кардинально отличается от более ранней версии этого ответа 2019. Фактический результат тот же!]

Используя какую-то традиционную математическую нотацию вместо того, чтобы выражать все в схеме, поскольку мне кажется, что об этом легче думать, поток чисел Фибоначчи, f, выглядит следующим образом:

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

В этом выражении я расширил функцию add-streams очевидным образом.

Итак, теперь, если нет мемоизации, остается просто подсчитать количество сложений, участвующих в вычислении f(n). Что ж, количество дополнений — это количество добавлений в самом потоке + количество добавлений в двух добавляемых нами составных потоках.

• количество добавлений в самом потоке равно 0, если n <= 1 в противном случае n - 1, что вы можете увидеть, просто взглянув на поток выше и подсчитав символы '+';
• количество дополнений в потоках компонентов равно 0, если n <= 1 (нет потоков компонентов), иначе сумма количества добавлений для вычисления f(n-1) и < em>f(n-2).

Or:

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, как и раньше;
• плюс количество дополнений в потоках компонентов, которое равно нулю, поскольку они уже были вычислены.

Or:

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

что, очевидно, линейно по n.

Ниже приведен некоторый код Racket, который реализует достаточное количество потоков, чтобы быть опасным, с контролем запоминания над delay (называемым retard) и force (называемым advance), а также поддержкой подсчета вызовов: с этим вы можете легко эмпирически проверить приведенные выше результаты. fc вычисляет nth fib и подсчитывает вызовы +, 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)))