HOP WPO 7
Assistant: Bjarno Oeyen (email@example.com)
Section 1: Recap
Add support for
let* in the basic metacircular evaluator (without making use of syntactic sugar). You can reuse the code from last time to access the body and clauses of
let*, since it has the same syntax as
Section 2: Continuation Passing Style Evaluator
A program written in Continuation-Passing Style never returns a value. Instead, every procedure call expects a procedure. The result of evaluating a procedure is sent by applying this procedure. The following is a handwritten CPS style definition of factorial.
Note that every tail-position in a CPS procedure is either:
- An application of the continuation procedure.
- An application of another procedure in CPS, that receives a continuation (can be a different one).
Therefore, since every procedure is in tail-position, the underlying Scheme interpreter can optimize this such that it does not consume additional stack space.
This same technique can also be applied to an evaluator, or any type of program. As an example of an evaluator written in CPS style, take alook at the
eval-if from the CPS evaluator.
evaluate evaluated an expression (first argument) in a given environment (second argument), and its result is sent by applying the continuation procedure (third argument). After the condition (or predicate) expression is evaluated, the lambda will be evaluated passing the boolean value from the evaluated predicate as argument.
If this boolean is true, the consequent expression is evaluated in the same environment, and the continuation that was passed to
eval-if is the continuation in which the result of evaluating the
if expression should be sent to. Otherwise, the alternative expression is evaluated, with the same semantics.
The other parts of this evaluator are also implemented in CPS style. The goal of tese exercises is to expand the CPS evaluator.
Note! During the lectures you have seen a CPS style evaluator implemented on top of the analysing evaluator. However, for simplicity, these exercises are to be made on top of the CPS evaluator without an analysing phase.
Therefore, for these exercises you have to implement them without syntactic sugar.
let* for the CPS evaluator, without syntactic sugar. You can reuse some code from exercise 1.
Exercise 3: Predict what happens
Predict what happens in the following Scheme programs.
What happens when you put this program in a procedure, and then call this procedure?
Explain what happens when you make use of the
find procedure when you give it a large data structure containing vectors and lists nested in each other, together with a predicate. What is the result of evaluating…
Exercise 4: Implement
By using syntactic sugar and
call/cc add support for
return by transforming procedure definitions in the CPS evaluator.
The transformed code for this can look like…
Binary tree implementation (with example)
To test your program (after loading the binary-trees file in the metacircular evaluator)…
Section 4: Boolean Operators
Exercise 5: Boolean Operators
or in the metacircular evaluator (not CPS!). Are they primitive procedures, or special forms? If the former, implement them either as primitive or user-defined procedures? If the latter, can they be implemented using syntactic sugar or explicit evaluation? Or both? Choose one approach.
Exercise 6: CPS Boolean Operators
or in your metacircular evaluator in CPS style.
Bonus Exercise 1: Generator procedures
Recommended after exercise 4
next. You can make use of the following boilerplate code:
Hint! Use the three “state” variables at the top to keep track of the state of the generator procedure. Use
saved to store a continuation in the generator procedure,
exit1 to store a continuation to return a value as the result of evaluating
next, and use
ended as a boolean to remember if the generator procedure ended its evaluation. If the latter is true, to continuation stored in
saved should not be called and the
end procedure (already implemented) should be called instead: returning
#f for every consequent
Hint! You have to make use of two
Bonus Exercise 2: Exceptions (simple)
Recommended after exercise 4
In this exercise, you will have to expand the evaluator such that is has built-in support for exceptions… Take the following program as an example (based on the example from the lectures).
Instead of implementing
throw inside a Scheme environment, you are going to expand the CPS evaluator with support for exception handling. You will need to do the following…
- Add two new primitive procedures (that for now do not do anything)
- Store a stack of exception handlers: if the stack is empty, no exception handler is active.
throwwill send its value to the current exception handler.
call-with-exception-handlerwill install a new exception handler, and execute its body. If no exception is thrown, the exception handler is removed again, and the result of the body is returned as result of the
Make sure that
throw removes the current exception handler as well, before continuing the program.
Bonus Exercise 3: Exceptions (advanced)
Recommended after bonus exercise 2
call-with-exception-handler with a bunch of lambdas each time we want to catch an exception is cumbersome. Therefore, add new syntax
try-catch that allows you to rewrite the example program from the previous exercise as follows…
The syntax for
try-catch expects two expressions: one that represents the body of the
try block, and another which is expected to evaluate to a exception handler procedure (as before). Make use of syntactic sugar to add support for