使用Racket实现流时遭遇内存溢出问题求助

我业余时间在学《计算机程序的构造和解释》（也就是常说的“巫师书”），前面进展都很顺利，直到尝试实现第三章的流结构。我用的是(Dr)Racket而非标准Scheme，这可能是问题的根源。

核心问题是创建流时触发内存错误：interactions disabled; out of memory，我怀疑是delay的用法出了问题。

我先试了书中推荐的代码：

#lang racket

(define (cons-stream a b)
  (cons a (delay b)))

(define (car-stream s)
  (car s))

(define (cdr-stream s)
  (force (cdr s)))

这里直接调用了Racket自带的delay和force。后来我也按照书中的方式自行实现了delay和force，但还是遇到同样的内存错误。

为了测试功能，我写了两个用例：

• 无限1流：

(define (ones) (cons-stream 1 (ones)))

• 超大区间流：

(define (interval low high)
  (if (> low high)
      null
      (cons-stream low
                   (interval (+ low 1) high))))

(define (first-integers n)
  (interval 0 n))

(define test-interval
  (first-integers 10000000000000000000000000))

按我的理解，这两个测试用例都不该出问题，因为流应该是按需生成的，但实际却触发了内存问题，看起来代码在尝试生成整个流的内容。

问题原因与解决办法 #

Racket的delay和标准Scheme里的delay有个关键区别：Racket默认会对delay的参数进行严格求值（哪怕用了delay，参数在传入delay前就会被计算），而SICP里的delay是完全惰性求值，只会在force时才计算参数。你自己实现delay和force时，也没绕开Racket的严格求值规则，所以才会内存溢出。

贴合SICP的流实现 #

要在Racket里实现符合SICP预期的流，需要用lazy宏确保第二个参数不会被提前求值，修改后的代码如下：

#lang racket

(define-syntax cons-stream
  (syntax-rules ()
    [(cons-stream a b) (cons a (delay (lazy b)))]))

(define (car-stream s) (car s))
(define (cdr-stream s) (force (cdr s)))

更简单的方案：用Racket内置流库 #

直接用Racket自带的racket/stream模块，它已经实现了正确的惰性流逻辑，写法也和SICP的流思路一致：

#lang racket

(require racket/stream)

; 无限1流
(define ones (stream-cons 1 ones))

; 区间流实现
(define (interval low high)
  (if (> low high)
      empty-stream
      (stream-cons low (interval (+ low 1) high))))

(define test-interval (interval 0 10000000000000000000000000))

为什么你的代码会溢出 #

你写的(define (ones) (cons-stream 1 (ones)))，在Racket的严格求值规则下，(ones)作为cons-stream的第二个参数，会被立即递归调用，哪怕套了delay也没用——因为delay的参数在传入前就被求值了，直接触发无限递归撑爆内存。用lazy包裹后，参数的求值会被完全推迟到force调用时，才会按需生成下一个流元素。

内容的提问来源于stack exchange，提问作者user11450692