Uploaded by UCBerkeley on 31.08.2012

Transcript:

JOHN DENERO: Okay. Time to learn can you hear me in the back.

Some announcements homework 1 is due today at 5:00ﾊp.m.. how many people have tried

to turn it in and have not been able to so far.

Not too many. Every year there is utter chaos trying to submit is first homework. Welcome

to Berkeley. That's part of the tradition. Typically it's smoother in the future.

And I'm glad most of you have been able to submit so far.

Questions? STUDENT: What was the command for check?

STUDENT: If we did some homework and it seemed to work fine should we assume it worked.

JOHN DENERO: What happens if you submit can you check it the 2 versions of same question:

you can type of G look up dash T. It will tell you whether or not you submitted.

G look up space dash T. Don't all try it announcement of there are a lot of you [LAUGHTER].

Homework 1 due today. Homework 2 is posted due next Friday.

STUDENT: If we work with partner and we submit their idea does it submit for both.

JOHN DENERO: How many times do you have to submit if you are work for partner on 1 version

for both of you. You don't both need to submit copy of same

thing either 1 submits as long as you submit IDs of both..

Can I work with partner in different section. No you have to work with partner in your section.

STUDENT: What if there are odd number of people in your section.

STUDENT: Oh! ! ! STUDENT: Error error.

JOHN DENERO: If you would like to ask for exception to the rule that you must work with

someone in your section talk to TA. For instance if there are odd number of people.

STUDENT: Don't just say I don't know how to work with someone.

JOHN DENERO: Okay. Homework 2 posted. I've done things a little bit differently

this time. Now you have not only a description of homework

you are meant to do but also a file that contains all the examples without answers in them to

get you started. That should save you the pain of having to go through and copy everything

in the html in new file and might make the process of doing homework a little bit simpler.

[APPLAUSE]. And I will have you know I didn't go through

and copy and paste all the examples myself. I used Python.

STUDENT: In homework 1 if we didn't put the heard or will we get docked for it.

JOHN DENERO: What if you don't put bog Kno to homework for homework 1 will you be docked

or kicked out. Nothing bad will handicap. Try to stick with format but we'll do our

best to handle exceptions as they come up. JOHN DENERO: Question is: what happens if

I submit twice? Or 422 times which probably has happened in the history of this course

we annual look at last submission. That's true for projects and homeworks you can submit

multiple times if you find something to change. Don't wait to submit if you think you are

don't do it but you can correct later. STUDENT: In the homework with the e mail to

log off. JOHN DENERO: Question is: what happens if

you submitted long ago before there was a new submit script asking for Gmail address.

That's okay. You might not get e mail about this homework 1. But you don't need to go

back and resubmit. Okay.

Project 1 is due in less than 2ﾊweeks. Get started now. As opposed to on September 11th.

STUDENT: Oh La ha ha. JOHN DENERO: Or September tenth [LAUGHTER]

or 90. Get started go through and read the project. I'll tell you little bit about it

today and hopefully that will inspire you to play around.

Last time we talked about while statements among other things. Every computer science

course that is worth anything at all talks about the following sequence called Fibonacci

sequence. With wonderful mathematical properties. It's defined as first 2 elements are 0 and

1. Every element after is sum of previous 2. Add 01, 1, 2, 1 and 2 get 3, 2 and 35.

There are lofts mathematical properties. With historical properties of Fibonacci sequence.

It was not invented by Fibonacci. Nor is it the case was Fibonacci's name was Fibonacci

there was a mathematician leaned narrow doe P. and they called him Fibonacci of.

How do we compute it. We know each element is sum of previous 2. We could go through

and walk through the elements. Here's a program or function defined in order

to compute the Fibonacci sequence using tools we've seen there are other way to see compute

this. What's exactly happening here. We start out

by defining what is the first and second element of this sequence? And we call them pred and

predecessor and cur for current element. Currently cur stores second element that's why K is

2 on second line. And then while statement increasing K 1 by 1. Third, fourth fourth

element until the income tax element which is what we want and store that in cur and

each time updating we say we are tracking the current element but predecessor and store

whatever current element in pred assess and add them together as new current element.

And walk through exactly in environment diagram. But it's a good idea to think about ways you

can abstract away from mechanical details and understand what's happening.

So action happens in this 1 statement. We start with pred and cur.

Are bound to 0 and 1. Then we are interested approximate update which happens over and

over again inside the while statement. And each time the Fibonacci sequence exists in

the realm of values. Imagine and we are marching along it. So evaluate we execute the assignment

statement mechanically we evaluate both expressions, cur and pred, plus cur. And binding to the

names pred and cur. But we are moving our names along the sequence. So the first time

we execute, we move along the sequence 1. Now pred and cur as 1, and 1. The next time

we moved along the sequence again. And this way we track along the sequence itself binding

the names to values as we go. And eventually we get to the 1 we want and

be done. That's a picture of Fibonacci sequence.

That should get you little bit of refresher of while statements work. And how we bind multiple names to multiple values

through assignment statement that has 2 names on left separated by commas and 2 on the right,

names. So just to make sure that this makes sense.

There was a problem loading the Web page. Example:

I bind big and small to 3 and 4. 3 is pretty big 4 is certainly small. While it's the case

that big is still big bigger than 2, or small is still small still less than 2.

I'm rebind big, and small. Big is going to be bound to small 1, and small

is bound to big+ 1. So what happens what happened as soon as I

execute the while statement I updated the names big and small they might mean something

different than at the top. Your mission should you choose the accept it. Is figure out what

big bound to right now. Talk to the person next to you and see what's going on.

STUDENT: Big is 3. FBI fib Fibonacci sequence. Okay let's see how it came out how many people

think big is still bigger than small? Hard to tell. That's not fair I asked what

big was but not what small was. You need the keep track of both of. Big is changing on

what small is bound too and vice versa. Big right now is 1.

Let's see if we can understand why. What happened in this example was that we

started out with small bound to 4 and big bound 3. That's what I said.

Then I check this condition which says is big big? Or small is small? Both happen to

be true. Remember or means: either 1 is true or both. That means the whole expression is

true value and I execute the suite of the while statement.

Now I go through I'm about to do first assignment statement and let's look at big. It changes

to whatever the small is minus 1 so that is 4 3 is 3 and small 2. Big 3, small 2. I check

again. Big is big, so 3 is bigger than 2. Small is no longer small enough. But only

1 has to be true because we haveﾊ"or" expression connecting the 2. It is the case that big

a bigger than 2, it's 3. And therefore, we execute the statement 1 more time. Leaving

big as 1 and small 2. Okay. 1 example down.

This isn't about the procedure that Python carries out when its executing programs but

instead some advice about how you write functions that are easy for others to read.

STUDENT: In the example did big get you have 2 assignments of that small+ 1. . You use

updated value of big and/or whole value. JOHN DENERO: Okay I will answer that it's

important. The question is: when I'm evaluating this

expression and this expression, what values of big and small do I use? I use the ones

that are currently bound in the current environment. And I'm going to evaluate all of the expressions

on the right of the equals using if names they are bound right now in order to get the

values before rebinding. That's the execution procedure do all the values on right and then

the binding of the names on the left. Let me tell you a little bit functions of

functions are beautiful things that's why I say the art of the function. They are sometimes

so beautiful they make me cry. What makes a beautiful function? It's best

if a function has 1 job. That's the way we use as functional abstraction. Give it a flame

and have it doing some arguments giving us some return values. And having a particular

purpose for a function. If you are into metaphors a good metaphor

is scissors are good at cutting things that's all they do. You don't want a Swiss army knife

function taking everything figure out what it is and can do something with it we have

a name or Swiss army naives if you never heard of it before it would take me sometime to

explain what it is if you haven't heard of it knife, saw, citizens sors, splicing opening

cans this thing on back is an awl for holes. So function should've exactly 1 job. That

means each function is going to encapsulate some pit bit of computational process we can

understand as not kind of complicated mess of a bunch of things but 1 particular purpose

in the program. It's okay if function can be used in different

situations. Another principle people talk about: you are

not meant the repeat yourself when writing programs. If you copied and paste it had same

thing over and over in program and then you realize oh I want to change then you have

to change every topic that's prone to error because you might forget 1. Programs are easier

to understand if every computational process is implemented exactly once and then reused

over and over again. So you kind of get some leverage by programming

in that way. These are 3. Identical trip lets this person

actually repeated himself. It's best to define function. Here the function

for raising the number to power. It's best oh it only works for powers greater than 6

and less than 9 that are odd or something like that. But instead can handle all the

cases you might want to apply particular 1 too. The world has failed. There's a process

where we connect a electrical device to current. But every country has its own way.

For instance we don't have a square function in the standard library for Python because

we have a function for raising things to arbitrary power and that seems to be fairly general.

Okay let's see how we might put some of this into practice.

Remember, we don't want to repeat ourselves but also we want to manage the complexity

of our programs and we want to do that by using tools of abstraction. We will see here

that there are very practical reasons for that when updating program but conceptual

programs as well. When I want to separate the concerns from 1 computational process

from another but still combine them in meaningful ways. So generalizing a partner using functions

and then patterns by the end we will use functions in new way you haven't seen before. Which

is treating the functions themselves can be just like values.

Let's start with abstracting over different values.

Here's a case in mathematics. Regular geometric shapes relate the area of something to something

else. The shape of regular rectangle or square relates the length of side to square. It's

r. You probably know the formula for getting the area of square from length of its side.

R2. A circle, relates the radius of the circle

to the area of the circle Pi r2. A regular hexagon relates the length of side area of

hexagon, 3 mumble. We have 2 functions 1 of which is less familiar

than other 2. But they say something about the how I relate the length of some aspect

of this regular shape to the area itself. We can look for common pattern among all.

If I look for area of square and I can multiply 1 and that's no trouble then I say the things

that change with each shape are this 1 versus the Pi versus the 323 over 2. And if I hide

those details of computing the area then I see if actions I take whatever the length

I'm interested in and I square it. That's a way in which we can generalize this pattern

of figuring area from length by noticing they all differ in terms of number I multiply in

the front. And finding common structure like this allows us to have shared implementation.

So coding to see why this might matter.

Here's an empty file I will start defining some functions.

Here is a function for the area of the square with side length r. I'm going to give it 1

line description. And then return r * r.

Then I will compute the area of a circle with the radius r.

It's pretty close to that. I will copy and paste that.

Circle with area r. What happens here: is that I return r * r

* Pi. What do I need in order to do that. From math import Pi. I know pretty soon I

need square root as well. So now I want the area of a hexagon.

Copy paste again. Return the area of area of regular hexagon with side length return

r * r * 3 * square root of 3. /2.

Okay now I'm in business sure there's repetition but that's fine. I've defined the 2, 3 things

I need if I want to I can go up here and compute the area of a circle with radius den get 314.

Do you see a problem with these functions? Rep active, not general.

Also they are wrong. What's the area of a square when side length 2ﾊ well apparently

it's 4 that's not right. Well I want to check and make sure I haven't done something wrong.

So assert statement in Python that checks to make sure some condition true. So I say

I want the area of r to be greater than or equal to 0. The way assert works you put an

expression in here. This is Boolean context all we care about whether it's true or false

and then the message after that says no negative sides.

And I'll put that everywhere. Now we are in business. Now when I want the area of a square,

of side length 2. It will complain and say no negative r, please.

Any other problems? How about the area of a square with side length

0. That's not a square at all so something else is wrong now I need to go back and change.

Say I want this bigger than 0. I want to say r markup must be positive. Okay.

I'm good. No I'm not good have to duplicate this everywhere.

Sad day. Fortunately I'm good at typing fast so it didn't take long but you want to avoid

this to make sure it's consistent the structure of the program itself should make it consistent

for you. Instead of doing this, I could say, "Well, there's a general notion of computing

the area of something it has to do with having a length of side or part and then some constant

for the shape that tells me exactly what I'm supposed to multiply r2 by in order to get

the area of shape I'm interested in. Return the area of a shape.

What does that look like? Well, we just return r * r * the shape constant. But here's a good

place to put the notion that r must be positive and then I can take it out everywhere else

as long as I use the function I created. The area of the r or shape constant is 1. The

shape constant here is Pi. And the shape constant down here is 3 times

* the square root of 3/2. And now I get the behavior I want. And in

enforcing a condition I cared about namely that r must be positive only happens in 1

place that notion is shared across my code. That helps me not repeat and organize my program

a little bit better. Also it is a means of abstraction. So I talked about the area of

square as special case of some kind of area. This is not the most interesting example.

But it's supposed to prime your mind for more interesting example we are about to do.

What I'm priming you for is that when we say that we can write a general version of a function,

we don't necessarily just need to parameterize it by some number we pass in like a constant

for the shape. But we can really pass in any computational process we are interested in.

The way we do that passing it as argument to a function another function.

So a function that takes another function as input is called aﾊ"higher order function".

It's called that because it's in the business not of manipulating numbers but computational

processes themselves. It's a computational process that takes in other computational

processes. And might run or not or multiple times. That's

a higher order function. Let's look at an example of that notion in order to find some

commonality among a bunch different things. Okay.

Questions so far? No questions about the area of hexagon? It's

like 6 triangles. We are trying not to generalize over computational

processes. We will start with some not very exciting computational processes it's important

to start simple to illustrate the concepts but next week they will be really interesting.

At least I think they are. And they are things I use in my day job. Common structure among

(On screen). It's not a shape constant but something you do.

For instance here's 3 different equations. The general mathematical expression is on

the left. This says the numbers sum the numbers 1 to

5 and we are sum the number itself, K. Here's what it looks like when expanded 1, 2, 3,

45, hopefully that's the answer looks right to me. Next. We sum the numbers K from 1 to

5 but cube of each 1. 5 different cubes summed up 225.

Finally down here we have a summation over some complicated expression that has a K in

it. Where did I get n this? From someone else. What does it do. A sequence that K it rates

to something large converges. Any guesses. STUDENT: Pi.

JOHN DENERO: Through Pi it's not there yet. But this is a way you can compute Pi yourself

instead of looking it up in a book. Okay.

What do these have in common they have a big sum symbol that's for sure.

And in particular they all have exactly the same sum symbol can same parameters of starting

and ending K. The only difference is sum over K itself or K cubes or some complicated expression.

Which gives us summation that converges to Pi.

Okay so here what we are circling last time it was a bunch of numbers here it's expressions,

expressions of K. Let's implement some of these and figure out

how to abstract them. Questions?

We might want to sum the natural numbers. So this gives us the sum of natural numbers

from 1 up to 5 is 15 we saw that already. How are we doing this? We star by saying there's

a total sum I commuted so far which is 0 at the beginning and then sum K which is the

current number I'm summing and I walk across from each term in the sequence that I am summing

up. So total 0, K 1. It's the case that K is either

less than or equal to n, we go up through n, we are going to rebind to names total and

K. What's total going to be? Well, total is going to be whatever total

was before plus K and K is 1 more than it was. And then return the total we got.

Let's check and make sure we've done correctly. Sum_naturals (4) touch 4 we get 10, 515, and.

We

also sum cubes. We can start with the same idea of total and

the K. Being 0, 1. Then while it's the case that K is less than n rebind total and K.

Total is whatever the total was before, plus K raised to the power of 3. Then K will be

1 bigger than it was. Now, when we sum cubes up to 5 we get to hundred

25. Let's look at these 2 things.

Where are they different? STUDENT: 5.

JOHN DENERO: So it's actually everything is exactly the same. Except for here I have power

K, 3 and here I just have K. Here it's some expression involving K here's another expression

involving K. Let's write the 2 down. 1 is the identity function of K. Just returns K.

The other is a function that cubes. K to the power of 3.

So power just races something. Okay so here are the 2 different things.

Between sum natural and is sum cubes. Is that either we take K and just add that to total

or we take K raised to the third power add that to total. Let's see if we can write down

a general notion of summation which has some number of things we sum up. But also computational

process which is a name bound to some function and we are calling it term. Term is: the way

to compute the Kth term of sequence I'm summing up.

Okay. What does this look like? We start with 0, 1. Then while K is less than or equal to

n. Total, K equals total+ﾊ okay he's the thing we always make different. K+ 1 and return

total. Owning now what do we put here. It's not K.

That would be specific to something naturals it's not pow K 3. It's in fact whatever you

get if you take the function we passed which we call term and apply to number K. If we

pass in K to the identity then get K back. If it's passed into the cube then we get the

cube of K. So the question is: is this just a sketch

of what's happening or does this actually work. The answer is it works. We are passing

in a function here. How do we do that. I will write down a new version of some of naturals.

Def sum_naturals. How does it work? It returns a general summation of (n terms.

But the function I will apply to each term in order to get the term I had together is

calledﾊ"identity". And then I can redefine some cubes (n) as

return summation n but what I do to each thing I assign is cube it.

Let's see how we've done. We want to make that small.

So can we still sum naturals? Yes, we can. What happened we call this sum naturals it

said please give me back whatever summation give me back if I defined combined a bunch

of different identity of K, so K itself. And can I sum cubes up to 5, yes, I can. I want

to run summation but cube each term before adding it to go.

STUDENT: I think you defined those 2 functions twice is that legal in Python.

JOHN DENERO: So what happened with I have sum naturals once here and again up here.

Remember what happens when you have execute def statement you create a new function and

then bind to name you've given to that function. We created the function and then forget about

it we rebound the name sum naturals to other function. If I delete it everything still

runs. What's happened?

We have this general pattern or general computational process for summing things together. And then

we've said: the way in which we could use this we could plug in particular function

like identity or cube. Into this summation and function use that.

Now notice there's no def term anywhere. Term is a name bound to a function that we

define elsewhere and it's either bound to whatever identity is bound to. That's the

identity function or whatever the cubed function name cube is bound to. That's the cube function.

There are no parentheses after it. We are naming the function and passing it in to parameter

to summation. (Function) I could def Pi term. ﾊ let's that was 8 ﾖ by what you get when

multiplying (On screen). And now if I want, the summation of 10000

different things where I apply this Pi term function to each 1 and then sum together then

I get a pretty reasonable approximation of Pi at least up that far.

STUDENT: When you call summation does it evaluate. (INAUDIBLE).

JOHN DENERO: Question is: When does a function get evaluated you pass

in. I passed in the function cube into summation I haven't actually call it yet. Only called

when I get to call expression here which says go figure term means will it.

Now I want to apply that function to whatever parameter or whatever argument a pass in the

current value of K that's finally when evaluating this call expression that's when the function

cube or Pi term finally gets called. Okay.

We generalized the computational processes. What happened was: we defined a function of

single argument. It's not called term it's called cube that's important this is about

cubing things specifically. Term is formal parameter that will be bound to the function

we created by the def cube statement. The function gets bound to term and then called

down here. When we actually call it that's what's going on in doctest. Is calling summation

naming the cube function and passing that in as argument which gets bound to term then

and then we call it as we wish over and over again within the suite of that while statement.

That's why we get 1 cube (On screen). You can't do this in all languages but you

can do it in many. And when they invent new language these days they let you to do this.

It's useful. It allow to go see abstract away from the general notion of computational process

and pass that computational process around. I will skip that until next time.

But I want to say a word about the purpose of higher order functions. So functions can

be actually no I want to do the example. It's so cool. Let's do it.

1 more example. So not only can I pass in a function as argument. I can return a function

as return value. Here's what it looks like: I will return a function that takes K and

returns n+ k. Here's how it works:

Add 3 is new function we create by calling add make adder and when add 3 to 4 I get back

7. The way I do this is define a function within another function. I call it the "adder"

and it takes in exactly 1 argument (k) but what it returns is n+ k.

I created the adder function. And then I Western it. So name the function I created and then

I used it in order to create new functions along the way. How does it work? Well I can

make an adder for 20. That will give me back a new function. It's

calledﾊ"adder". How do I use it let's say I bind it to a name like: add 20. Then I call

add 20 as many times as I want. I can call it on 1ﾊ whoops.

And I get 21 so on. I can add 20 to whatever you get when adding 20 to 12. And I get 52.

So notice the cool thing about this: this is a function of 1 argument, but as adds the

2 names together and nowhere in the global frame are either n or k defined, but instead

this adder function is allowed to see whatever names are around in the function in which

it was defined. So adder can see the end that was the former parameter. Make_add.

Okay. Parameter.

Talk to the person next to you and see if you can figure out when I type that.

Go. What is that thing? Have you seen something

like that before? It looks like some sort of emoticon.

Smiley. It's not it's a call expression. It gives you back 32. Let's look at how it works.

Functions can be defined within other functions. So when I type make_adder like this. I create

a function that gives me back a function. I've bound the name add 3 to that function.

I've created a local def statement which binds adder in local frame to new function I create

and I refer to both n and k from this position in code and with expression adder 12, 2012.

What you are looking at is call expression with a compound operate.

So remember: call expression has operands and operator. There's your operand and operate

how do we evaluate the call expression we evaluate the operator and operands and apply

the function that is the value of the operate to the values arguments of operands. So we

have to evaluate this call expression that's labeled operate right now and that gives a

function, a function that adds things together and now we have an expression that evaluates.

To 2. And then we apply this function which takes whatever it takes and adds 1 to it and

add that to 2 and we get 3. So make adder 1, 2, gives us 3. Because this

evaluates to a function that adds 1 to anything I pass into it.

STUDENT: How does Python know to make adder 1.

JOHN DENERO: Question is: how does Python know in advance that whatever this complicated

thing is you typed in as operate give you back a function. It doesn't so it tries to

evaluate whatever you have as operate expression and if it's a function it applies and not

it gives error. For some reason you put something else complicated

here like 2+ 2 and you try to use that as function. That doesn't work it gives number

not function. But this gives function that's what you want in that position in call expression.

STUDENT: When you type make_adder without declaring something as that it will say whatever

some point in mechanic memory is there a way to get there to that memory.

JOHN DENERO: Good question but we'll talk about that on off time.

So let me summarize functions are first class in Python. That means they are values. Values

include numbers but also include functions as well. What does that mean if I have a function

which is first class function which I can manipulate. I can pass to oh functions I can

return as value. I can anything to function that I would do to a number that makes sense.

Higher order functions take function as argument or return value. They operate at the level

of computational processes and we can express general methods of computation. Remove repetition

from programs. We only need 1 while statement for summation. Not a bunch. And allow the

concern of how I compute the particular term of this Pi summation from the general process

of just adding up a bunch stuff together. Okay so 1 thing we didn't get to was we were

playing a game for your project. But we don't have time. So sad.

So we'll play it another time and hopefully I can post an online version. Have a good

weekend. See you soon.

Announcement, announcement, announcement: there's no lecture on Monday, it's a holiday.

No section. But if you really want to go to section, you are welcome to crash a Tuesday

section. Sections are a good idea if you want to understand this but priority will actually

go to the people who are enrolled in that section. Okay. See ya.

25

Some announcements homework 1 is due today at 5:00ﾊp.m.. how many people have tried

to turn it in and have not been able to so far.

Not too many. Every year there is utter chaos trying to submit is first homework. Welcome

to Berkeley. That's part of the tradition. Typically it's smoother in the future.

And I'm glad most of you have been able to submit so far.

Questions? STUDENT: What was the command for check?

STUDENT: If we did some homework and it seemed to work fine should we assume it worked.

JOHN DENERO: What happens if you submit can you check it the 2 versions of same question:

you can type of G look up dash T. It will tell you whether or not you submitted.

G look up space dash T. Don't all try it announcement of there are a lot of you [LAUGHTER].

Homework 1 due today. Homework 2 is posted due next Friday.

STUDENT: If we work with partner and we submit their idea does it submit for both.

JOHN DENERO: How many times do you have to submit if you are work for partner on 1 version

for both of you. You don't both need to submit copy of same

thing either 1 submits as long as you submit IDs of both..

Can I work with partner in different section. No you have to work with partner in your section.

STUDENT: What if there are odd number of people in your section.

STUDENT: Oh! ! ! STUDENT: Error error.

JOHN DENERO: If you would like to ask for exception to the rule that you must work with

someone in your section talk to TA. For instance if there are odd number of people.

STUDENT: Don't just say I don't know how to work with someone.

JOHN DENERO: Okay. Homework 2 posted. I've done things a little bit differently

this time. Now you have not only a description of homework

you are meant to do but also a file that contains all the examples without answers in them to

get you started. That should save you the pain of having to go through and copy everything

in the html in new file and might make the process of doing homework a little bit simpler.

[APPLAUSE]. And I will have you know I didn't go through

and copy and paste all the examples myself. I used Python.

STUDENT: In homework 1 if we didn't put the heard or will we get docked for it.

JOHN DENERO: What if you don't put bog Kno to homework for homework 1 will you be docked

or kicked out. Nothing bad will handicap. Try to stick with format but we'll do our

best to handle exceptions as they come up. JOHN DENERO: Question is: what happens if

I submit twice? Or 422 times which probably has happened in the history of this course

we annual look at last submission. That's true for projects and homeworks you can submit

multiple times if you find something to change. Don't wait to submit if you think you are

don't do it but you can correct later. STUDENT: In the homework with the e mail to

log off. JOHN DENERO: Question is: what happens if

you submitted long ago before there was a new submit script asking for Gmail address.

That's okay. You might not get e mail about this homework 1. But you don't need to go

back and resubmit. Okay.

Project 1 is due in less than 2ﾊweeks. Get started now. As opposed to on September 11th.

STUDENT: Oh La ha ha. JOHN DENERO: Or September tenth [LAUGHTER]

or 90. Get started go through and read the project. I'll tell you little bit about it

today and hopefully that will inspire you to play around.

Last time we talked about while statements among other things. Every computer science

course that is worth anything at all talks about the following sequence called Fibonacci

sequence. With wonderful mathematical properties. It's defined as first 2 elements are 0 and

1. Every element after is sum of previous 2. Add 01, 1, 2, 1 and 2 get 3, 2 and 35.

There are lofts mathematical properties. With historical properties of Fibonacci sequence.

It was not invented by Fibonacci. Nor is it the case was Fibonacci's name was Fibonacci

there was a mathematician leaned narrow doe P. and they called him Fibonacci of.

How do we compute it. We know each element is sum of previous 2. We could go through

and walk through the elements. Here's a program or function defined in order

to compute the Fibonacci sequence using tools we've seen there are other way to see compute

this. What's exactly happening here. We start out

by defining what is the first and second element of this sequence? And we call them pred and

predecessor and cur for current element. Currently cur stores second element that's why K is

2 on second line. And then while statement increasing K 1 by 1. Third, fourth fourth

element until the income tax element which is what we want and store that in cur and

each time updating we say we are tracking the current element but predecessor and store

whatever current element in pred assess and add them together as new current element.

And walk through exactly in environment diagram. But it's a good idea to think about ways you

can abstract away from mechanical details and understand what's happening.

So action happens in this 1 statement. We start with pred and cur.

Are bound to 0 and 1. Then we are interested approximate update which happens over and

over again inside the while statement. And each time the Fibonacci sequence exists in

the realm of values. Imagine and we are marching along it. So evaluate we execute the assignment

statement mechanically we evaluate both expressions, cur and pred, plus cur. And binding to the

names pred and cur. But we are moving our names along the sequence. So the first time

we execute, we move along the sequence 1. Now pred and cur as 1, and 1. The next time

we moved along the sequence again. And this way we track along the sequence itself binding

the names to values as we go. And eventually we get to the 1 we want and

be done. That's a picture of Fibonacci sequence.

That should get you little bit of refresher of while statements work. And how we bind multiple names to multiple values

through assignment statement that has 2 names on left separated by commas and 2 on the right,

names. So just to make sure that this makes sense.

There was a problem loading the Web page. Example:

I bind big and small to 3 and 4. 3 is pretty big 4 is certainly small. While it's the case

that big is still big bigger than 2, or small is still small still less than 2.

I'm rebind big, and small. Big is going to be bound to small 1, and small

is bound to big+ 1. So what happens what happened as soon as I

execute the while statement I updated the names big and small they might mean something

different than at the top. Your mission should you choose the accept it. Is figure out what

big bound to right now. Talk to the person next to you and see what's going on.

STUDENT: Big is 3. FBI fib Fibonacci sequence. Okay let's see how it came out how many people

think big is still bigger than small? Hard to tell. That's not fair I asked what

big was but not what small was. You need the keep track of both of. Big is changing on

what small is bound too and vice versa. Big right now is 1.

Let's see if we can understand why. What happened in this example was that we

started out with small bound to 4 and big bound 3. That's what I said.

Then I check this condition which says is big big? Or small is small? Both happen to

be true. Remember or means: either 1 is true or both. That means the whole expression is

true value and I execute the suite of the while statement.

Now I go through I'm about to do first assignment statement and let's look at big. It changes

to whatever the small is minus 1 so that is 4 3 is 3 and small 2. Big 3, small 2. I check

again. Big is big, so 3 is bigger than 2. Small is no longer small enough. But only

1 has to be true because we haveﾊ"or" expression connecting the 2. It is the case that big

a bigger than 2, it's 3. And therefore, we execute the statement 1 more time. Leaving

big as 1 and small 2. Okay. 1 example down.

This isn't about the procedure that Python carries out when its executing programs but

instead some advice about how you write functions that are easy for others to read.

STUDENT: In the example did big get you have 2 assignments of that small+ 1. . You use

updated value of big and/or whole value. JOHN DENERO: Okay I will answer that it's

important. The question is: when I'm evaluating this

expression and this expression, what values of big and small do I use? I use the ones

that are currently bound in the current environment. And I'm going to evaluate all of the expressions

on the right of the equals using if names they are bound right now in order to get the

values before rebinding. That's the execution procedure do all the values on right and then

the binding of the names on the left. Let me tell you a little bit functions of

functions are beautiful things that's why I say the art of the function. They are sometimes

so beautiful they make me cry. What makes a beautiful function? It's best

if a function has 1 job. That's the way we use as functional abstraction. Give it a flame

and have it doing some arguments giving us some return values. And having a particular

purpose for a function. If you are into metaphors a good metaphor

is scissors are good at cutting things that's all they do. You don't want a Swiss army knife

function taking everything figure out what it is and can do something with it we have

a name or Swiss army naives if you never heard of it before it would take me sometime to

explain what it is if you haven't heard of it knife, saw, citizens sors, splicing opening

cans this thing on back is an awl for holes. So function should've exactly 1 job. That

means each function is going to encapsulate some pit bit of computational process we can

understand as not kind of complicated mess of a bunch of things but 1 particular purpose

in the program. It's okay if function can be used in different

situations. Another principle people talk about: you are

not meant the repeat yourself when writing programs. If you copied and paste it had same

thing over and over in program and then you realize oh I want to change then you have

to change every topic that's prone to error because you might forget 1. Programs are easier

to understand if every computational process is implemented exactly once and then reused

over and over again. So you kind of get some leverage by programming

in that way. These are 3. Identical trip lets this person

actually repeated himself. It's best to define function. Here the function

for raising the number to power. It's best oh it only works for powers greater than 6

and less than 9 that are odd or something like that. But instead can handle all the

cases you might want to apply particular 1 too. The world has failed. There's a process

where we connect a electrical device to current. But every country has its own way.

For instance we don't have a square function in the standard library for Python because

we have a function for raising things to arbitrary power and that seems to be fairly general.

Okay let's see how we might put some of this into practice.

Remember, we don't want to repeat ourselves but also we want to manage the complexity

of our programs and we want to do that by using tools of abstraction. We will see here

that there are very practical reasons for that when updating program but conceptual

programs as well. When I want to separate the concerns from 1 computational process

from another but still combine them in meaningful ways. So generalizing a partner using functions

and then patterns by the end we will use functions in new way you haven't seen before. Which

is treating the functions themselves can be just like values.

Let's start with abstracting over different values.

Here's a case in mathematics. Regular geometric shapes relate the area of something to something

else. The shape of regular rectangle or square relates the length of side to square. It's

r. You probably know the formula for getting the area of square from length of its side.

R2. A circle, relates the radius of the circle

to the area of the circle Pi r2. A regular hexagon relates the length of side area of

hexagon, 3 mumble. We have 2 functions 1 of which is less familiar

than other 2. But they say something about the how I relate the length of some aspect

of this regular shape to the area itself. We can look for common pattern among all.

If I look for area of square and I can multiply 1 and that's no trouble then I say the things

that change with each shape are this 1 versus the Pi versus the 323 over 2. And if I hide

those details of computing the area then I see if actions I take whatever the length

I'm interested in and I square it. That's a way in which we can generalize this pattern

of figuring area from length by noticing they all differ in terms of number I multiply in

the front. And finding common structure like this allows us to have shared implementation.

So coding to see why this might matter.

Here's an empty file I will start defining some functions.

Here is a function for the area of the square with side length r. I'm going to give it 1

line description. And then return r * r.

Then I will compute the area of a circle with the radius r.

It's pretty close to that. I will copy and paste that.

Circle with area r. What happens here: is that I return r * r

* Pi. What do I need in order to do that. From math import Pi. I know pretty soon I

need square root as well. So now I want the area of a hexagon.

Copy paste again. Return the area of area of regular hexagon with side length return

r * r * 3 * square root of 3. /2.

Okay now I'm in business sure there's repetition but that's fine. I've defined the 2, 3 things

I need if I want to I can go up here and compute the area of a circle with radius den get 314.

Do you see a problem with these functions? Rep active, not general.

Also they are wrong. What's the area of a square when side length 2ﾊ well apparently

it's 4 that's not right. Well I want to check and make sure I haven't done something wrong.

So assert statement in Python that checks to make sure some condition true. So I say

I want the area of r to be greater than or equal to 0. The way assert works you put an

expression in here. This is Boolean context all we care about whether it's true or false

and then the message after that says no negative sides.

And I'll put that everywhere. Now we are in business. Now when I want the area of a square,

of side length 2. It will complain and say no negative r, please.

Any other problems? How about the area of a square with side length

0. That's not a square at all so something else is wrong now I need to go back and change.

Say I want this bigger than 0. I want to say r markup must be positive. Okay.

I'm good. No I'm not good have to duplicate this everywhere.

Sad day. Fortunately I'm good at typing fast so it didn't take long but you want to avoid

this to make sure it's consistent the structure of the program itself should make it consistent

for you. Instead of doing this, I could say, "Well, there's a general notion of computing

the area of something it has to do with having a length of side or part and then some constant

for the shape that tells me exactly what I'm supposed to multiply r2 by in order to get

the area of shape I'm interested in. Return the area of a shape.

What does that look like? Well, we just return r * r * the shape constant. But here's a good

place to put the notion that r must be positive and then I can take it out everywhere else

as long as I use the function I created. The area of the r or shape constant is 1. The

shape constant here is Pi. And the shape constant down here is 3 times

* the square root of 3/2. And now I get the behavior I want. And in

enforcing a condition I cared about namely that r must be positive only happens in 1

place that notion is shared across my code. That helps me not repeat and organize my program

a little bit better. Also it is a means of abstraction. So I talked about the area of

square as special case of some kind of area. This is not the most interesting example.

But it's supposed to prime your mind for more interesting example we are about to do.

What I'm priming you for is that when we say that we can write a general version of a function,

we don't necessarily just need to parameterize it by some number we pass in like a constant

for the shape. But we can really pass in any computational process we are interested in.

The way we do that passing it as argument to a function another function.

So a function that takes another function as input is called aﾊ"higher order function".

It's called that because it's in the business not of manipulating numbers but computational

processes themselves. It's a computational process that takes in other computational

processes. And might run or not or multiple times. That's

a higher order function. Let's look at an example of that notion in order to find some

commonality among a bunch different things. Okay.

Questions so far? No questions about the area of hexagon? It's

like 6 triangles. We are trying not to generalize over computational

processes. We will start with some not very exciting computational processes it's important

to start simple to illustrate the concepts but next week they will be really interesting.

At least I think they are. And they are things I use in my day job. Common structure among

(On screen). It's not a shape constant but something you do.

For instance here's 3 different equations. The general mathematical expression is on

the left. This says the numbers sum the numbers 1 to

5 and we are sum the number itself, K. Here's what it looks like when expanded 1, 2, 3,

45, hopefully that's the answer looks right to me. Next. We sum the numbers K from 1 to

5 but cube of each 1. 5 different cubes summed up 225.

Finally down here we have a summation over some complicated expression that has a K in

it. Where did I get n this? From someone else. What does it do. A sequence that K it rates

to something large converges. Any guesses. STUDENT: Pi.

JOHN DENERO: Through Pi it's not there yet. But this is a way you can compute Pi yourself

instead of looking it up in a book. Okay.

What do these have in common they have a big sum symbol that's for sure.

And in particular they all have exactly the same sum symbol can same parameters of starting

and ending K. The only difference is sum over K itself or K cubes or some complicated expression.

Which gives us summation that converges to Pi.

Okay so here what we are circling last time it was a bunch of numbers here it's expressions,

expressions of K. Let's implement some of these and figure out

how to abstract them. Questions?

We might want to sum the natural numbers. So this gives us the sum of natural numbers

from 1 up to 5 is 15 we saw that already. How are we doing this? We star by saying there's

a total sum I commuted so far which is 0 at the beginning and then sum K which is the

current number I'm summing and I walk across from each term in the sequence that I am summing

up. So total 0, K 1. It's the case that K is either

less than or equal to n, we go up through n, we are going to rebind to names total and

K. What's total going to be? Well, total is going to be whatever total

was before plus K and K is 1 more than it was. And then return the total we got.

Let's check and make sure we've done correctly. Sum_naturals (4) touch 4 we get 10, 515, and.

We

also sum cubes. We can start with the same idea of total and

the K. Being 0, 1. Then while it's the case that K is less than n rebind total and K.

Total is whatever the total was before, plus K raised to the power of 3. Then K will be

1 bigger than it was. Now, when we sum cubes up to 5 we get to hundred

25. Let's look at these 2 things.

Where are they different? STUDENT: 5.

JOHN DENERO: So it's actually everything is exactly the same. Except for here I have power

K, 3 and here I just have K. Here it's some expression involving K here's another expression

involving K. Let's write the 2 down. 1 is the identity function of K. Just returns K.

The other is a function that cubes. K to the power of 3.

So power just races something. Okay so here are the 2 different things.

Between sum natural and is sum cubes. Is that either we take K and just add that to total

or we take K raised to the third power add that to total. Let's see if we can write down

a general notion of summation which has some number of things we sum up. But also computational

process which is a name bound to some function and we are calling it term. Term is: the way

to compute the Kth term of sequence I'm summing up.

Okay. What does this look like? We start with 0, 1. Then while K is less than or equal to

n. Total, K equals total+ﾊ okay he's the thing we always make different. K+ 1 and return

total. Owning now what do we put here. It's not K.

That would be specific to something naturals it's not pow K 3. It's in fact whatever you

get if you take the function we passed which we call term and apply to number K. If we

pass in K to the identity then get K back. If it's passed into the cube then we get the

cube of K. So the question is: is this just a sketch

of what's happening or does this actually work. The answer is it works. We are passing

in a function here. How do we do that. I will write down a new version of some of naturals.

Def sum_naturals. How does it work? It returns a general summation of (n terms.

But the function I will apply to each term in order to get the term I had together is

calledﾊ"identity". And then I can redefine some cubes (n) as

return summation n but what I do to each thing I assign is cube it.

Let's see how we've done. We want to make that small.

So can we still sum naturals? Yes, we can. What happened we call this sum naturals it

said please give me back whatever summation give me back if I defined combined a bunch

of different identity of K, so K itself. And can I sum cubes up to 5, yes, I can. I want

to run summation but cube each term before adding it to go.

STUDENT: I think you defined those 2 functions twice is that legal in Python.

JOHN DENERO: So what happened with I have sum naturals once here and again up here.

Remember what happens when you have execute def statement you create a new function and

then bind to name you've given to that function. We created the function and then forget about

it we rebound the name sum naturals to other function. If I delete it everything still

runs. What's happened?

We have this general pattern or general computational process for summing things together. And then

we've said: the way in which we could use this we could plug in particular function

like identity or cube. Into this summation and function use that.

Now notice there's no def term anywhere. Term is a name bound to a function that we

define elsewhere and it's either bound to whatever identity is bound to. That's the

identity function or whatever the cubed function name cube is bound to. That's the cube function.

There are no parentheses after it. We are naming the function and passing it in to parameter

to summation. (Function) I could def Pi term. ﾊ let's that was 8 ﾖ by what you get when

multiplying (On screen). And now if I want, the summation of 10000

different things where I apply this Pi term function to each 1 and then sum together then

I get a pretty reasonable approximation of Pi at least up that far.

STUDENT: When you call summation does it evaluate. (INAUDIBLE).

JOHN DENERO: Question is: When does a function get evaluated you pass

in. I passed in the function cube into summation I haven't actually call it yet. Only called

when I get to call expression here which says go figure term means will it.

Now I want to apply that function to whatever parameter or whatever argument a pass in the

current value of K that's finally when evaluating this call expression that's when the function

cube or Pi term finally gets called. Okay.

We generalized the computational processes. What happened was: we defined a function of

single argument. It's not called term it's called cube that's important this is about

cubing things specifically. Term is formal parameter that will be bound to the function

we created by the def cube statement. The function gets bound to term and then called

down here. When we actually call it that's what's going on in doctest. Is calling summation

naming the cube function and passing that in as argument which gets bound to term then

and then we call it as we wish over and over again within the suite of that while statement.

That's why we get 1 cube (On screen). You can't do this in all languages but you

can do it in many. And when they invent new language these days they let you to do this.

It's useful. It allow to go see abstract away from the general notion of computational process

and pass that computational process around. I will skip that until next time.

But I want to say a word about the purpose of higher order functions. So functions can

be actually no I want to do the example. It's so cool. Let's do it.

1 more example. So not only can I pass in a function as argument. I can return a function

as return value. Here's what it looks like: I will return a function that takes K and

returns n+ k. Here's how it works:

Add 3 is new function we create by calling add make adder and when add 3 to 4 I get back

7. The way I do this is define a function within another function. I call it the "adder"

and it takes in exactly 1 argument (k) but what it returns is n+ k.

I created the adder function. And then I Western it. So name the function I created and then

I used it in order to create new functions along the way. How does it work? Well I can

make an adder for 20. That will give me back a new function. It's

calledﾊ"adder". How do I use it let's say I bind it to a name like: add 20. Then I call

add 20 as many times as I want. I can call it on 1ﾊ whoops.

And I get 21 so on. I can add 20 to whatever you get when adding 20 to 12. And I get 52.

So notice the cool thing about this: this is a function of 1 argument, but as adds the

2 names together and nowhere in the global frame are either n or k defined, but instead

this adder function is allowed to see whatever names are around in the function in which

it was defined. So adder can see the end that was the former parameter. Make_add.

Okay. Parameter.

Talk to the person next to you and see if you can figure out when I type that.

Go. What is that thing? Have you seen something

like that before? It looks like some sort of emoticon.

Smiley. It's not it's a call expression. It gives you back 32. Let's look at how it works.

Functions can be defined within other functions. So when I type make_adder like this. I create

a function that gives me back a function. I've bound the name add 3 to that function.

I've created a local def statement which binds adder in local frame to new function I create

and I refer to both n and k from this position in code and with expression adder 12, 2012.

What you are looking at is call expression with a compound operate.

So remember: call expression has operands and operator. There's your operand and operate

how do we evaluate the call expression we evaluate the operator and operands and apply

the function that is the value of the operate to the values arguments of operands. So we

have to evaluate this call expression that's labeled operate right now and that gives a

function, a function that adds things together and now we have an expression that evaluates.

To 2. And then we apply this function which takes whatever it takes and adds 1 to it and

add that to 2 and we get 3. So make adder 1, 2, gives us 3. Because this

evaluates to a function that adds 1 to anything I pass into it.

STUDENT: How does Python know to make adder 1.

JOHN DENERO: Question is: how does Python know in advance that whatever this complicated

thing is you typed in as operate give you back a function. It doesn't so it tries to

evaluate whatever you have as operate expression and if it's a function it applies and not

it gives error. For some reason you put something else complicated

here like 2+ 2 and you try to use that as function. That doesn't work it gives number

not function. But this gives function that's what you want in that position in call expression.

STUDENT: When you type make_adder without declaring something as that it will say whatever

some point in mechanic memory is there a way to get there to that memory.

JOHN DENERO: Good question but we'll talk about that on off time.

So let me summarize functions are first class in Python. That means they are values. Values

include numbers but also include functions as well. What does that mean if I have a function

which is first class function which I can manipulate. I can pass to oh functions I can

return as value. I can anything to function that I would do to a number that makes sense.

Higher order functions take function as argument or return value. They operate at the level

of computational processes and we can express general methods of computation. Remove repetition

from programs. We only need 1 while statement for summation. Not a bunch. And allow the

concern of how I compute the particular term of this Pi summation from the general process

of just adding up a bunch stuff together. Okay so 1 thing we didn't get to was we were

playing a game for your project. But we don't have time. So sad.

So we'll play it another time and hopefully I can post an online version. Have a good

weekend. See you soon.

Announcement, announcement, announcement: there's no lecture on Monday, it's a holiday.

No section. But if you really want to go to section, you are welcome to crash a Tuesday

section. Sections are a good idea if you want to understand this but priority will actually

go to the people who are enrolled in that section. Okay. See ya.

25