Clojure - tail recursive sieve of Eratosthenes

Question

I have this implementation of the sieve of Eratosthenes in Clojure:

(defn sieve [n]
  (loop [last-tried 2 sift (range 2 (inc n))]
    (if
      (or (nil? last-tried) (> last-tried n))
      sift
      (let [filtered (filter #(or (= % last-tried) (< 0 (rem % last-tried))) sift)]
        (let [next-to-try (first (filter #(> % last-tried) filtered))]
        (recur next-to-try filtered))))))

For larger n (like 20000) it ends with stack overflow. Why doesn't tail call elimination work here? How to fix it?

Answer 1

If you look at the backtrace

(try
 (sieve 200000)
 (catch java.lang.StackOverflowError e
  (.printStackTrace e)))

it looks like this:

...
at clojure.lang.LazySeq.sval(LazySeq.java:42)
at clojure.lang.LazySeq.seq(LazySeq.java:56)
at clojure.lang.RT.seq(RT.java:440)
at clojure.core$seq__4176.invoke(core.clj:103)
at clojure.core$filter__5033$fn__5035.invoke(core.clj:1751)
at clojure.lang.LazySeq.sval(LazySeq.java:42)
at clojure.lang.LazySeq.seq(LazySeq.java:56)
...

It's too many filters that's causing the overflow, not the loop.

Unfortunately, I don't see an obvious solution for this.

Answer 2

Problem: filter does lazy evaluation, so each new level of filtering hangs around on the call stack.

Fix: Change (filter ...) to (doall (filter ...)).

See the explanation here.

Answer 3

I second Michal Marczyk's comment about checking out cgrande's beautiful incremental SoE. I did some really primitive benchmarks and put them up at http://clojure.roboloco.net/?p=100, for those curious about lazy prime generator performance.