Placeholder Image

Subtitles section Play video

  • [MUSIC PLAYING]

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