functional-programming - Scheme中流的空间复杂度

Question

我正在阅读计算机程序的结构和解释 (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 占用线性空间的额外帧。

这与其他语言中迭代器的行为不同。如果您需要深入下游，将占用大量空间。当然，也可以只保留直接封闭的框架而丢弃所有其他的祖先框架。这是实际的方案实现吗？

Answer 1

简短的回答，是的，在适当的情况下，直接封闭的环境被丢弃了。

我认为这不会发生在 (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 章以及递归与迭代过程的讨论，那么这是一个迭代过程，因为正文的最后一行是对同一函数的回调。

因此，也许您的问题可以重述为:“鉴于我现在对评估环境模型的了解，迭代过程如何使用恒定空间？”

正如你所说，这是因为祖先的框架被扔掉了。本书后面的第 5 章将详细介绍这是如何发生的，例如，第 5 节。 4.2 《序列求值与尾递归》，或者喜欢讲座视频，在 lecture 9b .

第 4 章和第 5 章的重要部分涵盖了明确回答这个问题所需的细节。或者正如作者所说，消除魔法。