Stack Machines Introduction

This section uses a fake stack machine language for educational purposes, and is unrelated to both the Java bytecode machine language and the CPython bytecode machine language.

1. What is a Stack Machine?

A Stack Machine is a type of virtual machine that uses a stack to store intermediary inputs and results. For instance, this program:

def my_fun(x: int):
    return x + 1

when compiled to a stack machine language, may look like this:

LOAD_LOCAL 0 (x)
LOAD_CONSTANT 0 (1)
ADD
RETURN

The stack starts initially empty, and each operation modifies it:

// []
LOAD_LOCAL 0 (x) // push x to the stack

// [x]
LOAD_CONSTANT 0 (1) // push 1 to the stack

// [x, 1]
ADD // pop top two elements (x, 1) and push their sum

// [(x+1)]
RETURN // returns TOS (x+1) to the caller

The stack is often not the only means of storage. Usually, there are local variables that can also be read and written to. For instance, this function:

def test(x):
    a = x + x
    b = x * x
    return a + b

when compiled to a stack machine language, may look like this:

// stack: [] locals: {}
LOAD_LOCAL 0 (x)

// stack: [x] locals: {}
DUP_TOP

// stack: [x, x] locals: {}
ADD

// stack: [(x + x)] locals: {}
STORE_LOCAL 1 (a)

// stack: [], locals: {a: x+x}
LOAD_LOCAL 0 (x)

// stack: [x], locals: {a: x+x}
DUP_TOP

// stack: [x, x], locals: {a: x+x}
MULTIPLY

// stack: [(x*x)], locals: {a: x+x}
STORE_LOCAL 2 (b)

// stack: [], locals: {a: x+x, b: x*x}
LOAD_LOCAL 1 (a)

// stack: [x+x], locals: {a: x+x, b: x*x}
LOAD_LOCAL 2 (b)

// stack: [x+x, x*x], locals: {a: x+x, b: x*x}
ADD

// stack: [(x+x) + (x*x)] locals: {a: x+x, b: x*x}
RETURN

2. Jumps in a Stack Machine

A stack machine opcode could conditionally jump to a different location. For instance:

def test(x):
    a = 0
    if x < 10:
        a += x
    return a

when compiled to a stack machine language, may look like this:

// stack: [] locals: {}
LOAD_CONSTANT 0 (0)

// stack: [0] locals: {}
STORE_LOCAL 1 (a)

// stack: [] locals: {a: 0}
LOAD_LOCAL 0 (x)

// stack: [x] locals: {a: 0}
LOAD_CONSTANT 1 (10)

// stack: [x, 1] locals: {a: 0}
LESS_THAN

// stack: [Type<bool>] locals: {a: 0}
POP_JUMP_IF_FALSE skip_if >---------------|
                                          |
// stack: [] locals: {a: 0}               |
LOAD_LOCAL 1 (a)                          |
                                          |
// stack: [a] locals: {a: 0}              |
LOAD_LOCAL 0 (x)                          |
                                          |
// stack: [a, x] locals: {a: 0}           |
ADD                                       |
                                          |
// stack: [(a+x)] locals: {a: 0}          |
STORE_LOCAL 1 (a)                         |
                                          |
[label skip_if]                           |
// stack: [] locals: {a: 0 or (0 + x)}    |
LOAD_LOCAL 1 (a) <------------------------|

// stack: [a] locals: {a: 0 or (0 + x)}
RETURN

In particular, the instruction after POP_JUMP_IF_FALSE will be the instruction after skip_if if TOS is False. If TOS is True, it will be the instruction after POP_JUMP_IF_FALSE instead. We call the possible next instruction(s) for a given instruction that instruction’s target(s).

This means the instruction after the label skip_if has two possible predecessors:

POP_JUMP_IF_FALSE if TOS was False
STORE_LOCAL (a + x) if TOS was True

In most stack based languages, stack state must be consistent. This means, among other things, the number of elements in the stack for a given opcode must be the same for all possible predecessors. For example, the following stack machine program is invalid:

// stack: []
LOAD_LOCAL 0 (x)

// stack: [x]
LOAD_CONSTANT 0 (10)

// stack: [x, 10]
LESS_THAN

// stack: [Type<bool>]
POP_JUMP_IF_TRUE skip_if >-----------------------------------------|
                                                                   |
// stack: []                                                       |
LOAD_CONSTANT 0 (10)                                               |
                                                                   |
[label skip_if]                                                    |
// Cannot compute stack; stack size mismatch [10] (1) vs [] (0)    |
LOAD_CONSTANT 0 (10)<----------------------------------------------|

// ???
RETURN

The if block pushed an extra element to the stack, but did not pop it, causing an inconsistent stack size after the if (either 1, if the branch was taken, or 0, if it was not).

3. Differences between Java and the CPython Virtual Machines

The Java and CPython virtual machines have a number of differences:

In Java, the compiler is allowed to introduce "extra" local variables not declared in the source program. This is because local variables in the JVM are stored in slots, and the number of slots does not need to match the number of local variables. In contrast, every local variable in the CPython virtual machine correlates to a declared local variable in the function, which is stored in a dictionary. This leads to CPython using the stack as storage for compiler local variables. For instance,

def my_fun(iterable):
    total = 0
    for item in iterable:
        total += item
    return total

translates roughly to

// [], locals: {}
LOAD_CONSTANT 1 (0)

// [0], locals: {}
STORE_LOCAL 1 (total)

// [], locals: {total: 0}
LOAD_LOCAL 0 (iterable)

// [iterable], locals: {total: 0}
GET_ITER

[forStart]<---------------------------------------------------------|
// [iter(iterable)], locals: {total: int}                           |
FOR_ITER afterFor >-------------------------------------------------+--|
                                                                    |  |
// [iter(iterable), int], locals: {total: int}                      |  |
STORE_LOCAL 2 (item)                                                |  |
                                                                    |  |
// [iter(iterable)], locals: {total: int, item: int}                |  |
LOAD_LOCAL 1 (total)                                                |  |
                                                                    |  |
// [iter(iterable), total], locals: {total: int, item: int}         |  |
LOAD_LOCAL 2 (item)                                                 |  |
                                                                    |  |
// [iter(iterable), total, item], locals: {total: int, item: int}   |  |
BINARY_OP 13 (+=)                                                   |  |
                                                                    |  |
// [iter(iterable), (total += item)]                                |  |
STORE_LOCAL 1 (total)                                               |  |
                                                                    |  |
// [iter(iterable)], locals: {total: int, item: int}                |  |
GOTO forStart>------------------------------------------------------|  |
                                                                       |
[afterFor]<------------------------------------------------------------|
// [], locals: {total: int, item: int}
LOAD_LOCAL 1 (total)

// [total], locals: {total: int, item: int}
RETURN_VALUE

Note that despite the fact iter(iterable) is not used inside the for block, it remains on the stack for the entire duration of the for block so it can be reused by FOR_ITER. In Java, the above code instead would roughly translate to

// [], locals: {}
LOAD_CONSTANT 0 (0)

// [0], locals: {}
STORE_LOCAL 1 (total)

// [], locals: {total: 0}
LOAD_LOCAL 0 (iterable)

// [iterable], locals: {total: 0}
INVOKE iterator()

// [iterable.iterator()], locals: {total: 0}
STORE_LOCAL 2 (iterator)

[forStart]<---------------------------------------------------------|
// [], locals: {total: 0, iterator: iterator}                       |
LOAD_LOCAL 2 (iterator)                                             |
                                                                    |
// [iterator], locals: {total: 0, iterator: iterator}               |
INVOKE hasNext()                                                    |
                                                                    |
// [boolean], locals: {total: 0, iterator: iterator}                |
JUMP_IF_FALSE afterFor >--------------------------------------------+--|
                                                                    |  |
// [], locals: {total: int}                                         |  |
LOAD_LOCAL 2 (iterator)                                             |  |
                                                                    |  |
// [iterator], locals: {total: int}                                 |  |
INVOKE next         |                                               |  |
                                                                    |  |
// [int], locals: {total: int}                                      |  |
STORE_LOCAL 3 (item)                                                |  |
                                                                    |  |
// [], locals: {total: int, item: int}                              |  |
LOAD_LOCAL 1 (total)                                                |  |
                                                                    |  |
// [total], locals: {total: int, item: int}                         |  |
LOAD_LOCAL 3 (item)                                                 |  |
                                                                    |  |
// [total, item], locals: {total: int, item: int}                   |  |
INT_ADD                                                             |  |
                                                                    |  |
// [total + item]                                                   |  |
STORE_LOCAL 1 (total)                                               |  |
                                                                    |  |
// [], locals: {total: int, item: int}                              |  |
GOTO forStart>------------------------------------------------------|  |
                                                                       |
[afterFor]<------------------------------------------------------------|
// [], locals: {total: int, item: int}
LOAD_LOCAL 1 (total)

// [total], locals: {total: int, item: int}
RETURN_VALUE

That is, instead of the iterator remaining on the stack, it got stored in a compiler local variable.

The stack state is before a try-block is preserved in Python, so it can be restored when an exception occurs. Thus, when an exception occurs in CPython, the stack state is <stack before try>, <exception info> (where <exception info> is either <frame info>, traceback, exception, exception_type if the Python version is before Python 3.11, exception otherwise). In contrast, after an exception occurs in Java, the stack state is exception. For example, this code:

def my_fun(session_list):
    for session in session_list:
        try:
            session.start()
        except IOError as e:
            print('Could not start session: ' + str(e))

translates roughly in python (3.11) to:

// [], {}
LOAD_LOCAL 0 (session_list)

// [session_list], {}
GET_ITER

[forStart]
// [iter], {}
FOR_ITER after_for

[tryStart]
// [iter, any], {}
STORE_LOCAL 1 (session)

// [iter], {session: any}
LOAD_LOCAL 1 (session)

// [iter, session], {session: any}
LOAD_METHOD 'start'

// [iter, session, method], {session: any}
CALL 1

// [iter], {session: any}
GOTO forStart

[except]
// [iter, exception], {}
PUSH_EXC_INFO

// [iter, exception, exception], {}
LOAD_GLOBAL 2 (IOERROR)

// [iter, exception, exception, IOError], {}
CHECK_EXC_MATCH

// [iter, exception, bool], {}
POP_JUMP_FORWARD_IF_FALSE finally

[ioError]
// [iter, exception], {}
STORE_LOCAL 2 (e)

// [iter], {e: Error}
LOAD_GLOBAL 5 (print)

// [iter, print], {e: Error}
LOAD_CONST 1 ('Could not start session: ')

// [iter, print, msg], {e: Error}
LOAD_GLOBAL 7 (str)

// [iter, print, msg, str], {e: Error}
LOAD_LOCAL 2 (e)

// [iter, print, msg, str, e], {e: Error}
CALL 1

// [iter, print, msg, str(e)], {e: Error}
BINARY_OP 0 (+)

// [iter, print, msg + str(e)], {e: Error}
CALL 1

// [iter, None], {e: Error}
POP_TOP

// [iter], {e: Error}
POP_EXCEPT

// [iter], {e: Error}
LOAD_CONST 0 (None)

// [iter, None], {e: Error}
STORE_LOCAL 2 (e)

// [iter], {e: None}
DELETE_LOCAL 2 (e)

// [iter], {}
GOTO forStart

[exceptionInExceptFinally]
// [iter, exception], {}
LOAD_CONST 0 (None)

// [iter, exception, None], {}
STORE_FAST 2 (e)

// [iter, exception], {e: None}
DELETE_FAST 2 (e)

// [iter, exception], {}
RERAISE

[unmatchExceptionTypeFinally]
// [iter, exception], {}
RERAISE

[exceptionInSetupCleanupFinally]
// [iter, exception], {}
POP_EXCEPT

// [iter, exception], {}
RERAISE

[forEnd]
// [], {}
LOAD_CONST               0 (None)

// [None], {}
RETURN_VALUE

ExceptionHandlers:
    Any: (tryStart, except) -> except
    Any: (except, ioError) -> exceptionInSetupCleanupFinally
    Any: (ioError, exceptionInExceptFinally) -> exceptionInExceptFinally
    Any: (exceptionInExceptFinally, unmatchExceptionTypeFinally) -> exceptionInSetupCleanupFinally

(In 3.10 and below, the ExceptionHandlers are done via the SETUP_FINALLY opcode which create the corresponding try/except blocks). In Java, the above code would instead roughly translate to:

// [], {}
LOAD_LOCAL 0 (session_list)

// [session_list], {}
INVOKE iterator()

// [iterator], {}
STORE_LOCAL 3 (iterator)

[forStart]
// [], {iterator: iterator}
LOAD_LOCAL 3 (iterator)

// [iterator], {iterator: iterator}
INVOKE hasNext()

// [bool], {iterator: iterator}
JUMP_IF_FALSE afterFor

// [], {iterator: iterator}
LOAD_LOCAL 3 (iterator)

// [iterator], {iterator: iterator}
INVOKE next()

[tryStart]

// [item], {iterator: iterator}
STORE_LOCAL 1 (session)

// [], {iterator: iterator, session: item}
LOAD_LOCAL 1 (session)

// [item], {iterator: iterator, session: item}
INVOKE start()

// [], {iterator: iterator, session: item}
GOTO forStart

[except]
// [exception], {iterator: iterator}
STORE_LOCAL 2 (e)

// [], {iterator: iterator, e: exception}
LOAD_CONST 1 ('Could not start session: ')

// [message], {iterator: iterator, e: exception}
LOAD_LOCAL 2 (e)

// [message, e], {iterator: iterator, e: exception}
INVOKE toString()

// [message, e.toString()], {iterator: iterator, e: exception}
INVOKE concat(String)

// [message + e.toString()], {iterator: iterator, e: exception}
INVOKESTATIC print(String)

// [], {iterator: iterator, e: exception}
GOTO forStart

[exceptionInExceptFinally]
// [exception], {iterator: iterator}
THROW

[forEnd]
// [], {iterator: iterator}
LOAD_CONST 0 (None)

// [None], {iterator: iterator}
RETURN_VALUE

ExceptionHandlers:
    IOError: (tryStart, except) -> except
    Any: (tryStart, exceptionInExceptFinally) -> exceptionInSetupCleanupFinally

Methods and types are objects on the stack in CPython. In contrast, methods and types are arguments to opcodes in Java. For example, this Python code:

def my_function(obj):
    return obj.my_function()

roughly translates to this bytecode in CPython

// []
LOAD_LOCAL 0 (obj)

// [obj]
LOAD_METHOD 'my_function'

// [obj, my_function]
CALL 1

// [value]
RETURN_VALUE

In Java, it would roughly translate to this instead:

// []
LOAD_LOCAL 0 (obj)

// [obj]
INVOKE ObjectType::my_function()

// [value]
RETURN_VALUE