Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

news.ycombinator.com

Post reply on HN
Print view View original

201–210 of 300 posts

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

#201

Post by LAC-Tech »

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…

Not a compiler expert, but don't a lot of VMs for languages with TCO have a special tail call instruction? I know Luas VM does.

https://www.lua.org/source/5.4/lopcodes.h.html

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

#202

Post by yw3410 »

kragen wrote: post #152
light_hue_1 wrote: post #151

Earlier quoted context omitted.

> In languages like Scala, Java, C#, and Swift, it basically never happens. Scalaz and cats use tail calls extensively and wouldn't be possible without them.

How does that work on the JVM?

Scala only does single method tail recursion and rewrites it into a while loop. Cats and other libraries use a technique called trampolining which basically moves the frames to the heap (or a mixed technique where they do recurse a certain depth on the stack before switching to trampolining).

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

#203

Post by yw3410 »

naasking wrote: post #200
light_hue_1 wrote: post #149

Earlier quoted context omitted.

> But, as Scheme has demonstrated, once the virtual machine supports tail calls, a compiler can implement exceptions and cooperative multithreading by way of compiling to continuation-passing style. So this is not the beginning of a long series of extensions; it's Lambda the Ultimate Goto. Well to an extent. CPS can be extremely slow. Scheme shows that continuations will also be needed down the road. But yes, that's…

IIRC, one shot continuations can be made pretty efficient, effectively folding back into a single stack. If there's a simple way to safely express this in wasm that might be the right balance. If you want multishot continuations you'd need to explicitly clone the one-shot continuation.

I think koka uses a different approach for its multishot continuations than scheme as well.

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

#204

Post by haberman »

wyager wrote: post #167
dataflow wrote: post #126

Earlier quoted context omitted.

> Implementations are required to have every call consume some abstract resource towards exhausting some abstract finite limit If an implementation really wanted to, they could get around this by incrementing a "function call counter" that traps at, say, 2^64, rendering it effectively moot. I feel like these kinds of situations are where being practical might make more sense than being mathematically precise. Somethi…

> each function call must consume at least N bits of memory This is going to be a problem for any long-running recursive program. Why would we mandate this?

You don't want it to be implementation-specific whether tail call optimization is performed or not.

The nightmare scenario is that you spend months writing a program that works great in browsers A and B, but when you roll it out to prod it immediately fails in browser C, which doesn't perform TCO.

You only want to write code that depends on TCO if you can get a guarantee that TCO will be performed. This is the motivation for the clang:musttail attribute in C/C++ (I implemented musttail in Clang): https://clang.llvm.org/docs/AttributeReference.html#musttail

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

#205

Post by int_19h »

JohnHaugeland wrote: post #191
apignotti wrote: post #18

Earlier 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. I don't see why. Compilers are how tail calls are literally always implemented. It's not like there's hardware support. What makes this impossible? . > The issue is that to avoid stack blow-up you need the engine to recycle stack frames. I mean, what's stopping you from just implementing a trampoline? . > The problem with this is that in WebAss…

Compilers implement tail calls on architectures where you can JMP with impunity. Wasm is not such an architecture - it deals with calls and returns and call stack as concepts.

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

#206

Post by int_19h »

leoc wrote: post #171
pygy_ wrote: post #158

Earlier quoted context omitted.

My comment is about ES6 proper tail calls. WASM is another story

Graaagh, sorry.

It's not that much better. Apparently at least some of the idiosyncracies in the design of wasm, such as the lack of regular unstructured branches, is due to the internal implementation details of V8.

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

#207

Post by int_19h »

shadowgovt wrote: post #55
atwood22 wrote: post #36

Earlier quoted context omitted.

I highly recommend TypeScript. I don't really like the JS runtime, but, purely from a language point of view, TS is my favorite. Some cool features: 1) Type unions interface A { a: string; } interface B { b: string; } type C = A | B; const c: C = { a: 'a' }; 2) Type assertions if ('a' in c) { /* compiler knows c is of type A here */ } function isA(c: A): c is A { return 'a' in C } // compiler knows c is A if this ret…

TBH, TypeScript's type system really impressed me. It's the strongest type system of any language I regularly use (I haven't had time to unpack Rust yet, and I learned enough Haskell to decide Haskell didn't help me solve problems I had).

TS type system is Turing complete.

https://github.com/microsoft/TypeScript/issues/14833

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

#208

Post by matheusmoreira »

lmm wrote: post #177
nu11ptr wrote: post #89

Earlier quoted context omitted.

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 struct…

> 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

I think I understood that concept but it still seems a bit strange to me. Doesn't that imply a potentially infinite stack of function calls?

I've seen this idea in other functional program examples as well. Instead of having a sequence of instructions, they have a sequence of function calls. Instead of a function returning to the caller, it calls the next function in the program which is analogous to the virtual machine moving on to the next line of code in the sequence. It implies the program's structure and state is actually expressed within the function call stack and its frames. I admit I'm not sure what the purpose of this is.

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

#209

Post by int_19h »

AtNightWeCode wrote: post #128

You can use F# with WASM. I know F# convert recursive tail calls to loops but I understand this is another case. But shouldn't F# have the same problem?

F# compiles to CIL bytecode, which has a tail call instruction. I'm not sure what happens to that when CIL is compiled to wasm, but since there's no way to do a general translation, it probably just drops the tail part and makes it a regular call.

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

#210

Post by martinflack »

keithwinstein wrote: post #94
apignotti wrote: post #18

Earlier 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…

Heya, (1) Thank you for implementing this in JSC!! I hope they take it, it makes it into Safari, and the tail-call proposal advances. (2) I don't think you are exactly right about the call stack being observable via thrown exceptions. There's no formal spec for the v3 exceptions proposal yet, but in the documents and tests, there's nothing that would change in WebAssembly core to make the call stack observable. (Ther…

> The spec tests say: "Implementations are required to have every call consume some abstract resource

It's a nice detail for you to highlight, but surely that exists in the test spec specifically because the opcode spec doesn't mandate tail-call handling. If the latter did (a la Scheme), then the test spec would be updated to no longer have this note...?

Post reply on HN