Я думаю, что стоит отметить, что анализ использования пространства в таких случаях не всегда достаточно прост.
Например, вот совершенно наивная реализация force & delay в Racket:
(define-syntax-rule (delay form)
(λ () form))
(define (force p)
(p))
И мы можем построить достаточно чего-нибудь, немного совместимого с потоками SICP, чтобы быть опасными для этого:
(define-syntax-rule (cons-stream kar kdr)
;; Both car & cdr can be delayed: why not? I think the normal thing is
;; just to delay the cdr
(cons (delay kar) (delay kdr)))
(define (stream-car s)
(force (car s)))
(define (stream-cdr s)
(force (cdr s)))
(define (stream-nth s n)
(if (zero? n)
(stream-car s)
(stream-nth (stream-cdr s) (- n 1))))
(Обратите внимание, что здесь много чего не хватает, потому что я ленивый.)
И на этом мы можем построить потоки целых чисел:
(define (integers-starting-from n)
(cons-stream n (integers-starting-from (+ n 1))))
И теперь мы можем попробовать это:
(define naturals (integers-starting-from 0))
(stream-nth naturals 10000000)
И эта последняя вещь возвращает 10000000, через некоторое время И мы можем вызывать его несколько раз, и каждый раз получаем один и тот же ответ.
Но наша реализация обещаний - отстой: принудительное выполнение обещания заставляет его работать каждый раз, мы его форсируем, и мы Я хотел бы сделать это один раз. Вместо этого мы могли бы запоминать наши обещания, чтобы этого не произошло, вот так (это, вероятно, не является потокобезопасным: это можно сделать так):
(define-syntax-rule (delay form)
(let ([thunk/value (λ () form)]
[forced? #f])
(λ ()
(if forced?
thunk/value
(let ([value (thunk/value)])
(set! thunk/value value)
(set! forced? #t)
value)))))
Весь остальной код одинаков.
Теперь, когда вы звоните (stream-nth naturals 10000000), у вас, вероятно, будет довольно плохое время: в частности, вам, скорее всего, не хватит памяти.
Причина, по которой вы будете иметь плохое время - это две вещи:
- есть ссылка на весь поток в виде
naturals; - , причудливые обещания запоминают свои значения, то есть весь хвост потока.
Это означает, что по мере того, как вы идете вниз по потоку, вы расходуете все большие объемы памяти до тех пор, пока не исчерпаете себя: сложность пространства программы идет как размер аргумента до stream-nth в последней строке.
Проблема здесь в том, что delay пытается быть умным, что бесполезно в этом случае. В частности, если вы думаете о потоках как об объектах, которые вы обычно просматриваете один раз, то запоминание их просто бесполезно: вы тщательно запомнили значение, которое никогда не будете использовать снова.
Версии delay & force предоставленный Racket memoize, и в этом случае он также будет использовать огромные объемы памяти.
Вы можете избежать этого либо не запоминать, либо быть уверенным, что никогда не держитесь за начало потока, поэтому G C можно забрать. В частности, эта программа
(define (silly-nth-natural n)
(define naturals (integers-starting-from 0))
(stream-nth naturals n))
не будет использовать пробел, пропорциональный n, потому что после того, как будет сделан первый хвостовой вызов stream-nth, ничто больше не будет удерживать начало потока.
Другой подход заключается в том, чтобы запомненное значение удерживалось только слабо, чтобы в случае отчаяния системы оно могло его отбросить. Вот хакерская и в основном не проверенная реализация этого (это очень специфично для Racket c):
(define-syntax-rule (delay form)
;; a version of delay which memoizes weakly
(let ([thunk (λ () form)]
[value-box #f])
(λ ()
(if value-box
;; the promise has been forced
(let ([value-maybe (weak-box-value value-box value-box)])
;; two things that can't be in the box are the thunk
;; or the box itself, since we made those ourselves
(if (eq? value-maybe value-box)
;; the value has been GCd
(let ([value (thunk)])
(set! value-box (make-weak-box value))
value)
;; the value is good
value-maybe))
;; the promise has not yet been forced
(let ((value (thunk)))
(set! value-box (make-weak-box value))
value)))))
Я подозреваю, что огромное количество слабых блоков может заставить G C выполнять большую работу .