What's wrong with this clojure prime seq?

Question

I can't figure out why this definition of a lazy primes sequence would cause non-termination. The stack-trace I get isn't very helpful (my one complaint about clojure is obtuse stack-traces).

(declare naturals is-prime? primes)

(defn naturals
  ([] (naturals 1))
  ([n] (lazy-seq (cons n (naturals (inc n))))))

(defn is-prime? [n]
  (not-any? #(zero? (rem n %))
                (take-while #(> n (* % %)) (primes))))

(defn primes
  ([] (lazy-seq (cons 2 (primes 3))))
  ([n] (let [m (first (filter is-prime? (naturals n)))]
         (lazy-seq (cons m (primes (+ 2 m)))))))

(take 10 (primes)) ; this results in a stack overflow error

Answer 1

Let's start executing primes, and we'll magically realise one seq just to be clear. I'll ignore naturals because it's correctly lazy:

 > (magically-realise-seq (primes))
=> (magically-realise-seq (lazy-seq (cons 2 (primes 3))))
=> (cons 2 (primes 3))
=> (cons 2 (let [m (first (filter is-prime? (naturals 3)))]
             (lazy-seq (cons m (primes (+ 2 3))))))
=> (cons 2 (let [m (first (filter
                            (fn [n]
                              (not-any? #(zero? (rem n %))
                                            (take-while #(> n (* % %)) (primes))))) 
                            (naturals 3)))]
             (lazy-seq (cons m (primes (+ 2 3))))))

I've substituted is-prime? in as a fn at the end there—you can see that primes will get called again, and realised at least once as take-while pulls out elements. This will then cause the loop.

Answer 2

The issue is that to know to calculate the "primes" function you are using the "is-prime?" function, and then to calculate the "is-prime?" function you are using "(primes)", hence the stack over flow.

So to calculate the "(primes 3)", you are need calculate the "(first (filter is-prime? (naturals 3)))", which is going to call "(is-prime? 1)", which is calling "(primes)", which in turns calls "(primes 3)". In other words you are doing:

user=> (declare a b)
#'user/b
user=> (defn a [] (b))
#'user/a
user=> (defn b [] (a))
#'user/b
user=> (a)
StackOverflowError   user/b (NO_SOURCE_FILE:1)

To see how to generate prime numbers: Fast Prime Number Generation in Clojure

Answer 3

I think the problem is, that you're trying to use (primes) before it's already constructed.

Changing is-prime? like that fixes the problem:

(defn is-prime? [n]
     (not-any? #(zero? (rem n %))
               (take-while #(>= n (* % %)) (next (naturals)))))

(Note, that I've changed > with >=, otherwise it gives that 4 is prime. It still says that 1 is prime, which isn't true and may cause problems if you use is-prime? elsewhere.