inducted you into some real magic, the magic of building

languages, really building new languages.

What have we looked at?

We've looked at an Escher picture language: this

language invented by Peter Henderson.

We looked at digital logic language.

Let's see.

We've looked at the query language.

And the thing you should realize is, even though these

were toy examples, they really are the kernels of really

useful things.

So, for instance, the Escher picture language was taken by

Henry Wu, who's a student at MIT, and developed into a real

language for laying out PC boards based just on extending

those structures.

And the digital logic language, Jerry mentioned when

he showed it to you, was really extended to be used as

the basis for a simulator that was used to

design a real computer.

And the query language, of course, is kind

of the germ of prologue.

So we built all of these languages, they're

all based on LISP.

A lot of people ask what particular problems is LISP

good for solving for?

The answer is LISP is not good for solving any particular

problems. What LISP is good for is constructing within it

the right language to solve the problems you want to

solve, and that's how you should think about it.

So all of these languages were based on LISP.

Now, what's LISP based on?

Where's that come from?

Well, we looked at that too.

We looked at the meta-circular evaluator and said well, LISP

is based on LISP.

And when we start looking at that, we've got to do some

real magic, right?

So what does that mean, right?

Why operators, and fixed points, and the idea that what

this means is that LISP is somehow the fixed-point

equation for this funny set of things which are defined in

terms of themselves.

Now, it's real magic.

Well, today, for a final piece of magic, we're going to make

all the magic go away.

We already know how to do that.

The idea is, we're going to take the register machine

architecture and show how to implement

LISP on terms of that.

And, remember, the idea of the register machine is that

there's a fixed and finite part of the machine.

There's a finite-state controller, which does some

particular thing with a particular amount of hardware.

There are particular data paths: the operation the

machine does.

And then, in order to implement recursion and

sustain the illusion of infinity, there's some large

amount of memory, which is the stack.

So, if we implement LISP in terms of a register machine,

then everything ought to become, at this point,

completely concrete.

All the magic should go away.

And, by the end of this talk, I want you get the feeling

that, as opposed to this very mysterious meta-circular

evaluator, that a LISP evaluator really is something

that's concrete enough that you can hold in the

palm of your hand.

You should be able to imagine holding a

LISP interpreter there.

All right, how are we going to do this?

We already have all the ingredients.

See, what you learned last time from Jerry is how to take

any particular couple of LISP procedures and hand-translate

them into something that runs on a register machine.

So, to implement all of LISP on a register machine, all we

have to do is take the particular procedures that are

the meta-circular evaluator and hand-translate them for a

register machine.

And that does all of LISP, right?

So, in principle, we already know how to do this.

And, indeed, it's going to be no different, in kind, from

translating, say, recursive factorial

or recursive Fibonacci.

It's just bigger and there's more of it.

So it'd just be more details, but nothing really

conceptually new.

All right, also, when we've done that, and the thing is

completely explicit, and we see how to implement LISP in

terms of the actual sequential register operations, that's

going to be our final most explicit model of

LISP in this course.

And, remember, that's a progression

through this course.

We started out with substitution, which is sort of

like algebra.

And then we went to the environment model, which

talked about the actual frames and how

they got linked together.

And then we made that more concrete in the

meta-circular evaluator.

There are things the meta-circular evaluator

doesn't tell us.

You should realize that.

For instance, it left unanswered the question of how

a procedure, like recursive factorial here , somehow takes

space that grows.

On the other hand, a procedure which also looks syntactically

recursive, called fact-iter, somehow doesn't take space.

We justify that it doesn't need to take space by showing

the substitution model.

But we didn't really say how it happens that the machine

manages to do that, that that has to do with the details of

how arguments are passed to procedures.

And that's the thing we didn't see in the meta-circular

evaluator precisely because the way arguments got passed

to procedures in this LISP depended on the way arguments

got passed to procedures in this LISP.

But, now, that's going to become extremely explicit.

OK.

Well, before going on to the evaluator, let me just give

you a sense of what a whole LISP system looks like so you

can see the parts we're going to talk about and the parts

we're not going to talk about.

Let's see, over here is a happy LISP user, and the LISP

user is talking to something called the reader.

The reader's job in life is to take characters from the user

and turn them into data structures in something called

a list structure memory.

All right, so the reader is going to take symbols,

parentheses, and A's and B's, and ones and threes that you

type in, and turn these into actual list structure: pairs,

and pointers, and things.

And so, by the time evaluator is going, there are no

characters in the world.

And, of course, in more modern list systems, there's sort of

a big morass here that might sit between the user and the

reader: Windows systems, and top levels, and mice, and all

kinds of things.

But conceptually, characters are coming in.

All right, the reader transforms these into pointers

to stuff in this memory, and that's what the

evaluator sees, OK?

The evaluator has a bunch of helpers.

It has all possible primitive operators you might want.

So there's a completely separate box, a floating point

unit, or all sorts of things, which do

the primitive operators.

And, if you want more special primitives, you build more

primitive operators, but they're

separate from the evaluator.

The evaluator finally gets an answer and communicates that

to the printer.

And now, the printer's job in life is to take this list

structure coming from the evaluator, and turn it back

into characters, and communicate them to the user

through whatever interface there is.

OK.

Well, today, what we're going to talk

about is this evaluator.

The primitive operators have nothing particular to do with

LISP, they're however you like to implement primitive

operations.

The reader and printer are actually complicated, but

we're not going to talk about them.

They sort of have to do with details of how you might build

up list structure from characters.

So that is a long story, but we're not going

to talk about it.

The list structure memory, we'll talk about next time.

So, pretty much, except for the details of reading and

printing, the only mystery that's going to be left after

you see the evaluator is how you build list structure on

conventional memories.

But we'll worry about that next time too.

OK.

Well, let's start talking about the evaluator.

The one that we're going to show you, of course, is not, I

think, nothing special about it.

It's just a particular register

machine that runs LISP.

And it has seven registers, and here

are the seven registers.

There's a register, called EXP, and its job is to hold

the expression to be evaluated.

And by that, I mean it's going to hold a pointer to someplace

in list structure memory that holds the

expression to be evaluated.

There's a register, called ENV, which holds the

environment in which this expression is to be evaluated.

And, again, I made a pointer.

The environment is some data structure.

There's a register, called FUN, which will hold the

procedure to be applied when you go to apply a procedure.

A register, called ARGL, which wants the list

of evaluated arguments.

What you can start seeing here is the basic

structure of the evaluator.

Remember how evaluators work.

There's a piece that takes expressions and environments,

and there's a piece that takes functions, or

procedures and arguments.

And going back and forth around here is

the eval/apply loop.

So those are the basic pieces of the eval and apply.

Then there's some other things, there's continue.

You just saw before how the continue register is used to

implement recursion and stack discipline.

There's a register that's going to hold the result of

some evaluation.

And then, besides that, there's one temporary

register, called UNEV, which typically, in the evaluator,

is going to be used to hold temporary pieces of the

expression you're working on, which you haven't gotten

around to evaluate yet, right?

So there's my machine: a seven-register machine.

And, of course, you might want to make a machine with a lot

more registers to get better performance, but this is just

a tiny, minimal one.

Well, how about the data paths?

This machine has a lot of special operations for LISP.

So, here are some typical data paths.

A typical one might be, oh, assign to the VAL register the

contents of the EXP register.

In terms of those diagrams you saw, that's a little button on

some arrow.

Here's a more complicated one.

It says branch, if the thing in the expression register is

a conditional to some label here, called the

ev-conditional.

And you can imagine this implemented in a lot of

different ways.

You might imagine this conditional test as a special

purpose sub-routine, and conditional might be

represented as some data abstraction that you don't

care about at this level of detail.

So that might be done as a sub-routine.

This might be a machine with hardware-types, and

conditional might be testing some bits for

a particular code.

There are all sorts of ways that's beneath the level of

abstraction we're looking at.

Another kind of operation, and there are a lot of different

operations assigned to EXP, the first clause

of what's in EXP.

This might be part of processing a conditional.

And, again, first clause is some selector whose details we

don't care about.

And you can, again, imagine that as a sub-routine which'll