为什么我在 scheme 中的惰性过滤列表会消耗这么多内存？
Why does my lazy filtered list in scheme consume so much memory?
我目前正在学习使用 scheme 的一些稍微更高级的功能，但我遇到了惰性列表的障碍。
基本上，我正在尝试创建一个无限的、延迟生成的列表，并对其应用延迟过滤器，并且只采用一个元素。我希望这会消耗很少的内存：过滤器一次只查看一个元素，并且不需要存储以前的条目。这是我的尝试：
(define lazy-inf-seq
(lambda (start next)
(delay (cons start (lazy-inf-seq (next start) next)))))
(define lazy-arithmetic-sequence
(lambda (start d)
(lazy-inf-seq start (lambda (v) (+ v d)))))
(define lazy-filter
(lambda (pred seq)
(delay
(let loop ([sequence seq])
(let ([forced (force sequence)])
(cond [(null? forced) '()]
[(pred (car forced))
(cons (car forced) (lazy-filter pred (cdr forced)))]
[else (loop (cdr forced))]))))))
所以，为了清楚起见，这里的 "lazy list" 是一个过程，当 (force)d 时，生成 (head . tail)，其中 head 是列表，tail 是列表的其余部分（需要依次强制执行）。我不知道这是方案中的 "standard" 惰性列表还是其他什么，但这是对我来说最有意义的变体。
(lazy-arithmetic-sequence a b) 函数（懒惰地）生成无限列表 a, a+b, a+2b, a+3b, ...
lazy-filter 函数是问题的核心：它接受一个谓词和一个惰性列表，returns 一个包含所有过滤元素的惰性列表。强制时，它会遍历输入列表，找到应该包含的第一个元素，然后 returns 该元素与列表其余部分的惰性过滤器相结合。
为了测试这一点，我 运行 这一行：
(force (lazy-filter (lambda (v) (= v 1000000000)) (lazy-arithmetic-sequence 0 1)))
这当然是一个毫无意义的过滤器 ("find the element with value one billion in this list from 0 to infinity")，但重点是测试代码。问题是这会消耗大量内存。几秒钟之内它就达到了好几千兆字节，而且它没有显示出减速的迹象，我不明白为什么。
我不明白为什么垃圾收集器不回收从列表中产生的内存。 lazy-filter 中的循环是尾递归的，并且没有其他对惰性列表的引用，所以我觉得 GC 应该吞噬掉所有内存。为了确保我什至制作了一个 运行 垃圾收集器的版本，在惰性过滤器循环的每次迭代中，当然它没有帮助。
我怀疑列表的开头有一些我没有看到的参考。就像，由 delay 在 lazy-filter 中创建的闭包以某种方式使 seq 引用挂起，或者其他什么。
我如何重写它才能不消耗无限量的内存？
我 运行ning Chez Scheme 如果这有什么不同，但我怀疑问题出在我身上而不是方案实施
解决问题的方法如下：
(定义lazy-filter
(lambda (pred <b>seq</b>)
（延迟
(让<b>循环</b>([序列seq])
;;添加了以下单行： ------ 注意！
<b>(set!seq序列)</b>
(let ([forced (forced sequence)])
(cond [(null?forced) '()]
[（pred（强制车））
(cons (car forced) (lazy-filter pred (cdr forced)))]
[else (<b>loop</b> (cdr forced))]))))))
我在 Racket 中尝试了 (force (lazy-filter (lambda (v) (= v 100000000)) (lazy-arithmetic-sequence 0 1)))，它完成了，虽然很慢，运行ning 在我的 OS、returning[= 报告的常量内存中37=]
'(100000000 . #<promise:unsaved-editor:12:4>)
如果没有 (set! seq sequence)，OS 报告的内存消耗会激增几千兆字节，然后 Racket 报告它 运行 内存不足并且执行中止。
您的其他一些 re-writes 代码位于下方，以及此答案的先前版本。
在 Racket 的调试器中尝试你的代码，我们得到
forced 和 sequence 进展顺利，但 seq 仍处于起步阶段。难怪，没有什么能改变它。
这正是您所怀疑的。无法释放对序列开头的引用，因为 seq 一直保留它直到找到结果并 returned（作为 cons 对）。对于 100 个元素，这不是问题，但对于 10 亿个元素，它肯定是。
将 loop 浮动 lazy-filter，问题似乎消失了：
这种代码转换技术被称为 lambda lifting。
lazy-filter 中对 loop 的调用因此变得完整而明显 tail。由于尾部调用优化，新的调用框架（对于 loop）可以替换旧的（对于 lazy-filter），旧的（对于 lazy-filter）现在可以被丢弃，连同它对它持有的任何数据的引用（这里，seq).
调试器快照显示了调试代码时发生的情况。也许在没有调试的情况下，它的编译方式不同，效率更高。也许一个非常聪明的编译器实际上会通过 lambda 提升来编译它，因此可以放弃对 seq 的引用，在第一个代码变体中就像在第二个代码变体中一样。看起来像您的 Chez Scheme，尽管编译它就像带调试的 Racket 一样（注意，我的 Racket 版本是旧的）。
所以它看起来确实像是一个实现问题。
如果您尝试 lambda-lifted 代码并查看是否能解决问题，您就会确定：
(定义 (lazy-filter pred <b>seq</b>)
(延迟<b>(lazy-filter-循环预测序列)</b>))
(定义<b>(lazy-filter-循环预测序列)</b>
(let ([forced (forced sequence)])
(cond [(null?forced) '()]
[（pred（强制车））
（缺点（汽车被迫）
(lazy-filter pred (cdr 强制)))]
[else <b>(lazy-filter-loop pred (cdr forced))</b>])))
尽管可以合理地期望 Chez 编译器自行完成此操作。也许您正在 运行ning 解释代码？也许您包含了调试信息？这些是需要考虑的问题。
重构代码的另一种方法是
(定义lazy-filter
(lambda (pred <b>seq</b>)
（延迟
(let <b>loop</b> ([forced (force <b>seq</b>)])
(cond [(null?forced) '()]
[（pred（强制车））
（缺点（汽车被迫）
(lazy-filter pred (cdr 强制)))]
[else <b>(set!seq (cdr forced))</b>
(<b>loop</b> (force (cdr forced)))])))))
（旧版答案如下：）
让我们看看强制 你的表达需要什么。我将为您的变量和函数使用更短的名称，以便更直观、更直接地阅读代码。
我们将使用SSA program transformation来明确函数的操作意义，并且只在遇到delay形式时停止。
您没有包含 delay 和 force 定义，但我们假设 (force (delay <exp>)) = <exp>:
(define (lz-seq s n) (delay (cons s (lz-seq (n s) n))))
(force (lz-seq s n))
=
(cons s (lz-seq (n s) n)) ;; lz-seq is a function, needs its args eval'd
=
(cons s (let* ([s2 (n s)]) (lz-seq s2 n)))
=
(let* ([s2 (n s)]
[lz2 (delay (cons s2 (lz-seq (n s2) n))) ])
(cons s lz2))
我们发现强制使用您的惰性序列会强制其 second 元素以及第一个元素！
(以下错误:)
事实上，这恰好解释了您观察到的行为：
(force (lazy-filter (lambda (v) (= v 1000000000)) (lazy-arithmetic-sequence 0 1)))
需要找出过滤无限流的第二个元素，然后才能return结果的第一个cons单元格，但只有过滤序列中的一个元素，因此对第二个元素的搜索永远不会结束。
我目前正在学习使用 scheme 的一些稍微更高级的功能，但我遇到了惰性列表的障碍。
基本上，我正在尝试创建一个无限的、延迟生成的列表，并对其应用延迟过滤器，并且只采用一个元素。我希望这会消耗很少的内存：过滤器一次只查看一个元素，并且不需要存储以前的条目。这是我的尝试：
(define lazy-inf-seq
(lambda (start next)
(delay (cons start (lazy-inf-seq (next start) next)))))
(define lazy-arithmetic-sequence
(lambda (start d)
(lazy-inf-seq start (lambda (v) (+ v d)))))
(define lazy-filter
(lambda (pred seq)
(delay
(let loop ([sequence seq])
(let ([forced (force sequence)])
(cond [(null? forced) '()]
[(pred (car forced))
(cons (car forced) (lazy-filter pred (cdr forced)))]
[else (loop (cdr forced))]))))))
所以，为了清楚起见，这里的 "lazy list" 是一个过程，当 (force)d 时，生成 (head . tail)，其中 head 是列表，tail 是列表的其余部分（需要依次强制执行）。我不知道这是方案中的 "standard" 惰性列表还是其他什么，但这是对我来说最有意义的变体。
(lazy-arithmetic-sequence a b) 函数（懒惰地）生成无限列表 a, a+b, a+2b, a+3b, ...
lazy-filter 函数是问题的核心：它接受一个谓词和一个惰性列表，returns 一个包含所有过滤元素的惰性列表。强制时，它会遍历输入列表，找到应该包含的第一个元素，然后 returns 该元素与列表其余部分的惰性过滤器相结合。
为了测试这一点，我 运行 这一行：
(force (lazy-filter (lambda (v) (= v 1000000000)) (lazy-arithmetic-sequence 0 1)))
这当然是一个毫无意义的过滤器 ("find the element with value one billion in this list from 0 to infinity")，但重点是测试代码。问题是这会消耗大量内存。几秒钟之内它就达到了好几千兆字节，而且它没有显示出减速的迹象，我不明白为什么。
我不明白为什么垃圾收集器不回收从列表中产生的内存。 lazy-filter 中的循环是尾递归的，并且没有其他对惰性列表的引用，所以我觉得 GC 应该吞噬掉所有内存。为了确保我什至制作了一个 运行 垃圾收集器的版本，在惰性过滤器循环的每次迭代中，当然它没有帮助。
我怀疑列表的开头有一些我没有看到的参考。就像，由 delay 在 lazy-filter 中创建的闭包以某种方式使 seq 引用挂起，或者其他什么。
我如何重写它才能不消耗无限量的内存？
我 运行ning Chez Scheme 如果这有什么不同，但我怀疑问题出在我身上而不是方案实施
解决问题的方法如下：
(定义lazy-filter
(lambda (pred <b>seq</b>)
（延迟
(让<b>循环</b>([序列seq])
;;添加了以下单行： ------ 注意！
<b>(set!seq序列)</b>
(let ([forced (forced sequence)])
(cond [(null?forced) '()]
[（pred（强制车））
(cons (car forced) (lazy-filter pred (cdr forced)))]
[else (<b>loop</b> (cdr forced))]))))))
我在 Racket 中尝试了 (force (lazy-filter (lambda (v) (= v 100000000)) (lazy-arithmetic-sequence 0 1)))，它完成了，虽然很慢，运行ning 在我的 OS、returning[= 报告的常量内存中37=]
'(100000000 . #<promise:unsaved-editor:12:4>)
如果没有 (set! seq sequence)，OS 报告的内存消耗会激增几千兆字节，然后 Racket 报告它 运行 内存不足并且执行中止。
您的其他一些 re-writes 代码位于下方，以及此答案的先前版本。
在 Racket 的调试器中尝试你的代码，我们得到
forced 和 sequence 进展顺利，但 seq 仍处于起步阶段。难怪，没有什么能改变它。
这正是您所怀疑的。无法释放对序列开头的引用，因为 seq 一直保留它直到找到结果并 returned（作为 cons 对）。对于 100 个元素，这不是问题，但对于 10 亿个元素，它肯定是。
将 loop 浮动 lazy-filter，问题似乎消失了：
这种代码转换技术被称为 lambda lifting。
lazy-filter 中对 loop 的调用因此变得完整而明显 tail。由于尾部调用优化，新的调用框架（对于 loop）可以替换旧的（对于 lazy-filter），旧的（对于 lazy-filter）现在可以被丢弃，连同它对它持有的任何数据的引用（这里，seq).
调试器快照显示了调试代码时发生的情况。也许在没有调试的情况下，它的编译方式不同，效率更高。也许一个非常聪明的编译器实际上会通过 lambda 提升来编译它，因此可以放弃对 seq 的引用，在第一个代码变体中就像在第二个代码变体中一样。看起来像您的 Chez Scheme，尽管编译它就像带调试的 Racket 一样（注意，我的 Racket 版本是旧的）。
所以它看起来确实像是一个实现问题。
如果您尝试 lambda-lifted 代码并查看是否能解决问题，您就会确定：
(定义 (lazy-filter pred <b>seq</b>)
(延迟<b>(lazy-filter-循环预测序列)</b>))
(定义<b>(lazy-filter-循环预测序列)</b>
(let ([forced (forced sequence)])
(cond [(null?forced) '()]
[（pred（强制车））
（缺点（汽车被迫）
(lazy-filter pred (cdr 强制)))]
[else <b>(lazy-filter-loop pred (cdr forced))</b>])))
尽管可以合理地期望 Chez 编译器自行完成此操作。也许您正在 运行ning 解释代码？也许您包含了调试信息？这些是需要考虑的问题。
重构代码的另一种方法是
(定义lazy-filter
(lambda (pred <b>seq</b>)
（延迟
(let <b>loop</b> ([forced (force <b>seq</b>)])
(cond [(null?forced) '()]
[（pred（强制车））
（缺点（汽车被迫）
(lazy-filter pred (cdr 强制)))]
[else <b>(set!seq (cdr forced))</b>
(<b>loop</b> (force (cdr forced)))])))))
（旧版答案如下：）
让我们看看强制 你的表达需要什么。我将为您的变量和函数使用更短的名称，以便更直观、更直接地阅读代码。
我们将使用SSA program transformation来明确函数的操作意义，并且只在遇到delay形式时停止。
您没有包含 delay 和 force 定义，但我们假设 (force (delay <exp>)) = <exp>:
(define (lz-seq s n) (delay (cons s (lz-seq (n s) n))))
(force (lz-seq s n))
=
(cons s (lz-seq (n s) n)) ;; lz-seq is a function, needs its args eval'd
=
(cons s (let* ([s2 (n s)]) (lz-seq s2 n)))
=
(let* ([s2 (n s)]
[lz2 (delay (cons s2 (lz-seq (n s2) n))) ])
(cons s lz2))
我们发现强制使用您的惰性序列会强制其 second 元素以及第一个元素！
(以下错误:)
事实上，这恰好解释了您观察到的行为：
(force (lazy-filter (lambda (v) (= v 1000000000)) (lazy-arithmetic-sequence 0 1)))
需要找出过滤无限流的第二个元素，然后才能return结果的第一个cons单元格，但只有过滤序列中的一个元素，因此对第二个元素的搜索永远不会结束。