Lab 12:

Metacircular Evaluator

Our evaluator for Lisp will be implemented as a Lisp program. It may seem circular to think about evaluating Lisp programs using an evaluator that is itself implemented in Lisp. However, evaluation is a process, so it is appropriate to describe the evaluation process using Lisp, which, after all, is our tool for describing processes. An evaluator that is written in the same language that it evaluates is said to be metacircular.

The metacircular evaluator is essentially a Scheme formulation of the environment model of evaluation described in section 3.2. Recall that the model has two basic parts:

These two rules describe the essence of the evaluation process, a basic cycle in which expressions to be evaluated in environments are reduced to procedures to be applied to arguments, which in turn are reduced to new expressions to be evaluated in new environments, and so on, until we get down to symbols, whose values are looked up in the environment, and to primitive procedures, which are applied directly (see figure 4.1). This evaluation cycle will be embodied by the interplay between the two critical procedures in the evaluator, eval and apply, which are described in section 4.1.1 (see figure 4.1).

The implementation of the evaluator will depend upon procedures that define the syntax of the expressions to be evaluated. We will use data abstraction to make the evaluator independent of the representation of the language. For example, rather than committing to a choice that an assignment is to be represented by a list beginning with the symbol set! we use an abstract predicate assignment? to test for an assignment, and we use abstract selectors assignment-variable and assignment-value to access the parts of an assignment. Implementation of expressions will be described in detail in section 4.1.2. There are also operations, described in section 4.1.3, that specify the representation of procedures and environments. For example, make-procedure constructs compound procedures, lookup-variable-value accesses the values of variables, and apply-primitive-procedure applies a primitive procedure to a given list of arguments.


finish this during section

Exercise 1.

List all the procedures in the metacircular evaluator that call eval.

Exercise 2.

List all the procedures in the metacircular evaluator that call apply.

Exercise 3.

Explain why make-procedure does not call eval.

Exercise 4.

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

Exercise 5.

In this lab exercise you will become familiar with the Logo programming language, for which you'll be writing an interpreter in project 4.

To begin, type logo at the Unix shell prompt - not from Scheme! You should see something like this:

Welcome to Berkeley Logo version 5.5

The question mark is the Logo prompt, like the > in Scheme. (Later, in some of the examples below, you'll see a > prompt from Logo, while in the middle of defining a procedure.)

  1. Type each of the following instruction lines and note the results. (A few of them will give error messages.) If you can't make sense of a result, ask for help.

    print 2 + 3
    print 2+3
    print sum 2 3
    print (sum 2 3 4 5)
    print sum 2 3 4 5
    print "yesterday
    print "julia"
    print revolution
    print [blue jay way]
    show [eight days a week]
    show first [golden slumbers]
    print first bf [she loves you]
    pr first first bf [yellow submarine]
    to second :stuff
    output first bf :stuff
    second "something
    print second "piggies
    pr second [another girl]
    pr first second [carry that weight]
    pr second second [i dig a pony]
    to pr2nd :thing
    print first bf :thing
    pr2nd [the 1 after 909]
    print first pr2nd [hey jude]
    repeat 5 [print [this boy]]
    if 3 = 1+1 [print [the fool on the hill]]
    print ifelse 2=1+1 ~
    [second [your mother should know]] ~
    [first "help]
    print ifelse 3=1+2 ~
    [strawberry fields forever] ~
    [penny lane]
    print ifelse 4=1+2 ~
    ["flying] ~
    [[all you need is love]]
    to greet :person
    say [how are you,]
    to say :saying
    print sentence :saying :person
    greet "ringo
    show map "first [paperback writer]
    show map [word first ? last ?] ~
    [lucy in the sky with diamonds]
    to who :sent
    foreach [pete roger john keith] "describe
    to describe :person
    print se :person :sent
    who [sells out]
    print :bass
    make "bass "paul
    print :bass
    print bass
    to bass
    output [johnny cymbal]
    print bass
    print :bass
    print "bass
    to countdown :num
    if :num=0 [print "blastoff stop]
    print :num
    countdown :num-1
    countdown 5
    to downup :word
    print :word
    if emptyp bl :word [stop]
    downup bl :word
    print :word
    downup "rain
    ;;;; The following stuff will work
    ;;;; only on an X workstation:
    repeat 4 [forward 100 rt 90]
    repeat 10 [repeat 5 [fd 150 rt 144] rt 36]
    cs repeat 36 [repeat 4 [fd 100 rt 90]
                 setpc remainder pencolor+1 8
                 rt 10]
    to tree :size
    if :size < 3 [stop]
    fd :size/2
    lt 30 tree :size*3/4 rt 30
    fd :size/3
    rt 45 tree :size*2/3 lt 45
    fd :size/6
    bk :size
    cs pu bk 100 pd ht tree 100
  3. Devise an example that demonstrates that Logo uses dynamic scope rather than lexical scope. Your example should involve the use of a variable that would have a different value if Logo used lexical scope. Test your code with Berkeley Logo.

  4. Explain the differences and similarities among the Logo operators " (double-quote), [ ] (square brackets), and : (colon).


do this in section if possible; finish the rest at home


Some students have complained that this weeks homework is very time-consuming. Accordingly, with some reluctance, I'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 ones have * next to them.

Exercise 6.

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

Exercise 7*.

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))) list))
    (list-ref list num))
> (foo 3 '(a b c d e))
> (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.)

Exercise 8.

Do the following reading:

Extra for Experts

Do this if you want to. This is NOT for credit.

Exercise 9.

Abelson & Sussman, exercises 4.16 - 4.21.