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

241–250 of 300 posts

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

#241

Post by dan-robertson »

martinflack wrote: post #210
keithwinstein wrote: post #94

Earlier quoted context omitted.

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

The proposed spec is to have an explicit tail call instruction separate from the regular call instruction for which resources must be used.

I think this would be the correct design even if tail calls were desired from the start. It makes for a better debugging experience and allows language implementations more control. (A trend in some functional languages is to require explicit annotation when tail recursion is desired, both to improve debugging for regular functions and to allow the compiler to check that you don’t accidentally stop being tail-recursive)

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

#242

Post by dan-robertson »

kragen wrote: post #129
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…

Your concern with burgeoning standards reinforcing the browser duopoly is well-founded, but unfortunately you're sticking your stake in on the wrong side of the dragon here. It sounds like you're confused about how Wasm works, and you imagine that it's like a normal assembly language, with calls and returns implemented by the compiler using instructions that push and pop a stack in memory. You're probably right that…

The purpose of the wasm rules (eg declaring variables/function args instead of having push/pop operations) is to allow the compiler to efficiently determine that functions follow the calling convention and won’t be able to mess with non-wasm functions they call or are called by. It means that you can put return pointers on the stack without the wasm being able to ever touch return pointers.

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

#243

Post by dan-robertson »

kamaal wrote: post #47
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…

I think its Rich Hickey who said something to the effect that tail calls are so fundamental that the underlying platform should be providing them.

And yet Clojure doesn’t have general tail calls (it has recur which allows something like tail calls so long as they are non-mutually recursive) and seems to do ok.

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

#244

Post by diarrhea »

jacobmischka wrote: post #24

Neat! This proposal caused me a lot of headaches, mechanizing its specification was the primary contribution of my Master's thesis a couple years ago[1]. I forgot until rereading it just now, but doing so caught a typo in the proposal specification[2], my extremely minor contribution to advancing WebAssembly. Glad to see it finally moving forward after stalling for so long! Excellent work! [1]: https://github.com/jac…

That might be the shortest (in word count) Master's thesis I have ever seen!

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

#245

Post by morenoh149 »

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?

https://en.wikipedia.org/wiki/Tail_call

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

#246

Post by miclill »

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…

Thanks for clarifying. What is this PTC you mention?

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

#247

Post by dan-robertson »

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…

An example of a tail-call that can easily be compiled to a loop is:

  let sum list =
    let rec loop a = function
      | [] -> a
      | x::xs -> loop (a+x) xs
    in
    loop 0 list
An example of a more tricky case which may be compiled to a loop is the following mutual recursion:

  let rec even_then b n =
    if n = 0 then b else odd_then (not b) (n - 1)
  and odd_then b n =
    if n = 1 then b else even_then (not b) (n - 1)
And this may be compiled either to a loop which uses a trampoline (or switch on the next function to run, which is a bit like a static trampoline) or to two separate functions that duplicate some code and are implemented as loops. A simple way this might get compiled is:

  fn even_then_or_odd_then(which_function, b1, n1, b2, n2) {
    loop {
      match(which_function) {
        Even => {
          if n1 = 0 { return b1 }
          else {
            b2 = not(b1);
            n2 = n1 - 1;
            which_function = Odd;
          }
        },
        Odd => { similar }
      }
    }
  }
  
  fn even_then(b,n) {
    even_then_or_odd_then(Even, b, n, null, null)
  }
  
  ...
An example of a tail-call that is hard to compile would be in a parser combinator library for example:

  let parse_both p1 p2 =
    fun buf pos success ->
      p1 buf pos (fun pos r ->
        p2 buf pos (fun pos r2 ->
          success pos (r, r2)))
  ;;
(As I’ve written it this design has some issues but they aren’t so relevant). Here it is important to be able to tail-call a function that you take as an argument (e.g. you want the parser p2 to tail call the success callback you give it, and if you parse and arbitrary-length list you want to do it tail-recursively). Speaking more generally, general tail-calls are like a safe long-distance goto. Wasm doesn’t have goto and so a whole-program transformation (or a trampoline[1] which may have performance issues) is required to support tail-calls.

[1] A trampoline means that functions effectively return continuations except typically they call their continuations (up to some max number of times) and only occasionally return them to the trampoline (which pops everything off the stack) which immediately calls the continuation again. But implementing continuation passing style this way is pretty slow.

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

#248

Post by skrebbel »

apignotti wrote: post #18
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…

Wouldn't it be much more productive to do a campaign to get `.stack` out of WASM?

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

#249

Post by jb1991 »

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…

One need only look at the Clojure language to see how tail calls are not solved by a compiler.

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

#250

Post by pygy_ »

miclill wrote: post #246
pygy_ wrote: post #6

Earlier quoted context omitted.

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…

Thanks for clarifying. What is this PTC you mention?

“Proper tail calls”, i.e. tail calls as specified for ES6
Post reply on HN