Fourth Assignment: Implementing Lisp, part II
Dave Matuszek, Spring 2003

Purpose of the assignment:

The basic idea:

When you have completed this assignment, you will have written a complete (though admittedly small) programming language. In part I you implemented all the basic functions of Lisp as an API (Application Programmers Interface); now, in part II, you put them to work.

Lisp runs as a read-eval-print loop: read in an expression, evaluate it, print out the result. You have already written Sexpr.parse(String), which does most of the work reading in an expression (though we need to be sure it gets clean input), and Sexpr.toString(), which does the printing. Hence, the main focus of this assignment is on evaluating Lisp expressions.

Caveat: In what follows, I try to give you pretty detailed instructions on just how to go about writing your methods. The general approach is correct and very workable; but since it's been over a year since I've written a Lisp interpreter, I do not guarantee that the following is correct in every single detail. If you understand the general idea, any problems should become obvious as you write the program. I will give a small amount of extra credit for the first emailed report of each error, provided that: (1) you describe the problem clearly enough, (2) it is significant enough to publish to the class, and (3) it is in time to help other students.

Your assignment:

Add the following methods to your Lisp class:

public void defun(Sexpr)
Takes a function definition (represented as a Sexpr) and saves it in a HashMap for later use.

public Sexpr eval(Sexpr)
Evaluates the given Sexpr and returns the result.

public Sexpr cond(Sexpr)
Evaluates the given Sexpr (which is known to be a COND) and returns the result.

public void load()
Reads in Sexprs from a file and evaluates them, printing the results.

Evaluating a Lisp expression:

This requires some attention to detail, but is basically simple. To evaluate an atom, you look up its value in a table. To evaluate a function, you evaluate its arguments, then recursively evaluate the function with those arguments. There are a lot of cases, and I don't guarantee I haven't missed some--if you notice any, please let me know as soon as possible.

Your eval method should do this:

Recall that the arguments to a cond are pairs, that is, lists of two elements. The first element of each pair is a test, the second is a value. The cond evaluates tests (only) until it finds one that is true, then evaluates and returns the corresponding value.

Your cond method take as its argument a list of pairs, and should do this:

Your defun method saves away (in a HashMap instance variable of the Lisp class) a function definition for later use. Be sure to include the list of formal parameters as part of the definition; it will be needed. Defun should return a "true" value; I recommend returning an atom whose value is something like "foo defined.", where "foo" is the name of the function.

Keeping track of values:

When you call a function, its actual parameters are evaluated, and those values are assigned to the formal parameters of the function. In this simple version of Lisp, this is the only time that variables (the formal parameters) are assigned values. ("Full" Lisp has let, setq, and other mechanisms for assigning values to variables, but we don't have to worry about those.)

Within a function, the only variables that the function can access are its formal parameters. If the function is recursive, every recursive call has its own copies of those parameters. These copies need to be maintained on a Stack. However, since your eval method is recursive, Java is already keeping eval's local variables on a stack. This makes keeping track of variables and their values incredibly easy: Just define a local HashMap for your variables, and use the variable names (as Strings, not as Sexprs) as your key.

You may (or may not) find it desirable to write a function that takes two arguments, an expression and a HashMap of name/value pairs, and use this as a helper function for eval.

One extra thing to be aware of: The values T and NIL are always defined. Somewhere you need to make a special check for these "variables."


This is the boring part. Your Sexpr.parse(String) method expects a complete expression, and we may want to have an expression spread across several lines. Also, we need to get input from two places: From the keyboard (so that the user can interact with the program), and from a file (mostly to get function definitions).

Here's how you get input from the keyboard (this is copied from "Data Structures & Algorithms in Java, Second Edition" by Robert Lafore):

public static String getString() throws IOException {
    InputStreamReader isr = new InputStreamReader(;
    BufferedReader br = new BufferedReader(isr);
    String s = br.readLine();
    return s;

For each line you get, count parentheses; if there aren't enough closing parentheses, get another line. If there are too many closing parentheses, report an error. If/when you have the right number of parentheses, parse and evaluate the input.

Counting parentheses is simple. Start with a count of 0, and examine each character in the input. If it is '(', add one to the count; if it is ')', subtract one. Whenever the count is zero, parentheses are balanced.

You also need to implement a simplified version of Lisp's load function. This version takes no arguments, opens a dialog box to get a file, and reads and executes the contents of that file. For simplicity, we will assume that no input line contains parts of more than one S-expression. Hence, when you count parentheses,

I've provided a LineReader class to do the I/O for you: The constructor displays a dialog box and opens the file, the readLine() method reads a line, and you should call the close() method when you are done.


Any method that may detect an error should throw an Exception. For example:

public void load() throws IOException {
    throw new IOException("Too many parentheses!");

If you can find an existing Exception type that seems to be appropriate, use it; otherwise, you can use the generic Exception, or you can write your own subclass of Exception. (For example, NoSuchMethodException seems ideal for reporting a call to an undefined function.)

Your read-eval-print loop should catch any and all Exceptions, print the enclosed message, and keep going--with one exception (no pun intended). One of the possible IOExceptions is EOFException (in the package). If the program gets an EOFException when reading from the keyboard, it should print a goodbye message of some sort, and quit. (Note: you can send an EOF signal from the keyboard by typing control-D.)

Due date: Tuesday, February 18, before midnight.