CIT 594 Assignment 6: The Big Picture
Spring 2010, 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:

  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 in turn.

Acquiring the program

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

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 from the text area (as a single String containing newlines) with the getText() method. Since you need to tokenize and parse this string, you will have your Parserdo this. 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 a "\n" at the end of any text you get from the text

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 isProgram() 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 isProgram() 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 isProgram() 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 to node as the value. There is no reason to remove the procedures from the Tree--the whole point is simply to find them .

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 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 a a+1
The interpreter has to evaluate a+1, then it has to save the result as the new value of a. This is slightly tricky, because you don't want to evaluate the left-hand a, 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, but all the drawing commands require integers. 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 impressivelybad.

Command semantics

The commands are all about controlling what the turtle does. The turtle moves on the screen (in a JPanel). The coordinate system is as in algebra, not as in Java's Graphics, so you have a (very small) bit of arithmetic to do. The origin (x=0, y=0) is at the center of the JPanel, not the top left corner. x values increase to the left, y values increase going up, not down. Zero degrees is facing right, 90 degrees is up, and so on counterclockwise.

penup
"Lift the pen up off the paper." Subsequent moves will not draw anything.
pendown
"Put the pen down on the paper." Subsequent moves will draw a line, in the current color.
color
Set the color used for subsequent drawings.
  • red = 0xFF0000
  • orange = 0xFF9900
  • yellow = 0xFFFF00
  • green = 0x00FF00
  • blue = 0x0000FF
  • purple = violet = 0x9900FF
  • brown = 0x996600
  • black = 0x000000
  • white = 0xFFFFFF
  • gray = 0xCCCCCC
  • pink = 0xFFCCCC
  • rgb r g b = new Color(r, g, b)
home
Without drawing anything, move the turtle to the center of the screen (x = 0, y = 0), facing right (0 degrees).
jump x y
Without drawing anything, move the turtle to the given x, y location. Does not change the direction that the turtle is facing.
set variable expression
Evaluates the expression, and sets the variable (which may be local or global) to that value.
repeat expression block
Evaluates the expression, then executes the block that many times. Since the expression will result in a double value, it should be rounded to an int, not truncated.
while condition block
Behaves like a while loop in Python or Java.
if condition block [ else block ]
Behaves like an if statement in Python or Java.
do procedure_name expression ... expression
Evaluates the expressions, then calls the named procedure with those values as parameters.
forward pixels
Move the turtle forward (in whatever direction it is facing) the given number of pixels.
face direction_in_degrees
Make the turtle "face" in the given direction (0=right, 90=up, 180=left, 270=down). Numbers outside the range 0 to 360 should be adjusted to fall within this range.
left degrees
Change the direction the turtle is facing to its old direction plus this number of degrees, adjusting the sum if necessary to be within 0 to 360.
right degrees
Change the direction the turtle is facing to its old direction minus this number of degrees, adjusting the result if necessary to be within 0 to 360.
to procedure_name variables
Like def in Python. Defines a procedure, with the given variables as formal parameters. (A procedure is like a function, except that it doesn't return a value.)

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 "toy" language--it isn't. It is Turing complete, which means that it can do any and all computations that could be done in Java or Python (though maybe not easily!).

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.