Throwing in my 2 cents to agree with apignotti - as someone who has implemented a compiler for a functional language that emits wasm, it is not possible to solve this performantly in the compiler.
Because wasm only has structured control flow & no way for user code to modify the wasm stack, there isn't any good way to tail call between multiple independent functions, particularly dynamic function calls. Simple tail recursion of a function calling itself is simple enough and can be implemented in the compiler (and I did), but that's it, and not enough to correctly implement Scheme, for instance.
I also want the wasm standard to remain as simple as possible, but this isn't a very complex addition and it is required for reasonable performance for both functional languages as well as C++20 features like coroutines, as mentioned by the article.
No worries - it depends on what your constraints and context are. It's fundamentally something a wasm-emitting compiler cannot solve performantly in general. You can use trampolines, as the sibling comments mention, but you'll take a heavy performance hit.
If we stretch things too far we'll end up in the "wasm is Turing-complete and thus can run anything" type of territory - if you're doing something performance intensive, say x86 virtualization like I believe apignotti is at Leaning Tech, I think it's fair to describe the problem as unsolvable by the compiler.
Thanks, that's pretty much what I suspected. I guess the issue is that the term (fundamental) is being used in a specific context assumed by experts in that area.
Obviously a Turing-complete system can simulate any other Turing-complete system. For example you could write an emulation of any system you like in WASM, and in the emulator you could have tail call optimization. Thus from context it should be apparent that we're talking about efficient implementations.
'call' leaves return state on the stack, so if you use it to implement 'jump'. that has to be cleaned up. a trampoline is kinda the only choice if you are forced to run on a stack. go ahead and use 'call' as much as you like, but as the useless return addresses (and often locals) pile up on the stack, at some point you just return all the way back (or do a longjmp equivalent if your environment supports it) and start over again.
this is measurably worse than just using jump, and as another posted pointed out, can introduce an O(n) term that doesn't need to exist. (edit: nevermind - if you are going through the forward direction n times then it doesn't change complexity to do a little more n work on the way out)
Because wasm only has structured control flow & no way for user code to modify the wasm stack, there isn't any good way to tail call between multiple independent functions, particularly dynamic function calls. Simple tail recursion of a function calling itself is simple enough and can be implemented in the compiler (and I did), but that's it, and not enough to correctly implement Scheme, for instance.
I also want the wasm standard to remain as simple as possible, but this isn't a very complex addition and it is required for reasonable performance for both functional languages as well as C++20 features like coroutines, as mentioned by the article.