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

101–110 of 300 posts

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

#101

Post by smolder »

munificent wrote: post #68
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…

> Reference types maybe. But I've yet to see a convincing argument as to why they are absolutely necessary. Are you referring to WASM GC here (or managed memory in general)? If so, I think the main compelling reason is interop. Without GC in underlying architecture, any managed language targeting WASM must include its own runtime and GC. If you then want to write a polyglot program using multiple languages, you now h…

I'm likely in the minority in my thinking, but I don't think targeting wasm with managed languages is such a great use case for wasm anyway, and so it wasn't worth building in GC to support. For the times you want to, something light like reference counting should be easy enough.

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

#102

Post by SamReidHughes »

throwaway17_17 wrote: post #77
apignotti wrote: post #20

Earlier quoted context omitted.

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.

I am genuinely asking, is your position that a compiler cannot convert: g(): a = 1+1; b = 2+a; print(b); return f() into code that does not allocate stack space and just reuses the frame allocated for g()?

It depends on the calling convention used -- whether it is caller clean-up or callee clean-up. With caller clean-up, the stack pointer is left below the argument list when the function returns. With callee clean-up, it gets popped above the argument list. You can perform tail calls naturally if it's callee clean-up. (With caller clean-up, a compiler might hypothetically pull off a tail call if the callee's argument list takes less memory, but it's not something you could add as a language feature.)

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

#103

Post by dwohnitmok »

nu11ptr wrote: post #89
samatman wrote: post #87

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

Happens a fair bit of time when parsing deeply nested structures (e.g. parsing deeply nested JSON structures) using mutually recursive parsers. I've generally resorted to either trampolining or explicit stacks.

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

#104

Post by aseipp »

nynx wrote: post #62
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…

.stack definitely seems like a mistake in the context of Webassembly. I’d be interested in seeing the justification for it.

Because people want a call stack when an exception is thrown, so they can print it out, just the same way they do in JavaScript and every other language.

EDIT: Also as another commenter mentioned, this is a property exposed by the VM engine to the host environment, not something directly observable from within WebAssembly itself.

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

#105

Post by munificent »

smolder wrote: post #101
munificent wrote: post #68

Earlier quoted context omitted.

> Reference types maybe. But I've yet to see a convincing argument as to why they are absolutely necessary. Are you referring to WASM GC here (or managed memory in general)? If so, I think the main compelling reason is interop. Without GC in underlying architecture, any managed language targeting WASM must include its own runtime and GC. If you then want to write a polyglot program using multiple languages, you now h…

I'm likely in the minority in my thinking, but I don't think targeting wasm with managed languages is such a great use case for wasm anyway, and so it wasn't worth building in GC to support. For the times you want to, something light like reference counting should be easy enough.

I'm biased since I work on a managed language that targets the web, but I strongly believe that it is a great use case for WASM.

Most programs targeting WASM are client-side apps with rich user experiences and I believe all but a small fraction of users would be better served implementing rich UIs in managed languages. Doing UI work in C++ (which I have done plenty of) is a special exercise is pain for almost no upside. GC is great.

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

#107

Post by convolvatron »

kaba0 wrote: post #98
convolvatron wrote: post #74

Earlier quoted context omitted.

tail calls are so fundamental that its trivial to build a call-push, return-pop stack calling protocol on top of them, but not the converse

Could you point me to some further info on this?

sorry, its kind of ... basic?

the kind of generalized tail call I'm talking about is generally referred to as a continuation. its easiest to think of it as a jump. so you can imagine that if we have jump and a stack register, we can push+jump and thats the same as 'call'. we can pop+jump and thats the same as 'return'. since 'call' and 'return' have side effects, we cant really use them to replace jump.

so thats really straightforward, but things do get a bit screwy. if we can support arbitrary jumps, and the frame storage (arguments + locals) cant necessarily go on a stack because our frames might have arbitrary liftimes, so we cant reclaim them in stack order.

so in a scheme for example we just pull in a gc and track references to these closures and dust our hands off with a smirk. if that doesn't work for you then you have to adopt some kind of framework that lets you know explicitly when these can be released. reference counting is a poor choice here because these references between frames can easily be cyclic.

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

#108

Post by emmelaich »

miloignis wrote: post #27
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…

Throwing in my 2 cents to agree with apignotti - as someone who has implemented a compiler for a functional language that emits wasm, it is not possible to solve this performantly in the compiler. Because wasm only has structured control flow & no way for user code to modify the wasm stack, there isn't any good way to tail call between multiple independent functions, particularly dynamic function calls. Simple tail r…

Can you please clarify? apignotti wrote

>Tail-calls is fundamentally something that the compiler _cannot_ solve.

You write

>it is not possible to solve this performantly in the compiler

So is it fundamental or not? Apologies if the question seems direct or rude.

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

#109

Post by leoc »

pygy_ wrote: post #6
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-...

The standard mandates it, and the V8 team implemented it, shipped it behind a flag, then unshipped based on reasons that initially seemed and ultimately were proven fuddy, when WebKit shipped PTC, and the world didn’t fall down. The reason actual why it was withdrawn is that it would have required expensive changes to Microsoft’s Chakra (the calling conventions were incompatible). Then Edge died... and Google didn’t…

These absolute bozos. A Web Assembler that can't do jumps. What a show.

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

#110

Post by retrac »

nu11ptr wrote: post #89
samatman wrote: post #87

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

In functional languages, recursive data structures are often most naturally walked with recursive functions. Languages like Haskell and ML take this to its natural conclusion and use it systematically. For example, a linked list. Here's how the Haskell "last" function, to get the last item in a linked list, is implemented in the standard library:

    last [x]                =  x
    last (_:xs)             =  last xs
    last []                 =  errorEmptyList "last"
If given a list with a single item, return that item. If given a list with two or more items, call itself with the list minus its head. If given an empty list, throw an error.
Post reply on HN