## Subtitles section Play video

• PROFESSOR: Well, yesterday was easy.

• 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

• 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.

• 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

• 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