Code as a value

The implementation of the stack machine assumes that all inputs to an operation have to be resolved prior to the execution of the operation. This means the operation tree is traversed using a depth-first traversal until the interpreter finds an operation where all the inputs are resolved.

This is not sufficient, however, to represent more complicated control flow. Let’s look at a conditional operation, using the Python language:

if a == 5:
    something()
else:
    something_else()

A naïve representation of the operation tree would look like the following:

Figure 11.1: Naïve operation tree for a conditional

However, if we consider how the stack machine is currently implemented, this would result in both branches of the conditional being evaluated before the condition itself is evaluated. This is not what was intended.

To solve this problem, we need to start by being able to represent the code to be executed in each branch...