Why am I getting stackoverflow?

Question

I played with Clojure and I managed to blow the stack. In this code snippet, I use recursion only with repetition. I do a lot of concatenation (note the concat in the trace below). I tried to do all the concatenated lists, since they are lazy, and I wanted them to be evaluated when I walked. I am still getting stack overflow. Here's the trace. I think this can be a common problem, and someone with a lot of Clojure hacking experience can point me in the right direction.

Here is the code snippet that caused the problem.

(defn move-split [[xs ys]] (doall (concat (list (concat xs (list (first ys)))) (list (next ys))))) 

I put doall there because of stackoverflow, but that still didn't solve the problem.

 (defn move-split [[xs ys]] (doall (concat (list (doall (concat xs (list (first ys)))) ) (doall (list (next ys))) ))) 

Pay attention to additional help? Here, when I call concat, I filter the result through doall. Stackoverflow is gone.

doall does not seem recursive. That is, nested lists, which are also the result of concat, are not evaluated. What do you think?

 Exception in thread "main" java.lang.reflect.InvocationTargetException at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39) at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25) at java.lang.reflect.Method.invoke(Method.java:597) at jline.ConsoleRunner.main(Unknown Source) Caused by: java.lang.StackOverflowError (bubble_sort2.clj:0) at clojure.lang.Compiler.eval(Compiler.java:5440) at clojure.lang.Compiler.load(Compiler.java:5857) at clojure.lang.Compiler.loadFile(Compiler.java:5820) at clojure.main$load_script.invoke(main.clj:221) at clojure.main$script_opt.invoke(main.clj:273) at clojure.main$main.doInvoke(main.clj:354) at clojure.lang.RestFn.invoke(RestFn.java:409) at clojure.lang.Var.invoke(Var.java:365) at clojure.lang.AFn.applyToHelper(AFn.java:163) at clojure.lang.Var.applyTo(Var.java:482) at clojure.main.main(main.java:37) ... 5 more Caused by: java.lang.StackOverflowError at clojure.core$seq.invoke(core.clj:122) at clojure.core$concat$fn__3450.invoke(core.clj:599) at clojure.lang.LazySeq.sval(LazySeq.java:42) at clojure.lang.LazySeq.seq(LazySeq.java:56) at clojure.lang.RT.seq(RT.java:450) at clojure.core$seq.invoke(core.clj:122) at clojure.core$concat$fn__3450.invoke(core.clj:599) at clojure.lang.LazySeq.sval(LazySeq.java:42) at clojure.lang.LazySeq.seq(LazySeq.java:56) at clojure.lang.RT.seq(RT.java:450) at clojure.core$seq.invoke(core.clj:122) at clojure.core$concat$fn__3450.invoke(core.clj:599) at clojure.lang.LazySeq.sval(LazySeq.java:42) at clojure.lang.LazySeq.seq(LazySeq.java:56) at clojure.lang.RT.seq(RT.java:450) at clojure.core$seq.invoke(core.clj:122) at clojure.core$concat$fn__3450.invoke(core.clj:599) at clojure.lang.LazySeq.sval(LazySeq.java:42) at clojure.lang.LazySeq.seq(LazySeq.java:56) at clojure.lang.RT.seq(RT.java:450) at clojure.core$seq.invoke(core.clj:122) at clojure.core$concat$fn__3450.invoke(core.clj:599) 

Answer 1

You collect a bunch of lazy operations in a row, creating an expression like

 (concat (concat (concat ... [3]) [2]) [1]) 

or similar. To determine even the first element in the resulting list, the compiler must deeply expand this stack of functions that you gave it. Try to structure your code so that this does not happen, or throw away (doall) each so often to force impatient / rigorous calculations. I can't go into details with just a stack trace, although the code will help.

Answer 2

Now let's add another answer that the OP delivered some source code and asked what is a great question. If this is wrong, someone will edit me accordingly.

It looks like you are converting [[1 2 3 4] [5 6 7]] to [[1 2 3 4 5] [6 7]]. Lists and lazy concats are not really the right solution to this problem, which is one of the reasons that cause you so much pain. My instinct would be to start with the vector [1 2 3 4 5 6 7] so that you constantly hold on and build sub-elements of this vector as needed. subvec cheap and fast, both for creation and for use.

For instance:

 (defn vector-split [v at] [(subvec v 0 at) (subvec v at)]) 

Answer 3

I'm not sure which inputs cause your function to explode. I can't get him to blow up two 5 billionth subsequences:

 boot.user=> (defn move-split [[xs ys]] #_=> (doall #_=> (concat #_=> (list (concat xs (list (first ys)))) #_=> (list (next ys))))) #'boot.user/move-split boot.user=> (def x (move-split [(range 5e0) (range 5e0)])) #'boot.user/x boot.user=> x ((0 1 2 3 4 0) (1 2 3 4)) boot.user=> (def x (move-split [(range 5e9) (range 5e9)])) #'boot.user/x boot.user=> (-> (nth x 0) first) 0 boot.user=> (-> (nth x 1) first) 1 

However, there are many possibilities to make this function more idiomatic. Looking at the function:

 (defn move-split [[xs ys]] (doall (concat (list (concat xs (list (first ys)))) (list (next ys))))) 

On line 4: we don’t need to build a list , since concat already returns the sequence. Similarly, we will not build list on line 5, or next already return the sequence. With these two changes:

 (defn move-split [[xs ys]] (doall (concat (concat xs (list (first ys))) (next ys)))) 

Now, why in the world would we doall up a perfectly good (lazy) function by pasting a doall at the top? Let's get rid of this. Also, since the function should return a two-element sequence, why not just do it instead of calling concat on line 3? The idiomatic way of constructing a two-element sequence is through the syntax of a vector literal. With these two changes we have:

 (defn move-split [[xs ys]] [(concat xs (list (first ys)))(next ys)]) 

Oh, and we can again apply the vector literal syntax instead of this list constructor, providing us with this final version:

 (defn move-split [[xs ys]] [(concat xs [(first ys)])(next ys)]) 

Now try this fn out ...

 boot.user=> (defn move-split [[xs ys]] #_=> [(concat xs [(first ys)])(rest ys)]) #'boot.user/move-split boot.user=> [(range 5e0) (range 5e0)] [(0 1 2 3 4) (0 1 2 3 4)] boot.user=> (def x (move-split [(range 5e0) (range 5e0)])) #'boot.user/x boot.user=> x [(0 1 2 3 4 0) (1 2 3 4)] boot.user=> (-> (nth x 0) first) 0 boot.user=> (-> (nth x 1) first) 1 

It seems to work. What if we have two huge subsequences? Let's try this with a pair of 5 billion subsequences:

 boot.user=> (def x (move-split [(range 5e9) (range 5e9)])) #'boot.user/x boot.user=> (-> (nth x 0) first) 0 boot.user=> (-> (nth x 1) first) 1 

In your initial question, as I said, I don’t know what source data called the original function in order to explode the stack. I saw this in the concat doc documentation:

Concatenated concatenations do not smooth out automatically! Thus, clj :: clojure.core / reduce with concat generates very nested structures and can easily generate stack overflows when trying to execute the resulting sequence. (apply concat ...).

Let us use a reduce to concat sequence of 10 sequences of 10 integers:

 boot.user=> (take 5 (reduce concat [] (for [x (range 1e1)] (range 1e1)))) (0 1 2 3 4) 

But if we try to use reduce to concat sequence of 10,000 sequences of 10 integers:

 boot.user=> (take 5 (reduce concat [] (for [x (range 1e5)] (range 1e1)))) java.lang.StackOverflowError: 

Using apply instead works fine:

 boot.user=> (take 5 (apply concat (for [x (range 1e5)] (range 1e1)))) (0 1 2 3 4) 

There is just something to keep in mind when concat .