Computer Science 61A - Lecture 3

Uploaded by UCBerkeley on 29.08.2012

JOHN DENERO: Okay. 2 announcements homework 1 due on Friday at 5:00Êp.m.
It was posted last Friday. Now's a really good time to take a look.
The way I suggest you approach homework is that you first just read through it and with
a paper and pencil think about how you might solve them. Sometimes the computer can be
distracting when you knowing when you think about a new computer science problem it's
good to think through it without immediately jumping into process of writing code.
The second thing to note: there's a lot of activity.
You can now submit online direction are on the Web site. What's happening is that we
are introducing a new system to give feedback in this course for the first time. The way
we will do it instead of you turning sheets of paper and us writing comments and then
returning them and you never bothering to pickup, which is usually what happens. Instead
you submit online. We will take whatever you sent us and put on Web page and insert comments
right there in a Webbased interface and you will be able to respond. So the if you disagree
with something a reader told you now is your chance to air grievances.
Now what system will we use to do this? This is intentionally small because it has
the answers to a project in it what's happenings you submit a project or homework to us. We
generate a Web page that looks like this. Which has what we gave you in the first place.
Other projects with starter code with places like your code here. Marked there and then
when you complete your project you filling in the regions on the left and right the difference
between what you started with and what you handed us.
Then in this Web interface people are allowed to make comments we can too. And they will
say things like: Oh, here's a suggestion you could called a function instead writing code
instead. So you are looking at the same tool that we've
used within Google for years as internal code review tool. Every time I write a code I century
send to a peer and say please read this make sure it looks write and your feedback make
sure it looks right before we put it in our service. Google isn't the only 1 to do this.
This is standard way in which programs are developed in industry. And useful for you
to start developing programs here in the University setting you can get feedback and this isn't
all telling you whether you did it correctly or not. But suggestions of how you can make
I easier to read. So remember I'll say over and over again programs
are written for other people to read and only intentionally for computer to come along can
and interrupt them as well programs easy to read by others often are extended and get
used and persist for decades where's where has more complicated ones tend to get disregarded
or rewritten. A. It's important you think about I'm actually
presenting ideas when writing program and I want to present them clearly.
So a lot of feedback you get through the system is focused on that theme of making things
as readable for overs. It's caveat the system was developed for Google
and opensourced and now for this class it turns out it only knows people who have Google
accounts. [LAUGHTER] I'm sorry I'm asking you all to have a Google account. It turns
out Berkeley EDU account will be Google soon maybe it is already. How many people think
they have B Cal or Googlebased Berkeley account? In October this will change. You will have
Berkeley mail look like Gmail and your Berkeley calendar will look like calendar and all this
stuff is happening but not in time for this class. So if you want to use the system with
Web site that shows you everything with pretty colors and such then you have to have Gmail
account. It can 1 you created for this class and throw away but if you don't want to do
that because you aren't interested in Google that's fine but you won't be able to respond
to comments but just an email. That's the submission system read the direction
on the Web site it's new. You might not find hiccups with submitting homework 1. In 2Êweeks
you will submit your projects which is where you get most feedback.
Project 1 is posted it's due Wednesday September 12th in 2Êweeks.
Someone has a question. I can tell. STUDENT: Right here.
STUDENT: Could we make a Gmail account to use with this and then later switch it to
our Berkeley account. JOHN DENERO: Switch to the Berkeley account
becomes Google absolutely. What email address do you want to use to get feedback for the
project and you can update sorry it's not all ready to go with your Berkeley account
just yet. So I will introduce the project on Friday.
I think it's fun. It's always a good idea to start early. If you don't start writing
programs you can at least read it understand what's going on so you can start thinking
about it and talking to your peers about how you solve some of the problems in it.
STUDENT: Is it by ourselves. JOHN DENERO: The question is do you program
by yourself or pairs. The projects and homework can be completed in pairs so pick someone
from your section do soon get together and start working.
It's better if you work together as opposed to dividing the project 1 does half. That's
a good way to get neither half done. Work together. Sometimes you only need 1 computer
and 2 people and you discuss as you go. STUDENT: That's the partners have to be in
the same section. JOHN DENERO: Partner in the section: yes.
Okay. I'm going to review things you've seen before.
We've seen def statements call expressions and calling and applying which is a diagram
of what happens when we call or apply a function. What you are looking at here is def statement
we give a name to userdefined function. We give formal parameter, that's a name for argument
a pass in. And then also the body of the function I'm defining which right now is the word return
indented that's important. So it's a return statement then we have a
return expression. That return expression is what we are abstracting.
We have this expression basically give it a name by calling I square. That's the body
of the function that's going to get evaluated every time we use the function. With def statement
we create a new function. We bind to name of that function square to the value that
function itself. We also have calling expressions they consist
of operate and operands those are both expressions themselves and operand in this case is 2+
2 an expression. The argument is value that is what the value is we get when evaluating
the operand. Here's operate that's expression to the name square and if we look it we get
back the function square X. What happens when we see call expression we
evaluate it. The procedure is the operate and operands are evaluate first and then if
function which is the value of the operate is applied to arguments which are the values
of the operands. So that's the function called with the arguments.
The last piece here, is that we have a diagram for calling or applying functions this is
telling you a function itself is some computational process that takes inputs that has a signature.
We know it takes 1 argument here because it has 1 thing within parentheses.
It takes inputs or argument here's the number 4 and has return values.
There's argument and return value. What happens when we call or apply a userdefined
function when we create a new frame? Which is hoteled bindings from names to values.
We are going to bind to the formal parameters to argument values we passed in and then execute
the body have evaluatings return expression. That's what I've talking you so far.
If you want to go back at other slides it's a good idea of course this is shorthand in
the column that says what happens that's over view of processes we have so far. In order
to create new userdefined functions and apply them via call expressions.
Okay. Now question.
STUDENT: What happens to the frame that's been created.
JOHN DENERO: What happens to the frame that you create well after you return from the
function you don't need the frame anymore at least in these examples we can effectively
think it goes away in diagrams we can leave there. The details of what happens to the
frames aren't important for execution. You can imagine they accumulate but sometimes
the computer needs be and say I don't need them anymore.
Here's a diagram. With multiple input. From operate I import mul. That multiplies. Then
I will define a function square X which returns the multiplication of X and X together.
And then what I'm doing is square the square of 3.
So the square 3 is 9 square of 9, 81 we should get 81 here. Let's see how it happens.
Well, 1 thing that happens first we look at call expression and evaluate the operands
and operate well the square 3 we have to figure that out of the that involves apply ago userdefined
function square where we create a new frame tonight round and bound the parameter X to
argument 3. Here we now execute the body of square function
meaning we multiply 3 times 3 with return value of 9. That is the argument to the outer
call expression we are trying to evaluate in the first place.
We evaluated square 3 which is operand and now we have its value, 9. And we pass that
to the square function generally that involves creating new frame. We've defined the function
once but called it twice. That's important we've been able to write some code and reuse
it. Computers are really fast and so it's a good idea if we don't have to specify everything
they do line by line but instead define some general computational methods and ask the
computers to do those over and over. So we are squaring again. Now we have a new frame
square but now argument is 9 so bound X to 9 so old frame is around but we don't use
it anymore and X is 9 and 9 and 9 to go with a return value of 81.
That's multiple environments on the same environment diagram. We have multiple environments meaning
X actually means multiple different things. At different stages of the execution of this
program. The way we make sure we have the right X at
the right time is via these frames. Okay.
Let's just piece it apart we had square, square 3. We actually had to use as call expression
break it up with expression tree. Square was square function square 3 we had to evaluate
so there's square and 3 and we got to this point in the diagram. We have the value of
9. Then what. Apply the square function to 9. Everything on the same row in the tree
the function ton left the argues on right of the how we got this diagram and what's
going on here? Well I told you an environment is sequence of frames.
Why don't you count the number of unique environments that are right now depicted somewhere on the
diagram. Talk to the person next to you and figure out how many environments there are
in this diagram right now. Go.
Depicted. JOHN DENERO: Okay. Let's convene an environment
is it a sequence of frames. So many frames what exactly is an environment
in this picture? Well, I told you last time there are 2 kinds of environments we have
had so far the global frame alone. That's the environment in which we are going to evaluate
square, square, 3. And then a local and then a global frame so 2 different frames to go
that forms on environment as well of and those are environments in which we valleyed mul
X, X. We have 1 environment. Which is just global
frame alone. We have a second environment which was that first frame we created the
local 1 followed by global 1. So it's 2 frames in sequence.
And then we have a third environment which is: the new local frame this is for squaring
9 instead of 3. Followed by global frame. Notice that all of these environments include
the global frame somewhere in the sequence. Either as the only thing in it or as second
element in it. And therefore they all have access to names
like mul and square. But they might have different name, different
values bound to the name X. So the answer is 4, 3, [LAUGHTER] 3.
Just keeping you on your toes from now on whenever I draw an environment draw I will
put link at the slides if you want to go back and load that link it will bring to you interactive
Python interpreter and you can play with example yourself.
Names have no means without environment this is why we have them. So names mean something.
Every expression is evaluated in context of environment. And a name evaluating the name
value bound to the name (On screen)I said that before but I told you.
Let's look procedurally at that. We have 3 environments on the screen. And let's say
that we are in the process of evaluating the whole thing and now doing square 9. And we
are inside the body of square in this green highlighted line return mul X, X that means
we have to evaluate the expression mul X, X.
Which means we look up both the names X and mul. How do we do that? Well current environment
is the local frame X bound to 9. Followed by global frame. Both names we look things
up in that order for the name X we first check and see is it in the local frame there it
is. We are done X means 9. Mul we look in the local environment first check if it's
there it's not therefore we check global environment there it is we know how to multiply.
So the purpose of these environment diagrams is telling you what names mean when.
And this process of looking up names walks through a sequence of frames 1 by 1 checking
for the name using the value if there otherwise check the next frame. If we never find the
name, that's an error. If I checked everywhere and I couldn't find it.
Questions? Why is there not mass confusion.
STUDENT: The order local and back to global frame.
JOHN DENERO: What's the order? I say it's a sequence in order to order is local then
global. Pretty soon there will be more too but for now every example is that.
Notice I didn't say we look here and then we look around in another local frame and
then global. It's just 1, 2, and dunk. Okay.
I showed you a slide that looked like this return square X (On screen).
Should do the same thing. Because every time I have X I could replace
with Y and it would only affect the local frame which is used in the evaluation of body
of that function nowhere else and this therefore if we changed the name we would be all right.
STUDENT: Would you say the global frame is. (INAUDIBLE).
JOHN DENERO: We have to talk about it more to make sure that's right.
We said formal parameters have local scope. And demo.
Even more complicated 1 than last time. First question what happens when I hit return?
Notice, that I haven't imported mul yet. We are okay why? When you execute a def statement
you don't actually do anything with the body except for keep it around. You don't look
up names not evaluating it the program hasn't bothered to figure out whether mul works now
if we called this function right now we would run into a problem. But (On screen)now we
know that mul means multiply in the global frame.
Last time I showed you what square 3 did. But now I will square and then square 2. Talk
to the person next to you and see what this does where I reuse the name square a lot in
this demonstration. Go. How many people think it will say 2. Not many
what about 16. How about an error? 16. Excellent job.
What's happening here. Is I've changed what square means. I said now it means square mul
return mul mul. Mul mul mul mul mul mul [LAUGHTER] I'm square 5. Talk to the person next to you
see what that's doing?
JOHN DENERO: Here we go. Here we go. How many mules does it take to break this
thing. Well apparently this M. it says not callable int object is not Callable it means we tried to say 5 (5, 5) this is
call expression when operate is not expression but a number.
Let's dig into this and try to understand what's happening.
STUDENT: What just happened? ! ! JOHN DENERO: Okay. Here is def square mul
return mul mul mul mul mul square of 3. What I've done just to back up a bit. Defined
the function I've called it with the argument 3, notice that in the local frame now I have
a binding of the name mul. To the value 3.
I also have a binding of mul to the multiply function which is great except for we will
never find it when we look the mul we check local first figure it's 3 and by 3 to 30 and
3 which is exactly the error we saw we tried to call an integer that's what int is. We've
used same name in local and global frame therefore we say the global name is shadowed we can't
get to it anymore the local frame comes first. This will same error as well question.
STUDENT: Is there a way to bypass. (INAUDIBLE).
JOHN DENERO: How could I get that global mul that's the 1 I want when I have a local mul.
You cannot do it. If you try really really really hard you can, but we won't go there.
When you shadowed a name effectively the bindings for that name for other frames later on in
environment are no longer available. STUDENT:
JOHN DENERO: The question is what happens when you write a function that calls itself.
We'll talk about that extensively but not today [LAUGHTER].
STUDENT: Let's say instead of importing mul in the global frame. If we did that in some
defined function and insteadÊ then we used mul in a second function would thereby an
error there? JOHN DENERO: Import inside the body of function
that will binds the name inside the frame only.
That's a detail that doesn't come up very often.
Okay. Now you know a lot about names and a lot about
how Python or number of other programming languages organize the memory to keep track
of what names mean. Now we will look at other features of language
that allow us to do more interesting things than just divine define functions and call
them. These things you can start layering together
in order to write more interesting programs. Now truth is we don't need all this. You can
compute with functions alone. But sometimes it's useful in order to have a readable program
to introduce other different methods such as these things we will go through in order
to kind of structure the program in way that it's easier to follow.
Demonstration time. Is that big enough? I didn't hear enough yes's.
STUDENT: Yes! That is pretty big okay.
JOHN DENERO: So first thing I told you about Max as a function.
It takes the maximum name. I can put new names and F23, that's what it's bound to arguments
2, 3. Now I can import add and mul but also use symbols+ and X so 2+ 3 on the first day.
Notice Python knows something about the order of operations that's equivalent to adding
together 2, with what you get when multiplying 3, and 4 then go back and add that to 5.
Oh. STUDENT: Parentheses.
JOHN DENERO: What did I did. STUDENT: Parentheses 1 more.
JOHN DENERO: That's what I meant. So while we do this it's easier for humans
to read why we do this we don't know need to know about presents of times of in cases
where you think it's there are esoteric rules of how things go together that's not true
for+ and times. But sometimes function notation makes clear about what's happening first and
second because operates when we use this function notation it's convenient to see what operations
happen first and what operations happen second. Okay. So we define functions already.
Well I told you a lot about assignment already so I can say X is 3, F is Max, I can now do
F(X) and 12. And get 12.
I told you I could bind 2 names to 2 values in 1 statement.
It turns out we can combined 2 names to 2 values import 1 name with 1 import statement
we can also return to values from a function in 1 return statement.
So I could say: def divide_exact. We give numerator and a denominator.
And we are going to return as a function called floordiv. What happens dividing n by d and
ignore the remainder. And we can also get remainder itself called mod. That happens
when dividing n by d but ignore the quotient and only keep the remainder.
What does this actually do? Well, if we say the quotient and the remainder
of divide_exact (2012, 10) 201 is quotient and 2 is remainder that's what we get left
over when dividing 2012 by 10. Sorry.
STUDENT: What does floordiv do again? JOHN DENERO: Floordiv. Takes the first number
and divides by the second number but then ignores the remainder. Instead of getting
the fractional value 201.2 we just get integer part 201. That's the quotient of the 2 remainder
is whatever is left over of we took 2012 we took 20110 and is we were left over with 2.
Okay now functions are fairly complicated people are asking questions. Maybe we should
start documenting what they do. From now on instead of writing the examples inside active
session I will put them if files so we can look at them and execute them at the same
time. And you should be doing this as well. What
does this look like? We are starting a new file with my favorite
editor. STUDENT: Yeah Boom!
JOHN DENERO: Make it really big. Now you can edit a file with any program you want. We
tell you Emacs because it's on every system it works well and people love it. If you don't
love it try something else talk to TA or pee at is a or talk to me. I'm not recommending
you to learn what I use and I'd rather you to focus on programming rather than complicated
editor. I might define a function called divide_exact. That's annoying.
I'm creating a text file at this point. I will take numerator and denominator the first
thing I do is add dock string 1 sentence description of what function does. That's useful if someone
is coming to use. So we say return the quotient and remainder
of dividing n by d. I had a brilliant idea. I will put that there
this down here. We'll see both at the same time [APPLAUSE]
Hmm innovation people! [LAUGHTER].
And then we might put in return floordiv (n, d), that's how we return multiple values it's
okay to make mistakes in file I can correct them. I can even go back here and write things
up at the top. Okay.
What happens when I create the dock string? I started out with throw quotes. The reason
you do that is that means you can put the dock string expand multiple lines if I want
1 line I put 3 quotes at the end and I'm done. But if you want more information inside the
top 3 and bomb quotes. You can put examples there.
Maybe somebody doesn't know what quotient and remainder are by dividing so examples
here's 1: If I divide_exact (2012, 10).
And I store those in quotient, and remainder =.
Then what happens? Remember I'm just editing a text file nothing interactive I'm typing
in it's nice to have colors but that's it. It's up to me to say what's happening next.
What's happening after assignment statement? Nothing.
But then if I look up the name quotient I should get back 201 and remainder I should
get back 2. Questions?
Is there some huge error everyone is staring out that I don't see okay maybe not. We have
description of what's going on and some tiny body of function that does the work. But the
nice thing it shows you exactly how it's supposed to work if someone says how do I use this
thing. This is how F. what can I do with this file? 1 thing: interpret it with Python and
then once I'm done interpreting it I can start interactive loop in order to call the functions
that I've defined. So I can Python 3Ê I that means start interactive loop when done reading
the file. Div dot Pi. We know what divide_exact is and we call it
12, 7 and we should get 1 as quotient. Q, r, 1 is quotient and 5 remainder.
Now I put all these different examples inside my file. What could I do about that? There's
another command called Python 3 m doctest if you added these are in lecture notes. It
will tell you what it's doing. What doctest does: It looks for interactive things that
I provide and checks to see if they do what I say.
Let's see what it says. It says I tried quotient remainder equals divide exact 2012, 10 and
I expected nothing to come of in a and that's exactly what I got nothing at all.
Then I tried the evaluate the name quotient and I expected 201 that was okay too and I
fried remainder and I expected 2 that was okay. So 3 of my tests past and 0 failed.
Hoar ray. It doesn't say HOORAY I wish it did. Python look at div Pi run the example
and is and make sure they do what I said to do.
You will use this a lot when developing projects. Okay of let's look at other features of Python.
1 thing we can do is figure out comparisons. So we can ask: is 4 less than 2. No. Is 5
greater than or equal to 5 yes. These are operates that also have functions
corresponding to them. We can look up all those as well but not today in intestine of
time. There are functions that are vers of these
things but sometimes it's easier the read 4 is less than 2. And I can even combine them
together. So I can say true well that's rue and I can
say: is true and false combined together something that's true or false that's a definition you
combine something true and something false you get false as aggregate.
(On screen)if I said is 4 less than 2 and/or 5 is greater than = to 5 this is not true
but this is. So whole thing will be true because the or
said is 1 or the other is true. Answer is true. We can combine different truth values.
Why? That's in order to be able to decide to execute different lines of code based on
different arguments that might come into a function.
Let's put that into practice. Aggregate.
Now I will define a new function: called absolute value of X.
Return the absolute value of X. What's absolute value supposed to do?
Bypass 3 it's supposed to give you back 3. That's all the documentation I will write.
What's the body look like. If X is less than 0 then I will return X.
So if I get 3 I'm negating the negation I get 3.
Otherwise if it's the case that X is 0, I'll return 0 and if neither are true. Then I just
return X. So here's another feature of Python. It's
called conditional statement. How does it work? Well, I can: Python 3/I
div dot Pi. I can absolute value 24.
And I get 24. I defined in this file and reason interactive session. And I tried it out.
Okay. Last example for the day:
Let me stop questions? STUDENT: Python used the word.
JOHN DENERO: Great question but I'm not going into it because I want you to read all about
it. JOHN DENERO: Question is can I define a function
within another function and another function within that he went ask that part I added
that. Yes we will do that Friday. Last thing is a wild statement.
So for instance I can have if I wanted to add up all the numbers from 1 to 3 then I
might start with zeros for I which keeps track of which number I'm adding and total which
keeps track of what's o going onÊ the total amount of numbers I've added so far. And then
I might write while it's the indication that i is less than 3. I make I equal to 1 more
than what it used to be. And then I make total equal to whatever it was before. And then
I add in whatever I is right now. If I see what happens at the end I found the
total is 6. That's all the number 1, 2, 3 added together.
Okay. So that's world wind tour of Python features.
Now you know really everything you need to know. In order to do homework and start your
project. I will spend next 7Êminutes going through the procedures that allowtous evaluate
these things. Question is: why is square, square, 3, 81
it is 81. Okay.
STUDENT: There's a typo this bes. JOHN DENERO: There was a typo on the slide
that's why it said 27 sorry I will fix that. Let's go through what I've told you in structured
way so you understand exactly what's going on. I don't want it to feel there's magic
inside Python it's carrying out a procedure in order to evaluate your programs.
A state statement is executed by interpreter statements are different from expressions.
Expressions are evaluated, they have a value. Statements are executed and something changes.
Assignment statements change what a name means. Now, in general, there are 2 kind of statements
simple fits in 1 line; like an assignment statement or return statement or import statement.
A compound statement might have multiple parts header lines other header lines and statement
that are indented the whole thing together is called statement.
Each thing with starts header and indented statements after is called a clause. And within
a clause if you ignore the header and just look at the stuff indented that's the suite.
It's useful for names for these. That allows us to describe the process when we use them
to have the first header determines statement type. The (On screen)it can actually determine
when and whether the suite statements are executed at all.
Notice in a def statement the body of the function doesn't actually get executed right
away. It gets squirrelled away and only executed when someone calls that function.
Squirrelled is the word in the English language that has the most letters but only 1 syllable.
STUDENT: Oh interesting. JOHN DENERO: Def statements are compound statements.
What other compound statements can we look at? So a suite is sequence of statements what
happens when we execute a sequence of statements it means we execute the statements in order.
We execute first 1 and then if something doesn't tell us otherwise we execute the rest.
Just walk through in order unless something tell us don't do this.
1 thing we can do is have local assignments that means assignment statement inside the
body of a function. This might seem obvious now but I want to tell you it's okay. What
happens when you have an assignment statement like the second line. The difference is absolute
value of XY that makes binding if local frame. So difference shows up here in local frame
because it happens inside the body of the function. So assignment statements what they
do is evaluate all the expressions on the right of = and then bind to names on the left
the resulting values on the right in the first frame of current environment of depending
on what the current environment is when assignment statements is executed you will make a different
binding in different place. Play with this. Conditional statements here we have 1 big
statement with 3 clauses, 3 headers, 3 suites. What happens with conditional statement each
clause is considered in order. We look at the top and we say what do we do with this
we want to evaluate header expression if X is greater than 0. If it's true we execute
the suite and skip the remaining clauses only execute 1 of the suites in a conditional statement.
We look in order till we find 1 that's true. What's the business about being true or false.
Logician George Boole. Boolean contexts. He's really important so we will make him big.
He keeps track of expressions that sit in the head ors of clauses of statement. He's
interested in whether it's true or false value. They are both values other values are true
and others are false. The false in Python are false but also 0 none. Also string without
anything in it. And true value is basically anything else. So anything not false is true
but there are a bunch of values false is most common. The Boolean contexts and deciding
whether it's true or false value when evaluating the expression. And if it's true I execute
the suite that follows if it's false I check the next 1. It's important how it works but
it has a lot of details but read section 1.5. Now we have the while and then we are done.
The execution for while statement is we evaluate the expression that's in the header I is less
than 3 in this case and then if it's a true value, we execute the entire suite. We don't
go back and check until we are done executing the entire suite. That means we increment
I and add something to total. Then once done with that we return to Step
1. We evaluate the headers expression again. This is only useful to do again if there's
a case something has changed. So what you will see within the body of a why would body
suite or why would statement there are change to names that show up in the expression. There's
George keeping an eye on that. And what happens walking through the code. First I and total
are bound to 0 and then check to see if I is less than 3. It is then we go and execute
the whole suite change (On screen). Then we go back and check the while header expression
again is I less than 3. Yes it is it's 1. Then I go will you and I make 1 i Bound to
2 I make total bound to 3. Because we added 2 then go back and check again. Is 2 less
than 3 do again. I is now 3, total is now 6 we have to check 1 more time. Is 3 less
than 3 no it certainly is not so we are done. That's why total was 6 after executing the
while statement. We are done. I'm happy to talk after, but we are done.