Space Scheme 中流的复杂度
Space complexity of streams in Scheme
我正在阅读 计算机程序的结构和解释 (SICP) 并想确保我的想法是正确的。
考虑以下使用递归定义的简单流：
(define (integers-starting-from n)
(cons-stream n (integers-starting-from (+ n 1))))
(define ints (integers-starting-from 1))
(car (cdr-stream (cdr-stream (cdr-stream (cdr-stream ints)))))
如果我们采用 SICP 中的实现，每当我们 cons-stream 时，我们实际上是在构造一个变量和一个 lambda 函数（用于延迟评估）。因此，随着我们 cdr-stream 沿着这个流， 嵌套的 lambda 函数 被创建，并且为 lambda 函数的评估存储了一个帧链。这些框架是必需的，因为 lambda 函数计算表达式并在封闭框架中找到它们。因此，我假设为了评估流的第 n 个元素，您需要存储 n 额外的帧，这些帧占用线性 space.
这与其他语言中迭代器的行为不同。如果您需要走得更远，将占用很多 space。当然，也可以只保留直接外框，将其他祖框全部扔掉。这是实际方案实施的作用吗？
简短的回答，是的，在适当的情况下，直接封闭的环境会被丢弃。
我认为 (car (cdr-stream (cdr-stream (cdr-stream (... 不会发生这种情况，但如果您转而查看 stream-ref 部分。 3.5.1:
(define (stream-ref s n)
(if (= n 0)
(stream-car s)
(stream-ref (stream-cdr s) (- n 1))))
如果你暂时忘记你对环境框架的了解，但回想一下第 1 章和递归与迭代过程的讨论，那么这是一个迭代过程，因为正文的最后一行是对相同的功能。
所以也许您的问题可以重述为：“鉴于我现在对环境评估模型的了解，迭代过程如何使用常量 space？”
正如你所说，因为祖传的框架被扔掉了。本书后面的第 5 章将详细介绍这种情况是如何发生的，例如 sect. 4.2 "Sequence Evaluation and Tail Recursion"，或者如果您喜欢讲座视频，请在lecture 9b.
第 4 章和第 5 章的重要部分涵盖了明确回答此问题所需的详细信息。或者正如作者所说，驱散魔法。
"nested lambda functions are created"
不。有 没有 嵌套范围。在
(define integers-starting-from
(lambda (n)
(cons-stream n (integers-starting-from (+ n 1)))))
(integers-starting-from (+ n 1)) 形式中对 integers-starting-from 的嵌套调用的参数，表达式 (+ n 1)，指的是 n 在对 [ 的原始调用中的绑定=18=]，但是 (+ n 1) 在调用 之前被评估。
Scheme 是一种 eager 编程语言，而不是 lazy 编程语言。
因此 cons-stream 结果中的 lambda 包含对调用框架的引用，是的，但是没有环境嵌套。在创建新的 lambda 并作为表示流的下一个状态的下一个 cons 单元格的一部分返回之前，已经获得了该值。
(define ints (integers-starting-from 1))
=
(define ints (let ((n 1))
(cons-stream n (integers-starting-from (+ n 1)))))
=
(define ints (let ((n 1))
(cons n (lambda () (integers-starting-from (+ n 1))))))
通话继续进行
(car (cdr-stream (cdr-stream ints)))
=
(let* ((ints (let ((n 1))
(cons n
(lambda () (integers-starting-from (+ n 1))))))
(cdr-ints ((cdr ints)))
(cdr-cdr-ints ((cdr cdr-ints)))
(res (car cdr-cdr-ints)))
res)
=
(let* ((ints (let ((n 1))
(cons n
(lambda () (integers-starting-from (+ n 1))))))
(cdr-ints ((cdr ints))
=
((let ((n 1))
(lambda () (integers-starting-from (+ n 1)))))
=
(integers-starting-from 2) ;; args before calls!
=
(let ((n 2))
(cons n
(lambda () (integers-starting-from (+ n 1)))))
)
(cdr-cdr-ints ((cdr cdr-ints)))
(res (car cdr-cdr-ints)))
res)
=
(let* ((ints (let ((n 1))
(cons n
(lambda () (integers-starting-from (+ n 1))))))
(cdr-ints (let ((n 2))
(cons n
(lambda () (integers-starting-from (+ n 1))))))
(cdr-cdr-ints (let ((n 3))
(cons n
(lambda () (integers-starting-from (+ n 1))))))
(res (car cdr-cdr-ints)))
res)
=
3
所以这里没有嵌套的 lambda。甚至不是 lambda 链，因为实现是非记忆化的。 cdr-ints 和 cdr-cdr-ints 的值是短暂的，在计算第三个元素时容易被垃圾收集。没有任何内容提及它们。
因此得到第 n 个元素是完成 常量 space 模垃圾 ，因为所有中间 O(n) space 个实体有资格被垃圾收集。
在 (one possible) memoizing 实现中，每个 lambda 实际上会被 cons 单元格 中的结果 替换，并且将是一个由三个组成的链——仍然是非嵌套的——lambda，与开放式列表一致
(1 . (2 . (3 . <procedure-to-go-next>)))
在不保留此类链顶部条目的程序中，所有临时 conses 也将有资格进行垃圾收集。
一个这样的例子，即使是非记忆 SICP 流，也是 the sieve of Eratosthenes。它的性能特征与其内部流的前缀部分没有内存保留是一致的。
我认为值得指出的是，在这种情况下对 space 用法的分析并不总是那么简单。
例如，这是 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)
最后这件事 returns 10000000，过了一会儿。我们可以多次调用它，每次都会得到相同的答案。
但是我们对 promise 的实现很糟糕：强制 promise 使它起作用 每次我们强制它，我们想做一次。相反，我们可以记住我们的承诺，这样就不会发生，就像这样（这可能不是线程安全的：它可以这样做）：
(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；
- 花哨的 promise 正在记忆它们的值，它们是流的整个尾部。
这意味着，当您沿着流向下走时，您会使用越来越多的内存，直到您 运行 out：程序的 space 复杂度与参数的大小相同到最后一行的 stream-nth。
这里的问题是 delay 试图以一种在这种情况下无益的方式变得聪明。特别是如果您将流视为您通常遍历一次的对象，那么记忆它们就毫无用处：您已经仔细记住了一个您永远不会再次使用的值。
Racket memoize 提供的delay & force版本，在这种情况下也会使用大量内存。
您可以通过不记忆或确保永远不要保留流的开头以便 GC 可以拾取它来避免这种情况。特别是这个程序
(define (silly-nth-natural n)
(define naturals (integers-starting-from 0))
(stream-nth naturals n))
将不会使用与 n 成比例的 space，因为一旦对 stream-nth 进行了第一次尾调用，就不再有任何内容保留在流的开头。
另一种方法是让 memoized 值只被弱保存，这样如果系统变得绝望它可以丢弃它。这是一个 hacky 且大部分未经测试的实现（这是非常特定于 Racket 的）：
(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)))))
我怀疑大量的 weak boxes 可能会使 GC 做很多工作。
我正在阅读 计算机程序的结构和解释 (SICP) 并想确保我的想法是正确的。
考虑以下使用递归定义的简单流：
(define (integers-starting-from n)
(cons-stream n (integers-starting-from (+ n 1))))
(define ints (integers-starting-from 1))
(car (cdr-stream (cdr-stream (cdr-stream (cdr-stream ints)))))
如果我们采用 SICP 中的实现，每当我们 cons-stream 时，我们实际上是在构造一个变量和一个 lambda 函数（用于延迟评估）。因此，随着我们 cdr-stream 沿着这个流， 嵌套的 lambda 函数 被创建，并且为 lambda 函数的评估存储了一个帧链。这些框架是必需的，因为 lambda 函数计算表达式并在封闭框架中找到它们。因此，我假设为了评估流的第 n 个元素，您需要存储 n 额外的帧，这些帧占用线性 space.
这与其他语言中迭代器的行为不同。如果您需要走得更远，将占用很多 space。当然，也可以只保留直接外框，将其他祖框全部扔掉。这是实际方案实施的作用吗？
简短的回答，是的，在适当的情况下，直接封闭的环境会被丢弃。
我认为 (car (cdr-stream (cdr-stream (cdr-stream (... 不会发生这种情况，但如果您转而查看 stream-ref 部分。 3.5.1:
(define (stream-ref s n)
(if (= n 0)
(stream-car s)
(stream-ref (stream-cdr s) (- n 1))))
如果你暂时忘记你对环境框架的了解，但回想一下第 1 章和递归与迭代过程的讨论，那么这是一个迭代过程，因为正文的最后一行是对相同的功能。
所以也许您的问题可以重述为：“鉴于我现在对环境评估模型的了解，迭代过程如何使用常量 space？”
正如你所说，因为祖传的框架被扔掉了。本书后面的第 5 章将详细介绍这种情况是如何发生的，例如 sect. 4.2 "Sequence Evaluation and Tail Recursion"，或者如果您喜欢讲座视频，请在lecture 9b.
第 4 章和第 5 章的重要部分涵盖了明确回答此问题所需的详细信息。或者正如作者所说，驱散魔法。
"nested lambda functions are created"
不。有 没有 嵌套范围。在
(define integers-starting-from
(lambda (n)
(cons-stream n (integers-starting-from (+ n 1)))))
(integers-starting-from (+ n 1)) 形式中对 integers-starting-from 的嵌套调用的参数，表达式 (+ n 1)，指的是 n 在对 [ 的原始调用中的绑定=18=]，但是 (+ n 1) 在调用 之前被评估。
Scheme 是一种 eager 编程语言，而不是 lazy 编程语言。
因此 cons-stream 结果中的 lambda 包含对调用框架的引用，是的，但是没有环境嵌套。在创建新的 lambda 并作为表示流的下一个状态的下一个 cons 单元格的一部分返回之前，已经获得了该值。
(define ints (integers-starting-from 1))
=
(define ints (let ((n 1))
(cons-stream n (integers-starting-from (+ n 1)))))
=
(define ints (let ((n 1))
(cons n (lambda () (integers-starting-from (+ n 1))))))
通话继续进行
(car (cdr-stream (cdr-stream ints)))
=
(let* ((ints (let ((n 1))
(cons n
(lambda () (integers-starting-from (+ n 1))))))
(cdr-ints ((cdr ints)))
(cdr-cdr-ints ((cdr cdr-ints)))
(res (car cdr-cdr-ints)))
res)
=
(let* ((ints (let ((n 1))
(cons n
(lambda () (integers-starting-from (+ n 1))))))
(cdr-ints ((cdr ints))
=
((let ((n 1))
(lambda () (integers-starting-from (+ n 1)))))
=
(integers-starting-from 2) ;; args before calls!
=
(let ((n 2))
(cons n
(lambda () (integers-starting-from (+ n 1)))))
)
(cdr-cdr-ints ((cdr cdr-ints)))
(res (car cdr-cdr-ints)))
res)
=
(let* ((ints (let ((n 1))
(cons n
(lambda () (integers-starting-from (+ n 1))))))
(cdr-ints (let ((n 2))
(cons n
(lambda () (integers-starting-from (+ n 1))))))
(cdr-cdr-ints (let ((n 3))
(cons n
(lambda () (integers-starting-from (+ n 1))))))
(res (car cdr-cdr-ints)))
res)
=
3
所以这里没有嵌套的 lambda。甚至不是 lambda 链，因为实现是非记忆化的。 cdr-ints 和 cdr-cdr-ints 的值是短暂的，在计算第三个元素时容易被垃圾收集。没有任何内容提及它们。
因此得到第 n 个元素是完成 常量 space 模垃圾 ，因为所有中间 O(n) space 个实体有资格被垃圾收集。
在 (one possible) memoizing 实现中，每个 lambda 实际上会被 cons 单元格 中的结果 替换，并且将是一个由三个组成的链——仍然是非嵌套的——lambda，与开放式列表一致
(1 . (2 . (3 . <procedure-to-go-next>)))
在不保留此类链顶部条目的程序中，所有临时 conses 也将有资格进行垃圾收集。
一个这样的例子，即使是非记忆 SICP 流，也是 the sieve of Eratosthenes。它的性能特征与其内部流的前缀部分没有内存保留是一致的。
我认为值得指出的是，在这种情况下对 space 用法的分析并不总是那么简单。
例如，这是 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)
最后这件事 returns 10000000，过了一会儿。我们可以多次调用它，每次都会得到相同的答案。
但是我们对 promise 的实现很糟糕：强制 promise 使它起作用 每次我们强制它，我们想做一次。相反，我们可以记住我们的承诺，这样就不会发生，就像这样（这可能不是线程安全的：它可以这样做）：
(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； - 花哨的 promise 正在记忆它们的值，它们是流的整个尾部。
这意味着，当您沿着流向下走时，您会使用越来越多的内存，直到您 运行 out：程序的 space 复杂度与参数的大小相同到最后一行的 stream-nth。
这里的问题是 delay 试图以一种在这种情况下无益的方式变得聪明。特别是如果您将流视为您通常遍历一次的对象，那么记忆它们就毫无用处：您已经仔细记住了一个您永远不会再次使用的值。
Racket memoize 提供的delay & force版本，在这种情况下也会使用大量内存。
您可以通过不记忆或确保永远不要保留流的开头以便 GC 可以拾取它来避免这种情况。特别是这个程序
(define (silly-nth-natural n)
(define naturals (integers-starting-from 0))
(stream-nth naturals n))
将不会使用与 n 成比例的 space，因为一旦对 stream-nth 进行了第一次尾调用，就不再有任何内容保留在流的开头。
另一种方法是让 memoized 值只被弱保存，这样如果系统变得绝望它可以丢弃它。这是一个 hacky 且大部分未经测试的实现（这是非常特定于 Racket 的）：
(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)))))
我怀疑大量的 weak boxes 可能会使 GC 做很多工作。