字幕表 動画を再生する
PROFESSOR: Well, I hope you appreciate that we have
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.