recursion - 如果 Clojure 中唯一不消耗堆栈的循环结构是 "recur"，那么这个惰性序列是如何工作的？

Question

The ClojureDocs page for lazy-seq gives an example生成所有正数的惰性序列:

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

这个惰性序列可以针对相当大的索引进行评估，而不会引发 StackOverflowError(与同一页面上的筛子示例不同):

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

如果 only recur can be used to avoid consuming stack frames在递归函数中，这个lazy-seq示例怎么可能看似调用自身而不会溢出堆栈？

Answer 1

惰性序列在 thunk 中具有序列生成计算的其余部分。它不会立即被调用。当请求每个元素(或可能的元素 block )时，将调用下一个 thunk 以检索值。如果继续，该 thunk 可能会创建另一个 thunk 来表示序列的尾部。神奇之处在于(1)这些特殊的 thunk 实现了序列接口(interface)，并且可以透明地使用；(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

魔法位发生在 clojure.lang.LazySeq 内部在 Java 中定义，但我们实际上可以通过在类型上实现接口(interface)并使用原子来缓存，直接在 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)