Re: java.lang.StackOverflowError when calling function name instead of recur
On Tue, Aug 2, 2011 at 4:47 PM, David Nolen wrote:
> On Tue, Aug 2, 2011 at 4:43 PM, Trastabuga wrote:
>>
>> I just came across the issue of getting the StackOverflowError in the
>> function reading long file and recursively building a list of data.
>> After I replaced function name with "recur" the problem went away.
>> Hence a couple of questions. It's the programmer's responsibility to
>> put recur instead of function names where tail-recursion is available?
>> (Kind of obvious, but then why the compiler wouldn't detect it?)
>> If tail-recursion is not available and function name has to be called,
>> how do I deal with stack overflow in this case?
>
> Clojure does not have tail call optimization. You must use recur,
> trampoline, or redesign your code around lazy sequences.
> David
More specifically, you must use recur when your call chain is:
a -> a -> a ...
You'll need trampoline for more elaborate cases of mutually recursive
functions, like
a -> b -> c -> a
or even
a -> b -> a -> c -> d -> b -> a
(where clearly a at least has conditional branches that can lead to
tail calls to at least either b or c depending).
Lazy sequences provide another way to do this. For example, suppose
you have a set of functions a, b, c ... and a state machine specified
with a map like {\a {\a b \b d \c q ...} \b {\a c \b a \c d ...} ...}
(as might be used if for some reason you wanted your own homegrown
regular expression implementation), you might implement this with
trampoline using
(defn a [in out]
(if in
(let [new-state ((state-map (first in)) \a)]
#(new-state (next in) (conj out whatever)))
(list out)))
...
(defn process [in]
(apply str (first (trampoline a (seq in) []
or something like that. You might also use lazy-seq:
(defn a [in]
(lazy-seq
(if in
(let [new-state ((state-map (first in)) \a)]
(cons whatever (new-state (next in)))
...
(defn process [in] (apply str (a in)))
though you might also use the higher-level reduce:
(def state-to-letter {a \a b \b ...})
(defn a [ch]
whatever)
...
(defn process [in]
(apply str
(second
(reduce
(fn [[[current-state out] ch]
(let [new-state ((state-map ch)
(state-to-letter current-state))]
[new-state (conj out (current-state ch))]))
[a []]
in
or a low-level loop/recur:
(defn process [in]
(loop [in (seq in) out [] current-state a]
(if in
(let [ch (first in)
new-state ((state-map ch)
(state-to-letter current-state))]
(recur (next in) (conj out (current-state ch)) new-state))
(apply str out
(Note: untested, and the "whatever"s are presumed to depend on the
state and the current input character, in such a way as to be hard to
replace with just a map lookup.)
Note that all of the above find some way to turn a calls b calls a
calls c calls ... into something sequentially calls a, then b on a's
return value, then a on that value, then c on that value ... and thus
avoids deeply nested stack frames.
In the case of trampoline, trampoline has the behavior that if the
function it's passed returns a new function, it calls that (with no
arguments), and repeats until a non-function return value is
generated. (In the state machine this has the awkward effect of
requiring the vector a returns if it's reached the end of in to be
wrapped in a list, since vectors are callable as functions and
trampoline might therefore call it instead of return it.) Since
functions can be selected programmatically in a functional language,
the state machine can be almost directly encoded in functions, or less
directly using a transition map as above.
Lazy-seq is good for cases like the above where each step is appending
to some growing output sequence. Then you just write each step almost
as you would with plain recursion, returning (cons this-steps-result
(next-step args)), but the whole thing is wrapped in (lazy-seq ...).
The seq is finite if and only if at some point one of the steps
returns nil instead of a cons. In this case that happens when the
input is exhausted. The seq generated is (step-1s-result
step-2s-result step-3s-result ...) and since it's lazy steps are only
performed as the consumer needs more items, and are called
sequentially, rather than nesting. (Technically, each step ends up
returning a delay rather than the cons, and the delay gets forced when
the step's output is needed by the consumer, which triggers the next
step, which produces another delay for the consumer to unwrap later;
so each step returns a delay instead of directly calling the next, and
the caller calls the next by forcing the delay, which turns the chain
of tail calls again into iteration.)
Reduce is generally useful for an iteration that accumulates a result,
in this case a vector. Direct use of loop/recur is also useful
sometimes for iteration.
Note that the trampoline, reduce, and loop/recur version
Re: java.lang.StackOverflowError when calling function name instead of recur
To add a bit to this, the JVM does not support tail call recursion. As I understand it, Clojure compiles into bytecode that effectively turns the recurs into an iterative process. Scala does something similar but automatically (i.e. you don't have to use a specific keyword). The advantage to Clojure's approach, IMO, is that given that it isn't guaranteed by the JVM, you at least know when you expect a tail recursion, and get an error from Clojure if you aren't calling from a tail position. The various clojure books out there expand more on this and by far more eloquently. Cheers On Aug 3, 6:47 am, David Nolen wrote: -- 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
Re: java.lang.StackOverflowError when calling function name instead of recur
To be even more pedantic, clojure does not guarantee that tail calls will be optimized. This is due to the lack of support in many of the jvm implementations. There is a post on using avian, a jvm implementation that supports TCO, that allows clojure to support TCO with little modification. http://groups.google.com/group/clojure/browse_thread/thread/5388b89d5b187e2f/e19a578f1a0ea6d3?lnk=gst&q=tail+call#e19a578f1a0ea6d3 On Aug 2, 4:47 pm, David Nolen wrote: > On Tue, Aug 2, 2011 at 4:43 PM, Trastabuga wrote: > > I just came across the issue of getting the StackOverflowError in the > > function reading long file and recursively building a list of data. > > After I replaced function name with "recur" the problem went away. > > Hence a couple of questions. It's the programmer's responsibility to > > put recur instead of function names where tail-recursion is available? > > (Kind of obvious, but then why the compiler wouldn't detect it?) > > If tail-recursion is not available and function name has to be called, > > how do I deal with stack overflow in this case? > > Clojure does not have tail call optimization. You must use recur, > trampoline, or redesign your code around lazy sequences. > > David -- 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
Re: java.lang.StackOverflowError when calling function name instead of recur
On Tue, Aug 2, 2011 at 4:43 PM, Trastabuga wrote: > I just came across the issue of getting the StackOverflowError in the > function reading long file and recursively building a list of data. > After I replaced function name with "recur" the problem went away. > Hence a couple of questions. It's the programmer's responsibility to > put recur instead of function names where tail-recursion is available? > (Kind of obvious, but then why the compiler wouldn't detect it?) > If tail-recursion is not available and function name has to be called, > how do I deal with stack overflow in this case? > Clojure does not have tail call optimization. You must use recur, trampoline, or redesign your code around lazy sequences. David -- 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
java.lang.StackOverflowError when calling function name instead of recur
I just came across the issue of getting the StackOverflowError in the function reading long file and recursively building a list of data. After I replaced function name with "recur" the problem went away. Hence a couple of questions. It's the programmer's responsibility to put recur instead of function names where tail-recursion is available? (Kind of obvious, but then why the compiler wouldn't detect it?) If tail-recursion is not available and function name has to be called, how do I deal with stack overflow in this case? -- 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
