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 <pierh...@gmail.com> 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 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. > -- 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.
