-
Notifications
You must be signed in to change notification settings - Fork 13
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Expand motivation section of overview #19
Comments
It's also not possible to emulate |
I'll just talk for myself because I'm not super knowledgeable here. Understood that tail recursion is different than general tail calls, and that tail recursion is more amenable to compiler transformations. Are there no feasible compiler transformations for general direct tail calls? That's probably the detail I am missing. |
Implementing tail calls was issue #1 for the JVM, back before there was issue trackers. Never got fixed though. |
There are only non-local transformations, and they are either very expensive (trampolining through exception handlers, like @fgmccabe is alluding to, provided you even have them) or only practical in simple cases (inlining the callee) or require whole program rewriting (defunctionalisation) to eliminate the calls, merging everything into very large functions (which may hit implementation limits and is incompatible with separate compilation). |
Okay, that is the detail I was missing. I think a paragraph about this in the overview would be helpful, it's definitely one of the FAQs I get about wasm. |
More background for @eqrion (adds nothing new to this issue, but provides a little more context): In 2018, when I was working on compiling a functional language to wasm, I asked @TerrorJack for advice on tail calls and about what they did in https:/tweag/asterius (Haskell to wasm compiler). His response was:
I also contacted @msprotz who responded:
|
As it stands, Js_of_ocaml is able to translate mutually-recursive functions into loops, but it can not do the same for recursive calls to dynamically-determined functions, like continuation parameters. This means that libraries like angstrom (which use continuations for running parser-combinators) to have separate code-paths for js_of_ocaml that implement a trampoline. |
Some feedback I've heard about this proposal is that the motivation is unclear for why this has to be an operation in core wasm.
Specifically I've had it asked, "why can't this be done by compilers targeting wasm"? I don't think the motivation section goes into this at all, and I think that would be useful.
The best answer I've been able to give is that this is not possible for
return_call_indirect
, which is basically an indirect jump and has no close analogue in core wasm. I'm not as knowledgeable though about the general case of a functional language wanting to compile to wasm and the feasibility of performing tail call elimination in a compiler. I think for posterity it would be nice to have something to point to on this.The text was updated successfully, but these errors were encountered: