A tiny and incomplete Python Virtual Machine

Compilation
Arithmetic operations
Boolean operations
The Code
The virtual machine
A few example functions
A driver

Important: Pyodide takes time to initialize. Initialization completion is indicated by a red border around Run all button.

In the previous post, I described how one can write an interpreter for the Python language in Python. However, Python itself is not implemented as a direct interpreter for the AST. Rather, Python AST is compiled first, and turned to its own byte code. The byte code is interpreted by the Python virtual machine. The Python virtual machine is implemented in C in the case of CPython, in Java in the case of Jython, in WASM for Pyodide, and in (reduced) Python in the case of PyPy.

The reason to use a virtual machine rather than directly interpreting the AST is that, a large number of the higher level constructs map to a much smaller number of lower level constructs. The lower level language (the bytecode) is also easier to optimize, and is relatively more stable than the higher level language.

For our purposes, the lower level language also allows us to get away with implementing our analysis techniques (such as taint analysis — to be discussed in later posts) on a much smaller number of primitives.

This post shows how to implement a very tiny Python virtual machine. For more complete implementations, refer to the AOSA Book or more complete and current Byterun or my fork of byterun.

We start as usual by importing the prerequisite packages. In the case of our virtual machine, we have only the dis module to import. This module allows us to disassemble Python bytecode from the compiled bytecode. Note that the package xdis may be a better module here (it is a drop in replacement).

As in the MCI, we try to use as much of the Python infrastructure as possible. Hence, we use the Python compiler to compile source files into bytecode, and we only interpret the bytecode. One can compile source strings to byte code as follows.

Compilation

The mode can be one of eval – which evaluates expressions, exec – which executes a sequence of statements, and single – which is a limited form of exec. Their difference can be seen below.

compile(mode=eval)

That is, the return value is the result of addition.

compile(mode=exec)

The top of the stack is popped off on execution. That is, it is treated as a statement. This mode is used for evaluating a series of statements none of which will return a value when eval() is called.

using exec

compile(mode=single)

The single mode is a restricted version of exec. It is applicable for a single line statement, which can even be constructed by stitching multiple statements together with semicolons.

The main difference is in the return value. In the case of exec, the stack is cleared before return, which means only the side effects remain.

In the case of single, the last value in the stack is printed before return. As before, nothing is returned.

Arithmetic operations

Next, we define all the simple arithmetic and boolean operators as below.

Boolean operations

Similar to arithmetic operations, we define all logical operators.

The `Code`

The compiled bytecode is of type code.

It contains the following attributes

Since it is a read-only data structure, and we want to modify it, we will use a proxy class Code to wrap it. We copy over the minimum attributes needed.

The virtual machine

As can be inferred from the dis output, the Python Virtual Machine is a stack based machine. So we define a bare bones virtual machine that can use a stack as below.

The return instruction is simply a pop of the stack.

Now, we define how a function is called. We need to extract the function and args, and pass the execution to the called function.

Implementing COMPARE_OP

Implementing jumps

Implementing loops

Wrappers

Translation of bytes to corresponding functions.

class Vm(Vm):
    def bytes(self, code):
        self.fnops = {
                'LOAD_GLOBAL': self.i_load_global,
                'LOAD_FAST': self.i_load_fast,
                'STORE_FAST': self.i_store_fast,
                'LOAD_NAME': self.i_load_name,
                'STORE_NAME': self.i_store_name,
                'LOAD_CONST': self.i_load_const,
                'RETURN_VALUE': self.i_return_value,
                'CALL_FUNCTION': self.i_call_function,
                'COMPARE_OP': self.i_compare_op,
                }
        self.jmpops = {
                'POP_JUMP_IF_TRUE':  self.i_pop_jump_if_true,
                'POP_JUMP_IF_FALSE': self.i_pop_jump_if_false,
                'JUMP_ABSOLUTE': self.i_jump_absolute
                }
        self.blockops = {
                'SETUP_LOOP': self.i_setup_loop,
                'POP_TOP': self.i_pop_top,
                }
        self.otherops = {
                'MAKE_FUNCTION' : self.i_make_function,
                'POP_BLOCK': self.i_pop_block,
                }
        self.code = Code(code)
        return self

The interpreter itself

def log(*args):
    #print(*args)
    pass

class Vm(Vm):
    def i(self):
        ops = self.code.opcodes
        ins = 0
        while ins < len(ops):
            i = ops[ins]
            log(ins,i.opname, i.arg, i.is_jump_target)
            if i.opname in mathops:
                fn = mathops[i.opname]
                nargs = fn.__code__.co_argcount
                args = self.stack[-nargs:]
                self.stack = self.stack[:len(self.stack)-nargs]
                v = fn(*args)
                self.stack.append(v)
            elif i.opname in self.fnops:
                fn = self.fnops[i.opname]
                self.result = fn(i.arg)
            elif i.opname in self.jmpops:
                fn = self.jmpops[i.opname]
                ins = fn(i.arg, ins)
                assert ops[i.arg//2].is_jump_target
                continue
            elif i.opname in self.blockops:
                fn = self.blockops[i.opname]
                fn(i.arg)
            elif i.opname in self.otherops:
                fn = self.otherops[i.opname]
                fn(i.arg)
            else:
                assert False
            ins += 1
        return self

def result():
        return self.result

Contents