CIT 594 Assignment 8: The Big Picture
Spring 2009, David Matuszek

Introduction

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:

The text that represents the program has to acquired (typically, read in from a file).
The characters in the string have to be tokenized, that is, assembled into meaningful tokens.
The tokens have to be assembled into a meaningful data structure--a parse tree.
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 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 text area. Pressing Load again should replace the text in the text area 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 text area.

You can, of course, do a mixture of both--load in a program from a file and then edit it in the text area. The Save button should, of course, let you write the (possibly modified) text back to the same file, while the Save As... button should let you choose where to save it.

Tokenizing the program

Now that you have a program in the text area, 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 text area results in a changed parse tree. You don't want to be looking at one version of the Logo program and running another!

Caution: The grammar requires every command to end with a newline character. In a text area, you might not have one at the end of the last line, which would cause a mysterious syntax error. Since we shouldn't require the user to be careful about this, please just automatically add an <eol> at the end of any text you get from the text area.

Parsing the program

What you have in the text area is supposed to be a Logo program. Your Parser is supposed to be able to parse a <program>. Once you have gotten the program from the text area, you should try to parse it with your program() method. If this succeeds, your parser stack should have exactly one Tree in it, but that Tree represents the entire program.

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 things down. Many syntax errors can cause a RuntimeException 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 RuntimeException 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 you have more than one thing on the parser stack after parsing a program(), something has gone wrong. 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 should display a message to the user. The provided GUI has a status area at the bottom you can use, but you are also welcome to pop up a message dialog.

Completely optional suggestion: One very nice feature that you might add (this is completely optional!) 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 Tree 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 the Parser assignment. Now what?

You have a Tree. On one side of the Tree 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.

You can do this by setting up a hash table of procedures. Walk down the right side of your Tree 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 define node as the value. There is no reason to actually remove the procedures from the Tree--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.
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>).

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.

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.

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, penup, pendown, and home commands.

Sending commands to the turtle is somewhat sophisticated. You need 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), and whether the "pen" is "up" or "down". 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 TurtleCommand and sends it to the DrawingArea.
DrawingArea: Keeps track of all the TurtleCommands sent to it, in an ArrayList. Whenever the paint(Graphics) method is called, it executes all of these commands, in order.

TurtleCommands? What are they? We really want to give the DrawingArea 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 interface (call it "TurtleCommand") that declares an abstract method (call it "execute()"). Then you can implement your TurtleCommand class with any number of other classes, each of which has a different definition of the execute() method. For example, my DrawLineCommand has four instance variables (x1, y1, x2, y2) and an execute() method that, when called, draws a line from (x1, y1) to (x2, y2).

I've provided a DrawStringCommand implements TurtleCommand class for you to use as a model. (This class won't actually be used in the final interpreter, unless you add statements to the language.)

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 just 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, comments, or a way to draw text, or setting the background color, or...whatever you feel like. One exceptionally easy (and useful!) thing to do is to add a turtle "speed control" to the GUI.