10 ms·

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 i

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.
    - bordercases 4y ago
    - miloignis 4y ago
      Well wasm doesn't have exceptions right now either! The exceptions proposal is also in phase 3, like tail-calls. Right now wasm just supports traps, which can't be caught or inspected from within wasm code, and don't actually need to record stack frames (but the JavaScript host does in web browsers). I'm not sure what benefit exposing the wasm part of the stack for traps gives the JavaScript host side except perhaps easing debugging? (though that is important, I think there are other valid solutions for that) To be clear, I do want wasm to support the major language use cases, and I think implementing exception support is a good (though tricky, see the exceptions proposal) idea.
      - j-pb 4y ago
        After reading the discussion, I think I'm much more in favour of adding tail calls, than adding exceptions. Actually I wonder if one couldn't adapt the tail-call mechanism slightly to also serve as an exception mechanism. I think you could do both by allowing `br` to jump to an arbitrary label previously established. An exception then simply being a "tail-call" that unwinds more than one stack frame, and calls into the "catch". Not sure how well JITable this would be, but I think an arbitrary backjump and call should be mostly fine in terms of control flow?
      - the_mitsuhiko 4y ago
        Would be interested in what other solutions you envision. In production error reporting to services like Sentry relies on getting access to a stack and unlike a native runtime there is nothing one could do to create a stack without the engine’s support.
        miloignis 4y ago
        If you control the compiler, you don't need the engine's support for exceptions (though you might want it for performance reasons) - emitting function prologues and epilogues that maintain debugging information like a call stack (or call trace in a ring buffer like some Schemes) would be one way. I actually did this in my purely functional language, but had it off by default for performance reasons - if you hit an error at runtime, the debugging code would re-execute from the last checkpoint with debugging information turned on to construct the missing debug data, something I could only do because the language is side-effect free.
- dataangel 4y ago
  The point is to run compiled langs like C++ though. Technically x86, ARM, etc don’t directly support exceptions either, but I assume WASM also has to define an ABI between WASM modules, and ABIs usually are exception aware. Or is it some other reason they got added?
nynx 4y ago
.stack definitely seems like a mistake in the context of Webassembly. I’d be interested in seeing the justification for it.
- aseipp 4y ago
  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.
nu11ptr 4y ago
> Tail-calls is fundamentally something that the compiler _cannot_ solve Possibly a stupid question as I haven't given this much thought, but I thought tail call elimination could be used to convert recursive calls in tail position into loops. Could a compiler not do this (like Scala does, for example)?
- samatman 4y ago
  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.
  - nu11ptr 4y ago
    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?
    - jhgb 4y ago
      For example pretty much any higher-order function that wants to do some decision-making and then hand over execution to one of several functions provided will want to hand over execution by means of a tail call, so that it doesn't unnecessarily change stack complexity for whatever algorithm is being run around that piece of code.
    - lilyball 4y ago
      State machines can often be implemented with a set of functions that each handle a single state and then tail-call into the function for the next state.
      - kevin_thibedeau 4y ago
keithwinstein 4y ago
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. (There's no ".stack property" that would be added to Wasm itself.) It's true that the proposal amends the JS API (but only the JS API) to describe a traceStack=true option; from Wasm's perspective I understand that's just an ordinary exception that happens to include an externref value (just like any other value) to which Wasm attaches no special significance. The Web-based engines can attach an informative stack trace if they want, but there's no requirement preventing frames from having been optimized out. The non-Web engines won't have to think about this. (3) I think the real reason that a Wasm engine can't implicitly make tail calls proper is that the spec tests forbid it, basically because they didn't want the implementation base to fragment by having some engines perform an optimization that changes the space complexity of a program, which some programs would have started to depend on. (The spec tests say: "Implementations are required to have every call consume some abstract resource towards exhausting some abstract finite limit, such that infinitely recursive test cases reliably trap in finite time. This is because otherwise applications could come to depend on it on those implementations and be incompatible with implementations that don't do it (or don't do it under the same circumstances.)") But the issue is much weaker than "call stack is observable" -- it's more like "infinite recursion must trap eventually, but it can be nondeterministic when." More discussion here: https://github.com/WebAssembly/spec/issues/150 https://github.com/WebAssembly/spec/issues/150
- dataflow 4y ago
  > 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. Something like "each function call must consume at least N bits of memory" or something concrete like that. Or heck, "implementations may not perform tail-call optimization" or even "implementations must be able to reconstruct the full logical call stack at any point".
OskarS 4y ago
I don't quite get your point here. Suppose I write a compiler to compile Scheme to WASM. I would have write it so that it does proper tail calls, otherwise it wouldn't be Scheme. What's stopping me? Would the browsers not run the code? Like, yeah, it would change .stack, but who cares? Same thing applies, I think, to any other language compiled to WASM. C/C++ compilers regularly inline huge amounts of the code when optimizations are turned on, as well as do tail-call optimization. I haven't tried, but I would assume that they do that for WASM just as they do for x86 or ARM or whatever other build target I choose. As long as my users are ok with this (and they presumably are, otherwise they wouldn't turn optimizations), what's the problem, exactly?
- marshray 4y ago
  > yeah, it would change .stack, but who cares? You might enjoy participating in an interoperable standardization process sometime.
  - OskarS 4y ago
    I don't mean to minimize anybody's work, I'm genuinely curious about why it can't be done. Like, what's stopping me from making a compiler that optimizes tail calls? For instance: the C and C++ standards have very strict rules for how to handle floating point math, and compilers aren't allowed to deviate from that according to the standard. Which turns off all sorts of cool optimizations you can do. But of course, all modern compilers implement some version of "-ffast-math" which turns off those rules and allows for the optimizations. It's no longer standard C/C++, but that doesn't mean that switch can't exist. The compiler is a computer program, it can output anything it wants, regardless of what the standard says. Nobody is going to go to jail because you turned on -ffast-math. The code will still run just fine. So, my question is, why can't you write a compiler with an option that's like "I don't particularly care that .stack changes, do the tail call optimization". A -ffast-math, but for tail calls. Is there a technical reason why you can't do this?
    - light_hue_1 4y ago
      > So, my question is, why can't you write a compiler with an option that's like "I don't particularly care that .stack changes, do the tail call optimization". A -ffast-math, but for tail calls. Is there a technical reason why you can't do this? Because the stack in web assembly is only observable. It is implicit. You cannot modify it yourself. There are simply no instructions for this. The WASM stack is not present on the WASM heap, like it is for your physical machine. You simply cannot express tail calls with the instruction set given to you by WASM right now. No hacks are possible.
anfilt 4y ago
What? Compilers handle tail calls all the time even in languages like C and higher level functional languages. Its just a jmp? Does the wasm VM not have a jmp instruction?!?
- Jtsummers 4y ago
  https://www.w3.org/TR/wasm-core-1/#control-instructions%E2%91%A0 https://www.w3.org/TR/wasm-core-1/#control-instructions%E2%9... Those are the list of control instructions. WASM seems to be a bit of a misnomer as it is not an assembly language in the more conventional sense. It is a structured language and provides a limited goto in the form of branches (in the section I linked to) which are constrained to a particular scope. If you compile your whole program so it fits within a single function, then yes you can use this to do universal tail call elimination. Otherwise you are restricted to doing TCE only on auto-recursive functions and maybe mutually recursive functions if you have a single entry point (of the set of functions) and decide to optimize by moving all of them into one function. Otherwise, function calls are performed using one of the two call instructions which (presently) implement a behavior more like conventional call stack/stack frames. This proposal would add a second pair of call instructions that a compiler can emit which the WASM runtime would then optimize (by not generating new stack frames).
  - anfilt 4y ago
    So no self modifying code either, since it seems like I can't just get the address of a function and modify the byte code?
    - shadowofneptune 4y ago
      That would be used most often for malware, unfortunately.
jjtheblunt 4y ago
> Tail-calls is fundamentally something the the compiler _cannot_ solve. How does the famous 1977 Guy Steele paper on compilers optimizing tail calls not apply? https://dl.acm.org/doi/10.1145/800179.810196 https://dl.acm.org/doi/10.1145/800179.810196
- taeric 4y ago
  My guess is that this is assuming that the compiler can rewrite a return into a jump. That is, these compilers have control over the stack on the machine.
  - jjtheblunt 4y ago
    compilers always have control over the stack on the machine: they generate the code which realizes the notion of a stack (and happily usually have dedicated registers to use for that generated code)
    - taeric 4y ago
      Not something compiling to WASM. Nor something compiling to JVM Bytecode.
      - jjtheblunt 4y ago
        If WASM and JVM Bytecode have a goto, then the compiler can use it. Anyway, if you've never read that paper i linked to above, i do believe you'll find it mind-blowingly cool stuff. not kidding.
        taeric 4y ago
        They don't. That is literally the thing. Edit: I should say, they don't have anything equivalent that can jump out of the method you are in. Edit2: This is a bit more clear if you consider what it means for JVM bytecode to have a "return" set of instructions. Why does the bytecode need a return, if that is all managed by code that the compiler should handle anyway? You can look at the instructions here: https://en.wikipedia.org/wiki/List_of_Java_bytecode_instructions https://en.wikipedia.org/wiki/List_of_Java_bytecode_instruct.... Note that it is the "jsr" instructions that let you do the equivalent of a long jump, and those specifically manipulate the stack. There is a "goto", but it is not valid to have that jump outside of the subroutine you are in.
JohnHaugeland 4y ago
> 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 WebAssembly (and JavaScript) the call stack is observable via the .stack property of thrown exceptions. Okay? This seems fine to me. What makes this a problem?
- naasking 4y ago
  Trampolines are a hack that penalizes the performance of any language that uses tail calls a lot, like functional languages (scheme, lisp, Haskell, etc). You could also handle exceptions manually too, without VM support, but that too would incir considerable overhead.
- int_19h 4y ago
  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.
- dragonwriter 4y ago
  > Compilers are how tail calls are literally always implemented. WASM doesn't have the same set of operations as a typical CPU. It's not something a compiler to WASM can do.
aaron_m04 4y ago
Is this the reason clojure added the recur form? IIRC, the JVM doesn't support tail calls because Java doesn't need it. https://clojuredocs.org/clojure.core/recur https://clojuredocs.org/clojure.core/recur
skrebbel 4y ago
Wouldn't it be much more productive to do a campaign to get `.stack` out of WASM?
randomswede 4y ago
There are probably WebAssembly-specific things I am unaware of. So, the following is a general "TCO" discussion. I normally consider TCO something that is a compiler feature. Replace a call to the head of yourself, with a jump (possibly to just after the "pull the arguments from the call stack to where the code wants it" prologue), making sure that the correct locals are present where they need to be. Well, that's for self-TCO. General TCO is definitely trickier (probably requires juggling stack allocations so as to ensure that the tail-called function has enough space for all that it needs).
WastingMyTime89 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. I have been out of the loop regarding compilers development for a long time but what prevents you from converting your program to CPS and using a trampoline like some LISP still do?
- antonvs 4y ago
  A trampoline is a workaround that wastes memory and time. The idea is to avoid that so that you can use function calls efficiently.

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.
  - bordercases 4y ago
  - miloignis 4y ago
    Well wasm doesn't have exceptions right now either! The exceptions proposal is also in phase 3, like tail-calls. Right now wasm just supports traps, which can't be caught or inspected from within wasm code, and don't actually need to record stack frames (but the JavaScript host does in web browsers). I'm not sure what benefit exposing the wasm part of the stack for traps gives the JavaScript host side except perhaps easing debugging? (though that is important, I think there are other valid solutions for that) To be clear, I do want wasm to support the major language use cases, and I think implementing exception support is a good (though tricky, see the exceptions proposal) idea.
    - j-pb 4y ago
      After reading the discussion, I think I'm much more in favour of adding tail calls, than adding exceptions. Actually I wonder if one couldn't adapt the tail-call mechanism slightly to also serve as an exception mechanism. I think you could do both by allowing `br` to jump to an arbitrary label previously established. An exception then simply being a "tail-call" that unwinds more than one stack frame, and calls into the "catch". Not sure how well JITable this would be, but I think an arbitrary backjump and call should be mostly fine in terms of control flow?
    - the_mitsuhiko 4y ago
      Would be interested in what other solutions you envision. In production error reporting to services like Sentry relies on getting access to a stack and unlike a native runtime there is nothing one could do to create a stack without the engine’s support.
      - miloignis 4y ago
        If you control the compiler, you don't need the engine's support for exceptions (though you might want it for performance reasons) - emitting function prologues and epilogues that maintain debugging information like a call stack (or call trace in a ring buffer like some Schemes) would be one way. I actually did this in my purely functional language, but had it off by default for performance reasons - if you hit an error at runtime, the debugging code would re-execute from the last checkpoint with debugging information turned on to construct the missing debug data, something I could only do because the language is side-effect free.
dataangel 4y ago
The point is to run compiled langs like C++ though. Technically x86, ARM, etc don’t directly support exceptions either, but I assume WASM also has to define an ABI between WASM modules, and ABIs usually are exception aware. Or is it some other reason they got added?

nynx 4y ago

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

aseipp 4y ago
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.

nu11ptr 4y ago

> Tail-calls is fundamentally something that the compiler _cannot_ solve Possibly a stupid question as I haven't given this much thought, but I thought tail call elimination could be used to convert recursive calls in tail position into loops. Could a compiler not do this (like Scala does, for example)?

samatman 4y ago
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.
- nu11ptr 4y ago
  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?
  - jhgb 4y ago
    For example pretty much any higher-order function that wants to do some decision-making and then hand over execution to one of several functions provided will want to hand over execution by means of a tail call, so that it doesn't unnecessarily change stack complexity for whatever algorithm is being run around that piece of code.
  - lilyball 4y ago
    State machines can often be implemented with a set of functions that each handle a single state and then tail-call into the function for the next state.
    - kevin_thibedeau 4y ago

keithwinstein 4y ago

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. (There's no ".stack property" that would be added to Wasm itself.) It's true that the proposal amends the JS API (but only the JS API) to describe a traceStack=true option; from Wasm's perspective I understand that's just an ordinary exception that happens to include an externref value (just like any other value) to which Wasm attaches no special significance. The Web-based engines can attach an informative stack trace if they want, but there's no requirement preventing frames from having been optimized out. The non-Web engines won't have to think about this. (3) I think the real reason that a Wasm engine can't implicitly make tail calls proper is that the spec tests forbid it, basically because they didn't want the implementation base to fragment by having some engines perform an optimization that changes the space complexity of a program, which some programs would have started to depend on. (The spec tests say: "Implementations are required to have every call consume some abstract resource towards exhausting some abstract finite limit, such that infinitely recursive test cases reliably trap in finite time. This is because otherwise applications could come to depend on it on those implementations and be incompatible with implementations that don't do it (or don't do it under the same circumstances.)") But the issue is much weaker than "call stack is observable" -- it's more like "infinite recursion must trap eventually, but it can be nondeterministic when." More discussion here: https://github.com/WebAssembly/spec/issues/150 https://github.com/WebAssembly/spec/issues/150

dataflow 4y ago
> 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. Something like "each function call must consume at least N bits of memory" or something concrete like that. Or heck, "implementations may not perform tail-call optimization" or even "implementations must be able to reconstruct the full logical call stack at any point".

OskarS 4y ago

I don't quite get your point here. Suppose I write a compiler to compile Scheme to WASM. I would have write it so that it does proper tail calls, otherwise it wouldn't be Scheme. What's stopping me? Would the browsers not run the code? Like, yeah, it would change .stack, but who cares? Same thing applies, I think, to any other language compiled to WASM. C/C++ compilers regularly inline huge amounts of the code when optimizations are turned on, as well as do tail-call optimization. I haven't tried, but I would assume that they do that for WASM just as they do for x86 or ARM or whatever other build target I choose. As long as my users are ok with this (and they presumably are, otherwise they wouldn't turn optimizations), what's the problem, exactly?

marshray 4y ago
> yeah, it would change .stack, but who cares? You might enjoy participating in an interoperable standardization process sometime.
- OskarS 4y ago
  I don't mean to minimize anybody's work, I'm genuinely curious about why it can't be done. Like, what's stopping me from making a compiler that optimizes tail calls? For instance: the C and C++ standards have very strict rules for how to handle floating point math, and compilers aren't allowed to deviate from that according to the standard. Which turns off all sorts of cool optimizations you can do. But of course, all modern compilers implement some version of "-ffast-math" which turns off those rules and allows for the optimizations. It's no longer standard C/C++, but that doesn't mean that switch can't exist. The compiler is a computer program, it can output anything it wants, regardless of what the standard says. Nobody is going to go to jail because you turned on -ffast-math. The code will still run just fine. So, my question is, why can't you write a compiler with an option that's like "I don't particularly care that .stack changes, do the tail call optimization". A -ffast-math, but for tail calls. Is there a technical reason why you can't do this?
  - light_hue_1 4y ago
    > So, my question is, why can't you write a compiler with an option that's like "I don't particularly care that .stack changes, do the tail call optimization". A -ffast-math, but for tail calls. Is there a technical reason why you can't do this? Because the stack in web assembly is only observable. It is implicit. You cannot modify it yourself. There are simply no instructions for this. The WASM stack is not present on the WASM heap, like it is for your physical machine. You simply cannot express tail calls with the instruction set given to you by WASM right now. No hacks are possible.

anfilt 4y ago

What? Compilers handle tail calls all the time even in languages like C and higher level functional languages. Its just a jmp? Does the wasm VM not have a jmp instruction?!?

Jtsummers 4y ago
https://www.w3.org/TR/wasm-core-1/#control-instructions%E2%91%A0 https://www.w3.org/TR/wasm-core-1/#control-instructions%E2%9... Those are the list of control instructions. WASM seems to be a bit of a misnomer as it is not an assembly language in the more conventional sense. It is a structured language and provides a limited goto in the form of branches (in the section I linked to) which are constrained to a particular scope. If you compile your whole program so it fits within a single function, then yes you can use this to do universal tail call elimination. Otherwise you are restricted to doing TCE only on auto-recursive functions and maybe mutually recursive functions if you have a single entry point (of the set of functions) and decide to optimize by moving all of them into one function. Otherwise, function calls are performed using one of the two call instructions which (presently) implement a behavior more like conventional call stack/stack frames. This proposal would add a second pair of call instructions that a compiler can emit which the WASM runtime would then optimize (by not generating new stack frames).
- anfilt 4y ago
  So no self modifying code either, since it seems like I can't just get the address of a function and modify the byte code?
  - shadowofneptune 4y ago
    That would be used most often for malware, unfortunately.

jjtheblunt 4y ago

> Tail-calls is fundamentally something the the compiler _cannot_ solve. How does the famous 1977 Guy Steele paper on compilers optimizing tail calls not apply? https://dl.acm.org/doi/10.1145/800179.810196 https://dl.acm.org/doi/10.1145/800179.810196

taeric 4y ago
My guess is that this is assuming that the compiler can rewrite a return into a jump. That is, these compilers have control over the stack on the machine.
- jjtheblunt 4y ago
  compilers always have control over the stack on the machine: they generate the code which realizes the notion of a stack (and happily usually have dedicated registers to use for that generated code)
  - taeric 4y ago
    Not something compiling to WASM. Nor something compiling to JVM Bytecode.
    - jjtheblunt 4y ago
      If WASM and JVM Bytecode have a goto, then the compiler can use it. Anyway, if you've never read that paper i linked to above, i do believe you'll find it mind-blowingly cool stuff. not kidding.
      - taeric 4y ago
        They don't. That is literally the thing. Edit: I should say, they don't have anything equivalent that can jump out of the method you are in. Edit2: This is a bit more clear if you consider what it means for JVM bytecode to have a "return" set of instructions. Why does the bytecode need a return, if that is all managed by code that the compiler should handle anyway? You can look at the instructions here: https://en.wikipedia.org/wiki/List_of_Java_bytecode_instructions https://en.wikipedia.org/wiki/List_of_Java_bytecode_instruct.... Note that it is the "jsr" instructions that let you do the equivalent of a long jump, and those specifically manipulate the stack. There is a "goto", but it is not valid to have that jump outside of the subroutine you are in.

JohnHaugeland 4y ago

> 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 WebAssembly (and JavaScript) the call stack is observable via the .stack property of thrown exceptions. Okay? This seems fine to me. What makes this a problem?

naasking 4y ago
Trampolines are a hack that penalizes the performance of any language that uses tail calls a lot, like functional languages (scheme, lisp, Haskell, etc). You could also handle exceptions manually too, without VM support, but that too would incir considerable overhead.
int_19h 4y ago
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.
dragonwriter 4y ago
> Compilers are how tail calls are literally always implemented. WASM doesn't have the same set of operations as a typical CPU. It's not something a compiler to WASM can do.

aaron_m04 4y ago

Is this the reason clojure added the recur form? IIRC, the JVM doesn't support tail calls because Java doesn't need it. https://clojuredocs.org/clojure.core/recur https://clojuredocs.org/clojure.core/recur

skrebbel 4y ago

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

randomswede 4y ago

There are probably WebAssembly-specific things I am unaware of. So, the following is a general "TCO" discussion. I normally consider TCO something that is a compiler feature. Replace a call to the head of yourself, with a jump (possibly to just after the "pull the arguments from the call stack to where the code wants it" prologue), making sure that the correct locals are present where they need to be. Well, that's for self-TCO. General TCO is definitely trickier (probably requires juggling stack allocations so as to ensure that the tail-called function has enough space for all that it needs).

WastingMyTime89 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. I have been out of the loop regarding compilers development for a long time but what prevents you from converting your program to CPS and using a trampoline like some LISP still do?

antonvs 4y ago
A trampoline is a workaround that wastes memory and time. The idea is to avoid that so that you can use function calls efficiently.