Hacker News Reader

Comment by apignotti | Hacker News Reader

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.

View on HN

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

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

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

It is implicitly already mandated, depending on how finite your finite limit is.

The reason for the existing mandate is to be a problem for recursive programs, so it is a feature, not a bug, of the proposed refinement that it more reliably achieves that.

(Specifically, to prevent one implementation getting an optimization for them that leads people to rely on it, making code that blows up in practical use on other implementations, despite both being nominally correct implementations of the same spec.)

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

This might be a silly question, but why is that a nightmare scenario? The exact same argument could be made for any compile-time optimization. If one compiler inlines a function where another doesn't, or unrolls a loop, or performs better constant propagation, any of those could impact the resource usage between the two compilers, leading to exactly that same scenario. But I wouldn't want to forbid improvements altogether out of a desire for consistency.

To me, I'd see a distinction between code that requires a specific optimization and code that could benefit from that optimization. If the standard forbids an optimization to avoid the former, it also removes the latter.

Most optimizations only offer constant factor improvements. Tail call optimization is the difference between O(1) and O(N) stack size.

Tail calls can be optimized at the source code level too. When I first read about them decades ago I thought it was a stupid notion due to me not understanding how a good compiler can optimize them away. Then I wondered why certain people felt the need to write code that way. I still wonder that.

I wrote an article about my motivation for it: https://blog.reverberate.org/2021/04/21/musttail-efficient-i...

Thanks for that. Having written a threaded interpreter before that immediately made sense. It does seem like you used some other hints to the compiler as well so this would fall under "experts only" type of code and that's OK. I still wonder how well good old "goto" might do, but once you move away from a huge switch/case to individual functions I can see how it might help a bit.

I still don't understand why some people seem to like the idea of iterating simpler things with recursion using a tail call.

> The exact same argument could be made for any compile-time optimization.

No.

For other optimization, the difference is the speed of execution. For tail call optimization, the difference can be normal execution and stack overflow.

Any optimization that removes an unnecessary stack allocation could also be the difference between normal execution and stack overflow, due to decreasing the size of the stack frame.

But the effect is much more likely in tail recursive cases.

That is exactly why tail call "optimisation" is not, in fact, an optimisation.

Indeed much of this discussion, including the title and text of the original post, carefully avoids using the word "optimisation". Somehow it got introduced at some point in these comments.

To flip it the other way: consider a normal (non-tail-call) program and choose a local variable in a routine that happens to be called quite a lot. Replace it with a list that you append to every time you call the routine, even though only the last entry is ever examined. The program will leak memory, potentially quite quickly, and eventually crash. Is it fair to say it's just less optimised than before? I would say it's worse than that: it has an actual bug.

That's exactly the situation in a program created with the assumption of tail calls that is then used in an environment without them.

> Replace it with a list that you append to every time you call the routine, even though only the last entry is ever examined. The program will leak memory, potentially quite quickly, and eventually crash.

I had to think on this example a bit, but I believe these programs exist and are quite common. This is an accurate description of any program in which memory is allocated and never explicitly freed. Some languages include runtimes that perform garbage collection, but until the garbage collection runs, the program is leaking memory and would crash without the garbage collection.

Which is to say, I think I agree with you, but had to chew over the example a bit. That it isn't a quantitative difference in speed or memory usage, but a qualitative difference in the types of programs that are acceptable in a language. Thank you for it.

> Is it fair to say it's just less optimised than before? I would say it's worse than that: it has an actual bug.

Yes, a program that depends on tail call optimization, despite having no guarantee of tail call optimization being performed, has a bug.

That doesn't mean that tail call optimization is not an optimization. In languages that allow, but do not guarantee, tail call elimination, it is an optimization performed by the optimizer that makes a program run more optimally than it would have otherwise. There is a long history of referring to it as an optimization, for example in the docs of LLVM: https://llvm.org/docs/LangRef.html#call-instruction

I don't think it makes sense to redefine the word "optimization" such that it excludes examples where a program could erroneously depend on a certain optimization being performed.

OK, if you prefer to be precise, there are two situations:

(1) In languages (or runtimes) where tail calls are not guaranteed to be elided, tail call elision is an optimisation. In that context, you could quite reasonably describe it as tail call optimisation. Programs that are written in these languages and rely on tail call elision are buggy.

(2) In languages (or runtimes) where tail calls are guaranteed to be elided, tail call elision is not an optimisation. In that context, you cannot reasonably describe it as tail call optimisation. Programs that are written in these languages and rely on tail call elision are not buggy (at least, not for that reason!).

This conversation is about making tail call elision a guaranteed feature of WASM. Therefore, in this context, it is not reasonable to describe tail call elision as an optimisation.

Try writing a loop over all 64 bit values. The computer will break before the loop finishes.

> 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)

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.

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.

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.

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.

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?

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.

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.

Well WTF is this doing https://docs.rs/wasm-bindgen/0.2.11/wasm_bindgen/fn.throw.ht... then ?

Calling into an external JavaScript function, which will then throw a JavaScript exception (as the linked documentation states).

Wasm cannot throw the exception itself, nor can it catch the exception. How exceptions are handled when raised in code called via FFI in another language are a property of the embedding and wasm engine, not of wasm itself, which (as of yet, barring that exceptions proposal) has no concept of them besides unrecoverable traps.

Great thank you for the info

Maybe I'm naive and I surely don't know anything about the WASM spec, but aren't CPUs implementing both exceptions and tail call elimination as gotos (some jump machine code instruction) ? Exceptions might have to pop some frame, TCE doesn't.

To avoid some classes of security issue, and also because it started much closer to asm.js in features, WASM uses structured programming control flow like blocks, if..then, and break statements. Functions can only be called by the call instruction right now, so this proposal is needed to jump to an function body.

Are you saying there is no goto in wasm ? Genuine question I don't have any knoweldge of WASM.

Yes, that is correct.

It's more important for exception handling to be implementable than for TCE to be implementable, yes. But it's more important for TCE to be provided by the virtual machine (or, alternatively, for call and return to be manipulations of user-level state, as on traditional CPUs, rather than magic privileged operations as in Wasm) because you can implement exception handling with TCE but you can't implement TCE with exception handling.

Plenty of C/C++ code de facto assumes it’s present even though it’s not mandated. Anybody trying a list algo in recursive style is relying on it implicitly.

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?

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

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?

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.

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.

This is just a fancy form of spaghetti code. Don't do it unless you actually need the performance.

State machines are known for a predilection to use `goto` extensively, but that does not make them 'spaghetti code'.

A state machine is, in fact, a well-understood method of applying structure to spaghetti.

The point is that tail calls obscure the transitions between states by spreading it everywhere.

I'm not too clear on how one would implement a state machine without "spreading the transitions everywhere". Can you share a link to some example code showing the format you prefer?

Typically, we'd see the code that implements the logic for each state gathered together. Since this is where the outgoing transitions get decided, the transitions end up being distributed across their originating states.

erlang/otp gen_fsm maybe?

you define a function with a clause per state (and some other args including the incoming message), and each clause returns a tuple with the new state and some other stuff. the loop is part of the framework, and handles generic otp stuff like updating code in a running system.

That doesn't compute for me. You'd need to give an example for me to understand you.

One example would be in a parser, as various parsing functions would be invoked recursively until end of input, or until some non-matching input is encountered. In pretty much any scenario where you would use recursive functions, it is quite common to have mutual recursion between multiple functions. Not always of course, which is where the tail call elimination optimization is typically applied, but not being able to freely use mutual recursion to arbitrary depth turns out to be quite an annoying limitation.

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.

This is usually a case where TCE doesn't help, in my experience, because most of the calls to sub-parsers aren't in tail position. This is especially unpleasant when you get bug reports of mysterious segfaults that turn out to be stack overflows...

Yep, a basic security check for any endpoint that accepts JSON: what happens when you hand it 4KiB of '[' characters

> parsing deeply nested JSON structures

How likely is it that the depth of the JSON structure would exceed the maximum depth of the stack? This doesn't appear to be a compelling example to me.

It probably is a shame that it's called tail call optimisation since nobody wants to mandate low level details for an optimisation.

It’s a security/DOS vulnerability if the object depth can be used to trigger stack overflow.

> How likely is it that the depth of the JSON structure would exceed the maximum depth of the stack?

Not that unlikely i'd say, at lest if the stack size is unreasonably small.

For example, on nodejs, JSON.stringify() chokes with a nested array of 10K depth:

  > N=10_000; JSON.stringify(JSON.parse("[".repeat(N) + "]".repeat(N)))
  Uncaught RangeError: Maximum call stack size exceeded
      at JSON.stringify (<anonymous>)

Curiously, JSON.parse() is OK with arrays of 10M depth (and probably more). A difference of over 3 orders of magnitude between functions that seem pretty symmetrical at first glance.

Imagine that you build some software that lets users nest things —e.g., a circuit designer, a visual programming language, a UI builder, etc— and you wanna save these nested structures as JSON, or process them recursively. Pretty natural fit i'd say. Now, as a user, i'd be pretty upset if my magnum opus of a very complex circuit, or giant visual program, or very busy beast of UI art, starts creashing the program when exceeding a mere 10K elements. My computer has gigabytes of memory! And, presumably, there's a lot still available. But nope, a meager stack can ruin all the fun.

I personally think this is a pretty silly limitation to have on software, especially given today's memory sizes.

TCO likely wouldn’t help here, as the parser is probably using non-tail recursion to build the nested arrays. (I haven’t looked at the code, but that’s the natural way to do it with a recursive descent algorithm.)

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.

This is the scenario I am used to using where "last" is called in tail position calling itself, but I see from the other answers there are definitely valid use cases for non-same function recursion as well

It's useful anytime you can benefit from the performance advantages of replacing a full fledged function call with little more than a jump. One classic example is implementing an efficient VM.

In languages like Scheme, Haskell, OCaml, and Erlang it happens all the time, often when the user isn't aware of it; even when these languages have special looping constructs they are often implemented in terms of tail recursion, sometimes mutual tail recursion between several anonymous subroutines.

In languages like Scala, Java, C#, and Swift, it basically never happens.

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

That sounds like it means that Scala doesn't support general tail-call elimination, so people don't write mutually tail-recursive code, instead transforming things that would naturally be expressed that way into a different structure that Scala does support.

Yes. It can be a major PITA, in certain problem spaces and I think most people don't pretend it's a great solution but ultimately accept it as a limitation of being hosted on the JVM.

> 98-99% of the time it was the same function calling itself

well if the same function is in the "tail" it would still apply a tail call elimination.

But a lot of the time tail call eliminiation is only needed in some extreme cases. it can eliminate stack overflow exceptions by a big amount. C#'s new System.Text.Json would greatly benefit with tail call ops, because it often has a call chain that is recursive and does not call itself (its mostly like ReadObject, ReadObjectAsync, ReadObject, ReadBla, ReadObject, etc. and if the object has a ref to itself system.text.json often blows up.

In Java and Scala this thing can btw. also happen (and I've already seen it) however at least you can configure the stack size there and thus most often eliminate the problem somewhat.

it's an edge case, but one that would be cool to fix, since it makes code often more reasonable especially parsers.

If you’re implementing a compiler for a language like Haskell, then everything is compiled into mutually-recursive tail calls.

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 structure - it's the only approach to stream processing I've found where you can have a value that represents a stage in the middle of processing a stream (not just a 1:1 function but something that does grouping or suspension or the like) in a natural way, that you can then test standalone etc.).

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

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

Yes, which is exactly why tail calls are so important. Otherwise you'd stack overflow after processing the first few thousand elements of your stream.

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

Well, if you want to express your function as an actual function, in the mathematical sense, recursion is often the natural way to do it. Things like the call stack are an implementation detail; often a natural way to describe a function is "do this, do that, then do the same thing for all the rest of it", and usually the easiest way to translate that into a program is recursion.

It also tends to be more compositional, because you don't have to worry about control flow (or at least, control flow isn't a special case: all your control flow is just function calls). For example if you are calling several nested functions in an imperative-style loop, there's no way to break out of that loop from the inner function. But if you write the same thing as several mutually recursive functions, you can "break out of the loop" by just not recursing under particular conditions.

Thanks, I think I have a better grasp now.

> Understood, but in practice how often does that really happen?

In functional code written where general tail call elimination (or special tail call operations) are available, non- or mutually-recursive tail calls are not uncommon.

Heck, non-recursive (potentially fairly nested) tail calls are common in languages without any optimization for it. Anytime you see something like “return f(x)” (or, because operators are implemented via special methods, even “return x+y”) in Python, for instance, you've got a tail call.

If it isn't direct or mutual recursion, it has to be a pretty degenerate case to blow the stack even without elimination, so elimination is must necessary for those cases. But other cases bene for from not having the extra memory usage and reducing pushing stuff onto and popping it off of the stack.

You can turn it into a loop with a case statement inside if you collect the connected component of tail called functions and make those the cases. But it’s gonna be a big function.

You can split it up a bit if you use a trampoline, but then you lose some efficiency.

Though at that point you're basically just one step removed from making your own stack frame.

Which would definitely work, no doubts about that, but it might be nicer to just get it handled at a more fundamental level.

If f1 calls f2 that calls f1 why can't the compiler inline f2 into the body of f1? It's not so complicated if the compiler has annotations or other hints to guide it.

I once wrote an interpreter in continuation-passing style, meaning every final line of a function called the next function in the interpreter, passing a continuation and error continuation on.

Such a program never returns until it finishes interpreting, and can make an unlimited number of such calls.

This is a bad idea without TCE.

Why couldn't the compiler inline the whole interpreter?

Because in the continuation-passing style, the functions-calling-functions are circular in many places, inlining would explode rather than halting.

Scala has a weak version that handles self-tail-calls only. It causes significant trouble for e.g. iteratee/streaming libraries in Scala (like FS2) where you always have to use a trampoline.

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?

> yeah, it would change .stack, but who cares?

You might enjoy participating in an interoperable standardization process sometime.

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?

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

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

Stack overflows are stopping you, if you implement Scheme calls as Wasm calls.

In Scheme, tail call elimination is not merely an optional "optimization", so the compiler can't opt to not do it when it's inconvenient.

The control flow in WebAssembly virtual machine is quite restricted (it's called "structured control flow" in the spec), you can't jump to code freely. Possibly you could compile scheme with having the whole program in one big wasm-level function and branching between blocks there?

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

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

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.

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.

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

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

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

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

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

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

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?

That would be used most often for malware, unfortunately.

> 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

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.

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)

Not something compiling to WASM. Nor something compiling to JVM Bytecode.

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.

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

WASM's version of a goto is a branch, it is constrained to a limited scope. This creates a problem for general tail call elimination but not for auto-recursive functions.

Auto-recursive functions can switch to using a branch or using another loop construct, and the compiler can generate that WASM code. The control structures available are described in the link below. Mutually recursive functions where only one is meant as the entry point could be similarly converted into WASM instructions but where the additional functions are, essentially, eliminated and inlined into the original caller (this may not be a good general solution, though). But general tail calls cannot be converted into gotos as you might with a more conventional assembly language since WASM branches cannot go to arbitrary instruction addresses.

The problem is that in a conventional assembly language, if you do TCE then the goto would go to (har har) the same (or nearly the same) point as a regular function call (maybe it skips the first few instructions depending on the calling conventions involved). With TCE and WASM you'd have to, essentially, inline the called function, or a variant of it, in order to be able to branch to the start of it. You cannot branch into a different function or to the start of a different function, you have to call the other function and then you have a single entry point. Which, in WASM as currently specified, means you have to use the current calling conventions which does not permit TCE.

https://www.w3.org/TR/wasm-core-1/#control-instructions%E2%9...

this paper espouses the use of jump+arguments instead of call. Wasm has no control transfer instruction that doesn't use the stack, nor does it have writable access to the stack pointer.

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

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

Reply on news.ycombinator.com