A more succinct test case: user=> (def escher-seq (lazy-seq (lazy-seq (if (seq escher-seq) nil (list 42))))) #'user/escher-seq user=> escher-seq (42)
thus escher-seq is not empty because it is empty :-) On Wed, Nov 28, 2012 at 4:42 PM, Christophe Grand <christo...@cgrand.net>wrote: > 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/ > > -- 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
