Higher-Order Programming » Lab Sessions

Session 9

Assistant: Steven Keuchel (steven.keuchel@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.

(define (factorial n cont) (if (= n 0) (cont 1) (factorial (- n 1) (lambda (result) (cont (* result n)))))) ; (factorial 5 display) ; prints 120

and these are CPS versions of a list sum using an iterative or recursive process.

(define (sum-iter cont acc xs) (if (null? xs) (cont acc) (sum-iter cont (+ acc (car xs)) (cdr xs)))) (define (sum-rec cont xs) (if (null? xs) (cont 0) (sum-rec (lambda (sumcdrxs) (cont (+ (car xs) sumcdrxs))) (cdr xs))))

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. This can be a different than what the enclosing procedure received. For instance, in the sum-rec procedure a new lambda term is passed as a continuation. This makes precise what remaining computation is usually build up on a control stack.

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.

(define (eval-if exp env cont) (evaluate (if-predicate exp) env (lambda (value) (if (true? value) (evaluate (if-consequent exp) env cont) (evaluate (if-alternative exp) env cont)))))

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 these exercises is to expand the CPS evaluator. Adding new primitive procedures to the CPS evaluator is identical to the exercises from last week: just add these procedures to the list of primitive procedures with a name, and procedure from the underlying Scheme evaluator. Similarly, implementing new special forms by desugaring them into existing primitives and existing special forms is analogous to extending the basic evaluator. Therefore, to train the direct implementation style you are asked to for these exercises you have to implement them without syntactic sugar.

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.

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: Boolean Operators

Exercise 3: Boolean Operators

Implement and and or in the metacircular evaluator (not CPS!). Implement the short-circuit logic of both operators correctly:

;; <does not output "message", just the return value #f> (and #f (display "message")) ;; <does not output "message", just the return value #t> (or #t (display "message"))

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 4: CPS Boolean Operators

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