[edit]

Homework 11

Exercise 0.

Some warmup questions to check your understanding:

List all the procedures in the metacircular evaluator that call mc-eval.
List all the procedures in the metacircular evaluator that call mc-apply.
Explain why make-procedure does not call mc-eval.

A Note on Homework 11

Some students have complained that this week's homework is very time-consuming.

Accordingly, with some reluctance, we've marked a few exercises as optional; these are the ones to leave out if you're really pressed for time. But it's much better if you do all of them!

The optional exercises have * next to them.

Template

You can copy the template for this homework by typing the following in your terminal:

  cp ~cs61as/autograder/templates/hw11.scm .

Or, you can download it here.

Exercise 1.

Abelson & Sussman, exercises 4.3, 4.6, 4.7, 4.10, 4.11*, 4.13, 4.14, and 4.15.

Exercise 4.

Abelson & Sussman, exercises 4.1, 4.2, 4.4, and 4.5.

Exercise 2*.

Modify the metacircular evaluator to allow type-checking of arguments to procedures. Here is how the feature should work. When a new procedure is defined, a formal parameter can be either a symbol as usual or else a list of two elements. In this case, the second element is a symbol, the name of the formal parameter. The first element is an expression whose value is a predicate function that the argument must satisfy. That function should return #t if the argument is valid. For example, here is a procedure foo that has typechecked parameters num and list:

> (define (foo (integer? num) ((lambda (x) (not (null? x))) lst))
    (list-ref lst num))
> (foo 3 '(a b c d e))
d
> (foo 3.5 `(a b c d e))
Error: wrong argument type -- 3.5
> (foo 2 '())
Error: wrong argument type -- ()

In this example we define a procedure foo with two formal parameters, named num and list. When foo is invoked, the evaluator will check to see that the first actual argument is an integer and that the second actual argument is not empty. The expression whose value is the desired predicate function should be evaluated with respect to foo's defining environment. (Hint: Think about extend-environment.)