« Return to index

HOP WPO 7 (Solutions)

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

Section 1: Recap

Exercise 1: let*

First, expand eval




		

Then, implement let*? and eval-let*




		

The procedure 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.

Download solution

Section 2: Continuation Passing Style Evaluator

Exercise 2: let*

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.

Download solution

Section 3: call-with-current-continuation

Exercise 3: Predict what happens

Tip! Extra informationa bout this exercise is available here

Program A




		

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.

Program B




		

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.

Program C

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 return

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 primitive-procedures structure…




		

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.




		

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

Download solution

Section 4: Boolean Operators

Exercise 5: Boolean Operators

Tip! Extra informationa bout this exercise is available here

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 b and c if a already evaluated to a #t. (and a b c) does not need to evaluate b and c if a already evaluates to #f.

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.




		

Then implement and? and eval-and, as well as or? and eval-or. First let’s implement the support for and.




		

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.

Similar for or




		

Note that difference in the definition of or-loop. or stops evaluating the constituent expressions once it encounters at least one expression that evaluated to #t.

Download solution

Exercise 6: CPS Boolean Operators

This is almost equivalent as the previous exercise, but using CPS style.




		

For and:




		

For or:




		

Note that instead of storing the result of eval (or 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.

Download solution

Bonus Exercises

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