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:
- class clojure.lang.TailCall contains an AFn
- Compiler checks for a tail call position and instead of calling it,
returns new TailCall(AFn)
- In invoke, while returnvalue instanceof TailCall, returnvalue =
returnvalue.fn.invoke(returnvalue)
I confess I don't yet have much familiarity with the compiler; I'm
just reading through it now. Is the above idea workable?
Upside: you could have real TCO tonight, with J2SE 5.
Downside: as soon as they finally get around to putting TCO in the
JVM, it becomes useless cruft.
I would think you could take it back out, though. And who knows when
they'll finally do it? And wouldn't it be better to put TCO workaround
cruft in the compiler, rather than in the language definition, around
which people are already (foolishly, perhaps) starting to build
serious programs?
On Nov 25, 9:05 am, Rich Hickey <richhic...@gmail.com> wrote:
> 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:
> - class clojure.lang.TailCall contains an AFn
> - Compiler checks for a tail call position and instead of calling it,
> returns new TailCall(AFn)
> - In invoke, while returnvalue instanceof TailCall, returnvalue =
> returnvalue.fn.invoke(returnvalue)
> I confess I don't yet have much familiarity with the compiler; I'm
> just reading through it now. Is the above idea workable?
> Upside: you could have real TCO tonight, with J2SE 5.
> Downside: as soon as they finally get around to putting TCO in the
> JVM, it becomes useless cruft.
> I would think you could take it back out, though. And who knows when
> they'll finally do it? And wouldn't it be better to put TCO workaround
> cruft in the compiler, rather than in the language definition, around
> which people are already (foolishly, perhaps) starting to build
> serious programs?
There's a very simple reason - such built-in trampolines are
incompatible with interoperability. Anyone can build a trampoline
system into their lang to get tail calls and make sure it is used
consistently within lang - but what do those TailCall return values
mean to a Java caller?
Also, in what you've described every invoke turns into a loop, every
tail call allocates etc.
I made a conscious decision here, and it was a pragmatic one. People
using Clojure are pragmatic, not foolish.
The vast majority of tail calls requiring TCO are self-calls handled
by recur.
I'm all for TCO, but trampolines are simplistic TCO and no substitute
for real jumps.
On Nov 26, 11:14 am, Rich Hickey <richhic...@gmail.com> wrote:
> There's a very simple reason - such built-in trampolines are
> incompatible with interoperability. Anyone can build a trampoline
> system into their lang to get tail calls and make sure it is used
> consistently within lang - but what do those TailCall return values
> mean to a Java caller?
Thanks. I was uneasy enough about performance, without really
understanding how much of a problem it would be, but interop would be
a deal-killer. Guess it's back to waiting.
> The vast majority of tail calls requiring TCO are self-calls handled
> by recur.
My favorite thing about recur is that the compiler tells you
immediately if you accidentally put it somewhere other than in a tail
position. You don't have to wait for the stack to overflow in actual
use because your test case was too small. I would hope the keyword
sticks around even if TCO gets added to the JVM.
On Wed, Nov 26, 2008 at 1:00 PM, dreish <dresweng...@dreish.org> wrote:
> My favorite thing about recur is that the compiler tells you > immediately if you accidentally put it somewhere other than in a tail > position. You don't have to wait for the stack to overflow in actual > use because your test case was too small. I would hope the keyword > sticks around even if TCO gets added to the JVM.
Hear, hear! +1 Can I only vote once? +10
:-)
Hm, maybe a general compile-time assert would be in order, once we have real tail-call optimization, so that even in the mutual-recursion case you could get a nice error if you make a mistake like:
On Tuesday 25 November 2008 06:05, Rich Hickey wrote:
> I've added trampoline to ease the conversion/creation of mutually > recursive algorithms in Clojure.
> ...
Clojure's new trampolines for mutually recursive functions has caught the attention of the Scala folks. There's a nice thread going on in the Scala-Debate list beginning with one user's mention of this new capability in Clojure. Two people there (one of them being Martin Odersky, the head architect of the Scala language) showed a comparable solution written in Scala.
On Tue, Nov 25, 2008 at 8:05 AM, Rich Hickey <richhic...@gmail.com> wrote:
big snip
> 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))
I'm curious about this syntax. I thought if #(function-name args) creates a closure then I can put one in a variable and execute it later. I entered this in a REPL.
> I'm curious about this syntax. I thought if #(function-name args) > creates a closure then I can put one in a variable and execute it > laterI entered this in a REPL.
On 25 nov, 15:05, Rich Hickey <richhic...@gmail.com> wrote:
> To convert to a trampoline, simply return closures over your tail
> calls, rather than direct calls. This is as simple as prepending #
I've maybe missed something, but will this work if one wants to make
the final return value of the tail call a closure ?
Will the closure not be called by the trampoline ?
(Maybe I've missed something regarding the explanation on Fn / IFn,
not clear to me)
If I'm right, then should there be some "marker" to wrap the returned
closure in, that will be checked by the trampoline for this special
case, which will then unwrap the closure and return it as the final
returned value ?
> I've maybe missed something, but will this work if one wants to make > the final return value of the tail call a closure ?
Along the same lines of this being a manual way to do TCO, that issue will need to be handled manually as well. Here's what (doc trampoline) has to say about it:
user=> (doc trampoline) ------------------------- clojure.core/trampoline ([f] [f & args]) trampoline can be used to convert algorithms requiring mutual recursion without stack consumption. Calls f with supplied args, if any. If f returns a fn, calls that fn with no arguments, and continues to repeat, until the return value is not a fn, then returns that non-fn value. Note that if you want to return a fn as a final value, you must wrap it in some data structure and unpack it after trampoline returns. nil
> > I'm curious about this syntax. I thought if #(function-name args)
> > creates a closure then I can put one in a variable and execute it
> > laterI entered this in a REPL.
> > (def myClosure #(prn "Hello"))
> > How can I execute the closure in myClosure now?
Hello Mark, maybe something got mixed up here:
#(prn "Hello") looks like an ordinary anonymous function to me,
and not like a closure.
Well, it depends on how we want to define “closure”.
I think the definition should include that it must be a function
(be it a named or anon one) that closes over some lexical
environment. In my opinion this environment should not be the
trivial one: the empty one.
We could do this, but in that case every function would be a
closure. So from that I would say that the given example was
not for a closure.
Maybe a simple accumulator could work here:
user> (let [acc (ref 0)]
(defn make-accumulator [n]
(dosync (ref-set acc n))
(fn [i]
(dosync (alter acc + i)))))
#'user/make-accumulator
So, here make-accumulator is a closure.
It closes over acc.
And the anon function that is returned by
make-accumulator is also a closure, as it
also closes over acc.
>> > I'm curious about this syntax. I thought if #(function-name args) >> > creates a closure then I can put one in a variable and execute it >> > laterI entered this in a REPL.
>> > (def myClosure #(prn "Hello"))
>> > How can I execute the closure in myClosure now?
> Hello Mark, maybe something got mixed up here: > #(prn "Hello") looks like an ordinary anonymous function to me, > and not like a closure. > Well, it depends on how we want to define "closure". > I think the definition should include that it must be a function > (be it a named or anon one) that closes over some lexical > environment. In my opinion this environment should not be the > trivial one: the empty one. > We could do this, but in that case every function would be a > closure. So from that I would say that the given example was > not for a closure.
> So, here make-accumulator is a closure. > It closes over acc. > And the anon function that is returned by > make-accumulator is also a closure, as it > also closes over acc.
Thanks! In the meantime I came up with an even simpler example that demonstrates capturing a parameter and a local variable in a closure.
On 26 Nov., 22:38, "Stephen C. Gilardi" <squee...@mac.com> wrote:
> [..] Note that if you want to return a fn as a
> final value, you must wrap it in some data structure and unpack it
> after trampoline returns.
If you want to return sets, keywords, maps, or everything that
implements the fn interface this is also an issue. Does trampolining
on keywords make sense?
> So, here make-accumulator is a closure.
> It closes over acc.
> And the anon function that is returned by
> make-accumulator is also a closure, as it
> also closes over acc.
Maybe I have a wrong understanding of "closure", but
as far as I understand, every function definition in
Clojure - be it defn or #() - finally translates to (fn ...).
And fn creates a closure. In fact #(prn "Hello") closes
over the var "prn". Consider the following example:
According to my understanding the output should
be "Hello".
I think the closure is never "empty". It refers to the
environment used at the closure's creation time.
Whether this environment is accessed or not, is not
very interesting, I think.
Ok. Maybe there are gc issues, so one might want
to optimise this. But a closure which, does not
access the environment at all... What would this
look like and which use would it have?
On Nov 27, 2008, at 5:21 AM, Robert Pfeiffer wrote:
> If you want to return sets, keywords, maps, or everything that > implements the fn interface this is also an issue. Does trampolining > on keywords make sense?
The svn revision that introduced trampoline also introduced a "marker" interface "fn" that distinguishes "things ultimately produced by fn" and "thinks that can be called". The former are the only things that are trampolined. It also changed the behavior if fn? and introduced ifn? that know about the difference. Here's an example:
Could trampoline benefit for being enhanced by allowing an explicit
"escaping" for a return value of type function (that could also work
for other return types, but would not be necessary for the common
case).
Something like these :
- common usage : as usual
user=> (def myClosure #(prn "Hello"))
#'user/myClosure
user=> (trampoline myClosure)
"Hello"
- explicit escape via a "noboing" (or "stop" or "return" any name you
like) call (works for any return type) :
user=> (def myClosure (noboing #(prn "Hello")))
#'user/myClosure
user=> (trampoline myClosure)
#'user/myClosure
And it could be implemented as :
public final class org.clojure.lang.NoBoingWrapper {
public final Object returnInstance;
public NoBoingWrapper(Object returnInstance)
{ this.returnInstance = returnInstance; }
and the modification of trampoline along these lines :
(defn trampoline [f]
(let [ret (f)]
(cond f
(fn? ret) (recur ret)
(instance? org.clojure.lang.NoBoingWrapper f) (.returnInstance
f)
else ret)))
HTH,
--
Laurent
On Nov 26, 10:38 pm, "Stephen C. Gilardi" <squee...@mac.com> wrote:
> > I've maybe missed something, but will this work if one wants to make
> > the final return value of the tail call a closure ?
> Along the same lines of this being a manual way to do TCO, that issue
> will need to be handled manually as well. Here's what (doc trampoline)
> has to say about it:
> user=> (doc trampoline)
> -------------------------
> clojure.core/trampoline
> ([f] [f & args])
> trampoline can be used to convert algorithms requiring mutual
> recursion without stack consumption. Calls f with supplied args, if
> any. If f returns a fn, calls that fn with no arguments, and
> continues to repeat, until the return value is not a fn, then
> returns that non-fn value. Note that if you want to return a fn as a
> final value, you must wrap it in some data structure and unpack it
> after trampoline returns.
> nil
