MIT OpenCourseWare
http://ocw.mit.edu


6.001 Structure and Interpretation of Computer Programs, Spring 2005

Transcript – 5B: Computational Objects



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 b ulbs, 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 build ing 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, a nd 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 thing s, 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 h as 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 wa y 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 inthe 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. Thisis 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 lunc h.
MIT OpenCourseWare
http://ocw.mit.edu


6.001 Structure and Interpretation of Computer Programs, Spring 2005





Please use the following citation format:

       Eric Grimson, Peter Szolovits, and Trevor Darrell, 6.001 Structure and

       Interpretation of Computer Programs, Spring 2005. (Massachusetts Institute
       of Technology: MIT OpenCourseWare).    http://ocw.mit.edu (accessed MM DD,
       YYYY). License: Creative Commons Attribution-Noncommercial-Share Alike.


Note: Please use the actual date you accessed this material in your citation.



For more information about citing these materials or our Terms of Use, visit:
http://ocw.mit.edu/terms