2

我现在正在学习惰性序列，我注意到它们通常涉及递归而不使用recur. 例如，这里是 的实现iterate：

(defn iterate
  "Returns a lazy sequence of x, (f x), (f (f x)) etc. f must be free of side-effects"
  {:added "1.0"
   :static true}
  [f x] (cons x (lazy-seq (iterate f (f x)))))

我的印象是，如果你在不使用的情况下递归recur，它会为每次调用创建一个新的堆栈帧，如果你迭代足够多的时间，这可能会导致堆栈溢出。

lazy-seq吞噬堆栈帧吗？如果不是，它如何避免这种情况？

4

2 回答 2

4

lazy-seq当您看到它在此示例中包含对迭代的调用时，实际上并没有递归。相反，当您请求第二项时，lazy-seq 宏会将自身展开为暂停的调用。因此，每次您检索一个项目时，您都会再次调用一次，但旧调用不在堆栈上。

同样有趣的是您是否正在消耗内存，这取决于您对序列头部的处理方式。如果您保留在 var 或本地绑定中，则将保留整个 cons 单元链。如果您避免握住头部，并沿序列向下遍历，GC 可以在您身后进行清理。

一个棘手的问题是，lazy-seq 宏中有一些特殊的元数据 ^{:once true} 让编译器知道 fn 闭包是一次性的，而不是保留任何封闭的变量。

于 2014-05-28T06:26:39.433 回答
1

没有惰性序列不会吞噬堆栈帧。

从这段代码的表面上看，它似乎是一个递归调用，但lazy-seq 不是一个函数，它是一个宏，在这种特殊情况下将转换为：

(lazy-seq (iterate f (f x))

变成类似的东西

(new clojure.lang.LazySeq (fn [] (iterate f (f x))))

如您所见，迭代函数调用被包装在另一个函数中（这使它变得懒惰，即稍后将调用该函数）。

于 2014-05-28T06:20:11.237 回答