3 ms·
You can use tail recursion to create abstractions in a compositional manner that cannot be created compositionally with iterative constructs. For example, if y
by noelwelsh 8y ago
You can use tail recursion to create abstractions in a compositional manner that cannot be created compositionally with iterative constructs.
For example, if you can express a finite state machine (FSM) as a number of mutually (tail) recursive functions. Then you can reuse this FSM as part of a larger FSM via a tail call. You can't do this with the iterative constructs in C et al---the whole FSM must be defined in one spot.
- gpderetta 8y agoof course you can, and trivially so; just return the next function to call from (as a pointer or some other identifier as a result of each state function.
- noelwelsh 8y agoThat's called a trampoline, and is one of the ways to simulate tail recursion. It requires a global modification to the code: you have to rewrite all your code that you want to be stack-safe to be trampolined. It wouldn't call that trivial, but then Node developers are happy to rewrite their code into CPS so what do I know.
- gpderetta 8y agoat the end of the day it is always continuations all the way down.
- alkonaut 8y agoCan you expand on this? What's a trivial exmaple? Doesn't it depend on how the iterations are compiled? Seeing how e.g. a normal continuation is compiled in C#. foreach(var thing in Things) { if (thing.IsAlive) yield return thing; } Those will compose (At least I think they will compose in the sense you mean) because they are alrerady sugar for a state machine and not a simple iteration. The for-loop construct didn't imply "loop here until done" in the sense that doesn't compose.
- burfog 8y agoSo do the tail recursion in C. Any decent compiler will handle it just fine. If you want to include crappy compilers, well, then we need to include the same for LISP and Scheme. Whatever the language specification may claim about tail recursion is not relevant when you sit down to produce code for the actual system at hand.
- kazinator 8y agoA Scheme compiler that doesn't do tail recursion isn't crappy; it is incorrect/nonconforming. A C compiler that doesn't do tail recursion still conforms to the abstract language semantics. In Scheme, local functions are used for looping (via tail recursion). C doesn't even have those (other than as a GNU C extension).
- noelwelsh 8y agoThis isn't a C vs Scheme (or whatever) discussion. It's about the utility of (tail) recursion vs iterative constructs. That C compilers may optimise tail recursion isn't relevant.