cs1120 Problem Set 7: mini-Python
Implementing Interpreters

Collaboration Policy - Read Carefully

Remember to follow the pledge you read and signed at the beginning of the semester. For this assignment, you may consult any outside resources, including books, papers, web sites and people, you wish except for materials from previous cs1120, cs150, and cs200 courses. You may consult an outside person (e.g., another friend who is a CS major but is not in this class) who is not a member of the course staff, but that person cannot type anything in for you and all work must remain your own. That is, you can ask general questions such as "can you explain recursion to me?" or "how do lists work in Python?", but outside sources should never give you specific answers to problem set questions. If you use resources other than the class materials, lectures and course staff, explain what you used in your turn-in.

You are strongly encouraged to take advantage of the scheduled help hours and office hours for this course.

Purpose

• Understand how language interpreters work
• Understand the meta-circular evaluator
• Ruminate on the nature of univeral programming languages
• Learn how changing the evaluation rules changes programming

Background

In this problem set, we provide a working interpreter for a mini-Python language, which is approximately a subset of Python. The interpreter implements the Python evaluation rules with state. Your assignment involves understanding the interpreter and making some additions and changes to it. If you are successful, you will produce an interpreter for our mini-Python language.

Getting Started With mini-Python

Interpreter Overview

Our interpreter is divided into three different phases: tokenization, parsing, and evaluation. These roughly correspond to the main activities involved in reading English or Text Messages. For example, to understand the text message I<3U Alan you must:

1. Break it up into "words": "I", "<3", "U" and "Alan". This is called tokenization, and each "word" (or bit of non-space punctuation) is called a token or terminal.
2. Determine if the "words" form a "sentence" or not. This is called parsing, and involves checking the words against a grammar (e.g., Sentence can be Subject Verb Object, etc.).
3. Finally, understand or interpret the resulting "sentence". This is called evaluation or interpretation. (This is the stage where we know that "<3" means "love", etc.)

To see how these different phases help us interpret a program, let's consider the following simple program in mini-Python:

x = 5
if x < 6:
    print 1
else:
    print 0

String myProgram = loadFile("code/Example1");

System.out.println(Tokenizer.tokenize(myProgram)));
// [x, =, 5, NEWLINE, if, x, <, 6, :, NEWLINE, 
//         TAB, print, 1, NEWLINE, else, :, NEWLINE, TAB, print, 0, NEWLINE]

In order to parse an input String, we use the parse method defined in the Parser class:

System.out.println(Parser.parse(myProgram));
/* [[assign, x, 5], 
    [if, 
        [<, x, 6], 
        [[print, 1]], 
        [[print, 0]]]]  */

With the program parsed, we are now ready to run the program. Given an AST and an Environment object, the meval method in the Evaluator class will run (i.e., evaluate) the input program in the given environment:

// Create a new Environment to run our code
Environment env = Environment.createGlobalEnvironment();

// Parse the program
ArrayList<Object> ast = Parser.parse(myProgram);

// Run the program
Evaluator.meval(ast.get(0),env); // Evaluate x=5
Evaluator.meval(ast.get(1),env); // Evaluate the if statement
// => 1

Our example program printed out 1, just as we expected. Since meval only works on one mini-Python statement at a time, we had to break our AST in to two parts and evaluate them separately.

Breaking the AST into pieces is a bit of a pain. To help out, Evaluator defines another helpful function evalSequence, which automatically evaluates all of the AST:

Environment env = Environment.createGlobalEnvironment();
ArrayList<Object> ast = Parser.parse(myProgram);
Evaluator.evalSequence(ast, env);
// => 1

runFile("code/Example1");
// => 1

It may be challenging to understand all of the parts of our interpreter the first time you see them. We will clarify each of the parts of the interpreter and provide more detail throughout the problem set.

Practicing with mini-Python

def square(x):
	return x*x
print square(4)
print square

runFile("code/ExampleSquare")
// 16
// Interpreter.Procedure@6ba8fb1b

If you run this code on your own machine, the second printed line may be slightly different but should generally look the same.

def factorial(x):
	#Your code here
print factorial(5)

runFile("code/YourFactorial")
// => 120

The Parser

The Parser takes a sequence of tokens from the tokenizer (as a TokenStream, which is really just an ArrayList of strings), and attempts to derive them using the rules of the grammar for our mini-Python language (just like you did in Problem Set 3). If the sequence of tokens is in the language of the grammar, our Parser produces a nice tree structure, which exactly diagrams the structure of our program.

To see how this works, let's see how our interpreter parses if statements (recall that mini-Python requires an else: branch for each if). In the Parser class, we define the method parseIf as follows:

public static ArrayList<Object> parseIf(TokenStream tokens) {
		// Make a new ArrayList to store our parsed If statement
		ArrayList<Object> retval = new ArrayList<Object>();
		
		// Make "if" the first element of our output list
		retval.add("if");
		tokens.munchAssert("if");
		
		// Parse the condition
		retval.add(parseExpression(tokens));
		
		// Parse the true clause
		tokens.munchAssert(":");
		retval.add(parseSequence(tokens));
		
		// Parse the false clause
		tokens.munchAssert("else");
		tokens.munchAssert(":");
		retval.add(parseSequence(tokens));
		return retval;
	}

["if", condition, true-clause, false-clause]

• String munch() - Returns the first token in the TokenStream and removes it from the list. For example, if we call munch on the list ["a","b","c"], it will return "a" and change the list to ["b","c"].
• void munchAssert(String val) - Also removes the first token in the TokenStream, but instead of returning it it checks that it has the value val and throws an error if it does not. This is used to check for tokens that must be present, like : in Python.

Now that we know how TokenStream works, let's see what happens when we run parseIf with a subset of the tokens from our earlier example:

["if", "x", "<", "5", ":", "INDENT", "print", "1", 
    "DEDENT", "else", ":", "INDENT", "print", "0", "DEDENT"]

["x", "<", "5", ":", "INDENT", "print", "1", 
    "DEDENT", "else", ":", "INDENT", "print", "0", "DEDENT"]

IfStatement := if Expression : Sequence else : Sequence

[":", "INDENT", "print", "1", "DEDENT", "else", ":", 
    "INDENT", "print", "0", "DEDENT"]

After performing all of these calculations, evalIf returns the following list:

["if", ["<", "x", "5"], [["print", "5"]], [["print", "6"]]]]

which represents the abstract syntax tree for our if statement. Note that you do not need to understand how parseSequence and parseExpression work, but you may refer to their commented definitions in Parser if you are curious.

Adding Loops

i = 1
while i <=10:
	print i
	i = i + 1

int i = 1;
while(i <= 10) {
	System.out.println(i);
	i = i + 1; // or i++;
}

In the next few problems, we will add support for while loops to mini-Python. We will do this in two parts. We first have to add the while loop to the Parser, then we will add the code that actually runs the while loop in the Evaluator.

Once completed, you should be able to get the following results by running this code in Main.java:

System.out.println(Parser.parse(loadFile("code/TestQuestion3")));
// => [[while, [<, i, [-, max, 1]], [[print, i], [assign, i, [+, i, 1]]]]]

while i < max-1:
	print i
	i = i + 1 

The Evaluator

meval

  
	public static Object meval(Object expr, Environment env) {
		    ...
		    ArrayList<Object> exp = (ArrayList<Object>) expr;		

            // To keep things simple, the first element of 
            // the list is always the operation. That's why we
            // went to the trouble of representing "1<2" as ["<","1","2"]
			Object operation = exp.get(0);

			// Function Definitions
			if (operation.equals("def")) {
				return evalDef(exp,env); 
			}
			// If Statements
			else if (operation.equals("if")) {				
				return evalIf(exp,env);
			}        
            ...
            // Multiplication
			else if (operation.equals("*")) {
				return evalMult(exp,env);
			}
            ...
            // Less Than
			else if (operation.equals("<")) {
				return evalLessThan(exp, env);
			}
            ...
	}

Environments

Errors

throw new EvalError("error_message");

Evaluating Simple Expressions

Note that for these last two examples, we cannot immediately compare two numbers, since we do not know the value of x or (x*y/2) right away. To determine the value of these expressions, we need to first evaluate them using meval. After evaluating both expressions, we should have two integers, which we can then compare and return True or False accordingly.

This is demonstrated in the evalLessThan method included below, which evaluates ComparisonExpressions that have the format ["<", expression1, expression2] :

	public static Boolean evalLessThan(ArrayList<Object> exp, Environment env) {
		// Evaluate the two expressions we'll be comparing
		Object v1 = meval(exp.get(1),env);
		Object v2 = meval(exp.get(2),env);
		
		// Check that both values are indeed integers
		if (v1 instanceof Integer && v2 instanceof Integer) {
			
			// Perform the actual calculation
			return (Integer)v1<(Integer)v2;
		}
		
		// Throw an error if we try to compare non-Integers
		throw new EvalError("Cannot compare " + v1 + " and " + v2);
	}

Once completed, you should be able to get the following results by running code in Main.java:

runFile("code/TestQuestion4");
// => True, True, False, False

def return6():
	return 6
x = 5
print (x <= 5)
print (x <= (return6()))
print (x <= (return6()-2))
print (10 <= (10-20))

Evaluating Loops

runFile("code/TestQuestion5");
// => 0, 0, 1, 0, 1, 2

def looptest(x):
	i = 0
	sum = 0
	while (i < x):
		j = 0
		while j < i:
			print j
			j = j+1
		i=i+1
looptest(4)

Lists

Our implementation for parseElement is based on the mini-Python grammar rule for list element accesses:

ElementExpression := PrimitiveExpression ElementAccess
ElementAccess := [ Expression ] ElementAccess | ε

x = [[1,[3,4,5]],[2,3],[7,9]]
print x[0][1][1]
# => 4

Evaluating Lists

Once completed, you should be able to get the following results by running code in Main.java:

runFile("code/TestQuestion7");
// => [1,2,3], [2,4,3,-5], 6

print [1,2,3]
print [1+1,2*2,9/3,5-10]
print |[1,2,3,4,5,6]|

Note that the vertical bar syntax |x| in mini-Python is equivalent to len(x) in normal Python. You will not need to implement anything related to this syntax in this problem set.

Once completed, you should be able to get the following results by running code in Main.java:

runFile("code/TestQuestion8");
// => 9, 1, 7, 3, 2, 5

myList = [9,1,7,3,2,5]
i = 0
while i<|myList|:
	print myList[i]
	i = i+1

Checking for List Equality

Once completed, you should be able to get the following results by running code in Main.java:

runFile("code/TestQuestion9");
// => True, False, True, False, True

print [1, 2, 3] == [1, 2, 3]
print [1, 2] == [1,2,3]
print [[1,2], True] == [[1,2], True]
print [5] == False
print [[]] == [[]]

Submitting Your Assignment