Figure 1: Support Window Creation
The long term goal of this MQP is to provide a free and accessible system by which anyone can learn the basics of programming. To that end, we designed a beginners' programming language called RoBOTL and implemented an interpreter for it in Java. The language is simple in nature, but includes more advanced object-oriented concepts. The interpreter includes a graphical interface, many standard debugging features and a full tutorial, the content of which is being supplied by a companion MQP.
Since the beginning of digital computers, programming has changed from an obscure hobby that many people do not understand into a lucrative profession that many people do not understand. Today, we are witnessing another major transition: programming is becoming a useful skill across a wide variety of fields. Unfortunately, the environments that require this skill--anything from maintaining a personal computer to using an application's macro language--are often not the best environments for learning the basic concepts required.
The long-term goal of this MQP is to provide a Web-based system by which someone can learn some of the fundamentals of computer programming with little or no prior experience. This is aimed partly at students, but also at simply anyone with an interest in learning to program. To this end, we have implemented an interpreter for a simple programming language in the form of a Java applet. This applet will be made generally available to the world.
The programming language, called RoBOTL, is an elementary object-oriented language. It was derived from a language called Karel the Robot, which was created at Stanford in the 1970s. Complete information on the nature and history of RoBOTL can be found at www.robotl.com. For now, it is enough to know that it is a graphical language based on moving virtual robots around on a grid. The robots can encounter obstacles and manipulate "beepers," which are just markers that can sit in a grid cell or be carried by the robots. These obstacles and beepers are laid out by the programmer as part of a RoBOTL program. The programmer can also define multiple types of robots by subclassing and give them variables and custom instructions.
There were three stages to this project. The first few weeks were spent implementing a parser for RoBOTL and some of the underpinnings of the interpreter. During this time, the language was slightly modified from earlier versions to improve consistency and functionality. When the parser was able to generate usable abstract syntax trees, the basic interpreter was completed to traverse the trees and simulate the operation with only a rudimentary display. The display remained relatively static until the interpreter was almost complete. At this point, we changed the original utilitarian layout to be much more flexible and customizable. As the interface caught up to the engine, we implemented new interface features that were not dictated by the interpreter, but were added strictly for the user.
In addition, we are working with a second MQP being done by Pia Haugerud. During the first term, Pia acted as a consultant on the interface issues. She has already performed some usability tests to evaluate our applet, which generated many useful suggestions. She will also be writing a tutorial for RoBOTL so that new users have a place to start learning.
We have found several efforts, inside and outside of WPI that bear some resemblance to our own. However, while some may be similar on a technical basis, none of them share the same long-term goals as ours. All of these examples are attempts to create interpreters or runtime environments as Java applets.
The most unusual of these was used for the 1997 Frontiers program at WPI. It was written specifically for Frontiers by Yong Li. For the Frontiers system, a hybrid of Java and RoBOTL called JavaBOTL was created. This primarily involved implementing the built-in functions of RoBOTL in Java. Since Java and RoBOTL syntax are both loosely based on C, it is not difficult to translate RoBOTL to Java. With this system, a RoBOTL program can be slightly modified to conform to Java syntax, and then have access to a simulated version of the RoBOTL runtime environment. Other enhancements were made to RoBOTL in the process, including the addition of threads, so that robots could be run concurrently.
In B, C and D terms of the 1996-1997 school year, Michael Gennert of the WPI Computer Science department advised an MQP group consisting of David Bishop and Edward Hallissey. The purpose of this project was to use Java to write an interpreter for the Scheme programming language. The interpreter, parser and interface were all completed successfully for this project, but the group was unable to integrate the interface with the other two. The problem is that the parser generated by the Java Compiler Compiler (JavaCC) takes its input in the form of a stream, but the interface produces its output as a string.
As part of WPI's graduate compiler course, CS 544, Ross Andrus implemented a full RoBOTL interpreter as a Java applet. Understandably, the focus of this project was to create a working interpreter and just enough of a user interface to demonstrate that it operated correctly. It was later expanded by Tom Custodio. We have obtained Ross's source code and occasionally referred to it to get started. Ross also used JavaCC to generate the parser and the accompanying JJTree tool to build the abstract syntax tree. Our implementation has some things in common with his, though with more of an emphasis on the interface.
Scouring the Web, we did actually find an applet-based interpreter available for public use. Michael Cahill, a student at the University of Sydney has created an applet that interprets what he describes as a "polymorphic functional language." This was actually a translation of an existing interpreter from Galileo to Java. The applet features a relatively mature interface. The language is very simple, so parsing was done without a parser generator and an abstract syntax tree was never explicitly constructed. Our interpreter will be a bit more complex, but we can certainly learn from his interface.
Ross's and Michael's applets are the closest to our goals, Ross's because it is the same language and Michael's because of the interface. However, nothing that we have found is designed to be generally accessible, including thorough documentation and a language tutorial. Also, nothing has the sophisticated development environment that we have.
The RoBOTL language was designed to be simple enough that people could easily learn structured programming techniques, yet have advanced functions that would allow for object-oriented syntax and mechanisms. This was accomplished by a combination of intuitive instructions for controlling robots and more sophisticated C-style constructs. The RoBOTL language keywords mimic instructions that one would issue to a real-life robot, and the project premise is based upon physical robots and objects (beepers, worlds, blocks, etc.)
All RoBOTL programs are split up into two main sections: define statements, and execute statements.
define section:Initially, the world of RoBOTL is very plain. The world is barren; no walls or beepers exist. The only available robot type is basic_bot, which includes the pre-defined robot functions and no variables. There are obviously a limited number of programs one can create using only this pre-defined robot and sparse world. To perform more complex operations, the user must be able to define new robots and worlds. This is accomplished via the define section.
There are four types of define statements that allow a user to make the world more interesting and useful. The first is DefineMapSize. By default, the RoBOTL map is a square with twenty columns and twenty rows. This size is appropriate to start with, and will handle most programs one would want to write. There are times, however, where a larger or smaller map size is appropriate. While the map must always be square in shape, the DefineMapSize statement allows the user to change the number of rows/columns to be in the range between ten to fifty.
The second type of WorldEntity statement. Using these statements, one can create "worlds" which are defined to be collections of blocks (obstacles for the robot), and beepers (items with which robots can mark grid spaces.) These worlds can be placed onto the RoBOTL map, and may overlap worlds that have already been placed. Since overlapping worlds may conflict in any given grid space, the following placement rules are followed:
NewRobotType is the third type of define statement. This statement is used (in true object-oriented form) to derive a robot from either the basic_bot superclass, or a previously declared robot type. Subclassing is performed by the use of the IsLikeA statement (declaring that a new robot type "is like a" basic_bot declares it to be a sub-class of basic_bot.) The purpose of creating a new robot type is to allow users to define local variables and instructions which each robot of the defined type can use. Since the only defined instruction which can be used to turn a robot is turnleft, one of the first instructions that is typically defined by a user is "turnright", which simply causes the robot to execute turnleft three times.
DefineGlobalInteger is the fourth and final type of define statement. Using this statement, one can define a variable which is usable by robots, and by statements within the execute section.
execute section: While the define section is actually optional, the execute section is required. This section is much like the main() function within a C or C++ program; it is the only section where a user can issue commands to a robot, and control the placement of worlds onto the RoBOTL map. However, this section is itself split up into two parts: execute statements and robot instructions. Statements are mostly used to interface the program with the RoBOTL map, by use of the new, place, and remove statements. Instructions are used to actually instruct a given robot to perform certain functions, such as move, turnleft, and any user defined instructions. These robot instructions reside within a tell Statement.
Within define statements, execute statements, and robot instructions, users are allowed to use mathematical expressions in locations where values are needed. RoBOTL uses a fairly standard mathematical expression set. Operators which are included in the expression set (in decreasing precedence order) are:
Also allowed in the expression grammar are parentheses (to define precedence: 3*5+2 is not equal to 3*(5+2)), and signed values for integers (+2 and -3, etc.)
Interpreters and compilers can be thought of as having two major sections, the front-end (lexing, parsing, and semantic analysis, which includes intermediate representation (IR) generation), and the back-end (interpretation of the program from the optionally optimized intermediate representation, and IR to bytecode.) We used JavaCC to generate a parser and JJTree (which is bundled with JavaCC) to create abstract syntax trees.
JavaCC is much like the UNIX tools 'lex' and 'yacc' in that a lexer and parser is generated from a template file. However, while yacc produces a bottom-up parser (LALR(1)), JavaCC creates a top-down parser (LL(1)). The source file for JavaCC is composed of a number of sections:
The options set various parameters for both JavaCC and JJTree such as the number of characters for lookahead, case-insensitivity, default AST node type, etc.
A list of all tokens within the language. In our case, some of these include execute, definemapsize, and place.
Tokens which are matched, and attached to a special variable within the following token. This allows things such as comments to be ignored while parsing language productions, but to be available after a production is completed.
A list of tokens to skip. For this project, the skip tokens were whitespace characters (space, newline, tab, etc.)
The actual list of language productions. For example:
Program -> [DefineSection] ExecuteSection
ASTStart Start() : {}
{
[Declaration()] Execution() { return jjtThis; }
}
JJTree is a pre-processor for the JavaCC source which creates an abstract syntax tree (AST) from the JavaCC productions. By default, all productions create a simplistic node in the AST. However, we chose to ignore certain productions for this project. This is because some productions are needed to parse, but are irrelevant during interpretation.
The RoBOTL JavaCC/JJTree source files were designed to create source files which are efficient in both size and speed, and also allow a decent amount of user feedback and functionality. For instance, the interpreter allows C++ style comments (both single (//) and multi (/* */) line) within a RoBOTL program. Comments aren't used within the language, but they are a nice thing to have when programming. For the abstract syntax tree used in the project, we tried to make efficient use of memory by keeping the number of nodes used to a minimum. To do this, we didn't create nodes from irrelevant productions (see above.)
One of the most efficient sections of the RoBOTL AST is within the expression nodes. One of the advantages of using JJTree to handle the AST generation is that a node can have multiple children, instead of the more common binary tree method which constrains nodes to have only two children. Our expression implementation allows the AND and OR nodes to have a relatively unlimited number of children. Using this feature, the expression "3 or 4 or 5" can be expressed in four nodes instead of five:
OR instead of OR 3 3 4 OR 5 4 5
The interpreter takes the abstract syntax tree generated by the parser and executes the RoBOTL program it represents. As the interpreter walks down the tree, it identifies the different nodes and executes them internally. Symbol tables are built to keep track of all of the robots, robot types, variables and world entities that are created. Other data structures are updated to keep track of the positions of robots, beepers and blocks on the grids as well as the states of the robots. As these states change, the display is updated to reflect them.
Before delving into the internals of the interpreter, a couple of the primary Java classes should be described. The interpreter portion of the project has over 30 classes in it of varying size and complexity. However, control of the applet's behavior is ultimately shared between two major classes: RobotlApplet and RobotWorld. RobotlApplet is the main Applet-derived class that is referenced by the HTML file. It initializes the primary window in the interface and all of its components and it handles all of the actions that occur in that window. In addition, when a RoBOTL program is executing, the applet receives frequent messages about the state of the execution. The applet, in turn, can inform the interface elements when and how to update themselves. RobotlApplet, then, serves as a kind of communications center; it controls the interactions between the user and the applet as well as between the different interface elements.
RobotWorld is the class that controls the actual interpretation of a parsed RoBOTL program. RobotWorld walks through the abstract syntax tree created by the parser and updates the internal RoBOTL grid and the global symbol tables. Although interpretation of commands issued to robots is ostensibly handled by another class called Robot, Robot actually calls back into RobotWorld to interpret the expressions, conditionals, loops and assignments. Even robot movement is ultimately handled by RobotWorld, not Robot.
Although RobotlApplet ultimately acts as a center of communication, messages sometimes go through intermediate objects. For instance, a Robot object doesn't have a reference to the presiding RobotlApplet, but it does have one to the RobotWorld in which it exists. Since there are only a few messages that a Robot needs to send to the RobotlApplet, RobotWorld has wrappers for them. The wrappers simply call a routine in RobotlApplet with the same arguments. This system (also used elsewhere) contributes to the robustness of the applet and helps to preserve our sanity. The performance shouldn't be impacted because Java will inline these methods, copying the body of a method directly into the place where the method call would ordinarily be.
When the interpreter engine was initially being developed, interpretation took place in the same thread as the rest of the applet. RobotlApplet simply called a method and turned over control to the engine. This had two problems. First, if the applet display was temporarily covered by another window or for some other reason needed to perform a full screen redraw, it would not be able to do so. The interpreter engine would have had to either perform periodic full screen updates, which is very slow, or call back into RobotlApplet regularly to give it a chance to update any invalid regions. Neither of these is very desirable.
The second problem is that it did not lend itself to one of the features we were planning: debugging. The central feature of the debugging system would be the ability to pause execution of the program between instructions. The user would then be able to retrieve information about the current state of the program. In order to do this in the original implementation, the engine would have to somehow save its state and return control to the rest of the applet. The interpretation state would then have to be restored when execution resumed. While not impossible, this would be a complicated system prone to errors.
Once the code was to the point at which we could starting thinking about display issues and debugging features, we solved both of these problems by running the interpreter in its own thread. When the user starts to run a program, a new thread is created. Execution of this thread starts in RobotWorld, the main part of the interpretation engine. Java's thread support makes it remarkably simple for RobotlApplet to communicate with the thread. Starting and stopping the execution of a program is simply a matter of creating and destroying the thread.
Our interface also lets the user specify an amount of time to pause between instructions. Every instruction that should have a pause after it calls a method in RobotWorld that will suspend the thread for the required amount of time. When the user selects a new delay time, RobotlApplet sends a message to RobotWorld indicating the new delay. The next time a delay is scheduled, RobotWorld simply instructs the current thread to pause for the amount of time currently set.
While only the significant robot instructions cause execution to pause for a fixed amount of time, execution can be paused indefinitely at almost any instruction represented by a node in the abstract syntax tree. Before almost any node in the tree is executed, a small method is called which can suspend the thread. The interface provides a means both to pause execution indefinitely and to step through a program one instruction at a time. These can both be accomplished with a single flag in RobotWorld. When the user pauses or resumes execution, the flag (called interrupted) is reversed. If it becomes positive, the thread will be suspended indefinitely at the next appropriate tree node. If it becomes negative, the thread is notified that it may resume. When the user presses the "step" button, interrupted is simply set to true and the thread is signaled to continue. This way, one node will be interpreted, but the thread will be suspended before the next one.
Allowing the user to control the execution of a program to this degree is the first half of our debugging scheme. However, stepping through a program is of very limited use if the user can't get any information about the state of the program while it's paused. We still needed a way to get information about the state of the execution to the user. This is discussed next in the section on the interface.
Both because this interpreter is for a fundamentally graphical language and because our target is beginning programmers, the interface is a crucial part of the project. We have had sketches of possible interfaces since early in the project, but implementation didn't really begin until the basic interpreter was nearly complete. Initially, all of the program feedback was done through the console. This was of course for development purposes only. As this became inadequate for testing the interpreter, we wrote a simple graphical grid display and laid out the interface in a static manner. Finally, when the interpreter engine was nearing the end of its development cycle, we laid out everything in a movable, resizable window. A screen shot of the final interface can be found attached to the end of this document. The interface was loosely geared toward Windows and Macintosh users and was subjected to usability testing by Pia and our companion MQP. Then we really got to work.
As was mentioned above, our debugging system needs some way to get information about the program's state to the user. Of course, since the RoBOTL language itself includes graphical output, the user is always getting some feedback. However, not all information can be displayed in the limited space available, especially information about a robot. A robot's position and direction are displayed effectively on the grid, but it's more difficult to display a robot's identity or the number of beepers that it carries. And when it comes to variables (both robot and global), there's simply no way to fit them into our existing display. We solved this problem with something similar to context-based help.
In Java, when the mouse pointer moves into, over or out of a component in the interface, an event is generated. The object that draws the grid (RobotlCanvas) catches its mouse events and notifies RobotlApplet. RobotlApplet uses this to display information about the grid cell that the mouse is currently pointing to. Our interface includes a text box for this purpose. When the mouse moves into a new cell in the grid, information on that cell (coordinates and contents) is displayed in the text box. Any global variables that have been defined are displayed here as well, along with their values. If the user clicks on the cell, that cell will be displayed in the text box regardless of the mouse position. Clicking on it again unlocks it and clicking on a different one unlocks the old one and locks the new one.
Since most of a cell's information is displayed graphically, this is mostly useful for finding the coordinates of a given cell. It will also display the name of the robot occupying a cell (if any), solving the problem of robot identification. However, much of the information useful for debugging--robot variables and the number of beepers a robot has--are not displayed. Therefore, we also allow the user to get information about a particular robot. If the user holds down the shift key while moving the mouse over a cell, information about the robot in that cell (if any) is displayed instead of the information on the cell itself. This robot information includes the name, location and type of the robot, plus the number of beepers it holds and a list of all variables, both global and robot-level. Clicking acts the same for robots as for cells.
The information in the info box is always up to date. If the user is viewing a robot or cell and it changes, the info box will update automatically. This is discussed in more detail in the next section. Additionally, if the user is not viewing any object, the info box displays some short instructions on how to use the feature. One of the problems turned up by usability testing is that the function of the info box is not immediately apparent and holding shift to look at robots is downright obscure. The instructions should solve the problem and they do it using space in the interface that is otherwise vacant. We also colored the info box similar to the world in order to link the two together visually.
Internally, this was one of the most troublesome features to implement. The main reason is simply that we're dealing directly with the user. The user is often the least predictable element in an application. Another reason is that RobotlCanvas can generate a large number of mouse movement events as the mouse moves over the grid and this can happen while a program is being executed. Consequently, the code that handles these events must be very efficient. First of all, even if the mouse is over the RobotlCanvas component, it may not be in the grid. The number of pixels along one axis of the component often won't divide evenly by the number of grid cells. In this case, a rounding error is accepted and the grid doesn't fill all of the available space. When the mouse is in this portion, the event isn't even sent to RobotlApplet.
Another situation when we don't want to do anything is when the mouse moves without moving into a new cell. As soon as RobotlApplet is notified of the mouse movement, it checks the mouse's last known location in grid coordinates. If the mouse is in the same cell, it returns without updating anything. This much could be done by RobotlCanvas with few modifications, but there's more. There are five states this system can be in: looking at a cell, looking at a robot, locked on a cell, locked on a robot, and off. The user can shift among any of the first four states arbitrarily. We haven't discovered any way to detect when the shift key is pressed, so the user could, for instance, be looking at a robot, release shift and click on the cell. This would jump straight from looking at a robot to being locked on a cell. And of course the user might do something silly like shift-click on a cell with no robot. The considerable number of cases to be handled was constantly at war with the need for efficiency in this feature.
Finally, whenever the state of the currently viewed object changes, the information in the box may need to be updated. This part isn't as speed-critical, but it can have a negative effect on the interface if it's not implemented carefully. Every time the string in a text box changes, the box blinks perceptibly (some VMs are worse than others). If the info box were updated every time anything changed, this would develop into a perceptible flicker. For this reason--and just on general principles--we only want to update the text box when we know that the text is different. Whenever an object changes, it requests an update, which only occurs if the user is looking at that object (be it a cell or robot). The only catch is that we have to be sure we call this every time something significant changes, but this was not very difficult to test and verify.
The cell and robot info displays, combined with the stepping and related features combine to form our debugging system. The only feature that this debugging scheme obviously lacks is the ability to set breakpoints. Unfortunately, the addition of breakpoints would be a significant undertaking, mostly in terms of adding them to the interface. Given the small size of the programs that will be executed by our interpreter, we don't feel that breakpoints are very important for RoBOTL and almost certainly not worth the amount of effort required.
With the addition of the mouse-based feedback, users have everything they need to build, run and examine RoBOTL programs. Except, of course, knowledge of RoBOTL. Part of our target audience is people who would use this on their own, without supervision or guidance. Therefore, we have always planned on including a tutorial with the product, one way or another. This was originally the main purpose of recruiting Pia to do a concurrent MQP. In the end, we implemented two related features to act as online support for the RoBOTL language. One is the tutorial and the other is a set of example programs that can be loaded by the user to examine, run and modify.
The two features have very similar interfaces, although the tutorial is more complex. When the applet loads up, two of the menus on the menu bar are "Examples" and "Tutorial". The Examples menu contains a list of all of the example programs that are available. Selecting one of these menu items will simply load the program into the code box. All this does is copy the text of the predefined program in, so it can be edited just as any other program could.
In addition, there's a menu item at the top called "Browse...". When this item is selected, a new window appears (it's effectively a non-modal dialog box). This window has a scrollable list of all of the examples and a text box on the right which displays a short description of the one that's currently selected. The user can choose to load the current selection by pressing return, double-clicking on it or clicking a button in the lower right. When one of these things happens, the code is loaded into the code box and the main window moves to the foreground.
The tutorial feature looks almost exactly the same in terms of the menu and the dialog box. However, selecting a module of the tutorial (from the menu or the list) doesn't load any code--it brings up another window with the text of that module in it. This text should lead the user through implementing some concept in RoBOTL. The interpreter window is still available, so the user can work with that while referring to the tutorial. Each module will also have some code associated with it, which demonstrates the featured idea. A button in the module window allows the user to pop up another window with that code in it. If the user wants to experiment with the code, it can also be loaded directly into the code box. Finally, there are "Next" and "Previous" buttons to move to adjacent modules in the tutorial without going back to the tutorial browser.
The tutorial has one additional feature. In the Tutorial menu there's an item under "Browse..." labeled "Index...". This will bring up another window just like the two "Browse..." windows. The list in the index window lists keywords and concepts from the tutorial. Choosing one of the items sends the user to the tutorial module that deals with it.
A couple of screen shots of the support features can be found attached to the end of this document. One is the browser window for the example programs and the other is a window to display a single tutorial module. A diagram of how all of the windows relate from the user's perspective can be found in Figure 1. The labels represent the actions necessary to trigger the appearance of the target window.
Of all the classes in the interpreter, only the support windows form a real class hierarchy, shown in Figure 2. The parent is, of course, java.awt.Frame, part of the Java AWT package. Frame itself is never used in the applet. Derived from Frame is RobotlFrame, the parent of all of the windows that are instantiated. The main interface window is a RobotlFrame, as is the window that the tutorial uses to display a piece of code.
RobotlFrame provides only a few basic services and sets the structure of our windows. A RobotlFrame has a single private field called supervisor; in our case, the supervisor is always a reference to the frame that created it. This supervisor is of type ElJefe ("the boss" in Spanish), an interface that requires only two methods. The most important one is killFrame(RobotlFrame), which a RobotlFrame uses to inform its supervisor that the window is closing. The parameter is the window that is closing, or "this".
This is needed because in Java, windows don't close on their own. When the user clicks on the close box, a WINDOW_DESTROY event is generated. A RobotlFrame catches this event, uses killFrame to inform its supervisor that it is closing and, finally, closes. The supervisor needs to know that the frame has closed, because it has to drop any reference it has to the frame object. Otherwise, the garbage collector wouldn't be able to dispose of the frame and it wouldn't disappear.
Using this method, any object that wishes to open and manage a child window must implement ElJefe and its two methods. When killFrame is called, it should drop its reference to the frame that is passed to it. Also remember that a subordinate window has a reference to its supervisor. So if the supervisor closes, the subordinate must drop that reference. Therefore, before a frame closes, it must close all of its subordinates as well. The other method in ElJefe, which has not been mentioned yet, is action(Event, Object). This is actually only needed so that the main interface window and the tutorial's code viewing window (both of type RobotlFrame) can pass action events to their supervisors (the RobotlApplet and a ModuleFrame, respectively). All other currently implemented RobotlFrames handle their own actions.
With very little code, RobotlFrame dictates the relationships between all of the windows in the applet. Of course, it doesn't provide any means for creating these subordinate windows, as this is very window-specific. Two classes are derived from RobotlFrame, adding more specific functionality. SupportFrame is an abstract class with a single abstract method: useSelection(). SupportFrame represents the frame that the user sees when they choose "Browse..." from either the Examples or Tutorial menu. When the user acknowledges the selected item in the list by clicking on the button, hitting return, etc., useSelection() is called. This method must be overridden in a subclass to define some action to take.
In the case of ExamplesFrame, the action is simply to load the code associated with the selected item into the code box. TutorialFrame is more complicated, however, and its implementation of useSelection() creates or activates a ModuleFrame, the second subclass of RobotlFrame. In addition to overriding useSelection(), TutorialFrame has a few methods to navigate the modules in the tutorial. A ModuleFrame doesn't keep a reference to the complete list of modules, so when the user clicks on the Previous or Next buttons in a ModuleFrame, it sends a message to its supervisor (a TutorialFrame) asking for the previous or next module. This way, the TutorialFrame always knows which module the user is looking at and can update its own display. The third SupportFrame, IndexFrame, is just as simple as ExamplesFrame. Each item in the list has a tutorial module associated with it. When the user chooses an item, the IndexFrame asks the applet (its supervisor) to load the associated module, as if the user had chosen it from the menu.
Since every RobotlFrame can have only one supervisor, the window structure is rather strongly enforced. For instance, in Figure 1, you will notice a thin line from RobotlApplet to ModuleFrame. This is only how it appears to the user; they choose a module from the menu and the module appears, without the TutorialFrame. What actually happens is that RobotlApplet creates a TutorialFrame, but tells it to remain hidden. RobotlApplet then instructs the TutorialFrame to display the chosen module. This way, the chain of command is preserved, despite appearances.
A lot of time was spent on pretty-printing because it is so well suited to this project and, frankly, because it's an interesting problem. Beginning programmers are likely to encounter a lot of parser errors as they learn the syntax; this feature would make it easier for the user to identify and fix these errors. Some benefit would also be gained simply by making the code more readable. The challenge is to format the code in the text box before it is parsed. Unfortunately, formatting the code itself requires some amount of parse information. Just how much wasn't known until it was attempted.
The first attempt was to implement some rudimentary pretty-printing by scanning through the raw text of the code itself. The only thing done in that algorithm was to watch for braces and indent the lines accordingly. However, RoBOTL does not require braces around groups of statements. As in C, a single statement can be placed under a conditional or loop without the braces. So while this approach worked adequately for statements contained in braces, the implicit indentations were missed altogether. This first attempt was really just to get acquainted with the problem and we already had another approach ready to go.
In the second attempt, the token manager generated by JavaCC was used. Tokens were retrieved one at a time and recreated the entire text of the code based on them. By default, each token had a space before it, but no newline. However, each token could override these defaults, forcing a newline or suppressing the space. For instance, a brace should have a newline before it and a semicolon should never be preceded by a space. In addition, every token had a chance to change the defaults for the next token in line. Again, a brace must have a newline after it and a left parenthesis should never have a space after it.
This approach worked very well for most situations. Since we were dealing with the tokens, it was possible to keep track of parentheses and semicolons to identify the implicit indentations. For most RoBOTL programs, this scheme lacked only one thing: preservation of newlines. This is only a minor flaw, however, and could be fixed by having the token manager take note of double newlines. Unfortunately, there are two things which are not dealt with by this algorithm: else and do-while. Both of these simply require the services of a real parser; the system of tracking braces and parentheses is not adequate. Each else needs to be matched with its if and each while might be either a true while or the end of a do-while. Even if we could account for these cases in this system, we would be so close to having written a parser that we might as well use our existing one.
The problem is that one needs both the parse information and the complete token stream. We would prefer not to recreate the code from the abstract syntax tree for a number of reasons. First, our interpreter supports comments and these are ignored by the parser. Second, it means that the program would already have been parsed, so it would be of no use to the user in finding parse errors. The token-based system doesn't even notice parse errors; the text is just formatted strangely, indicating that something is wrong. Finally, braces and parentheses are not preserved through the parse. The user could have used an unlimited number of combinations of braces and parentheses to produce a given AST.
None of these problems are fatal. One could easily decide where braces and parentheses did and did not belong, although we'd rather not contradict the user in their use of these characters. Alternatively, we could add the needed information to the abstract syntax tree, although it would expand the tree. Comments might also be added to the tree, with some difficulty. And even if we could only do the formatting after the parsing had completed, it would still be a worthwhile feature.
Three other possibilities have been suggested to combine the needed parse information with the needed token information. One is to have the pretty-printer call pieces of the parser as it needs them. We believe that individual productions of the parser can be used and this would give us enough information to create the formatted code. Another possibility is to somehow match up the abstract syntax tree with the token stream. This could probably be done accurately and would yield all of the required information. Finally, it might be possible to have the parser itself build the string, just as it builds the tree. We're not sure how difficult this would be, but it may be the most efficient way to do it.
The first menu added to the main interface window was called "Options," which allows the user to customize certain aspects of the applet. There was one option that was envisioned from the beginning and others have been added since. It was mentioned earlier that every time a robot's appearance changed on the screen, execution was paused for a set amount of time. This time can be changed in a submenu of the Options menu called Delay. The delay can be set to 0, 50, 100, 250, 500 or 1000 milliseconds, with 250 being the default. This can be changed at any time.
The next option was added to the applet toward the end: Colors. Usability testing showed that the original color scheme was not universally agreeable. Pia did some research on colors and we put together a number of different color schemes that could be used. These are listed in a submenu and the user can switch among them at any time. A color scheme contains five colors: the grid background, the robot, the walls, the beepers and the grid and robot information text box.
The remaining three options are simple toggles. First of all, we added sound effects to a few events in the applet (such as a parse error). Usability testing suggested that sounds should be very common. However, the "Play sounds" item in the Options menu allows the user to disable and enable the sound effects. Sound is enabled by default.
The next option takes advantage of some of the features we implemented for stepping through a program. Whenever the program is paused, the line of code that will be executed next is highlighted in the text box. A one-line description of the instruction is displayed below the buttons. Selecting the "Show debug info" option causes this information to be displayed during normal execution as well. This option is off by default.
Finally, although pretty-printing is not complete, it only fails in certain obscure situations. These cases will not be encountered very often, especially by beginning programmers. Also, if the pretty-printer does fail, the parse will not be affected; the code will simply look a little strange. Therefore, pretty-printing is included as an option, although it is off by default. When it is turned on, a warning is displayed informing the user of the small risk of failure and that the function of their program should never be affected.
Early in the project, we were concerned that the applet we were planning would be too ambitious for the current state of Java. Along the way, we did indeed encounter a number of Java features that were implemented inconsistently or improperly in some virtual machines. A few examples are listed below:
Many of the problems we encounter are simple VM bugs, as above. The only thing we can do about these is to report them to the software manufacturer and either find a workaround or document the problem. However, one other problem we have faced is simply one of inconsistent implementation. When an event is generated, it takes the form of an object of type Event. One field of Event (called arg) is of type Object, meaning that an object of any class can be assigned to it.
When a menu item generates an event, arg should be a String object representing the text of the menu item. However, when a toggle-type menu item generates an event under Microsoft's virtual machine, arg is of type Boolean, representing the state of the toggle. Fortunately, the data in the arg field can always be obtained elsewhere, so we were able to program around it. Still, this inconsistency effectively renders the arg field useless, since its contents are not dependable.
Overall, we are very pleased with the results of this project. When it was originally being planned, such features as stepping through a program and getting detailed information about the grid and robots were merely tentative. The tutorial and example programs weren't even conceived of, at least in their final form. We definitely exceeded our own expectations and believe that the applet is fit to be made public. Even so, there are a few things that could be added to it in the future.
There were a couple of things that we were not able to do because of the current state of Java. For instance, we mentioned that there was no apparent way for our applet to know when the shift key had been pressed. Modifier keys don't seem to generate events; their state can only be determined in reference to another event. The only real implication this has for the user is that if they change the state of the shift key, they must move the mouse at least one pixel before the change will be registered.
Another lack in Java 1.0 is shortcut keys for menu items. We had originally planned to put the control functions (run, step, kill, etc.) in a menu with keyboard equivalents to make them easier to access. Since keyboard shortcuts are not available in Java 1.0, the menu was not useful and was discarded. If this applet were to be upgraded using Java 1.1, one of the first things that should be done is to add this menu.
Perhaps the most unfortunate restriction that Java placed on us has to do with text boxes. On many platforms, with many VMs, text boxes in Java do not wrap text. Some VMs, however, do. We actually would like both, wrapping for the text in the tutorial, for instance, and non-wrapping for the code. We believe that Java 1.1 provides this choice, but most current browsers do not support version 1.1. As soon as they do, the text boxes in the applet should be explicitly specified as wrapping or non-wrapping.
There are also a couple of features that could have been implemented now, but weren't. For instance, at present, when the user clicks on the grid to select a cell for feedback, the cell is immediately selected at the time of the mouse-down event. Most systems use a more complex method whereby the action is considered to take place when the mouse is released. In our case, that would mean that the user could click on a cell and hold the mouse down as they moved around the grid. When the mouse was released, the cell they were currently pointing at would be selected. The main reason this was not done is that it's not entirely clear that users would find it more comfortable. Selecting on mouse-down is simple and direct and should not cause any confusion, even if it lacks a degree of polish. The more complex method might be investigated in the future to determine whether it would in fact be more usable.
A more important feature that could be implemented is context-based help for the buttons. Every project with a deadline has a few features that don't make it in and this is one of ours. The idea is simply to pop up a short help message for each of the buttons in the interface. A good deal of debate went into the naming and arrangement of the buttons and because of it we ended up with a fairly well thought-out system. Most of the buttons are also described in the online documentation that is part of the example programs and tutorial. Context-based help for the buttons would be the final touch to our built-in help systems.
Finally, one area that did not get much attention is the error messages for parse errors. These are generated by JavaCC, but they can be changed. One thing we did do is to highlight the line of an error when it occurs. However, the errors can still be obscure, especially to a beginning programmer. One thing that might be done is to watch for common mistakes such as missing semicolons and generate special error messages for those. Beyond those few special cases, the wording of the error messages could probably be improved to be more friendly and descriptive. They should make the user realize that parse errors are common and are usually easy to correct.
This applet contains a number of features that one might want to expand in the future. We have tried to make it as easy as possible for someone to do this without a great deal of knowledge about the code. The most general thing we did is to comment the code fully with JavaDoc-style comments. These comments should provide a complete HTML reference guide to the source. This will be useful to anyone wanting to make any changes, but in this appendix we are also including instructions on the most likely changes that someone will wish to make to our applet.
This is one of the easiest things to add, as the only thing to be changed is the menu. Most of the time, when the user chooses a menu item, the applet identifies the item by name. In this case, any menu item that ends with the string "milliseconds" will be assumed to be under the Delay menu. All of the characters before the first space of the menu's text is assumed to be a number indicating the delay time. This number is parsed by the Integer class and used as the new delay. Therefore, all that is required to add a new delay is to add a menu item that starts with a number and ends with "milliseconds". All of the menus, including Delay, are set up in RobotlApplet.init().
Adding a sound is almost as easy as adding a delay. All one has to do is to find the location in the code where it should be played and then make sure there is a reference to the RobotlApplet there. The most important classes keep references to the applet object. If an object needs to send a message to the applet, but doesn't have a reference to it, there is a wrapper in some other class. For instance, the Robot class sends a number of messages to RobotlApplet through RobotWorld. Once you've found the place, you just have to make a call to the playSound(String, boolean) method of RobotlApplet. The String is the name of the sound file on the server. If the boolean is true, then the applet will only play the sound if the user has sounds enabled. To force a sound to play, just pass false as the second argument.
Java is rather picky about the sounds that it will play. Through some experimentation, we found a format that it likes. The sounds that we use are Sun audio files (.au) with u-law encoding, 8 kHz and 16-bit mono sampling. Some of these parameters might be able to be changed without disabling the sound, but we're not sure which ones.
The support features (examples and tutorial) get all of their information from the server in the form of text files. When the applet starts up, it retrieves three of these files to build the menus and associated data structures. Tutorial information is in "tutorial.ind", examples in "examples.ind" and the tutorial index in "index.ind". These files must be in the same directory that the applet is in. A .ind file for a tutorial with two entries might look like the following:
Module 1 tutorial/mod1.rob,tutorial/mod1.txt This is the first module. Module 2 tutorial/mod2.rob,tutorial/mod2.txt This is the second module. Line 2 of the second module's description.
The first line of each entry is the name. Internally, the entries are stored in a hashtable with the name as the key. It is important that no two names are the same. The second line contains two file names. The comma and the second file name are optional. For tutorial.ind, the first name refers to the file with the associated code and the second name refers to the file with the text of the tutorial. examples.ind contains only one file name, which refers to the file with the example code in it. index.ind is a little different. An entry in the index doesn't refer to any files, but it does refer to a module. So one of the entries in index.ind might have "Module 1" on its second line. After the second line, the file may contain any number of lines for the description. This description will appear in the box next to the list in the "Browse..." window.
Notice that path information may be included with a file name. By convention, we place all of the example code files in a sub-directory called "examples" under the applet's main directory. Tutorial files go in "tutorial." The only files that must be in a particular place are the three .ind files.
Finally, someone may want to add or remove a color scheme to the applet. There are only three steps to this procedure. First, the new set of colors must be defined. In RobotlApplet, there is a two-dimensional array called colors. Each sub-array contains a list of five objects of the Color class. In order, the Colors are for the walls, beepers, world background, robots and the grid/robot information text box. Any element can be either a predefined Color (such as Color.black) or a new one created for the array (new Color(r, g, b)). The three values passed to the Color constructor are for the red, green and black components of the color. Each one is a value from 0 to 255. For maximum compatibility, we have restricted ourselves to "Web colors" using the values 0, 51, 102, 153, 204 and 255 (or, in hex, 0, 33, 66, 99, cc, ff). To add the color scheme, simply add another sub-array to the definition of colors with the five desired Color objects in it.
The second step is to give your color scheme a name. Right below the colors array is a set of constants naming the colors. The integer of each constant is the number of the sub-array with the associated colors. Since you added a sub-array to the bottom of the list, add a constant to the end with the next consecutive number.
Finally, you need to add the color scheme to the menu. The Colors menu works differently from the others. Each item in the Colors menu is actually of a subclass of MenuItem. The constructor of class ColorItem takes an integer which represents the color scheme associated with that menu item. In RobotlApplet.init(), find the place where the color menu is created and add another line just like the others. You can add the item anywhere in the list of colors. The code will take the form:
colorMenu.add(new ColorItem("Name", SCHEME));
"Name" is the label that will appear in the menu and SCHEME is the constant that you just defined.
Key:
----
[] = 0 or 1 (regexp = ()?)
{} = 0 or more (regexp = ()*)
<> = 1 or more (regexp = ()+)
Program -> [Declaration] Execution
/* World & Robot Declaration Section */
Declaration -> Define "{" [DMS_State] {DecState} "}"
DMS_State -> DMS Expression ";"
DecState -> WE_State | NRT_State | DGI_State
WE_State -> WorldEntity Name "{" {WE_Inst} "}"
WE_Inst -> Beeper_Inst | Block_Inst | Wall_Inst
Beeper_Inst -> Beeper At Coords ["=" Expression] ";"
Block_Inst -> Block At Coords ";"
Wall_Inst -> Wall From Coords Direction For Expression ";"
NRT_State -> NRT Name "{" IsLikeA Name ";" {NRT_Inst} "}"
NRT_Inst -> DNI_Inst | DIB_Inst | DI_Inst
DNI_Inst -> DNI Name As Instructions
DIB_Inst -> DIB Expression ";"
DI_Inst -> DI Name ["=" Expression] ";"
DGI_State -> DGI Name ["=" Expression] ";"
Coords -> Expression "," Expression
Direction -> North | East | West | South
/* Robot Execution Section (Statements) */
Execution -> Execute "{" {Statements} "}"
Statements -> Statement | "{" {Statements} "}"
Statement -> NewState | TellState | IterateState | PlaceState | RemoveState | AssignState | TurnonState | TurnoffState | IfState | WhileState | DoWhileState
NewState -> New Name Name [At Coords] ";"
TellState -> Tell Name ":" Instructions
IterateState -> Iterate Expression Times Statements
PlaceState -> Place Name [At Coords] ";"
RemoveState -> Remove Name ";"
AssignState -> Name "=" Expression ";"
TurnonState -> TurnOn All ";"
TurnoffState -> TurnOff All ";"
IfState -> If "(" Expression ")" Statements [Else Statements]
WhileState -> While Expression Statements
DoWhileState -> Do Statements While "(" Expression ")" ";"
/* Robot Execution Section (Instructions) */
Instructions -> Instruction | "{" {Instructions} "}"
Instruction -> MoveInst | AssignUserInst | IterateInst | IfInst | WhileInst | DoWhileInst | SimpleInst
SimpleInst -> TurnOn ";" | TurnOff ";" | PutBeep ";" | PickBeep ";" | TurnLeft ";"
MoveInst -> Move Expression ";"
AssignUserInst -> Name ( AssignInst | UserInst )
AssignInst -> "=" Expression ";"
UserInst -> ";"
IterateInst -> Iterate Expression Times Instructions
IfInst -> If "(" Expression ")" Instructions [Else Instructions]
WhileInst -> While Expression Instructions
DoWhileInst -> Do Instructions While "(" Expression ")" ";"
/* Expression Grammar */
Expression -> Exp1 {Or Exp1}
Exp1 -> Exp2 {And Exp2}
Exp2 -> Exp3 {RelOp Exp3}
Exp3 -> Exp4 {LtGt Exp4}
Exp4 -> Exp5 {AddOp Exp5}
Exp5 -> Exp6 {MulOp Exp6}
Exp6 -> Not Value | AddOp Value | Value
Value -> IntegerFunc | BoolFunc | "(" Expression ")" | Number | Name
IntegerFunc -> BeepersInBag | BeepersOnFloor | XPosition | YPosition | MapSize
BoolFunc -> FrontIsClear | LeftIsClear | RightIsClear | FacingNorth | FacingSouth | FacingEast | FacingWest
/* Basic Tokens - Case Insensitive */
Number ->
Name -> Letter {Digit | Letter | "_"}
Letter -> "A-Z" | "a-z"
Digit -> "0-9"
TurnOff -> "turnoff"
TurnOn -> "turnon"
All -> "all"
Define -> "define"
Size -> "size"
WorldEntity -> "worldentity"
Beeper -> "beeper"
At -> "at"
Block -> "block"
Wall -> "wall"
From -> "From"
For -> "for"
North -> "north"
South -> "south"
East -> "east"
West -> "west"
NRT -> "newrobottype"
IsLikeA -> "islikea"
As -> "as"
DNI -> "definenewinstruction"
Execute -> "execute"
DI -> "defineinteger"
DIB -> "defineinitialbeepers"
DMS -> "definemapsize"
DGI -> "defineglobalinteger"
Tell -> "tell"
New -> "new"
Iterate -> "iterate"
Times -> "times"
Place -> "place"
Remove -> "remove"
If -> "if"
Else -> "else"
While -> "while"
Do -> "do"
Move -> "move"
TurnLeft -> "turnleft"
PickBeep "pickbeeper"
PutBeep -> "putbeeper"
Not -> "not" | "!"
BeepersInBag -> "beepersinbag"
BeepersOnFloor -> "beepersonfloor"
XPosition -> "xposition"
YPosition -> "yposition"
FrontIsClear -> "frontisclear"
LeftIsClear -> "leftisclear"
RightIsClear -> "rightisclear"
FacingNorth -> "facingnorth"
FacingSouth -> "facingsouth"
FacingEast -> "facingeast"
FacingWest -> "facingwest"
Or -> "or" | "||"
And -> "and" | "&&"
RelOp -> "!=" | "=="
LtGt -> ">" | "<" | ">=" | "<="
AddOp -> "+" | "-"
MulOp -> "*" | "/"
www.robotl.com
All current work on this project can be found here, including the applet, the reference guide and the tutorial.
Flannagan, David. Java in a Nutshell, Second Edition. Sebastopol, CA: O'Reilly & Associates, 1997.
Fischer, Charles N.; LeBlanc, Richard J. Jr. Crafting a Compiler. Menlo Park, CA: The Benjamin/Cummings Publishing Company, Inc., 1988.
JavaCC
Sun's JavaCC site.
Frontiers
The Frontiers site, from which one can find information on JavaBOTL.
Scheme Interpreter in Java (MQP). David Bishop, Edward Hallissey, Michael Gennert (advisor).