CIT 594 Bugs Interpeter, part 1
Spring 2008, David Matuszek

Purposes:

Give you more practice with

recursion
general trees

hash tables

General Idea:

Given a program in the Bugs language, you now can create an AST (Abstract Syntax Tree) for it. The next step is to interpret the AST, so that your Bugs program "does something."

In this assignment you will write the first half of the interpreter. (The next assignment will be to complete the interpreter.) We will leave three things for later: Implementing function calls, displaying the bugs' actions on the screen, and coordinating the actions of multiple bugs.

Now might be a very good time to review The Bugs Language.

Algorithm:

Name your Bug interpreter class Bug.

Two fundamental methods are needed:

public double evaluate(Tree<Token> tree), for parts of the tree (mostly, expressions) that need to return a value, and
public void interpret(Tree<Token> tree), for parts of the tree (such as statements) that do not return a value.

You will begin by calling interpret with the root node of a Bug (the AST representing a

<bug
definition>

. To interpret this node, you interpret each of its five children, as follows:

Save the name of the Bug in an instance variable.
Interpret the list of var declarations.
Interpret the initialization block.
Interpret the block (of commands).
For this assignment, ignore the list of function declarations.

As you see, this is basically a recursive walk of the AST, where each type of node is interpreted differently, according to its type (for example, a loop node will walk its children repeatedly). Some nodes, such as an assignment node, may cause certain children to be evaluated, rather than interpreted, and it will be obvious when to do this.

Note: Although the interpretation proceeds top down, starting at the Bug root, you will need to write the methods by starting at the bottom and working your way up (just as you did in the Recognizer and Parser), so that you can test as you go. Of course, full JUnit testing is required.

For keeping track of variables and their values, write the following two methods:

void store(String variable, double value) is used to perform the assignment variable=value.
double fetch(String variable) is used to retrieve the current value of variable. (If there is no such variable, throw some kind of RuntimeException.)

These methods use a HashMap<String, Double> to keep track of the values of variables. However, there are three variables that need to be treated specially: x, y, and angle. These do not go into the HashMap, but are instance variables of the Bug class, for reasons that should become clear when we implement functions. Make sure that store and fetch handle these three variables correctly.

Details:

These are more-or-less in the order given in the Bugs Grammar, not in the order you need to write them. Remember, bottom up!

Nodes to be "processed" rather than interpreted:

"Interpreting" code means to execute it--to do what it says to do. The following nodes are "processed," that is, we pull some information out of them and store it in tables. We do this part in a separate Interpreter class, not in a Bug class.

program

Part 2. Process the Allbugs part. Then, for each "Bug" node, create a Bug object. The constructor should take as arguments the Bug's name, the Bug's AST, and a reference to the Interpreter that created the Bug. Save each Bug in a HashMap<String, Bug> , using the Bug's name as key.

Allbugs

Part 2. Create the following tables:

A HashMap<String, Double> to store the var declarations (with initial values of 0.0).
A HashMap<String, Tree<Token>> to store the function definitions.

function

Part 2. The constructor for your Bug class should have an instance variable HashMap<String, Tree<Token>> functions. Add each function definition to this HashMap, using the function name as the key, and the complete tree rooted at the function node as the value. (Actually interpreting the function will be done by a call node.)

Nodes to be interpreted:

Bug

Interpret the bug as described above. Part 2. The Interpreter begins the interpretation for each bug.

list

Interpret each node in turn.

var

store each named variable, with an initial value of zero.

initially

Interpret its (one) block child.

block

Interpret each statement in turn. Quit interpreting statements if the boolean "exiting loop" flag has been set.

move

Evaluate the expression child, and "move" this Bug forward (its angle tells what direction it is facing) by that amount, by setting new values of x and y. You will need a small amount of trigonometry to determine the new values of x and y; get help from a classmate if necessary. Part 2. The Bug is supposed to draw a line as it moves (unless its color is set to none). Create a Command object that specifies the color and endpoints of the line, and save it in a list. Notify the Interpreter that this bug has performed an action.

moveto

Evaluate the two expression children, and set x and y to these two values, respectively. Part 2. The Bug is supposed to draw a line as it moves (unless its color is set to none). Create a Command object that specifies the color and endpoints of the line, and save it in a list. Notify the Interpreter that this bug has performed an action.

turn

Evaluate the expression child, and add this amount to this Bug's angle. If necessary, adjust the value to be between 0.0 and 360.0, inclusive. (Maintain full accuracy--do not use int values!). Part 2. Notify the Interpreter that this bug has performed an action.

turnto

Evaluate the expression child, and set this Bug's angle to the new value. If necessary, adjust the value to be between 0.0 and 360.0, inclusive. (Maintain full accuracy--do not use int values!). Part 2. Notify the Interpreter that this bug has performed an action.

return someExpression

Part 2. Evaluate the expression and save it in an instance variable. Pop a HashMap from the stack of HashMaps, and exit from evaluating the function (similar to exiting from a loop).

line

Part 2. Create a Command object that specifies the color and endpoints of the line, and save it in a list. Notify the Interpreter that this bug has performed an action.

assign

Get the name from the first child, and throw a RuntimeException of some kind if that variable has not been declared (isn't in the HashMap). If all is well, evaluate the second child, and store the result of the evaluation into the variable name.

loop

Interpret the one child (a block) repeatedly. The loop ends when an exit if statement in the block is interpreted. You can do it by setting and clearing a boolean variable, to be checked by block.

exit

Stop executing the block of commands in the immediately enclosing loop.

switch

To interpret a switch, evaluate each case child, in order, until one returns "true"--then stop. (It seems strange to evaluate a case clause, rather than interpreting it, but this is an easy way to implement the switch statement.) Remember, "false" is any number between -0.001 and +0.001, and "true" is any number that isn't false.

color

Get the color name from the child, create a corresponding java.awt.Color value (there is no shortcut to doing this, you just need a big if statement), and store the result in this Bug's color instance variable. Throw some kind of RuntimeException if the name isn't a legal color.

call

Part 2. Find the function in this Bug's HashMap of functions. If it's not there, try the Allbug's HashMap of functions. When you find it,

Create a new HashMap<String,Double>, and put each formal parameter (under the var node into it. Push this HashMap onto this Bug's stack of HashMaps.

Evaluate each actual parameter, and store the result into the corresponding formal parameter (in the HashMap).

Interpret the body of the function.

When you reach a return statement, evaluate its expression, store the result in an instance variable, pop the HashMap off this Bug's stack of HashMaps, and return from interpreting the callnode.

If you reach the end of the function without interpreting a return statement, treat it as a return 0 statement.

Nodes to be evaluated:

+: If unary (has a single child), evaluate that child and return the value. If binary (has two children), evaluate both children, add them, and return the sum.
-: If unary (has a single child), evaluate that child and return the negative of its value. If binary (has two children), evaluate both children, subtract the second from the first, and return the difference.
*: Evaluate the two children and return their product.
/: Evaluate the two children and return the result of dividing the first by the second.
<, <=, = (not == !), !=, >, and >=: Evaluate the two children, compare them (again, you need a big if statement), and return 1.0 for "true", 0.0 for "false." Remember, two numbers are "equal" if they are within 0.001 of each other.
case: Evaluate the first child, and if "true" (not zero or nearly zero), interpret the second child. Return the result you got earlier when you evaluated the first child.
call: Part 2. As above, but use the returned value in the expression you are evaluating.

JUnit testing and Javadoc:

Required, as usual.

Write multiple test methods for evaluate and interpret, not one huge test method for each. For example, evaluateAddition and interpretAssignmentStatement (or testAddition and testAssignmentStatement, or whatever). Remember that JUnit 4 tests can be named whatever you like.

Since the interpret method returns void, you need to test it by its effect. That means that pretty much everything you interpret should set the values of some variables, so you can fetch those variables and see if they were set correctly.

Due date:

Zip the complete project and submit it via Blackboard by midnight Tuesday, April 15.