Virtual Machines

Stack Addition

As we know, addition is a binary operation of the form ${a + b.}$ Thus, to perform addition with a stack, we perform the following:

1. Pop the first operand.
2. Pop the second operand.
3. Add the two popped values.
4. Store the result in the top most frame (where the second operand once was).

Visually, this process looks like:

Stack Negation

Negation is a unary operation of the form ${-a.}$ Thus, to negate a value, we pop the topmost frame, negate the popped value, then push the result back to the stack:

General Form of Stack Arithmetic

Examining these two procedures, we see that stack arithmetic follows a general procedure:

• To apply a function ${f}$ on the stack:
  1. Pop ${f}$'s arguments from the stack.
  2. Perform ${f}$ on the popped arguments.
  3. Push the result of ${f}$ onto the stack.

How Are Functions Executed?

Before we examine the implementation, there are a few key points we should understand about how how computers, in general, execute functions. First, functions can be thought of as "mini programs." Viewed in this manner, it follows that functions need memory to perform their operations. Accordingly, whenever we call a function, we need stack and the associated memory segments.

Second, computer programs will usually consist of many functions. Given a sufficiently complex program, it may look like thousands of functions are executing. This is not the case. At any given point in time in a program, only one function in the program is running.

For example, suppose we had a program with the following structure:

int h(a) {
	// code
}
int g(m) {
	// code
	h(m)
}
int f(n) {
	// code
	g(n)
}

int x = f(2)

This structure has a specific call chain or call sequence:

Every single one of the functions above has some state — private worlds of their own — and these states must exist as long as the function is on the call chain. Otherwise, we either wouldn't have a chain at all, or we'd have functions colliding with one another.

So how do we ensure the functions get worlds of their own? By creating a new stack for each function call. Thus, whenever we make a function call, the following facts apply at run time:

1. Once the function starts running, two events occur:
   1. A new working stack is created for the function.
   2. Memory segments are allocated for the function.
2. The working stack and memory segments are maintained as long as the function is executing.
3. When the function finishes executing, the memory is released for others to use (i.e., "recycled" or "freed").

The third point is particularly important to take note of. If we never release the memory, we'd consume far too much memory. Knowing these facts, let's consider an example. Suppose we had the following program in some language:

int multiply(int x, int y) {
	int sum = 0;
	int n = 1;
	while !(n > y) {
		sum += y;
		n++;
	}
	return sum;
}
int main() {
	int x = 3 + multiply(5,8)
	return x;
}

This program consists of two functions, main and multiply. When we send this court code to the the compiler, it generates VM code that might look like the following (source code to the left and pseudo VM code to the right):

int multiply(int x, int y) {
	int sum = 0;
	int n = 1;
	while !(n > y) {
		sum += y;
		n++;
	}
	return sum;
}

function multipy 2
	push constant 0
	pop local 0
	push constant 1
	pop local 1
label LOOP
	push local 1
	push argument 1
	gt
	ifgoto END
	push local 0
	push argument 0
	add
	pop local 0
	push local 1
	push constant 1
	add
	pop local 1
	goto LOOP
label END
	push local 0
	return

int main() {
	int x = 3 + multiply(5,8)
	return x;
}

function main 0
	push constant 3
	push constant 8
	push constant 5
	call multiply 2
	add
	return

Making these calls results in two separate states: A state for main (the caller), and a state for multiply (the callee).

How do we ensure that these states are saved? Well, let's go back to our earlier proposition: At any given point in time in a program, only one function is executing. This means that the only function that can return (i.e., terminate) is the function that's currently running. This means that in our call chain, all of the functions to be called after the current function must wait for the current function to return. This means that the call chain lengthens and shortens with each function call.

Looking at how this grows and shrinks, we can see that this can actually be viewed as a stack. Using this perspective, we see that the call pattern follows LIFO (last-in-first-out):

Building on this observation, let's see how we might save function states using a stack. Say we're inside a function main(), and make the call multiply(17,21). Big-picture-wise, the call looks like:

Clearly, there are a series of steps that lead to this result. Let's examine each step. First, when we call main(), we get a stack and memory segments. Nothing new:

Eventually, as main()'s commands are executed it encounters a call f nArgs command, where nArgs is the number of arguments for the function call. This results in the following:

Pause. Let's look at what's going on here. First, recall that a function call has the form ${f(arg_0, arg_1, \ldots, arg_n).}$ Each of those arguments have a value. And since those arguments have values, they're each pushed onto the stack. Once those values are pushed, the ARG pointer is set to point at the first argument from the call.

Second, recall that we have to save the state of the caller (in this case main()). That state consists of:

1. The caller's current working stack, and
2. The caller's currently used segments

Beause we're using a stack data structure, the first part of the state is taken care of. It's already saved. The second part is where we need additional memory. So, we push a few more values onto the stack. These values are the function's return address and the pointers to the function's currently used segments (e.g., the pointers to the local segment, argument segment, this segment, etc). This area of the stack is called the caller's function frame.

With all of this data saved, we can now jump to the instruction function f nVars, where nVars is the number of local variables for f. This results in the following:

Above, a local segment is set up for f(). Once the local segment is set up, the f() can begin executing. Its working stack grows and shrinks, just as it would if it were the function main():

Once all of f()'s commands have finished executing, the function pushes its return value to stack. Once that value's pushed, the return instruction is executed. This results in the following:

Several things occur when the return instruction is executed:

1. First, the return value that was just pushed by f() onto the stack is copied onto argument 0 (the place where the first argument in the call to f was pushed).
2. Second, the caller's (main) segment pointers are restored. This is done by using the function frame set up earlier (in the diagram, the grey blocks).¹
3. Third, we clear f's entire working stack (freeing the memory).
4. Fourth, we set back up the caller's (main) stack pointer, having it point just after the return value.
5. Finally, we jump back to the return address of the caller's code, and continue executing the caller's instructions.

The end result:

A few things to note about this implementation. First, as we can likely tell, this isn't a trivial implementation. And this shouldn't be surprising. The ability to execute function instructions is akin to a primitive brain. We're implementing a machine that can, in the middle of performing some task ${A,}$ go out and perform another task ${B,}$ then come back and pick up where it left off in ${A.}$ That's a non-trivial action, and humans themselves occassionally fail it ("Where was I?").

Second, the introduction of function calls now creates the notion of a global stack. Examining the preceding example, we can imagine a situation where f() calls g(), g() calls h(), h() calls i(), and so on. The sum of all these functions constitutes the global stack.

Third, because of how large the global stack can be, when we program in a higher-level language and have to deal with memory issues, it's often easier to think of function calls rather than the individual elements of the global stack. This is done by dividing the global stack into function blocks__ or __call frames:

By making these divisions, we can analyze programs with a higher-level abstraction called the call stack:

Example: Recursive Functions

To tie it all together, let's consider an example with a recursive implementation of the factorial function. The code to the right is the function written in some higher-level language, and to the left is the function in pseudo VM code:

int factorial(int n) {
	if (n == 1) {
		return 1;
	} else {
		return n * factorial(n - 1);
	}
}

int main() {
	return factorial(3);
}

function main      // main()
	push 3
	call factorial
	return
function factorial // factorial()
	push n           // test condition
	push 1
	eq
	if-goto BASECASE // conditional branching
	push n           // else block
	push n
	push 1
	sub
	call factorial
	call mult
	return
label BASECASE     // base case label
	push 1
	return

Let's walk through this code. First, the function main() is called. The function's instructions are executed as usual. Then, it encounters call factorial. So, we jump to the function factorial(n) instruction.

Once we're at that instruction, we push n and push 1. Then we check the if-block's test condition: Run the command eq on n and 1. If the result is true, we jump to the BASECASE label. This label is automatically generated by the compiler (more on this later). This takes care of the if-block.

Now we turn to the else-block. We get to this block if the test condition earlier failed. If it did, we want to execute the command n * factorial(n-1). This command needs three arguments: One n, another n, and a 1. So, we make the pushes: push n, push n, and push 1. Once those values are pushed onto the stack, we subtract that last two things we pushed: n and 1.

Now we have to call factorial. This first call cannot return until this new factorial call returns. Thus, we go through the process again, this time with the new arguments supplied. Only after the new call returns do we execute the remaining instructions: call mult and finally, return.

A few things to notice about this example. First, given what we know, this implementation of factorial is virtually guaranteed to hit a stackoverflow for large values of n. Second, if we look at the virtual machine code, this is really not all that different from iteration. The only real difference is, we're reusing the function's commands within the function itself. This should dispell some of the magic behind recursion. At the computer's depths, it's really just another way to implement loop.

As an aside, more accurate pseudo VM code might look like:

function main 0
	push constant 3
	call factorial 1
	return
function factorial 0
	push argument 0
	push constant 1
	eq
	if-goto BASECASE
	push argument 0
	push argument 0
	push constant 1
	sub
	call factorial 1
	call mult 2
	return
labl BASECASE
	push constant 1
	return
function mult 2

Implementing Call & Return Statements

Let's consider a few possible implementations. First, let's say we had the following source code in some language:

class Math {
	int mult(int x, y) {
		return x * y;
	};
}

int main() {
	int a = 3;
	int b = -Math.mult(19, a);
}

We'll use the source code above to guide us through a possible implementation of the call and return operations. In pseudo VM code, the source code might be compiled to:

function main
	push local 3
	push constant 19
	call Math.mult 2
	neg
	return
function Math.mult 2
	// multiplcation code
	push local 1
	return

Notice what the pseudo VM code looks like. They're just functions. The notion of a class is just a high-level abstraction. At the virtual machine level and below, they reduce to functions.

The call and return statements in a language are implemented through a set of protocols, or contracts — a set of rules and conditions that the entities performing the operation must always abide by. For functions, these entities are the caller and the callee. For the caller, these rules apply:

1. If the caller is a callee, it follows the callee protocol, alongside the rules below.
2. Before the caller makes a call to another function, it must push as many arguments as the callee expects to receive.
3. After pushing the arguments, the caller will invoke the function by using a command called call <function-name> <nArgs>.
4. After the caller returns, the arguments the caller pushed before the call disappear from the stack.
5. After those arguments disappear from the stack, the callee's returned value will occupy the space of the first argument pushed.
6. Finally, all of the caller's memory segments are exactly as they were before the call, other than specified segments like temp or static.

For the callee, these rules apply:

1. When a callee receives a call and before it starts executing:
   1. Its argument segment has been initialized with the argument values passed by the caller.
   2. Its local variables have been allocated and initialized to zero.
   3. The static segment has been set to the static segment of the file the callee is defined in.
   4. Certain specified segments like this, that, and pointer are undefined upon entry.
   5. The callee's working stack is empty.
   6. The callee will always push some value onto the stack.²
2. If a call is made to another function, the callee follows the caller protocol, alongside the rules above.

Simple Approach

The simple approach is to design the translator as a program of three parts:

• A parser (named Parser) that parses each VM command into lexical elements. This is the program that breaks the stream of virtual machine code into smaller, meaningful parts.
• An encoder (named CodeWriter) that will take and implement the parser's output.
• A driver (a program called Main) that will conduct and direct the entire process (the VM translator's "brain").

For the main driver, the process works as follows:

1. First, the driver takes as input some file containing virtual machine chode. In languages like Java, these are files with extensions like Main.class.
2. The moment it receives this file, the driver constructs a new parser to parse the input file, and a codewriter to handle the output file.
3. After constructing the other two components, the driver goes through the file, line by line. At each line, the parser parses the code and feeds it to the codewriter.
4. The codewriter then takes the parsed elements, outputting it to an Assembly language file.
5. The end result is some file with an Assembly language extension (e.g., .asm).

Now let's consider the other two components, starting with the parser.