Tell HN: We are trying to get tail calls into the WebAssembly standard • Hacker News Board

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#11

Post by RHSeeger » Tue, Jul 12, 2022, 2:43 PM UTC

codedokode wrote: post #8

Recursion indeed can be useful when working with trees or graphs. However, I don't like using recursion instead of a loop, because you make reader to unroll your code in their head to understand what it really does. If you need to add two arrays of numbers, use loop or array addition, but don't use recursion as a replacement for a loop. Sadly the article uses a poor example, writing a useless factorial function. I ha…

> If you need to add two arrays of numbers, use loop or array addition

There are plenty of algorithms that make more sense when expressed using recursion. Iterating over a list of numbers generally isn't one of them. But walking a tree is a good example.

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#12

Post by jagger27 » Tue, Jul 12, 2022, 2:44 PM UTC

codedokode wrote: post #8

Recursion indeed can be useful when working with trees or graphs. However, I don't like using recursion instead of a loop, because you make reader to unroll your code in their head to understand what it really does. If you need to add two arrays of numbers, use loop or array addition, but don't use recursion as a replacement for a loop. Sadly the article uses a poor example, writing a useless factorial function. I ha…

Readability is really not a relevant factor for WebAssembly. Having tail-call recursion support is critical for the languages that compile to Wasm that use tail-calls themselves.

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#13

Post by traviswt » Tue, Jul 12, 2022, 2:45 PM UTC

labrador wrote: post #7

I'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.

Genuine question: is the goal to get something that is not achievable with JS/TS, or is the goal to simply avoid JS/TS?

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#14

Post by brrrrrm » Tue, Jul 12, 2022, 2:50 PM UTC

j-pb wrote: post #10

Sorry if I miss something obvious, but how is this not solvable by the compiler? I'm a huge functional programming evangelist, but high-level stuff like this does not belong in a low level language bytecode like WASM. Wasm should only care about two things: Security and Performance. With the standard blowing up like crazy we'll get neither. Worse, we'll cemenent the current duopoly of browser engines, because we'll m…

Edit: this is wrong.

For posterity my original comment was:

“From what I understand, tail calls can always (?) be lowered to while loops[1], which are expressible in WASM.

1. https://en.wikipedia.org/wiki/Tail_call#Relation_to_the_whil...

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#15

Post by labrador » Tue, Jul 12, 2022, 2:50 PM UTC

traviswt wrote: post #13

labrador wrote: post #7

I'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.

Genuine question: is the goal to get something that is not achievable with JS/TS, or is the goal to simply avoid JS/TS?

I really dislike JavaScript for a number of reasons. Dart gives me more distance from it than TypeScript. Of course, I can't avoid it, but I don't have to deal with many annoyances such as which 'this' is this? Should I put 'this' into a var called 'self' to be safe? That's just one example of how JavaScript and I don't get along. I understand some people have brains that think this way, but mine doesn't

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#16

Post by mibsl » Tue, Jul 12, 2022, 2:51 PM UTC

j-pb wrote: post #10

Sorry if I miss something obvious, but how is this not solvable by the compiler? I'm a huge functional programming evangelist, but high-level stuff like this does not belong in a low level language bytecode like WASM. Wasm should only care about two things: Security and Performance. With the standard blowing up like crazy we'll get neither. Worse, we'll cemenent the current duopoly of browser engines, because we'll m…

Compilers can easily lower tail recursion into loops, but not general tail calls between arbitrary (possibly unknown, indirect) functions.

The best they can do are trampolines, which come with a high performance cost.

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#17

Post by brrrrrm » Tue, Jul 12, 2022, 2:51 PM UTC

andsoitis wrote: post #3

> tail-calls has been proposed as an extension to the WebAssembly standard. Do you know why it wasn't in the standard to begin with? Even ECMAScript 6 mandates PTC (proper tail call) - article from 2016 on Webkit.org no less - https://webkit.org/blog/6240/ecmascript-6-proper-tail-calls-...

How is ECMAScript 6 (high level language) related to WebAssembly (low level target)?

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#18

Post by apignotti » Tue, Jul 12, 2022, 2:51 PM UTC

j-pb wrote: post #10

Sorry if I miss something obvious, but how is this not solvable by the compiler? I'm a huge functional programming evangelist, but high-level stuff like this does not belong in a low level language bytecode like WASM. Wasm should only care about two things: Security and Performance. With the standard blowing up like crazy we'll get neither. Worse, we'll cemenent the current duopoly of browser engines, because we'll m…

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 (and JavaScript) the call stack is observable via the .stack property of thrown exceptions.

Since an implicit conversion would be observable engines cannot simply optimize the problem away, and that is the reason why new opcodes (return_call/return_call_indirect) are actually required at the WASM level.

For the specific case of direct calls (return_call opcode) the compiler could solve the problem by inlining, with some luck. But for the case of return_call_indirect there is no other possible solution.

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#19

Post by mibsl » Tue, Jul 12, 2022, 2:52 PM UTC

brrrrrm wrote: post #14

j-pb wrote: post #10

Sorry if I miss something obvious, but how is this not solvable by the compiler? I'm a huge functional programming evangelist, but high-level stuff like this does not belong in a low level language bytecode like WASM. Wasm should only care about two things: Security and Performance. With the standard blowing up like crazy we'll get neither. Worse, we'll cemenent the current duopoly of browser engines, because we'll m…

Edit: this is wrong. For posterity my original comment was: “From what I understand, tail calls can always (?) be lowered to while loops[1], which are expressible in WASM. 1. https://en.wikipedia.org/wiki/Tail_call#Relation_to_the_whil...

Only tail recursion, not tail calls in general.

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#20

Post by apignotti » Tue, Jul 12, 2022, 2:53 PM UTC

brrrrrm wrote: post #14

j-pb wrote: post #10

Sorry if I miss something obvious, but how is this not solvable by the compiler? I'm a huge functional programming evangelist, but high-level stuff like this does not belong in a low level language bytecode like WASM. Wasm should only care about two things: Security and Performance. With the standard blowing up like crazy we'll get neither. Worse, we'll cemenent the current duopoly of browser engines, because we'll m…

Edit: this is wrong. For posterity my original comment was: “From what I understand, tail calls can always (?) be lowered to while loops[1], which are expressible in WASM. 1. https://en.wikipedia.org/wiki/Tail_call#Relation_to_the_whil...

This is possible, and trivial, when self-recursing: A -> A

If you have an A -> B, or A -> [indirect] call, that is not the case.