Hi Ulrich,
Wow, you got me scratching my head because your code should not even work.
The problem I see with it is that your recursion has no base case. You have
to know that 2 is prime to boot the algorithm. Eg
(def primes
(cons 2
(filter
(fn isprime[n]
(every?
#(pos? (mod n %))
(take-while #(<=(*%%)n) primes)))
(iterate inc 3))))
So now we have two behaviours to explain:
1/ why it works with iterate
2/ why it doesn't work with range
The difference comes from range returning a chunked seq (which explain the
batched processing you rightly identified)
Both have a definitive reentrant smell.
1/ Let's look at the code for LazySeq
https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/LazySeq.java#L59especially
the seq and sval methods.
So calling seq (and thus realizing the first prime) on a yet unrealized
primes sequence causes at some points to evaluate
(every?
#(pos? (mod n %))
(take-while #(<=(*%%)n) primes))
which by the nature of every? is going to realize at least one item of
primes. But we are exactly trying to compute it!
>From the implementation point of view, we are in the first call to seq, in
the while loop. f has been cleared bu the first call to sval (which set sv)
and sv cleared before entering the while and s has still its default value:
null.
Thus a recursive call to seq causes is going to see sv as null and returns
s which is null!
So the primes into the take-while is considered empty! Thus every? returns
true and 2 is considered prime! By luck.
A sentinel or a flag could solve the problem.
2/ This is the same problem exacerbated by the fact that we are producing a
chunked seq so the recursive call sees an empty prime for the first 30
items.
However if you swap iterate by range in my version (which is correct,
having a base case) you still have a reentrance bug
ser=> (def primes
(cons 2
(filter
(fn isprime[n]
(every?
#(pos? (mod n %))
(take-while #(<=(* % %)n) primes)))
(drop 3 (range)))))
#'user/primes
user=> (take 50 primes)
(2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 37 41 43 47 53 59 61 67 71 73
79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179
181 191 193 197)
Christophe
On Wed, Nov 28, 2012 at 2:29 PM, Ulrich <umuel...@c007.de> wrote:
> Hello,
>
> I tried to define the sequence of primes via corecursion,
> with trial divisions by primes p with p*p<=n,
> finally arriving at following code.
>
> (def primes
> (filter
> (fn isprime[n]
> (every?
> #(pos? (mod n %))
> (take-while #(<=(*%%)n) primes)
> )
> )
> (iterate inc 2)
> )
> )
>
> Seems there's nothing wrong with that,
> it's just the algorithm straightly set down
> in a functional way. And it works correctly
> as one can quickly confirm by "(take 50 primes)".
>
> But if replacing "(iterate inc 2)" with "(drop 2 (range))",
> we get strange behaviour, "primes" then consists of all!!
> numbers from 2 until 30 followed by primes only from 31 on.
>
> Being relatively new to clojure, I find this
> very irritating and a potential cause of bad bugs.
> And hope that this is not a bug in clojure itself
> or even bad language design, but rather
> some basic misunderstanding by me.
>
> So I analyzed it a bit, and it seems, that
> "range" triggers? execution of "drop" and "filter"
> in batches of 32 numbers, and "primes" in "take-while"
> is not updated during such a batch. While using
> "iterate" instead updates "primes" each step.
>
> Can someone more into clojure than me please correct and
> better explain internal reasons of this strange behaviour.
> How could one know the "batch size" of more complicated
> expressions? And how could "range" be wrapped to yield
> numbers one by one?
>
> Thanks, Ulrich.
>
>
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clojure@googlegroups.com
> Note that posts from new members are moderated - please be patient with
> your first post.
> To unsubscribe from this group, send email to
> clojure+unsubscr...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
--
On Clojure http://clj-me.cgrand.net/
Clojure Programming http://clojurebook.com
Training, Consulting & Contracting http://lambdanext.eu/
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
