LARA

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 non-sugared, forms.

In 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 expression:

  (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))

Add a new form of conditional expressions, case, which compares one value against many possible alternatives, in a nicer way than with nested ifs. 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 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 value_2, then 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, such as scala. It allows the user to interact with the system by entering expressions and then to directly examine the result of their evaluation. 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. BufferedReader, InputStreamReader and System will come in handy. Have a look at the JavaDoc for more information.

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.