Hacker News Reader

Comment by readittwice | Hacker News Reader

I would still consider WASM a stack machine and not a register machine. Yes, there are mutable local variables in WASM but Java bytecode has them as well - which you consider a stack machine. BTW the designers of WASM explicitly call WASM a stack machine here: https://github.com/WebAssembly/design/blob/master/Rationale..... With WASM's MVP it was necessary to store e.g. loop state in local variables, thanks to recent changes this doesn't seem to be necessary anymore. I think this was the main argument that blog post considered WASM to be a register machine. javac also makes heavy use of variables in bytecode, but somehow no one considers the JVM a register machine.

> my observations are that people with experience in the field tend to prefer register machines

That's actually the opposite of my observation, they seem to prefer stack machines.

View on HN

The clang disassembly given in the article sure makes it look like WASM is a nested expression tree, which leaves the choice of stack versus register to the implementation.

      (f32.add
        (f32.add
          (f32.mul
            (f32.load
              (local.get 0))
            (f32.load
              (local.get 1)))
          (f32.mul
            (f32.load offset=4
              (local.get 0))
            (f32.load offset=4
              (local.get 1))))
        (f32.mul
          (f32.load offset=8
            (local.get 0))
          (f32.load offset=8
            (local.get 1))))

The outer f32.add could translate into a byte code instruction that finds its two operands on a stack, or to one which gets them from registers.

The code only says that there is a f32.add call which has two operands that are the result of a f32.add and f32.mul and so on.

The implementations will agree in their treatment of locals: that there are two locals 0 and 1, which support loading at offsets and such.

Both stack and register machines can support locals.

Yes, that’s exactly true. The “stack machine” here can be seen as nothing more than a way of encoding the expression tree.

The stack machine is a model for the semantics of wasm, in the sense that the safety properties of wasm are defined in terms of stack types rather than SSA of register properties (for those that are unfamiliar with stack machines, this stack is a different type of concept from the call stack, that in wasm is used store the local variables). Whether during execution it is better implemented as a register machine or a stack machine is an implementation detail.

That's just the pprinter working its magic :-).

Just read the standard, it's quite clear from the semantics that it's a stack machine: https://webassembly.github.io/spec/core/exec/runtime.html#st... https://webassembly.github.io/spec/core/exec/instructions.ht...

Java has instructions like dup, swap etc. To me, that is the critical difference here, and where I draw the line between “stack machine” and “register machine”.

I have to admit this line seems arbitrary to me. So WASM is a register machine to you but if they would simply add those 2 instruction would it suddenly become a stack machine then? Those instructions would actually be trivial to add. I think those terms are relatively well defined and when you argue that WASM is a register machine even though the inventors explicitly claim it's a stack machine you should have really good arguments for that. Personally I would be surprised if you could point me to any literature that supports your definition.

Turing completeness sounds like an arbitrary distinction to those outside of the field of CS, but it’s not.

To me, the distinction here is that the stack machine in WASM is restricted to the point that it corresponds 1:1 with an expression tree—not even a graph, just a tree. This means that every function in Web Assembly can be thought of as a collections of statements and expressions, and the stack machine abstraction is nothing more than a serialization format for the expressions.

Maybe dial it back a bit with the challenge to point at literature. The literature has not really caught up with the existence of WASM yet.

The multi-value proposal breaks the ability to turn Wasm into expressions easily, and thus makes it even more of a stack machine than it already is. Dup and swap may still be added in the future.

A defining feature of a register machine is that the actual instruction encoding has direct references to source and destination registers in it. Wasm doesn't have those, it has explicit get_local instructions instead.

That said, if you turn off LLVM's WebAssemblyRegStackify pass, all LLVM IR's values will end up in locals, with little to no stack usage. Still no register machine, but a bit more of a grey area :)

> Maybe dial it back a bit with the challenge to point at literature. The literature has not really caught up with the existence of WASM yet.

It wasn't me who claimed that WASM is "obviously" a register machine, despite the inventors saying otherwise. They even explicitly state that they decided against a register machine. I guess it's then reasonable for me to ask on what definition of stack vs register you are basing this opinion on. Let me be clear: I was not asking here for literature about WASM specifically but a definition of register/stack machines that supports your claim.

WASM's instruction encoding is very much based on a stack machine. Even with the initial limitations you mentioned I don't think it qualifies as "obviously a register machine". As already mentioned in multiple comments those restrictions were already lifted with the multi value proposal.

I understand that there is a grey area, but simply claiming "obviously a register machine" doesn't seem right to me. Implementation-wise WASM is a stack machine even if it needs/needed locals to be turing-complete.

dup and swap can be implemented with locals in wasm (on well typed stacks)

Reply on news.ycombinator.com