Earlier quoted context omitted.
These absolute bozos. A Web Assembler that can't do jumps. What a show.
My comment is about ES6 proper tail calls. WASM is another story
Graaagh, sorry.
Tell HN: We are trying to get tail calls into the WebAssembly standard
171–180 of 300 posts
Re: Tell HN: We are trying to get tail calls into the WebAssembly standard
#172Earlier quoted context omitted.
If it is a mistake depends on the point of view. What seems to be more important: exceptions of tail-call elimination? Most modern languages use exceptions in one way or another, conversely very few use the later feature. From the point of view of existing software it is way more important to optimize VMs for exception handling than for tail call elimination.
Maybe I'm naive and I surely don't know anything about the WASM spec, but aren't CPUs implementing both exceptions and tail call elimination as gotos (some jump machine code instruction) ? Exceptions might have to pop some frame, TCE doesn't.
[deleted]
Re: Tell HN: We are trying to get tail calls into the WebAssembly standard
#173Earlier quoted context omitted.
Not something compiling to WASM. Nor something compiling to JVM Bytecode.
If WASM and JVM Bytecode have a goto, then the compiler can use it. Anyway, if you've never read that paper i linked to above, i do believe you'll find it mind-blowingly cool stuff. not kidding.
They don't. That is literally the thing.
Edit: I should say, they don't have anything equivalent that can jump out of the method you are in.
Edit2: This is a bit more clear if you consider what it means for JVM bytecode to have a "return" set of instructions. Why does the bytecode need a return, if that is all managed by code that the compiler should handle anyway? You can look at the instructions here: https://en.wikipedia.org/wiki/List_of_Java_bytecode_instruct.... Note that it is the "jsr" instructions that let you do the equivalent of a long jump, and those specifically manipulate the stack. There is a "goto", but it is not valid to have that jump outside of the subroutine you are in.
Re: Tell HN: We are trying to get tail calls into the WebAssembly standard
#174Earlier quoted context omitted.
Not something compiling to WASM. Nor something compiling to JVM Bytecode.
If WASM and JVM Bytecode have a goto, then the compiler can use it. Anyway, if you've never read that paper i linked to above, i do believe you'll find it mind-blowingly cool stuff. not kidding.
WASM's version of a goto is a branch, it is constrained to a limited scope. This creates a problem for general tail call elimination but not for auto-recursive functions.
Auto-recursive functions can switch to using a branch or using another loop construct, and the compiler can generate that WASM code. The control structures available are described in the link below. Mutually recursive functions where only one is meant as the entry point could be similarly converted into WASM instructions but where the additional functions are, essentially, eliminated and inlined into the original caller (this may not be a good general solution, though). But general tail calls cannot be converted into gotos as you might with a more conventional assembly language since WASM branches cannot go to arbitrary instruction addresses.
The problem is that in a conventional assembly language, if you do TCE then the goto would go to (har har) the same (or nearly the same) point as a regular function call (maybe it skips the first few instructions depending on the calling conventions involved). With TCE and WASM you'd have to, essentially, inline the called function, or a variant of it, in order to be able to branch to the start of it. You cannot branch into a different function or to the start of a different function, you have to call the other function and then you have a single entry point. Which, in WASM as currently specified, means you have to use the current calling conventions which does not permit TCE.
https://www.w3.org/TR/wasm-core-1/#control-instructions%E2%9...
Re: Tell HN: We are trying to get tail calls into the WebAssembly standard
#175Earlier quoted context omitted.
> Tail-calls is fundamentally something that the compiler _cannot_ solve Possibly a stupid question as I haven't given this much thought, but I thought tail call elimination could be used to convert recursive calls in tail position into loops. Could a compiler not do this (like Scala does, for example)?
Tail-call elimination applies to any function which calls another function as the last action. Turning this into a loop is only possible when the function calls itself, not when it calls another function, and not (naively) when two functions call each other in the tail position.
You can turn it into a loop with a case statement inside if you collect the connected component of tail called functions and make those the cases. But it’s gonna be a big function.
You can split it up a bit if you use a trampoline, but then you lose some efficiency.
Re: Tell HN: We are trying to get tail calls into the WebAssembly standard
#176Earlier quoted context omitted.
Tail-calls is fundamentally something that the compiler _cannot_ solve. Trust me, if there was a way we would have avoided ourselves all this work. The issue is that to avoid stack blow-up you need the engine to recycle stack frames. You might argue that this could happen implicitly in the VM, with all the calls in tail position being automatically converted to tail-calls. The problem with this is that in WebAssembly…
> Tail-calls is fundamentally something that the compiler _cannot_ solve Possibly a stupid question as I haven't given this much thought, but I thought tail call elimination could be used to convert recursive calls in tail position into loops. Could a compiler not do this (like Scala does, for example)?
Scala has a weak version that handles self-tail-calls only. It causes significant trouble for e.g. iteratee/streaming libraries in Scala (like FS2) where you always have to use a trampoline.
Re: Tell HN: We are trying to get tail calls into the WebAssembly standard
#177Earlier quoted context omitted.
Tail-call elimination applies to any function which calls another function as the last action. Turning this into a loop is only possible when the function calls itself, not when it calls another function, and not (naively) when two functions call each other in the tail position.
Understood, but in practice how often does that really happen? (I'm aware of the contrived 'odd'/'even' example always given, but in the real world, I never had anything like that). Even when I wrote more functional code I rarely (if ever?) did that. 98-99% of the time it was the same function calling itself. Is your experience different?
Iteratees are immensely useful in practice and they involve doing this all the time (basically you do stream processing with a source and a sink that are mutually recursive - the source emits an element by calling the sink to process it, the sink processes it and then recurses into the source for the next element. It feels a bit forced if you describe it like that, but it gives you a model wiht lots of natural structure - it's the only approach to stream processing I've found where you can have a value that represents a stage in the middle of processing a stream (not just a 1:1 function but something that does grouping or suspension or the like) in a natural way, that you can then test standalone etc.).
Re: Tell HN: We are trying to get tail calls into the WebAssembly standard
#178Earlier quoted context omitted.
When you have a set of functions that may recourse into each other, you can convert them into a iterative one by doing a `while cond {switch function_selector {..}}` block. It's an ugly piece of code, but because of parsers, there is a huge amount of know how on it.
You really can't. For example, what if those functions are in different modules or libraries? Tail calls are still supposed to work.
If they are statically linked, it's not a problem, and since AFAIK wasm doesn't support dynamic linking, the only problem is on crossing security boundaries, that will be probably kept unsolved anyway. (IMO, this one is better left unsolved, it's to complicated a problem to require for interoperability.)
Re: Tell HN: We are trying to get tail calls into the WebAssembly standard
#179I'm using Blazor (C#) WebAssembly and I'm really wishing it could do DOM manipulation. My favorite tool for that is Dart, so I'm working on marrying C# and Dart for my client solutions.
What's C# giving you that Dart isn't, OOI? My impression is they're fairly similar languages. (Does Dart not have a WebAssembly backend?)
Re: Tell HN: We are trying to get tail calls into the WebAssembly standard
#180Earlier quoted context omitted.
Tail-calls is fundamentally something that the compiler _cannot_ solve. Trust me, if there was a way we would have avoided ourselves all this work. The issue is that to avoid stack blow-up you need the engine to recycle stack frames. You might argue that this could happen implicitly in the VM, with all the calls in tail position being automatically converted to tail-calls. The problem with this is that in WebAssembly…
> Tail-calls is fundamentally something the the compiler _cannot_ solve. How does the famous 1977 Guy Steele paper on compilers optimizing tail calls not apply? https://dl.acm.org/doi/10.1145/800179.810196
this paper espouses the use of jump+arguments instead of call. Wasm has no control transfer instruction that doesn't use the stack, nor does it have writable access to the stack pointer.