为什么在 Clojure 中 reduce 会给出 StackOverflowError? [英] Why does reduce give a StackOverflowError in Clojure?

问题描述

我正在尝试连接 Seq 的 Seq.

我可以通过 apply concat 做到这一点.

user=>(count (apply concat (repeat 3000 (repeat 3000 true))))9000000

然而，根据我有限的知识，我会假设 apply 的使用会强制实现惰性 Seq，这对于非常大的输入来说似乎不合适.如果可以，我宁愿懒惰地这样做.

所以我认为使用 reduce 可以完成这项工作.

user=>(count (reduce concat (repeat 3000 (repeat 3000 true))))

但这会导致

StackOverflowError clojure.lang.RT.seq (RT.java:484)

我很惊讶，因为我会认为 reduce 的语义意味着它是尾调用递归.

两个问题:

• apply 是最好的方法吗?
• reduce 通常不适合大输入吗?

解决方案

使用 apply.当函数参数是惰性的时，apply 也是惰性的.

让我们检查一下对基础子序列的计数副作用:

(def counter (atom 0))(def ss (反复 3000(fn [] (反复 3000(fn [] (do (swap! counter inc) true))))))(def foo (应用 concat ss))so.core=>@柜台0so.core=>(dorun (需要 1 foo))零so.core=>@柜台1so.core=>(多伦(取 3001 foo))零so.core=>@柜台3001

---

reduce由于thunk组合导致大量concat溢出

惰性序列，例如由 concat 产生的序列，是通过 thunk、延迟函数调用实现的.当你 concat 一个 concat 的结果时，你已经在另一个 thunk 中嵌套了一个 thunk.在您的函数中，嵌套深度为 3000，因此一旦请求第一个项目，堆栈就会溢出，并且 3000 个嵌套的 thunk 被展开.

so.core=>(def bar (reduce concat (repeat 3000 (repeat 3000 true))))#'so.core/barso.core=>(第一个酒吧)StackOverflowError clojure.lang.LazySeq.seq (LazySeq.java:49)

惰性序列的实现 通常会在 seq ed 时展开嵌套的 thunks 蹦床样式并且不会炸毁堆栈:

so.core=>(循环 [lz [1], n 0](if (< n 3000) (recur (lazy-seq lz) (inc n)) lz))(1)

但是，如果您在实现它的同时在未实现部分的惰性序列中调用 seq...

so.core=>(循环 [lz [1], n 0](if (< n 3000) (recur (lazy-seq (seq lz)) (inc n)) lz))StackOverflowError so.core/eval1405/fn--1406 (form-init584039696026177116.clj:1)so.core=>(pst 3000)

<前>堆栈溢出错误so.core/eval1619/fn--1620 (form-init584039696026177116.clj:2)clojure.lang.LazySeq.sval (LazySeq.java:40)clojure.lang.LazySeq.seq (LazySeq.java:49)clojure.lang.RT.seq (RT.java:484)clojure.core/seq (core.clj:133)so.core/eval1619/fn--1620 (form-init584039696026177116.clj:2)clojure.lang.LazySeq.sval (LazySeq.java:40)clojure.lang.LazySeq.seq (LazySeq.java:49)clojure.lang.RT.seq (RT.java:484)clojure.core/seq (core.clj:133)……(反复)

然后你最终构建 seq 堆栈帧.concat 的实现就是这样.使用 concat 检查 StackOverflowError 的堆栈跟踪，您会看到类似的内容.

I'm trying to concatenate a Seq of Seqs.

I can do it with apply concat.

user=> (count (apply concat (repeat 3000 (repeat 3000 true))))
9000000

However, from my limited knowledge, I would assume that the use of apply forces the lazy Seq to be realised, and that doesn't seem right for very large inputs. I'd rather do this lazily if I can.

So I thought that using reduce would do the job.

user=> (count (reduce concat (repeat 3000 (repeat 3000 true))))

But this results in

StackOverflowError   clojure.lang.RT.seq (RT.java:484)

I'm surprised because I would have thought that the semantics of reduce would mean it was tail-call recursive.

Two questions:

• Is apply the best way to do this?
• Is reduce generally inappropriate for large inputs?

解决方案

Use apply. When the function argument is lazy, so is apply.

Let's check that with a counting side effect on the underlying sub-sequences:

(def counter (atom 0))

(def ss (repeatedly 3000 
          (fn [] (repeatedly 3000 
            (fn [] (do (swap! counter inc) true))))))


(def foo (apply concat ss))

so.core=> @counter
0

so.core=> (dorun (take 1 foo))
nil

so.core=> @counter
1

so.core=> (dorun (take 3001 foo))
nil

so.core=> @counter
3001

---

reduce with a large number of concats overflows due to thunk composition

Lazy sequences, such as those produced by concat are implemented with thunks, delayed function calls. When you concat the result of a concat you have nested a thunk within another thunk. In your function, the nesting goes 3000 deep and thus the stack is overflowed as soon as the first item is requested and the 3000 nested thunks are unwound.

so.core=>  (def bar (reduce concat (repeat 3000 (repeat 3000 true))))
#'so.core/bar

so.core=> (first bar)
StackOverflowError   clojure.lang.LazySeq.seq (LazySeq.java:49)

The implementation of lazy-sequences will in general unwind nested thunks trampoline style when seqed and not blow the stack:

so.core=> (loop [lz [1], n 0] 
            (if (< n 3000) (recur (lazy-seq lz) (inc n)) lz))
(1)

However, if you call seq within the lazy-sequence on the unrealized portion while realizing it...

so.core=> (loop [lz [1], n 0] 
            (if (< n 3000) (recur (lazy-seq (seq lz)) (inc n)) lz))
StackOverflowError   so.core/eval1405/fn--1406 (form-init584039696026177116.clj:1)

so.core=> (pst 3000)

StackOverflowError
        so.core/eval1619/fn--1620 (form-init584039696026177116.clj:2)
        clojure.lang.LazySeq.sval (LazySeq.java:40)
        clojure.lang.LazySeq.seq (LazySeq.java:49)
        clojure.lang.RT.seq (RT.java:484)
        clojure.core/seq (core.clj:133)
        so.core/eval1619/fn--1620 (form-init584039696026177116.clj:2)
        clojure.lang.LazySeq.sval (LazySeq.java:40)
        clojure.lang.LazySeq.seq (LazySeq.java:49)
        clojure.lang.RT.seq (RT.java:484)
        clojure.core/seq (core.clj:133)
        ... (repeatedly)

Then you end up building seq stack frames. The implementation of concat is such. Examine the stack trace for your StackOverflowError with concat and you will see similar.

这篇关于为什么在 Clojure 中 reduce 会给出 StackOverflowError?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！