CS 3323 Topics in Programming Languages
Lisp Interpreter Project
LISP Interpreter--Overview
For this programming project you are to write an interpreter for a subset
of Lisp. You must write the interpreter itself in C++, though initially
we will be using C and gradually add parts of C++. The objectives of the
project are to acquire:
- An introduction to compiler techniques, including scanners, parsers,
and syntax-directed translation.
- Specifics about the Lisp language and its implementation.
- Programming skills in C and C++, particularly in the use of pointers, and
recursion, the construction of a medium-sized program,
the use of separate files,
and an introduction to C++.
- Experience with abstract data types and with the functional style of
programming.
The project itself will consist of four parts as outlined below.
Source code for each of the first two parts will be available, so that
students can continue the project even if they were not successful (or
only partially successful) with the first or second part. Each assignment
can be turned in one class meeting late with a substantial late penalty.
If you are more than one period late on the first or second part, you
should work on the next part using the source supplied in
class. The four parts are:
- Scanner for Lisp.
This will read Lisp source character-by-character
and successively return one of four tokens:
- a left parenthesis,
- a right parenthesis,
- a numeric atom (along with the integer representing the atom), or
- an alphabetic atom (along with the character string representing the atom).
This part introduces the use of a finite
automaton in constructing a program.
- Parser and translator for Lisp.
This will convert Lisp S-expressions
back and forth between external form (with parentheses and blanks)
and internal (or linked list) form. You will write recursive procedures
based on a BNF grammar for Lisp that will convert the sequence of
tokens produced by the scanner to the internal form. Similar recursive
procedures will convert the linked list form to the external form. This
part gives practice in working with pointers and in regarding S-
expressions as an abstract data type.
- Simple initial evaluator of
S-expressions.
The values of S-expressions will be computed using implementation
of various basic
Lisp functions, including arithmetic functions like NUMBERP,
PLUS, DIFFERENCE, MINUS, TIMES,
QUOTIENT, EQ, and GREATERP,
list functions like ATOM, CAR, CDR,
CONS, as well
as others like QUOTE. It will be to your advantage to implement
CAAR, CADR, CDAR, and CDDR,
but these are not required. You
may also implement COND in this assignment. At this stage
alphabetic atoms will not have values, and there will be no
user-defined functions. This part allows one to try using a functional
programming style within C, where this term means that one uses
only functions that return values, and one does not use the assignment
statement or any iterative statement, but instead uses recursion.
- Lisp interpreter with function
definitions and SETQ's. In this
final part alphabetic atoms are associated with values that are simply
S-expressions, and COND, DEFUN, and SETQ
will be implemented.
This part introduces the idea of an environment in which Lisp
functions are executed. The functional programming style of part 3 is
continued.
Optional Additional Features. There are a number of additional
features that could reasonably be incorporated into your Lisp interpreter:
- Garbage collection. This would be the most important addition,
relatively hard to implement.
- Separate types of real, integer, and rational.
Reals make an easy
addition which you could do from the beginning. The scanner needs
to recognize a real constant, and there are a few other minor changes
here and there. For rationals you just need to build in code to work
with fractions.
- Iterative looping.
All forms of Lisp provide some form of iteration
as an alternative to recursion (though recursion would always
suffice). This would also be relatively hard to implement.
Good programming style. This is not a software engineering course,
but you should nevertheless use good C programming techniques. In
particular, the separate parts for the assignment should be separate files,
with separate header files (although you might combine parts 3 and 4).
You should use C static types to isolate functions needed only in a
given file. You do not need line-by-line comments in your code, or even
elaborate comments at the start of each function. (Each function and file
should have brief comments at the beginning, but nothing more is
required.) Instead you must have a single piece of overview
documentation as a separate file. Documentation must be machine
readable; the instructor will treat hand-written comments as if they are
not present. Overview documentation answers at least the following
questions, using an outline format, rather than long boring paragraphs of
prose:
- Author. Date. Purpose. Who wrote the code, when, and for what
purpose.
- Implementation Overview. What was implemented. How it works.
(A tiny user's manual. Emphasize anything different from the
specifics of the assignment.)
- Implementation Plan. Specifics about the approach used for
implementation, including especially anything unusual or different
from the approach recommended in class.
- Implementation History. Description of the work required during
development, including debugging.
- Testing. Overview of the test plan and results of testing.
- Problems. Features not implemented, known bugs, deficiencies,
other problems.
- Sources.
If you used ideas or code that you did not originate, you
must cite the sections of code and the sources here, whether
individuals, books, or other code. Otherwise state explicitly that you
used no outside sources.
You can add to this overview documentation as you go along. I want
clarity and brevity, not length.
Revision date: 1/6/99