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.