You learned all of the rules of programming and lived.

Almost all of them.

And so at this point, you're now certified programmers--

it says.

However, I suppose what we did is we, aah, sort of got you a

little bit of into an easy state.

Here, you still believe it's possible that this might be

programming in BASIC or Pascal with just a funny syntax.

Today, that illusion--

or you can no longer support that belief.

What we're going to do today is going to

completely smash that.

So let's start out by writing a few programs on the

blackboard that have a lot in common with each other.

What we're going to do is try to make them abstractions that

are not ones that are easy to make in most languages.

Let's start with some very simple ones that you can make

in most languages.

Supposing I want to write the mathematical expression which

adds up a bunch of integers.

So if I wanted to write down and say the sum from i

equal a to b on i.

Now, you know that that's an easy thing to compute in a

closed form for it, and I'm not interested in that.

But I'm going to write a program that

adds up those integers.

Well, that's rather easy to do to say I want to define the

sum of the integers from a to b to be--

well, it's the following two possibilities.

If a is greater than b, well, then there's nothing to be

done and the answer is zero.

This is how you're going to have to think recursively.

You're going to say if I have an easy case that I know the

answer to, just write it down.

Otherwise, I'm going to try to reduce this problem to a

simpler problem.

And maybe in this case, I'm going to make a subproblem of

the simpler problem and then do something to the result.

So the easiest way to do this is say that I'm going to add

the index, which in this case is a, to the result of adding

up the integers from a plus 1 to b.

Now, at this point, you should have no trouble looking at

such a definition.

Indeed, coming up with such a thing might be a little hard

in synthesis, but being able to read it at this point

should be easy.

And what it says to you is, well, here is the subproblem

I'm going to solve.

I'm going to try to add up the integers, one fewer integer

than I added up for the the whole problem.

I'm adding up the one fewer one, and that subproblem, once

I've solved it, I'm going to add a to that, and that will

be the answer to this problem.

And the simplest case, I don't have to do any work.

Now, I'm also going to write down another simple one just

like this, which is the mathematical expression, the

sum of the square from i equal a to b.

And again, it's a very simple program.

And indeed, it starts the same way.

If a is greater than b, then the answer is zero.

And, of course, we're beginning to see that there's

something wrong with me writing this down again.

It's the same program.

It's the sum of the square of a and the sum of the square of

the increment and b.

Now, if you look at these things, these programs are

almost identical.

There's not much to distinguish them.

They have the same first clause of the conditional and

the same predicate and the same consequence, and the

alternatives are very similar, too.

They only differ by the fact that where here I have a,

here, I have the square of a.

The only other difference, but this one's sort of unessential

is in the name of this procedure is sum int, whereas

the name of the procedure is sum square.

So the things that vary between these

two are very small.

Now, wherever you see yourself writing the same thing down

more than once, there's something wrong, and you

shouldn't be doing it.

And the reason is not because it's a waste of time to write

something down more than once.

It's because there's some idea here, a very simple idea,

which has to do with the sigma notation--

this much--

not depending upon what it is I'm adding up.

And I would like to be able to--

always, whenever trying to make complicated systems and

understand them, it's crucial to divide the things up into

as many pieces as I can, each of which I understand

separately.

I would like to understand the way of adding things up

independently of what it is I'm adding up so I can do that

having debugged it once and understood it once and having

been able to share that among many different uses of it.

Here, we have another example.

This is Leibnitz's formula for finding pi over 8.

It's a funny, ugly mess.

What is it?

It's something like 1 over 1 times 3 plus 1 over 5 times 7

plus 1 over 9 times 11 plus--

and for some reason, things like this tend to have

interesting values like pi over 8.

But what do we see here?

It's the same program or almost the same program.

It's a sum.

So we're seeing the figure notation, although over here,

we're dealing with incrementing by 4, so it's a

slightly different problem, which means that over here, I

have to change a by 4, as you see right over here.

It's not by 1.

The other thing, of course, is that the thing that's

represented by square in the previous sum of squares, or a

when adding up the integers.

Well, here, I have a different thing I'm adding up, a

different term, which is 1 over a times a plus 2.

But the rest of this program is identical.

Well, any time we have a bunch of things like this that are

identical, we're going to have to come up with some sort of

abstraction to cover them.

If you think about this, what you've learned so far is the

rules of some language, some primitive, some means of

combination, almost all of them, the means of

abstraction, almost all of them.

But what you haven't learned is common patterns of usage.

Now, most of the time, you learn idioms when learning a

language, which is a common pattern that mean things that

are useful to know in a flash.

And if you build a great number of them, if you're a

FORTRAN programmer, of course, everybody knows how to--

what do you do, for example, to get an integer which is the

biggest integer in something.

It's a classic thing.

Every FORTRAN programmer knows how to do that.

And if you don't know that, you're in real hot water

because it takes a long time to think it out.

However, one of the things you can do in this language that

we're showing you is not only do you know something like

that, but you give the knowledge of that a name.

And so that's what we're going to be going after right now.

OK, well, let's see what these things have in common.

Right over here we have what appears to be a general

pattern, a general pattern which covers all of the cases

we've seen so far.

There is a sum procedure, which is being defined.

It has two arguments, which are a lower bound

and an upper bound.

The lower bound is tested to be greater than the upper

bound, and if it is greater, then the result is zero.

Otherwise, we're going to do something to the lower bound,

which is the index of the conversation, and add that

result to the result of following the procedure

recursively on our lower bound incremented by some next

operation with the same upper bound as I had before.

So this is a general pattern, and what I'd like to do is be

able to name this general pattern a bit.

Well, that's sort of easy, because one of the things I'm

going to do right now is-- there's nothing very special

about numbers.

Numbers are just one kind of data.

It seems to me perfectly reasonable to give all sorts

of names to all kinds of data, for example, procedures.

And now many languages allow you have procedural arguments,

and right now, we're going to talk

about procedural arguments.

They're very easy to deal with.

And shortly, we'll do some remarkable things that are not

like procedural arguments.

So here, we'll define our sigma notation.

This is called sum and it takes a term, an A, a next

term, and B as arguments.

So it takes four arguments, and there was nothing

particularly special about me writing this in lowercase.

I hope that it doesn't confuse you, so I'll write it in

uppercase right now.

The machine doesn't care.

But these two arguments are different.

These are not numbers.

These are going to be procedures for computing

something given a number.

Term will be a procedure which, when given an index,

will produce the value of the term for that index.

Next will be given an index, which will

produce the next index.

This will be for counting.

And it's very simple.

It's exactly what you see.

If A is greater than B, then the result is 0.

Otherwise, it's the sum of term applied to A and the sum

of term, next index.

Let me write it this way.

Now, I'd like you to see something, first of all.

I was writing here, and I ran out of space.

What I did is I start indenting according to the

Pretty-printing rule, which says that I align all of the

arguments of the procedure so I can see

which ones go together.

And this is just something I do automatically, and I want

you to learn how to do that, too, so your programs can be

read and understood.

However, what do we have here?

We have four arguments: the procedure, the lower index--

lower bound index--

the way to get the next index, and the upper bound.

What's passed along on the recursive call is indeed the

same procedure because I'm going to need it again, the

next index, which is using the next procedure to compute it,

the procedure for computing next, which I also have to

have separately, and that's different.

The procedure for computing next is different from the

next index, which is the result of using next on the

last index.

And I also have to pass along the upper bound.

So this captures both of these and the other nice program

that we are playing with.

So using this, we can write down the original program as

instances of sum very simply.

A and B. Well, I'm going to need an identity procedure

here because ,ahh, the sum of the integers requires me to in

this case compute a term for every integer, but the term

procedure doesn't want to do anything to that integer.

So the identity procedure on A is A or X or whatever, and I

want to say the sum of using identity of the term procedure

and using A as the initial index and the incrementer

being the way to get the next index and B being the high

bound, the upper bound.

This procedure does exactly the same as the sum of the

integers over here, computes the same answer.

Now, one thing you should see, of course, is that there's

nothing very special over here about what I used as the

formal parameter.

I could have, for example, written this

X. It doesn't matter.

I just wanted you to see that this name does not conflict

with this one at all.