Phase 2: Interpretation

Your goal for this assignment is to create an interpreter for the MITScript language. For this assignment you will use the MITScript Language Specification (link) to inform your interpreter implementation.


You will deliver an interpreter, test cases, and documentation (see Project Overview for documentation specification).


Your interpreter should read an input program from a file whose name is given on the commandline and produce the output of the program according to the semantics given in the MITScript Language Specification.

Test Cases

You will submit 10 test cases, titled, …, Your tests should not use the input function, but should use print to produce an output.

Simiar to Phase 1, submission of your assigment should be accomplished by pushing your code to a branch with the name a2-submission. The last commit pushed to this branch before the assignment due date is the one we will grade.


We will be evaluating your interpreter by passing it programs and verifying that the output of your interpreter matches that of our reference implementation.

Important: because we are testing the textual output, make sure your interpreter does not produce any unnecessary output (e.g., logging or debugging output); it should only produce the output as specified in the semantics.

Implementation Notes

Skeleton Code

In your repository in interpreter/interpreter.cpp we have included a simple driver for your interpreter that illustrates its basic setup. Execute the command git pull 6s081 master within your repository to bring in the latest changes (if any).

Unlike Phase 1, one change to be mindful of is that your interpreter should take the input program from a file instead of standard input. The reason why is because MITScript programs support an input function that reads user-input from the commandline, which is separate from the input program. We have provided simple code to read from a file in the skeleton.

In interpreter/Makefile we have also included a make target to support the command make interpreter , which then produces an exectuable named mitscript in the same directory.

Inference Rules to Visitors

Use visitors (the bread and butter of compiler implementation) to implement the inference rules included in the specification.

Note, however, that visit functions in the visitor takes as input an AST Node (e.g., an expression) and return void whereas an evaluation relation like (Γ,h,e)(h,v)(\Gamma, h, e) \rightarrow (h,v) means that your implementation will take as input a stack and a heap – in addition to the expression – and produce a heap and a value.

Produced Values

You are free to implement this as you see fit. However, one way to modify your visitor to – conceptually – be able to return more than just void is to use instance variables in your interpreter to store the return value:

class Interpreter : public Visitor 
  Value* rval_;

Then, when visiting expressions, you can enforce the property that every visit method for an expression sets the value of rval_ to the result of evaluating that expression.

So for example, when visiting a binary expression expr, your code can operate as follows:

void visitBinaryOp(BinaryOp* expr)
  Value* leftVal = rval_;

  Value* rightVal = rval_;

  rval_ = computeBinaryOp(expr->op, leftVal, rightVal);


You can also use an instance variable to keep track of the stack. For example, you add the following variable to your interpreter:

std::stack<Frame*> stack_;

When your implement needs to refer to or manipulate the stack, it can simply use the instance variabe.


In the case of the heap (a map from address to values), there is no need to define your own heap. Instead, your implementation already has a heap: the heap maintained by the C++ runtime!

Thus, for example, at any point in the semantics where you should allocate an address and map a value to that address, you can implement this by allocating memory for that value within your interpreter implementation (i.e., by using new Integer).