Computer Science Honours Industry Project
Lisp Interpreter in Java

Click here for a sample!

Supervisors:

• Ann Nicholson
• Lloyd Allison

Table of Contents

• Introduction
• User Manual
• Text Interface
• Graphical Interface
• Interpreter Window
• List Display Window
• Input Only Window
• Single input/output area interface
• Interpreter Module
• Methodology
• Text Interface
• Graphical Interface
• Interpreter Module
• Lexical Analyzer
• Parser
• Storage Tables
• Code Evaluator
• Possible Future Improvements
• Bibliography

Acknowledgments:

I would like to thank my project supervisors Ann Nicholson and Lloyd Allison as well as my fellow student David Golshevsky for their invaluable help.

Introduction

Lisp programming language is one of the main tools used in artificial intelligence. Being a flexible and sophisticated language, it is often available in packages that are engineered to be as efficient and powerful as possible, often assuming the knowledge of the language and the particular package to be of a lesser importance. The Lisp interpreter written for this project is a package that while offering a reasonable functionality, has a primary goal of being a Lisp teaching tool. This is achieved by integrating such interpreter into the most common hypertext environment available - World Wide Web HTML. The implementation is done in the World Wide Web friendly Java language. The project can be subdivided into two major sections: the interface and the interpreter itself.

Two type of interfaces have been developed. There is a simple text interface that is executable within a text shell, and a GUI interface that can be run as a standalone window or integrated within a World Wide Web browser environment as an applet. The interpreter is interface independent and accepts string commands as input and outputs results to an output stream. The interpreter's capabilities of handling Lisp data types and commands matches the syllabus covered in the CSC2940/CSC3940 "Lisp Programming" subject and hopefully, it will be used within the subject as a learning aid.

The first section of this report is a user manual to the package. The second section goes into the technicalities of the implementation. Finally, possibilities of the future improvements on the package is discussed.

User Manual

This section concentrates on the usage of the two user interfaces provided as well as the dealing with the interpreter itself. From now on, term "interpreter" will refer to the program module that accepts a command as a string and after processing, produces an string outcome in the form of a result or an appropriate error message. The term "interface" will refer to the module the user manipulates in order to get the Lisp commands to the interpreter, while the interpreter uses it to communicate its output.

There are two interfaces provided to the interpreter.

Text Interface

The text interface is available in a stand-alone mode only and it is invoked in a shell by "java TextLisp" command. Lisp commands are entered at the " > " prompt. The interface will not pass the command to the interpreter until all opened brackets are matched by the closed brackets. In the case of missing closing brackets, the interpreter awaits completion of the command on the following line which no longer has the " > " prompt in front.

The returning value of the command is preceded by a ":" on the following line. Error messages and the output of Lisp printing functions is displayed without a prompt preceding them. Command "quit" (in both upper and lower case) is a special command that causes end of the program.

Graphical Interface

This user interface provides more flexibility. This interface is loaded by executing "java Klisp" command for the stand-alone mode or can be loaded off a web page in a more integrated environment. An example of the web page using the integrated interface is available here The integrated interface is made up of 3 major windows: the browser window, the interpreter window and the list displaying window. Each one will be discussed in further detail.

The interpreter window is separated into 3 vertical sections: the button panel, the program code editable window and the output/message not-editable window. The buttons allow execution of clearing the both text windows ("cLear"), running the code in the input window ("Run"), showing or hiding list display window (a button with a changing "Show List Display Window" / "Hide List Display Window" label) as well as clearing the variable table ("Clear Var") and user defined table ("Clear Funct"). Clearing, running and showing/hiding the list display can also be performed by typing in the input window ctrl-l, ctrl-r, ctrl-q and ctrl-q respectively (as long as the keyboard control keys has been configured properly for Java). Usage of ctrl-c for clearing has been avoided due to clashes with Windows copy-to-clipboard command shortcut.

The top text area window is used as an editor for the Lisp commands. The code can be executed full in its original sequence or single bits can be selected and executed one at a time. After choosing program execution action, either by pressing the "Run" button or by pressing ctrl-r, the interpreter will evaluate the selected text, or if none is available, the full contents of the input window.

The output window is not editable and has no special control key sequences. Every code evaluation results in the output window displaying the "Running…" message, followed by interpreter's output.

The stand-alone version of the interpreter window differs from the integrated set-up due to the existence of quitting capability. In the integrated mode, the window is removed only when another page is selected in the browser. In stand-alone mode, quitting either by pressing the additionally provided "Quit" button, pressing ctrl-q or destroying the window via the window manager functions brings the user back to the outer shell.

List display window is a graphical representation of results generated by the user Lisp code. When the window is showing, all output is displayed in both the interpreter window (text form) and in the list display window (graphical form for lists, text for not linked atoms). If a list display window list node contents is clipped due to being too long for the display grid size, it can be displayed in full by clicking on the appropriate list node. The list display can be cleared by pressing the "Clear" button. Once the display grid overfills, no more output will be added until the display is cleared. "Enlarge" and "Reduce" buttons change the magnitude of the size of the output in the list display window.

The lists are displayed across the window up to the end of the list symbol, with their node values inside them. If the node value is a list itself, this sublist is linked to it on its own separate line below. A null list is represented as a link with end of link symbol within its node. Atoms that are not within list nodes are not put into node boxes to avoid confusion with single element lists.

The integrated page setup has another component, an input only applet that is embedded within the web page on the browser. While the browser displays some command description as text, this window displays sample code that can be executed in the evoked interpreter window at a press of the "Run" button. There can be multiple instances of such applet embedded within a single page.

This type of interface mimics the text only interface, but in a graphical window. Such GUI lacks originality compared to the text interface and also lacks useful command editing functions as described for the previously mentioned graphical interface. Since these shortcomings have been taken care of in another GUI model, this model was abandoned.

Interpreter Module

The interpreter is capable of handling simple Lisp data types such as numbers, strings, boolean true and nil (representing both a null list and a boolean false), as well as more complex data types that are lists, dotted pairs and property lists.

Functions implemented are described below. Both the first name and the optional name in brackets are valid function names. All function parameters are evaluated unless specified.

Methodology

Both the interpreter module and the interface modules work as separate and independent units. The only thing in common is communication, that is the passing of the string commands to be evaluated by the interpreter, and the output or exception handling to be performed by the interface on the interpreter's behalf. Hence, the implementation of interfaces and the interpreter can be described separately. All names in italics represent Java classes which's code is included in the appendix.

Text Interface

This simple interface is implemented with the use of the TextKlisp class. It polls awaiting input commands from the user until "quit" command is typed in. The "quit" command is filtered out by the interface, not the interpreter. Every other command line is scanned for the number of opening and closing brackets, and if closing brackets are outnumbered, the next command line is attached on top of the original one the result checked again. The interface uses standard input and output streams.

Graphical Interface

The interpreter window is made up of a button panel and two text areas. The bottom, message area is implemented with the use of Java's TextArea class that is set to non-editable mode. The top, input area is implemented with a CtrlTextArea class that is capable of delivering Java events (indications of a change) whenever ctrl-l, ctrl-r, ctrl-q or ctrl-s are pressed. Pressing of the top panel buttons also generates events resulting in the same actions.

The list display window makes use of the ListDisplay class that controls a Canvas and two ScrollBar classes to give an impression of a scrollable Canvas. Besides the scrollbar position update, the class also handles the scrollbar size changes that are a consequence of resizing of the window. The list node pictures are stored in an virtual grid, where a link list helps to determine where each not empty node points to. To avoid list clashes, each sublist owns a whole grid row. Magnifying and reducing is done via grid and font size manipulation.

The input only applet embedded within a web page is implemented by the InputApplet class. Activating the button passes the contents of the input TextArea to the interpreter window. This one way communication is done via the AppletComms class which is made up of a static reference to the interpreter, as well as and a function that creates the interpreter window if called the for first time, and returns the reference to the already created interpreter window after that.

Lisp code can be initially passed to the applet text window when the web page loads. This is done by specifying an input parameter with the use of " < PARAM > " HTML tag. Similarly, a text library file URL, with Lisp code declerations inside it can be specified the same way, eg:

< APPLET code="InputApplet.class" width=300 height=170 archive="Klisp.jar" >
< PARAM  name="libraryFile" value="standard.lib">
< PARAM  name="inputText" value=
"(defun recursive_length (L)                    @
   (cond ((null L) 0)                           @
          (t (+ 1 (recursive_length             @
          (cdr L)))))                           @
)                                               @
(setq length (recursive_length '(1 2 3 4 5 6))) @
" >
< /APPLET >

The "@" character indicates end of line, a precaution necessary as most browsers ignore new-line characters in a HTML document. The applet calculates its required text area size by the number of lines passed to it, though it will not go below a 1 row minimum size.

Interpreter Module

The interpreter has been divided into four sub-modules: lexical analysis, parsing, variable and function storage and code evaluation. The lexical analyzer separates the input stream into suitable tokens, the parser builds up a parse tree, the storage tables accumulate the current variables and functions and the code evaluator calculates output given the parse tree and the variable and function storage tables.

The lexical analyzer, implemented by Lexer class, divides a stream of characters into strings, numbers and other single characters. The lexical analyzer discards comments starting with character ";" and recognizes text within double quotes ("") as a single string.

The Parser class builds up a parse tree out of linked lists and atoms. It returns a linked list corresponding to given S expression's parse tree. Whenever a new sub-tree is encountered, the parser calls itself recursively, adding on to the current tree the returned sub-tree.

Each List command, also called an S expression, parse tree can be represented by a one way linked list. Every token within a set of brackets represents an element of a list (or a dotted pair, ignored for now), and every pair of brackets within represents another sub-list. For example, given S expression (defun plus10 (n) (+ n 10)) results are presented in a parse tree of Figure 1.

A one way linked list class Llist was written for this purpose, which besides a the normal lookup functions, is capable of both inserting elements at the head as well as appending them to the tail. Insertion at the head is useful in code evaluation and variable storage construction, while appending is necessary for the creation of the parse trees.

The parser receives a token from the lexical analyzer and determines it to be a number, string, opening or closing bracket, or other (illegal token causing an error). In the case of a number, equivalent double float is added on to the list. In the case of a string, the token is compared to a number of abbreviations corresponding to the mathematical boolean operations and in the case of a successful comparison, expended to their full string names, e.g. > = expends to gte (greater or equal to). The strings are then added to the list.

Encountering an open bracket indicates the need to create either a dotted pair (Pair object) or a new sublist (Llist node). A dotted pair is checked for the syntax: "(S expression #1 . S expression #2)", where both expressions can be dotted pairs, linked lists or simple data types. If a full stop follows the first object but the rest of the syntax does not match, a ParseException error is produced, otherwise, the structure is assumed to be a list. The list is parsed until a closed bracket is detected. If the stream ends without a corresponding closing bracket, the parse exception is thrown. Likewise, any additional unmatched opening brackets cause an exception. Due to Lisp's run time linking, the parser does not check whether a used variable or function name currently parsed exist in the variable or function tables.

Three tables were implemented for the use of variable and function storage. User defined and hard-coded functions are stored in separate HashTable class objects. For each user defined atom, all values of the current, and previous scopes' (so called shadowed values) as well as global properties of the atom are stored in an object of the EnvironmentTable class.

The first attempted implementation of the environment table involved a stack that adds a new scope region on top of the stack for every function call. Any variables to be shadowed in the function are placed within that region. Such scope boundary exists only within the function and is removed from the stack when the scope finishes. Whenever the variable is required, it is searched for from the top of the stack downwards. Reaching the bottom of the stack implies non-existence of the variable.

The advantage of the approach is the ease of creation and removal of boundary stacks. However, certain data types in Lisp, e.g. property lists, have global scoping and bind themselves to the symbols, not the variables. Therefore, each variable on the stack would need to keep a reference to its symbol's bindings. This problem is illustrated in Figure 2.

Such multiple references to a property list can be avoided with environment table implemented as a modification of a standard hash table (EnvironmentTable, displayed in Figure 3). Each table entry can be considered a list of nodes of atom's properties. The first, value node, holds a structure of values the atom has at the current and its outer scopes. The structure has last-one-in-first-one-out approach and is implemented with linked lists. This way, the current value lies at the head of the list and is quickly accessible. The environment table provides functions that can:

• start scope on a atom (create an entry if necessary), initializing it to a given value
• remove atom's scope (remove the entry if possible)
• check for atom's name existence in the variable table
• put in a static symbol property
• get a static symbol property

Although hash table implementation requires progressing through longer list, the overall data structure is of a smaller size and is therefore currently preferred to the single stack approach.

The other properties ignore scope changes, and therefore do not accumulate values. They are implemented as dotted pairs, where the head stores the property name, the tail the property value. These properties can only be entered and altered.

The functions are stored in standard hash tables provided by Java's HashTable class. The table with the hard-coded functions is initialized only once, and whenever a new function is created, its name is checked against the keys of this table. If the function name matches one of the key already there, an error is produced informing of the clash.

Function declaring Lisp function defun is capable of creation and insertion of a function, represented by LambdaFunction object, into the user defined function table. Such object is made up of a function parameter list and a function body. LambdaFunction class possesses a procedure that sets up these parameters before insertion to the table. Another procedure performs evaluation of the user function code and is executed when the user defined function is invoked in the interpreter. This procedure initially compares the number of local parameters set up with the number of parameters passed in, and if match, creates new scope for the local variables. Then the function body is evaluated by the interpreter, current scope of the local variables removed and result returned.

Existence of separate variable and function tables allows function declarations to be of the same names as atoms, as the code evaluator is capable of recognizing which one to look for given its placing in the parse tree. The separate hard-coded and user defined function tables makes it quicker to check whether a function can be redefined or not.

S expression can take the form of an atom, or a function call defined by a not-empty parse tree (a linked list). The interpreter evaluates a list of such S expressions, returning the result of the final one. Upon receiving a single user declared atom, it returns its value of the current scope. The predefined boolean true and Nil as well as numbers return themselves. Any list indicates a function call and the first string of the list is used as the key in the function hash table. Quote (') is a special function that does not need to be enclosed in a list with its parameters, and therefore is checked separately. Matching hard-coded function or user defined LambdaFunction is evaluated with the rest of the list as function parameters. Since most functions require parameter and/or other function of code evaluation via the interpreter, the reference to the interpreter object is also included in the function calls. Therefore, the evaluation process is recursive, with functions calling other functions via the interpreter to evaluate their sub-S expressions.

The interpreter evaluates all S expression presented to it by the parser in the following manner:

  EvaluateSexpression(ParseTree tree) {   // main function
      while tree.isNotEmpty
          switch (tree.currentElement)
              case predefined atom:           // nil, true or number
                  return tree.currentElement
              case linked list or a quote:            // another S expression
                  return EvaluateFunction(tree.currentElement)
              default:
                  // check if user defined atom
                  if tree.currentElement is a string and 
                      tree.currentElement exists in the variable table then
                      return atom's value stored in the variable table
                  else
                      must be an error,
                      produce exception indicating unknown atom

          tree.currentElement = tree.nextElement
  }

  EvaluateFunction(ParseTree tree) {
      if tree.currentElement exists in the function tables then
          function = FunctionTableEntryFor (tree.currentElement)
          return function.evaluate(tree.nextElement)
      }
  }

Every class of a function object inserted into the function tables inherits the Funct class and starts its name with term Funct (eg. Functcond). Funct class contains evaluate method that when given the rest of the parse tree and a reference to the interpreter works out the result, or throws a EvaluateException informing why the evaluation was unsuccessful.

All user defined LambdaFunct functions and some hard-coded functions, eg. mathematical operators, setting functions, do loops, have common abstract super classes which are still inherited from the Funct class. The members of each of such family of functions have so much in common, the bulk of the code is usually the same, with only one small function differentiating them from the other family members.

Possible Future Improvements

An interpreter will never be finished until all data types and commands are implemented. The current specifications of the package were imposed by the structure of the CSC2940/CSC3940 "Lisp Programming" subject and by no means claim to be complete. Also, the interfaces, while seemingly easy to learn and use, have never been tested in a learning environment, and until so, cannot be assumed to be the flawless. The package was only tested under Windows95 and Unix operating systems, with the use of Netscape browser only. It is possible that further testing would reveal certain undetected problems.

Bibliography

Harlequin FreeLisp
JavaByExample Lisp Interpreter
Java class descriptions

"ANSI Common Lisp", Graham, Paul Upper Saddle River, N.J. : Prentice Hall, c1996
"Common Lisp : a tutorial", Milner, Wendy L Englewood Cliffs, N.J. : Prentice Hall, c1988
"Common LISP : a gentle introduction to symbolic computation", Touretzky, David S Redwood City, Calif. : Benjamin/Cummings Pub., c1990
"COMMON LISP : the language", Steele, Guy Bedford, Mass. : Digital Press, c1990
"LISPcraft", Wilensky R.: University of California, Berkely, 1984
"Java in a Nutshell: a desktop quick reference for Java programmers", Flanagan, David Sebastopol, CA : O'Reilly ; Associates, Inc., 1996