The Metacircular Evaluator

The metacircular evaluator is what we've been working towards for much of this class. It's a grown-up version of Scheme-1 that supports define and set!. It's also an implementation of the Environment Model of Evaluation, which means it follows all the rules for lambda-created procedures and procedure calls that regular Scheme does.

What does "metacircular" mean? Well, it's "circular" because it's an implementation of Scheme using Scheme. But it's "meta" because we're building a new Scheme on top of STk. Ergo, "metacircular". (That, or Abelson and Sussman just thought it sounded cool.)

(What's an "evaluator"? Pretty much the same as an "interpreter" — it's a program that takes in expressions and evaluates them. The ultimate in DDP: a Scheme interpreter doesn't do anything on its own, but can be programmed to do everything.)

An interesting thing about implementing an evaluator is that your new language can have features that your implementation language might not. For example, we saw in lab that you can force arguments to be evaluated right-to-left in MCE-Scheme, even though Scheme doesn't guarantee an order and STk actually uses left-to-right. A more subtle point is that the metacircular evaluator doesn't use any higher-order procedures.

No, really. Go check if you don't believe me.

MCE-Scheme supports higher-order procedures just fine, of course. This proves you can implement higher-order procedures even in a language that doesn't have them, like C.

For those who know C, this is not exactly true anymore! Both C++0x "lambdas" and Apple's "blocks" are implementations of lambda / closures / higher-order procedures in C, and they're already supported in some of the most popular compilers.

Okay, enough talk. The most important procedures in the Metacircular Evaluator are, as you'd expect, mc-eval and mc-apply.

mc-eval

(define (mc-eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ((begin? exp) 
         (eval-sequence (begin-actions exp) env))
        ((cond? exp) (mc-eval (cond->if exp) env))
        ((application? exp)
         (mc-apply (mc-eval (operator exp) env)
                   (list-of-values (operands exp) env)))
        (else
         (error "Unknown expression type -- EVAL" exp))))

• Give an example of an expression that will be handled by each of the cond clauses in mc-eval.

  (show answer)

  self-evaluating?	3, "hello", #f
  variable?	foo, +
  quoted?	'abc, '(a b c), (quote abc), (quote (a b c))
  assignment?	(set! x 3)
  definition?	(define x 3), (define (sq x) (* x x))
  if?	(if x (+ x 1) 0)
  lambda?	(lambda (x) (* x x))
  begin?	(begin (set! x 3) x)
  cond?	(cond ((= x 0) #f) (else (+ x 1)))
  application?	(sq x), (newline), ((lambda (x) (* x x)) 5)

  The tricky one here was "application". Remember, it comes from the word "apply", meaning "call a procedure". So this is any procedure call, i.e. anything in parentheses that's not a special form!

  (hide answer)

• What part of mc-eval makes this applicative order?

  (show answer)

  Let's remember what applicative order means: when you call a procedure,

  1. First, evaluate all the arguments
  2. Then create a new frame with the argument values
  3. Finally, evaluate the body using that new environment

  (Normal order skips that first step, and leaves the argument expressions unevaluated until you actually need the values.)

  Okay. Well, do we evaluate the arguments before calling a procedure? Yes! We evaluate the arguments right there, using list-of-values, and passing the result to mc-apply. We know STk is going to do the call to list-of-values first, and so we're all right.

  We did something interesting there, though: we depended on the fact that STk uses applicative order. If it used normal order, the call to list-of-values might not happen when we want it to!

  (hide answer)

• Why does mc-eval take an environment as an argument? Which environment is it?

  (show answer)

  What are environments for? They store variables and values. And mc-eval is where we get and set the values of variables. So we definitely need to know which environment we're in, so we can get the correct values.

  "Which environment is it?" It's the current environment! That is, it's the environment we use when looking up and setting variables...which is exactly what we just said.

  (hide answer)

Environments and Procedures in the MCE

How should we represent these very important concepts? Well, we can answer that by thinking about what each thing represents.

• An environment is made up of frames, linked together by their parent arrows. So it's reasonable to represent an environment as a list of frames. The empty list then represents the "empty environment" (no frames), and the cdr of a regular list represents the parent environment (starting with the parent frame).

  What frame has no parent? The global frame. A one-element list represents the global environment, and in the MCE the last element of any environment is always the global frame.

• A frame is just a place to store variables, along with what values they refer to. You might think we should use an association list for this, a list of key-value pairs. Unfortunately, for silly efficiency reasons, the authors of SICP decided to represent frames using a pair whose car is a list of variable names, and whose cdr is the list of their values. The lists are always in sync; the third name in the first list corresponds to the third value in the second list.

• A primitive is a procedure that's implemented by magic, i.e. by our underlying Scheme. We still want to be able to recognize primitives, though, so we use tagged data, where the tag is the word primitive and the contents is just the STk procedure.

  Note that an MCE "primitive" just means "something STk will handle". That is, it's perfectly okay to put an STk lambda-procedure into MCE as a "primitive" in this way.

• A compound or lambda procedure is a procedure that the user typed in as input to the MCE. We need to make sure we store all of the information in the "double-bubbles" of our environment diagram, so we store these procedures as a list of the parameters, the body, and the current environment at the time the procedure was created (the "right-bubble environment"). To keep things straight, we also type-tag these procedures with the word compound.

But these are ADTs as well. The code for the Metacircular Evaluator has a lot of selectors for each of these, and you can mostly just say what you mean (procedure-body, extend-environment, etc.) when you work with these.

mc-apply

(define (mc-apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters procedure)
             arguments
             (procedure-environment procedure))))
        (else
         (error
          "Unknown procedure type -- APPLY" procedure))))

• When we do environment diagrams, we always create a new frame whenever we call a procedure. Where does that happen in mc-apply?

  (show answer)

  "Creating a new frame" is pretty much the same thing as "extending an (existing) environment", since every new frame has to be attached to some parent environment. So this happens when we call extend-environment.

  (hide answer)

• Why doesn't mc-apply take an environment as an argument?

  (show answer)

  Well, we said environments deal with variables. But mc-apply only works with values: both the procedure and arguments have already been evaluated.

  But don't we need an environment to extend? Well, yes, but in Scheme, we extend the environment stored in the procedure (the "right-bubble environment"), which isn't (necessarily) the same as the current environment. And that environment we already have, via the procedure.

  (hide answer)

• Does the metacircular evaluator use dynamic or lexical scope? How do you know?

  (Don't remember what "scope" is?)

  (show answer)

  Lexical scope. Remember, that just means we extend the environment the procedure was created in, the one in the right-bubble of the procedure. (Just like real Scheme!) And that's what we're doing; the third argument to extend-environment is (procedure-environment procedure).

  (hide answer)

• How could we change the metacircular evaluator to use the other scope?

  (show answer)

  Well, in order to use dynamic scope, we just need to extend the current environment instead of the procedure's environment. That means we need to actually pass the current environment to mc-apply after all, and then just use that in the call to extend-environment. It's that easy!

  (hide answer)

Back to Jordy's home page | Course home page