CIT 594 Assignment 6: Interpreter
Spring 2010, David Matuszek

Purposes:

General Idea:

You finally get to see the point of everything we've been doing. In this assignment you will implement an interpreter for a mini-language based loosely on Logo. At last, all your hard work will pay off!

Logo is a general-purpose programming language, originally designed for children. The idea is that you write a program to instruct a "turtle" how to walk around the screen; the turtle has colored pens which it drags as it walks, so you can see where it has been. The object is to teach the turtle how to draw various objects: squares, spirals, stars, houses, faces, etc. All important features of a programming language are included.

Details:

You will need a GUI for this assignment. I have provided some starter code; you are free to use it exactly as is, add to it, change it, modify it in any way you like, or just ignore it altogether and write your own. But please, don't lose any functionality!

The GUI should have:

The text area should be completely editable. (Java's java.awt.TextArea is just fine for this.)

The control panel should have:

Buttons and menu items should be disabled when they are not applicable. For example, the Start button should be grayed out when there is no program, or when the program has a syntax error, or when the turtle is already running.

You are welcome to have other controls and display areas as well, so long as they work and their function is clear. I've done some of this, but you can do more.

Writing the interpreter:

Clicking the Start button should cause the drawing area to be cleared and the program interpreted. Then tokenize, parse, and interpret the program.

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

For example, if the complete program consists of:
penup
home

to foo a b c {
  left a
}
Then the Tree should look like:
program

To interpret the program, you simply interpret the top node. Usually this means interpreting its children, recursively. Almost every type of node will have a little procedure associated with it, to interpret the node (do the thing that that node says to do).

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

Grammar rule (partial) Example input The Tree How to interpret this
<variable> ::= <name> "foo" Depends on context. In an <expression>, look up the value of the variable. As the first child of a <set> statement, assign a value to the variable. See below.
<factor> ::= "x" | "y" "x" x You can think of x and y as "read only" variables. x and y evaluate to the Turtles's current (x, y) location.
<command> ::=
<move> <expression> <eol>
"forward 5 \n" Evaluate the child <expression>, and tell the turtle to move forward that distance. If the pen is down, the turtle draws; otherwise, it moves without drawing.
<command> ::=
"penup" <eol>
"penup \n" Tells the turtle to lift its pen, that is, don't draw.
<command> ::=
"pendown" <eol>
"pendown \n" Tells the turtle to lower its pen. Future moves will draw lines.
<command> ::=
"color" <colorname> <eol>
"color red \n" Tells the turtle to use the color red in any future drawing.
<command> ::=
"color" "rgb"<expression> <expression> <expression> <eol>
"color rgb a 127 b \n" rgb Tells the Turtle to use the color new Color(rgb) in any future drawing.
<command> ::=
   "home" <eol>
"home \n" Tells the turtle to go to the center of the screen and face right.
<command> ::=
 "set" <variable> <expression> <eol>
"set a 5 \n" Evaluate the second child <expression> and save the numerical result in the first child <variable>. See below.
<command> ::=
 "repeat" <expression> <block> <eol>
"repeat 5 { \n
penup \n
} \n"
Evaluate the first child <expression>. Then interpret the second child <block> that many times.
<command> ::=
 "while" <condition> <block> <eol>
"while x < 5 { \n
penup \n
} \n"
Evaluate the first child <condition>. If true, interpret the <block> and start the while over again, otherwise do nothing.
<command> ::=
 "if" <condition> <block> <eol>
"if x < 5 { \n
penup \n
} \n"
Evaluate the first child <condition>. If true, interpret the <block>, otherwise do nothing.
(Note: x is being read, not set, so it is legal to use in this way.)
<command> ::=
"do" <name> { <expression> } <eol>
"do foo 1, 2, 3\n" do Evaluate each <expression> in the second child <list>, then interpret the procedure <name> with these values as parameters.
<block> ::= "{" <eol> { <command> } "}" <eol> "{ \n penup \n home \n
pendown \n

} \n

Interpret, in order, each child of the block.

<expression> ::= [ <add_operator> ] <term> { <add_operator> <term> } "foo + 5"

Evaluate both children and add the results.

"-foo + 5" negative An initial unary + can be discarded. For an initial unary -, evaluate the child and negate the result.
<term> ::= <factor> { <multiply_operator> <factor> } "foo * 5" Evaluate both children and multiply the results.
<condition> ::= <expression> <comparator> <expression> "x < 5" Evaluate both children and compare the results, getting a boolean value.
<procedure> ::= "to" <name> { <variable> } <eol>
{ <command> } "end" <eol>
"to foo a b c \n
left a \n
end \n"
procedure

Assign values to the formal parameters, then interpret the block.

<program> ::= <command> { <command> } { <procedure> } "penup \n
home \n
to foo a b c { \n
left a \n
} \n"
program

Save the definition of each of the <procedure> children of list for later interpretation (see below), then interpret the right <command> children in order.

Program architecture:

The Logo class (which contains the main method) creates and calls an Interpreter, which then walks the parse tree and interprets the commands as necessary. Many of these will be control commands, such as if, while, and set. These commands are handled directly by the Interpreter class.

Some commands, such as forward, will cause the turtle to do something. For each such command, the Interpreter will call a method in the Turtle class (such as public void forward(int n)). The turtle will then change its state as necessary.

Some commands that the turtle receives, such as forward and color, will also affect what is drawn on the screen (the DrawingArea). In these cases, the method in the Turtle class will create a TurtleCommand to send to the DrawingArea. The DrawingArea keeps a Vector of all the TurtleCommands it has received, and executes them whenever the screen has to be repainted. (This is necessary because all actual drawing has to be done from the paint() method).

TurtleCommand is an interface with one method, execute(), that implementing classes must define. There should be several implementations of TurtleCommand; I've provided a DrawStringCommand, which is a throwaway example to use as a model for your own commands.

Here is the starter code.

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 map. Use a HashMap<String, Double> for this purpose.

So here's all you need to do. To evaluate x or y, ask the Turtle for its location. Whenever you are evaluating a <factor> and you want to get the value of a variable, look it up in the hash map. 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 map.

Some additional points:

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.

Do this by setting up a separate hash map of procedures. Step through the right-hand side of your <program> tree and, for each <procedure> (to 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 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 map to keep track of its parameter values. Since one procedure can call another, you need to keep all these hash maps on a stack.

In our little language, procedures are defined by to and called by do. When you encounter a do command:

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

Variables, part 2

In the absence of procedures, we need only a single hash map in which to keep variables. But once we introduce procedures, we need a notion of "scope." Because we don't have an explicit mechanism to declare variables, as in Java, we will need somewhat different scope rules. In our language, we will have exactly two scopes: local (to the current procedure) and global (in the "main" program).

Because procedures can call other procedures, we need a stack of hash maps, one hash map for each procedure invocation. The scope of a variable depends on what hash map it is in. Only two hash maps will be active at any given time: the global hash map, and the hash map at the top of the stack, for the current procedure invocation. Other hash maps on the stack can be ignored.

Each time we enter a procedure, we create a new hash map for it. We evaluate the actual parameters (the ones in the do statement), and put their values into the new, local hash map, as the values of the corresponding formal parameters (the ones in the to declaration). This is the same as the way things are done in Python, Java, and almost every other language.

Other variables--other than the parameters, that is--should be treated as follows:

Put another way: If you are in the main program, use only global variables. If you are in a procedure, look for a local variable before you look for a global variable, but if you don't find it either place, create it locally.

Variables managed in this way don't follow either the Python scope rules or the Java scope rules. In our language, as in Python, variables are "declared" by assigning a value to them. Whether a variable is local to a procedure or global depends on whether it has been given a value in the main program. You might call a procedure, then set a variable in the main program, then call the procedure again. The first procedure call will use a local variable, and the second one will use the global variable.

Testing

The standard JUnit package is not designed for GUI testing. For this assignment, please include the JUnit tests for Token, Tokenizer, Tree, and Parser (but not Recognizer). You can correct and augment these tests if you like.

Also include one Logo program (call it sample.logo) that we can run. This program should showcase all the features of the language, should be at least 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:

Interpreter for everything except procedures: Thursday, March 25, before midnight. This part will be worth 100 points.

Complete Interpreter, including procedures: Thursday, April 1, before midnight. This part will be worth an additional 50 points.