CIT 594 A Lisp Interpreter Walkthrough
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 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
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,
If the input does not contain a complete S-expression,
you might change the prompt to something like
Note that these examples use
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
Sexpr by the
parse method. All expression evaluation
is done with
Sexprs. When evaluation is completed, the result is
Sexpr, and the
toString method is used to
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.
In Lisp there are functions and special forms. The only
special forms we are concerned with are
COND; everything else (
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
and calls it with
the Lisp interpreter first evaluates the arguments, assigns
(Y Z) to
ARG2, then calls
with these values.
The arguments to a special form are not evaluted, except possibly within the
special form itself. In the
MYFUN example above,
is called with three unevaluated arguments:
The built in functions (
etc.) do not need access to a table of variable names and their values, because
they receive their arguments fully evaluated.
receive their arguments unevaluated, but don't evaluate them.
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
COND would have to know the values of
COND is like a user-defined function in
My recommended way of assigning values to formal parameters is to create a
new hash table (either a
Hashtable or a
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
(This could be in addition to the single-argument form of
which you still should have.)
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
extracted and passed to the method for handling
DEFUN, which simply
puts the function definition in a table, probably implemented as a
HashMap. A good way to do this is to use the
name of the function,
"first", as a key, and the parameters
as the value. Finally, the method returns an atomic Sexpr containing the string
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
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
is not evaluated, but is passed to the method for handling
just returns the argument unchanged. This completes the evaluation of the argument
The next task is to evaluate
FIRST with the (now evaluated) argument
. 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
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,
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
COND, with the list of pairs,
and the same hash table (which contains the value for
The method for handling
COND first extracts the test part of the
(NULL X), and evaluates it. discovers that
is a built in function, and (since it is a function rather than a special form)
extracts the argument
NULL and evaluates it.
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
is not null, so it returns
Next, the method for handling
COND first extracts the test part
of the next pair,
T, and evaluates it. (The values of
NIL are always known). Since
T is true,
evaluates the result part of the pair,
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. This is the result returned by
which in turn is the result returned by
was called from the top-level read-eval-print loop, its result (
is turned into a String and printed out.