594 Assignment 8: Interpreter, Part II
Spring 2006, David Matuszek
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.
Here are examples of the kinds of trees your Parser should have constructed:
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.
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
Vector, and you can use some
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
On the second call to
x = 1 call bar 3 define bar x x = x + 1 end
Make sure this works, but realize that it would be rather poor style!
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.
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
store, and test that procedures handle variables according
to this specification.
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).