1

我目前正在学习使用方案的一些更高级的功能，并且我遇到了惰性列表的障碍。

基本上，我正在尝试创建一个无限的、延迟生成的列表，并在其上应用一个延迟过滤器，并且只采用一个元素。我希望这会消耗很少的内存：过滤器一次只查看一个元素，并且不需要存储以前的条目。这是我的尝试：

(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))]))))))

因此，需要明确的是，这里的“惰性列表”是一个过程，当(force)d 产生时(head . tail)，其中head是列表中的一个值，并且tail是列表的其余部分（需要依次强制执行）。我不知道这是否是方案中的“标准”惰性列表或其他什么，但它是对我来说最有意义的变体。

该(lazy-arithmetic-sequence a b)函数（懒惰地）产生无限列表a, a+b, a+2b, a+3b, ...

该lazy-filter函数是问题的核心：它接受一个谓词和一个惰性列表，并返回一个包含所有过滤元素的惰性列表。强制时，它会通过输入列表找到应该包含的第一个元素，然后返回该元素与列表其余部分的惰性过滤器相结合。

为了测试这一点，我运行了这一行：

(force (lazy-filter (lambda (v) (= v 1000000000)) (lazy-arithmetic-sequence 0 1)))

这当然是一个相当无意义的过滤器（“在这个列表中从 0 到无穷大找到值 10 亿的元素”），但重点是测试代码。问题是这会消耗大量内存。几秒钟之内，它就达到了许多 GB，而且没有任何减速的迹象，我不明白为什么。

我不明白为什么垃圾收集器不回收从列表中产生的内存。循环lazy-filter是尾递归的，并且没有其他对惰性列表的引用，所以我觉得 GC 应该只是吞噬所有内存。为了确保我什至制作了一个在惰性过滤器循环的每次迭代中都运行垃圾收集器的版本，当然它没有帮助。

我的怀疑是，列表的头部有一些我没有看到的参考。就像，由delayin 惰性过滤器创建的闭包以某种方式使seq引用徘徊，或者其他什么。

我怎样才能重写它以不消耗无限量的内存？

如果这有什么不同，我正在运行 Chez Scheme，但我怀疑问题出在我身上，而不是方案实施

4

1 回答 1

1

以下是解决问题的方法：

(define lazy-filter
  (lambda (pred seq)
    (delay
      (let loop ([sequence seq])
        ;; the following single line is added:   ------ NB!
        (set! seq sequence)
        (let ([forced (force sequence)])
          (cond [(null? forced) '()]
                [(pred (car forced))
                 (cons (car forced) (lazy-filter pred (cdr forced)))]
                [else (loop (cdr forced))]))))))

我在 Racket 中尝试过(force (lazy-filter (lambda (v) (= v 100000000)) (lazy-arithmetic-sequence 0 1)))，它完成了，虽然很慢，在我的操作系统报告的恒定内存中运行，返回

'(100000000 . #<promise:unsaved-editor:12:4>)

如果(set! seq sequence)操作系统报告的内存消耗增加了几 GB，然后 Racket 报告它已经耗尽内存并且执行被中止。

下面是您的代码的其他一些重写，以及此答案的先前版本。

在 Racket 的调试器中尝试您的代码，我们得到

在此处输入图像描述

forced并且sequence进展顺利，但seq仍处于起步阶段。难怪，没有什么能改变它。

这正是你所怀疑的。无法释放对序列开头的引用，因为seq它一直保留到结果被发现并返回（作为cons对）。对于 100 个元素，这不是问题，但对于 10 亿个元素，它肯定是。

浮出水面loop，lazy-filter问题似乎消失了：

在此处输入图像描述

这种代码转换技术称为lambda 提升。

loop由于它，对in的调用lazy-filter变得完全而明显的尾部。由于尾调用优化，新的调用框架 (for loop) 可以替换旧的 (for lazy-filter)，它现在可以被丢弃，连同它对它持有的任何数据的引用 (这里, seq)。

调试器快照显示了调试代码时发生的情况。也许没有调试，它的编译方式不同，效率更高。也许一个非常智能的编译器实际上会通过 lambda 提升来编译它，因此seq可以放弃对第一个代码变体的引用，就像它在第二个代码变体中一样。看起来你的 Chez Scheme 虽然编译它就像带有调试的 Racket 一样（注意，我的 Racket 版本是旧的）。

所以这似乎是一个实施问题。

如果您尝试 lambda-lifted 代码并查看这是否解决了问题，您将肯定知道：

(define (lazy-filter pred seq)
    (delay (lazy-filter-loop pred seq)))

(define (lazy-filter-loop pred sequence)
        (let ([forced (force sequence)])
          (cond [(null? forced) '()]
                [(pred (car forced))
                  (cons (car forced) 
                          (lazy-filter pred (cdr forced)))]
                [else  (lazy-filter-loop pred (cdr forced))])))

尽管人们可以合理地期望 Chez 编译器自行执行此操作。也许您正在运行解释代码？也许您包含调试信息？这些都是需要考虑的问题。

重组代码的另一种方法是

(define lazy-filter
  (lambda (pred seq)
    (delay
      (let loop ([forced (force seq)])
          (cond [(null? forced) '()]
                [(pred (car forced))
                  (cons (car forced) 
                          (lazy-filter pred (cdr forced)))]
                [else  (set! seq (cdr forced))
                       (loop  (force (cdr forced)))])))))

（旧版本的答案如下：）

让我们看看强迫你的表达意味着什么。我将为您的变量和函数使用较短的名称，以便更直观、更直接地阅读代码。

我们将使用SSA 程序转换来明确函数的操作含义，并且仅在遇到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))

我们发现，强制你的惰性序列会强制它的第二个元素以及第一个元素！

（以下不正确：）

这实际上准确地解释了您正在观察的行为：

(force (lazy-filter (lambda (v) (= v 1000000000)) (lazy-arithmetic-sequence 0 1)))

需要找出过滤后的无限流的第二个元素才能返回cons结果的第一个单元格，但过滤后的序列中只有一个元素，因此对第二个元素的搜索永远不会结束。

于 2019-12-10T16:41:50.123 回答