PROFESSOR: Well, so far we've invented enough programming to

do some very complicated things.

And you surely learned a lot about

programming at this point.

You've learned almost all the most important tricks that

usually don't get taught to people until they have had a

lot of experience.

For example, data directed programming is a major trick,

and yesterday you also saw an interpreted language.

We did this all in a computer language, at this point, where

there was no assignment statement.

And presumably, for those of you who've seen your Basic or

Pascal or whatever, that's usually considered the most

important thing.

Well today, we're going to do some thing horrible.

We're going to add an assignment statement.

And since we can do all these wonderful things without it,

why should we add it?

An important thing to understand is that today we're

going to, first of all, have a rule, which is going to always

be obeyed, which is the only reason we ever add a feature

to our language is because there is a good reason.

And the good reason is going to boil down to the ability,

you now get an ability to break a problem into pieces

that are different sets of pieces then you could have

broken it down without that, give you another means of

decomposition.

However, let's just start.

Let me quick begin by reviewing the kind of language

that we have now.

We've been writing what's called functional programs.

And functional programs are a kind of encoding of

mathematical truths.

For example, when we look at the factorial procedure that

you see on the slide here, it's basically two clauses.

If n is one, the result is one, otherwise n times

factorial n minus one.

That's factorial of n.

Well, that is factorial of n.

And written down in some other obscure notation that you

might have learned in calculus classes, mathematical logic,

what you see there is if n equals one, for the result of

n factorial is one, otherwise, greater than one, n factorial

is n times n minus one factorial.

True statements, that's the kind of

language we've been using.

And whenever we have true statements of that sort, there

is a kind of, a way of understanding how they work

which is that such processes can be involved by

substitution.

And so we see on the second slide here, that the way we

understand the execution implied by those statements in

arranged in that order, is that you do successive

substitutions of arguments for formal parameters in the body

of a procedure.

This is basically a sequence of equalities.

Factorial four is four times factorial three.

That is four times three times factorial of two and so on.

We're always preserving truth.

Even though we're talking about true statements, there

might be more than one organization of these true

statements to describe the computation of a particular

function, the computation of the value of

a particular function.

So, for example, looking at the next one here.

Here is a way of looking at the sum of n and m.

And we did this one by a recursive process.

It's the increment of the sum of the decrement of n and m.

And, of course, there is some piece of mathematical logic

here that describes that.

It's the increment of the sum of the decrement of n and m,

just like that.

So there's nothing particularly magic about that.

And, of course, if we can also look at an iterative process

for the same, a program that evolves an iterative process,

for the same function.

These are two things that compute the same answer.

And we have equivalent mathematical truths that are

arranged there.

And just the way you arrange those truths determine the

particular process.

In the way choose and arrange them determines the process

that's evolved.

So we have the flexibility of talking about both the

function to be computed, and the method

by which it's computed.

So it's not clear we need more.

However, today I'm going to this awful thing.

I'm going to introduce this assignment operation.

Now, what is this?

Well, first of all, there is going to be another kind of

kind of statement, if you will, in a programming

language called Set!

Things that do things like assignment, I'm going to put

exclamation points after.

We'll talk about what that means in a second.

The exclamation point, again like question mark, is an

arbitrary thing we attach to the symbol which is the name,

has no significance to the system.

The only significance is to me and you to alert you that this

is an assignment of some sort.

But we're going to set a variable to a value.

And what that's going to mean is that there is a time at

which something happens.

Here's a time.

If I have time going this way, it's a time access.

Time progresses by walking down the page.

Then an assignment is the first thing we have that

produces the difference between a before and an after.

All the other programs that we've written, that have no

assignments in them, the order in which they were evaluated

didn't matter.

But assignment is special, it produces a moment in time.

So there is a moment before the set occurs and after, such

that after this moment in time, the variable has the

value, value.

Independent of what value it had before, set!

changes the value of the variable.

Until this moment, we had nothing that changed.

So, for example, one of the things we can think of is that

the procedures we write for something like factorial are

in fact pretty much identical to the function factorial.

Factorial of four, if I write fact4, independent of what

context it's in, and independent of how many times

I write it, I always get the same answer.

It's always 24.

It's a unique map from the argument to the answer.

And all the programs we've written so far are like that.

However, once I have assignment, that isn't true.

So, for example, if I were to define count to be one.

And then I'm going to define also a procedure, a simple

procedure called demo, which takes argument x and does the

following operations.

It first sets x to x plus one.

My gosh, this looks just like FORTRAN, right--

in a funny syntax.

And then add to x count, Oh, I just made a mistake.

I want to say, set! count to one plus count.

It's this thing defined here.

And then plus x count.

Then I can try this procedure.

Let's run it.

So, suppose I get a prompt and I say, demo three.

Well, what happens here?

The first thing that happens is count is currently one.

Currently, there is a time.

We're talking about time.

x gets three.

At this moment, I say, oh yes, count is

incremented, so count is two.

two plus three is five.

So the answer I get out is five.

Then I say, demo of say, three again.

What do I get?

Well, now count is two, it's not one anymore, because I

have incremented it.

But now I go through this process, three goes into x,

count becomes one plus count, so that's three now.

The sum of those two is six, so the answer is six.

And what we see is the same expression leads to two

different answers, depending upon time.

So demo is not a function, does not compute a

mathematical function.

In fact, you could also see why now, of course, this is

the first place where the substitution model

isn't going to work.

This kills the substitution model dead.

You know, with quotation there were some little problems that

a philosopher might notice with the substitutions,

because you have to worry about what deductions you can

make when you substitute into quotes, if you're allowed to

do that at all.

But here the substitution model is dead, can't do

anything at all.

Because, supposing I wanted to use a substitution model to

consider substituting for count?

Well, my gosh, if I substitute for here and here, they're

different ones.

It's not the same count any more.

I get the wrong answer.

The substitution model is a static phenomenon that

describes things that are true and not things that change.

Here, we have truths that change.

OK, Well, before I give you any understanding of this,

this is very bad.

Now, we've lost our model of computation.

Pretty soon, I'm going to have to build you a new model of

computation.

But ours plays with this, just now, in an informal sense.

Of course, what you already see is that when I have

something like assignment, the model that we're going to need

is different from the model that we had before in that the

variables, those symbols like count, or x are no longer

going to refer to the values they have, but rather to some

sort of place where the value restored.

We're going to have to think that way for a while.

And it's going to be a very bad thing and

cause a lot of trouble.

And so, as I said, the very fact that we're inventing this

bad thing, means that there had better be a good reason

for it, otherwise, just a waste of time

and a lot of effort.

Let's just look at some of it just to play.

Supposing we write down the functional version, functional

meaning in the old style, of factorial by

an iterative process.

Factorial of n, we're going to iterate of m and i, which says

if i is greater than n, then the result is m, otherwise,

the result of iterating the product of i and m.

So m is going to be the product that I'm accumulating.

m is the product.

And the count I'm going to increase by one.

Plus, ITER, ELSE, COND, define.

I'm going to start this up.

And these days, you should have no trouble reading

something like this.

What I have here is a product there being

accumulated and a counter.

I start them up both at one.

I'm going to buzz the counter up, i goes to i plus one every

time around.

But that's only our putting a time on the process, each of

this is just a set of truths, true rules.

And m is going to get a new values of i and m, i times m

each time around, and eventually i is going to be

bigger than n, in which case, the answer's going to be m.

Now, I'm speaking to you, use time in this.

That's just because I know how the computer works.

But I didn't have to.

This could be a purely mathematical description at

this point, because substitution

will work for this.

But let's set right down a similar sort of program, using

the same algorithm, but with assignments.

So this is called the functional version.

I want to write down an imperative version.

Factorial of n.

I'm going to create my two variables.

Let i initialize itself to one, and m be initialized to

one, similar.

We'll create a loop which has COND greater than i, and if i

is greater than n, we're done.

And the result is m, the product I'm accumulating.

Otherwise, I'm going to write down three things to do.

I'm going to set!