I've added trampoline to ease the conversion/creation of mutually
recursive algorithms in Clojure.
Trampolines are a well known technique for implementing TCO - instead
of actually making a call in the tail, a function returns the function
to be called, and a controlling loop calls it, thus allowing chained
execution without stack growth.
In order to do this I've made the following changes (SVN 1122):
Added clojure.lang.Fn marker interface, used on all true fns.
Breaking change - fn? now tests for Fn, not IFn (this was frequently
requested)
Added ifn? which will test for anything callable (IFn)
Added trampoline, implements trampoline protocol for TCO
Here's how it works. Normally, if you have mutual recursion (i.e.
which can't be replaced with recur), you can blow the stack:
(declare bar)
(defn foo [n]
(if (pos? n)
(bar (dec n))
:done-foo))
(defn bar [n]
(if (pos? n)
(foo (dec n))
:done-bar))
(foo 1000000)
-> java.lang.StackOverflowError
To convert to a trampoline, simply return closures over your tail
calls, rather than direct calls. This is as simple as prepending #
(declare bar)
(defn foo [n]
(if (pos? n)
#(bar (dec n))
:done-foo))
(defn bar [n]
(if (pos? n)
#(foo (dec n))
:done-bar))
Then make the top-level call via trampoline:
(trampoline #(foo 1000000))
-> :done-foo
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 [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
