« Return to index

HOP WPO 7

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

Section 1: Recap

Exercise 1: let*

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

Section 2: Continuation Passing Style Evaluator

Download the CPS 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:

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.


Adding new primitive procedures to the CPS evaluator is identical to exercises 1 and 2 from last week[1], as well as syntax transformations for implementing new special forms[2].

Therefore, for these exercises you have to implement them without syntactic sugar.

Exercise 2: let*

Download the CPS evaluator

Implement let* for the CPS evaluator, without syntactic sugar. You can reuse some code from exercise 1.

Section 3: call-with-current-continuation

Exercise 3: Predict what happens

Predict what happens in the following Scheme programs.

Program A:




		

What happens when you put this program in a procedure, and then call this procedure?

Program B:




		

Program C:




		

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 return

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

Implement and and 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

Implement and and or in your metacircular evaluator in CPS style.

Bonus Exercises

Bonus Exercise 1: Generator procedures

Recommended after exercise 4

Implement generators from JavaScript using call-cc.

Example program:




		

Implement generate and 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 (next generator).

Hint! You have to make use of two call-with-current-continuations!

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 call-with-exception-handler and 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…

  1. Add two new primitive procedures (that for now do not do anything)
  2. Store a stack of exception handlers: if the stack is empty, no exception handler is active.
  3. throw will send its value to the current exception handler.
  4. call-with-exception-handler will 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 call-with-exception-handler expression.

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

Typing 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 try-catch.


  1. Just add these procedures to the list of primitive procedures with a name, and procedure from the underlying Scheme evaluator. ↩︎

  2. Just write a procedure that transforms one program to a much simpler program using other (already implemented) primitives and special forms. ↩︎