Fun discussion: TCO via trampolining in Clojure and Scala

[Patrick Wright]

Over in Clojure land, Rich Hickey announced [1]
"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."

This kicked off a great discussion in Scala's debate mailing list [2],
seeing how they could implement the idea as well. An interesting
aspect of this is that the programmer using the technique actually
indicates it in the code--see the two discussions for examples.

Thought I'd post this here so you all wouldn't miss the fun. I'm sure
many of you will have your own approaches to the problem.

And _ahem_, for those of you who are going to say you-know-what, yes,
we all wish this were easier and cheaper to do on the JVM. So, count
that as said for today.

Cheers (and hope I didn't misrepresent anything)
Patrick

1 http://tinyurl.com/6zbrsy or
http://groups.google.com/group/clojure/browse_thread/thread/6257cbc4454bcb85/3addf875319c5c10?#3addf875319c5c10
2 http://tinyurl.com/6bn35b or
http://www.nabble.com/Tail-calls-via-trampolining-and-an-explicit-instruction-td20702915.html