Computer Science 61A - Lecture 4

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