Clojure thunk:堆栈溢出[0]但不是'(0)？

Question

这是一段代码,它给了我一个StackOverflowError(从我的代码库中的实际示例中简化):

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

(注:此代码是不是为了做除了说明问题或返回零任何东西.)

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

1. 删除该reduce行
2. 更改[0]到 '(0)
3. (take 100000000)在mapcat和之间的任何点添加(或任何整数)count.

我基本上对这种行为感到困惑(特别是#2).我很感激任何意见.

(我有一种感觉这可能与为什么reduce在Clojure中给出一个StackOverflowError有关？但是我不知道如何 - 所以如果它是相关的,我会理解为什么会这样解释.)

Answer 1

在正常情况下,reduce使用loop/ recurconstruct进行操作并使用常量堆栈空间.然而,你已经遇到了一个令人讨厌的角落情况,这是因为减少了通过提供concat交替的分块和非分块序列而产生的序列(向量[0]被分块; seq产生的(take 100 (repeat %))是非分块的).

当第一个参数concat为一个分块序列时,它将返回一个延迟序列,chunk-cons用于产生另一个分块序列.否则,它将cons用于生成非分块序列.

同时,实现reduce使用InternalReduce协议(定义clojure.core.protocols),该协议internal-reduce为结构提供功能,与默认的第一次/下一次递归相比,它可以更有效地减少自身.internal-reduce分块序列的实现使用块函数来循环使用分块项,直到它留下非分块序列,然后调用internal-reduce其余部分.默认internal-reduce实现类似地使用first/ next来消耗循环中的项,直到底层seq类型更改,然后调用internal-reduce新的seq类型以分派到适当的优化版本.当你逐步完成生成的seq,concat在chunked和non-chunked子序列之间交替时,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)使用非分块的子序列替换分块的子序列,绕过分块的seqs的优化,internal-reduce并允许减少在具有恒定堆栈空间的单个循环中发生.
• 插入take会创建一个新的非分块序列,完全由cons单元组成.