Clojure thunks : stack overflow with [0] but not '(0)?

Question

这是一段代码，它给了我一个StackOverflowError(从我的代码库中的实际示例中总结出来):

( ->> (range 3000)
      (mapcat #(concat [0] (take 100 (repeat %))))
      (reduce (constantly nil))
      (count))

(注意:除了演示问题或返回零之外，此代码的目的不是做任何事情。)

我可以通过以下任何步骤“拯救”它:

1. 删除reduce行
2. 将[0]更改为'(0)
3. 在 mapcat 和 count 之间的任意点添加一个(取 100000000)(或任何整数)。

我基本上对这种行为感到困惑(尤其是#2)。我将不胜感激任何意见。

(我有一种感觉，这可能与 Why does reduce give a StackOverflowError in Clojure? 相关，但我不太清楚如何相关 - 所以如果它相关，我会很高兴解释原因。)

Answer 1

在正常情况下，reduce 使用loop/recur 结构进行操作并使用常量堆栈空间。但是，您遇到了一个令人讨厌的极端情况，这是由于减少了通过提供 concat 交替分块和非分块序列(向量 [0] 已分块)而生成的序列; (take 100 (repeat %)) 生成的 seq 是非分块的。

当 concat 的第一个参数是分块序列时，它将返回一个惰性序列，该序列将使用 chunk-cons 生成另一个分块序列。否则，它将使用 cons 生成非分块序列。

同时，reduce 的实现使用 InternalReduce 协议(protocol)(在 clojure.core.protocols 中定义)，该协议(protocol)提供了内部-reduce 结构函数，可以比默认的第一个/下一个递归更有效地减少自身。分块序列的 internal-reduce 实现使用分块函数来消耗循环中的分块项，直到剩下非分块序列，然后调用 internal-reduce其余的。默认的 internal-reduce 实现类似地使用 first/next 在循环中使用项目，直到底层 seq 类型发生更改，然后调用 对新的 seq 类型进行内部减少以分派(dispatch)到适当的优化版本。当您继续执行 concat 生成的 seq 时，在分块子序列和非分块子序列之间交替，internal-reduce 调用会堆积在堆栈上并最终耗尽堆栈。

此案例的更简单说明是:

;; All chunked sub-seqs is OK
user> (reduce + (apply concat (take 10000 (repeat [1]))))
10000

;; All non-chunked sub-seqs is OK
user> (reduce + (apply concat (take 10000 (repeat '(1)))))
10000

;; Interleaved chunked and non-chunked sub-seqs blows the stack
user> (reduce + (apply concat (take 10000 (interleave (repeat [1]) (repeat '(1))))))
StackOverflowError   clojure.lang.LazySeq.seq (LazySeq.java:60)

检查堆栈跟踪:

StackOverflowError 
    clojure.core/seq (core.clj:133)
    clojure.core/interleave/fn--4525 (core.clj:3901)
    clojure.lang.LazySeq.sval (LazySeq.java:42)
    clojure.lang.LazySeq.seq (LazySeq.java:60)
    clojure.lang.RT.seq (RT.java:484)
    clojure.core/seq (core.clj:133)
    clojure.core/take/fn--4232 (core.clj:2554)
    clojure.lang.LazySeq.sval (LazySeq.java:42)
    clojure.lang.LazySeq.seq (LazySeq.java:60)
    clojure.lang.Cons.next (Cons.java:39)
    clojure.lang.RT.next (RT.java:598)
    clojure.core/next (core.clj:64)
    clojure.core/concat/cat--3925/fn--3926 (core.clj:694)
    clojure.lang.LazySeq.sval (LazySeq.java:42)
    clojure.lang.LazySeq.seq (LazySeq.java:60)
    clojure.lang.ChunkedCons.chunkedNext (ChunkedCons.java:59)
    clojure.core/chunk-next (core.clj:660)
    clojure.core.protocols/fn--6041 (protocols.clj:101)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6034 (protocols.clj:147)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6041 (protocols.clj:104)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6034 (protocols.clj:147)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6041 (protocols.clj:104)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6034 (protocols.clj:147)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6041 (protocols.clj:104)

至于您的解决方法:

• 显然，避免 reduce 可以完全避免这个问题。
• 将 [0] 更改为 '(0) 会将分块子序列替换为非分块子序列，从而规避了内部对分块序列的优化 -减少并允​​许减少在具有恒定堆栈空间的单个循环中发生。
• 插入 take 会创建一个新的非分块序列，完全由 cons 单元组成。