Clojure

lazy recursive definition giving incorrect results

Details

  • Type: Defect Defect
  • Status: Open Open
  • Priority: Major Major
  • Resolution: Unresolved
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
    None
  • Patch:
    Code and Test

Description

If you define a global data var in terms of a lazy sequence referring to that same var, you can get different results depending on the chunkiness of laziness of the functions being used to build the collection.

Clojure's lazy sequences don't promise to support this, but they shouldn't return wrong answers. In the example given in http://groups.google.com/group/clojure/browse_thread/thread/1c342fad8461602d (and repeated below), Clojure should not return bad data. An error message would be good, and even an infinite loop would be more reasonable than the current behavior.

(Similar issue reported here: https://groups.google.com/d/topic/clojure/yD941fIxhyE/discussion)

(def nums (drop 2 (range)))
(def primes (cons (first nums)
             (lazy-seq (->>
               (rest nums)
               (remove
                 (fn [x]
                   (let [dividors (take-while #(<= (* % %) x)
primes)]
                     (println (str "primes = " primes))
                     (some #(= 0 (rem x %)) dividors))))))))
(take 5 primes)

It prints out:
(primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
2 3 5 7 9)
  1. CLJ-457-2.diff
    03/Dec/12 11:18 AM
    3 kB
    Christophe Grand
  2. clj-457-3.diff
    23/Nov/13 12:35 AM
    3 kB
    Andy Fingerhut

Activity

Hide
Assembla Importer added a comment -
Show
Assembla Importer added a comment - Converted from http://www.assembla.com/spaces/clojure/tickets/457
Hide
Aaron Bedra added a comment -

Stu and Rich talked about making this an error, but it would break some existing code to do so.

Show
Aaron Bedra added a comment - Stu and Rich talked about making this an error, but it would break some existing code to do so.
Hide
Rich Hickey added a comment -

Is there a specific question on this?

Show
Rich Hickey added a comment - Is there a specific question on this?
Hide
Aaron Bedra added a comment -

Stu, you and I went over this but I can't remember exactly what the question was here.

Show
Aaron Bedra added a comment - Stu, you and I went over this but I can't remember exactly what the question was here.
Hide
Christophe Grand added a comment -

Tentative patch attached.
Have you an example of existing code which is broken by such a patch (as mention by Aaron Bedra)?

Show
Christophe Grand added a comment - Tentative patch attached. Have you an example of existing code which is broken by such a patch (as mention by Aaron Bedra)?
Hide
Rich Hickey added a comment -

The patch intends to do what? We have only a problem description and code. Please enumerate the plan rather than make us decipher the patch.

As a first principle, I don't want Clojure to promise that such recursively defined values are possible.

Show
Rich Hickey added a comment - The patch intends to do what? We have only a problem description and code. Please enumerate the plan rather than make us decipher the patch. As a first principle, I don't want Clojure to promise that such recursively defined values are possible.
Hide
Christophe Grand added a comment - - edited

The proposal here is to catch recursive seq realization (ie when computing the body of a lazy-seq attempts to access the same seq) and throw an exception.

Currently when such a case happens, the recursive access to the seq returns nil. This results in incorrect code seemingly working but producing incorrect results or even incorrect code producing correct results out of luck (see https://groups.google.com/d/topic/clojure/yD941fIxhyE/discussion for such an example).

So this patch moves around the modification to the LazySeq state (f, sv and s fields) before all potentially recursive method call (.sval in the while of .seq and .invoke in .sval) so that, upon reentrance, the state of the LazySeq is coherent and able to convey the fact the seq is already being computed.

Currently a recursive call may find f and sv cleared and concludes the computation is done and the result is in s despite s being unaffected yet.

Currently:

State f sv s
Unrealized not null null null
Realized null null anything
Being realized/recursive call from fn.invoke not null null null
Being realized/recursive call from ls.sval null null null

Note that "Being realized" states overlap with Unrealized or Realized.
(NB: "anything" includes null)

With the patch:

State f sv s
Unrealized not null null null
Realized null null anything but this
Being realized null null this
Show
Christophe Grand added a comment - - edited The proposal here is to catch recursive seq realization (ie when computing the body of a lazy-seq attempts to access the same seq) and throw an exception. Currently when such a case happens, the recursive access to the seq returns nil. This results in incorrect code seemingly working but producing incorrect results or even incorrect code producing correct results out of luck (see https://groups.google.com/d/topic/clojure/yD941fIxhyE/discussion for such an example). So this patch moves around the modification to the LazySeq state (f, sv and s fields) before all potentially recursive method call (.sval in the while of .seq and .invoke in .sval) so that, upon reentrance, the state of the LazySeq is coherent and able to convey the fact the seq is already being computed. Currently a recursive call may find f and sv cleared and concludes the computation is done and the result is in s despite s being unaffected yet. Currently:
State f sv s
Unrealized not null null null
Realized null null anything
Being realized/recursive call from fn.invoke not null null null
Being realized/recursive call from ls.sval null null null
Note that "Being realized" states overlap with Unrealized or Realized. (NB: "anything" includes null) With the patch:
State f sv s
Unrealized not null null null
Realized null null anything but this
Being realized null null this
Hide
Andy Fingerhut added a comment -

That last comment, Christophe, goes a long way to explaining the idea to me, at least. Any chance comments with similar content could be added as part of the patch?

Show
Andy Fingerhut added a comment - That last comment, Christophe, goes a long way to explaining the idea to me, at least. Any chance comments with similar content could be added as part of the patch?
Hide
Christophe Grand added a comment - - edited

New patch with a comment explaining the expected states.
Note: I tidied the states table up.

// Before calling user code (f.invoke() in sval and, indirectly,
// ((LazySeq)ls).sval() in seq -- and even RT.seq() in seq), ensure that 
// the LazySeq state is in one of these states:
//
// State            f          sv
// ================================
// Unrealized       not null   null
// Realized         null       null
// Being realized   null       this

CLJ-1119 is also fixed by this patch.

Show
Christophe Grand added a comment - - edited New patch with a comment explaining the expected states. Note: I tidied the states table up.
// Before calling user code (f.invoke() in sval and, indirectly,
// ((LazySeq)ls).sval() in seq -- and even RT.seq() in seq), ensure that 
// the LazySeq state is in one of these states:
//
// State            f          sv
// ================================
// Unrealized       not null   null
// Realized         null       null
// Being realized   null       this
CLJ-1119 is also fixed by this patch.
Hide
Andy Fingerhut added a comment -

Patch clj-457-3.diff is identical to Christophe's CLJ-457-2.diff, except it has been updated to no longer conflict with the commit made for CLJ-949 on Nov 22, 2013, which basically removed the try/catch in method sval(). It passes tests, and I don't see anything wrong with it, but it would be good if Christophe could give it a look, too.

Show
Andy Fingerhut added a comment - Patch clj-457-3.diff is identical to Christophe's CLJ-457-2.diff, except it has been updated to no longer conflict with the commit made for CLJ-949 on Nov 22, 2013, which basically removed the try/catch in method sval(). It passes tests, and I don't see anything wrong with it, but it would be good if Christophe could give it a look, too.

People

Vote (0)
Watch (4)

Dates

  • Created:
    Updated: