All the Evaluators and What They're For

I received a request for a review sheet for all the different kinds of evaluators we've worked with. In general, each of them represents a different variation of Scheme: providing some new feature that normal Scheme doesn't support. Let's get a quick overview of all the evaluators we've covered, then examine each of them in a bit more detail.

If you take nothing else away, though, it's to remember that the evaluator is stupid. Don't try to be smart and anticipate what any of them are going to do. Just follow the rules very carefully, and you should be all right. And remember, if an evaluator doesn't explicitly change how something is done, it should be the same as in regular Scheme!

Evaluator	Above-the-Line Changes	Below-the-Line Changes
Metacircular Evaluator	Missing a few Scheme features, like vectors and some special forms.	(reference implementation)
Analyzing Evaluator	None	Analyzes code, including procedure bodies, when it is typed in. A form of compilation.
Lazy Evaluator	Normal-order evaluation (for compound procedure calls)	Arguments to compound procedures are delayed; these promises are forced only when necessary.
Logo Evaluator (Project 4)	Speaks Logo instead of Scheme, has dynamic scope.	Different evaluation model, procedures stored separately from variables.

Metacircular Evaluator

There's not much to say about the metacircular evaluator: it reads, evaluates, prints, and repeats (loops). mc-eval contains a big cond that decides what to do with a given expression, based on what kind of expression it is. Procedure calls are handled by mc-apply, which differentiates between primitive calls (which use the underlying Scheme / STk apply) and compound calls (which are handled within the MCE code). All special forms are checked for and handled "manually", meaning we get little help from the underlying Scheme.

• You should still know how the MCE is put together. For instance, what would you need to change to make the MCE-Scheme use dynamic scope, instead of lexical scope? (You can go look at the MCE code for this.)

  (show answer)

  "Lexical scope" just means that when we call a procedure and make a frame, we extend the environment the procedure was defined in (the right-bubble environment). With dynamic scope, we extend the current environment at the time of the call. This is the only difference between lexical and dynamic scope.

  The new frame for a procedure call is created in mc-apply. All we have to do is change that to use the current environment instead of the procedure's saved environment. This means we have to add an env parameter to mc-apply as well, and change our procedure call clause in mc-eval to deal with that.

  (hide answer)

Analyzing Evaluator

The analyzing evaluator is, from the user's point of view, exactly the same as the "vanilla" unmodified MCE. The difference is in how expressions are handled. Instead of reading each expression and then doing what it says, the analyzing evaluator reads all expressions in advance, then builds a machine (a procedure in the underlying Scheme) that will evaluate the expressions in a given environment. It's like the difference between solving a math problem and writing a program to solve it for you—the first one might be faster for just one problem, but if you have to solve many problems the time spent writing the program will quickly become worth it.

In general, we discount the analyzing evaluator's overhead in "compiling" code that is only run once; while the MCE is technically faster when you just evaluate something once, it's not a very significant difference. The big win for the analyzing evaluator comes when a compound procedure is called over and over. Because the body of the procedure has already been analyzed, there's no need to figure out what to do every time. You just feed in a new environment and get your answer out.

To summarize, if a procedure is called more than once, the analyzing evaluator will be more efficient than the vanilla MCE. If it is only called once, then they both have to "analyze" once, and so the MCE wins on the overhead technicality.

• Is there ever a case where the analyzing evaluator does more analysis or evaluation work than the vanilla MCE?

  (show answer)

  Actually, yes. The vanilla MCE performs analysis every time a procedure is called; the analyzing evaluator, only when it is defined. It stands to reason, then, that if a procedure is never called, the analyzing evaluator will have done more work.

  The two evaluators conceptually always do the same amount of "evaluation", finding an answer in a given environment. This cannot be analyzed ahead of time, since we don't have an environment until the procedure is called.

  (hide answer)

Lazy Evaluator

Now we're coming to something new! The lazy evaluator swaps Scheme's familiar applicative-order evaluation for exotic normal-order evaluation. How does it do this? By delaying every expression until it is absolutely needed. And yes, by delaying we mean promises, though as usual we don't use STk's implementation.

There are a few simple rules to the lazy evaluator:

1. Delay all arguments to a compound procedure call.
2. Force all arguments to a primitive procedure call.
3. Force the condition of an if, so you can actually test it.
4. Force a procedure being called, so you can actually call it.
5. Force a value returned to the top level REPL, so it can be printed as a value and not a promise.

Everything else is the same as the vanilla MCE. Of course, as we've seen a lot, side effects tend to get lost or a little messed up in normal-order evaluation. In a real normal-order system, you should stick to functional programming.

• Let's walk through a problem from some of the other TAs' practice handouts (originally by past TA Chung Wu). Evaluating the last define results in the lazy evaluator hanging. Why?

  > (define count 0)
  > (define (foo x y) (x y))
  > (define z (foo (lambda (a) (set! count a) (* a a))
                   (begin (set! count (+ count 1)) count)))

  (show answer)

  1. The first two definitions happen normally. define is not a compound procedure and so the value subexpression isn't delayed or anything.
  2. The last definition, as usual, starts by trying to evaluate the value expression, which is a call to foo.
  3. foo is a compound procedure, so first, delay both arguments.
  4. Next, call foo with the two promises we just made.
  5. foo's body says to evaluate (x y). Because x is being called, we force it, which creates the lambda. (Note that because delaying something saves its environment, the lambda's right-bubble still points to the global environment.)
  6. x is a compound procedure, so we delay its argument y. Notice that x's argument is a promise to evaluate a promise!
  7. Call x with this new promise.
  8. The set! sets count to this promise (a). Note that set! is a special form, which does not force promises.
  9. Now we multiply a by a. Since * is a primitive, we need to force the promise.
  10. We start by setting count to (+ 1 count). Since + is a primitive, we need to force the value of count…

  …but count has been set to the promise a, the one that starts with begin. In order to evaluate count, we need to force this promise. But in order to force this promise, we need to evaluate count! So we get an infinite loop here.

  For comparison, here's what would happen in the usual applicative order:

  1. The last expression of the last definition is a procedure call, so evaluate the subexpressions.
  2. The procedure is the procedure foo in the global environment, and the first argument is a procedure we're creating right now that takes one argument a
  3. Evaluating the second argument causes us to set count to (+ count 1), which is 1, and then use the new value—1—as our argument
  4. We call foo now with our newly created procedure and the value 1.
  5. foo's body says to evaluate (x y). y, of course, is 1.
  6. The procedure now known as x sets count to 1 (which it already was), and returns (* a a), or 1*1, or 1.

  (hide answer)

Logo Evaluator

The most important differences (besides the syntax, particularly the infix notation) is that Logo uses dynamic scope, and has first-class expressions, rather than first-class procedures. That's how we can have ifelse not be a special form in Logo; there are no special forms except to.

? ifelse 2=3 [print "yes] [print "no]
no
? make first "abc "hi
? :a
hi

You can't do that call to make in Scheme at all, because define (and set!) are special forms!

In addition, Logo allows you to have a procedure and a variable with the same name, and they won't overlap.

? make "first [brian harvey]
? pr first :first
brian

• One other thing Logo has is it doesn't allow defining procedures inside other procedures. Why is this not a problem?

  (show answer)

  In Scheme, we define procedures inside other procedures in order to allow the inner procedures to use variables from the outer ones. But this is a feature of lexical scope, and Logo uses dynamic scope! So there's not really much point to it.

  Of course, the other reason you want to put procedures inside other procedures is so you don't pollute the global namespace with names like helper or iter. That's something Logo doesn't have: a tradeoff of simplicity. (You could probably argue that both sides make things "simpler" in some sense.)

  (hide answer)

Hopefully that was helpful! You should be able to keep all the evaluators straight, and understand what each one adds to the Scheme language. Now go ace this final!

Back to Jordy's home page | Course home page