Purposes:

• To teach the use of stacks and stack frames
• To give you more experience with Threads
• To further illustrate how interpreters and compilers work

General Idea:

There are three aspects to this assignment:

• Implementing functions and function calls
• Using Threads to coordinate actions among multiple Bugs
• Displaying the actions of Bugs in a GUI

Create a new class called Interpreter. This class will ask the user for a text file containing a Bugs program, then it will interpret the program. The Bugs and their movements will be displayed in a GUI.

Details:

The Interpreter

The Interpreter should use a JFileChooser to allow the user to select a file containing a Bugs program.

The program may begin with an Allbugs part, which may have some var declarations and some function definitions. Your Interpreter class should have two HashMaps, one for variables and one for functions. Interpret these the same way you did for the Bug class, in the previous assignment. (If there is no Allbugs part, these HashMaps can be empty.)

After the optional Allbugs part, there will be one or more Bug declarations. For each one, create a new instance of the Bug class. Keep track of all the bugs you create. Each bug should have its own Thread (by extending Thread or implementing Runnable).

Once all the bugs have been created, start them running. Coordinate their actions (see Coordinating Bugs, below), so that each bug executes up to and including an "action" command, then waits for the other bugs to catch up. When each bug has executed an action, display the results in a GUI.

Functions

A bug has access to two HashMaps containing functions: One in itself, and one in the Interpreter object. (Other bugs each have their own HashMap of functions and access to the one in the Interpreter object.) To look up a function by name, look first in the bug's HashMap; then, if not found, look in the Allbug's HashMap. Wherever you find it, you will interpret it the same way. (If you never find it, throw a RuntimeException.)

For your main program you also used a HashMap to keep track of the values of variables. Functions have local variables and parameters. This means you will need to use, not just one HashMap, but a Stack of HashMaps for keeping track of variables.

Your basic data structure for dealing with variables will be a stack of maps; specifically, a Stack<HashMap<String,Integer Double>>. Name this stack scopes. Push the HashMap that you used for variables in Part 1 of the Interpreter onto the stack, so that it is the first (bottommost) thing on this stack. (Note: Stack extends Vector, and you will almost certainly need to use one or more Vector operations; but most of the time, think of this as just a Stack.)

Each time you call a function, you create a new HashMap and put it on the stack. This HashMap is used to hold the variables (and their values) that are "owned" by this function. If the function recurs (calls itself), create a new HashMap for each level of the recursion. In more detail:

To call a function,

1. Create a new HashMap for the function, and put it on the stack.
2. Evaluate the arguments (actual parameters) to the function.
3. Get the corresponding formal parameters of the function (from the define).
4. Put the formal parameters and their values (the argument value) into the HashMap.

To fetch the value of a variable,

1. Look in the topmost HashMap (on the Stack) for the variable. If you find it there, use its value.
2. Look in the next HashMap down (on the Stack). If you find it, use its value.
3. Keep searching downward in the Stack until you either find the variable in one of the HashMaps, or you run out of HashMaps.
   1. If you find it, get its value.
   2. If you don't find it, look for it in Allbug's HashMap of variables (in the Interpreter object).
      1. If you find it, get its value.
      2. If you can't find the variable anywhere, it's an undeclared variable. Throw a RuntimeException.

To store the value of a variable,

1. As with fetch, look for the variable in the topmost HashMap, then the next, then the next, etc., until you find the variable or you run out of HashMaps.
   1. If you find the variable in some HashMap, put its new value there.
   2. If you don't find it, look for it in Allbug's HashMap of variables (in the Interpreter object).
      1. If you find it, put its new value there.
      2. If you can't find the variable anywhere, it's an undeclared variable. Throw a RuntimeException.

To return from a function,

1. Evaluate the expression that is to be returned, and save it in an instance variable.
2. Pop the function's HashMap from the stack.

This implementation method results in dynamic scoping of variables, rather than the lexical scoping that is used in most languages (including Java). That is, a function can use the variables in the function that called it, and the function that called that one, ..., all the way up to the main program.

Coordinating Bugs

The coordination problem is simple to describe but difficult to program. We want to have a number of Bugs performing "actions," in step with one another. No Bug should be performing action N+1 until all bugs have completed their action N.

An analogy would be musicians in an orchestra; they play different parts, but we prefer them to all play at the same "speed." The conductor's job is to coordinate the musicians.

From The Bugs Language paper:

The "main program" part of each bug is executed, up to and including an action command. Upon reaching an action command, the bug pauses execution until every other bug has also executed one action command. At that point, all the various actions are reflected on the screen, and there is a brief pause (a fraction of a second).

Once the new screen image has been displayed, each bug continues from where it left off, and again computation continues until all bugs have performed another action.

Notice that each bug continues "from where it left off." This is important. You cannot start a new Thread after every action is completed, because that would start the run() method again from the beginning; the Bug's Thread has to stop and wait() for a signal before it can continue. You have to make this work in your Interpreter program.

Because this kind of coordination is difficult to program, I am providing an extremely similar program (two files, ThreadMaster.java and Worker.java) which you can use as a model and adapt as necessary.

It would be a very good idea to read and understand my code before you try to adapt it.

In my program there is one ThreadMaster (like your Interpreter) and some number of Workers (like your Bugs). For synchronization to work, all synchronized methods need to be in the same class, so they are in my ThreadMaster class.

I think of a Worker as "blocked" (my term) if it is waiting to be allowed to run, and "unblocked" if it can run. Each Worker has a boolean blocked variable that is used by the ThreadMaster (the Worker itself never uses this variable for anything, but its a convenient way for the ThreadMaster to keep track of who is blocked and who isn't).

The ThreadMaster first creates a number of Workers, and keeps them in an ArrayList. Initially, all Workers are "blocked."

Next, the ThreadMaster tells each Worker to start(). (My Workers extend Thread, though they could equally well implement Runnable.) The Threads start, but because every Worker is "blocked," they don't get very far. About the first thing each Worker does is ask the ThreadMaster for a "work permit" for itself (the keyword this refers to the Worker doing the asking):

tm.getWorkPermit(this);

This synchronized method waits until some external agency (the ThreadMaster) sets this Worker's status to "unblocked." Once the Worker is unblocked, the method returns.

The ThreadMaster then goes into a loop. As long as there are Workers remaining (my code allows them to "die" at different times), the ThreadMaster tries to unblock all the Workers:

unblockAllWorkers();

To achieve the desired coordination, this synchronized method waits until all remaining Workers (some may have died) are blocked. Then it sets all remaining Workers to unblocked, and does a notifyAll(). (The notifyAll() causes all waiting Threads to check whether they can stop waiting.) As little work as possible should be done by a synchronized method, because it prevents other Threads from using synchronized methods. In this example program, the state of each Worker is printed out, simply to demonstrate that they are actually in step with one another.

When a Worker is unblocked (gets its "work permit"), it can do some work. In this example, the "work" is just to increment a counter and sleep for some random amount of time. (In the bugs Interpreter, your Bug would not be sleeping--it would be busy interpreting statements, up to the next "action" command.)

When the Worker finishes, it goes back to a blocked state. However, because the ThreadMaster has to keep track of who is blocked and who isn't, the worker does this by calling yet another synchronized method in the ThreadMaster:

tm.completeCurrentTask(this);

This synchronized method sets this Worker's status back to blocked, and does a notifyAll().

Remember, wait() and sleep(ms) both allow other Threads to execute. The difference is that sleep(ms) stops the current Thread for executing for a given number of milliseconds, while wait() stops the current Thread from executing until some other Thread does a notify() or notifyAll()--at which time, the Thread wakes up, decides whether it was the one being notified, and if not, goes back to waiting. These methods-- wait(), notify(), and notifyAll()--can only be done within a synchronized block (otherwise you get an IllegalMonitorStateException).

Finally, in my example the Workers are set to "die" after completing a certain amount of work (from 10 to 20 "work permits") worth.

tm.terminateWorker(this);

This synchronized method simply removes this Worker from the ArrayList of Workers. The way I have written the code, the ThreadMaster only knows about Workers that are in the ArrayList, so nothing bad happens by trying to reference a "dead" Worker.

Finally, we want to program to quit cleanly, not leave Threads running after everything is done. The Worker Threads are set to die after doing a certain (random) number of work permits. The ThreadMaster is in a (possibly infinite) loop, trying to unblock all remaining Workers; I have set it to exit the loop (and reach the end of the program, and die) when there are no more Workers:

while (workers.size() > 0) { unblockAllWorkers(); }

Other coordination issues

Each bug is able to fetch (not store) certain variables in other bugs (but not all of them). Specifically, each bug can read the values of another bug's x, y, and angle special variables. It can also read all variables declared in the other bug's "main" program--the ones in the bottom HashMap of the other bug's stack of HashMaps. In the other bug, this will be the HasMap at scopes[0]. You will need to provide some method in the Bug class to provide read access to these variables, using "dot notation" (e.g. Fred.x).

[Variables declared in a function only exist when a bug is executing that function. One bug cannot reasonably tell when another bug will be in a particular function, so we won't allow access to those variables.]

Variables declared in the Allbugs section are shared by all bugs, and all bugs have both read and write (fetch and store) access to those variables. You don't use dot notation to access those variables, just their names.

There are two "special" functions that you need to implement: distance(nameOfBug) and direction(nameOfBug). The first computes the distance between this bug and the named bug; the second computes the angle this bug should be set to in order to directly face the named bug. Both these functions are written in Java and made available to the Bugs program. You can do this by modifying the method you use in your Bug class to evaluate function calls, and make these special cases.

The GUI

You have already written, in the GUI (Bouncing Ball) assignment, the exact GUI you need for this assignment. Please use that GUI if you can. If you are now using Eclipse, and you have a hard time migrating the GUI from NetBeans to Eclipse, you can use my simple Eclipse GUI instead. All features of the GUI should work correctly.

There are likely to be two problems with the GUI. When you draw a bug on it, it will be difficult to "erase" that bug without possibly erasing other things as well. Also, when you cover the window with another, or resize the window, it will not redraw correctly. I will talk about possible solutions later.

Grading:

Due date:

Zip the complete NetBeans project and submit via Blackboard before midnight, Thursday March 24.