PROFESSOR: Last time, we took a look at an explicit control

evaluator for Lisp, and that bridged the gap between all

these high-level languages like Lisp and the query

language and all of that stuff, bridged the gap between

that and a conventional register machine.

And in fact, you can think of the explicit control evaluator

either as, say, the code for a Lisp interpreter if you wanted

to implement it in the assembly language of some

conventional register transfer machine, or, if you like, you

can think of it as the microcode of some machine

that's going to be specially designed to run Lisp.

In either case, what we're doing is we're taking a

machine that speaks some low-level language, and we're

raising the machine to a high-level language like Lisp

by writing an interpreter.

So for instance, here, conceptually, is a special

purpose machine for computing factorials.

It takes in five and puts out 120.

And what this special purpose machine is is actually a Lisp

interpreter that's configured itself to run factorials,

because you fit into it a description of

the factorial machine.

So that's what an interpreter is.

It configures itself to emulate a machine whose

description you read in.

Now, inside the Lisp interpreter, what's that?

Well, that might be your general register language

interpreter that configures itself to behave like a Lisp

interpreter, because you put in a whole bunch of

instructions in register language.

This is the explicit control evaluator.

And then it also has some sort of library, a library of

primitive operators and Lisp operations and all sorts of

things like that.

That's the general strategy of interpretation.

And the point is, what we're doing is we're writing an

interpreter to raise the machine to the level of the

programs that we want to write.

Well, there's another strategy, a different one,

which is compilation.

Compilation's a little bit different.

Here--here we might have produced a special purpose

machine for, for computing factorials, starting with some

sort of machine that speaks register language, except

we're going to do a different strategy.

We take our factorial program.

We use that as the source code into a compiler.

What the compiler will do is translate that factorial

program into some register machine language.

And this will now be not the explicit control evaluator for

Lisp, this will be some register language for

computing factorials.

So this is the translation of that.

That will go into some sort of loader which will combine this

code with code selected from the library to do things like

primitive multiplication.

And then we'll produce a load module which configures the

register language machine to be a special

purpose factorial machine.

So that's a, that's a different strategy.

In interpretation, we're raising the machine to the

level of our language, like Lisp.

In compilation, we're taking our program and lowering it to

the language that's spoken by the machine.

Well, how do these two strategies compare?

The compiler can produce code that will execute more

efficiently.

The essential reason for that is that if you think about the

register operations that are running, the interpreter has

to produce register operations which, in principle, are going

to be general enough to execute any Lisp procedure.

Whereas the compiler only has to worry about producing a

special bunch of register operations for, for doing the

particular Lisp procedure that you've compiled.

Or another way to say that is that the interpreter is a

general purpose simulator, that when you read in a Lisp

procedure, then those can simulate the program described

by that, by that procedure.

So the interpreter is worrying about making a general purpose

simulator, whereas the compiler, in effect, is

configuring the thing to be the machine that the

interpreter would have been simulating.

So the compiler can be faster.

On the other hand, the interpreter is a nicer

environment for debugging.

And the reason for that is that we've got the source code

actually there.

We're interpreting it.

That's what we're working with.

And we also have the library around.

See, the interpreter--the library sitting there is part

of the interpreter.

The compiler only pulls out from the library what it needs

to run the program.

So if you're in the middle of debugging, and you might like

to write a little extra program to examine some run

time data structure or to produce some computation that

you didn't think of when you wrote the program, the

interpreter can do that perfectly well, whereas the

compiler can't.

So there are sort of dual, dual advantages.

The compiler will produce code that executes faster.

The interpreter is a better environment for debugging.

And most Lisp systems end up having both, end up being

configured so you have an interpreter that you use when

you're developing your code.

Then you can speed it up by compiling.

And very often, you can arrange that compiled code and

interpreted code can call each other.

We'll see how to do that.

That's not hard.

In fact, the way we'll--

in the compiler we're going to make, the way we'll arrange

for compiled coding and interpreted code to call, to

call each other, is that we'll have the compiler use exactly

the same register conventions as the interpreter.

Well, the idea of a compiler is very much like the idea of

an interpreter or evaluator.

It's the same thing.

See, the evaluator walks over the code and performs some

register operations.

That's what we did yesterday.

Well, the compiler essentially would like to walk over the

code and produce the register operations that the evaluator

would have done were it evaluating the thing.

And that gives us a model for how to implement a

zeroth-order compiler, a very bad compiler but

essentially a compiler.

A model for doing that is you just take the evaluator, you

run it over the code, but instead of executing the

actual operations, you just save them away.

And that's your compiled code.

So let me give you an example of that.

Suppose we're going to compile--suppose we want to

compile the expression f of x.

So let's assume that we've got f of x in the x register and

something in the environment register.

And now imagine starting up the evaluator.

Well, it looks at the expression and it sees that

it's an application.

And it branches to a place in the evaluator code we saw

called ev-application.

And then it begins.

It stores away the operands and unev, and then it's going

to put the operator in exp, and it's going to go

recursively evaluate it.

That's the process that we walk through.

And if you start looking at the code, you start seeing

some register operations.

You see assign to unev the operands, assign to exp the

operator, save the environment, generate

that, and so on.

Well, if we look on the overhead here, we can see, we

can see those operations starting to be produced.

Here's sort of the first real operation that the evaluator

would have done.

It pulls the operands out of the exp register and assigns

it to unev. And then it assigns something to the

expression register, and it saves continue, and it saves

env.

And all I'm doing here is writing down the register

assignments that the evaluator would have done in

executing that code.

And can zoom out a little bit.

Altogether, there are about 19 operations there.

And this is the--this will be the piece of code up until the

point where the evaluator branches off to

apply-dispatch.

And in fact, in this compiler, we're not going to worry about

apply-dispatch at all.

We're going to have everything--we're going to

have both interpreted code and compiled code.

Always evaluate procedures, always apply procedures by

going to apply-dispatch.

That will easily allow interpreted code and compiled

code to call each other.

Well, in principle, that's all we need to do.

You just run the evaluator.

So the compiler's a lot like the evaluator.

You run it, except it stashes away these operations instead

of actually executing them.

Well, that's not, that's not quite true.

There's only one little lie in that.

What you have to worry about is if you have a, a predicate.

If you have some kind of test you want to do, obviously, at

the point when you're compiling it, you don't know

which branch of these--of a conditional like this you're

going to do.

So you can't say which one the evaluator would have done.

So all you do there is very simple.

You compile both branches.

So you compile a structure that looks like this.

That'll compile into something that says, the code, the code

for P. And it puts its results in, say, the val register.

So you walk the interpreter over the predicate and make

sure that the result would go into the val register.

And then you compile an instruction that says, branch

if, if val is true, to a place we'll call label one.

Then we, we will put the code for B to walk the

interpreter--walk the interpreter over B. And then

go to put in an instruction that says, go to the next

thing, whatever, whatever was supposed to happen after this

thing was done.

You put in that instruction.

And here you put label one.

And here you put the code for A. And you

put go to next thing.

So that's how you treat a conditional.

You generate a little block like that.

And other than that, this zeroth-order compiler is the

same as the evaluator.

It's just stashing away the instructions instead of

executing them.

That seems pretty simple, but we've gained

something by that.

See, already that's going to be more

efficient than the evaluator.

Because, if you watch the evaluator run, it's not only

generating the register operations we wrote down, it's

also doing things to decide which ones to generate.

So the very first thing it does, say, here for instance,

is go do some tests and decide that this is an application,

and then branch off to the place that, that handles

applications.

In other words, what the evaluator's doing is

simultaneously analyzing the code to see what to do, and

running these operations.

And when you--

if you run the evaluator a million times, that analysis

phase happens a million times, whereas in the compiler, it's

happened once, and then you just have the register

operations themselves.

Ok, that's a, a zeroth-order compiler, but it is a

wretched, wretched compiler.

It's really dumb.

Let's--let's go back and, and look at this overhead.

So look at look at some of the operations

this thing is doing.

We're supposedly looking at the operations and

interpreting f of x.

Now, look here what it's doing.

For example, here it assigns to exp the

operator in fetch of exp.

But see, there's no reason to do that, because this is--