14 ms·

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 d

• brrrrrm 4y ago
  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_while_statement” https://en.wikipedia.org/wiki/Tail_call#Relation_to_the_whil...
  • mibsl 4y ago
    Only tail recursion, not tail calls in general.
  • apignotti 4y ago
    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.
    • throwaway17_17 4y ago
      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()?
      • SamReidHughes 4y ago
        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.)
        • throwaway17_17 4y ago
          Thanks, that explains the trouble I was having. I was thinking about it without any consideration to calling-convention.
    • marcosdumay 4y ago
      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.
      • light_hue_1 4y ago
        You really can't. For example, what if those functions are in different modules or libraries? Tail calls are still supposed to work.
        • marcosdumay 4y ago
          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.)
• mibsl 4y ago
  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.
• apignotti 4y ago
  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.
  • j-pb 4y ago
    Fair enough. Sounds more like an issue with .stack being an observable property though. I've long suspected exceptions making it into WASM being it's million dollar mistake, and this further confirms it.
    • miloignis 4y ago
      I haven't messed with .stack, but on first impression I agree with you that it seems like a mistake. Even if it wasn't observable though, I think guaranteed tail-call elimination via either a new opcode or having it be a required property of regular calls in the spec (we already missed that ship, of course) is important. Without it, proper compilation and execution of some languages on wasm would depend on an otherwise invisible property of the engine - that is, tail call elimination isn't just an optimization, it's a critical aspect of language semantics that needs to be guaranteed to be relied on.
      • coliveira 4y ago
        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.
• deleted 4y ago
  [deleted]
• ufo 4y ago
  Wasm is too high level to implement your own tail calls. The WASM virtual machine handles the call stack & function calling convention, instead of being something that the code itself is responsible for. This means that the compiler can't implement tail calls; WASM doesn't allow a jump instruction in one function to jump into a different function. There are a bunch of reasons why WASM was designed to be higher level than native assembly. One is that they want it to be more compact to save bandwidth when downloading via the internet. Another is that they want to make it faster to compile down to native code; one way they do this is that the control flow is more structured, for example it forbids irreducible control flow graphs. There is also the matter of safety. WASM defines several validation constraints that are checked before the bytecode is run e.g.: the target of a jump instruction must be listed in labels list. If WASM were too low level, it wouldn't be possible to do the safety checks they want.
  • MikeHolman 4y ago
    The compiler absolutely can implement tail calls, I don't know why this keeps getting thrown around. Adding a high-level directive in the spec doesn't enable the compiler to do anything, it just enforces it. The only thing preventing it is browser vendors wanting the .stack property to stay well behaved, but that isn't required by the spec and certainly isn't relevant for non-browser targets.
    • light_hue_1 4y ago
      This is simply false. The compiler cannot implement tail calls correctly as it stands. You do not have access to modify the WASM stack and it's not present on the heap like it is for normal programs. No compiler tricks can enable tail calls in WASM at the moment (with the exception of trampolines which always work and are absurdly slow).
    • wtetzner 4y ago
      I think they're referring to a compiler that is targeting WASM, not a WASM-to-machine-code compiler.
    • xenadu02 4y ago
• miloignis 4y ago
  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 recursion of a function calling itself is simple enough and can be implemented in the compiler (and I did), but that's it, and not enough to correctly implement Scheme, for instance. I also want the wasm standard to remain as simple as possible, but this isn't a very complex addition and it is required for reasonable performance for both functional languages as well as C++20 features like coroutines, as mentioned by the article.
  • emmelaich 4y ago
    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.
    • thayne 4y ago
      It might be possible for a compiler to generate code that effectively does trampolining. But that would definitely have a performance cost.
    • convolvatron 4y ago
      'call' leaves return state on the stack, so if you use it to implement 'jump'. that has to be cleaned up. a trampoline is kinda the only choice if you are forced to run on a stack. go ahead and use 'call' as much as you like, but as the useless return addresses (and often locals) pile up on the stack, at some point you just return all the way back (or do a longjmp equivalent if your environment supports it) and start over again. this is measurably worse than just using jump, and as another posted pointed out, can introduce an O(n) term that doesn't need to exist. (edit: nevermind - if you are going through the forward direction n times then it doesn't change complexity to do a little more n work on the way out)
• jhgb 4y ago
  > I'm a huge functional programming evangelist, but high-level stuff like this does not belong in a low level language bytecode like WASM. A tail call is a jump. Jumps are not "high-level stuff". They're very simple instructions. If WASM can't do a jump, it is actually WASM that you can't call "a low level bytecode".
  • Spivak 4y ago
    WASM doesn't have jumps [1]. And it's not as low-level as you might expect. But even still you're assuming that low level means a specific model of computation a la PDP-11 that's as fictional as any other. https://webassembly.github.io/spec/core/syntax/instructions.html https://webassembly.github.io/spec/core/syntax/instructions....
    • jhgb 4y ago
      I never expected WASM to be low-level to begin with, so I don't believe it could ever possibly be "as low level as I might expect". Something like NaCl (the original one) perhaps could have been called "low level". > But even still you're assuming that low level means a specific model of computation a la PDP-11 that's as fictional as any other. I don't see how jumps are "fictional". Plenty of CPUs have them. Even actual stack CPUs, for that matter.
      • shadowgovt 4y ago
        Jump as a concrete implementation is easy to understand (it's just math on a program counter). But code is both a mechanical implementation and an abstract, often mathematical, concept. In the concept space, jump is as abstract as call, variable assignment, operator evaluation, etc. A Von Neumann machine is but one way to implement an abstract mathematical / conceptual machine. In the mathematical space, there's no "high level" vs. "low level," there's just "features a language has" vs. "features it does not." There are other abstractions that are actually harder / impossible to do correctly with jump in the language (stack unwinding comes to mind, which is why C++ solves the exceptions vs. setjmp / longjmp dichotomy by... Not solving it, and a program that uses both will just do something undefined. C++ without setjmp / longjmp would be a language with fewer undefined behaviors).
• kamaal 4y ago
  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.
  • convolvatron 4y ago
    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
    • kaba0 4y ago
      Could you point me to some further info on this?
      • convolvatron 4y ago
        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.
      • morenoh149 4y ago
        https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call
  • dan-robertson 4y ago
    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.
• munificent 4y ago
  > 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 have a single WASM executable containing multiple garbage collectors each managing their own objects. If you end up with cycles between those different managed heaps, you can end up in a situation where the GCs are unable to reclaim memory because they don't understand cross GC cycles. This is why Chrome did Oilpan [1]: so that they could more easily handle cycles between the DOM, JS heap, and (aspirationally at the time) Dart VM heap. A more general user-value proposition argument is that putting the GC in the WASM implementation means any improvements made to it are amortized across all managed languages that target WASM. Also, it makes applications written in managed languages and compiled to WASM smaller because they don't have to ship a runtime and GC with the app. [1]: https://chromium.googlesource.com/v8/v8/+/main/include/cppgc/README.md https://chromium.googlesource.com/v8/v8/+/main/include/cppgc...
  • smolder 4y ago
    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.
    • munificent 4y ago
      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.
      • 4y ago
• wruza 4y ago
  We shouldn't have GC, Exceptions or Tail calls in WASM, as long as the compiler can provide them. I’m not a compiler guy, but spent my time with runtimes closely, and can say that befriending GCs/RCs, exceptions, continuations, etc between them was my least favorite part. That said, wasm is already a potential target for different runtimes built with no common vm in mind, so interop headaches are imminent either way.
• marcosdumay 4y ago
  The problem here is that for security, your interpreted code can not do whatever it wishes on your memory. And for performances, you can't validate every small memory operation your code does. The result is a fairly high-level VM that doesn't export enough power for your program to implement GC or exceptions without sacrificing a lot of performance. Tail calls is a different matter, and there is a cost-benefit analysis for it.
• kragen 4y ago
  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 that's how it should have been designed. But that is not how Wasm works. The stack is not in Wasm's "linear memory". (This makes it much easier to compile access to local variables efficiently.) Calls, returns, and in a sense exceptions in Wasm are provided by the virtual machine at a fundamental level in a way that makes it impossible for a compiler targeting Wasm to implement tail calls, call/cc, or cooperative multithreading, except by compiling your entire program into a single function, which ruins the performance of existing Wasm implementations. 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.
  • light_hue_1 4y ago
    > 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 about it.
    • kragen 4y ago
      In theory CPS is very fast indeed, but of course our hero can easily collapse attempting to cross the chasm of the Sufficiently Smart Compiler. I suspect Chicken using CPS for everything is the main reason http://canonical.org/~kragen/urscheme http://canonical.org/~kragen/urscheme, which doesn't implement call/cc, is so much faster than Chicken.
    • naasking 4y ago
      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.
• gumby 4y ago
  Webassembly doesn't have a goto. There are some special cased scoped branches but if you read the spec you'll see they are so specific that you can't branch back to the head. (ex compiler dev)
• deleted 4y ago
  [deleted]
• usrn 4y ago
  WebAssembly is actually very high level. You need tail call support if you want to preserve the original structure of the program (which seems to be the intention.) I think you can get around it with eg CPS but then you'd get something more like traditional assembly.
• LAC-Tech 4y ago
  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 https://www.lua.org/source/5.4/lopcodes.h.html
• peterkelly 4y ago
  > Wasm should only care about two things: Security and Performance For languages that rely heavily on tail calls (functional languages in particular), good performance can only be achieved by having tail calls (or general-purpose jump instructions) as part of the instruction set. Excluding tail calls hurts performance for these languages as they have to resort to techniques like trampolines. As apignotti suggested, it's impossible for a compiler to generate efficient code for tail calls if the underlying instruction set does not support it.
• dan-robertson 4y ago
  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.
• jb1991 4y ago
  One need only look at the Clojure language to see how tail calls are not solved by a compiler.
• afiori 4y ago
  There are two compilers involved, Source to Wasm and Wasm to native (usually JIT). The second could easily optimize tail calls but it is required not to do so to increase reliability (all implementations need to agree which calls are tail calls that should be optimized and the simplest way to agree is to never do it) as otherwise a Wasm modules could work fine on an implementation and be unusable in another. The first compiler cannot, the only possibility is to use whole-program transformations that significantly degrade performances.