PROFESSOR: Well, now that we've given you some power to
make independent local state and to model objects, I
thought we'd do a bit of programming of a very
complicated kind, just to illustrate what you can do
with this sort of thing.
I suppose, as I said, we were motivated by physical systems
and the ways we like to think about physical systems, which
is that there are these things that the world is made out of.
And each of these things has particular independent local
state, and therefore it is a thing.
That's what makes it a thing.
And then we're going to say that in the model in the
world--we have a world and a model in our minds and in the
computer of that world.
And what I want to make is a correspondence between the
objects in the world and the objects in the computer, the
relationships between the objects in the world and the
relationships between those same obj...--the model objects
in the computer, and the functions that relate things
in the world to the functions that relate
things in the computer.
This buys us modularity.
If we really believe the world is like that, that it's made
out of these little pieces, and of course we could arrange
our world to be like that, we could only model those things
that are like that, then we can inherit the modularity in
the world into our programming.
That's why we would invent some of this object-oriented
programming.
Well, let's take the best kind of objects I know.
They're completely--they're completely wonderful:
electrical systems. Electrical systems really are the
physicist's best, best objects.
You see over here I have some piece of machinery.
Right here's a piece of machinery.
And it's got an electrical wire connecting one part of
the machinery with another part of the machinery.
And one of the wonderful properties of the electrical
world is that I can say this is an object, and this is an
object, and they're--
the connection between them is clear.
In principle, there is no connection that I didn't
describe with these wires.
Let's say if I have light bulbs, a light bulb and a
power supply that's plugged into the outlet.
Then the connection is perfectly clear.
There's no other connections that we know of.
If I were to tie a knot in the wire that connects the light
bulb to the power supply, the light remains lit up.
It doesn't care.
That the way the physics is arranged is such that the
connection can be made abstract, at least for low
frequencies and things like that.
So in fact, we have captured all of the connections there
really are.
Well, as you can go one step further and talk about the
most abstract types of electrical systems we have,
digital to dual circuits.
And here there are certain kinds of objects.
For example, in digital circuits we
have things like inverters.
We have things like and-gates.
We have things like or-gates.
We connect them together by sort-of wires which represent
abstract signals.
We don't really care as physical variables whether
these are voltages or currents or some combination or
anything like that, or water, water pressure.
These abstract variables represent certain signals.
And we build systems by wiring these things
together with wires.
So today what I'm going to show you, right now, we're
going to build up an invented language in Lisp, embedded in
the same sense that Henderson's picture language
was embedded, which is not the same sense as the language of
pattern match and substitution was done yesterday.
The pattern match/substitution language was interpreted by a
Lisp program.
But the embedding of Henderson's program is that we
just build up more and more procedures that encapsulate
the structure we want.
So for example here, I'm going to have some various primitive
kinds of objects, as you see, that one and that one.
I'm going to use wires to combine them.
The way I represent attaching--
I can make wires.
So let's say A is a wire.
And B is a wire.
And C is a wire.
And D is a wire.
And E is wire.
And S is a wire.
Well, an or-gate that has both inputs, the inputs being A and
B, and the output being Y or D, you notate like this.
An and-gate, which has inputs A and B and output C, we
notate like that.
By making such a sequence of declarations, like this, I can
wire together an arbitrary circuit.
So I've just told you a set of primitives and means of
combination for building digital circuits, when I need
more in a real language than abstraction.
And so for example, here I have--here
I have a half adder.
It's something you all know if you've
done any digital design.
It's used for adding numbers together on A and B and
putting out a sum and a carry.
And in fact, the wiring diagram is
exactly what I told you.
A half adder with things that come out of the box-- you see
the box, the boundary, the abstraction is always a box.
And there are things that come out of it, A, B, S, and C.
Those are the declared variables--declared variables
of a lambda expression, which is the one that
defines half adder.
And internal to that, I make up some more wires, D and E,
which I'm going to use for the interconnect--
here E is this one and D is this wire, the interconnect
that doesn't come through the walls of the box--
and wire things together as you just saw.
And the nice thing about this that I've just shown you is
this language is hierarchical in the right way.
If a language isn't hierarchical in the right way,
if it turns out that a compound object doesn't look
like a primitive, there's something
wrong with the language--
at least the way I feel about that.
So here we have--here, instead of starting with mathematical
functions, or things that compute mathematical
functions, which is what we've been doing up until now,
instead of starting with things that look like
mathematical functions, or compute such things, we are
starting with things that are electrical objects and we
build up more electrical objects.
And the glue we're using is basically the
Lisp structure: lambdas.
Lambda is the ultimate glue, if you will.
And of course, half adder itself can be used in a more
complicated abstraction called a full adder, which in fact
involves two half adders, as you see here, hooked together
with some extra wires, that you see here, S, C1, and C2,
and an or-gate, to manufacture a full adder, which takes a
input number, another input number, a carry in, and
produces output, a sum and a carry out.
And out of full adders, you can make real adder chains and
big adders.
So we have here a language so far that has primitives, means
of combination, and means of abstraction to real language.
Now, how are we going to implement this?
Well, let's do it easily.
Let's look at the primitives.
The only problem is we have to implement the primitives.
Nothing else has to be implemented, because we're
picking up the means of combination and abstraction
from Lisp, inheriting them in the embedding.
OK, so let's look at a particular primitive.
An inverter is a nice one.
Now, inverter has two wires coming in, an in and an out.
And somehow, it's going to have to know what to do when a
signal comes in.
So somehow it's going to have to tell its input wire--
and now we're going to talk about objects and we're going
to see this in a little more detail soon--
but it's going to have to tell its input wire that when you
change, tell me.
So this object, the object which is the inverter has to
tell the object which is the input wire,
hi, my name is George.
And my, my job is to do something with results when
you change.
So when you change, you get a change, tell me about it.
Because I've got to do something with that.
Well, that's done down here by adding an action on the input
wire called invert-in, where invert-in is defined over here
to be a procedure of no arguments, which gets the
logical not of the signal on the input wire.
And after some delay, which is the inverter delay, all these
electrical objects have delays, we'll do the following
thing-- set the signal on the output wire to the new value.
A very simple program.
Now, you have to imagine that the output wire has to be
sensitive and know that when its signal changes, it may
have to tell other guys, hey, wake up.
My value has changed.
So when you hook together inverter with an and-gate or
something like that, there has to be a lot of communication
going on in order to make sure that the
signal propagates right.
And down here is nothing very exciting.
This is just the definition of logical not for some
particular representations of the logical values--
1, 0 in this case.
And we can look at things more complicated like and-gates.
And-gates take two inputs, A1 and A2, we'll call them, and
produce an output.
But the structure of the and-gate is identical to the
one we just saw.
There's one called an and-action procedure that's
defined, which is the thing that gets called when an input
is changed.
And what it does, of course, is nothing more than compute
the logical and of the signals on the inputs.
And after some delay, called the and-gate delay, calls this
procedure, which sets a signal on the output to a new value.
Now, how I implement these things
is all wishful thinking.
As you see here, I have an assignment operation.
It's not set.
It's a derived assignment operation in the same way we
had functions that were derived from CAR and CDR. So
I, by convention, label that with an exclamation point.
And over here, you see there's an action, which is to inform
the wire, called A1 locally in this and-gate, to call the
and-action procedure when it gets changed, and the wire A2
to call the and-action procedure
when it gets changed.
All very simple.
Well, let's talk a little bit about this communication that
must occur between these various parts.
Suppose, for example, I have a very simple circuit which
contains an and with wires A and B. And that connects
through a wire called C to an inverter which has a wire
output called D. What are the comput...--here's
the physical world.
It's an abstraction of the physical world.
Now I can buy these out of little pieces that you get at
Radio Shack for a few cents.
And there are boxes that act like this, which have little
numbers on them like LS04 or something.
Now supposing I were to try to say what's the
computational model.
What is the thing that corresponds to that, that part
of reality in the mind of us and in the computer?
Well, I have to assign for every object in the world an
object in the computer, and for every relationship in the
world between them a relationship in the computer.
That's my goal.
So let's do that.
Well, I have some sort of thing called the signal, A.
This is A. It's a signal.
It's a cloudy thing like that.
And I have another one down here which I'm going to call
B. It's another signal.
Now this signal--these two signals are somehow going to
have to hook together into a box, let's call it this, which
is the and-gate, action procedure.
That's the and-gate's action procedure.
And it's going to produce--well, it's going to
interact with a signal object, which we call C--a wire
object, excuse me, we call C. And then the--
this is going to put out again, or connect to, another
action procedure which is one associated with the inverter
in the world, not.
And I'm going to have another--another wire, which
we'll call D.
So here's my layout of stuff.
Now we have to say what's inside them and what they have
to know to compute.
Well, every--every one of these wires has to know what
the value of the signal that's on that wire is.
So there's going to be some variable inside here, we'll
call it signal.
And he owns a value.
So there must be some environment
associated with this.
And for each one of these, there must be an environment
that binds signal.
And there must be a signal here, therefore.
And presumably, signal's a value that's either 1 or 0,
and signal.
Now, we also have to have some list of people to inform if
the signal here changes.
We're going to have to inform this.
So I've got that list. We'll call it the
Action Procedures, AP.
And it's presumably a list. But the first thing on the
list, in this case, is this guy.
And the action procedures of this one happens to have some
list of stuff.
There might be other people who are sharing A, who are
looking at it.
So there might be other guys on this list, like somebody
over there that we don't know about.
It's the other guy attached to A.
And the action procedure here also has to point to that, the
list of action procedures.
And of course, that means this one, its action procedures has
to point up to here.
This is the things--
the people it has to inform.
And this guy has some too.
But I don't know what they are because I didn't
draw it in my diagram.
It's the things connected to D.
Now, it's also the case that when the and-action procedure
is awakened, saying one of the people who know that you've
told--one of the people you've told to wake you up if their
signal changes, you have to go look and ask them what's their
signal so you can do the and, and produce a
signal for this one.
So there has to be, for example, information here
saying A1, my A1 is this guy, and my A2 is this guy.
And not only that, when I do my and, I'm going to have to
tell this guy something.
So I need an output--
being this guy.
And similarly, this guy's going to have a thing called
the input that he interrogates to find out what the value of
the signal on the input is, when the signal wakes up and
says, I've changed, and sends a message this way saying,
I've changed.
This guy says, OK, what's your value now?
When he gets that value, then he's going to have to say, OK,
output changes this guy, changes this guy.
And so on.
And so I have to have at least that much connected-ness.
Now, let's go back and look, for example, at the and-gate.
Here we are back on this slide.
And we can see some of these parts.
For any particular and-gate, there is an A1, there is an
A2, and the output.
And those are, those are an environment that was created
at the--those produce a frame at the time and-gate was
called, a frame where A1, A2, and output are--have as their
values, they're bound to the wires which, they are--which
were passed in.
In that environment, I constructed a procedure--
this one right there.
And-action procedure was constructed in that
environment.
That was the result of evaluating a lambda
expression.
So it hangs onto the frame where these were defined.
Local--part of its local state is that.
The and-action procedure, therefore, has access to A1,
A2, and output as we see here.
A1, A2, and output.
Now, we haven't looked inside of a wire yet.
That's all that remains.
Let's look at a wire.
Like the overhead, very good.
Well, the wire, again, is a, is a
somewhat complicated mess.
Ooh, wrong one.
It's a big complicated mess, like that.
But let's look at it in detail and see what's going on.
Well, the wire is one of these.
And it has to have two things that are part of
it, that it's state.
One of them is the signal we see here.
In other words, when we call make-wire to make a wire, then
the first thing we do is we create some variables which
are the signal and the action procedures for this wire.
And in that context, we define various functions--or
procedures, excuse me, procedures.
One of them is called set-my-signal to a new value.
And what that does is takes a new value in.
If that's equal to my current value of my signal, I'm done.
Otherwise, I set the signal to the new value and call each of
the action procedures that I've been, that I've
been--what's the right word?--
introduced to.
I get introduced when the and-gate was applied to me.
I add action procedure at the bottom.
Also, I have to define a way of accepting an action
procedure-- which is what you see here---
which increments my action procedures using set to the
result of CONSing up a new process--a procedure, which is
passed to me, on to my actions procedures list. And for
technical reasons, I have to call that procedure one.
So I'm not going to tell you anything about that, that has
to do with event-driven simulations and getting them
started, which takes a little bit of thinking.
And finally, I'm going to define a thing called the
dispatcher, which is a way of passing a message to a wire,
which is going to be used to extract from it various
information, like what is the current signal value?
What is the method of setting your signal?
I want to get that out of it.
How do I--how do I add another action procedure?
And I'm going to return that dispatch, that
procedure as a value.
So the wire that I've constructed is a message
accepting object which accepts a message like, like what's
your method of adding action procedures?
In fact, it'll give me a procedure, which is the add
action procedure, which I can then apply to an action
procedure to create another action procedure in the wire.
So that's a permission.
So it's given me permission to change your action procedures.
And in fact, you can see that over here.
Next slide.
Ah.
This is nothing very interesting.
The call each of the action procedures is just a CDRing
down a list. And I'm not going to even
talk about that anymore.
We're too advanced for that.
However, if I want to get a signal from a
wire, I ask the wire--
which is, what is the wire?
The wire is the dispatch returned by creating the wire.
It's a procedure.
I call that dispatch on the message get-signal.
And what I should expect to get is a method
of getting a signal.
Or actually, I get the signal.
If I want to set a signal, I want to change a signal, then
what I'm going to do is take a wire as an argument and a new
value for the signal, I'm going to ask the wire for
permission to set its signal and use that permission, which
is a procedure, on the new value.
And if we go back to the overhead here, thank you, if
we go back to the overhead here, we see that the method--
if I ask for the method of setting the signal, that's
over here, it's set-my-signal, a procedure that's defined
inside the wire, which if we look over here is the thing
that says set my internal value called the signal, my
internal variable, which is the signal, to the new value,
which is passed to me as an argument, and then call each
of the action procedures waking them up.
Very simple.
Going back to that slide, we also have the one last thing--
which I suppose now you can easily work out for yourself--
is the way you add an action.
You take a wire--a wire and an action procedure.
And I ask the wire for permission to add an action.
Getting that permission, I use that permission to give it an
action procedure.
So that's a real object.
There's a few more details about this.
For example, how am I going to control this thing?
How do I do these delays?
Let's look at that for a second.
The next one here.
Let's see.
We know when we looked at the and-gate or the not-gate that
when a signal changed on the input, there was a delay.
And then it was going to call the procedure, which was going
to change the output.
Well, how are we going to do this?
We're going to make up some mechanism, a fairly
complicated mechanism at that, which we're going to have to
be very careful about.
But after a delay, we're going to do an action.
A delay is a number, and an action is a procedure.
What that's going to be is they're going to have a
special structure called an agenda, which is a thing that
organizes time and actions.
And we're going to see that in a while.
I don't want to get into that right now.
But the agenda has a moment at which--at
which something happens.
We're setting up for later at some moment, which is the sum
of the time, which is the delay time plus the current
time, which the agenda thinks is now.
We're going to set up to do this action, and add that to
the agenda.
And the way this machine will now run is very simple.
We have a thing called propagate, which is the way
things run.
If the agenda is empty, we're done--if there's nothing more
to be done.
Otherwise, we're going to take the first item off the agenda,
and that's a procedure of no arguments.
So that we're going to see extra parentheses here.
We call that on no arguments.
That takes the action.
Then we remove that first item from the agenda, and we go
around the propagation loop.
So that's the overall structure of this thing.
Now, there's a, a few other things we can look at.
And then we're going to look into the agenda a
little while from now.
Now the overhead again.
Well, in order to set this thing going, I just want to
show you some behavior out of this simulator.
By the way, you may think this simulator is very simple, and
probably too simple to be useful.
The fact of the matter is that this simulator has been used
to manufacture a fairly large computer.
So this is a real live example.
Actually, not exactly this simulator, because I'll tell
you the difference.
The difference is that there were many more different kinds
of primitives.
There's not just the word inverter or and-gate.
There were things like edge-triggered, flip-flops,
and latches, transparent latches, and adders, and
things like that.
And the difficulty with that is that there's pages and
pages of the definitions of all these primitives with
numbers like LS04.
And then there's many more parameters for them.
It's not just one delay.
There's things like set up times and hold
times and all that.
But with the exception of that part of the complexity, the
structure of the simulator that we use for building a
real computer, that works is exactly what
you're seeing here.
Well in any case, what we have here is a few simple things.
Like, there's inverter delays being set up and
making a new agenda.
And then we can make some inputs.
There's input-1, input-2, a sum and a
carry, which are wires.
I'm going to put a special kind of object called a probe
onto, onto some of the wires, onto sum and onto carry.
A probe is a, can object that has the property that when you
change a wire it's attached to, it types out a message.
It's an easy thing to do.
And then once we have that, of course, the way you put the
probe on, the first thing it does, it says, the current
value of the sum at time 0 is 0 because I just noticed it.
And the value of the carry at time 0, this is
the time, is 0.
And then we go off and we build some structure.
Like, we can build a structure here that says you have a
half-adder on input-1, input-2, sum, and carry.
And we're going to set the signal on input-1 to 1.
We do some propagation.
At time 8, which you could see going through this thing if
you wanted to, the new value of sum became 1.
And the thing says I'm done.
That wasn't very interesting.
But we can send it some more signals.
Like, we set-signal on input-2 to be one.
And at that time if we propagate, then it carried at
11, the carry becomes 1, and at 16, the sum's new
value becomes 0.
And you might want to work out that, if you like, about the
digital circuitry.
It's true, and it works.
And it's not very interesting.
But that's the kind of behavior we
get out of this thing.
So what I've shown you right now is a large-scale picture,
how you, at a bigger, big scale, you implement an
event-driven simulation of some sort.
And how you might organize it to have nice hierarchical
structure allowing you to build abstract boxes that you
can instantiate.
But I haven't told you any of the details about how this
agenda and things like that work.
That we'll do next.
And that's going to involve change and mutation of data
and things like that.
Are there any questions now, before I go on?
Thank you.
Let's take a break.
Well, we've been making a simulation.
And the simulation is an event-driven simulation where
the objects in the world are the objects in the computer.
And the changes of state that are happening in the world in
time are organized to be time in the computer, so that if
something happens after something else in the world,
then we have it happen after, after the corresponding events
happen in the same order in the computer.
That's where we have assignments, when
we make that alignment.
Right now I want to show you a way of organizing time, which
is an agenda or priority queue, it's sometimes called.
We'll do some--we'll do a little bit of just
understanding what are the things we need to be able to
do to make agendas.
And so we're going to have--and so right now over
here, I'm going to write down a bunch of primitive
operations for manipulating agendas.
I'm not going to show you the code for them because they're
all very simple, and you've got
listings of all that anyway.
So what do we have?
We have things like make-agenda which produces a
new agenda.
We can ask--we get the current-time of an agenda,
which gives me a number, a time.
We can get--we can ask whether an agenda is empty,
empty-agenda.
And that produces either a true or a false.
We can add an object to an agenda.
Actually, what we add to an agenda is an operation--an
action to be done.
And that takes a time, the action itself, and the agenda
I want to add it to.
That inserts it in the appropriate
place in the agenda.
I can get the first item off an agenda, the first thing I
have to do, which is going to give me an action.
And I can remove the first item from an agenda.
That's what I have to be able to do with agendas.
That is a big complicated mess.
From an agenda.
Well, let's see how we can organize this thing as a data
structure a bit.
Well, an agenda is going to be some kind of list. And it's
going to be a list that I'm going to have
to be able to modify.
So we have to talk about modifying of lists, because
I'm going to add things to it, and delete things from it, and
things like that.
It's organized by time.
It's probably good to keep it in sorted order.
But sometimes there are lots of things that happen at the
same time--approximate same time.
What I have to do is say, group things by the time at
which they're supposed to happen.
So I'm going to make an agenda as a list of segments.
And so I'm going to draw you a data structure for an agenda,
a perfectly reasonable one.
Here's an agenda.
It's a thing that begins with a name.
I'm going to do it right now out of list structure.
It's got a header.
There's a reason for the header.
We're going to see the reason soon.
And it will have a segment.
It will have--it will be a list of segments.
Supposing this agenda has two segments, they're the car's--
successive car's of this list. Each segment is
going to have a time--
say for example, 10--
that says that the things that happen in this
segment are at time 10.
And what I'm going to have in here is another data structure
which I'm not going to describe, which is a queue of
things to do at time 10.
It's a queue.
And we'll talk about that in a second.
But abstractly, the queue is just a list of things to do at
a particular time.
And I can add things to a queue.
This is a queue.
There's a time, there's a segment.
Now, I may have another segment in this agenda.
Supposing this is stuff that happens at time 30.
It has, of course, another queue of things that are
queued up to be done at time 30.
Well, there are various things I have to be
able to do to an agenda.
Supposing I want to add to an agenda another thing to be
done at time 10.
Well, that's not very hard.
I'm going to walk down here, looking for the
segment of time 10.
It is possible that there is no segment of time 10.
We'll cover that case in a second.
But if I find a segment of time 10, then if I want to add
another thing to be done at time 10, I just
increase that queue--
"just increase" isn't such an obvious idea.
But I increase the things to be done at that time.
Now, supposing I want to add something to be
done at time 20.
There is no segment for time 20.
I'm going to have to create a new segment.
I want my time 20 segment to exist between
time 10 and time 30.
Well, that takes a little work.
I'm going to have to do a CONS.
I'm going to have to make a new element of the agenda
list--list of segments.
I'm going to have to change.
Here's change.
I'm going to have to change the CDR of the CDR of the
agenda to point that a new CONS of the new segment and
the CDR of the CDR of the CDR of the agenda, the CD-D-D-DR.
And this is going to have a new segment now of time 20
with its own queue, which now has one element in it.
If I wanted to add something at the end, I'm going to have
to replace the CDR of this, of this list with something.
We're going to have to change that piece of data structure.
So I'm going to need new primitives for doing this.
But I'm just showing you why I need them.
And finally, if I wanted to add a thing to be done at time
5, I'm going to have to change this one, because I'm going to
have to add it in over here, which is why I planned ahead
and had a header cell, which has a place.
If I'm going to change things, I have to have
places for the change.
I have to have a place to make the change.
If I remove things from the agenda, that's not so hard.
Removing them from the beginning is pretty easy,
which is the only case I have. I can go looking for the
first, the first segment.
I see if it has a non-empty queue.
If it has a non-empty queue, well, I'm going to delete one
element from the queue, like that.
If the queue ever becomes empty, then I have to delete
the whole segment.
And then this, this changes to point to here.
So it's quite a complicated data structure manipulation
going on, the details of which are not really very exciting.
Now, let's talk about queues.
They're similar.
Because each of these agendas has a queue in it.
What's a queue?
A queue is going to have the following primitive
operations.
To make a queue, this gives me a new queue.
I'm going to have to be able to insert into
a queue a new item.
I'm going to have to be able to delete from a queue the
first item in the queue.
And I want to be able to get the first thing in the queue
from some queue.
I also have to be able to test whether a queue is empty.
And when you invent things like this, I want you to be
very careful to use the kinds of conventions I use for
naming things.
Notice that I'm careful to say these change something and
that tests it.
And presumably, I did the same thing over here.
OK, and there should be an empty test over here.
OK, well, how would I make a queue?
A queue wants to be something I can add to at the end of,
and pick up the thing at the beginning of.
I should be able to delete from the beginning
and add to the end.
Well, I'm going to show you a very simple
structure for that.
We can make this out of CONSes as well.
Here's a queue.
It has--it has a queue header, which contains two parts--
a front pointer and a rear pointer.
And here I have a queue with two items in it.
The first item, I don't know, it's perhaps a 1.
And the second item, I don't know, let's give it a 2.
The reason why I want two pointers in here, a front
pointer and a rear pointer, is so I can add to the end
without having to chase down from the beginning.
So for example, if I wanted to add one more item to this
queue, if I want to add on another item to be worried
about later, all I have to do is make a CONS, which contains
that item, say a 3.
That's for inserting 3 into the queue.
Then I have to change this pointer here to here.
And I have to change this one to point to the new rear.
If I wish to take the first element of the queue, the
first item, I just go chasing down the front pointer until I
find the first one and pick it up.
If I wish to delete the first item from the queue,
delete-queue, all I do is move the front
pointer along this way.
The new front of the queue is now this.
So queues are very simple too.
So what you see now is that I need a certain number of new
primitive operations.
And I'm going to give them some names.
And then we're going to look into how they work, and how
they're used.
We have set the CAR of some pair, or a thing produced by
CONSing, to a new value.
And set the CDR of a pair to a new value.
And then we're going to look into how they work.
I needed setting CAR over here to delete the first
element of the queue.
This is the CAR, and I had to set it.
I had to be able to set the CDR to be able to move the
rear pointer, or to be able to increment the queue here.
All of the operations I did were made out of those that I
just showed you on the, on the last blackboard.
Good.
Let's pause the time, and take a little break then.
When we originally introduced pairs made out of CONS, made
by CONS, we only said a few axioms about them, which were
of the form--
what were they--
for all X and Y, the CAR of the CONS of X and Y is X and
the CDR of the CONS of X and Y is Y. Now, these say nothing
about whether a CONS has an identity like a person.
In fact, all they say is something sort of abstract,
that a CONS is the parts it's made out of.
And of course, two things are made out of the same parts,
they're the same, at least from the point of view of
these axioms.
But by introducing assignment--
in fact, mutable data is a kind of assignment, we have a
set CAR and a set CDR--
by introducing those, these axioms no longer tell the
whole story.
And they're still true if written exactly like this.
But they don't tell the whole story.
Because if I'm going to set a particular CAR in a particular
CONS, the questions are, well, is that setting all CARs and
all CONSes of the same two things or not?
If I--if we use CONSes to make up things like rational
numbers, or things like 3 over 4, supposing I had two
three-fourths.
Are they the same one--
or are they different?
Well, in the case of numbers, it doesn't matter.
Because there's no meaning to changing the
denominator of a number.
What you could do is make a number which has a different
denominator.
But the concept of changing a number which has to have a
different denominator is sort of a very weird, and sort of
not supported by what you think of as mathematics.
However, when these CONSes represent things in the
physical world, then changing something like the CAR is like
removing a piece of the fingernail.
And so CONSes have an identity.
Let me show you what I mean about identity, first of all.
Let's do some little example here.
Supposing I define A to the CONS of 1 and 2.
Well, what that means, first of all, is that somewhere in
some environment I've made a symbol A to have a value which
is a pair consisting of pointers to a 1 and a pointer
to a 2, just like that.
Now, supposing I also say define B to be the CONS--
it doesn't matter, but I like it better, it's prettier--
of A and A.
Well, first of all, I'm using the name A twice.
At this moment, I'm going to think of
CONSes as having identity.
This is the same one.
And so what that means is I make another pair, which I'm
going to call B. And it contains two pointers to A. At
this point, I have three names for this object.
A is its name.
The CAR of B is its name.
And the CDR of B is its name.
It has several aliases, they're called.
Now, supposing I do something like set-the-CAR, the CAR of
the CAR of B to 3.
What that means is I find the CAR of B, that's this.
I set the CAR of that to be 3, changing this.
I've changed A. If I were to ask what's the
CAR of A--of A now?
I would get out 3, even though here we see that A was the
CONS of 1 and 2.
I caused A to change by changing B.
There is sharing here.
That's sometimes what we want.
Surely in the queues and things like that, that's
exactly what we defined our--organized our data
structures to facilitate--
sharing.
But inadvertent sharing, unanticipated interactions
between objects, is the source of most of the bugs that occur
in complicated programs. So by introducing this possibility
of things having identity and sharing and having multiple
names for the same thing, we get a lot of power.
But we're going to pay for it with lots of
complexity and bugs.
So also, for example, if I just looked at this just to
drive that home, the CADR of B, which has nothing to do
with even the CAR of B, apparently.
The CADR of B, what's that?
Take that CDR of B and now take the CAR of that.
Oh, that's 3 also.
So I can have non-local interactions by sharing.
And I have to be very careful of that.
Well, so far, of course, it seems I've introduced several
different assignment operators--
set, set CAR, set CDR. Well, maybe I should just get rid of
set CAR and set CDR. Maybe they're not worthwhile.
Well, the answer is that once you let the camel's nose into
the tent, the rest of him follows.
All I have to have is set, and I can make all of the--all of
the bad things that can happen.
Let's play with that a little bit.
A couple of days ago, when we introduced compound data, you
saw Hal show you a definition of CONS in terms
of a message acceptor.
I'm going to show you even a more horrible thing, a
definition of CONS in terms of nothing but air, hot air.
What is the definition of CONS, of the old functional
kind, in terms of purely lambdic expressions,
procedures?
Because I'm going to then modify this definition to get
assignment to be only one kind of assignment, to get rid of
the set CAR and set CDR in terms of set.
So what if I define CONS of X and Y to be a procedure of one
argument called a message M, which calls that
message on X and Y?
This [? idea ?] was invented by Alonzo Church, who was the
greatest programmer of the 20th century, although he
never saw a computer.
It was done in the 1930s.
He was a logician, I suppose at Princeton at the time.
Define CAR of X to be the result of applying X to that
procedure of two arguments, A and D, which selects A. I will
define CDR of X to be that procedure, to be the result of
applying X to that procedure of A and D, which selects D.
Now, you may not recognize this as CAR, CDR, and CONS.
But I'm going to demonstrate to you that it satisfies the
original axioms, just once.
And then we're going to do some playing of games.
Consider the problem CAR of CONS of, say, 35 and 47.
Well, what is that?
It is the result of taking car of the result of substituting
35 and 47 for X and Y in the body of this.
Well, that's easy enough.
That's CAR of the result of substituting into lambda of M,
M of 35 and 47.
Well, what this is, is the result of substituting this
object for X in the body of that.
So that's just lambda of M--
that's substituted, because this object is being
substituted for X, which is the beginning of a list,
lambda of M--
M of 35 and 47, applied to that procedure of A and D,
which gives me A. Well, that's the result of substituting
this for M here.
So that's the same thing as lambda of A, D, A,
applied to 35 and 47.
Oh, well that's 35.
That's substituting 35 for A and for 47 for D in A. So I
don't need any data at all, not even numbers.
This is Alonso Church's hack.
Well, now we're going to do something nasty to him.
Being a logician, he wouldn't like this.
But as programmers, let's look at the overhead.
And here we go.
I'm going to change the definition of CONS.
It's almost the same as Alonzo Church's, but not quite.
What do we have here?
The CONS of two arguments, X and Y, is going to be that
procedure of one argument M, which supplies M to X and Y as
before, but also to two permissions, the permission to
set X to N and the permission to set Y to N, given that I
have an N.
So besides the things that I had here in Church's
definition, what I have is that the thing that CONS
returns will apply its argument to not just the
values of the X and Y that the CONS is made of, but also
permissions to set X and Y to new values.
Now, of course, just as before, CAR
is exactly the same.
The CAR of X is nothing more than applying X, as in
Church's definition, to a procedure, in this case, of
four arguments, which selects out the first one.
And just as we did before, that will be the value of X
that was contained in the procedure which is the result
of evaluating this lambda expression in the environment
where X and Y are defined over here.
That's the value of CONS.
Now, however, the exciting part.
CDR, of course, is the same.
The exciting part, set CAR and set CDR. Well, they're nothing
very complicated anymore.
Set CAR of a CONS X to a new value Y is nothing more than
applying that CONS, which is the procedure of four--the
procedure of one argument which applies its argument to
four things, to a procedure which is of four arguments--
the value of X, the value of Y, permission to set X, the
permission to set Y--
and using it--using that permission to set
X to the new value.
And similarly, set-cdr is the same thing.
So what you've just seen is that I didn't introduce any
new primitives at all.
Whether or not I want to implement it this way is a
matter of engineering.
And the answer is of course I don't implement it this way
for reasons that have to do with engineering.
However in principle, logically, once I introduced
one assignment operator, I've assigned--I've
introduced them all.
Are there any questions?
Yes, David.
AUDIENCE: I can follow you up until you get--I can follow
all of that.
But when we bring in the permissions, defining CONS in
terms of the lambda N, I don't follow where N gets passed.
PROFESSOR: Oh, I'm sorry.
I'll show you.
Let's follow it.
Of course, we could do it on the blackboard.
It's not so hard.
But it's also easy here.
Supposing I wish to set-cdr of X to Y. See that right there.
set-cdr of X to Y. X is presumably a CONS, a thing
resulting from evaluating CONS.
Therefore X comes from a place over here, that that X is of
the result of evaluating this lambda expression.
Right?
That when I evaluated that lambda expression, I evaluated
it in an environment where the arguments
to CONS were defined.
That means that as free variables in this lambda
expression, there is the--there are in the frame,
which is the parent frame of this lambda expression, the
procedure resulting from this lambda expression, X and Y
have places.
And it's possible to set them.
I set them to an N, which is the argument of the
permission.
The permission is a procedure which is passed to M, which is
the argument that the CONS object gets passed.
Now, let's go back here in the set-cdr The CONS object, which
is the first argument of set-cdr
gets passed an argument.
That--there's a procedure of four things, indeed, because
that's the same thing as this M over here, which is applied
to four objects.
The object over here, SD, is, in fact, this permission.
When I use SD, I apply it to Y, right there.
So that comes from this.
AUDIENCE: So what do you--
PROFESSOR: So to finish that, the N that was here is the Y
which is here.
How's that?
AUDIENCE: Right, OK.
Now, when you do a set-cdr, X is the value the
CDR is going to become.
PROFESSOR: The X over here.
I'm sorry, that's not true.
The X is--set-cdr has two arguments--
The CONS I'm changing and the value I'm changing it to.
So you have them backwards, that's all.
Are there any other questions?
Well, thank you.
It's time for lunch.