JOHANN SEBASTIAN BACH]

PROFESSOR: Well, there's one bit of mystery left, which I'd

like to get rid of right now.

And that's that we've been blithely doing things like

cons assuming there's always another one.

That we've been doing these things like car-ing and

cdr-ing and assuming that we had some idea

how this can be done.

Now indeed we said that that's equivalent to having

procedures.

But that doesn't really solve the problem, because the

procedure need all sorts of complicated mechanisms like

environment structures and things like that to work.

And those were ultimately made out of conses in the model

that we had, so that really doesn't solve the problem.

Now the problem here is the glue the data

structure's made out of.

What kind of possible thing could it be?

We've been showing you things like a machine, a computer

that has a controller, and some

registers, and maybe a stack.

And we haven't said anything about, for

example, larger memory.

And I think that's what we have to worry about right now.

But just to make it perfectly clear that this is an

inessential, purely implementational thing, I'd

like to show you, for example, how you can do it

all with the numbers.

That's an easy one.

Famous fellow by the name of Godel, a logician at the end

of the 1930s, invented a very clever way of encoding the

complicated expressions as numbers.

For example--

I'm not saying exactly what Godel's scheme is, because he

didn't use words like cons.

He had other kinds of ways of combining to make expressions.

But he said, I'm going to assign a number to every

algebraic expression.

And the way I'm going to manufacture these numbers is

by combining the numbers of the parts.

So for example, what we were doing our world, we could say

that if objects are represented by numbers, then

cons of x and y could be represented by 2 to the x

times 2 to the y.

Because then we could extract the parts.

We could say, for example, that then car of, say, x is

the number of factors of 2 in x.

And of course cdr is the same thing.

It's the number of factors of 3 in x.

Now this is a perfectly reasonable scheme, except for

the fact that the numbers rapidly get to be much larger

in number of digits than the number of

protons in the universe.

So there's no easy way to use this scheme other than the

theoretical one.

On the other hand, there are other ways of representing

these things.

We have been thinking in terms of little boxes.

We've been thinking about our cons structures as looking

sort of like this.

They're little pigeon holes with things in them.

And of course we arrange them in little trees.

I wish that the semiconductor manufacturers would supply me

with something appropriate for this, but actually what they

do supply me with is a linear memory.

Memory is sort of a big pile of pigeonholes,

pigeonholes like this.

Each of which can hold a certain sized object, a fixed

size object.

So, for example, a complicated list with 25 elements won't

fit in one of these.

However, each of these is indexed by an address.

So the address might be zero here, one here, two here,

three here, and so on.

That we write these down as numbers is unimportant.

What matters is that they're distinct as a way to get to

the next one.

And inside of each of these, we can stuff something into

these pigeonholes.

That's what memory is like, for those of you who haven't

built a computer.

Now the problem is how are we going to impose on this type

of structure, this nice tree structure.

Well it's not very hard, and there have been numerous

schemes involved in this.

The most important one is to say, well assuming that the

semiconductor manufacturer allows me to arrange my memory

so that one of these pigeonholes is big enough to

hold the address of another I haven't made.

Now it actually has to be a little bit bigger because I

have to also install or store some information as to a tag

which describes the kind of thing that's there.

And we'll see that in a second.

And of course if the semiconductor manufacturer

doesn't arrange it so I can do that, then of course I can,

with some cleverness, arrange combinations of these to fit

together in that way.

So we're going to have to imagine imposing this

complicated tree structure on our nice linear memory.

If we look at the first still store, we see a classic scheme

for doing that.

It's a standard way of representing Lisp structures

in a linear memory.

What we do is we divide this memory into two parts.

An array called the cars, and an array called the cdrs.

Now whether those happen to be sequential addresses or

whatever, it's not important.

That's somebody's implementation details.

But there are two arrays here.

Linear arrays indexed by sequential indices like this.

What is stored in each of these

pigeonholes is a typed object.

And what we have here are types which begin with letters

like p, standing for a pair.

Or n, standing for a number.

Or e, standing for an empty list. The end of the list. And

so if we wish to represent an object like this, the list

beginning with 1, 2 and then having a 3 and a 4 as its

second and third elements.

A list containing a list as its first part and then two

numbers as a second and third parts.

Then of course we draw it sort of like this these days, in

box-and-pointer notation.

And you see, these are the three cells that have as their

car pointer the object which is either 1, 2 or 3 or 4.

And then of course the 1, 2, the car of this entire

structure, is itself a substructure which contains a

sublist like that.

What I'm about to do is put down places which are--

I'm going to assign indices.

Like this 1, over here, represents the

index of this cell.

But that pointer that we see here is a reference to the

pair of pigeonholes in the cars and the cdrs that are

labeled by 1 in my linear memory down here.

So if I wish to impose this structure on my linear memory,

what I do is I say, oh yes, why don't we drop

this into cell 1?

I pick one.

There's 1.

And that says that its car, I'm going to

assign it to be a pair.

It's a pair, which is in index 5.

And the cdr, which is this one over here, is a pair which I'm

going to stick into place 2.

p2.

And take a look at p2.

Oh yes, well p2 is a thing whose car is the number 3, so

as you see, an n3.

And whose cdr, over here, is a pair, which lives in place 4.

So that's what this p4 is.

p4 is a number whose value is 4 in its car and whose cdr is

an empty list right there.

And that ends it.

So this is the traditional way of representing this kind of

binary tree in a linear memory.

Now the next question, of course, that we might want to

worry about is just a little bit of implementation.

That means that when I write procedures of the form

assigned a, [UNINTELLIGIBLE] procedures--

lines of register machine code of the form assigned a, the

car of [UNINTELLIGIBLE]

b, what I really mean is addressing these elements.

And so we're going to think of that as a abbreviation for it.

Now of course in order to write that down I'm going to

introduce some sort of a structure called a vector.

And we're going to have something which will reference

a vector, just so we can write it down.

Which takes the name of the vector, or the--

I don't think that name is the right word.

Which takes the vector and the index, and I have to have a

way of setting one of those with something called a vector

set, I don't really care.

But let's look, for example, at then that kind of

implementation of car and cdr.

So for example if I happen to have a register b, which

contains the type index of a pair, and therefore it is the

pointer to a pair, then I could take the car of that and

if I-- write this down--

I might put that in register a.

What that really is is a representation of the assign

to a, the value of vector reffing--

or array indexing, if you will-- or

something, the cars object--

whatever that is--

with the index, b.

And similarly for cdr. And we can do the same thing for

assignment to data structures, if we need to do that sort of

thing at all.

It's not too hard to build that.

Well now the next question is how are we going to do

allocation.

And every so often I say I want a cons.

Now conses don't grow on trees.

Or maybe they should.

But I have to have some way of getting the next one.

I have to have some idea of if their memory is unused that I

might want to allocate from.

And there are many schemes for doing this.

And the particular thing I'm showing you

right now is not essential.

However it's convenient and has been done many times.

One scheme's was called the free list allocation scheme.

What that means is that all of the free memory that there is

in the world is linked together in a linked list,

just like all the other stuff.

And whenever you need a free cell to make a new cons, you

grab the first, one make the free list be the cdr of it,

and then allocate that.

And so what that looks like is something like this.

Here we have the free list starting in 6.

And what that is is a pointer-off to say 8.

So what it says is, this one is free and the

next one is an 8.

This one is free and the next one is in 3, the next one

that's free.

That one's free and the next one is in 0.

That one's free and the next one's in 15.

Something like that.

We can imagine having such a structure.

Given that we have something like that, then it's possible

to just get one when you need it.

And so a program for doing cons, this is what

cons might turn into.

To assign to a register A the result of cons-ing, a B onto

C, the value in this containing B and the value

containing C, what we have to do is get the current

[? type ?] ahead of the freelist, make the free list

be its cdr. Then we have to change the cars to be the

thing we're making up to be in A to be the B, the thing in B.

And we have to make change the cdrs of the thing that's in A

to be C. And then what we have in A is the right new frob,

whatever it is.

The object that we want.

Now there's a little bit of a cheat here that I haven't told

you about, which is somewhere around here I haven't set that

I've the type of the thing that I'm cons-ing up to be a

pair, and I ought to.

So there should be some sort of bits here are being set,

and I just haven't written that down.

We could have arranged it, of course, for the free lift to