« Return to index

HOP WPO 6 (Solutions)

Assistant: Bjarno Oeyen (bjarno.oeyen@vub.be)

General Remarks

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.

Download solution

Exercise 2: Division by Zero

For this exercise, I’ve chosen to return either +Inf.0 (for positive infinity) or -Inf.0




		

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

Download solution

Section 2: Syntactic Sugar

Exercise 3: Implementing when




		

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 if and begin.




		

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…




		

Since 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.




		

Download solution

Exercise 4: Implementing let

The solution of this exercise is quite similar. We first add an additional case to eval




		

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 lambda.




		

From 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.

Note that 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.

Download solution

Section 3: Special Forms

Exercise 5: Implementing when

We have already implemented when before by converting an expression using when to something using only if and begin. This exercise repeats the previous one, without converting the program into another form.




		

And the actual implementation of eval-when




		

Download solution

Exercise 6: Implementing let

We start this exercise for the fourth time by modifying eval




		

Then we repurpose the accessor procedures from before…




		

Then we implement the procedure eval-let.




		

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 eval-let.

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…

  1. A list of variable names
  2. A list of values
  3. 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.

Download solution

Section 4: Lazy Evaluator

Exercise 7: Repetition

Adding procedures




		

The solution to this exercise is identical to that of exercise 1.

Download solution

Adding special forms (via program transformation)




		

The solution to this exercise is identical to that of exercise 3.

Download solution

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.

Download solution

Bonus Exercises

If you want to verify the solution of the bonus exercises, you can send your solution via email.