Logo (including my miniature version of Logo) is a programming language. As with any programming language, a program in Logo is nothing more than text--it has to go through a number of steps before it becomes a running program.

Briefly, the steps are as follows:

1. The text that represents the program has to acquired (typically, read in from a file).
2. The characters in the string have to be tokenized, that is, assembled into meaningful tokens.
3. The tokens have to be assembled into a meaningful data structure--a parse tree.
4. The parse tree has to be "walked" and processed (interpreted or compiled).

As the interpreter walks the parse tree, it has to take various actions, depending on the kinds of nodes that it sees. Some of these (such as repeat) cause it to interpret parts of the parse tree over and over again. Some, such as forward, it must send to the "turtle."

We'll go over each of these steps in turn.

Acquiring the program

You have to get a Logo program from somewhere. There are two basic possibilities:

• Load it in from a file (using the Load button). When you do this, the text file is read in and displayed in a TextArea. Pressing Load again should replace the text in the TextArea with the newly read text (or leave it alone, if the Cancel button in the FileDialog is clicked.)
  
  
• Type the program text directly into the TextArea.

You can, of course, do a mixture of both--load in a program from a file and then edit it in the TextArea. The Save button should, of course, let you write the (possibly modified) text to a file.

Caution: When you type directly into the TextArea, you need to remember to hit Return after typing the last line. This is because the grammar requires every command to end with a newline ('\n') character. In a TextArea, hitting the Return key enters a newline (typing \n just puts those two characters into the TextArea!), and you might not have one at the end of the last line. Since this is a really stupid thing to have to ask the user to do, please fix the parser so that that last <eol> isn't required!

Tokenizing the program

Now that you have a program in the TextArea, you need to tokenize it and parse it. If it has changed in any way since the last time you ran the program, you will need to tokenize it and parse it all over again. You can either just do this every time you run the program, or (if this seems to take too long), you can keep a "dirty" flag and only do it if the program text has changed. (This is exactly what Eclipse does, by the way.)

You can get the program text (as a single String containing newlines) with the getText() method. Since you need to tokenize and parse this string, you probably have your Parser set up to create the necessary Tokenizer. However you do it, be sure that any change visible in the TextArea results in a changed parse tree. You don't want to be looking at one version of the Logo program and running another!

Hint: When you get the program from the TextArea, it wouldn't hurt (assuming your Parser can handle multiple <eol>s) to append a '\n' to it before you try to tokenize and parse it. This will solve the stupid input problem mentioned in the last section.

Parsing the program

What you have in the TextArea is supposed to be a Logo program. Your Parser is supposed to be able to parse a <program>. Once you have gotten the program with getText(), you should try to parse it with your program() method. If this succeeds, your parser stack should have exactly one BinaryTree in it, but that BinaryTree represents the entire program. If you have more than one thing on the parser stack after parsing a program(), something has gone wrong.

If the parse fails, you need to inform the user, as best you can, what caused the failure. After all, a Logo program is still a program, and it may--probably will--have syntax errors. The Logo programmer would like help tracking those syntax errors down. Many Logo syntax errors can cause a LogoParseException to be thrown, and for those you can print out the associated message. It might also be a good idea to modify your program() parsing procedure so that it throws a LogoParseException instead of failing--this should allow your interpreter to be a bit simpler.

Remember, a program is defined as one or more commands, followed by zero or more procedures. That is,

<program> ::= <command> { <command> } { <procedure> }

In Java terms, the one or more commands represent your "main method," and the procedures represent "other methods." If your program() parse succeeds but there is more than one thing left on the stack, then probably there is a Logo synax error immediately after the { <command> }, and you need to warn the user. (Of course, it could also be a bug in your program() method, in which case you need to fix it.)

When the parse fails, however it fails, you need to display a message to the user. The assignment says to put a message area in your GUI for this purpose, but if you have more than one line to display, you are welcome to pop up a second window instead.

Completely optional suggestion: One very nice feature that you might add is to have a lineNumber field in your Token class, so that when a syntax error occurs, you can tell the user what line number you were on.

Indexing the procedures

Okay, you've made it this far, and you have one BinaryTree on the Parser stack. Except for the GUI and a bit of file I/O, all of this should have been essentially done by the time you finished Assignment 4 (the Parser). Now what?

You have a BinaryTree. On one side of the BinaryTree is a list of <command>s, and these represent your "main method." On the other side you have a list of <procedure>s, and these represent methods that might be called from the main method, or from one another. When a procedure is called, you will need to find that procedure. So before you start trying to interpret the program, it would be wise to "index" those procedures.

Probably the best way to do this is to set up a hash table of procedures. Walk down the right side of your BinaryTree and, for each procedure you find, put it in the hash table, using the name of the procedure as the key, and a reference to the procedure's to node as the value. There is no reason to actually remove the procedures from the BinaryTree--the whole point is simply to find them easily.

Interpreting the program

Everything is now ready for you to interpret the program. That is, now is the time to walk through the parse tree and do what it says. Your interpreter will do this by starting at the root and evaluating (computing a boolean or integer value) or interpreting (causing an action to occur) each node that it finds.

For example (this is not a complete list):

• If the interpreter sees a node that looks like the root of an <expression> subtree (a number, a variable, or an arithmetic operator), it has to evaluate that subtree and find what number it represents. This is what your old ArithmeticExpression class did--in fact, you can probably use some of that code again.
  
  
• If the interpreter sees a node that looks like the root of a <condition> subtree (a less than, greater than, or equals symbol), it has to evaluate that nodes left and right subtrees, then evaluate the condition.
  
  
• If the interpreter sees an if node, it must first evaluate the left subtree (which must represent a <condition>). If (and only if) the result is true, it should interpret the right subtree (which should be a <block>).
  
  
• The commands representing the "main method," the procedure body, and any block, are represented by a list of commands. To interpret this list, the interpreter must walk down the subtree and evaluate each command in turn.

If you understand what each <command> is supposed to do, you should be able to figure out how to evaluate or interpret it. You already have some evaluation code, from your old ArithmeticExpression class.

Here are some of the commands that the interpreter needs to be able to cope with:

repeat 5 <block>

The interpreter has to interpret the <block> five times, which means doing the commands in that block five times.

while x < 5 <block>

The interpreter has to evaluate the <condition>, x < 5, and if it is true, interpret the <block>. Then the interpreter has to do the whole thing over again, and again, and again, until x is no longer less than 5. Hopefully, something in the <block> will change the value of x, but if not, that Stop button you have will come in handy.

set x x+1

The interpreter has to evaluate x+1, then it has to save the result as the new value of x. This is slightly tricky, because you don't want to evaluate the first x, you want to set it.

Coping with variables

Forget procedures for a minute. You don't know what variable names are going to be in the Logo program. To deal with these variables, you need a hash table. To get the value of a variable (usually because you are evaluating an expression), you look it up in the hash table. To set the value of a variable, you put it in the hash table. Simple. The only trick here is that you don't want to evaluate the left child of a set command--you want to just get it as a String, so you can use it as a key into the hash table.

Now, procedures make this picture a lot more complicated, because every procedure can have its own variables. So you need more than one hash table. Furthermore, procedures can be recursive, so actually each procedure invocation needs a new hash table. The best way to handle this is with a Stack of hash tables--when you need to look up a variable, look first in the topmost hash table, then the one next to the top, etc., until you find it. Details were given in Interpreter, Part II.

Turtle commands

Some commands are to be sent to the turtle. For example, if you interpret repeat 3 [forward 50 right 120] (I'm leaving out some necessary <eol>s here), the commands actually sent to the turtle are forward 50, right 120, forward 50, right 120, forward 50, right 120. In other words, the turtle only gets "turtle commands," and never sees things like repeat or set or if commands. It does need to see forward, right, left, color <colorname>, and home commands. Your turtle commands do not need to exactly correspond to the Logo commands; for example, I have a moveCommand (for moving with the pen up) and a drawLineCommand (for moving with the pen down), and I never tell the turtle penup or pendown.

The above is a little oversimplified. Sending commands to the turtle is somewhat sophisticated. I actually have two main classes:

Turtle

Keeps track of just a few things: the turtle's x and y co-ordinates, the direction it is facing (in degrees), whether the penIsDown, and how long to pause each time it gets a command (thus controlling the speed at which the turtle appears to move). Most commands that it gets, the turtle just creates a DrawingCommand and sends it to the DrawingCanvas.

DrawingCanvas

Keeps track of all the DrawingCommands sent to it, in a Vector. Whenever the paint(Graphics) method is called, it executes all of these commands, in order.

DrawingCommands? What are they?  We really want to give the DrawingCanvas a series of "commands," or methods, to execute. We want to give it a command to change the color, or to draw a line, etc. How do you pass a method as a parameter? In Java, you don't. But...there is a standard trick you can use. You can pass an Object that has a method in it. In fact, you can write an abstract class (call it "DrawingCommand") that declares an abstract method (call it "apply()"). Then you can extend your DrawingCommand class with any number of other classes, each of which has a different definition of the apply() method. For example, my DrawLineCommand has four instance variables (x1, y1, x2, y2) and an apply() method that, when called, draws a line from (x1, y1) to (x2, y2).

So, you tell the turtle to do something, and what it actually does is to construct a suitable DrawingCommand and send it to the DrawingCanvas. If the command is something that changes the turtle's state, then of course the turtle has to keep track of that information. But you need to be careful to distinguish between the turtle's state (its position, the direction it is facing, its speed, or whether its pen is down) and the state of the canvas (what is actually being drawn), and keep track of things in their proper class.

I've provided a couple of subclasses of DrawingCommand for you to use as a model.

By the way, you might notice that the turtle position x, y values are kept as doubles. This is a nuisance, but there is a good reason for it. Suppose you kept them as integers, then you repeatedly moved forward one step at an angle of, say, 30 degrees. You would actually be drawing a line at an angle of 45 degrees, because each new position would be rounded off to the nearest integer point. This repeated rounding would make it impossible to put fine details in a drawing, and the results would be impressively bad.

Summary

If all goes well, you should have a complete programming language for controlling the actions of a "turtle" on the screen. Syntax errors may give you a lot of trouble, but you will get immediate visual feedback on any logic errors--just watch the turtle!

Logo was designed to teach very young children to program, and it has been very successful. Our version differs from "real" Logo mostly by (1) being simpler, and (2) having relatively terrible error messages. But don't be misled into thinking that this is a "toy" language--it isn't. You can really do a lot with it.

After this assignment, this is your language. You are welcome to add features to it--for example, an <else clause> for the if command, or comments, or drawing text, or setting the background color, or....