CIT 594 08 Bugs Interpeter, part 1
Spring 2015, 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. Each "bug" will be an instance of this class.

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.

Each of these methods will use either a switch statement or a multi-branch if statement to examine the String value in the root of the given tree, and call the appropriate method to evaluate or interpret the tree.

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 should 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. Write the lowest-level, most fundamental methods first (like fetch and store), so that you can test them, then work your way up to the higher-level methods.

Nodes to be interpreted:

program: Not in this assignment.
Allbugs: Not in this assignment.
Bug: As described above.
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 child, in order (first to last).
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.
moveto: Evaluate the two expression children, and set x and y to these two values, respectively.
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!).
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!).
return: Not in this assignment.
line: Not in this assignment.
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. (This may be a bit tricky; you can probably do it by setting and clearing a boolean variable, but remember, you can have loops inside loops (inside loops....)).
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.
function: 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.

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: Not in this assignment.

JUnit testing and Javadoc

Write multiple test methods for evaluate and interpret, not one huge test method for each. For example, testAddition and testAssignmentStatement. 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.

Write complete Javadoc comments, generate the Javadoc, and save it in your project folder.

Due date

Turn your entire project in to Canvas before 6 a.m. Tuesday, March 24.