CIT594 Writing the Interpreter

CIT 594 Writing the Bugs Interpreter
Spring 2008, David Matuszek	TR 4:30-6:00, Moore 212

The Bugs Interpreter Part 2 assignment is a particularly difficult one. As I see it, there are two main sources of difficulty:

You have done most of the parts of this assignment; how do you put them together? That is, what is the overall program design?
While you are trying to integrate these parts, what kind of testing can you do?

Here's what you have so far:

A Parser for the Bugs language. Given a String, it will produce the Abstract Syntax Tree (AST).
A Bug class
- that can:
  - Interpret the statements of the AST for an individual bug.
  - Fetch and store the bug's own variables.
- but cannot:
  - Interpret the actions (commands that show up on the screen) for a bug.
- Part 2 of the assignment gives fairly explicit instructions for:
  - Calling the bug's own methods.
  - Fetching and storing variables declared in the Allbugs part (but...where is this done?)
  - Getting functions from Allbugs
A GUI class (with a bouncing ball) that you can use almost directly.
- If you are using NetBeans, you can use the GUI you wrote for a previous assignment.
- If you are using Eclipse, I've provided a similar but much simpler GUI that doesn't depend on NetBeans.
The provided ThreadMaster and Worker classes that demonstrate how to coordinate Threads.

How do you put all these pieces together?

A use case

One aid in designing a program is to think of a use case: A little "story" about how the user might make use of the system. Let's look at a use case and see what we can learn from it.

What the user does	What happens
The user writes a program in the Bugs language, using his or her favorite text editor.	Nothing yet.
The user starts our Bugs interpreter, possibly by double-clicking on a program named Bugs.	The GUI appears. It currently has buttons labeled New, Step, Run, Pause, and Reset. Since we don't yet have a program loaded, these buttons should all be disabled.
The user looks for a Load... menu item.	This is the usual way of loading a file. We do have a File menu, we should add a Load... command to it.
The user loads in a Bugs program.	The GUI should ask the Parser to parse the program. If there are syntax errors, it should notify the user in as much detail possible. If the program is correct, the Step and Run buttons should be enabled. The New button made sense when the GUI created a model (the bouncing ball). It doesn't seem to make sense now, so it should be eliminated. What else can be done to prepare the program? The Allbugs section declares variables and functions, and these can be extracted and put into hash maps. The named Bugs can be created (and given their respective ASTs), and put into another hash map. The maps I have are: variable name --> double function name --> AST for that function bug name --> `Bug` object Remember the MVC (Model-View-Controller) Pattern, which says that the model should be entirely separate from the Controller and View. So, after reading in the program, all the above work should be done in a model class. Let's call it `Interpreter`. Ideally, one GUI action should call one model method, but it doesn't actually hurt to call several.
The user clicks the Run button.	The GUI tells the interpreter to execute the program. The interpreter has to create a Thread for each bug (if it hasn't done so already), and start them. It needs to use code extremely similar to that in `ThreadManager` to coordinate the Bugs (and each bug has to have code extremely similar to that in `Worker`). You should study this code. A bug may execute as many "statements" as it likes, but only one "action". After an action, it needs another work permit to continue. Actions draw something on the screen.
The user clicks the Pause button.	The Bugs should pause execution as soon as possible. Effectively, this means that the interpreter should check a "blocked" flag that tells it to stop handing out "work permits".
The user clicks the Step button.	The interpreter should hand out one and only one more round of work permits each time the Step button is clicked.
The user clicks the Run button again.	The "blocked" flag should be cleared, and the interpreter should resume handing out work permits. It does not do all the work required for the first click of the Run button.
[Not a user action:] A bug reaches the end of its program and the Thread dies.	The interpreter should notice the Thread death, and thereafter hand out work permits only to live bugs, not dead ones. If/when all Threads die, the interpreter has nothing more to do.
The user clicks the Reset button.	The interpreter should stop any remaining bugs, and return to the state it was in just after the Bugs program was loaded.
The user loads another program.	All current activity should cease, and the new program should be processed the same way the previous one was.

The design

The MVC is usually the best pattern to use when writing a GUI-based program. How do we divide the above work into these three parts?

The Controller: The GUI class has all the controls on it, so it is most naturally part of the Controller. The Controller might also contain other classes for interacting with the user, but in this assignment there isn't much more.
The Model: The Model should do all the actual work of the application, so it will include the Parser, the Bug class (for interpreting the code of individual bugs), the Interpreter class (for controlling and coordinating the bugs--which also makes it a handy place for keeping the variables and functions declared in Allbugs). A few other classes are included in the Model, such as Tree, Token, and SyntaxException.
The View: It will turn out that there is some work involved in preparing results to display, so it helps to have a separate View class to do that work. Since the display happens in the large central JPanel of the GUI, a really good way to do this is to write a View class that extends JPanel, and put the View object (rather than a plain old JPanel) into the GUI.

The use case and the MVC pattern, taken together, give us some strong hints about the design.

The GUI: This is your Controller. When Load... is chosen, a program has to be read in, parsed, and partly interpreted. The GUI should ask the user for the File; then it could either read in the File and give the text to the Interpreter, or it could give the text to the Parser and give the resultant AST to the Interpreter. When Run or Step is chosen, it should tell the Interpreter to run or to single step.

The Interpreter: The Interpreter class is the "main" class of the Model. The constructor should be given an AST for a <program> (or the text of a program to parse into an AST), and it should construct the needed maps (Allbugs variables, Allbugs functions, and Bugs). Later, when told to Run or Step, it should start() all the Bugs (if they haven't already been started), and hand out "work permits" to either run continuously or single step.

Quick Java review. The wait() method causes a program to pause right where it is, and wait until it gets a notification. The notifyAll() method sends a notification to all waiting bugs. Since you cannot control which bugs get notified, when a waiting bug gets notified, it usually has to perform some other check to see whether it can proceed, or whether it has to wait some more. These methods are only allowed in synchronized code.

The Bugs: Each Bug runs in a separate Thread. The constructor for a Bug needs to be given the AST for that bug, so that it has something to interpret. It also needs to be given a reference to the Interpreter that started it up, because it will have to go to that interpreter to get work permits, and to ask for variables and functions declared in the Allbugs part, and to ask for other Bugs (so it can read certain variables from them, such as Fred.x).

Getting the interpreter to create all the Bugs, and to coordinate their activities, is a fairly complex problem. The GUI just adds complexity, and makes testing that much harder. If you are using MVC, the Model part is completely independent of the Controller and View. This is a huge advantage, because you don't need the GUI to test the Model.

All you need is a simple main method (I put one in the Interpreter) to read in a file, parse it, and run the Interpreter. The methods that are supposed to draw lines can, temporarily, just print out information about the line instead. Later, you can add in the GUI.

The View. You might think that a Bug, when it moves, draws a line directly on the display. This seems obvious, but it's horribly wrong, and causes more problems than I have the energy to write about. Instead I'll just remind you that a Bug, which is part of the Model, should be completely independent of the View.

Here's what it does instead. When a bug "draws a line" (with a move, moveto, or line command), it really just creates an object representing that line, and puts it in a list of "things that should be drawn." In my code I have a simple class called Command that holds the x and y coordinates of the two endpoints of a single line, and the color that the line should be. Each bug could keep its own list of commands, but I found it slightly simpler to have just one list, in the Interpreter class.

The View class extends JPanel, and is the large area in the center of the GUI. When its paint(Graphics g) method is called, it paints all the lines in the list of Commands. Then it draws something to represent the individual bugs, at each bugs current position. It does this 25 times a second (once every 40 ms.), regardless of what the bugs are doing or not doing. This is done in a completely independent Thread, created by a javax.swing.Timer object that I created when I first started the program and made a View object; the Timer calls repaint() every 40 milliseconds.

A note on the speed control slider in the GUI: It does not control how often things are drawn. Instead, it controls how long the Interpreter should sleep before it tries to hand out more work permits.