On Tue, Aug 10, 2010 at 2:40 AM, Mark Engelberg <mark.engelb...@gmail.com> wrote: > arbitrary-sized lists is a primary goal. The posted code (minus the > call to recur), is an elegant recursive formulation that is idiomatic > in Scheme because Scheme is (typically) implemented in a way that > makes stack limitations (mostly) a non-issue. > > In Clojure, you have to work around stack limitations imposed by Java, > and recursive functions must be "translated" to work on largish lists > in Clojure. There is no one recipe to make that translation, but > there are several common patterns. If the recursive call is in tail
I want to add a little bit of information. (I am not a specialist of Scheme but believe what follow to be true) The original function minus recur + a recursive call on the second cond is not tail-recursive. So, in this particular case, Scheme does not warranty no exhaustion of resources. (A lot of Scheme implementation, and SML/NJ I believe, are CPS-compiled and will exhaust heap and not stack but those that are based on Lazy Stack copying would probably exhaust stack). Anyway, this implementation - in any language - would still eat memory, constructing a long stack-allocated (or heap-allocated in most Scheme and SML/NJ) list of continuations to remember "what to do when I have finished". In more fancy term, whether on the stack and on the heap, you need to keep a list of "continuations" to the computation. "When I am at the end of the list, I will add one, and then add one, and then add one ...." A tail-call has the particularity to have a trivial continuation: "I take the result and return it", so you don't have to actually keep any information. Most functional languages optimise this, but those on the JVM have a hard time doing it, because the way the JVM works. Scheme warranties it. You are not a Scheme implementation if you do not do tail-call optimisation. Clojure does it, for self recursion, when you explicitly ask for it, emitting a compile-time error if it can't. I think it is a good idea, because sometimes you write the function lightly badly and do not realise tail-call optimisation do not happen until a bug in production. There are ways to transform a call in tail-call. Adding an accumulator, using a list passed as argument as a stack, or doing a Continuation passing Style transformation. (http://en.wikipedia.org/wiki/Continuation-passing_style , in a word: to put the future in a closure we pass to the recursive call.) It is harder to transform a program to only self tail-call, but I think CPS+trampoline always do the trick. (Without the restriction to only do self calls, CPS does always the trick) Best regards, Nicolas. -- 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
