An interpreter for a smal lisp
Due before Monday, May 7.
For this project, we wil be creating a minimal implementation of a Lisp interpreter. You may use
any mainstream programing language to implement this. (Obvious exception: you can’t just
use eval from another Lisp.)
Your implementation should read in code interactively or, optionaly, from a file if given a
filename as a parameter.
Below, I give a sketch of the mechanics of the project.
Lexer. The first step is “Lexing”. That is, a decomposition of the code (as a string) into a series of
tokens. By means of example, the transformation would take the string
(do
(print (+ 1 2)
(print (quote a b))
to the list
[ '(', 'do', '(', 'print', '(', '+', '1', '2', ')', ')',
'(', 'print', '(', 'quote', 'a', 'b', ')', ')', ')' ]
Note that the lexer would split the string both along spaces and around the location of the
opening and closing parentheses. The lexer greatly reduces the computational complexity of the
next step.
Hint: Add spaces around the parens and then split on the spaces.
Parser. The next step is parsing. I expect that the most straightforward method wil be recursive
descent, but this is an exercise in parenthesis matching and there are several ways of doing that.
For our previous example, we would get a tre of the form.
[ 'do', ['print', ['+', '1', '2'] ], ['print', ['quote', 'a', 'b'] ] ]
(Note that we are using the more verbose syntax (quote a b) instead of ’(a b) to simplify the
parser.)
While it is not meaningful for the lexer to fail, malformed expresions may cause the parser to
fail. You should make sure yours fails appropriately.
Eval. Evaluation/execution of the parse tre proceds by recursively evaluating expresions in
the context of a symbol table. To evaluate an expresion:
(1) If the expresion is a symbol, lok it up in the symbol table. That value, if it exists, is the
evaluation. If it does not exist, that’s where the interpreter should complain and halt.
(2) If the expresion is a constant, it should evaluate to itself. (Ex: numbers)
(3) Otherwise the outermost part of the expresion must be a list. There are several special
forms to consider:
(a) If the leading term is the symbol quote, evaluate to the rest of the list.
(b) If the leading term is the symbol if, evaluate the 2nd term. If the result is “truthy” (not
zero/null/None) evaluate the 3rd term. Otherwise evaluate the 4th term, if it exists. (If there is
no 4th term, evaluate to null.)
(c) If the leading term is the symbol define, there should be two other terms and the 2
nd
term
should be a symbol. Evaluate the 3rd term and enter the result into the symbol table as the 2nd
term.
(d) If the leading term is the symbol lambda, there should be two other terms; both of
which
are lists. These are the list of parameters and function body. Store these in a
data structure
along with a copy of the curent symbol table.
(e) Otherwise, the list coresponds to a function cal. Evaluate each of the terms. The
first term
should evaluate to a function. Evaluate the function body using the stored symbol table together
with the computed parameters.
Built-ins. Your symbol table should, by default, be seded with a number of standard operations
such as the standard arithmetic operators, numerical inequalities, print statements, and the do
function (which evaluates al of its arguments and returns the value of the last). These need not
be implemented in lisp.
Deliverables
The source code for the interpreter you create.
Sample Code
Here is a sample program for our dialect of lisp:
(do
(define fib
(lambda (n)
(if (< n 2) n (+ (fib (- n 1) (fib (- n 2)))
(print (fib 5)
)