Re: Observations about new lazy branch
On Feb 28, 2009, at 6:25 PM, Mark Engelberg wrote: > > On Sat, Feb 28, 2009 at 6:09 AM, Rich Hickey > wrote: >> I think your fundamental hangup is on looking at (rest x) as a >> calculation/effect triggered by a consumer. (rest x) is logically >> just >> a slot lookup that obtains another seq. The laziness of that seq is >> its constructor's problem. > > Right, I'm aware that "rest" isn't an expensive operation. This was > meant to be for illustrative purposes. > > In my actual code, it's more like this: > > Imagine a permutation algorithm that works by storing the sequence in > a vector, and then permuting the various indices to get new sequences. > Simplifying considerably, with no laziness, the heart might look kind > of like this: > > (defn permutation-helper [v indices] > (cons (vector-in-order-of-indices v indices) > (permutations v > (do-complicated-transformation-of-indices-to-next-permutation > indices > > So where should the lazy-seq call go? > > (defn permutation-helper [v indices] > (lazy-seq (cons (vector-in-order-of-indices v indices) > (permutations v > (do-complicated-transformation-of-indices-to-next-permutation > indices) > > unnecessarily does the complicated-transform function when you call > first. > > (defn permutation-helper [v indices] > (cons (vector-in-order-of-indices v indices) > (lazy-seq (permutations v > (do-complicated-transformation-of-indices-to-next-permutation > indices) > > works better for this case, but unnecessarily does the > vector-in-order-of-indices at the beginning, and whenever you call > rest (not a hugely expensive operation, but let's pretend it is). > > (defn permutation-helper [v indices] > (lazy-seq (cons (vector-in-order-of-indices v indices) > (lazy-seq (permutations v > (do-complicated-transformation-of-indices-to-next-permutation > indices)) > > delays everything, but with a whole lot of overhead. That is a false economy. If do-complicated-transformation-of-indices- to-next-permutation is truly expensive it will dwarf the cost of lazy- seq. > > When you have a lot of local definitions that compute things before > the first call, and the helper function is embedded in something else, > deciding where to put lazy-seq becomes even more complicated. > > For the most part, I decided the odd-style worked best, and went with > something like this: > (defn permutation-helper [v indices] > (cons (vector-in-order-of-indices v indices) > (lazy-seq (permutations v > (do-complicated-transformation-of-indices-to-next-permutation > indices) > > (defn permutation [sequence] > (lazy-seq (permutation-helper (vec sequence) (initialize-indices))) > > thus delaying the setup and first element of the list, as well as all > the rests. This is all just pseudo-code and not the actual thing, but > it's enough to convey the idea. > There's no problem with this. Clojure features interop between concrete and lazy sequences. If you want to create a concrete seq whose rest is a lazy seq that's no problem, but you have to make sure that creating the first of that concrete seq doesn't force any other seqs. > My point is that lazy-seq gives you a lot more choices than lazy-cons, > but isolating the expensive part, rather than just blindly choosing > even laziness (which is the paradigm it's mainly geared for), can be > complicated. As I mentioned, rewriting filter to delay the call to > rest is an interesting exercise to see the challenge involved > (although I acknowledge that delaying rest isn't inherently useful > given that, like you said, sequence providers will ensure that.rest is > fast). > You are creating your own complexity by trying to avoid another lazy- seq call. There's no challenge. If you have code that produces a sequence, and you'd like to delay that work until the sequence is needed, simply wrap it in a call to lazy-seq. I think this still misses the critical distinction about lazy-seq vs lazy-cons. It's no longer about delaying the work of rest until it is called - it's about rest returning something that doesn't do work until it is needed, which may be never. Rich --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Re: Observations about new lazy branch
On Sat, Feb 28, 2009 at 6:09 AM, Rich Hickey wrote: > Clojure's fully-lazy now pretty much follows the "even" model > described by Wadler: > > How to add laziness to a strict language without even being odd: > > http://homepages.inf.ed.ac.uk/wadler/papers/lazyinstrict/lazyinstrict.ps OK, I just read the article. Section 4.3 is basically what I was talking about, where he talks about how, without the $ notation, the decrement in the call to countdown gets evaluated too soon. The postscript suggests that integrating something like the $ syntactic sugar does not conflict, and gives the best of both worlds. Maybe something like that could be added to Clojure to work with lazy-seq... --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Re: Observations about new lazy branch
On Sat, Feb 28, 2009 at 6:09 AM, Rich Hickey wrote: > I think your fundamental hangup is on looking at (rest x) as a > calculation/effect triggered by a consumer. (rest x) is logically just > a slot lookup that obtains another seq. The laziness of that seq is > its constructor's problem. Right, I'm aware that "rest" isn't an expensive operation. This was meant to be for illustrative purposes. In my actual code, it's more like this: Imagine a permutation algorithm that works by storing the sequence in a vector, and then permuting the various indices to get new sequences. Simplifying considerably, with no laziness, the heart might look kind of like this: (defn permutation-helper [v indices] (cons (vector-in-order-of-indices v indices) (permutations v (do-complicated-transformation-of-indices-to-next-permutation indices So where should the lazy-seq call go? (defn permutation-helper [v indices] (lazy-seq (cons (vector-in-order-of-indices v indices) (permutations v (do-complicated-transformation-of-indices-to-next-permutation indices) unnecessarily does the complicated-transform function when you call first. (defn permutation-helper [v indices] (cons (vector-in-order-of-indices v indices) (lazy-seq (permutations v (do-complicated-transformation-of-indices-to-next-permutation indices) works better for this case, but unnecessarily does the vector-in-order-of-indices at the beginning, and whenever you call rest (not a hugely expensive operation, but let's pretend it is). (defn permutation-helper [v indices] (lazy-seq (cons (vector-in-order-of-indices v indices) (lazy-seq (permutations v (do-complicated-transformation-of-indices-to-next-permutation indices)) delays everything, but with a whole lot of overhead. When you have a lot of local definitions that compute things before the first call, and the helper function is embedded in something else, deciding where to put lazy-seq becomes even more complicated. For the most part, I decided the odd-style worked best, and went with something like this: (defn permutation-helper [v indices] (cons (vector-in-order-of-indices v indices) (lazy-seq (permutations v (do-complicated-transformation-of-indices-to-next-permutation indices) (defn permutation [sequence] (lazy-seq (permutation-helper (vec sequence) (initialize-indices))) thus delaying the setup and first element of the list, as well as all the rests. This is all just pseudo-code and not the actual thing, but it's enough to convey the idea. My point is that lazy-seq gives you a lot more choices than lazy-cons, but isolating the expensive part, rather than just blindly choosing even laziness (which is the paradigm it's mainly geared for), can be complicated. As I mentioned, rewriting filter to delay the call to rest is an interesting exercise to see the challenge involved (although I acknowledge that delaying rest isn't inherently useful given that, like you said, sequence providers will ensure that.rest is fast). --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Re: Observations about new lazy branch
On Feb 27, 2009, at 11:10 PM, Mark Engelberg wrote: > > I just finished porting my combinatorics code to the new lazy > constructs, and I discovered some subtleties to using lazy-seq that > were not at first apparent. > > To begin with, consider the two versions of map: > The old way: > > (defn map > ([f coll] > (when (seq coll) > (lazy-cons (f (first coll)) (map f (rest coll) > > The new way: > > (defn map > ([f coll] > (lazy-seq >(when-let [s (seq coll)] > (cons (f (first s)) (map f (rest s)) > > Let's imagine that you are using map on a collection for which it is > very computation intensive to generate the rest, but trivial to > generate the first. > > I believe that in this case, you'd get more desirable behavior from > the old way than the new way. > > That's because the original lazy-cons kept the first and rest thunks > separate. It would force the first to get the rest, but it would NOT > force the rest to get at the first. So if you ask for the first, it > wouldn't do all the rest-generating computation. However, the new > version uses a delayed regular cons. So when you invoke the first of > the sequence, both arguments of cons are evaluated, so (map f (rest > s)) is called, and therefore (rest s) must be evaluated. > > If this is unclear, consider this: > (defn a [] (do (println "a") nil)) > (def s (lazy-seq (cons (a) (a > (first s) > > If you type this into the REPL, you'll see that the rest gets > evaluated when you ask for the first. > > To get the desired separation of first and rest evaluation with the > new lazy-seq function, you'd actually need to do something like this: > > (def lazier-map > (let [step (fn step [f coll] > (when-let [s (seq coll)] >(cons (f (first s)) (lazy-seq (step f (rest s))] >(fn [f coll] > (lazy-seq (step f coll) > > Basically, I've made a helper function which uses lazy-seq to delay > the evaluation of the rest, and then wrapped the call to the helper > function in a lazy-seq in order to delay evaluation of the very first > item. > > As a challenge, try to similarly fix up the version of filter provided > on the lazy page so that it fully separates the evaluation of first > and rest, thus protecting you against unnecessary evaluation if rest > is a slow operation on coll. I think you'll find that you end up with > two levels of indirection, and it's extremely difficult to write it > properly. Post your simplest solution here. > > Now in both these examples, you could argue that in all likelihood, > rest will be a fast operation. But I chose map here because everyone > knows the way we're supposed to write map, so it seemed like a good > choice to illustrate my concerns without having to explain how the > function works, etc. > > But this kind of problem does actually occur in practice. It appeared > in several places in the code I ported, because my code tends to do > most of the work within the arguments to the recursive call. I found > it difficult to reason about where to place the calls to lazy-seq in > order to achieve the separation I needed for evaluating the first and > the rest. I think I pulled it off correctly, but I've got to say I'm > not crazy about how, to do the "right thing", the code ends up looking > quite obfuscated. > > In summary, the new version gives you the most power to place the > delays where you want, but it's hard to get it right. > I think you've got the responsibilities wrong. If someone is making a "collection" for which first is cheap and rest expensive, and that doesn't build rest via a recursive call to a lazy-seq-bodied function (as do all the sequence fns), they could create it as follows: ... (cons cheap (lazy-seq (expensive))) All consumers of sequences presume each sequence is lazy if need be. Pushing the delaying of the rest part onto consumers is backwards. If you want a lazy collection, make one. Clojure's fully-lazy now pretty much follows the "even" model described by Wadler: How to add laziness to a strict language without even being odd: http://homepages.inf.ed.ac.uk/wadler/papers/lazyinstrict/lazyinstrict.ps with the enhancement of allowing interoperability between lazy and concrete sequences. I think your fundamental hangup is on looking at (rest x) as a calculation/effect triggered by a consumer. (rest x) is logically just a slot lookup that obtains another seq. The laziness of that seq is its constructor's problem. Rich --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Re: Observations about new lazy branch
Mark Engelberg a écrit : > Let's imagine that you are using map on a collection for which it is > very computation intensive to generate the rest, but trivial to > generate the first. > I don't think that's that simple: it depends on what is in the cons. For example, if the input seq is the result of mapping a computation intensive function (a common source of computation intensive seqs) then taking the rest of this seq is cheap because the rest itslef is a lazy-seq (as per map definition): user=> (def b (map #(do (println "mapping" %) %) (range 10))) #'user/b user=> (doall (take 3 (map inc b))) mapping 0 mapping 1 mapping 2 (1 2 3) When you really want to delay the computation of rest, you can replace (rest s) by (drop 1 s) but that holds on s (so does your lazier-map). Your lazier-map can be written: (defn lazier-map ([f coll] (lazy-seq (when-let [s (seq coll)] (cons (f (first s)) (lazier-map f (drop 1 s)) Hope this helps Christophe -- Professional: http://cgrand.net/ (fr) On Clojure: http://clj-me.blogspot.com/ (en) --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Re: Observations about new lazy branch
> I'm not sure which old-map you mean here. If you mean the old > lazy-cons version, using your above macro, this will have too many > lazy-seq calls. Yeah, you're right ... I managed to confuse myself. Off the top of my head I can't think of a nicer way to write lazier- map than what you've got. Hmmm... -Jason --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Re: Observations about new lazy branch
On Fri, Feb 27, 2009 at 8:33 PM, Jason Wolfe wrote: > > If lazy-cons makes your life easier, I think you can still have > something very much like it: > > (defmacro lazy-cons [x s] > `(lazy-seq (cons ~x (lazy-seq ~s As you pointed out, in most contexts, this will double the number of lazy-seq calls, which will really hurt performance. > > If you're interested in perf, you'd just have to write your code a bit > carefully to avoid double lazy-seq'ing the rests: > > (defn map [f coll] > (lazy-seq > (old-map [f coll]))) > > where old-map is the old version of map (modified to cache the call to > "seq"?). Does this make sense? I'm not sure which old-map you mean here. If you mean the old lazy-cons version, using your above macro, this will have too many lazy-seq calls. --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Re: Observations about new lazy branch
If lazy-cons makes your life easier, I think you can still have something very much like it: (defmacro lazy-cons [x s] `(lazy-seq (cons ~x (lazy-seq ~s If you're interested in perf, you'd just have to write your code a bit carefully to avoid double lazy-seq'ing the rests: (defn map [f coll] (lazy-seq (old-map [f coll]))) where old-map is the old version of map (modified to cache the call to "seq"?). Does this make sense? -Jason P.S. thanks for updating combinatorics, I've been waiting for that. On Feb 27, 8:10 pm, Mark Engelberg wrote: > I just finished porting my combinatorics code to the new lazy > constructs, and I discovered some subtleties to using lazy-seq that > were not at first apparent. > > To begin with, consider the two versions of map: > The old way: > > (defn map > ([f coll] > (when (seq coll) > (lazy-cons (f (first coll)) (map f (rest coll) > > The new way: > > (defn map > ([f coll] > (lazy-seq > (when-let [s (seq coll)] > (cons (f (first s)) (map f (rest s)) > > Let's imagine that you are using map on a collection for which it is > very computation intensive to generate the rest, but trivial to > generate the first. > > I believe that in this case, you'd get more desirable behavior from > the old way than the new way. > > That's because the original lazy-cons kept the first and rest thunks > separate. It would force the first to get the rest, but it would NOT > force the rest to get at the first. So if you ask for the first, it > wouldn't do all the rest-generating computation. However, the new > version uses a delayed regular cons. So when you invoke the first of > the sequence, both arguments of cons are evaluated, so (map f (rest > s)) is called, and therefore (rest s) must be evaluated. > > If this is unclear, consider this: > (defn a [] (do (println "a") nil)) > (def s (lazy-seq (cons (a) (a > (first s) > > If you type this into the REPL, you'll see that the rest gets > evaluated when you ask for the first. > > To get the desired separation of first and rest evaluation with the > new lazy-seq function, you'd actually need to do something like this: > > (def lazier-map > (let [step (fn step [f coll] > (when-let [s (seq coll)] > (cons (f (first s)) (lazy-seq (step f (rest s))] > (fn [f coll] > (lazy-seq (step f coll) > > Basically, I've made a helper function which uses lazy-seq to delay > the evaluation of the rest, and then wrapped the call to the helper > function in a lazy-seq in order to delay evaluation of the very first > item. > > As a challenge, try to similarly fix up the version of filter provided > on the lazy page so that it fully separates the evaluation of first > and rest, thus protecting you against unnecessary evaluation if rest > is a slow operation on coll. I think you'll find that you end up with > two levels of indirection, and it's extremely difficult to write it > properly. Post your simplest solution here. > > Now in both these examples, you could argue that in all likelihood, > rest will be a fast operation. But I chose map here because everyone > knows the way we're supposed to write map, so it seemed like a good > choice to illustrate my concerns without having to explain how the > function works, etc. > > But this kind of problem does actually occur in practice. It appeared > in several places in the code I ported, because my code tends to do > most of the work within the arguments to the recursive call. I found > it difficult to reason about where to place the calls to lazy-seq in > order to achieve the separation I needed for evaluating the first and > the rest. I think I pulled it off correctly, but I've got to say I'm > not crazy about how, to do the "right thing", the code ends up looking > quite obfuscated. > > In summary, the new version gives you the most power to place the > delays where you want, but it's hard to get it right. --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
