HOP WPO 7 (Solutions)
Assistant: Bjarno Oeyen (email@example.com)
Section 1: Recap
let*-loop evaluates the expressions of the clauses sequentially (from top-to-bottom), extending the current environment for every clause. Note that
extend-environment expects as the first two arguments, a list of variable names and a list of values to bind, therefore the result of evaluating a clause must be wrapped in a list.
Section 2: Continuation Passing Style Evaluator
We have just implemented
let* in the basic metacircular evaluator. This time the extension needs to be made in the CPS evaluator.
Note the difference between this solution and the other solution is that now the result of evaluating
(let*-clause expression clause) in the
env environment is given by evaluating the
(lambda (result) ...) procedure.
Exercise 3: Predict what happens
The lambda given to
call-with-current-continuation will store the continuation in the global
c variable, and then returns 5. Therefore, the first part of the program prints
50 (since \(5 \times 10 = 50\)). The continuation itself is something that expects a value, then multiplies that value by 10, and then displays that result. Therefore, the next time the continuation is used it will have to evaluate \(7 \times 10 = 70\), thus printing 70.
And finally the continuation is called with 20 as argument, and the value \(20 \times 10 = 200\) is printed. Note that when the continuation
c is called, that the current continuation is discarded, thus the continuation representing \(? + 50 = ?\) is never evaluated!
If this program would be wrapped in a procedure, and this procedure would have been called, then an infinite loop would occur, since the continuation stored in
c in that scenario would be “give me a value, I will multiple it by 10 and then resume the program”. Resuming the program means reloading the same continuation as before. Which results in an infinite loop.
What seems like an infinite loop, is in fact not an actual loop, since the continuation stored in
c is used to escape the loop. As in the previous example, when a continuation is restored, the current continuation is discarded.
Continuations are used in this example program to escape a possible long-running application. Instead of passing through multiple recursive stack frames, the program can simply restore the continuation stored at the beginning when the
find procedure is started, and return the value that matched the predicate immediately.
Therefore, when the example program is running the number
15 should be returned.
Exercise 4: Implement
Three modifications in total need to be made in order to make the example program run. The first part is to add the necessary native procedures to the
The second is to make sure that boolean expressions evaluate to themselves, therefore the
self-evaluating? procedure needs to be modified.
The last modification is the actual exercise, and that is to transform procedure definitions before they are evaluated.
transform-define there is a check whether the definition is a procedure definition, or a definition of a plain variable with a non-procedural value.
Note that there would be an issue if
transform-define would be applied on all lambda expressions (e.g. by modifying the definition of
make-lambda). Since our approach adds an anonymous procedure to the body of every procedure, this would result in an infinite expansion (since the new lambda expression would also need to be transformed and thus producing even more lambda expressions).
Section 4: Boolean Operators
Exercise 5: Boolean Operators
Boolean operators are special forms: since they only evaluate their arguments as long as they need to. E.g.
(or a b c) does not need to evaluate
a already evaluated to a
(and a b c) does not need to evaluate
a already evaluates to
Thus there are two approaches: either we make use of syntactic sugar, or via explicit evaluation. Note that simply transforming
(or a b) to
(if a a b) does not work, as expressions can contain side effects. E.g. if
a modifies a variable, then it will modify it twice. This can be circumvented by caching an evaluated expression in a variable, thus transforming
(if a a b) to
(let ((e-a a)) (if e-a e-a b)).
However, the solution in this exercise is to make use of explicit evaluation.
First, modify the definition of
eval-and, as well as
eval-or. First let’s implement the support for
The evaluation of an
and expression starts in
eval-and. It will first read the constituent expressions of the
and expression. If there are none, it immediately returns
#t. Otherwise, it will enter a loop to evaluate each consituent in order until either: one of the evaluated constituent expressions evaluates to
#f, the last constituent expression has been evaluated.
Note that difference in the definition of
or stops evaluating the constituent expressions once it encounters at least one expression that evaluated to
Exercise 6: CPS Boolean Operators
This is almost equivalent as the previous exercise, but using CPS style.
Note that instead of storing the result of
evaluate) in a variable using
let as before, it is now given by passing it to a lambda that binds the result to a variable with the same name.
If you want to verify the solution of the bonus exercises, you can send your solution via email.