8 ms·
They left out the part where Clojure DOES NOT implement tail-call optimization for mutually recursive functions. Without TCO, you can't fully leverage functiona
by wahern 10y ago
They left out the part where Clojure DOES NOT implement tail-call optimization for mutually recursive functions. Without TCO, you can't fully leverage functional composition and immutable data structures without introducing some ugly hacks or relying on other language-level constructs offered by the implementation--that they can't be implemented in the language strongly suggests something about the limitations of the language.[1]
A great language that does optimize mutually recursive tail-calls, among many other elegant features: Lua!
... TCO, asymmetric stackful coroutines (90% as powerful as call/cc, but with zero calories), lexical closures, prototype-based object orientation, duck typing-based object orientation (among other possibilities), and a first-class C API that allows C code to work cleanly with coroutines, closures, the object system(s)....
Lua is truly multi-paradigm. The only downside is dynamic typing, though that's not always a liability and often an asset. Also, Lua has other interesting features, like lexical global namespace substitution using _ENV, that permit devising solutions to minimize some of the headaches of dynamic typing. And because Lua is so powerful in so many dimensions, yet so simple and tiny, writing unit and regression tests is often a breeze.
Once you add the canonical extension module LPeg into the mix (written by one of the Lua co-maintainers), Lua is about as formidable as they come. Only Perl 6 comes close to the ease of writing parsers with Lua+LPeg.
[1] The JVM will eventually add support for implementing TCO in Clojure and other languages, at which point many Clojure proponents will find religion in the power of TCO.
- brandonbloom 10y ago> Without TCO, you can't fully leverage functional composition and immutable data structures Look, I like tail calls as much as any language geek, but this statement is just plain silly. The idea that TCO is needed to "fully" leverage anything is silly. Never mind that necessitating so-called full leverage is pointless, as even supposedly partially leveraged anything can be useful. In the case of Clojure, function composition and immutable data structures are highly leveraged and, after learning the seq abstraction and lib functions, you won't even miss tail calls unless you try to write a direct-style interpreter for a language that supports recursion.
- willtim 10y agoPerhaps TCO is not required for idiomatic Clojure, but for advanced functional programming using e.g. Monads or CPS, TCO is absolutely necessary in practice.
- dragandj 10y agoClojure has TCO, though. This is what recur is for.
- willtim 10y agoNo Clojure does not have TCO, due to the JVM. It allows you to manually optimise self-recursion via recur. This is not enough for many advanced FP techniques, such as CPS. For example, using CPS and TCO, I can traverse a tree in constant stack space. I agree with the parent that lack of TCO in Clojure is probably not an issue for most.
- brandonbloom 10y agoThe fact that monads are not popular in Clojure is a good thing, IMHO. Besides, test.check and clojure.spec get by just fine with macros for generator monads. It's not quite perfect, and everyone would like proper tail calls, but it's far from an impediment for the overwhelming majority of tasks tackled with Clojure.
- pjmlp 10y agoThe ML family of languages and the Lisp one, with exception of Scheme, don't require TCO. So none of them are worthy of being FP languages according to you.
- nemoniac 10y agoI think you'll find that you can rely on TCO in all of the languages you mention. Certainly Scheme, Racket and most ML languages and their implementations. Common Lisp does not require it but the most popular implementations (CMUCL, SBCL, CCL, Allegro, LispWorks) all provide full TCO.
- junke 10y agoI think pjmlp knows about this. The important word was "require", which makes a lot of difference. If you don't guarantee TCO at the language level, you can afford to emit code that performs other useful things (like debugging) while remaining conform to the language specification.
- pjmlp 10y agoThen your code will become implementation dependent and fail spectacularly when trying to port it.
- PuercoPop 10y agoSBCL does TCE on some circumstances/optimization levels, not on every instance. Nor is it portable nor idiomatic CL. (Although I certainly write code that depends on it sometimes)
- retrogradeorbit 10y agoClojure does actually support TCO, it doesn't support automatic TCO because of the JVM limitations. And after using explicit TCO calls in clojure for a while I actually prefer it now over automatic TCO. Because I can clearly see from reading my code where tail calls are optimized, and where they build up stack. I don't have to try and work out if the recursive call is in the tail position. It's all explicit. For mutually recursive TCO there's `trampoline` https://clojuredocs.org/clojure.core/trampoline https://clojuredocs.org/clojure.core/trampoline
- nemoniac 10y agoAgreed that explicit is better than implicit but I can't imagine when you might want tail calls to build up stack. And if you do have a use case for it in mind, wouldn't you want to be explicit about that and have TCO be the default?
- retrogradeorbit 10y agoWell that (default being TCO, and explicitly declaring a stack call) would mean every normal function call (the vast majority) would need to be explicitly declared (call func args...), and the implicit case would need to blow up everywhere it's invoked in a non-tail position. What I was getting at is: in an automatic TCO language you don't actually know if the call is optimised or not. You might think it's optimised, but it isn't, because it's not in the tail position. You don't find this out until one day in production the stack explodes. The only way to know if it's optimised is to determine if it is in the tail position. That sometimes is straight forwards, but sometimes requires careful thought. It is certainly not always obvious. Additionally, another coder can come along and break your tail position. You've gone "return func()" and it's TCO and then later someone changes it to "return 1 + func()" and now the call to func is not TCO, but there is no warning and no obvious outward signs that this has changed. In the explicit TCO of clojure, if the second programmer adds the extension the compiler will explode with something like "recur not in tail position", immediately informing you that this has happened, and then you may either refactor to put it back in the tail position, or change it to a full stack function call once you determine that building up stack is ok in this case. Now I think loop/recur was implemented in Clojure as a work around the JVM limitations, but in doing so I think Hickey stumbled onto a really great new syntactic formulation for TCO. Explicitly declared TCO. I like it.
- anonymoushn 10y agoYou can use a small patch to add the remaining power of call/cc to Lua. I've thought I would need to do this for a game, because I was using both "state stored in execution contexts" and "speculative execution of the game's update() function while waiting for remote players' inputs". I didn't end up making that game though :(
- bad_user 10y agoLua isn't homoiconic and doesn't have LISP style macros; yes there's this or that patch available, but like all other attempts at implementing macros in other languages, it never comes close to being as good as what LISP does naturally, because in LISP code is data literally. In other words, Lua has nothing to do with LISP, except that it's your favorite, hence I don't understand this comment. As for TCO, it's regrettable that the JVM runtime doesn't provide support, however you can work around it by implementing trampolines, which is how developers of Scala, Clojure and PureScript have managed to live. For example you can implement a fairly efficient and lazy IO type, like the one in Haskell, which then gives you memory-safe tail-calls for free. Examples include the Free monad or the Task type from Scala. The only downside of this approach is that it involves effectively building your own call-stack and keeping it in heap, which stresses the garbage collector and implies some indirection. But then again, if you'll look at the TCO performance of platforms supporting it (e.g. .NET, ES6), TCO calls have a performance penalty which can be quite significant, so I'm not sure that you'd gain much in terms of performance. And if you measure the performance of FP-heavy Scala and Clojure, you'll see that it's not bad compared with Scheme implementations or Haskell, in spite of trampolines being used for tail-calls.
- meric 10y agoYou have listed the reasons why I wrote a language that's a superset of Lua and Lisp, allowing lisp style macros to manipulate lua code as data. http://github.com/meric/l2l http://github.com/meric/l2l
- edem 10y agoIt is not a limitation of Clojure but a limitation of the JVM. And you can use the recur keyword to actually do TCO.
- PuercoPop 10y agoRecur only handles a limited case of tail call elimination, not when the function calls another function on the tail position. Also you can implement TCE on the JVM Kawa Scheme does, just not efficiently. It is a limitation resulting from the design decision of Clojure.
- poizan42 10y agoI'm getting a bit tired of the "we don't have TCO because the JVM doesn't support it" argument. You know what doesn't have a tail-call construct either? Every hardware architecture in existence. You know what they have though? They have jumps. That is all a TCO is. It turns a recursive construct into a looping construct. And it's a really simple optimization - just update the local arguments to their new value and jump back to the start of the function instead of a call + return. No, Clojure doesn't have TCO because of a design decision. We can discuss the rationale behind that decision and the merits of it, but claiming it has anything to do with the JVM is dishonest.
- lmm 10y ago> You know what doesn't have a tail-call construct either? Every hardware architecture in existence. You know what they have though? They have jumps. Guess what the JVM doesn't have. Remember also that the JVM was originally designed for running untrusted bytecode, so it doesn't generally let code directly manipulate the call stack.
- poizan42 10y ago> Guess what the JVM doesn't have. https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.html#jvms-6.5.goto https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.ht... > so it doesn't generally let code directly manipulate the call stack. You are doing something wrong if you need to manipulate the call stack to do a tail call. You just have to update the local arguments and jump back to the start of the function. It is literally just turning the call into a loop.
- jeremiep 10y agoThat works for tail recursive functions, but not tail calls. TCO works for all tail calls, not just the recursive ones, so that jump would be to another function's body. The current stack frame may not have enough space for the new function's.
- 10y ago
- draegtun 10y ago>> ...Only Perl 6 comes close to the ease of writing parsers with Lua+LPeg. I would argue that it doesn't get any easier than using Rebol/Red parse dialect - http://blog.hostilefork.com/why-rebol-red-parse-cool/ http://blog.hostilefork.com/why-rebol-red-parse-cool/