CIT 594 Assignment 9: Interpreter
Spring 2012, David Matuszek

Purposes

To give you more practice using stacks, trees, and hash tables.
To complete the study of recursive descent.
To have a nice program to add to your portfolio.

General Idea

I have defined a small "language for robots."

You already have a Parser for the language. When applied to a syntactically correct program, the Parser will produce an AST (Abstract Syntax Tree).

You have written a RobotPiece class, to paint the robot, and a RobotController class, to tell the RobotPiece what to do.

You have written a small GUI, in which you make an instance of a RobotController; then the RobotController makes an instance of a RobotPiece and places it in the GUI. The user can then manipulate the GUI controls to send commands to the RobotController.

The last step is to write an Interpreter for the robot language, so that the RobotController receives its commands, not from a user, but from a program. The job of the Interpreter is to step through the AST provided by the Parser, and give commands to the RobotController. This requires a different GUI, which I am providing as RobotGui.java.

How to write an interpreter

When the Parser finishes, it should have exactly one (possibly very large) Tree on its stack. That Tree should represent the entire program.

For example, if the complete
program consists of:

program {
  forward
  turn left
  back 1
}

Then the Tree
should look like:

To interpret a program, you interpret its first child, a block. To interpret a block, you interpret each of its children, in order. Each type of node is interpreted differently, as described in the table below. Some types of nodes are evaluated (produce a value) rather than interpreted.

Three of the most important methods in your interpreter will be:

int evaluateExpression(Tree expression): Given the root of a Tree representing an arithmetic expression, evaluate the expression and return the numerical result.
boolean evaluateCondition(Tree condition): Given the root of a Tree representing a condition, evaluate the condition and return the boolean result.
void interpret(Tree command): Given the root of a Tree representing a program or a command, interpret the program or command (that is, do what it says to do)

Your interpret method will most likely consist of a fairly large if...else if...else if statement, containing clauses something like the following:

...
else if ("while".equals(command)) {
    while (evaluateCondition(child[0])) {
        interpret(child[1]);
     }
}
else if ...

Since the Interpreter will be controlling a robot, and displaying it on a Board, it should begin by creating a RobotController, and making sure the Board is populated with objects, including a RobotPiece. It should also be able to take some commands from the GUI: To start interpreting a program, to pause and resume interpreting a program, and to stop interpreting a program. In more detail, my GUI expects the following:

Execution starts with the GUI, as usual. The GUI will create an Interpreter, giving it both a program (in the robot language) to be run, and a Board on which to display the robot's actions.

public class Interpreter extends Thread -- because it has to run concurrently with the GUI.
- Interpreter(Tree<Token> program, Board board) -- constructor, to create a RobotController, and tell it what program to interpret and where to display its actions.
- public void run() -- to interpret the program. This method isn't called directly; the GUI calls the Thread's start() method.
- public void setPaused(boolean paused) -- true should pause the interpreter, false should resume interpretation.
- public boolean isPaused() -- to check whether the interpreter is paused.
- public void stopProgram() -- to terminate interpretation of the current robot program.

As the Interpreter runs, there is a distinction between two types of commands: <action>s, which cause something visible to happen on the board, and <thought>s, which do not. Basically, interpreting an <action> results in the Interpreter telling the RobotController to do something, while <thought>s are just computations done in the Interpreter. The Interpreter should therefore compute <thought>s with no artificial delays; but every <action> should be preceded or followed by a 100ms. delay, otherwise things will happen too fast for the human observer to follow.

In the following table, I have tried to use the following terminology consistently:

interpret: Do what the statement says to do.
evaluate: Compute an integer or boolean result.

Grammar rule (partial)	Example input	How to interpret this
`<variable> ::= <name>`	`foo`	Depends on context. In an `<expression>`, look up the value of the variable. As the `<variable>` in a `<set>` statement, assign a value to the variable.
`<thing> ::= <name>`	`foo`	This is just a "thing"--it doesn't do anything. It is used in statements or expressions that need to know the name of the thing.
`<action> ::= <move> <expression> ";"`	`forward 5;`	Evaluate the `<expression>` to get a number, then tell the robot to move forward that number of squares. If something blocks the robot from moving that far, it moves as far as it can.
`<action> ::= "turn" <direction> ";"`	`turn right;`	Tell the robot to turn 90? to the right.
`<action> ::= "take" <object> ";" \| "drop" <object> ";"`	`take rock;`	Tell the robot to pick up or put down an object of the named type in the same square as the robot.
`<thought> ::= "set" <variable> <expression> ";"`	`set x 5;`	Evaluate the right child `<expression>` and save the numerical result in the left child `<variable>`. See below.
`<thought> ::= "repeat" <expression> <block>`	`repeat 5 { turn left; stop; }`	Evaluate the first child, `<expression>`. Then interpret the second child, `<block>`, that many times.
`<thought> ::= "while" <condition> <block>`	`while x<5 { turn left; }`	Evaluate the left child `<condition>`. If `true`, interpret the `<block>` and start the while over again, otherwise do nothing.
`<thought> ::= "if" <condition> <block> [ "else" <block> ]`	`if x < 5 { stop ; }`	Evaluate the first child, `<condition>`. If `true`, interpret the `<block>`, otherwise do nothing.
`<thought> ::= "if" <condition> <block>`	`if x < 5 { } else { stop; }`	Evaluate the left child `<condition>`. If `true`, interpret the first `<block>`, else interpret the second `<block>.`
`<thought> ::= "call" <name> { <expression> } ";"`	`call foo 2 3 6;`	Evaluate each `<expression>` child, not including the `<name>`, then interpret the procedure `<name>` with the expression values as parameters. Seebelow.
`<action> ::= "stop" ";"`	`stop;`	Stop interpreting; the program is finished.
`<block> ::= "{" ";" { <command> } "}" ";"`	`{ turn left; forward 5; turn right; }`	To interpret a `<block>`, interpret each statement in the block, one after the other, beginning with the first.
`<expression> ::= <term> { <add_operator> <term> }`	`foo + 5`	Evaluate both children and add the results.
`<expression> ::= <term> { <add_operator> <term> }`	`2 + 3 + 6`	Evaluate both children and add the results. (Recursion will take care of the subtree.)
`<expression> ::= [ <addOperator> ] <term>`	`-5`	Evaluate the child, then negate the result.
`<term> ::= <factor> { <multiply_operator> <factor> }`	`foo * 5`	When a `<term>` consists of a single factor, the tree is the same as it is for that `<factor>` alone
`<factor> ::= <name>`	`foo`	When a `<factor>` consists of a name or number, evaluate that `<name>` or `<number>`.
`<factor> ::= "(" <expression> ")"`	`(foo + 5)`	Evaluate both children and add the results.
`<condition> ::= "seeing" <thing>`	`seeing rock`	Find the first nonempty square in the direction the robot is facing (not including the square that the robot is on), and return `true` if that square contains an object of the given type. For `not`, the child is a `<condition>` of some sort.
`<factor> ::= "distance"`	`distance`	Find the first nonempty square in the direction the robot is facing (not including the square that the robot is on), and return the distance (number of squares) to that object.
`<condition> ::= <expression> <comparator> <expression>`	`x < 5`	Evaluate both children and compare the results, getting a `boolean` value.
`<procedure> ::= "def" <name> { <variable> } <block>`	`def foo x y { forward x; turn left; back y; }`	Assign values to the left `<variable>` children, then interpret the right `<command>` children.
`<program> ::= "program" <block> { <procedure> }`	`program { forward 5; turn left; back 1; }`	The `<procedure>`s, if any, are additional children of `<program>`, following the `<block>`. Before you begin interpreting the program, save the `<procedure>` children (none in this example) as described below. To interpret the program, just interpret the `<block>`.

Error handling

Your program should never crash, or produce an unhandled exception.

If the parser detects an error, it should pop up a dialog box, giving the user as much information as possible about the error. The user should not be allowed to try to interpret a program with a syntax error.

The robot language interpreter always makes a "best effort" to do what the program says, and never reports an error if it cannot. For example, if the robot is told to move 5 spaces, and can only move 3 spaces, then it moves 3 spaces. It the robot is told to drop something that it isn't holding, it simply doesn't do anything.

Program architecture

The Interpreter walks the parse tree and interprets the commands as necessary. Many of these will be <thought>s, such as if, while, and set. These commands are handled directly by the Interpreter class and are not sent to the RobotController. Expression evaluation is also done by the Interpreter class, not the robot, although some expressions may involve getting values (for example, distance) from the robot.

Some commands, the <action>s , will cause the robot to do something. For each such command, the Interpreter will call a method in the Robot class (such as public void forward(int n)). The robot will then perform some appropriate action.

Variables, part 1

An interpreter needs to keep track of the values of variables. The way this is done is with a symbol table, which you should implement with a java.util.HashMap<String, Integer>. Basically, the HashMap has two important methods:

put(String key, Integer value): Puts the key and its associated value into the hash table. In this case, the key will be the name of the variable.
Integer get(String key): Given the key, returns the associated value.

Whenever you are evaluating a factor and you need to get the value of a variable, look it up in the symbol table. Whenever you are evaluating a set command and you have a value you want to save in a variable, put the variable/value pair into the symbol table.

Some additional points:

<variable> is the only place in the grammar where you have to evaluate something in two different ways (getting the value, and setting the value).
If you get a null value back from the symbol table, that means you never put this variable into the table. Treat it as a zero.

Procedures

First of all, you should get the rest of your program running reasonably well before you attempt procedures. The program without procedures will be worth 100 points. Procedures will add another 50 points.

The keyword def defines a procedure. The call command calls a procedure. Procedures consist of a list of commands, just like the rest of the program, but you have to do extra work to sort out the procedures from the rest of the program, and keep track of parameters.

A <procedure> is represented as a subtree of the parse tree produced by your Parser. You need to find the subrees representing these procedures and keep track of them separately, by name.

The best approach is to set up a separate HashMap<String, Tree<Token>> of procedures. Step through the right-hand side of your <program> tree and, for each <procedure> (def node), put it in the hash map. The <name> of the procedure will be the key (we won't allow more than one procedure with the same name), and the whole procedure (rooted at the def node) will be the value.

Procedures can have parameters, and can be recursive. This means that each time you call a procedure, you must create a new HashMap to keep track of its parameter values. Since procedures can call procedures, you need to keep all these HashMaps on a Stack.

When you encounter a call command (that is, a procedure call):

Prepare for the procedure call:
1. Look up the procedure, by name, in your hash table of procedure names.
2. Create a new HashMap and put it on the Stack of HashMaps.
3. There should be exactly as many <variable>s in the def statement as there are <expression>s in the call statement. For each <variable> in the def, evaluate the corresponding <expression>s in the call command. Put these in the new HashMap, using the variable as the key and the evaluated expression as the value.
  
  If there are not exactly as many <variable>s as <expression>s, make a "best effort". I suggest that excess variables be set to zero, and excess expressions be ignored; but the truth is, I don't really care what you do. Just don't crash.
Call the procedure:
1. Evaluate the procedure body (the right subtree of the def node), using the Stack of HashMaps.
Clean up afterwards:
1. When the procedure finishes, pop the new HashMap from the Stack.

Variables, part 2

In the absence of procedures, we need only a single HashMap in which to keep variables. When we have procedures, we need a Stack of HashMaps, one for each procedure invocation.

To find a variable, look for it first in the topmost hash table on the stack, then in the next one down, then the next one down, etc., until you either find it or you run out of hash tables.

If you find the variable, either set or get its value, as appropriate.
If you don't find the variable, and you are trying to get its value, use zero.
If you don't find the variable, and you are trying to set its value, add the variable and its value to the topmost hash table.

Variables managed in this way won't follow the same scope rules as variables in Java; it's more like scopes in Python. You should think about the effects of this approach--do we have global variables? Local variables? From where in the program can we access which variables?

Testing

For this assignment, please include all previous JUnit tests (for Token, Tokenizer, Tree, and Parser, and optionally Recognizer), updated as appropriate.

I recommend that you test those parts of the Interpreter that can readily be tested. Many parts aren't amenable to unit testing, but you can still test your interpreter the old-fashioned way: Interpret one or more programs on files, and see if the robot does what you wanted it to do.

Due date:

Your program is due before 6am Tuesday, April 10. Zip up the entire directory for this project, and submit via Blackboard. Only assignments submitted via Blackboard will be accepted--any assignments emailed to me will be discarded without comment. A late penalty of 5 points per day (out of 150 points) will apply.

Because many of you are interviewing this semester, a limited number of 48-hour extensions will be available. To get an extension, email me before 5pm Friday, stating the reason you need the extension. No extensions will be granted after Friday. If you get an extension and fail to get the project in by the extended due date, late points will be counted from the original due date.