Some people are still not very clear on exactly what the Lisp interpreter is supposed to do, or how it is supposed to do it. I hope this addition will clarify a few things.

This page is not a formal part of the assignment, and does not impose additional requirements.

Input.

Input can come from one of two places: from the keyboard, or from a file. Initially input comes from the keyboard. Wherever it comes from, you treat it exactly the same: Evaluate each expression, do what it says, and print the result. Any expression that can come from one place can come from the other.

Input initially comes from the keyboard. When you call getString(), whatever you type in will show up in the same terminal window that your output goes to. Although not required, it is a good idea to print a prompt to tell the user that input is expected; for example, System.out.print("Input Lisp expression: "); If the input does not contain a complete S-expression, you might change the prompt to something like System.out.print("Continue expression: "); Note that these examples use print rather than println.

As each expression is read in, it should be converted to a single case (all uppercase or all lowercase), in order to simplify looking up function and variable names. Uppercase is more traditional, lowercase is more readable. Then it is parsed.

Strings are only used to communicate with the user. When the user types an expression, it is read as a String, but is immediately converted to a Sexpr by the parse method. All expression evaluation is done with Sexprs. When evaluation is completed, the result is another Sexpr, and the toString method is used to display this Sexpr to the user.

When the user enters the expression (LOAD) at the prompt, your program should use LineReader to open a file, read it in, execute the contents, and return to reading from the keyboard.

Evaluation.

In Lisp there are functions and special forms. The only special forms we are concerned with are QUOTE, DEFUN, and COND; everything else (CAR, CDR, CONS, etc.) is a function. Users can define new functions, but not new special forms.

The arguments to a function are defined before the function is called. The values of these arguments are assigned to the formal parameters of the function. For example, if the user defines (DEFUN MYFUN (ARG1 ARG2) (CONS ARG1 ARG2)) and calls it with (MYFUN (QUOTE W) (CDR (QUOTE (X Y Z)))), the Lisp interpreter first evaluates the arguments, assigns W to ARG1 and (Y Z) to ARG2, then calls CONS with these values.

The arguments to a special form are not evaluted, except possibly within the special form itself. In the MYFUN example above, DEFUN is called with three unevaluated arguments: MYFUN, (ARG1 ARG2), and (CONS ARG1 ARG2).

The built in functions (CAR, CDR, CONS, etc.) do not need access to a table of variable names and their values, because they receive their arguments fully evaluated. QUOTE and DEFUN receive their arguments unevaluated, but don't evaluate them. COND is different, since it receives an unevaluated argument (a list of test-result pairs) and evaluates it using whatever parameter values are in effect at the time. That is, if MYFUN (above) had a COND in its body, that COND would have to know the values of ARG1 and ARG2. COND is like a user-defined function in this respect.

My recommended way of assigning values to formal parameters is to create a new hash table (either a Hashtable or a HashMap) and, as the arguments are evaluated, putting each value into the hash table using the corresponding formal parameter name as the key. Then the hash table can be passed to the evaluation function. The evaluation function, in this case, might have a signature such as Sexpr eval(Sexpr functionBody, HashMap arguments). (This could be in addition to the single-argument form of eval, which you still should have.)

Walkthrough.

Suppose the program reads in:

(DEFUN FIRST (X)
     (COND
     ((NULL X) NIL)
     (T (CAR X)) ) )

As the expression is read in, it is converted to all uppercase or all lowercase (your choice). If the input is from the keyboard, the inupt is checked to ensure that it is a complete S-expression, that is, an expression with balanced parentheses. It is then parsed into a Sexpr, and all subsequent work is done with that Sexpr.

Next the function name (DEFUN) is extracted and tested against the names of built-in functions and special forms. DEFUN is found to be a special form, so the program does not evaluate the parameters to it. The three parameters to DEFUN--FIRST, (X), and (COND ((NULL X) NIL) (T (CAR X)))--are extracted and passed to the method for handling DEFUN, which simply puts the function definition in a table, probably implemented as a Hashtable or HashMap. A good way to do this is to use the String name of the function, "first", as a key, and the parameters and body, ((X) (COND ((NULL X) NIL) (T (CAR X)))), as the value. Finally, the method returns an atomic Sexpr containing the string "FIRST DEFINED."

Sometime later, the user enters the expression

(FIRST (QUOTE (A B C)))

and the program reads this in and converts it to a Sexpr. The function name (FIRST) is extracted and tested against the names of built-in functions and special forms, but is not found there. It is then tested against the table of user-defined functions, and the definition ((X) (COND ((NULL X) NIL) (T (CAR X)))) is found. Since FIRST is a function, the argument(s) to the function must be evaluated. The one argument is (QUOTE (A B C)), so this is (recursively) evaluated.

QUOTE turns out to be a special form, so the argument (A B C) is not evaluated, but is passed to the method for handling QUOTE--which just returns the argument unchanged. This completes the evaluation of the argument to FIRST.

The next task is to evaluate FIRST with the (now evaluated) argument (A B C). In this case there is only one argument, but there could be several. A good way of getting the argument(s) to the function is to create a small Hashtable or HashMap and put the arguments into it. The names of the arguments are the formal parameter names in the function definition. In this example, the only entry in this new hash table has key X and value (A B C). Once the hash table is set up, an "evaluate function" method is called with the hash table and the rest of the function body, (COND ((NULL X) NIL) (T (CAR X))).

Here's what the "evaluate function" does. First, the function name (COND) is extracted and tested against the names of built-in functions and special forms. COND is found to be a special form, so the program does not evaluate the parameters to it. It then calls the method for handling COND, with the list of pairs, ( ((NULL X) NIL) (T (CAR X)) ), and the same hash table (which contains the value for X).

The method for handling COND first extracts the test part of the first pair, (NULL X), and evaluates it. discovers that NULL is a built in function, and (since it is a function rather than a special form) extracts the argument X to NULL and evaluates it. Since X is an atom, it is evaluated by looking up its value in the hash table that was passed in, and the value, (A B C), is passed in to the method that handles NULL, which determines that (A B C) is not null, so it returns the S-expression NIL.

Next, the method for handling COND first extracts the test part of the next pair, T, and evaluates it. (The values of T and NIL are always known). Since T is true, COND evaluates the result part of the pair, (CAR X). To do this, the value of X has to be looked up in the hash table and passed to the method for handling CAR, which gets (A B C) and returns A. This is the result returned by COND, which in turn is the result returned by FIRST. Since FIRST was called from the top-level read-eval-print loop, its result (A) is turned into a String and printed out.