by kragen | 2025-09-08 00:15:28+00:00
Thank you! This is indeed very thought-provoking!

It certainly does depend on which stack machine. I'm surprised that Wasm doesn't have a one-byte encoding for (local.get 0) or (local.set 0)! As you point out, even the JVM has one. My survey of bytecode instruction sets in https://dercuano.github.io/notes/tiny-interpreters-for-micro... found such an 8-bit or 5-bit instruction in nearly every example except CPython, with a 3-to-5-bit operand field in the local.get and local.set instruction byte, but of course Wasm didn't exist in 02007. The JVM only offering 2 bits is atypically stingy.

RVC and Thumb2 are pretty extreme cases of optimized register-machine encoding, and probably not something you'd want to decode in software on a 6502. The comparable stack-machine code would be something like Chuck Moore's x18/F18A with its four instructions per 18-bit word or James Bowman's J1A.

It also depends, as you say, on the code. Most code is somewhere in between the extremes of x += y and your example of

det = a*(e*i − f*h) − b*(d*i − f*g) + c*(d*h − e*g)

with statements like these:

dstRect.bottom := Max(dstRect.bottom,dstRect.top + txMinHeight); thePort^.grafProcs := Nil; { restore to normal } if (n != 0 && --n != 0) ... target_command = entry_i + CAM_CONTENT_COUNT * j; tfd = open(ptr, O_RDWR|O_TRUNC|O_EXCL|O_CREAT, 0600); for (size_t i = 1; i < n; i++) ... if (event == EV_enter_state) ... else if (event == EV_tick) ... else if (event == EV_reenter_state) ...

Those are all taken from my examples in https://dernocua.github.io/notes/c-stack-bytecode.html. There are a lot of subroutine calls, some reuse of the same value in multiple computations, many more variable reads than writes, and an occasional infix expression with more than one operator. These are all factors that favor stack instruction sets more than x += y does.

Subroutine calls in particular are typically a single bytecode once all the operands are on the stack, referring to a subroutine name or address stashed elsewhere with a short literal index, which similarly is usually allocated a 3–5-bit field in the opcode byte. Very popular subroutines like car or #at:put: can get their own bytecode.

There's a bit of a difference between the 8 registers in the PDP-11 or the 8086 and the 3-bit local variable field in an Emacs Lisp bytecode byte. The stack pointer soaks up one of those slots; on the PDP, the program counter soaks up another. (On ARM the link register sometimes is a third. Thumb and RVC do better here by excluding these registers from their 3-bit namespaces.) Analogously, one of the 8 local-variable indices in Elisp is "see next byte". Also, though, stack machines don't need to spend local variable indices on temporaries, and they often have instance-variable-access opcodes as well. So in effect register machines have less local variables than it at first appears.

Incidentally, as that note mentions, Aztec C for the 6502 did support a bytecode interpreter to more than halve code size:

> As an alternative, the pseudo-code C compiler, CCI, produces machine language for a theoretical machine with 8, 16 and 32 bit capabilities. This machine language is interpreted by an assembly language program that is about 3000 bytes in size.

> The effects of using CCI are twofold. First, since one instruction can manipulate a 16 or 32 bit quantity, the size of the compiled program is generally more than fifty percent smaller than the same program compiled with C65 [the Aztec C native code compiler for the 6502]. However, interpreting the pseudo-code incurs an overhead which causes the execution speed to be anywhere from five to twenty times slower.

But I don't know whether it was a stack bytecode, an accumulator bytecode, a register bytecode, or something weirder.

My experience programming in FORTH is that often I can profitably keep about one variable on the operand stack, so accessing that variable takes no instructions and no bytes. In theory this is something that a compiler could do, but the only case I know of is when you store to a variable in Smalltalk inside a larger expression. Similarly it's common in FORTH to spend no instructions on accessing arguments or returning a value; you just don't drop it before returning.