quite amazing.

We're going to understand what we mean by a program a little

bit more profoundly than we have up till now.

Up till now, we've been thinking of programs as

describing machines.

So for example, looking at this still store, we see here

is a program for factorial.

And what it is, is a character string description, if you

will, of the wiring diagram of a

potentially infinite machine.

And we can look at that a little bit and

just see the idea.

That this is a sort of compact notation which says, if n is

0, the result is one.

Well here comes n coming into this machine, and if it's 0,

then I control this switch in such a way that the switch

allows the output to be one.

Otherwise, it's n times factorial of n minus one.

Well, I'm computing factorial of n minus one and multiplying

that by n, and, in the case that it's not 0, this switch

makes the output come from there.

Of course, this is a machine with a potentially infinite

number of parts, because factorial occurs within

factorial, so we don't know how deep it has to be.

But that's basically what our notation for programs really

means to us at this point.

It's a character string description, if you will, of a

wiring diagram that could also be drawn some other way.

And, in fact, many people have proposed to me, programming

languages look graphical like this.

I'm not sure I believe there are many advantages.

The major disadvantage, of course, is that it takes up

more space on a page, and, therefore, it's harder to pack

into a listing or to edit very well.

But in any case, there's something very remarkable that

can happen in the competition world which is that you can

have something called a universal machine.

If we look at the second slide, what we see is a

special machine called eval.

There is a machine called eval, and I'm going to show it

to you today.

It's very simple.

What is remarkable is that it will fit on the blackboard.

However, eval is a machine which takes as input a

description of another machine.

It could take the wiring diagram of a

factorial machine as input.

Having done so, it becomes a simulator for the factorial

machine such that, if you put a six in, out comes a 720.

That's a very remarkable sort of machine.

And the most amazing part of it is that it fits on a

blackboard.

By contrast, one could imagine in the analog electronics

world a very different machine, a machine which also

was, in some sense, universal, where you gave a circuit

diagram as one of the inputs, for example, of this little

low-pass filter, one-pole low-pass filter.

And you can imagine that you could, for

example, scan this out--

the scan lines are the signal that's describing what this

machine is to simulate--

then the analog of that which is made out of electrical

circuits, should configure itself into a filter that has

the frequency response specified

by the circuit diagram.

That's a very hard machine to make, and, surely, there's no

chance that I could put it on a blackboard.

So we're going to see an amazing thing today.

We're going to see, on the blackboard,

the universal machine.

And we'll see that among other things, it's extremely simple.

Now, we're getting very close to the real spirit in the

computer at this point.

So I have to show a certain amount of reverence and

respect, so I'm going to wear a suit jacket for the only

time that you'll ever see me wear a suit jacket here.

And I think I'm also going to put on an appropriate hat for

the occasion.

Now, this is a lecturer which I have to warn you--

let's see, normally, people under 40 and who don't have

several children are advised to be careful.

If they're really worried, they should leave. Because

there's a certain amount of mysticism that will appear

here which may be disturbing and cause

trouble in your minds.

Well in any case, let's see, I wish to write for you the

evaluator for Lisp.

Now the evaluator isn't very complicated.

It's very much like all the programs we've seen already.

That's the amazing part of it.

It's going to be-- and I'm going to write it right here--

it's a program called eval.

And it's a procedure of two arguments in expression of an

environment.

And like every interesting

procedure, it's a case analysis.

But before I start on this, I want to tell you some things.

The program we're going to write on the blackboard is

ugly, dirty, disgusting, not the way I would write this is

a professional.

It is written with concrete syntax, meaning you've got

really to use lots of CARs and CDRs which is exactly what I

told you not to do.

That's on purpose in this case, because I want it to be

small, compact, fit on the blackboard so you can get the

whole thing.

So I don't want to use long names like I normally use.

I want to use CAR-CDR because it's short.

Now, that's a trade-off.

I don't want you writing programs like this.

This is purely for an effect.

Now, you're going to have to work a little harder to read

it, but I'm going to try to make it clear

as I'm writing it.

I'm also--

this is a pretty much complete interpreter, but there's going

to be room for putting in more things--

I'm going to leave out definition and assignment,

just because they are not essential, for a mathematical

reason I'll show you later and also they take up more space.

But, in any case, what do we have to do?

We have to do a dispatch which breaks the types of

expressions up into particular classes.

So that's what we're going to have here.

Well, what expressions are there?

Let's look at the kinds of expressions.

We can have things like the numeral three.

What do I want that to do?

I can make choices, but I think right now, I want it to

be a three.

That's what I want.

So that's easy enough.

That means I want, if the thing is a number, the

expression, that I want the expression

itself as the answer.

Now the next possibility is things that we

represent as symbols.

Examples of symbols are things like x, n, eval, number, x.

What do I mean them to be?

Those are things that stand for other things.

Those are the variables of our language.

And so I want to be able to say, for example, that x, for

example, transforms to it's value which might be three.

Or I might ask something like car.

I want to have as its value--

be something like some procedure, which I don't know

what is inside there, perhaps a machine language code or

something like that.

So, well, that's easy enough.

I'm going to push that off on someone else.

If something is a symbol, if the expression is a symbol,

then I want the answer to be the result, looking up the

expression in the environment.

Now the environment is a dictionary which maps the

symbol names to their values.

And that's all it is.

How it's done?

Well, we'll see that later.

It's very easy.

It's easy to make data structures that are tables of

various sorts.

But it's only a table, and this is the access routine for

some table.

Well, the next thing, another kind of expression--

you have things that are described constants that are

not numbers, like 'foo.

Well, for my convenience, I want to syntactically

transform that into a list structure which is, quote foo.

A quoted object, whatever it is, is going to be actually an

abbreviation, which is not part of the evaluator but

happens somewhere else, an abbreviation for an expression

that looks like this.

This way, I can test for the type of the expression as

being a quotation by examining the car of the expression.

So I'm not going to worry about that in the evaluator.

It's happening somewhere earlier in

the reader or something.

If the expression of the expression is quote, then what

I want, I want quote foo to itself evaluate to foo.

It's a constant.

This is just a way of saying that this evaluates to itself.

What is that?

That's the second of the list. It's the second element of the

list. The second element of the list is it's CADR. So I'm

just going to write here, CADR.

What else do we have here?

We have lambda expressions, for example,

lambda of x plus x y.

Well, I going have to have some representation for the

procedure which is the value of an expression, of a lambda

expression.

The procedure here is not the expression lambda x.

That's the description of it, the textual description.

However, what what I going to expect to see here is

something which contains an environment as one of its

parts if I'm implementing a lexical language.

And so what I'd like to see is some type flags.

I'm going to have to be able to distinguish procedures

later, procedures which were produced by lambdas, from ones

that may be primitive.

And so I'm going to have some flag, which I'll just

arbitrarily call closure, just for historical reasons.

Now, to say what parts of this are important.

I'm going to need to know the bound variable

list and the body.

Well, that's the CDR of this, so it's going to be x and plus

x y and some environment.

Now this is not something that users should ever see, this is

purely a representation, internally,

for a procedure object.

It contains a bound variable list, a body, and an

environment, and some type tag saying, I am a procedure.

I'm going to make one now.

So if the CAR of the expression is quote lambda,

then what I'm going to put here is--

I'm going to make a list of closure, the CDR of the

procedure description was everything except the lambda,

and the current environment.

This implements the rule for environments in the

environment model.

It has to do with construction of procedures from lambda

expressions.

The environment that was around at the time the

evaluator encountered the lambda expression is the

environment where the procedure resulting interprets

it's free variables.

So that's part of that.

And so we have to capture that environment as part of the

procedure object.

And we'll see how that gets used later.

There are also conditional expressions of things like

COND of say, p one, e one, p two, e two.

Where this is a predicate, a predicate is a thing that is

either true or false, and the expression to be evaluated if

the predicate is true.

A set of clauses, if you will, that's the

name for such a thing.

So I'm going put that somewhere else.

We're going to worry about that in another piece of code.

So EQ--

if the CAR of the expression is COND, then I'm going to do

nothing more than evaluate the COND, the CDR of the

expression.

That's all the clauses in the environment that I'm given.

Well, there's one more case, arbitrary thing like the sum