Placeholder Image

字幕表 動画を再生する

  • 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.