Name: Lecture 2A: Higher-order Procedures
Uploaded: 2020-03-29T16:07:51.000Z
Duration: 1 h 1 min 21 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

You learned all of the rules of programming and lived.

Adverbs of degree

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

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

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

programming in BASIC or Pascal with just a funny syntax.

or you can no longer support that belief.

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

Supposing I want to write the mathematical expression which

So if I wanted to write down and say the sum from 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.

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

well, it's the following two possibilities.

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

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

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

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

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

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

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

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

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

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

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 sum of the square of a and the sum of the square of

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

They have the same first clause of the conditional and

the same predicate and the same consequence, and the

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

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

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

Now, wherever you see yourself writing the same thing down

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

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

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

which has to do with the sigma notation--

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

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

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.

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

Subtitles ListPlay Video

Lecture 2A: Higher-order Procedures

sort

expression

pattern

term