Assignment 3: Virtual Machine

Your goal for this assignment is to implement a bytecode compiler and interpreter for the MITScript Virtual Machine. Your bytecode compiler will take as input your parsed MITScript AST and generate a bytecode-style intermediate representation. Given that intermediate representation, your interpreter will execute the bytecode to produce the program's results.

Deadline: March 23rd, 2018

MITScript Virtual Machine (by Example)

The MITScript VM provides a stack-based machine abstraction of the execution of a program.

As discussed in lecture, virtual machines provide a syntax-independent and platform-independent (e.g. x86) mechanism to specify a program representation and execution model. As a strong distinction between your bytecode interpreter from Assignment #2, your representation here is flat in that the body of a function is a straight-line sequence of simple non-recursive operations.

The MITScript VM abstracts an MITScript program into a single function that 1) contains multiple nested functions (each of which correspond to the creation of a closure) and 2) has a list of instructions that when executed augment an operand stack and the heap.

We illustrate the basic structures of an MITScript VM bytecode representation with the following MITScript program snippet:

x = 1;
y = 2;
z = x + y;

One possible translation of this MITScript program snippet to an MITScript bytecode representation is the following:

function
{
  functions = [],
  constants = [1, 2],
  parameter_count = 0,
  local_vars = [x, y, z],
  local_ref_vars = [],
  free_vars = [],
  names = [ ],
  instructions =
  [
    load_const  0
    store_local 0
    load_const  1
    store_local 1
    load_local  0
    load_local  1
    add
    store_local 2
  ]
}

Functions

A function consists of a sequence of instructions as well as additional supporting metadata for the function. In the abbreviated presentation of this example, this additional metadata includes the function's constant pool (the list of constants used by the function's instructions) and the function's locals (the list of local variables in the function).

Instructions

An MITScript instruction consists of an operation code and an optional operand (which we refer to as operand 0). For example, the instruction load_const 0 loads the constant at index 0 of the function's constants. The mnemonic or name for the operation code is load_const and operand 0 is the integer value 0. The meaning of load_const 0 for this example is to load the value 1 and push that value onto the function's operand stack.

Operand Stack

The MITScript VM maintains an operand stack while executing the sequence of instructions within a function. The operand stack is a standard stack (or LIFO queue) that stores intermediate values during the execution of the function. Instructions receive their input operands (excluding operand 0) by popping values off of the operand stack. Instructions produce values by pushing their results onto the stack.

As a note, each function execution maintains its own operand stack. Therefore, if a function calls another function, the virtual machine creates a new, empty operand stack for the second function that only the second function operates on. Once invocation of the second function returns, the virtual machine deallocates its operand stack.

Step-by-Step Example

We next illustrate the execution of the above function step-by-step. We present the contents of the function's frame and operand stack both before and after each instruction with their values specified in braces.

{ Frame: {x : uninit , y : uninit, z : uninit}, Stack : { } }
0: load_const 0
{ Frame: {x : uninit , y : uninit, z : uninit}, Stack : { 1 } }

The load_const i instruction pushes the ith constant in the function's constant pool onto the operand stack. In this case, the 0th constant is the integer value 1.

{ Frame: {x : uninit , y : uninit, z : uninit}, Stack : { } }
1: store_local 0
{ Frame: {x : 1 , y : uninit, z : uninit}, Stack : { } }

The store_local i instruction stores the top of the operand stack into the function's ith local variable as determined by the function's locals array. The instruction also pops or removes the top value of the operand stack. In this case the 0th variable is the variable x.

{ Frame: {x : 1 , y : uninit, z : uninit}, Stack : { } }
2: load_const 1
{ Frame: {x : 1 , y : uninit, z : uninit}, Stack : { 2 } }

As above, load_const i loads the ith constant onto the operand stack. In this case the constant is the integer value 2.

{ Frame: {x : 1 , y : uninit, z : uninit}, Stack : { 2 } }
3: store_local 1
{ Frame: {x : 1 , y : 2, z : uninit}, Stack : {  } }

As above, store_local i stores the top of the operand stack into the function's ith local variable. In this case, the 1st variable is the variable y.

{ Frame: {x : 1 , y : 2, z : uninit}, Stack : {  } }
4: load_local  0
{ Frame: {x : 1 , y : 2, z : uninit}, Stack : { 1 } }

The load_local i instruction reads the value of the function's ith local variable and pushes onto the top of the operand stack. Because the function's 0th local is the variable x and its value is the integer value 1, the instruction pushes 1 onto the operand stack.

{ Frame: {x : 1 , y : 2, z : uninit}, Stack : { 1 } }
5: load_local  1
{ Frame: {x : 1 , y : 2, z : uninit}, Stack : { 1, 2 } }

As per the reasoning above, this instruction pushes the integer value 2 onto the operand stack. Note that the top of the stack is the rightmost element.

{ Frame: {x : 1 , y : 2, z : uninit}, Stack : { 1, 2 } }
6: add
{ Frame: {x : 1 , y : 2, z : uninit}, Stack : { 3 } }

The add instruction pops two elements off of the top of the stack, performs the addition of the two elements, and pushes the result back onto the top of the stack. Note that unlike the other instructions, this instruction does not have an operand 0.

{ Frame: {x : 1 , y : 2, z : uninit}, Stack : { 3 } }
7: store_local 2
{ Frame: {x : 1 , y : 2, z : 3}, Stack : { } }

As described previously, the store_local i instruction stores the top of operand stack into the specified local variable.

MITScript Virtual Machine

The MITScript VM refines the values, program state, and errors of MITScript as seen in Assignment #2.

Values

As in Assignment #2, the MITScript VM includes the following values:

The MITScript VM also includes the following values:

To illustrate these values, consider the following MITScript program:

x = 1;
f = fun(y)
{
  g = fun(z)
  {
     return x + y + z;
  };
};

The most important aspect to this example is the code inside g in that it accesses the global variable x, the reference variable y, and the local variable z. In the MITScript VM, each of these variables have different access instructions as well as different runtime machinery to support their execution. To understand these differing implementations, consider the following bytecode translation for this program:

function 
{
  functions =
  [
    function
    {
      functions =[
        function
         {
          functions  = [],
          constants  = [],
          parameter_count = 1,
          local_vars = [z],
          local_ref_vars = [],
          free_vars  = [y],
          names = [x],
          instructions = [
             load_global 0
             push_ref    0
             load_ref
             add
             load_local  0
             add
             return
          ]
         }
      ],
      constants = [None],
      parameter_count = 1,
      local_vars = [y, g],
      local_ref_vars = [y],
      free_vars = [],
      names = [],
      instructions = [
        load_func     0
        push_ref      0
        alloc_closure 1
        store_local   1
        load_const    0
        return
       ]
    }
  ],
  constants = [None, 1 ],
  parameter_count = 0,
  local_vars = [],
  local_ref_vars = [],
  free_vars = [],
  names = [x, f],
  instructions =
  [
    load_const   1
    store_global 0
    load_func    0
    alloc_closure 0
    store_global 1
  ]
}

Functions: In the MITScript VM, each function includes an expanded set of metadata that capture the semantics of managing local variables (including parameters).

Variables: Given this metadata, we can now distinguish and give a semantics to the machinery of variable access.

Closures: To support reference variables, creating closures on the MITScript VM is different than the corresponding implementation in Assignment #2. In Assignment #2, a closure consisted of a function to execute, as well as a pointer to the frame to be used as a parent frame when executing the function.

In the MITScript VM, instead of taking a pointer to a frame, a closure takes a list of references to the free variables in the nested function. This design is more efficent in that each access to variable inside the function need not recursively search its ancestry of frames to find the appropriate value for the variable.

The instructions for the functionf above illustrates how f creates a closure for variable g. The instruction sequence first pushes a reference to y onto the stack (via the push_ref 0 instruction), and then pushes the function that corresponds to g (load_func 0).

The alloc_closure instruction, consumes and stores the function and variable references and then asserts that the number of passed variable references matches the number of free variables in the function.

The files VirtualMachine/types.h and VirtualMachine/instructions.h give a more precise explanation of a function's instructions and metadata.

Program State

Frames: A stack frame in MITScript includes 1) dedicated storage for the value of local variables, 2) dedicated storage for local variable references that are accessed/passed in/passed by reference, and 3) an operand stack.

Heap: Some of your runtime structures will be allocated in a heap. It is up to your discretion as to how you store an MITScript's data and runtime structures for this assignment.

Errors

The MITScript VM reports the same exceptions for the error conditions as in Assignment #2. At the bytecode level, however, there are also new opportunities for execution to encounter an error. For example, consider this alternative translation of our first MITScript program:

function:
  local_vars = [x, y, z],
  constants = [1, 2],

  instructions =
  [
    0: load_const  0
    1: store_local 0
    2: load_const  1
    3: store_local 1
    4: load_local  0
    5: add
    6: store_local 2
  ]

In this case, the bytecode compiler has failed to generate the code to load the value of y prior to the add instructions on line 5. The height of the operand stack prior to line 5 is 1 and, therefore, the add instruction will fail because it cannot pop its two necessary operands from the stack.

Your bytecode interpreter should generate the following additional exceptions:

Your interpreter should also generate a RuntimeException if the provided bytecode attempts to perform an operation with objects that were not given a semantics in Assignment #2. For example, if the bytecode attempts to print a variable reference, then your interpreter should generate a RuntimeException.

Native Functions

For this assignment, we will use the convention that the first three indices in the functions list of the outermost function (the function for the whole program) correspond to the print, input, and intcast functions, respectively. The function's specified at the top level of the program's source code should therefore be indexed by an integer greater than 2. Plan for your generated bytecode to include a prologue that explicitly creates closures (load_func, alloc_closure) for the native functions and assigns them to the corresponding variables (print, input, and intcast) in the global frame.

Your bytecode interpreter should detect when one of these functions has been called and perform the correct action.

Skeleton

We have added a directory to the project skeleton that includes specifications and data structures for MITScript instructions and types (instructions.h and types.h). We have also included a pretty printer that will turn a bytecode data structure into a string. In addition, we have provided a bytecode parser that parses bytecode as specified as text in a file and produces a bytecode data structure. If you find an issue with the provided pretty printer or the bytecode parser (e.g., it may not correctly identify variables with the same name as an instruction), you do not need to fix the issue. We will not test your system on programs that exercise an error in the pretty printer or bytecode parser.

Deliverables

You will deliver a compiler, an interpreter, documentation, and test cases

Compiler

Your compiler should translate the AST representation of an MITScript program to a single bytecode function and pretty print the bytecode to standard output (the command line). We have included a pretty printer class as part of the skeleton that may use to pretty print your bytecode representation for output.

As explained above, the definition of a function within the program should be located within the function's field of that function's parent function. If the function does not syntatically have a parent function (it is defined at the top level), then its parent should be the single bytecode function that you generate for the whole program.

Please call the compiler binary mitscriptc. The first argument to the binary should be the filename.

Interpreter

Your interpeter should interpret your compiled bytecode representation and produce its results. Your intereter should support two modes of operation:

  1. MITScript Source: if passed the option -s on the command, then it should parse the input as MITScript source code. In this case, your system should use your bytecode compiler generate the bytecode intermedate representation in memory (you do not need to output it to standard output). Your implementation should then interpret the bytecode intermediate representation.

  2. MITScript Bytecode: if passed the option -b on the command line, then it should treat the input as MITScript VM bytecode. We have provided a bytecode parser in the skeleton to help support this mode of operation.

Please call the interpreter binary mitscript. The first argument to the binary should be the flag, and the second should be the filename.

Test Cases

In addition to your compiler and interpreter, you should submit 5 tests named bytecodetest[1-5].mit. Your tests should not use the input function, but should use print.

Evaluation

We will evaluate your implementation in two ways. For the compiler, we will execute your compiler on a number of test programs to generate bytecode for each program. Given that bytecode, we will execute it on our own reference bytecode interpreter to verify that your compiler produces correct bytecode. To validate correctness, we will verify that the output of the reference bytecode interpeter when executed on your generated bytecode matches that of the MITScript semantics. For the interpreter, we will execute your interpreter on test programs written in bytecode that may be from either your compiler or from our own reference bytecode compiler. To validate correctness, we will verify that the output of your interpreter when executed on the bytecode matches that of the MITScript semantics. To support these evaluations, your compiler and your interpreter should faithfully adhere to the semantics of each MITScript bytecode instruction.

Submission Instructions

As before, submission of your assigment should be accomplished by pushing your code to a branch with the name a3-submission.

The last assignment pushed to this branch before the assignment due date is the one we will grade unless you notify us otherwise.

Implementation Notes

There are two main programming patterns that you will see in this assignment: the visitor pattern and the interpreter loop.

As a group, you should plan to use your interpeters from Assignment #2 to provide a reference semantics for Assignment #3. This will help with debugging. Note that across the different interpreters from your group members, you may find inconsistencies in your own approaches. So, using only a single interpreter may not be optimal unless you verify that a single one is the best. Instead you are more likely to find issues if you reference all of your interpreters. This technique (using multiple software implementations of a single specification) is called N-version programming and -- broadly -- can be helpful in some scenarios.