Why am I getting a stackoverflow?

Question

I've been playing around with Clojure and I managed to blow the stack. In this piece of code, I use recursion only with recur. I am doing a lot of concatenation (note calls to concat in the trace below). I tried to doall on all concatenated lists, since these are lazy and I wanted them evaluated as I went along. I still get a stack overflow. Here's the trace. I am thinking this might be a common issue and someone with more experience hacking clojure can point me in the right direction.

Here's the piece of code that was causing the problem.

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

I put the doall in there because of the stackoverflow, but that still did not solve the problem.

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

Notice the extra doalls? Here, everwhere I call concat I filter the result through a doall. Stackoverflow gone.

doall does not seem to be recursive. That is nested lists that are also results 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're piling up a bunch of lazy operations all in a row, building up an expression like

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

or similar. In order to determine even the first element in the resulting list, the compiler must drill deeply into this stack of functions you've given it. Try to structure your code so that this doesn't happen, or throw in a (doall) every so often to force eager/strict computations. I can't really go into more detail with just a stack trace, though - code would help.