Higher-Order Programming » Lab Sessions

Session 9 (Solutions)

Assistant: Steven Keuchel (steven.keuchel@vub.be)

Section 1: Recap

Exercise 1: let*

First, expand eval...

(define (eval exp env) (cond ; ... ((let*? exp) (eval-let* exp env)) ((application? exp) (apply (eval (operator exp) env) (list-of-values (operands exp) env))) (else (error "Unknown expression type -- EVAL" exp))))

Then, implement let*? and eval-let*...

(define (let*? exp) (tagged-list? exp 'let*)) (define (let*-body exp) (cddr exp)) (define (let*-clauses exp) (cadr exp)) (define (let*-clause-variable cl) (car cl)) (define (let*-clause-expression cl) (cadr cl)) (define (eval-let* exp env) (let*-loop (let*-clauses exp) (let*-body exp) env)) (define (let*-loop clauses body env) (if (null? clauses) (eval-sequence body env) (let ((clause (car clauses)) (rest-clauses (cdr clauses))) (let*-loop rest-clauses body (extend-environment (list (let*-clause-variable clause)) (list (eval (let*-clause-expression clause) env)) env)))))

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.

(define (evaluate exp env cont) (cond ; ... ((let*? exp) (eval-let* exp env cont)) ((application? exp) (eval-application exp env cont)) (else (error "Unknown expression type -- EVAL" exp)))) ; ... (define (eval-let* exp env cont) (let*-loop (let*-clauses exp) (let*-body exp) env cont))) (define (let*-loop clauses body env cont) (if (null? clauses) (eval-sequence body env cont) (let ((clause (car clauses)) (rest-clauses (cdr clauses))) (evaluate (let*-clause-expression clause) env (lambda (result) (let*-loop rest-clauses body (extend-environment (list (let*-clause-variable clause)) (list result) env) cont))))))

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

Exercise 3: Boolean Operators

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.

(define (eval exp env) (cond ; ... ((and? exp) (eval-and exp env)) ((or? exp) (eval-or exp env)) ((if? exp) (eval-if exp env)) ; ... ((application? exp) (apply (eval (operator exp) env) (list-of-values (operands exp) env)))

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

(define (and? exp) (tagged-list? exp 'and)) (define (eval-and exp env) (let ((constituents (cdr exp))) (if (null? constituents) #t (and-loop constituents env)))) (define (and-loop lst env) (let ((result (eval (car lst) env))) (if (or (not result) ; Or it evaluated to `#f` (null? (cdr lst))) ; Or the `cdr` is the empty list result (and-loop (cdr lst) env))))

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

(define (or? exp) (tagged-list? exp 'or)) (define (eval-or exp env) (let ((constituents (cdr exp))) (if (null? constituents) #f (or-loop constituents env)))) (define (or-loop lst env) (let ((result (eval (car lst) env))) (if (or result (null? (cdr lst))) result (or-loop (cdr lst) env))))

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

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

(define (evaluate exp env cont) (cond ; ... ((and? exp) (eval-and exp env cont)) ((or? exp) (eval-or exp env cont)) ; ... (else (error "Unknown expression type -- EVAL" exp))))

For and:

(define (and? exp) (tagged-list? exp 'and)) (define (eval-and exp env cont) (let ((constituents (cdr exp))) (if (null? constituents) (cont #t) (and-loop constituents env cont)))) (define (and-loop lst env cont) (evaluate (car lst) env (lambda (result) (if (or (not result) (null? (cdr lst))) (cont result) (and-loop (cdr lst) env cont)))))

For or:

(define (or? exp) (tagged-list? exp 'or)) (define (eval-or exp env cont) (let ((constituents (cdr exp))) (if (null? constituents) (cont #t) (or-loop constituents env cont)))) (define (or-loop lst env cont) (evaluate (car lst) env (lambda (result) (if (or result (null? (cdr lst))) (cont result) (or-loop (cdr lst) env cont)))))

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