Re: (iterate inc 2) vs (drop 2 (range)) in corecursion

237 views
Skip to first unread message

Christophe Grand

unread,
Nov 28, 2012, 10:42:32 AM11/28/12
to clojure
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#L59 especially 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 <umue...@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 clo...@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+u...@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/

Christophe Grand

unread,
Nov 28, 2012, 10:49:15 AM11/28/12
to clojure
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 :-)

Ulrich

unread,
Nov 28, 2012, 11:24:45 AM11/28/12
to clo...@googlegroups.com, chris...@cgrand.net


Am Mittwoch, 28. November 2012 16:42:32 UTC+1 schrieb Christophe Grand:
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

...

Salut Christophe,

thanks first for pointing out to the clojure source for tracking down problems, I hadn't thought about that yet.
Considering base case, in fact, the first code I started off with, was something similiar with starting values 2,3,5 :

(def primes
  (concat
    '(2 3 5)
    (filter
      (fn[n]

        (every?
          #(pos? (mod n %))
          (take-while #(<=(*%%)n) primes)
          )
        )
      (drop 6 (range))
      )
    )  
  )

What works. But with '(2,3) (or '(2) like you suggested) this doesn't work any more, as 25 is included in the first "batch" (of the so called chunked sequence) which is only tested against the starting value of primes.

Then I found the solution with "iterate" and then further reduced starting values to '(2) and then to '() what worked as well,
as every? returns true for empty sequences, what is right from a logical point of view too. And with '() as start even the concat wasn't necessary any more. So this was no luck, but intention :)

Anyway, the question that still remains is, how one could "rechunk" a chunked sequence?

Ulrich.
 
 

Ulrich

unread,
Nov 28, 2012, 7:11:24 PM11/28/12
to clo...@googlegroups.com

... so the main problem seems to be chunked vs. unchunked sequences in corecursion.
I read a bit into "chunked sequences" and so far it seems that a sequence is either chunked with size 32 or unchunked. So a "rechunk" of variable size seems of no use. Instead I found an "unchunk" at stackoverflow:

(def unchunk #(lazy-seq(when(seq%)(cons(first%)(unchunk(rest%))))))

Now the original code posted at top also works with "(drop 2 (unchunk(range)))".
Further I found following remark by RichHickey in changes.txt for Clojure 1.1
(https://github.com/richhickey/clojure/blob/68aa96d832703f98f80b18cecc877e3b93bc5d26/changes.txt#L85)
Consumption of chunked-seqs as normal seqs should be completely transparent. However,
note that some sequence processing will occur up to 32 elements at a time. This could
matter to you if you are relying on full laziness to preclude the generation of any
non-consumed results. An interface to force single-item consumption of chunked seqs is
still being designed. Please share any use cases where chunked processing has resulted
in behavioral differences that matter to you on the Clojure google group.
Now, this is a good such example, where chunking leads to behavioral error.
Has the afore mentioned interface for forced single-item consumption meanwhile been created?

Ulrich

Christophe Grand

unread,
Nov 29, 2012, 3:21:00 AM11/29/12
to clojure
On Wed, Nov 28, 2012 at 5:24 PM, Ulrich <umue...@c007.de> wrote:
Then I found the solution with "iterate" and then further reduced starting values to '(2) and then to '() what worked as well,
as every? returns true for empty sequences, what is right from a logical point of view too. And with '() as start even the concat wasn't necessary any more. So this was no luck, but intention :)

It was your intention then but based on a false premise: a seq is immutable and as such can't be both empty and non-empty depending how/when you access it. There is no fix-point semantics to justify this behaviour. So to me it's a bug.

With '(2 3 5) it worked because it was enough to remove all non primes from the first chunk (< 32).

With the patch I propose I get:
* without a base case for recursion, I get an exception, chunked or not.
user=> (def primes
    (filter
      (fn isprime[n]

        (every?
          #(pos? (mod n %))
          (take-while #(<=(* % %)n) primes)))
      (drop 2 (range))))

#'user/primes
user=> (take 50 primes)
RuntimeException Recursive seq realization  clojure.lang.LazySeq.sval (LazySeq.java:64)
user=> (def primes
    (filter
      (fn isprime[n]

        (every?
          #(pos? (mod n %))
          (take-while #(<=(* % %)n) primes)))
      (iterate inc 2)))
#'user/primes
user=> (take 50 primes)
RuntimeException Recursive seq realization  clojure.lang.LazySeq.sval (LazySeq.java:64)

* With a base case however I get either the right result or an exception. Even if the chunkiness of the seq still changes the outcome, it's an improvement over the current situation where one gets either the right result or an incorrect result. Better to fail than to err.
user=> (def primes
  (cons 2
    (filter
      (fn isprime[n]

        (every?
          #(pos? (mod n %))
          (take-while #(<=(* % %)n) primes)))
      (iterate inc 3))))
user=> (take 50 primes)
(2 3 5 7 11 13 17 19 23 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 199 211 223 227 229)
user=> (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)
RuntimeException Recursive seq realization  clojure.lang.LazySeq.sval (LazySeq.java:64)


On Thu, Nov 29, 2012 at 1:11 AM, Ulrich <umue...@c007.de> wrote:
Has the afore mentioned interface for forced single-item consumption meanwhile been created?

Afaik, no.


Christophe

Ulrich

unread,
Nov 29, 2012, 5:20:34 PM11/29/12
to clo...@googlegroups.com

You are right demanding a base case. I don't deny that any more. As stated above, me as a beginner, experimenting for experience, took the well-known Fibonacci corecursion (with base case) as guidance in setting my first prime corecursion code with range, and then reduced the base case from '(2 3 5) to '(2 3) realizing that it didn't work any longer. Then finding that with "iterate" it did. Then further reduced to '(2) and '(), finding that it still worked. What clojure version are you using btw to get the exceptions? I never got those exceptions but the correct result (tried with 1.2, 1.3 and 1.4). So thought with '() everything is still fine, so thought I can omit the whole concat. This was seconded from a mathematical point of view: the only subset S from X=[2,3,4,...] where each n is included, if it has no divisor in {m in S: m*m<=n} is THE sequence of primes. But of course clojure won't be able (yet :) ) to logically deduce this relation simply by evaluating the corecursion code. And simple calculation run into problems while evaluating "take-while". With a base case "take-while" will return properly.

Now, that's clear, anyway, the main point was and still is,
that the code (the version corrected with a base case)


(def primes
  (cons
    2
    (filter
      (fn[n]

        (every?
          #(pos? (mod n %))
          (take-while #(<=(*%%)n) primes)
          )
        )
      (drop 3 (range))
      )
    )
  )


SHOULD imho properly work in a proper clojure implementation,
n'est ce pas?

If it doesn't because of internal!!! representation
of the involved sequences,
be it chunked or something else,
than this is a huge pitfall,
which might be hard to detect
in more complicated structures.

Now should we consider this a clojure bug?

Ulrich.

Christophe Grand

unread,
Nov 30, 2012, 5:20:29 AM11/30/12
to clojure
Hallo,


On Thu, Nov 29, 2012 at 11:20 PM, Ulrich <umue...@c007.de> wrote:
Now should we consider this a clojure bug?
What clojure version are you using btw to get the exceptions?

master from Github with my patch to CLJ-457 applied :-)

Now, that's clear, anyway, the main point was and still is,
that the code (the version corrected with a base case)

(def primes
  (cons
    2
    (filter
      (fn[n]
        (every?
          #(pos? (mod n %))
          (take-while #(<=(*%%)n) primes)
          )
        )
      (drop 3 (range))
      )
    )
  )


SHOULD imho properly work in a proper clojure implementation,
n'est ce pas?

Genau and it certainly worked in Clojure 1.0 (chunked sequences were introduced in 1.1).
 
So, with my patch applied, this code still does not work but at least we get an exception rather than an incorrect result. Not perfect but, in my opinion, a step towards correctness (and it should also break some rare code ("recursive" chunked seqs only) which happens to work by luck).

Christophe

Christophe Grand

unread,
Dec 3, 2012, 2:21:19 AM12/3/12
to maclo, clojure
Hi maclo,

Your code assume there is two "primes" sequences: the result and the one being constructed. But there's only one and which is infinite.
You define your sequence as being (cons 2 something) and computing "something" requires evaluating (every? #(pos? (mod 3 %)) (cons 2 something))
since (pos? (mod 3 2)) is true, every? continues processing the seq and tries to evaluate (every? #(pos? (mod 3 %)) something).
So computing "something" requires knowing "something"!

The take-while is useful in that it reduces the scope of every to primes already computed.

Your code works only because of a bug/unspecified behaviour which makes the recursive reference of the sequence to be considered nil.

hth,

Christophe


On Sun, Dec 2, 2012 at 4:30 PM, maclo <maclo...@gmail.com> wrote:
Hi


 user=> (def primes
  (cons 2
    (filter
      (fn isprime[n]

        (every?
          #(pos? (mod n %))
          (take-while #(<=(* % %)n) primes)))
      (iterate inc 3))))
user=> (take 50 primes)
(2 3 5 7 11 13 17 19 23 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 199 211 223 227 229)
 
 Is it really necessary to call 'take-while' ? The version without it


(def primes
  (cons 2
    (filter
      (fn isprime? [n]
        (every? #(pos? (mod n %)) primes))
      (iterate inc 3))))

works for me as well. Is it safe to use this version or is using 'take-while' for some reason necessary ?

maclo
Reply all
Reply to author
Forward
0 new messages