3 ms·
For immediate recursion, an explicit keyword makes perfect sense, and indeed may be seen as preferable owing to gotchas around what might otherwise be interpret
by barrkel 17y ago
For immediate recursion, an explicit keyword makes perfect sense, and indeed may be seen as preferable owing to gotchas around what might otherwise be interpreted as a non-tail call, such as not structuring things with accumulator(s) as necessary.
Tail call can start to work magic, though, when you use it with mutual recursion. Tail calling is not just a kosher way to write a loop just to fit in with a functional religion; it makes it possible to structure programs that have certain performance characteristics that are hard to achieve any other way.
Consider a simple interpreter of opcodes, for a simple virtual machine. A trivial interpreter could use a big switch statement, with one entry per opcode; but that wouldn't be particularly neatly structured, because you'd likely have to inline most opcode implementation bodies into the switch in order to get decent performance.
An optimization is a threaded code interpreter; scan through the program once, transforming opcodes into function pointers, where each function implements a single opcode, and proceeds to the next opcode by calling it directly. But this causes a problem in most imperative languages, without low-level hackery or an unsafe feature like gcc's computed goto: the stack will grow with every opcode interpreted, because each call grows the stack. Tail call support permits this approach in both a safe and efficient way.
I do agree, though, that even in these cases, some kind of tail call directive would be preferable, to indicate to the compiler that a tail call is expected here for algorithmic correctness, and help the programmer avoid accidentally inhibiting tail calling.
- JulianMorrison 17y agoSo build up a lazy seq of fns and then dorun it. There are ways and means ;-)
- silentbicycle 17y agoBuilding up thunks carries some overhead. In languages without TCO, virtual machines are usually written with e.g. a big switch statement with everything in one big function just because any overhead there will impact every single operation that runs on the system. Not every VM needs to be fast, of course, but it's a common requirement for production versions.
- dkersten 17y agoand if you simply want mutual recursion, trampoline works well.
- dkersten 17y agoI'd prefer a goto function or call with no return statement, personally.
- JulianMorrison 17y agoI agree, (goto fname arg arg) seems like a very clean way of "tail calling" explicitly. In particular, the fact that it's in tail position can be checked as a syntax issue, as it is with (recur).