# HOP WPO 7 (Solutions)

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

## Section 1: Recap

`let*`

Exercise 1: 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.

## Section 2: Continuation Passing Style Evaluator

`let*`

Exercise 2: 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.

`call-with-current-continuation`

Section 3: ### 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.

`return`

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

## 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`

.

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

## Bonus Exercises

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