Critiques of "my-flatten" which uses CPS
I'm very new to continuation passing style (CPS), and as part of the learning process I've done a CPS version of a "flatten" function. Ie, it does the same thing as the standard clojure "flatten", but is implemented using a recursive local CPS helper function. I'm interested in comments / critiques on what I've done. Here it is... (defn my-flatten [xs] (letfn [(my-flatten-cps [xs k] (if (nil? xs) (k '()) (let [x (first xs), ys (next xs)] (if (sequential? x) (recur ys (fn [v] (my-flatten-cps (seq x) (fn [w] (k (concat w v)) (recur ys (fn [v] (k (conj v x] (my-flatten-cps (seq xs) identity))) I'm relatively inexperienced with clojure, so please feel free to suggest improvements to my clojure code. But what I'm most interested in is understanding CPS better and about how it interacts with Clojure and with "recur". As you can see, my-flatten-cps uses recur nicely to traverse at a breadth level. But as we sink down into depth, I've done an actual non-recur call to my-flatten-cps. I presume I can't do a recur here instead (because it would attempt to jump to the most immediate fn??) - is this correct? Is there any way around this? (As I write this, the word "trampoline" comes to mind - some videos I've watched speak of this - but not sure how this would work and what efficiency trade-offs would be involved.) The other things is... is it so bad that it is not fully using recur - maybe using a bit of stack is okay?? Thanks, Mark. -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Critiques of "my-flatten" which uses CPS
Yes, here's the trampolined version which won't stack overflow: (defn my-flatten [xs] (letfn [(my-flatten-cps [xs k] (if (nil? xs) (k '()) (let [x (first xs), ys (next xs)] (if (sequential? x) (recur ys (fn [v] (fn [] (my-flatten-cps (seq x) (fn [w] (fn [] (k (doall (concat w v) (recur ys (fn [v] #(k (conj v x] (trampoline my-flatten-cps (seq xs) identity))) Basically, you just wrap the body of each continuation in a function of no arguments, and call the recursive function with trampoline. Another thing you have to do is wrap the concat in a doall, otherwise you'll get a stack overflow when the deeply nested lazy concatenation is realized. On Tue, Jul 15, 2014 at 12:13 AM, Mark P wrote: > I'm very new to continuation passing style (CPS), and as part of the > learning process I've done a CPS version of a "flatten" function. Ie, it > does the same thing as the standard clojure "flatten", but is implemented > using a recursive local CPS helper function. I'm interested in comments / > critiques on what I've done. > > Here it is... > > (defn my-flatten > [xs] > (letfn [(my-flatten-cps [xs k] > (if (nil? xs) > (k '()) > (let [x (first xs), ys (next xs)] > (if (sequential? x) > (recur ys (fn [v] (my-flatten-cps (seq x) (fn [w] (k > (concat w v)) > (recur ys (fn [v] (k (conj v x] > (my-flatten-cps (seq xs) identity))) > > I'm relatively inexperienced with clojure, so please feel free to suggest > improvements to my clojure code. > > But what I'm most interested in is understanding CPS better and about how > it interacts with Clojure and with "recur". As you can see, my-flatten-cps > uses recur nicely to traverse at a breadth level. But as we sink down into > depth, I've done an actual non-recur call to my-flatten-cps. I presume I > can't do a recur here instead (because it would attempt to jump to the most > immediate fn??) - is this correct? > > Is there any way around this? (As I write this, the word "trampoline" > comes to mind - some videos I've watched speak of this - but not sure how > this would work and what efficiency trade-offs would be involved.) > > The other things is... is it so bad that it is not fully using recur - > maybe using a bit of stack is okay?? > > Thanks, > > Mark. > > -- > 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 > --- > You received this message because you are subscribed to the Google Groups > "Clojure" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to clojure+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Critiques of "my-flatten" which uses CPS
I haven't really used CPS myself, but I think you should be able to use the trampoline function to clean up your code. http://clojuredocs.org/clojure_core/clojure.core/trampoline Jonathan On 15 July 2014 09:13, Mark P wrote: > I'm very new to continuation passing style (CPS), and as part of the > learning process I've done a CPS version of a "flatten" function. Ie, it > does the same thing as the standard clojure "flatten", but is implemented > using a recursive local CPS helper function. I'm interested in comments / > critiques on what I've done. > > Here it is... > > (defn my-flatten > [xs] > (letfn [(my-flatten-cps [xs k] > (if (nil? xs) > (k '()) > (let [x (first xs), ys (next xs)] > (if (sequential? x) > (recur ys (fn [v] (my-flatten-cps (seq x) (fn [w] (k > (concat w v)) > (recur ys (fn [v] (k (conj v x] > (my-flatten-cps (seq xs) identity))) > > I'm relatively inexperienced with clojure, so please feel free to suggest > improvements to my clojure code. > > But what I'm most interested in is understanding CPS better and about how > it interacts with Clojure and with "recur". As you can see, my-flatten-cps > uses recur nicely to traverse at a breadth level. But as we sink down into > depth, I've done an actual non-recur call to my-flatten-cps. I presume I > can't do a recur here instead (because it would attempt to jump to the most > immediate fn??) - is this correct? > > Is there any way around this? (As I write this, the word "trampoline" > comes to mind - some videos I've watched speak of this - but not sure how > this would work and what efficiency trade-offs would be involved.) > > The other things is... is it so bad that it is not fully using recur - > maybe using a bit of stack is okay?? > > Thanks, > > Mark. > > -- > 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 > --- > You received this message because you are subscribed to the Google Groups > "Clojure" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to clojure+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Critiques of "my-flatten" which uses CPS
Thanks for explaining how one creates a trampolined version from the cps version! This makes sense. Thanks also for alerting me to potential issues with the concat laziness. From a code efficiency point of view, producing a lazy something and then immediately evaluating it is inefficient. It is better to use a strict version of the something in the first place. Does Clojure provide strict versions of things like concat, or would I need to roll-my-own? Thinking again of efficiency... I had a go at doing an accumulator-passing-style (APS) version of flatten. Here it is... (defn my-apsbased-flatten [xs] (letfn [(my-flatten-aps [xs avec] (if (nil? xs) avec (let [x (first xs), ys (next xs)] (if (sequential? x) (recur ys (into avec (my-flatten-aps (seq x) '[]))) (recur ys (conj avec x))] (seq (my-flatten-aps (seq xs) '[] This is more efficient (I think) than my earlier cps-based flatten. But it has the problem again of using the stack via the non-recur call to my-flatten-aps. I'm wondering if it's somehow possible to modify this aps implementation to also use trampolining? Alternatively, maybe there's a combination aps-cps variation which can be trampolined?? I've had a bit of a go at this and so far can't see how to do it. Perhaps not, as APS seems to do pre-calculation whereas CPS seems to do post-calculation? But I can't help thinking that there must be a more efficient trampolined version of flatten that utilizes the structure of the "flatten problem" more, like APS does? Cheers, Mark. On Tuesday, 15 July 2014 19:25:26 UTC+9:30, puzzler wrote: > > Yes, here's the trampolined version which won't stack overflow: > > (defn my-flatten > [xs] > (letfn [(my-flatten-cps [xs k] > (if (nil? xs) > (k '()) > (let [x (first xs), ys (next xs)] > (if (sequential? x) > (recur ys (fn [v] (fn [] (my-flatten-cps (seq x) (fn [w] > (fn [] (k (doall (concat w v) > (recur ys (fn [v] #(k (conj v x] > (trampoline my-flatten-cps (seq xs) identity))) > > Basically, you just wrap the body of each continuation in a function of no > arguments, and call the recursive function with trampoline. > > Another thing you have to do is wrap the concat in a doall, otherwise > you'll get a stack overflow when the deeply nested lazy concatenation is > realized. > > > On Tue, Jul 15, 2014 at 12:13 AM, Mark P > > wrote: > >> I'm very new to continuation passing style (CPS), and as part of the >> learning process I've done a CPS version of a "flatten" function. Ie, it >> does the same thing as the standard clojure "flatten", but is implemented >> using a recursive local CPS helper function. I'm interested in comments / >> critiques on what I've done. >> >> Here it is... >> >> (defn my-flatten >> [xs] >> (letfn [(my-flatten-cps [xs k] >> (if (nil? xs) >> (k '()) >> (let [x (first xs), ys (next xs)] >> (if (sequential? x) >> (recur ys (fn [v] (my-flatten-cps (seq x) (fn [w] (k >> (concat w v)) >> (recur ys (fn [v] (k (conj v x] >> (my-flatten-cps (seq xs) identity))) >> >> I'm relatively inexperienced with clojure, so please feel free to suggest >> improvements to my clojure code. >> >> But what I'm most interested in is understanding CPS better and about how >> it interacts with Clojure and with "recur". As you can see, my-flatten-cps >> uses recur nicely to traverse at a breadth level. But as we sink down into >> depth, I've done an actual non-recur call to my-flatten-cps. I presume I >> can't do a recur here instead (because it would attempt to jump to the most >> immediate fn??) - is this correct? >> >> Is there any way around this? (As I write this, the word "trampoline" >> comes to mind - some videos I've watched speak of this - but not sure how >> this would work and what efficiency trade-offs would be involved.) >> >> The other things is... is it so bad that it is not fully using recur - >> maybe using a bit of stack is okay?? >> >> Thanks, >> >> Mark. >> >> -- >> 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 >> --- >> You received this message because you are subscribed to the Google Groups >> "Clojure" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to clojure+u...@googlegroups.com . >> For more options, visit https://group
Re: Critiques of "my-flatten" which uses CPS
To avoid the doall-concat, you'd just have the base case return [] (btw, you don't need the apostrophe for vectors or for the empty list), and use `into` rather than `concat`. If you're looking for something that exploits the structure of flatten and uses an accumulator, you could do this: (defn my-flatten [xs] (letfn [(my-flatten-aps [xs avec] (if (empty? xs) avec (let [x (first xs), ys (rest xs)] (if (sequential? x) (if (seq x) (recur (cons (first x) (cons (rest x) ys)) avec) (recur ys avec)) (recur ys (conj avec x))] (my-flatten-aps xs []))) The idea is that if you have a non-empty sequence in the first position, you pull out its first element and stick it on the front of the overall sequence. So ((1 2 3) 4 5) will recur as (1 (2 3) 4 5). The next go around will pick up that 1 is atomic and add it to the accumulator, and so on. If you have an empty sequence in the first position, you just skip over it entirely. -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Critiques of "my-flatten" which uses CPS
It's worth understanding how to go back and forth between accumulator-style and a lazy construction. You can convert the above non-lazy accumulator version into a similar version that is lazy but has no risk of stack overflow in the realization of that lazy flattened list: (defn my-flatten [xs] (if (empty? xs) () (let [x (first xs), ys (rest xs)] (if (sequential? x) (if (seq x) (recur (cons (first x) (cons (rest x) ys))) (recur ys)) (lazy-seq (cons x (my-flatten ys))) Basically, you just get rid of the accumulator, and in the place where you would have conj'd in the next atomic element, you just build the lazy sequence. -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Critiques of "my-flatten" which uses CPS
Interesting - thank you! Good to know about "into" as a way to achieve a non-lazy concat - in conjunction with a vector. I like your accumulator version - morphing the structure of the input as you go to achieve the desired result. I've come up with another version, that passes through both a "result so far" accumulator and a "still to be computed" stack. It is very much non-lazy, but that's okay in some applications (a performance feature even!). Here it is... (defn my-accandstackbased-flatten [xs] (letfn [(flatten-accandstack [xs accvec stackvec] (if (empty? xs) (if (empty? stackvec) accvec (recur (peek stackvec) accvec (pop stackvec))) (let [x (first xs), ys (next xs)] (if (sequential? x) (recur x accvec (conj stackvec ys)) (recur ys (conj accvec x) stackvec)] (seq (flatten-accandstack xs [] [] This has nice recur behaviour and doesn't mess too much with the structure of the input nested lists. In the case of flatten, retaining structure is not important (as you nicely illustrated), but there are generalizations of this kind of function where retaining structure becomes more important. Now here's the thing... In the above, my stackvec is sort of like a continuation. It contains a stack of computation to be performed later on. That sounds very much like a continuation to me (though I am still in the process of getting my head around this stuff). So I've thought, surely I could write an "acc and cps" version of my-flatten? Here is what I came up with... (defn my-accandcpsbased-flatten [xs] (letfn [(flatten-accandcps [xs accvec k] (if (empty? xs) (k accvec) (let [x (first xs), ys (next xs)] (if (sequential? x) (recur x accvec (fn [v] (flatten-accandcps ys [] (fn [w] (k (into v w)) (recur ys (conj accvec x) k)] (seq (flatten-accandcps xs [] identity And I could do the trick you showed me with thunks and a trampoline, if I wanted to make it completely stack-avoiding. What does this show? I'm not sure. Presumably the acc and stack version is the most efficient as it uses recur everywhere? The structure of the continuation I pass in with the "acc and cps" version is very similar in complexity to the continuation I passed as part of my original cps implementation. So where's the gain? I guess the inclusion of an accvec means that continuations are generated less frequently so that the overall size and execution time of continuations is smaller? And it is an improvement over my earlier aps version that used only an acc vector - because this version has everything in tail-call position and is amenable to trampolining. Is this attempt at analysis reasonable? Is there anything else worth observing etc? Presumably I could make the "acc and cps" above more lazy using concat, cons and lazy-seq. I'd need to think about how easy/hard it would be to make my "acc and stack" version as lazy. Thanks again for your helpful comments and examples. -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Critiques of "my-flatten" which uses CPS
Right. Overall lessons: In recursion, the call stack automatically keeps track of what still needs to be done. In Clojure, due to Java, the stack is significantly more limited than heap, so this can be a real limitation. To break free of that limitation, you must somehow keep track of what still needs to be done in a heap-allocated data structure. CPS is one way to do that, effectively using closures wrapping other closures to create a "stack" of things that need to be done. Unfortunately, CPS is usually not very useful in Clojure -- when the closures are executed you are again using Clojure's severely-limited stack to perform that execution, so you'll blow the stack then. So the better solution is to think explicitly about what kind of "remains to be done" information needs to be tracked, and just track that information in a heap-allocated data structure. So CPS is a good starting point for reasoning about a recursion problem, but ultimately, you want to convert it into some sort of accumulator. I'm not sure I see the utility of the CPS/accumulator hybrid model you proposed. I think the goal is to get away from CPS once you understand what is going on behind the scenes. I saw an interesting analysis once of the factorial function, starting from the recursive formulation of the function, then doing CPS, then doing an analysis of exactly what values need to be tracked by the continuations, and then eliminating the actual continuations. What you are left with is a version of the function that begins by building a heap-allocated structure of all the numbers from 1 to n, and then just reduces them with multiplication, which is basically what you'd expect the concise version of the function to be. I think that's a great example to keep in mind. On Wed, Jul 16, 2014 at 8:39 PM, Mark P wrote: > Interesting - thank you! > > Good to know about "into" as a way to achieve a non-lazy concat - in > conjunction with a vector. > > I like your accumulator version - morphing the structure of the input as > you go to achieve the desired result. > > I've come up with another version, that passes through both a "result so > far" accumulator and a "still to be computed" stack. It is very much > non-lazy, but that's okay in some applications (a performance feature > even!). Here it is... > > (defn my-accandstackbased-flatten > [xs] > (letfn [(flatten-accandstack [xs accvec stackvec] > (if (empty? xs) > (if (empty? stackvec) > accvec > (recur (peek stackvec) accvec (pop stackvec))) > (let [x (first xs), ys (next xs)] > (if (sequential? x) > (recur x accvec (conj stackvec ys)) > (recur ys (conj accvec x) stackvec)] > (seq (flatten-accandstack xs [] [] > > This has nice recur behaviour and doesn't mess too much with the structure > of the input nested lists. In the case of flatten, retaining structure is > not important (as you nicely illustrated), but there are generalizations of > this kind of function where retaining structure becomes more important. > > Now here's the thing... In the above, my stackvec is sort of like a > continuation. It contains a stack of computation to be performed later on. > That sounds very much like a continuation to me (though I am still in the > process of getting my head around this stuff). So I've thought, surely I > could write an "acc and cps" version of my-flatten? Here is what I came up > with... > > (defn my-accandcpsbased-flatten > [xs] > (letfn [(flatten-accandcps [xs accvec k] > (if (empty? xs) > (k accvec) > (let [x (first xs), ys (next xs)] > (if (sequential? x) > (recur x accvec (fn [v] (flatten-accandcps ys [] (fn [w] > (k (into v w)) > (recur ys (conj accvec x) k)] > (seq (flatten-accandcps xs [] identity > > And I could do the trick you showed me with thunks and a trampoline, if I > wanted to make it completely stack-avoiding. > > What does this show? I'm not sure. > > Presumably the acc and stack version is the most efficient as it uses > recur everywhere? > > The structure of the continuation I pass in with the "acc and cps" version > is very similar in complexity to the continuation I passed as part of my > original cps implementation. So where's the gain? I guess the inclusion > of an accvec means that continuations are generated less frequently so that > the overall size and execution time of continuations is smaller? And it is > an improvement over my earlier aps version that used only an acc vector - > because this version has everything in tail-call position and is amenable > to trampolining. > > Is this attempt at analysis reasonable? Is there anything else worth > observing etc? > > Presumably I could make the "acc and cps" above more lazy using concat, > cons and lazy-seq. I'd need to think about how
Re: Critiques of "my-flatten" which uses CPS
Slightly off-topic from original poster's question, but if you're interested in another implementation of flatten, I suggest you take a look at the reducers library. clojure.core/flatten is elegant but a bit slow. The reducers version is very fast as part of a reduce/fold operation. The whole reducers library is worth studying. http://clojure.org/reducers -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Critiques of "my-flatten" which uses CPS
> http://clojure.org/reducers i dare say the "When to use" part should not be at the bottom but come right after the otherwise laughably specious "yielding code that will get faster automatically as machines get more cores". -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Critiques of "my-flatten" which uses CPS
Coming back to your helpful comments about relationship between acc-style and lazy... It's worth understanding how to go back and forth between accumulator-style > and a lazy construction. You can convert the above non-lazy accumulator > version into a similar version that is lazy but has no risk of stack > overflow in the realization of that lazy flattened list: > I notice in your lazy version (below), you preface the last cons with a lazy-seq call, but do not do the same with the other cons calls (within the first recur form). I know it was only the last line that previously had a conj call and so participated in this transformation... but I'm wondering why you wouldn't also use lazy-seq with the other cons-involving line? To answer my own wondering, I am thinking it is for two reasons: 1. The main reason for using lazy-seq in the last line is to defer the recursive call to my-flatten until something wants to use it. In contrast, the other cons-involving line only conses up things which are relatively harmless to evaluate. 2. The "cons (first x) ..." will be "undone" almost immediately after the recur is executed, via the "(first xs)". So inserting laziness here is counter productive. Another question... I notice that you bound ys to (rest xs), in contrast to my choice of (next xs) in some of my implementations. I realize this is probably a minor point, but just wondering whether (rest xs) was a deliberate choice of yours, or just habit. I realize that rest maximizes laziness in contrast to next, but do we want maximum laziness here? To again attempt to answer my own question... It probably depends on what xs is being passed into my-flatten. It xs is a fully realized sequence, then (next x) would probably do. But if xs is itself lazy (and possibly expensive to compute), then using (rest x) maximizes our laziness opportunity. Maybe the thing to do would be to use (next x) here for this implementation, which is angling to be lazy... But in your earlier acc-based my-flatten, to use (next x) instead, because this implementation is eager and we know we're going to realize all of xs at some point anyway. It this logic sound? (I realize I am being pedantic, but I'm trying to understand the principles involved.) Thanks again for showing me the relationship between acc-based and lazy - helpful! > (defn my-flatten > [xs] > (if (empty? xs) () > (let [x (first xs), ys (rest xs)] > (if (sequential? x) > (if (seq x) > (recur (cons (first x) (cons (rest x) ys))) > (recur ys)) > (lazy-seq (cons x (my-flatten ys))) > > Basically, you just get rid of the accumulator, and in the place where you > would have conj'd in the next atomic element, you just build the lazy > sequence. > > -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Critiques of "my-flatten" which uses CPS
Woopse, typo towards the end of my last post... Maybe the thing to do would be to use (next x) here for this > implementation, which is angling to be lazy... But in your earlier > acc-based my-flatten, to use (next x) instead > Should be... Maybe the thing to do would be to use (rest x) ... -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Critiques of "my-flatten" which uses CPS
One other question occurs to me re your comment... It's worth understanding how to go back and forth between accumulator-style > and a lazy construction. You can convert the above non-lazy accumulator > version into a similar version that is lazy but has no risk of stack > overflow in the realization of that lazy flattened list: > Why does going lazy avoid a stack overflow risk? Again, to answer my own question :-) ... The resultant flat list from my-flatten will be realized one element at a time. The call stack will be used during this process, but lazy-seq prevents it getting very deep. I think lazy-seq is a bit like a thunk (invoked via the seq call), except that it also caches the result. So its like the thunks in our trampolining, except that the "bouncing" doesn't occur eagerly as with trampolining, but only on-demand as a consumer traverses the flat list. Is this a good way of thinking about it? > > (defn my-flatten > [xs] > (if (empty? xs) () > (let [x (first xs), ys (rest xs)] > (if (sequential? x) > (if (seq x) > (recur (cons (first x) (cons (rest x) ys))) > (recur ys)) > (lazy-seq (cons x (my-flatten ys))) > > Basically, you just get rid of the accumulator, and in the place where you > would have conj'd in the next atomic element, you just build the lazy > sequence. > > -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Critiques of "my-flatten" which uses CPS
On Thu, Jul 17, 2014 at 7:54 PM, Mark P wrote: > > I notice in your lazy version (below), you preface the last cons with a > lazy-seq call, but do not do the same with the other cons calls (within the > first recur form). I know it was only the last line that previously had a > conj call and so participated in this transformation... but I'm wondering > why you wouldn't also use lazy-seq with the other cons-involving line? > The lazy-seq is necessary because of the recursive call that isn't in tail-call position (so you can't use recur). One way to think about it is that at that point, we know what the first element of the sequence is going to be, so the lazy-seq lets us return immediately with the computed first element and a description of the further computation that can compute the rest on demand. lazy-seq is the secret sauce that makes it so non-tail recursive calls don't overflow the stack. That's because the sequence is prompted for one element at a time from an outside consumer -- as you noted in one of your messages, it's a lot like what trampolining does. So to make sure you don't have stack overflow, all you have to do is make sure that you use bounded stack space in the process of computing the next element. The other calls to cons are just part of the process of coming up with the next element, basically sticking "stuff to be computed" on the front of the list as a trick to avoid a separate accumulator. Because they are inside a recur, no additional stack is consumed (the list grows, but that's a heap-allocated data structure, so not a problem). > > Another question... > > I notice that you bound ys to (rest xs), in contrast to my choice of (next > xs) in some of my implementations. I realize this is probably a minor > point, but just wondering whether (rest xs) was a deliberate choice of > yours, or just habit. I realize that rest maximizes laziness in contrast > to next, but do we want maximum laziness here? > One idiom is to use to use (next xs), and then you can test against it being nil to determine whether it is empty or not. But to use that idiom, you have to be very careful to make sure you call seq on the sequence that is passed as an input to the function (which you did in your version). If you do that and are careful, the performance of next/nil? is slightly better than rest/empty?. But I've gotten burned enough times, I simply prefer to use empty? as my test, and then you might as well use rest rather than next. It's my own preference. I think many people in the Clojure community prefer to seq the input and then next/nil?. Either is fine. -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Critiques of "my-flatten" which uses CPS
Thanks again - that all makes sense. One (hopefully) tiny question... an efficiency one... (and feel free not to answer it if I've already taken up enough of your time) If you do that and are careful, the performance of next/nil? is slightly > better than rest/empty?. > If I use the next/nil? idiom, is there a performance difference between doing: 1. (if (nil? xs) a b) 2. (if xs b a) And a related question... Clojure has two falsey values: nil and false. I assume that low-level somewhere, when checking for falsey, an (if x a b) call will do something like "if x is false, short circuit to b, if x is nil, short circuit to b, otherwise a". Except, I don't know which gets priority of place with the short circuits - is it false (as I've just written), or is it nil? Actually, if I'm thinking about it correctly... If false takes priority then... A branch to "a" will take three tests for 1. and two tests for 2 And a branch to "b" will take two tests for 1. and two tests for 2.. If nil takes priority then... A branch to "a" will take three tests for 1. and one test for 2 And a branch to "b" will take three tests for 1. and two tests for 2.. So 2. is always as good or better than 1. I think - performance wise. Of course, these things are very much minor factors in overall performance (especially when things like immutable data structures are involved), but I wouldn't mind knowing. Cheers, Mark. -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Critiques of "my-flatten" which uses CPS
I *think* I've found the answer to my own question...
In this post...
https://groups.google.com/forum/#!topic/clojure/Cuk_bJrIq-Y
I found this link (I changed the line number)...
https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Compiler.java#L2589
And if the implementation of eval() within the IfExpr class is anything to
go by...
public Object eval() {
Object t = testExpr.eval();
if(t != null && t != Boolean.FALSE)
return thenExpr.eval();
return elseExpr.eval();
}
Then I think Rich has implemented it so that nil takes priority over false.
...Which strengthens the case for choosing (if xs b a) over (if (nil? xs) a
b).
Of course, in practice it probably makes no difference, as either will be
very quick compared to other things going on.
Cheers,
Mark.
On Friday, 18 July 2014 14:39:53 UTC+9:30, Mark Phillips wrote:
>
> Thanks again - that all makes sense.
>
> One (hopefully) tiny question... an efficiency one... (and feel free not
> to answer it if I've already taken up enough of your time)
>
> If you do that and are careful, the performance of next/nil? is slightly
>> better than rest/empty?.
>>
>
> If I use the next/nil? idiom, is there a performance difference between
> doing:
>
>1. (if (nil? xs) a b)
>2. (if xs b a)
>
> And a related question... Clojure has two falsey values: nil and false.
> I assume that low-level somewhere, when checking for falsey, an (if x a b)
> call will do something like "if x is false, short circuit to b, if x is
> nil, short circuit to b, otherwise a". Except, I don't know which gets
> priority of place with the short circuits - is it false (as I've just
> written), or is it nil?
>
> Actually, if I'm thinking about it correctly...
>
> If false takes priority then... A branch to "a" will take three tests for
> 1. and two tests for 2 And a branch to "b" will take two tests for 1.
> and two tests for 2..
>
> If nil takes priority then... A branch to "a" will take three tests for
> 1. and one test for 2 And a branch to "b" will take three tests for 1.
> and two tests for 2..
>
> So 2. is always as good or better than 1. I think - performance wise.
>
> Of course, these things are very much minor factors in overall performance
> (especially when things like immutable data structures are involved), but I
> wouldn't mind knowing.
>
> Cheers,
>
> Mark.
>
>
--
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
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Re: Critiques of "my-flatten" which uses CPS
Yeah, you've answered your own question. In practice, I doubt the difference is measurable. Another common idiom you see in Clojure code is: (defn f [xs] (if-let [s (seq xs)] ...do something with (first s) and (f (rest s))... ...base case...)) This ensures that you seq-ify the input (rather than assuming it has been seq'ed before passed in), gives you the fast test against nil, and uses rest rather than next because next would have the effect of causing an extra unnecessary call to seq. In a loop-recur situation, it is more common to do the seq once in the initialization of the loop and then use next which calls seq: (defn f [xs] (loop [s (seq xs)] (if s ... (recur (next s))... ... base case ...))) Out of habit, I prefer to see the base case first so I don't usually do either of these, but these two patterns are a very popular style, and very fast execution. If you don't have a pre-existing preference, these would be good choices. -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Critiques of "my-flatten" which uses CPS
Thanks - useful idioms to know about! On Friday, 18 July 2014 16:18:33 UTC+9:30, puzzler wrote: > > Yeah, you've answered your own question. In practice, I doubt the > difference is measurable. > > Another common idiom you see in Clojure code is: > (defn f [xs] > (if-let [s (seq xs)] > ...do something with (first s) and (f (rest s))... > ...base case...)) > > This ensures that you seq-ify the input (rather than assuming it has been > seq'ed before passed in), gives you the fast test against nil, and uses > rest rather than next because next would have the effect of causing an > extra unnecessary call to seq. > > In a loop-recur situation, it is more common to do the seq once in the > initialization of the loop and then use next which calls seq: > > (defn f [xs] > (loop [s (seq xs)] > (if s >... (recur (next s))... >... base case ...))) > > > Out of habit, I prefer to see the base case first so I don't usually do > either of these, but these two patterns are a very popular style, and very > fast execution. If you don't have a pre-existing preference, these would > be good choices. > -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
