Tail Calls

[RyanLamansky]

I'd like to see an instruction for tail calls ( https://en.wikipedia.org/wiki/Tail_call ). The attractive feature of tail calls is that the called function's stack frame replaces the caller's, instead of being appended.

This makes it much easier to implement functional languages that make heavy use of recursion, so much so that standard calls would experience a stack overflow. Simple recursions can be converted to loops, but this becomes very complicated when there's a sequence of functions that call each other recursively.

It would also be useful for WASM-targetting compilers to use a tail call as an optimization for any call that is immediately followed by a function exit.

[lukewagner]

This is indeed already on the future features list.

[RyanLamansky]

Ah, it is. I didn't notice it and didn't find it when I searched the issues. As much as I'd like to see it in MVP, I realize it's likely to be a future release. How are backlog items like that tracked so I can use the "+1" process on it?

[lukewagner]

That's a good question; we don't have that at the moment. As the MVP draws to a close, I think we'll want to put planned batches of new features on roadmap.md but that's not something you can +1. Maybe it makes sense to have an appropriately-tagged issue (like this one) open for each future feature and linked to by FutureFeatures.md to host discussion on that future feature until it begins active development?

[jfbastien]

@RyanLamansky are you willing to champion this? It would be a great post-MVP addition.

[piranna]

Up to some degree, tail calls can be easily detected, they will be always a call instruction followed by a return or a function end instruction... There's no need to add new opcodes.

[RyanLamansky]

@jfbastien Can you provide more clarity on the "champion" role?

I do want to see this happen, but I'm actually more passionate about #937, which I think has broader applications: there isn't a clean way to return a low-complexity-but-greater-than-8-bytes structure like a GUID or Fixed128 in the current WASM spec, for instance.

[jfbastien]

@jfbastien Can you provide more clarity on the "champion" role?

Sure thing! I should probably document this for meetings anyways.

Briefly, the idea of a champion is someone who's willing to propose an initial draft of what a feature would look like, and drive it forward. That often implies getting consensus from other interested parties (here VM developers as well as potential users of varied languages targeting the VM), as well as often providing a sample implementation.

A champion would often have to show that something is useful, usable in non-trivial context, and performs well without unexpected gotchas or overheads.

It's a pretty common thing in standards bodies to champion features. Sometimes, someone will start off a proposal and then pick up helpers along the way or hand off champion-ship to someone else. Ideas without champions are just that: ideas. It's not that they're bad, it's just that nobody wants to drive them forward so they stall. Everyone can agree we want a thing, but if nobody drives it then it won't go anywhere.

One of my roles as chair is to make sure ideas get moved forward, and the right people are involved. That usually requires finding champions for each idea, and helping them be as productive as need be.

[RyanLamansky]

@jfbastien Thanks for the detailed explanation 🙂

as well as often providing a sample implementation.

This... could be a challenge. I don't work for a browser vendor and my own .NET Core-based WASM implementation is still too primitive to be seriously considered as an implementation. .NET does support explicit tail calls (needed for F#), so I suppose I could create a focused example that does this and little else...

@piranna Today in WASM, a tail call is nothing more than an optional optimization. If you're compiling a functional language that favors loops via recursion, a tail call is absolutely mandatory to prevent a near-instant stack overflow. It needs to be a non-backward-compatible enhancement to prevent WASM 1.0 implementations from trying to run it.

[jfbastien]

This... could be a challenge. I don't work for a browser vendor and my own .NET Core-based WASM implementation is still too primitive to be seriously considered as an implementation. .NET does support explicit tail calls (needed for F#), so I suppose I could create a focused example that does this and little else...

Especially for tail call this may be something folks think is required: ES6 tail call aren't in all browsers yet and I'm wary of WebAssembly tail call being in the same boat. Explicit may be easier. There's also the question of module to modules tail calls, and whether there should be any restrictions.

[sunfishcode]

(As a minor clarification, wasm does not permit implementations to perform implicit tail-call optimization, in general. See the comments and tests here, for example.)

[rossberg]

As with multiple returns, I'm happy to champion this (soon).

[RyanLamansky]

(@sunfishcode Getting into the technical weeds now, but as written, the optimization is permitted as long as its effect is not observable. Code that will trigger a stack overflow must do so, however if the compiler has enough information to know with 100% certainty the stack wouldn't overflow if tail calls were used, it may choose to use them.)

[rossberg]

See https://github.com/WebAssembly/tail-call/ for the proposal.

[diakopter]

(@sunfishcode Getting into the technical weeds now, but as written, the optimization is permitted as long as its effect is not observable. Code that will trigger a stack overflow must do so, however if the compiler has enough information to know with 100% certainty the stack wouldn't overflow if tail calls were used, it may choose to use them.)

nitpick: should be "if tail calls were not used"