[wgd]

There's a fascinating relationship between tail recursion and continuations, because any non-tail-recursive function call can in principle be made tail-recursive through conversion to explicit continuation-passing style.

For added fun, that continuation can then be defunctionalized [1] back into a data structure. It can be argued that TRMC as implemented in the linked post is simply a special case of this more general transformation.

[1] https://www.pathsensitive.com/2019/07/the-best-refactoring-y...

[wahern]

> because any non-tail-recursive function call can in principle be made tail-recursive through conversion to explicit continuation-passing style.

I mean, the call stack is literally just a convention for storing continuation state. The C standard describes the effect of calling another function "suspend[ing]" execution of the current function.[1] What differentiates CPS from regular recursive programming is that this behavior isn't maximally transparent, and typically is also less efficient in machine code.

All of these modes of behavior were mostly well understood early on, but it took several years for the literature to rigorously distinguish and define them, and then complete the circle by declaring equivalencies that nobody ever seriously doubted in the first place.

The upshot is we're like in the 4rd or 5th cycle of people rediscovering things like asynchronous programming. During previous epochs people just beefed over different but functionally similar terminology: e.g. interrupts vs polling (in that case, a carry over from hardware terminology). Unix's awkward signals and then threading APIs being a legacy of those (not very distant) debates. One of the first battles was whether to build recursion into languages at all, rather than requiring explicit management of call state, relying on global space for the fast path that didn't require recursion. Today the dispute is CPS vs blocking, but it's the same basic dichotomy and arguably we're just rehashing the same battle over again, without even changing the terminology.

The blocking/polling/recursion camp seems to invariably win out. The whole purpose of general purpose programming languages is to hide basic code flow management, particularly call state, behind an abstraction, and in the vast majority of code written in these languages, even highly concurrent code, such state bookkeeping is obnoxious noise when it leaks through too heavily. It's ironic when some language aficionados (Rust, Javascript, etc) justify it by saying it's about maximizing performance or making things explicit, ignoring the fact that almost all of this "efficient" and "transparent" code is running within a process (also variously described as "threads" and "coroutines" in bygone eras) isolated with hardware-supported virtual memory, all of which are predicated on transparent, blocking behavior. IOW, preferences have already been established and then punctuated multiple times, now we're just haggling over the finer details.

[1] C11 6.2.4p6: "... Entering an enclosed block or calling a function suspends, but does not end, execution of the current block...."

[seles]

Cool, I had heard of defunctionalizing CPS before but never dared to try it.

I tried to follow along defunctionalizing map, but it is a bit different since it has a return value, whereas in the video it is a void. What I ended up with was equivalent to building a list and then reversing it. So it did infact work (all functions were tail callable). This was mentioned in the article as inferior to the author's final product though. So I think it is a bit different to a special case of CPS defunctionalization optimization.

Although there may have been other ways to deal with the return value in continuations...

[yccs27]

> any non-tail-recursive function call can in principle be made tail-recursive through conversion to explicit continuation-passing style

This sounds great, but in the end you just construct your own call stack under the guise of chaining continuations together.

The real optimization happens when the continuations have structure, so that you can merge the composition of multiple continuations into one. And once you represent the continuation with its data, you just get "accumulator-passing style".

[Rusky]

Indeed, it's a special case that relies on associativity, which is why it also works for + and *: https://www.cs.ox.ac.uk/jeremy.gibbons/publications/continue...