字幕列表 影片播放 列印英文字幕 [MUSIC PLAYING - "JESU, JOY OF MAN'S DESIRING" BY JOHANN SEBASTIAN BACH] PROFESSOR: Well, up 'til now, I suppose, we've been learning about a lot of techniques for organizing big programs, symbolic manipulation a bit, some of the technology that you use for establishing languages, one in terms of another, which is used for organizing very large programs. In fact, the nicest programs I know look more like a pile of languages than like a decomposition of a problem into parts. Well, I suppose at this point, there are still, however, a few mysteries about how this sort of stuff works. And so what we'd like to do now is diverge from the plan of telling you how to organize big programs, and rather tell you something about the mechanisms by which these things can be made to work. The main reason for this is demystification, if you will, that we have a lot of mysteries left, like exactly how it is the case that a program is controlled, how a computer knows what the next thing to do is, or something like that. And what I'd like to do now is make that clear to you, that even if you've never played with a physical computer before, the mechanism is really very simple, and that you can understand it completely with no trouble. So I'd like to start by imagining that we-- well, the way we're going to do this, by the way, is we're going to take some very simple Lisp programs, very simple Lisp programs, and transform them into hardware. I'm not going to worry about some intermediate step of going through some existing computer machine language and then showing you how that computer works, because that's not as illuminating. So what I'm really going to show you is how a piece of machinery can be built to do a job that you have written down as a program. That program is, in fact, a description of a machine. We're going to start with a very simple program, proceed to show you some simple mechanisms, proceed to a few more complicated programs, and then later show you a not very complicated program, how the evaluator transforms into a piece of hardware. And of course at that point, you have made the universal transition and can execute any program imaginable with a piece of well-defined hardware. Well, let's start up now, give you a real concrete feeling for this sort of thing. Let's start with a very simple program. Here's Euclid's algorithm. It's actually a little bit more modern than Euclid's algorithm. Euclid's algorithm for computing the greatest common divisor of two numbers was invented 350 BC, I think. It's the oldest known algorithm. But here we're going to talk about GCD of A and B, the Greatest Common Divisor or two numbers, A and B. And the algorithm is extremely simple. If B is 0, then the result is going to be A. Otherwise, the result is the GCD of B and the remainder when A is divided by B. So this we have here is a very simple iterative process. This a simple recursive procedure, recursively defined procedure, recursive definition, which yields an iterative process. And the way it works is that every step, it determines whether B was zero. And if B is 0, we got the answer in A. Otherwise, we make another step where A is the old B, and B is the remainder of the old A divided by the old B. Very simple. Now this, I've already told you some of the mechanism by just saying it that way. I set it in time. I said there are certain steps, and that, in fact, one of the things you can see here is that one of the reasons why this is iterative is nothing is needed of the last step to get the answer. All of the information that's needed to run this algorithm is in A and B. It has two well-defined state variables. So I'm going to define a machine for you that can compute you GCDs. Now let's see. Every computer that's ever been made that's a single-process computer, as opposed to a multiprocessor of some sort, is made according to the same plan. The plan is the computer has two parts, a part called the datapaths, and a part called the controller. The datapaths correspond to a calculator that you might have. It contains certain registers that remember things, and you've all used calculators. It has some buttons on it and some lights. And so by pushing the various buttons, you can cause operations to happen inside there among the registers, and some of the results to be displayed. That's completely mechanical. You could imagine that box has no intelligence in it. Now it might be very impressive that it can produce the sine of a number, but that at least is apparently possibly mechanical. At least, I could open that up in the same way I'm about to open GCD. So this may have a whole computer inside of it, but that's not interesting. Addition is certainly simple. That can be done without any further mechanism. Now also, if we were to look at the other half, the controller, that's a part that's dumb, too. It pushes the buttons. It pushes them according to the sequence, which is written down on a piece of paper, and observes the lights. And every so often, it comes to a place in a sequence that says, if light A is on, do this sequence. Otherwise, do that sequence. And thereby, there's no complexity there either. Well, let's just draw that and see what we feel about that. So for computing GCDs, what I want you to think about is that there are these registers. A register is a place where I store a number, in this case. And this one's called a. And then there's another one for storing b. Now we have to see what things we can do with these registers, and they're not entirely obvious what you can do with them. Well, we have to see what things we need to do with them. We're looking at the problem we're trying to solve. One of the important things for designing a computer, which I think most designers don't do, is you study the problem you want to solve and then use what you learn from studying the problem you want to solve to put in the mechanisms needed to solve it in the computer you're building, no more no less. Now it may be that the problem you're trying to solve is everybody's problem, in which case you have to build in a universal interpreter of some language. But you shouldn't put any more in than required to build the universal interpreter of some language. We'll worry about that in a second. OK, going back to here, let's see. What do we have to be able to do? Well, somehow, we have to be able to get B into A. We have to be able to get the old value of B into the value of A. So we have to have some path by which stuff can flow, whatever this information is, from b to a. I'm going to draw that with by an arrow saying that it is possible to move the contents of b into a, replacing the value of a. And there's a little button here which you push which allows that to happen. That's what the little x is here. Now it's also the case that I have to be able to compute the remainder of a and b. Now that may be a complicated mess. On the other hand, I'm going to make it a small box. If we have to, we may open up that box and look inside and see what it is. So here, I'm going to have a little box, which I'm going to draw this way, which we'll call the remainder. And it's going to take in a. That's going to take in b. And it's going to put out something, the remainder of a divided by b. Another thing we have to see here is that we have to be able to test whether b is equal to 0. Well, that means somebody's got to be looking at-- a thing that's looking at the value of b. I have a light bulb here which lights up if b equals 0. That's its job. And finally, I suppose, because of the fact that we want the new value of a to be the old value of b, and simultaneously the new value of b to be something I've done with a, and if I plan to make my machine such that everything happens one at a time, one motion at a time, and I can't put two numbers in a register, then I have to have another place to put one while I'm interchanging. OK? I can't interchange the two things in my hands, unless I either put two in one hand and then pull it back the other way, or unless I put one down, pick it up, and put the other one, like that, unless I'm a juggler, which I'm not, as you can see, in which case I have a possibility of timing errors. In fact, much of the type of computer design people do involves timing errors, of some potential timing errors, which I don't much like. So for that reason, I have to have a place to put the second one of them down. So I have a place called t, which is a register just for temporary, t, with a button on it. And then I'll take the result of that, since I have to take that and put into b, over here, we'll take the result of that and go like this, and a button here. So that's the datapaths of a GCD machine. Now what's the controller? Controller's a very simple thing, too. The machine has a state. The way I like to visualize that is that I've got a maze. And the maze has a bunch of places connected by directed arrows. And what I have is a marble, which represents the state of the controller. The marble rolls around in the maze. Of course, this analogy breaks down for energy reasons. I sometimes have to pump the marble up to the top, because it's going to otherwise be a perpetual motion machine. But not worrying about that, this is not a physical analogy. This marble rolls around. And every time it rolls around certain bumpers, like in a pinball machine, it pushes one of these buttons. And every so often, it comes to a place, which is a division, where it has to make a choice. And there's a flap, which is controlled by this. So that's a really mechanical way of thinking about it. Of course, controllers these days, are not built that way in real computers. They're built with a little bit of ROM and a state register. But there was a time, like the DEC PDP-6, where that's how you built the controller of a machine. There was a bit that ran around the delay line, and it triggered things as it went by. And it would come back to the beginning and get fed round again. And of course, there were all sorts of great bugs you could have like two bits going around, two marbles. And then the machine has lost its marbles. That happens, too. Oh, well. So anyway, for this machine, what I have to do is the following. I'm going to start my maze here. And the first thing I've got to do, in a notation which many of you are familiar with, is b equal to zero, a test. And there's a possibility, either yes, in which case I'm done. Otherwise, if no, then I'm going have to roll over some bumpers. I'm going to do it in the following order. I want to do this interchange game. Now first, since I need both a and b, but then the first-- and this is not necessary-- I want to collect this. This is the thing that's going to go into b. So I'm going to say, take this, which depends upon both a and b, and put the remainder into here. So I'm going to push this button first. Then, I'm going to transfer b to a, push that button, and then I transfer the temporary into b, push that button. So a very sequential machine, it's very inefficient. But that's fine right now. We're going to name the buttons, t gets remainder. a gets b.