Purposes:

• To teach the use of stacks and stack frames
• To further illustrate how interpreters and compilers work

General Idea:

You have now written a Parser for a fairly simple programming language (RoboTalk), and an Interpreter for most of the language. This assignment concludes the implementation of the language.

Programs in RoboTalk consist of a main program, which is just a list of commands, followed by some number of methods, each of which begins with the keyword define and ends with the keyword end.

For your main program you used a Map (probably a HashMap) to keep track of the values of variables. The rules were these:

• (Store) If a variable occurred on the left-hand side of an assignment statement, you computed the value of the expression on the right-hand side, and map.put(variable, value) into your map. You did not evaluate the variable on the left-hand side of the assignment statement.
• (Fetch) If a variable occurred anywhere else, you got its value as follows:
  • If the variable was already in your Map, you used value = map.get(variable) to get its value.
  • If the variable was not in your Map, you put it in with a value of zero, and used zero as its value.

In this assignment you will implement methods, and you will need to be concerned about the scope of variables. Unlike Java, which has static scope (you can tell what method owns a variable by just looking at where it is declared), RoboTalk will have dynamic scope (variables belong to the method in which they are first used).

Details:

Finding methods

Before you begin to interpret your program, do the following.

Create a new Map to keep track of your methods. This Map is different from all the rest of the Maps in your program; its keys will be the names of methods, and its values will be (references to) the actual Tree (under program -> procedures) in the complete parse tree. Step through the parse tree and populate (put keys and values in) this Map.

Later on, when you need to call a method, just look it up in this Map, handle parameter transmission (see below), and interpret the body of the method.

Handling variables

Your basic data structure for dealing with variables will be a stack of maps; specifically, a Stack<Map<String,Integer>>. Name this stack variables, and do not make it private. The Map that you used for variables in your main program will be the first (bottommost) thing on this stack. (Note: Stack extends Vector, and you will almost certainly need to use one or more Vector operations; but most of the time, think of this as just a Stack.)

Each time you call a method, you create a new Map and put it on the stack. This Map is used to hold the variables (and their values) that are "owned" by this method. If the method recurs (calls itself), create a new Map for each level of the recursion.

When you call a method, do the following:

1. Create a new Map for the method, and put it on the stack.
2. Evaluate the arguments (actual parameters) to the method.
3. Get the corresponding formal parameters of the method (from the define).
4. Put the formal parameters and their values (the argument value) into the Map.

When you need to fetch the value of a variable, do the following:

1. Look in the topmost Map (on the Stack) for the variable. If you find it there, use its value.
2. Look in the next Map down (on the Stack). If you find it, use its value.
3. Keep searching downward in the Stack until you either find the variable in one of the Maps, or you run out of Maps.
   1. If you find it, use its value.
   2. If you don't find it, put it in the topmost Map with a value of zero, and use zero as its value.

When you need to store the value of a variable, do the following:

1. As with fetch, look for the variable in the topmost Map, then the next, then the next, etc., until you find the variable or you run out of Maps.
   1. If you find the variable in some Map, put its new value there.
   2. If you don't find the variable, put its value in the topmost Map.

When you return from a method, pop its Map from the stack. (But before you do this, evaluate the expression that is to be returned and put it in a safe place--if the method was called from within an expression, you will need this value in the calling expression.)

Consequences

Here are at least some of the consequences of this particular way of doing dynamic scope:

Program skeleton	Explanation
define A use var call B end define B use var end	Method B uses the variable var that was first used in A
define A call B use var end define B use var end	Method B uses its own var, then returns. Since B's Map is discarded when it returns, method A uses a new, different var.
use var1 call A use var2 define A use var1 use var2 end	The main program uses var1, but doesn't use var2, before it calls method A. Hence, method A uses the same var1 as the main program, but uses its own var2.
if 2 = 2 { use var1 } else { use var2 } call A define A use var1 use var2 end	Just as in the previous example, the main program uses var1 but doesn't use var2 before it calls method A. Hence, method A uses the same var1 as the main program, but uses its own var2.
define A use var call B 5 end define B var use var end	Since var is a formal parameter of method B, it hides the variable of the same name in method A. There are two distinct variables named var.

Testing

Test your interpreter with some RoboTalk programs (written as Strings in your test class). Make sure that you can pass values in to methods and get the correct value back. Also devise a couple of simple test programs to ensure that you have implemented the dynamic scope rules correctly (to simplify testing, your variables stack should not be private).

Due date:

Zip the complete Eclipse project and submit via Blackboard before midnight Thursday, April 12 Sunday, April 15.