Higher-Order Programming » Lab Sessions

Session 8 (Solutions)

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

General Remarks

As it is not easy to publish the solutions for these exercises on a single web page, I will add executable solutions to each exercise.

Therefore, a short summary of what is changed in each exercise is given here, together with a link to that file that contains ONLY the solution of your exercise, in case you want to verify your solution of a single exercise.

Section 1: Procedures

Exercise 1: Division by Zero

For this exercise, I've chosen to return either +Inf.0 (for positive infinity) or -Inf.0. The primitive is implemented as a procedure in the evaluator

(define (sign a) (cond ((< a 0) -1) ((> a 0) +1) (else 0))) (define (my-division a b) (if (= b 0) (* (sign a) +inf.0) (/ a b)))

which is then plugged in instead of the normal division operator:

@@ -290,7 +300,7 @@ (list '+ +) (list '- -) (list '* *) - (list '/ /) + (list '/ my-division) (list '= =) (list 'newline newline) (list 'display display)

The primitives available in the metacircular evaluator can be changed by modifying the list of primitive procedures. You are not required to give procedures in the metacircular evaluator the same name as in the implementation.

If you are puzzled: try to think in which layer you are working in: either the evaluator layer (the code you write in DrRacket), or the interpreted layer (the code you write in the REPL of the metacircular evaluator).

Download solution

Section 2: Syntactic Sugar

Exercise 2: Implementing when

To implement a special form by desugaring we write

1. a predicate that recognizes the special form, and
2. a procedure that does the syntax transformation.

For when these two ingredients are

(define (when? exp) (tagged-list? exp 'when)) (define (when->if exp) (let ((condition (cadr exp)) (body (cddr exp))) (list 'if condition (cons 'begin body))))

which can then be plugged into the eval function

@@ -21,4 +21,5 @@ ((cond? exp) (eval (cond->if exp) env)) ;; Add your special forms here! + ((when? exp) (eval (when->if exp) env)) ((application? exp) (apply (eval (operator exp) env)

Be sure that when you add something to eval, that it is above the normal procedure application.

Quasi-quotation

So far, every time you had to quote an expression you made use of '. There is another way for quoting, and that is quasi-quoting (`).

In quasi-quoted expression you have access to insert a variable inside the quoted expression.

(define a 2) `(1 ,a 3) ; -> '(1 2 3)

You can also insert lists inside lists...

(define lst (list 4 5 6)) `(1 2 3 ,lst 7 8 9) ; -> '(1 2 3 (4 5 6) 7 8 9)

If you want to insert the elements of the list, instead of inserting the list itself, you make use of ,@ inside the quasi-quoted expression.

(define lst (list 4 5 6)) `(1 2 3 ,@lst 7 8 9) ; -> '(1 2 3 4 5 6 7 8 9)

In this case, let's try to retrieve the information of the when, in order to create an equivalent program using if and begin.

(define exp '(when (something-true? x) (display "it's true!") (do-calculation x)))

Therefore, if you want to retrieve the condition and the body of the when...

(car exp) ; -> 'when (cdr exp) ; -> ((something-true? x) ...) (define condition (cadr exp)) ; -> (something-true? x) (define body (cddr exp)) ; -> ((display "it's true!") (do-calculation x))

Note that the body is a list of expressions, and should therefore be seen as a sequence... not a single expression. Evaluating a sequence is evaluating every expression in the expression list of the sequence in-order.

We can make use of quasi-quoting to make our converted program...

`(if ,condition (begin ,@body))

Since condition is a single expression, it can be insterted using an ordinary ,. However, we want to make use of ,@, otherwise we would get the following as a result.

(if (something-true? x) (begin ((display "it's true!") (do-calculation x))))

In this program, begin contains only one expression. Which is not a valid expression since the result of display is not an application. Therefore splicing using ,@ results in the correct output.

(if (something-true? x) (begin (display "it's true!") (do-calculation x)))

Putting everything together the desugaring function when->if can be replaced by the following version that uses quasi-quotation:

(define (when->if exp) (let ((condition (cadr exp)) (body (cddr exp))) `(if ,condition (begin ,@body))))

Download solution

Exercise 3: Implementing let

The solution of this exercise is quite similar. We first add an additional case to eval...

@@ -20,4 +20,5 @@ (eval-sequence (begin-actions exp) env)) ((cond? exp) (eval (cond->if exp) env)) + ((let? exp) (eval (let->lambda exp) env)) ;; Add your special forms here! ((application? exp)

Then we add the accessor procedures...

(define (let? exp) (tagged-list? exp 'let)) (define (let-body exp) (cddr exp)) (define (let-clauses exp) (cadr exp)) (define (let-clause-name clause) (car clause)) (define (let-clause-expression clause) (cadr clause))

As before, we add a predicate to check whether an expression is a let expression. Then we add the accessor procedures.

The clauses of a let can be found by applying cadr on the expression, the body using cddr (the same as in the previous exercise using when). The clauses is a list of lists where the first element (car) is the variable name, and the second element (cadr) is the expression to evaluate.

Note! that in this implementation there is no error checking whether a clause contains too many expressions.

Then, we add the actual procedure that converts a let, using an application of a lambda.

(define (let->lambda exp) (let* ((clauses (let-clauses exp)) (body (let-body exp)) (parameter-list (map let-clause-name clauses)) (argument-list-exp (map let-clause-expression clauses))) `((lambda ,parameter-list ,@body) ,@argument-list-exp)))

From a let expression we first extract the clauses, and the body. Then from the list of clauses we retrieve the variable names they want to define inside the new scope, and the argument expression to evaluate in the current scope.

Note that clauses is a list of clauses. Therefore we can make use of map in order to extract the parameters and arguments for the corresponding equivalent program.

After everything is extracted, it can be converted.

Download solution

Section 3: Special Forms

Exercise 4: Implementing when

We have already implemented when before by converting an expression using when to something using only if and begin. This exercise repeats the previous one, without converting the program into another form.

@@ -20,4 +20,5 @@ (eval-sequence (begin-actions exp) env)) ((cond? exp) (eval (cond->if exp) env)) + ((when? exp) (eval-when exp env)) ;; Add your special forms here! ((application? exp)

And the actual implementation of eval-when...

(define (when? exp) (tagged-list? exp 'when)) (define (when-condition exp) (cadr exp)) (define (when-body exp) (cddr exp)) (define (eval-when exp env) (if (true? (eval (when-condition exp) env)) (eval-sequence (when-body exp) env) #f))

Download solution

Exercise 5: Implementing let

We start this exercise for the fourth time by modifying eval...

@@ -20,4 +20,5 @@ (eval-sequence (begin-actions exp) env)) ((cond? exp) (eval (cond->if exp) env)) + ((let? exp) (eval-let exp env)) ;; Add your special forms here! ((application? exp)

Then we repurpose the accessor procedures from before...

(define (let? exp) (tagged-list? exp 'let)) (define (let-body exp) (cddr exp)) (define (let-clauses exp) (cadr exp)) (define (let-clause-name clause) (car clause)) (define (let-clause-expression clause) (cadr clause))

Then we implement the procedure eval-let.

(define (eval-let exp env) (let* ((clauses (let-clauses exp)) (body (let-body exp)) (parameter-list (map let-clause-name clauses)) (argument-list-exp (map let-clause-expression clauses)) (argument-list-val (map (lambda (exp) (eval exp env)) argument-list-exp))) (eval-sequence body (extend-environment parameter-list argument-list-val env))))

At first sight, this seems difficult to understand, since a lot is going on at once.

As in exercise 3, the clauses, body, and names of the let are extracted. However, instead of retrieving only the expression of a clause in the let, the value needs to be evaluated. Therefore the value stored in values should be a list of values after evaluating every clause.

We pass an anonymous procedure to map that first extracts the expression of the clause, and then evaluates that expression in the environment given to eval-let.

After everything has been extracted, and the arguments have been evaluated, the body is evaluated in the extended environment.

In order to extend the environment we make use of extend-environment. This procedure takes 3 arguments...

1. A list of variable names
2. A list of values
3. The base environment (the environment to extend)

This procedure is currently only being used for procedure application. However, it can be used for evaluating a let as well. We pass it the list of variable names from the let, the values that were evaluated by evaluating the expression of the let, and we pass the current environment as the environment that has to be extended.

After the new environment has been created, the body (which is a sequence of expressions) is evalauted in that new environment, the return value of the let, is the result of evaluating that expression.

Download solution