Computer science classes often teach us that there are two ways to build and run a computer program. To either interpret it or to compile (and then execute) it. For example the Java compiler will compile the Java source code into JVM bytecode, which can then be interpreted by the JVM (but is also often JITed - another type of compilation). So here are all the types of compilers and interpreters I can think of:

I’ll pause my list now to say, yes there are (have been?) compilers that emitted executable code directly. Some also used anther intermediate format that I can’t remember the name of. S-code or something. Let’s continue:

Once you have bytecode you can:

Some fancier methods exist for interpreting bytecode, many come from a long history in interpreting Forth programs, you can read more here:

Finally:

There’s a lot we could talk about here, but now we’ve painted the scene let’s assume you have some bytecode and want ti interpret it in the simplest way possible.

There’s one more topic to discuss first, what bytecode actually is / looks like.

Instructions, either in machine code, assembly language, or a bytecode, tell the machine what to do. They’re made up of an opcode (operation code I guess?) and optionally some operands (parameters for the opcode). The opcode of an instruction tells the machine what to do, and the operands tell it what to do it with. I was going to use some x86 as an example here, however x86 has opcodes from 1-3 bytes long, optional prefix bytes and about 4 different types of operands (also of different lengths) instructions are anywhere from 1 to 15 bytes long, and encoding is very complex, sometimes operands are actually implied by the opcode, other times parts of them (like a high bit) is given as part of the prefix (for the extra registers in x86_64). The point I was going to make here, with a nice tidy example, was that real machines and virtual machines use the same opcode followed by operands paradigm.

In some CPU architectures, and many bytecode formats, the opcode is a fixed number of bytes (usually 1). Followed by the operands. This is true in the JVM. In the JVM an increment instruction looks like this:

This increments the 2nd local by 1. 84 is the opcode meaning 'increment' and 02 and 01 are each of the two operands, 02 selects the 2nd local variable, and 01 is how much to increment by. In this case 02 can be considered a selector, it tells the machine what to perform the operation on (the 2nd local variable), in a register machine this may refer to one of the registers. While 01 can be considered an immediate value, a value used by the program that is stored in the instruction stream. The JVM, PZ, and many other virtual machines are stack-based machines meaning they have no general-purpose registers and operations are almost-always performed on the values located at the top of the stack.

Plasma currently has two different bytecode formats, one for on disk, and one for in memory. On disk a PZ (that’s the Plasma abstract machine) bytecode instruction has a one byte opcode, two separate one byte operand size bytes, and an optional immediate value (pz_format.h). The opcode says whether the other bytes will be present. An instruction like 'add' has a single operand size byte, this tells the interpreter what size of data 'add' should add eg: 8-bit, 32-bit, pointer-sized etc data. Most instructions require one of these bytes, some don’t (like 'roll' and some require two like 'sign-extend'. 'Load' and 'call' instructions require an immediate value. For 'load' instructions this says what to place on the stack, for 'call' it is the number of the procedure to call.

While Plasma is under development the format is not fixed, so it doesn’t make sense to talk about the constants for particular opcodes and operand sizes, so there is no example here.

These instructions follow one-after-another to form an instruction stream. The program will execute each instruction in the stream one after another unless it encounters something like a 'call', 'jump' or 'return' instruction. For example if in the JVM we incremented local 2 by 1, then local 3 by 2. We would have an instruction stream like

The first three bytes make up the first instruction, and the next three make up the second instruction.

Plasma currently has a single bytecode interpreter, a token-based interpreter. It is probably the slowest type of bytecode interpreter, however it is one of the most straight-forward to write and can be done portably. We will add faster but architecture-specific interpreters later, and hopefully support for native code generation.

Many of the techniques for interpreting bytecode transform the bytecode in some way before interpreting it. With token-threaded bytecode execution this is not necessary, however we do do this for PZ to remove the operand size bytes, and instead having a distinct opcodes for each on-disk opcode and operand size byte(s) combination.

A token-based interpreter will have a loop and switch somewhat like this:

The ip variable is the virtual machine’s instruction pointer. It points to the next byte from the instruction stream to be interpreted. The interpreter’s loop reads each byte, advances the pointer and then decides what action to perform depending on the opcode (the opcode is a token).

The next thing we need to handle is immediate values. Some instructions can load data from memory, or sometimes other places like IO ports (in real machines running in supervisor mode), but some will load data from the instruction stream itself. Program constants are usually loaded this way. In Plasma’s in-memory bytecode format these values are aligned (for portability and efficiency).

We’ve also introduced two new variables here. expr_stack and esp. The PZ machine has two stacks, the return stack and the expression stack (called the parameter stack in Forth literature). The expression stack stores values that we’re currently working with (local variables) and saves them across procedure calls. In the PZ interpreter expr_stack points to the base of the stack and esp is an offset within it. Each stack slot is a C union and u32 is a 32bit field in that union. Treating each stack slot as a C union is a little wasteful, but it simplifies the implementation and helps things remain fairly portable.

Finally our interpreter needs to handle jumps and calls. These use an immediate value like above, but interpret it as a code address to control the program’s flow.

There are two new variables here once more. The return stack and return stack pointer. Note that in the PZ Machine there are two stacks, the return stack is separated from the expression stack. This allows a little more expressitivity within PZ, which is common to stack machines.

The PZ machine supports many more instructions, only the three most interesting for how to write a stack machine have been shown here. The others can be derived from these or seen in pz_run_generic.c in the Plasma source code.