Download the interpreter.zip handout archive file and extract it somewhere on your machine. Then, follow the instructions on how to setup up the git repository for this project.
You are provided with an implementation of the Lisp interpreter
seen in class (
Lisp.scala). In this part, you will modify it to
add “syntactic sugar”.
In a programming language, syntactic sugar allows us to express concepts that already exist in the language, but in a different way, which should be neater/more elegant to write for the programmer.
In this exercise, you must change the
eval1 function in such a
way that it will interpret the sugared forms with equivalent, but
1. A better ''def''
Lisp.scala, add a new form of
def which makes it possible to define a
function more easily. The idea is to interpret the following
(def (name arg_1 ... arg_n) body expr)
as the following expression:
(def name (lambda (arg_1 ... arg_n) body) expr)
This makes it possible, for example, to test the successor function as follows:
(def (succ x) (+ x 1) (succ 0))
2. Switch-like construct
Add a new form of conditional expressions,
case, which compares one value against many possible alternatives, in a nicer way than with nested
The syntax of this form is as follows:
(case expr_scrut (value_1 expr_1) (value_2 expr_2) ... (value_n expr_n) (else expr_else) )
What this expression means is– if the
expr_scrut is equal to the first
value_1 (in the sense of the
= predicate), then
the first expression
expr_1 is evaluated and returned; otherwise, if the
scrutinee is equal to
expr_2 is evaluated and
returned, and so on and so forth till the
nth value; if the scrutinee is
not equal to any of the values, the expression following the keyword
else is evaluated and returned. The conditional expression
case is thus translated into a chain of tests as follows:
(if (= expr_scrut value_1) expr_1 (if (= expr_scrut value_2) expr_2 ... (if (= expr_scrut value_n) expr_n expr_else) ) )
Hint: think recursively!
In this part, you will add a read-eval-print loop, or REPL, to your
interpreter. Such a tool is at the heart of any interactive interpreter,
scala. It allows the user to interact with the system
by entering expressions and then to directly examine the result of
Your REPL will tell the user that it is ready for evaluation with a
prompt, for example
lisp>. It should wait until a user enters an expression,
then it should evaluate it, and then print the result of the evaluation. An interaction
using your REPL will look like:
lisp> (+ 1 3) 4 lisp> (cons 1 (quote ())) (1) lisp>
You can make use of Java classes which make it possible to read in data line by line.
System will come in handy.
Have a look at the JavaDoc for more information.
Coding in Lisp
In Lisp, write a tail-recursive function
differences which computes a list composed of the first element
followed by the differences of successive elements of the list.
Also write a reciprocal
rebuildList function, which computes the original list
out of a list of differences. You do not need to write it tail-recursive.
You will first implement, as a helper, a tail-recursive reverse function.
Test your functions with your interpreter, and verify that you obtain the expected result for a few examples.