Variables, part 1

An interpreter or compiler needs to keep track of variables. A compiler needs to keep track of the locations (machine addresses) of variables, while an interpreter needs to keep track of the values of variables.

The way this is done is with a symbol table, usually implemented as a hash table. Java supports several flavors of hash tables; the one I would like you to use is java.util.HashMap. Basically, the HashMap has two important methods:

• put(Object key, Object value) -- Puts the key and its associated value into the hash table.
  
  
• Object get(Object key) -- Given the key, returns the associated value.

You can find more details in the Java API.

Note that the parameters and return values are Objects. Therefore, Strings are fine to use as keys, but int values must have an Integer wrapper in order to be put into the hash table.

So here's all you need to do. Whenever you are evaluating a <factor> and you want to get the value of a variable, look it up in the hash 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 hash table.

Some additional points:

• The definition I gave you for factor was:
        <factor> ::= <name> | <number> | "(" <expression> ")"
  but it should have been:
        <factor> ::= <variable> | <number> | "(" <expression> ")"


• <variable> is the only place in the grammar (that I can think of) 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 hash table, that means you never put this variable into the table. This is an error in the Logo program.

Procedures

First of all, you should get the rest of your program running reasonably well before you attempt procedures.

The keyword to defines a procedure. The do 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 hash table of procedures. Step through the right-hand side of your <program> binary tree and, for each <procedure> (to node), put it in the hash table. 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 to node) will be the value. It doesn't matter whether you take the procedure out of the program tree or just leave it there.

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, you need to keep all these hash tables on a stack.

When you encounter a do command (procedure call):

1. Look up the procedure, by name, in your hash table of procedure names.
2. Evaluate each of the <expression>s in the do command.
3. Create a hash table and put it on the stack of hash tables.
4. For each parameter, get the value of the actual parameter (from step 2), and put these values in the new hash table as the value of the matching formal parameter (listed in the right-hand subtree of the header node of the procedure you found in step 1).
5. Evaluate the procedure body (the right subtree of the to node found in step 1).
6. When the procedure finishes, pop the hash table you created in step 3.

Variables, part 2

In the absence of procedures, we need only a single hash table in which to keep variables.

When we have procedures, we need a stack of hash tables, one hash table for each procedure invocation. (A Vector would also do, given some of the operations we need to perform. Your choice.)

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, this is an error.
  
  
• 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, so don't expect them to. (If you are curious, variables have what is called dynamic scope.) 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

The standard JUnit package is not designed for GUI testing. For this assignment, please include all previous JUnit tests (for Token, Tokenizer, BinaryTree, and Parser, but not Recognizer), updated as appropriate.

Also include one Logo program (call it sample.logo) that we can run. This program should showcase all the features of the language, and should draw something interesting. We will also want to run our own Logo test programs, so make sure that we can use the Load button to replace the current Logo program--we don't want to have to stop and restart your interpreter!

Due date:

Tuesday, March 2, before midnight.