如果Clojure中唯一不消耗堆栈的循环结构是“recur”，那么这个lazy-seq如何工作？

Question

ClojureDocs页面中对lazy-seq的介绍给出了一个例子，用于生成所有正数的延迟序列：

(defn positive-numbers
  ([] (positive-numbers 1))
  ([n] (cons n (lazy-seq (positive-numbers (inc n))))))

这个lazy-seq可以被评估为相当大的索引，而不会抛出StackOverflowError（与同一页上的筛子示例不同）：

user=> (nth (positive-numbers) 99999999)
100000000

如果在递归函数中只能使用 only recur 来避免消耗堆栈帧，那么这个懒惰序列的例子如何能够看似自我调用而不会导致堆栈溢出？

- matt b

---

我认为你在文档中过度解读了这句话，使它比实际上更有意义：“recur是唯一的非堆栈消耗的 循环结构”，但这并不意味着你不能使用非堆栈消耗的递归。请参考懒惰序列和 trampoline 的方法。 - Charles Duffy

Answer 1

一个惰性序列在一个thunk中生成其余的序列。它不会立即被调用。当每个元素（或一组元素）被请求时，将调用下一个thunk来检索值。如果需要继续生成序列，则该thunk可能创建另一个thunk来表示序列的尾部。这种魔法在于，(1)这些特殊的thunk实现了序列接口，并且可以透明地用作序列；(2)每个thunk只被调用一次--其值被缓存--因此已实现的部分是一系列值。

以下是没有魔法的概念，只使用了好的老函数：

(defn my-thunk-seq 
  ([] (my-thunk-seq 1)) 
  ([n] (list n #(my-thunk-seq (inc n)))))

(defn my-next [s] ((second s)))

(defn my-realize [s n] 
  (loop [a [], s s, n n] 
    (if (pos? n) 
      (recur (conj a (first s)) (my-next s) (dec n)) 
      a)))

user=> (-> (my-thunk-seq) first)
1
user=> (-> (my-thunk-seq) my-next first)
2
user=> (my-realize (my-thunk-seq) 10)
[1 2 3 4 5 6 7 8 9 10]
user=> (count (my-realize (my-thunk-seq) 100000))
100000 ; Level stack consumption

魔法发生在Java中定义的clojure.lang.LazySeq内部，但我们实际上可以直接在Clojure中执行魔法（为了示例目的而提供的实现），通过在类型上实现接口并使用原子进行缓存。

(deftype MyLazySeq [thunk-mem]
  clojure.lang.Seqable 
  (seq [_] 
    (if (fn? @thunk-mem) 
      (swap! thunk-mem (fn [f] (seq (f)))))
      @thunk-mem)
  ;Implementing ISeq is necessary because cons calls seq
  ;on anyone who does not, which would force realization.
  clojure.lang.ISeq
  (first [this] (first (seq this)))
  (next [this] (next (seq this)))
  (more [this] (rest (seq this)))
  (cons [this x] (cons x (seq this))))

(defmacro my-lazy-seq [& body] 
  `(MyLazySeq. (atom (fn [] ~@body))))

现在这个已经可以使用 take 等函数，但是由于 take 函数底层调用了 lazy-seq，我们将创建一个名为 my-take 的新函数，该函数使用 my-lazy-seq 来避免任何混淆。

(defn my-take
  [n coll]
  (my-lazy-seq
   (when (pos? n)
     (when-let [s (seq coll)]
      (cons (first s) (my-take (dec n) (rest s)))))))

现在让我们创建一个缓慢的无限序列来测试缓存行为。

(defn slow-inc [n] (Thread/sleep 1000) (inc n))

(defn slow-pos-nums 
  ([] (slow-pos-nums 1)) 
  ([n] (cons n (my-lazy-seq (slow-pos-nums (slow-inc n))))))

并且是REPL测试

user=> (def nums (slow-pos-nums))
#'user/nums
user=> (time (doall (my-take 10 nums)))
"Elapsed time: 9000.384616 msecs"
(1 2 3 4 5 6 7 8 9 10)
user=> (time (doall (my-take 10 nums)))
"Elapsed time: 0.043146 msecs"
 (1 2 3 4 5 6 7 8 9 10)

- A. Webb

---

注意：这里使用atom仅为举例而已。如果您真的被迫在Clojure中实现它，更好的选择是使用delay。 - A. Webb

Answer 2

请记住，lazy-seq是一个宏，因此当您调用positive-numbers函数时，它不会评估其主体。从这个意义上说，positive-numbers并不真正递归。它立即返回，并且对positive-numbers的内部“递归”调用直到序列被消耗才会发生。

user=> (source lazy-seq)
(defmacro lazy-seq
  "Takes a body of expressions that returns an ISeq or nil, and yields
  a Seqable object that will invoke the body only the first time seq
  is called, and will cache the result and return it on all subsequent
  seq calls. See also - realized?"
  {:added "1.0"}
  [& body]
  (list 'new 'clojure.lang.LazySeq (list* '^{:once true} fn* [] body)))

- Alex

Answer 3

我认为诀窍在于生产函数（positive-numbers）没有被递归调用，它不会像使用基本递归Little-Schemer风格调用的那样累积堆栈帧，因为LazySeq会根据需要为序列中的各个条目调用它。一旦对一个条目评估了闭包，那么它就可以被丢弃。因此，在代码通过序列时，以前调用函数的堆栈帧可以被垃圾回收。

- Nathan Hughes