CIT 594 Assignment 9: Logo Interpreter
Spring 2014, David Matuszek
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.
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 is described in a separate document, GUI for Logo Interpreter.
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.
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:
|Then the Tree should look like:
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|
||Depends on context. In an
||You can think of
||Evaluate the child
||Tells the turtle to lift its pen, that is, don't draw.|
||Tells the turtle to lower its pen. Future moves will draw lines.|
||Tells the turtle to use the color red in any future drawing. (If your parser turned each color name into a color(r,g,b) command, that's okay, too.)|
||Tells the Turtle to use the color
||Tells the turtle to go to the center of the screen and face right.|
||Evaluate the second child
||Evaluate the first child
||Evaluate the first child
||Evaluate the first child
Interpret, in order, each child of the block.
Evaluate both children and add the results.
||An initial unary
||Evaluate both children and multiply the results.|
||Evaluate both children and compare the results, getting a
Assign values to the formal parameters, then interpret the block.
Save the definition of each of the
Logo class (which contains the
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
set. These commands are handled directly by the
Some commands, such as
color, will cause the turtle to do
something, either draw something on the screen (
forward) or change its state (
color). For each such command, the
Interpreter will call a
method in the
Turtle class (such as
forward(int n)). In these cases, the method in the
Turtle class will create a
TurtleCommand to send to
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
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.
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
So here's what you need to do. To evaluate
getY, 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
command and you have a value you want to save in a
<variable>, put the variable/value pair into the hash
Some additional points:
setcommand you have to get the name of the first
<variable>, not it's value.
nullvalue back from the hash map, that means you never put this variable into the table. If you are trying to fetch the value of a variable, and you get
null, this is an error in the Logo program. Throw an exception and display an appropriate message to the user. Stop the Logo program, but not the Interpreter. The user should be able to edit the program and try again.
First of all, you should get the rest of your program running reasonably well before you attempt procedures.
def 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
<procedure> is represented as a subtree of the
parse tree produced by your Parser. You need to find the subtrees 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,
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
will be the value. Don't remove the procedure from
the program tree; it's no longer needed there, but it costs nothing to leave it alone..
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 version of Logo, procedures are defined by
def and called by
do. When you encounter a
<expression>s in the
headernode of the procedure you found in step 1).
defnode found in step 1).
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 slightly 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
def 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. (OK, that's weird, but logical.)
The standard JUnit package is not designed for GUI testing. For this
assignment, please include the JUnit tests for
Parser (but not
Recognizer). You can correct and augment these tests if you
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
Interpreter for everything except procedures: 6am Tuesday, April 8. This part will be worth 100 points.
Complete Interpreter, including procedures: 6am Thursday, April 17. This part will be worth an additional 50 points.