clojure-tco

the JVM that do tail call optimization, but I assumed they utilised some kind of virtual stack. Jörg W Mittag on StackOverflow confirmed this: "Nah, TCO [on the JVM] is easy. Seph does it, Erjang does it, Kawa and all the other Scheme implementations on the JVM do it. The JVM has Exceptions, which are basically the same as GOTO, which can be used to implement TCO. Or you use trampolines. Or you don't use the JVM call stack at all and just implement your own. The reason why Clojure and Scala only provide limited TCO (basically, only tail recursion is optimized) is because they want to use the JVM call stack for interoperability and performance reasons. As Rich Hickey, Clojure's designer said: Interop, speed, TCO -- Pick two." [1] James Iry wrote the following on LtU, which explains why even though "Real instruction sets (or C) don't 'support' proper tail recursion either", the fact that the JVM doesn't is an issue for Clojure (and Scala): "Native instruction sets often let you do whatever you want with the stack. C doesn't in the ANSI standard, but you can do it with a bit of assembly. .NET IL has an explicit instruction for tail calls. The JVM, on the other hand, is very strict about how you use its stack and has no tail call instruction." [2] During my Googling, I also found this[3], which is pretty interesting! "CTCO works by applying a first-order one-pass CPS algorithm (via Danvy 2007), then transforming the code to return thunks, and finally creating a custom trampoline to be used when the code is executed. Thanks to the properties of the CPS transformation, CTCO will make all function calls into tail calls, thereby even making non-tail code compiled by CTCO use constant space." This actually sounds not far from what you suggested! Although it does seem to be a bit more than "just an AST transformation". I haven't read through it, or read the referenced paper [4] it's a bit over my head. You should check it out and report back! I've bookmarked it for now. Finally, you wrote: "And I don't think it's a trade-off in the least. If so, what are Clojure programmers winning now? The glorious overhead of thousands of function calls? Those tasty 'stack overflow' back-traces, with thousands of calls to the same function?" Do you still think it's not a trade-off? Unless that last link I found is a magic bullet that makes TCO fast without interfering with Java interop (or the performance of Java interop) then I really don't think it's fair to say that it's not a design trade-off. Rich Hickey (and Martin Odersky) obviously made a conscious decision about this, and you're welcome to disagree with them, but it's not clear cut. What Clojure programmers are winning now (by being hosted on the JVM) is a lot, I think. Easy interop is one of the pillars of Clojure that has contributed heavily to it picking up steam. I think the same applies to Scala. I said earlier that I don't have an opinion, and I guess it's only true that I don't have a strong opinion. If I had to pick, I think I'd pick interop. Sorry for the long comment but I'd already done the research, I figured I might as well share it, although there really already has been a great deal said about this. [0] https://groups.google.com/forum/?fromgroups=#!msg/clojure/Oi... [1] http://stackoverflow.com/questions/7261039/haskell-on-jvm [2] http://lambda-the-ultimate.org/node/3106 [3] https://github.com/cjfrisz/clojure-tco [4] http://www.brics.dk/RS/07/Abs/BRICS-RS-07-Abs/BRICS-RS-07-Ab...

rmance. Some other CPS-related avenues you may want to look into include "The Essence of Compiling with Continuations" (co-authored by one of my heroes, Amr Sabry) which formalizes A-normal form, an alternative to compiling with continuations that was ground-breaking in pointing out the number of unnecessary redexes introduced by traditional CPS algorithms. There's also a more recent paper by Andrew Kennedy at MS Research called "Compiling with Continuations, Continued" which I admittedly have not gotten a chance to dig into yet. It's stated goal is to revive some of the ideas of the original "Compiling with Continuations" by Andrew Appel. Of course with the method you present, continuation application isn't your only performance hit. If you're using a trampoline, you're undoubtedly thunkifying the code to delimit the bounces on the trampoline. I also need to do some work in this area, but I'm familiar with at least one paper on doing minimal thunkification from 1993 and linked here: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.158.... . I'm a big fan of both CPS+trampolining and the work like ClojureScript that's bringing efficient Lisp programming to the JavaScript arena. I'm hoping to get a chance to look over the work that you've done with Outlet and I'd love to chat with you about it. It sounds like we share quite similar interests.