Purposes:

• To give you more practice with stacks and hash tables
• To complete the Logo2006 set of assignments

General Idea:

In Part I of this assignment you were to implement the interpreter and display for Logo2006, not including procedures, procedure calls, and local variables. In Part II you are to finish implementing Logo2006.

All languages have scope rules that specify where a variable can be accessed. Since Logo2006 has neither objects nor variable declarations, the scope rules in Logo2006 must be different from those in Java. Java uses lexical scoping (scope is determined by position in the program text); Logo2006 will use dynamic scoping (scope is determined when the Interpreter encounters the variable). Basically, global variables are those encountered when the Interpreter is in the "main" program; local variables are those encountered when the interpreter is in a procedure (this includes the formal parameters of the procedure).

A cardinal rule of Extreme Programming is: Debug before adding features. The rest of your program should be tested and known to work before you attempt procedures. In other words, finish Part I of the Interpreter before attempting Part II.

Details:

Here are examples of the kinds of trees your Parser should have constructed:

Initializating the Interpreter:

There are two new steps that must be done when you initialize the Interpreter.

In order to implement the call statement easily, you need to be able to find the named procedure. To expedite this, your Interpreter should, as an initialization step, create a hash table that maps procedure names to the root nodes of the corresponding procedure Tree. It should do this only once per execution of the program.

private void stripProcedures(Tree<Token> proceduresNode)

Given the procedures node as input, puts each child (that is, each define node) into a global hash table procedures. The define node itself is used as a value, and the procedure name (the define node's first child) is used as a key.

 

You also need to create a Stack of hash tables. You already have (from Part I of this assignment) a hash table for "global" variables; put this as the first thing on your stack.

Dealing with variables:

Without procedures, we need only a single hash table in which to keep variables (names and values).

When we have procedures, we need a stack of hash tables, one hash table for the main program and one for each procedure invocation. (The Stack class extends Vector, and you can use some Vector operations if necessary.) Each hash table will contain variable names and their values. You will need to modify the following methods:

protected void store(String name, int value)

Using the name as a key look in the topmost hash table on the stack, then in the next one down, then the next one down, etc., until you either find name or you run out of hash tables. If you find name, replace its value with the new value; but if you don't find name, store it in the topmost hash table (thus making it a "local" variable, more or less) with a value of zero.

protected int fetch(String name)

Using the name as a key look in the topmost hash table on the stack, then in the next one down, then the next one down, etc., until you either find name or you run out of hash tables. If you find name, return its value, otherwise store name in the topmost hash table with a value of zero, and return zero as the result.

This approach has some odd consequences. Consider the following program:

x = 1
repeat 2 [
    call foo x
    y = 5
]
define foo a
    y = 2
    x = a + y
end

x = 1
call bar 3
define bar x
    x = x + 1
end

Execution of the call statement:

Procedures can have parameters, and can be recursive. This means that each time you call a procedure, you need to create a hash table to keep track of its parameter values. Since one procedure can call another (or itself), you need to keep all these hash tables on a stack.

The call statement has the form: call procedureName parameters.

To interpret a procedure call:

1. Using the procedureName as a key, look up the procedure's Tree (whose root is a define node) in the procedures hash table.
2. Create a new hash table for variables, and put it on the stack of variable hash tables.
3. Evaluate each actual parameter expression, and store the result as the value of the corresponding formal parameter variable. (If there are more or fewer actual parameters than formal parameters, report an error and terminate the program).
4. Interpret the block that is the body of the procedure.
5. Pop the hash table from the stack, thus discarding the variable values.

Testing:

Do JUnit testing as appropriate. That basically means testing everything except what goes up on the screen (JUnit can't "see" the screen, so manual testing is necessary.) In particular, update your tests for fetch and store, and test that procedures handle variables according to this specification.

Due dates and grading:

Please zip up your entire working Logo2006 interpreter, along with your JUnit tests, and submit via Blackboard before midnight, Thursday, March 30. The program will be worth 150 points total (100 points for Part I, and an additional 50 points for Part II).