I see your point - tail calls are identical to MLIR-style phi nodes, where not the branch source determines the value, but it's passed explicitly as a function argument.

I still think that tail recursion is too low level a construct for functional programmers to interact with, but it's wrapped into something like a reduce operation, which allows to write an identical fibonacci impl, as you would in a procedural language.

That "tail recursion" is a thing in it's own right is more a sign of people getting their implementation wrong than anything else.

Specifically, if calling a function at the end of your current function _doesn't_ clean up the call stack first, what you've got is a space leak. That C's ABI on various architectures gives you this behaviour is a bad thing. The space leak sucks there too. You get functions with a tailcall: label at the top and `goto tailcall;` written in the body as a workaround when functional programmers collide with this.

Related is RAII in C++ - implicitly calling things on leaving scope mostly means the function call in the "tail" position has to do more stuff after it returns, so it isn't in the tail position, and you burn memory on keeping track of the work still to do. This takes the initial mistake from C and really leans into it.

If your language doesn't make that implementation mistake, you just have function calls that work fine. Tree style recursion is still a problem, but it's an out of memory one and at least only one side of the tree is eating memory, and in proportion to the book keeping needed to find the other side of the tree.

In the olden days, _function calls_ in Fortran didn't work, because they put their local state in global memory, not on a stack. So if foo called bar called foo, broken. We don't tolerate that any more, everyone has a call stack. But we still tolerate "ah, let's just leak this stack frame for a while, we've always done it like that" at present.

If you want automatic implicit tail calls for literally everything, then you need a solution for

  {
    FooObject foo = FooObject(123);
    return foo.bar();
  }

ending up in a UAF when FooObject::bar() tries accessing the receiver "this". Or any other case of the tail function accessing a pointer to something the caller has put on the stack. Short of some kind of crazy dependency tracking (or shoving stuff onto the heap and using a GC), at the end of the day the programmer will have to explicitly work around the stack frame no longer existing in most return statements. To which the only workaround would be doing some circumlocutions specifically to avoid the tail-call recognition.

Good example. It's a little clearer if desugared:

    {
       FooObject foo = FooObject(123);
       return FooObject::bar(&foo);
    }

The foo object needs to be somewhere that the address of it means something, because C++ passes 'this' by pointer.

The answer to this is to look at the current stack frame, shuffle everything that needs to stay alive to one end of it, move the stack pointer to deallocate the rest and then jump to bar, where bar is now responsible for deallocating N bytes of stack before it continues onwards.

It's a pain, sure, but in the scheme of compiler backends it's fine. They do very similar things on optimisation grounds, e.g. "shrink wrapping" means holding off on allocating stack in case an early return fires and you don't need it after all.

Though, when memory use is a function of escape analysis, which is a function of how much time you gave the compiler to work with, I do start to empathise with the make-the-programmer-do-it as the solution.

> where bar is now responsible for deallocating N bytes of stack before it continues onwards.

That doesn't really seem feasible in general? For a function with pointer parameters, the compiler would need to generate a new version for every possible stack offset left by its callers. And this could be indefinitely large, if, e.g., the caller builds a linked list on the stack before passing it to a function, or if the escape analysis fails to prove that some stack pointers are no longer in use.

Also, in C++/Rust/etc., the stack objects can also have destructors that must run, and so the callee must remember which destructors it needs to run before deallocating those objects and returning. One generic way to do this would be to also pass an address to a shim that calls the destructors in the correct order, but at that point you've literally just reinvented return addresses.

In general, it can make sense for a compiler to shrinkwrap the stack to an extent, and to automatically use tail calls when it can prove it makes no difference, but ultimately you're going to have to make the programmer do it one way or another. And if you're going to make the programmer manually track the lifetimes differently than they would for any other function call, it's much clearer to have an explicit tail call indication.

I am dense but don't see the issue. I would assume that functions being called with pointers to the stack of the currently executing function would be ineligible for tail recursion.