Third Assignment: Implementing Lisp, I
Dave Matuszek, Spring 2003

Purpose of the assignment:

The basic idea:

Implement the fundamental Lisp functions, plus a few others.

Your assignment:

Implement the following three classes and their methods. You may define additional classes and methods as needed; however, consider whether additional methods should be public or private.

class Sexpr

public static final Sexpr NIL
public static final Sexpr T
public static final Sexpr QUOTE
public Sexpr(String value)
Creates and returns an atom representing an uppercase version of the given String.
public Sexpr(int value)
Creates and returns an atom representing the given numeric value. Depending on your implementation, you may find the java.lang.Integer wrapper class helpful.
public Sexpr(Sexpr arg1, Sexpr arg2)
Creates and returns a new list whose CAR is arg1 and whose CDR is arg2.
public String toString()
Returns a String representation of this Sexpr.
     Note: This method is most simply written as a recursive method.
public static Sexpr parse(String arg)
Given an argument that represents either an atom or a list, return the S-expression corresponding to that list. If there is an error in the argument, print an error message and return nil.
     Note 1: This is probably the most difficult method in the entire assignment; java.util.StringTokenizer is your friend.
     Note 2: You do not need to parse the special syntax for quoting an S-expression with the ' symbol, and you do not need to parse dotted pairs. Just atoms (variable names and integers) and lists.
     Note 3: This method is most simply written as a recursive method.

class Lisp

None required.
static public Sexpr quote(Sexpr arg)
Implements Lisp QUOTE: That is, it returns its argument unchanged.
static public Sexpr car(Sexpr arg)
Implements Lisp CAR.
static public Sexpr cdr(Sexpr arg)
Implements Lisp CDR.
static public Sexpr cons(Sexpr arg1, Sexpr arg2)
Implements Lisp CONS.
static public Sexpr eq(Sexpr arg1, Sexpr arg2)
Implements Lisp EQ (see Note below).
static public Sexpr atom(Sexpr arg)
Implements Lisp ATOM (see Note below).
static public Sexpr null(Sexpr arg)
Implements Lisp NULL (see Note below).
static public Sexpr numberp(Sexpr arg)
Implements Lisp NUMBERP, which returns "true" if its argument is a number (see Note below). The only numbers in this assignment will be integers.
static public Sexpr equal(Sexpr arg1, Sexpr arg2)
Implements Lisp EQUAL (see Note below). This method is most simply written as a recursive method.

Note: As defined above, Lisp predicates eq, atom, null, equal, numberp do not return a boolean value; instead, they return a value of either Sexpr.NIL or Sexpr.T (or, for a "true" result, possibly something else).

class Test

As needed.
public static void main(String[] args)
Thoroughly tests all the above methods. Part of your grade may be based on how thorough you make your test cases.


Both Sexpr and Lisp can be implemented as ADTs. Think about what data and operations should be made available to the user of the class. Note that the only user of Sexpr should be the Lisp class, so this gives you some additional flexibility in designing Sexpr; but you should still work to make it an ADT. The Lisp class, on the other hand, may (theoretically) have a much wider audience, so you need to be careful not to expose any more of its inner workings than absolutely necessary.

Methods, etc., that should be available to the user should be marked public. Everything else should be private.

All classes, constructors, variables, and methods should either be private or should be fully documented with javadoc documentation comments. Things which are marked private, if they are reasonably self-explanatory, do not need to be documented.

Follow, as closely as possible, the implementation of Lisp as described in class. Don't try to use Vectors or Lists from Java's Collection interface.

Due date: Thursday, February 6, before midnight.