如果 Clojure 中唯一的非堆栈消耗循环结构是“recur"，那么这个惰性序列是如何工作的? [英] If the only non-stack-consuming looping construct in Clojure is "recur", how does this lazy-seq work?

问题描述

lazy-seq 的 ClojureDocs 页面给出了一个例子 生成所有正数的惰性序列:

The ClojureDocs page for lazy-seq gives an example of generating a lazy-seq of all positive numbers:

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

这个lazy-seq 可以针对相当大的索引进行评估，而不会抛出 StackOverflowError(与同一页面上的筛选示例不同):

This lazy-seq can be evaluated for pretty large indexes without throwing a StackOverflowError (unlike the sieve example on the same page):

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

如果 只有 recur 可用于避免消耗堆栈帧递归函数，这个lazy-seq的例子怎么可能在不溢出堆栈的情况下调用自己?

If only recur can be used to avoid consuming stack frames in a recursive function, how is it possible this lazy-seq example can seemingly call itself without overflowing the stack?

推荐答案

懒惰序列的其余部分在 thunk 中生成计算.它不会立即被调用.当请求每个元素(或元素块，视情况而定)时，调用下一个 thunk 以检索值.如果继续，该 thunk 可能会创建另一个 thunk 来表示序列的尾部.神奇之处在于(1)这些特殊的 thunk 实现了序列接口，并且可以透明地使用；(2)每个 thunk 只被调用一次——它的值被缓存——所以实现的部分是一个值序列.

A lazy sequence has the rest of the sequence generating calculation in a thunk. It is not immediately called. As each element (or chunk of elements as the case may be) is requested, a call to the next thunk is made to retrieve the value(s). That thunk may create another thunk to represent the tail of the sequence if it continues. The magic is that (1) these special thunks implement the sequence interface and can transparently be used as such and (2) each thunk is only called once -- its value is cached -- so the realized portion is a sequence of values.

这里是没有魔法的一般想法，只是很好的ol'功能:

Here it is the general idea without the magic, just good ol' functions:

(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 内部，但我们实际上可以通过在键入并使用原子进行缓存.

The magic bits happen inside of clojure.lang.LazySeq defined in Java, but we can actually do the magic directly in Clojure (implementation that follows for example purposes), by implementing the interfaces on a type and using an atom to cache.

(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 代替以消除任何混淆.

Now this already works with take, etc., but as take calls lazy-seq we'll make a my-take that uses my-lazy-seq instead to eliminate any confusion.

(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)))))))

现在让我们制作一个缓慢的无限序列来测试缓存行为.

Now let's make a slow infinite sequence to test the caching behavior.

(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)

这篇关于如果 Clojure 中唯一的非堆栈消耗循环结构是“recur"，那么这个惰性序列是如何工作的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！