5

The following piece of Clojure code results in java.lang.StackOverflowError when I call it with (avg-bids 4000 10 5). I try to figure out why, since sum-bids is written as a tail-recursive function, so that should work. Using Clojure 1.2.

Anyone knows why this happens? 

(ns fixedprice.core
  (:use (incanter core stats charts)))

(def *bid-mean* 100)

(defn bid [x std-dev]
  (sample-normal x :mean *bid-mean* :sd std-dev))

(defn sum-bids [n offers std-dev]
  (loop [n n sum (repeat offers 0)]
    (if (zero? n)
      sum
      (recur (dec n) (map + sum (reductions min (bid offers std-dev)))))))

(defn avg-bids [n offers std-dev]
  (map #(/ % n) (sum-bids n offers std-dev)))
Maurits Rijk
  • 9,789
  • 2
  • 36
  • 53
  • A tail-recursive function calls itself as the last thing it does. I don't see anything like that in your code. – Gabe Nov 22 '10 at 20:48
  • @Gabe: loop-recur causes a tail-recursion-like behavior. See http://clojure.org/special_forms. – Ralph Nov 22 '10 at 20:49
  • Ralph: `loop-recur` is a `for` loop pattern. Calling `recur` as the last thing in your function would be tail recursion, which is not what he does. – Gabe Nov 22 '10 at 21:12
  • 1
    `recur` complains in case it is not in tail position. – kotarak Nov 23 '10 at 08:47

1 Answers1

8

map is lazy, and you're building a very deeply nested mapping of mappings via recur. The backtrace is a bit cryptic, but look closely and you can see map, map, map...

Caused by: java.lang.StackOverflowError
        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$map$fn__3699.invoke(core.clj:2099)
        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$map$fn__3699.invoke(core.clj:2099)
        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$map$fn__3699.invoke(core.clj:2099)
        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$map$fn__3699.invoke(core.clj:2099)

One way to fix it is to put doall around it to defeat laziness.

(defn sum-bids [n offers std-dev]
  (loop [n n sum (repeat offers 0)]
    (if (zero? n)
      sum
      (recur (dec n) (doall (map + sum (reductions min (bid offers std-dev))))))))

user> (avg-bids 4000 10 5)
(100.07129114746716 97.15856005697917 95.81372899072466 94.89235550905231 94.22478826109985 93.72441188690516 93.32420819224373 92.97449591314158 92.67155818823753 92.37275046342015)
Brian Carper
  • 71,150
  • 28
  • 166
  • 168
  • 1
    Thanks Brian, that did the trick. I guess I have to be a little bit careful more aware of the consequences of lazy sequences. – Maurits Rijk Nov 22 '10 at 21:03