WASM is not quite a stack machine

Everyone knows Wasm is a stack machine. Wikipedia says so, the official Wasm design specification says so, you get it. I thought so too.

That is, until I started writing Wasm code – not compiling for Wasm, but writing the instructions by hand. And I found out that there exists a major difference between Wasm and all other stack-based languages, that makes this claim misleading.

Let’s back up a bit. What is a stack machine, even?

Say you write a program in a high-level language, and at some point you want to calculate 2 * 3 + 5 * 7 . Low-level languages don’t have a notion of compound expressions: they can only perform one operation at a time. So you need to do two multiplications, save their results, and then perform addition.

Many low-level languages, like x86 assembly, would represent these steps as follows:

a = 2 b = 3 c = a * b d = 5 e = 7 f = d * e g = c + f

This is called a register machine. You have variables (called registers), which can be used to store both persisted values and temporary results, and each instruction has form var1 = var2 op var3 .

Other languages, like Forth or Hex Casting, use a stack for this purpose. The stack can store a sequence of values in an ordered manner, so that already computed subexpressions can lie around while you’re working on other parts. In a stack-based language, the same calculation would look like:

push(2) push(3) mul() – pops the last two values from the stack and pushes their product push(5) push(7) mul() add()

Note that there’s a similarity between the two programs: they have the same number of steps, and the corresponding steps perform the same operation. The major difference is that with a stack machine, the values operated upon are implicitly encoded in the program order, while the register machine always encodes indices.

We know always-shrinking lossless compression doesn’t exist, though, so what expression power is lost by making indices implicit? For simple expressions, not much. But when values are reused, the difference becomes clear.

Say you’re a compiler, and you’re asked to compile this program:

x = 1 + 2 + 3 + 4
y = x * x * x

With a register machine, you can do:

x (as usual) tmp = x * x y = tmp * x

A stack machine as described above, however, does not offer a way to refer to the same value twice: mul always multiplies two values on different positions in the stack. To enable this calculation, real stack machines introduce stack manipulation operations in addition to pure calculation. The one we’re looking for is called dup , and it duplicates the value on top of the stack:

(calculate x) dup() – the stack now contains x, x dup() – the stack now contains x, x, x mul() – the stack now contains x, x*x swap() – the stack now contains x*x, x mul() – the stack now contains (x*x)*x

In practice, more operations are usually used to facilitate computation: over (copy second-last value to the top), 2dup (duplicate two values), drop (pop last value), rot (move third-last value to the top), etc.

From this perspective, stack machines can be seen as decoupling operations from indices they operate on. Whereas register machines always encode indices and pay a higher price when they’re redundant, stack machines encode them on an as-needed basis, but at the cost of a higher instruction count.

If you look at JVM, a well-known stack machine Wikipedia compares WebAssembly to, you’ll find basically this exact list of bytecode instructions: dup, swap, pop.

Now let’s look at the Wasm instruction set: i32.add, i32.load, drop, uhh, ???. Well, now isn’t that interesting? Wasm has plenty of instructions that receive arguments and place return values on the stack, but almost no instructions that can rearrange it – and, as far as I can tell, drop only exists because otherwise you wouldn’t have a way to ignore a function output.

Pretty much the only thing pure Wasm can do is evaluate simple expressions exactly as written in source code. An optimizing compiler can’t perform common subexpression elimination or optimize x^2 to x * x without introducing new variables. The moment you need anything non-trivial, you have to reach for variables – and thus end up with a register machine, the “stack machine” illusion falling apart.

In my opinion, the right way to look at Wasm is as a register machine with operations generalized to compound expressions. In binary Wasm, the expressions are encoded in Reverse Polish notation, which can be evaluated with a stack, but this is just an encoding.

Does it really matter? Pretty much any machine can be converted to SSA, at which point the input format is not a consideration; and I suppose the simplicity of stack-based implementation was a good thing for Wasm adoption. But I think it’s fair to highlight that experience with stack-based VMs doesn’t translate well to Wasm, since it’s not quite a stack machine.