Description
In the past few lectures, we’ve discussed how to implement a Lisp interpreter in OCaml. For this laboratory assignment, you will modify the Lisp interpreter so it can evaluate three kinds of expressions that it could not evaluate before. Among other things, this gives you some practice reading and modifying OCaml code that you didn’t write yourself—as you might have to do in the Real World.
1. Implementation.
The file tests12.ml contains OCaml source code for a Lisp interpreter like the one that has been discussed in the lectures. You must modify the interpreter so it can evaluate three new primitive functions: number, imply and let. They are described as follows, where the arrow ‘⇒’ means returns.
Number. The function number takes one argument, evaluates it, and tests if its result is a number (an integer). It returns t if the test succeeds, and nil if the test fails. Here are some examples of how number must work.
(number nil)
⇒
nil (number (quote a))
⇒
nil (number (quote (a b c)))
⇒
nil (number 7734)
⇒
t (number 0)
⇒
t (number (+ 2 2))
⇒
t
If number is called with no arguments, or with two or more arguments, then it must raise the exception EvaluatorError. Modify the Lisp interpreter so it can evaluate calls to number.
Imply. In propositional logic, α → β is called an implication, and is read as ‘‘alpha implies beta.’’ It is an abbreviation for (¬ α) ∨ β. If α is false, then α → β is true. If β is true, then α → β is true. Otherwise α → β is false.
The Lisp function (imply e₁ e₂ ⋯ eₙ) acts like a series of one or more implications e₁ → e₂ ⋯ → eₙ. You can also think of it as being like an or, where all arguments but the last are in not’s: (or (not e₁) (not e₂) ⋯ eₙ).
The function imply evaluates its arguments e₁, e₂ ⋯, eₙ one at a time, from left to right. If one of the first n−1 arguments evaluates to nil, then imply stops immediately and returns t, without evaluating the remaining arguments. Otherwise, it returns the result of evaluating the nth argument. Here are some examples of how imply must work.
(imply t)
⇒
t (imply nil)
⇒
nil (imply nil (/ 0 0))
⇒
t (imply t nil (/ 0 0))
⇒
t (imply t t t 100)
⇒
100 (imply (quote a) (quote b) (quote c) (quote z))
⇒
z
If imply is called with no arguments, then it must raise the exception EvaluatorError. Modify the Lisp interpreter so it can evaluate calls to imply.
Let. The Lisp function (let s e₁ e₂) acts like an OCaml let-expression. First, let evaluates the expression e₁. Next, it binds the symbol s in the local environment to the result of evaluating e₁. Then it evaluates the expression e₂, which may contain at least one appearance of s. Finally, let restores the current environment to what it was before s was bound. Here are some examples of how let must work.
(let n 1 n)
⇒
1 (let n 2 n)
⇒
2 (let two 2 (+ two two))
⇒
4 (let two 2 (number two))
⇒
t (let a 1 (let b 2 (+ a b)))
⇒
3
If let is called with fewer than three arguments, or more than three arguments, then it must raise the exception EvaluatorError. If its first argument is not a symbol, then it must also raise the exception EvaluatorError. Modify the Lisp interpreter so it can evaluate calls to let.
2. Deliverables.
The file tests12.ml contains a version of the Lisp interpreter, along with code that performs a series of tests. Each test is worth a specific number of points, in the usual way. All the tests together are worth 40 points.
Modify the Lisp interpreter in tests12.ml so that it implements number, imply, and let, as described above. Run the tests. When you are satisfied with the results of the tests, submit the modified version of tests12.ml to Canvas. You must submit your work by 11:55 PM on December 14, 2021. Check to make sure you have submitted the correct file to Canvas, both BEFORE AND AFTER you have submitted it!
