• English only

Lab for Automated Reasoning and Analysis LARA

Handout

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.

Syntactic Sugar

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.

1. A better ''def''

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

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 `if`s. 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 `n`th 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!

REPL

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.

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.