HOP WPO 6 (Solutions)
Assistant: Bjarno Oeyen (email@example.com)
As it is not easy to publish the solutions for these exercises on a single web page, I will add executable solutions to each exercise.
Therefore, a short summary of what is changed in each exercise is given here, together with a link to that file that contains ONLY the solution of your exercise, in case you want to verify your solution of a single exercise.
Section 1: Procedures
Exercise 1: Adding support for vectors
Adding new primitives to your metacircular Scheme evaluator is as simple as expanding the list of primitives
When the Scheme evaluator is started, it will install all primitive procedures in this list in the global environment of the metacircular evaluator.
Exercise 2: Division by Zero
For this exercise, I’ve chosen to return either
+Inf.0 (for positive infinity) or
Just like the previous exercise, the primitives available in the metacircular evaluator can be changed by modifying the list of primitive procedures. You are not required to give procedures in the metacircular evaluator the same name as in the implementation.
If you are puzzled: try to think in which layer you are working in: either the evaluator layer (the code you write in DrRacket), or the interpreted layer (the code you write in the REPL of the metacircular evaluator).
Section 2: Syntactic Sugar
Exercise 3: Implementing
Be sure that when you add something to
eval, that it is above the normal procedure application.
So far, every time you had to quote an expression you made use of
'. There is another way for quoting, and that is quasi-quoting (
In quasi-quoted expression you have access to insert a variable inside the quoted expression.
You can also insert lists inside lists…
If you want to insert the elements of the list, instead of inserting the list itself, you make use of
,@ inside the quasi-quoted expression.
In this case, let’s try to retrieve the information of the
when, in order to create an equivalent program using
Therefore, if you want to retrieve the condition and the body of the when…
Note that the body is a list of expressions, and should therefore be seen as a sequence… not a single expression. Evaluating a sequence is evaluating every expression in the expression list of the sequence in-order.
We can make use of quasi-quoting to make our converted program…
condition is a single expression, it can be insterted using an ordinary
,. However, we want to make use of
,@, otherwise we would get the following as a result.
In this program,
begin contains only one expression. Which is not a valid expression since the result of
display is not an application. Therefore splicing using
,@ results in the correct output.
Exercise 4: Implementing
The solution of this exercise is quite similar. We first add an additional case to
Then we add the accessor procedures…
As before, we add a predicate to check whether an expression is a
let expression. Then we add the accessor procedures.
The clauses of a
let can be found by applying
cadr on the expression, the body using
cddr (the same as in the previous exercise using
when). The clauses is a list of lists where the first element (
car) is the variable name, and the second element (
cadr) is the expression to evaluate.
Note! that in this implementation there is no error checking whether a clause contains too many expressions.
Then, we add the actual procedure that converts a
let, using an application of a
let expression we first extract the clauses, and the body. Then from the list of clauses we retrieve the variable names they want to define inside the new scope, and the argument expression to evaluate in the current scope.
clauses is a list of clauses. Therefore we can make use of
map in order to extract the parameters and arguments for the corresponding equivalent program.
After everything is extracted, it can be converted.
Section 3: Special Forms
Exercise 5: Implementing
We have already implemented
when before by converting an expression using
when to something using only
begin. This exercise repeats the previous one, without converting the program into another form.
And the actual implementation of
Exercise 6: Implementing
We start this exercise for the fourth time by modifying
Then we repurpose the accessor procedures from before…
Then we implement the procedure
At first sight, this seems difficult to understand, since a lot is going on at once.
As in exercise 4, the clauses, body, and names of the let are extracted. However, instead of retrieving only the expression of a clause in the let, the value needs to be evaluated. Therefore the value stored in
values should be a list of values after evaluating every clause.
We pass an anonymous procedure to
map that first extracts the expression of the clause, and then evaluates that expression in the environment given to
After everything has been extracted, and the arguments have been evaluated, the body is evaluated in the extended environment.
In order to extend the environment we make use of
extend-environment. This procedure takes 3 arguments…
- A list of variable names
- A list of values
- The base environment (the environment to extend)
This procedure is currently only being used for procedure application. However, it can be used for evaluating a let as well. We pass it the list of variable names from the let, the values that were evaluated by evaluating the expression of the let, and we pass the current environment as the environment that has to be extended.
After the new environment has been created, the body (which is a sequence of expressions) is evalauted in that new environment, the return value of the let, is the result of evaluating that expression.
Section 4: Lazy Evaluator
Exercise 7: Repetition
The solution to this exercise is identical to that of exercise 1.
Adding special forms (via program transformation)
The solution to this exercise is identical to that of exercise 3.
Adding special forms (explicit evaluation)
The solution to this exercise is almost identical to that of exercise 6. The sole difference is that instead of writing
(eval ...), we make use of the
delay-it procedure to avoid calculating the expression of every clause until it is needed in the body of the let, which is the same behaviour we would have got if we would have used to “syntax transformation” technique from exercise 4.
Note that now, the values stored in
values are thunks: they are not evaluated yet. Therefore, these expressions are only evaluated if needed. If we execute the following program in the modified metacircular evaluator…
No error will be thrown, however, if we use
z in the body of the program…
then an error will be raised.
If you want to verify the solution of the bonus exercises, you can send your solution via email.