Purposes:

• To give you more practice using assorted data structures
• To complete the study of recursive descent

General Idea:

In this assignment we will implement an interpreter for the mini-language Logo2006, which is based loosely on an ancient (1966) programming language 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" (program) the turtle to draw various objects: squares, spirals, stars, houses, faces, etc. All the most important features of a programming language are included.

Wikipedia has a good article on Logo.

In this assignment we will not implement procedures or the call statement; that's for Part II.

Classes and interfaces:

The story so far:

Your Tokenizer takes a String input and produces Tokens, each of which has a Type and a String value. The Tokens were used in your Recognizer, which used recursive descent to recognize Strings according to a particular grammar. This Recognizer is itself no longer needed, but it formed the basis of a Parser class which recognizes Strings and converts them into Trees. Now, what shall we do with those Trees...?

New classes:

To finish implementing Logo2006, we need to interpret a Tree (called a parse tree or an abstract syntax tree) that represents a Logo2006 program. This means moving a cursor (traditionally called a turtle) around on a canvas, according to commands issued by an interpreter. All of this will take place within the context of a GUI.

public class Logo

The only purpose of this class is to give us a well-named starting point. Here is the class in its entirety (well, you should add some Javadoc to it):

public class Logo { public static void main(String[] args) { LogoGui.main(null); } }


class LogoGui

Provides facilities for creating, loading, editing, and saving files, controlling the Interpreter, and controlling the speed of the turtle. I have supplied this as a skeleton class that does all the routine stuff; you need to modify it to interact with the Interpreter.


class Interpreter

Executes (interprets) the Logo2006 program shown in the LogoGui. (Note: If the GUI is displaying the syntax tree instead of the program, the Interpreter should still execute the program.) In order to facilitate grading with our JUnit tests, I will specify some of the Interpreter methods below.


class Turtle

The turtle converts calls from the Interpreter into TurtleCommands, which it passes along to the TurtleCanvas. It also keeps track of its own state (what coordinates it is at, what direction it is facing, whether its pen is up or down, what color it is using, its speed, and whether it is paused). In order to facilitate grading with our JUnit tests, I will specify some of the Turtle methods below.


interface TurtleCommand

Declares the method void execute(Graphics g).

class ColorCommand    implements TurtleCommand
class DrawLineCommand implements TurtleCommand
class MoveCommand     implements TurtleCommand
class HomeCommand     implements TurtleCommand

Each of these holds information specific to that command. These are very small classes: a DrawLineCommand has fields x1, y1, x2, y2 to hold the endpoints of the line, and its execute method calls g.drawLine(x1, y1, x2, y2), while a HomeCommand has no fields and its execute method does nothing.


class TurtleCanvas extends JPanel

This is the drawing area. It maintains a list of all TurtleCommands that it has been given. It requires the method public void paint(Graphics g); when called, this method will execute all those commands, in order, and afterwards it will draw the turtle (it may have to ask the Turtle where it is and what direction it is facing). It will have a clear() command to empty the list of TurtleCommands (used when running a new program). This class does not need JUnit tests.

 

Creating instances of these classes

Ideally, all classes are independent, and can be tested independently. The above classes fall short of this ideal. To make it feasible for us to test your classes, therefore,

• The main method of LogoGui creates the Interpreter.
• The Interpreter constructor creates the LogoGui and the Turtle.
  • The LogoGui creates the TurtleCanvas (in a method called from the constructor)
  • The Interpreter calls the getCanvas() method (which you write) of the LogoGui to get the TurtleCanvas, and uses this as an argument to the Turtle constructor.

Is this the best way of doing things? Probably not. But it does work.

Testing

One of the central principles of JUnit testing is that testing should be done frequently, hence must require little effort. You shouldn't have to look at anything more than the green bar to know that all your tests passed. Since testing graphics requires more than this, the goal is to do as much testing as possible without graphics.

The two classes that require testing are Interpreter and Turtle.

Testing the interpreter

You can test expressions without reference to anything else (as long as you use numeric constants, not variables). You can test conditions and directions once you have expressions working (conditions return a true/false value; directions return an integer number of degrees).

Before doing much else, you must be able to store and fetch the values of variables, so write methods to test these next. (Because "store" and "fetch" are not Logo2006 commands, you probably should make these methods protected.) Until you implement procedures, all your variables will be global.

Once you have global variables working, you can test out assignment statements, repeat loops, while loops, and if statements. Test these by doing some computation, saving the result in a variable, and testing the (numerical) result.

You can test define and call statements by writing some Logo2006 procedures that do computation, and storing the results in global variables (local variables no longer exist once the procedure finishes). You can test local variables by writing procedures that use them (preferably, procedures that use other procedures), and storing the results in global variables. Recursion is more difficult to test, because our procedures don't return values, but it can be done.

Commands that tell the turtle to do something (move, pendown, etc.) should be tested in a separate test class.

Testing the turtle

The turtle has state: where it is, whether the pen is up or down, etc. You can test turtle commands by issuing the command (such as move), then using getter methods to test if the turtle's state is as expected (such as, is it in the correct x, y position after a move). You can speed these tests up by setting the turtle's speed to maximum.

Ultimately, of course, you have to look at the results; but you shouldn't have to do that very often.

Required methods

I need to specify signatures so that we can do JUnit testing. Here they are, with little or no explanation; we will test these methods. If the purpose of a method is not clear, ask.

Interpreter

• protected Interpreter() // constructor
• protected int evaluateExpression(Tree<Token> node)
• protected boolean evaluateCondition(Tree<Token> node)
• protected int evaluateDirection(Tree<Token> node)
• protected void store(String name, int value)
• protected int fetch(String name)
• protected void interpret(Tree<Token> node)
• protected void stripProcedures(Tree<Token> tree) // for Part II
• protected void callProcedure(String name, Tree<Token> actualParameters)
protected void callProcedure(Tree callStatement) // for Part II

Turtle

• protected Turtle(TurtleCanvas canvas) // constructor
• protected void color(String colorName)
• protected void face(int degrees)
• protected void home()
• protected void move(int distance)
• protected void pendown()
• protected void penup()
• public void setPaused(boolean paused)
• protected void setSpeed(int speed)
  Getters:
  
• protected double getX() // turtle's distance in pixels east of home
• protected double getY() // turtle's distance in pixels south of home
• protected int facing() // degrees counterclockwise from east
• protected int getSpeed()
• protected Color getColor()
• protected boolean isPenDown()
• protected boolean isPaused()

Interpreting parse trees:

This is the same table as in the Parser assignment, but I have replaced the Comments column with a How To Interpret column. I am making a distinction between "evaluate," which says to compute a value, and "interpret," which does not.

Grammar rule (partial)	Example input	What it should push onto the stack	How To Interpret
<variable> ::= <NAME>	"foo"		Depends on context. In an <expression>, look up the value of the variable. In an assignment statement, assign a value to the variable. See below.
<command> ::= "move" <expression> <eol>	"move 5 \n"		Evaluate the <expression> and tell the Turtle to move forward that many spaces. If the pen is down, the turtle draws; otherwise, it moves without drawing.
<command> ::= "turn" <direction> <eol>	"turn east \n"		Evaluate <direction> to find the direction (in degrees counterclockwise from East) and tell the Turtle to face in that direction.
<command> ::= "turn" <direction> <eol>	"turn left 45\n"		Evaluate <direction> and add it to the direction the turtle is currently facing. Tell the Turtle to face in that new direction.
<command> ::= "penup" <eol>	"penup \n"		Tell the Turtle not to leave a line behind it when it moves.
<command> ::= "pendown" <eol>	"penup \n"		Tell the Turtle to leave a line behind it (in the current color) when it moves.
<command> ::= "color" <colorName> <eol>	"color red \n"		Tell the Turtle what color to use in any future drawing.
<command> ::=    "home" <eol>	"home \n"		Tell the Turtle to move to the center of the TurtleCanvas and face East.
<command> ::=  <variable> "=" <expression> <eol>	"x = 5 \n"		Evaluate the right child <expression> and save the numerical result in the left child <variable>. See below.
<command> ::=  "repeat" <expression> <block>	"repeat 5 [ \n   penup \n ] \n"		Evaluate the <expression>, then interpret the <block> that many times.
<command> ::=  "while" <condition> <block>	"while x < 5 [ \n   penup \n ] \n"		Evaluate the <condition>, and if it is true, interpret the <block>. Repeat until the <condition> becomes false.
<command> ::=  "if" <condition> <block>	"if x < 5 [\n   penup\n ]\n"		Evaluate the <condition>, and if it is true, interpret the <block>, otherwise do nothing.
<command> ::=  "if" <condition> <block> "else" <block>	"if x < 5 [\n   penup \n ]\n else [\n   pendown \n ]\n"		Evaluate the <condition>, and if it is true, interpret the first <block>, else interpret the second <block>.
<command> ::= "call" <name> { <expression> } <eol>	"call foo 1 2 3\n"		Don't do anything. We'll handle this in a followup assignment.
<colorName> ::= "red"	"red"		Tell the Turtle to set the current color.
<block> ::= "[" <eol> { <command> } "]" <eol>	"[ \n   penup \n   home \n   pendown \n ] \n		Interpret each of the children of the <block>, in order.
<comparator> ::= "<" | "=" | ">"	"<"		See <comparison>.
<comparison> ::= <expression> <comparator> <expression>	"x < 5"		Evaluate the two children, compare the results, and return a true or false value.
<condition> ::= <disjunct> { "or" <disjunct> }	"x<0 or x>100"		Evaluate the first child, and if it is true, return true. If the first child is false, evaluate the second child, and return that result.
<condition> ::= <disjunct> { "or" <disjunct> }	"x<0 or x>y and y>100"		As above.
<disjunct> ::= <conjunct> { "and" <conjunct> }	"x>y and y>100"		Evaluate the first child, and if it is false, return false. If the first child is true, evaluate the second child, and return that result.
<disjunct> ::= <conjunct> { "and" <conjunct> }	"x<y and y<z and z<100"		As above.
<conjunct> ::= [ "not" ] <logicalFactor>	"not x < 5"		Evaluate the child and return its negation.
<logicalFactor> := <comparison>	"x < 5"		This is the same Tree as for a <comparison>. See <comparison>.
<expression> ::= <term> { <add_operator> <term> }	"foo + 5"		Evaluate the two children and return their sum.
<expression> ::= <term> { <add_operator> <term> }	"x + y + z"		Evaluate the two children and return their sum.
<term> ::= <factor> { <multiply_operator> <factor> }	"foo * 5"		Evaluate the two children and return their product.
<factor> ::= <name>	"foo"		When a variable occurs in an <expression>, look up its value in a hash table, and return that value.
<factor> ::= "(" <expression> ")"	"(foo + 5)"		Evaluate the two children and return their sum.
<procedure> ::= "define" <name> { <variable> } <eol> { <command> } "end" <eol>	"define foo x y z \n   move x \n end \n"		Don't do anything. We'll handle this in a followup assignment.
<program> ::= <command> { <command> } { <procedure> }	"penup \n home \n define foo x y z \n   move x \n end \n"		Interpret the <block> that is the first child of <program>; don't do anything with the <procedures> branch for now.
<eol> ::= "\n" { "\n" }	"\n"		No tree, nothing to do.

Program architecture:

The Interpreter walks the parse tree and interprets the commands as necessary. Many of these will be control commands (repeat, if, while, call, and assignment statements). These commands are handled directly by the Interpreter class.

Some commands (move, turn, penup, pendown, color, home) will cause the turtle to do something. For each such command, the Intepreter will call a method in the Turtle class (such as public void forward(int n)). It will also add a delay (for move, turn, and home), based on the GUI speed control, so that the user can watch the turtle move. The turtle will keep track of its state (position, direction, pen, color, speed, whether paused).

The commands that the turtle receives will affect what is drawn on the screen (the TurtleCanvas). The Turtle class will create a TurtleCommand to send to the TurtleCanvas. The TurtleCanvas keeps a list of all the TurtleCommands it has received, and executes them whenever the screen has to be repainted, with no delay between commands.

TurtleCommand is an interface with one method, execute(), that implementing classes must define. There should be several implementations of TurtleCommand; I've provided two, a DrawLineCommand that you will probably want to keep, and a DrawStringCommand, which is a throwaway example.

Movement

The distance that the turtle is to move is given in pixels. This is exact if the turtle is moving horizontally or vertically. However, if the turtle is moving at an angle, you will need to use trigonometry to determine the approximate location that the turtle will move to. It is a good idea to store the turtle's x-y location as double values, and cast to int as necessary; this will prevent roundoff errors from accumulating, and will result in a visibly better drawing.

The direction that the turtle faces is given in degrees, according to the following scheme: east is 0°, north is 90°, west is 180°, and south is 270°. A turn to one of these directions is to that many degrees; a turn left or turn right implies a 90° turn, while a turn left <expression> or turn right <expression> means to turn that number of degrees.

Variables

All of our Logo2006 variables are integer, and do not need to be declared (they are implicitly declared when they are first encountered by the Interpreter). In this assignment, all variables are global variables, and are kept in a HashMap, with their name as the key and their integer value as the value. In your Interpreter, you will need the following methods:

protected void store(String name, int value)

Stores the name/value pair into the global variable hash table, possibly replacing a previous value.


protected int fetch(String name)

Returns the value in the global variable hash table that is associated with the name. Special case: If the name is not in the hash table, its value is zero; put it into the hash table and return zero.

In the next assignment, store and fetch will be modified to also handle local variables.

Provided code:

I haven't been sitting still; some of these classes have been modified. Here are the latest versions. (I intend to post Parser.java before much longer.) You should use your own classes as much as possible, and only use mine if absolutely necessary.

Due date:

To be determined, but not earlier than March 23.

Turn in your program via Blackboard, and follow these conventions:

• Do not use package declarations in your Java files.
• Put your files in a single directory, and zip up that directory.
• Do not include your javadoc files.

It is your responsibility to check and make sure that you have correctly submitted the correct files via Blackboard. Errors in the submission process will not be taken as an excuse for late homework.