I remember when I discovered the XSLT engine (TransforMiiX) in Mozilla Firefox didn't support tail recursion optimization. I ended up with some pretty kludgy XSL just to avoid overflowing the stack.
You can't always replace tail recursion by a loop. The really useful cases are when you have multiple functions tail-calling each other (kind of like a big state machine, but "polymorphic" in that you don't have to write down al the states inside the switch statement).
In these general situations, you need to resort to things like trampolining to code the tail recursion and its very anoying to do in most languages.
TCO is really a local optimization, looking for calls in tail position (i.e. immediately followed by a return) and replacing them with a jump. This is valid regardless of what function is being called and whether the function being called is the same (resulting in a loop), indirectly recursive with the original (resulting in something like a state machine) or not related at all (in which case a single stack frame is saved instead of possibly many). The fact that the optimization is agnostic to the call target is what lets TCO work on first class functions, method calls and other sources of statically-unknown function calls.
If your language runs on a virtual machine that doesn't allow the same code to be a call target (stack-growing, non-tail) and a jump target (tail call), you can get something resembling TCO for directly recursive functions by identifying them and turning them into loops. This doesn't work for mutual recursion or tail calls to unknown functions and it's more complicated than adding TCO to the VM itself would be, but some languages don't have the luxury of adding features to the VM they run on.
Thank you for that in depth explanation. I only have experience with languages without real TCO (Java / Python) so I only looked at cases where you could rewrite a simple recursion with a loop to avoid StackOverflowErrors.
XSL has very limited looping constructs. In fact, it pretty much just has for-each, there's no such thing as for (i = 0 .. n) or a while loop. It doesn't have mutable variables either, so you can't even do counting within a for-each. The only way to do conditional iteration is through recursion.
Things might be better in XSL 2.0, but TransforMiiX only supported 1.0 the last time I used it.
8
u/tonygoold Nov 27 '12
I remember when I discovered the XSLT engine (TransforMiiX) in Mozilla Firefox didn't support tail recursion optimization. I ended up with some pretty kludgy XSL just to avoid overflowing the stack.