Computer Science 61A - Lecture 9

JOHN DENERO: Announcements are that there is a
midterm in this class next Tuesday at 7:00ﾊp.m. STUDENT: Woo! Yay.
JOHN DENERO: Where go to the course Web site with a page of midterm information at the
top it tells you the rooms it's in and login ranges there please go to the room that's
assigned to you based on your login. There are maps to get you there. 1 Pimentel is right
here. There's information for you that tells you you can bring 1 page front and back handwritten
sheet of notes of your own design that can contain whatever you want.
And then we will provide for you midterm 1 study guide which is published you don't need
to bring to the exam it will be stapled to the back. It looks like this. In small print
and that has slides. That I think are important. STUDENT: Whoa [APPLAUSE].
JOHN DENERO: You don't need to hand copy this on to your sheet because you will have it
with you that would take a long time.
STUDENT: Does it mean it's going to be really hard?
JOHN DENERO: It's going to be really hard! . To prepare you for a really hard exam you
look through the topic list, of all the things it could cover. Notice there are particular
emphasis user defined functions iteration and higher order functions there is a practice
exam. Look at midterm 1 but you can SKAUR 2 as well. There are review sessions. 2 of
them in fact 1 is run by our core staff tomorrow at 2:00ﾊp.m.
I don't know yet whether we will figure out the Web cast so I recommend come. But we will
try to get it on Internet. There's second 1 on Sunday at noon in Soda Hall run by HKN
volunteers who like to teach. You can go to both they will be different content. The first
1 before you show up you look at the practice problems which are linked here and do on your
own first. And then during the session they'll tell you what's going on with them.
That should help you prepare. Office hours on Monday and Tuesday of next week. Come and
talk about the exam if you want. Questions?
1 more thing: homework 3 is posted. In my day, we would call such a homework a
beast because it goes and it goes and it goes and it goes and and it goes and then you are
done.
STUDENT: Whoa. JOHN DENERO: If you feel like you run out
of things to do because you turned in project for that's what homework 3. Data abstraction
is on there mostly. We talk about that Wednesday. If you want practice with data abstraction
start now. It is due next Friday.
Before starting the homework you get to listen to me tell you about sequences.
Last time we talked about abstract data types which are constructor and selectors by behavior
condition telling you how they relate. Now the sequence distraction which is an distraction
over different abstracted types. We like to have lofts layers of things. A sequence abstraction
is common set of behaviors that exist for different types some built in some we create
on our own. And they tell us what sequence is. What is a sequence? It's a bunch of things
in in a row colors. I took the time to color them. To make more interesting. There's more
than 1 sequence type. There's more than 1 way to represent this list of colors. In Python.
The abstraction or the way in which we commonly represent a sequence of things, is a collection
of behaviors. There's really 2 important ones 1 sequence has a finite link. There's some
how many elements in the sequence? And element selection, that is a sequence has an element
corresponding to any non negative integer index less than its length.
Starting at 0 for the first element. The important result of this behavior condition is that
the elements in sequence are ordered. You can anyone of them by look at the index. There
are 7 things. And I want the element alt index 5 that's I need GOECHLT that's a sequence
2 behaviors bundled together and sequence abstraction which means things have length
and element selection method. Is a couple of properties shared among a bunch
of sequence types different abstract data types some of which ra are in Python and some
we do ourselves. We will do both today. Both will satisfy the sequence abstraction both
represent sequences of things.
Let's talk about tuples. Last time we saw they take 2 things and bundle them together
in a pair but in fact they can do more than that.
So indeed, we can bundle together let's say not only 1 and 2 as tuple but also 1, 2, 3,
4, 5. Or 1,s 2, 3, 4, 5, red, green, blue.
Okay so if we want to give the tuple a name so we can refer to over again. We can call
this a bunch of things. And because we know we can compute the length
and access individual elements via element selection there must be built in ways for
language to do that for it to be proper data type for sequence abstraction. The less than.
That tells us there are 8 things in the bunch and we can use the square bracket notation
in order to get the tell me at element 6 we know it's green because it's element 7. 1
less than the length and we know they are indexed from 0 to 1 less than the length and
there we get green. So that's 1 type of tell me selection we can
also achieve the same thing with the getitem function, which is allows us to get from the
bunch is element at index 6. Now, what else can we put inside a sequence?
Here we put numbers, strings on the same sequence. What else? Well, in the beginning anything
we can come up with: none, 12.2, or another sequence. What's going is I have a tuple with
3 elements and the element that index 2 is in fact itself a sequence. So a simpler version
might look like: just 12, followed by 3, 4. Okay so tuples can go within tuple as elements.
Then of course we can access them using either getitem function or the square bracket notation
which is an element selection operate BIELT in to Python.
These are values in our language. That means that in environment diagram we need a way
the represent them. Let's have a look.
Here we go. We have: 2 lines the name numbers is bound to this tuple and the pairs bound
to that tuple what happens when weﾊ oh and I would like the note if you watch carefully
the red arrow slides from where it is to next. Oh fancy.
So we got rid of highlighting with arrows instead because people said it was easier
to follow and make slide. So everything else in the environment diagram should be the same
as before. So now we bound numbers to this compound object which represent as tuple you
know it's a tuple because it says so. You can see the indexing happens at the top in
small numbers and then we have 2 box glued together as 1 object. So we can treat it as
whole via nameﾊ"numbers" or we can access its parts.
Then what happens when we have tuples within tuples? Basically, a tuple a pair of boxes
or any number of box depending on how throng tuple is. And each value within is easier
simple in stripping in which case we put it in there or it's more complex like tuple or
function or whatnot and there we draw an Arto that value. That original nates at the original
position. We have a tuple that contains to element and (On screen).
At index 0 and 1. Questions about this diagram? When you draw the diagrams by executing longer
programs the various box get sprayed all over the place on the right and you don't need
to know exactly where they are but what's important is where the arrows point. That
says this element is containing in tuple. As opposed to to the other way around so direction
of the arrow matters.
Okay. That's what our environment diagram looks like I think all I said all there was
to say about that. Do you have questions?
Question is: how many tuples can you put inside a tuple? There could be no end.
STUDENT: End tuple. JOHN DENERO: Let's see how we group tuples
together. Well we know there's a final ever finite length for sequence there's some limit
but no particular finite maximum length just depends on the memory of your computer. Since
it's the case we can put a tuple inside another it has a property called closure property
of data type. Which is true of sequences in general in Python we can combine data values
and if we do in way that satisfy it is closure property the result of combination. The tuple
you create with a tuple literal, can itself be combined using the same method. We can
put a tuple inside of a tuple. The closure property is key. What's what does
it do. It means that we can combine data values in a way that isn't just a sequence but builds
hierarchal structures. Which means that we can contain a value within
a value within a value within a value effectively to no limit. Building kind of arbitrary structures
as we go. And 1ﾊday I'm going to stand up here and
tell you something quite profound. But today I'm tell it to you now. And then
I'll tell you later because profound things are worth telling more than once that is programs
themselves are just hierarchal structures like these.
Hierarchal sequences. Okay. So hierarchal structures are important
because they represents programs but also everything else. They are made of parts which
themselves are made of parts and so on that's how we build.
Nothing is really stopping us from for instance saying that we call this hierarchy is a tuple
of numbers, pairs, and so manyﾊ well maybe that's not it.
At which point we would create numbers we would have created our pairs and then we create
our hierarchy which contains not only our numbers, but also our pairs.
1ﾊday we plight clean it up but here's what you get for now.
Yeah so it can be confusing to follow the arrows that's why they turn red with mouseover
them so you can tell where you are going. Okay. So hierarchal data in general is very
powerful way of collecting different data types together value types but theres a particular
case that we will focus on the recursive list. And that is a way of creating a sequence so
we have the built in tuple data type which allows us to create sequences figure the length
select their elements. But we want to a way the build such a thing ourselves we can't
always rely on built in features in language to do what we want. So the recursive list
doesn't rely on built in features of the language but it's is going to be a abstract data type
we define via constructor and selector functions so it has an constructor fudges here's what
it does. A recursive list is something that we form from its first element, which can
be anything, and then the rest of the list. Then we have 2 selectors first returns the
first element. Recursive list S. I use S because it evokes sequence throughout. So the first
element. Recursive list or we get the rest of the elements of recursive list and. And
there's a particular behavior condition that binds them together in order to make abstract
data type. And that behavior condition I will list as 2 parts, if a recursive list S is
constructed from some first element F and some recursive list R, as its rest. Then first
S gives back the first element F. And rest will give us back R a recursive list
that represents the rest of the list. So we think about a long list of things and
then the rest which is itself a slightly smaller list of in the beginnings. And we can say
the abstract data type has a selector and constructor with different piece where they
are they are Juries 2ﾊpieces the first element and the rest of the list.
Okay the nice thing about recursive list we implement them via pairs and we talked about
pairs last time as something we can use a built in tuple in language it was possibility
to implement a pair with higher order functions alone. So now we can say we build sequences
based on pairs and pairs on higher order functions so we can build anything with functions alone.
But first let's talk about how we build this with 2 element tuples with pairs. What would
it look like to represent the whole sequence 1, 2, 3, 4 which has length. 2 using pairs
alone. Break it up into first element and then the rest. So in an environment diagram
what we would build is a tuple. Recursive list is a pair of things and first element
of that pair is going to be the first element of the whole list.
So 1 is the first element of pair and first element of the whole list what about the rest
of list it has the same structure. So it is the second element of the pair that represents
the recursive list and in itself is a recursive list so if I list consist of anything the
element and then a recursive list when does it end. With none a value NN that represents
the empty list that allows us to complete the implementation of abstract the data type
forever recursive list by saying there's some empty list and then making.
Question is: how do we add elements in the middle it's a great question but we are going
to write code instead. We want to make sure we can develop the sequence
abstraction making old lists. The sequence abstraction tells us we need to compute the
length and get particular tells me out of it and after that we can insert elements.
Let's do some work finally. So we take in a first element and then the
rest of the list that's how we build rlist a recursive list we bundle to go using 2 element
tuple the first and the rest. We need some way for it to end we also need
to define the empty recursive list is none. Then we need our selectors we want the first
thing of rlist S is to return the element at index 0.
And if we want the rest of the list well that's the element at index Y.
We've used only 2 element tuples in order to implement this general form of a recursive
list. How do I build things? I can say stuff like counts is an rlist that consists as 1
as the first element. The rest starts with 2 and followed by rlist which is 3 followed
by rlist starts with 4. So let's say we are trying to build 1, 2, 34 nothing after 4.
The second element after 4 is empty_rlist. So now I've used my abstract data type my
constructors my selectors and a special value I introduced in order to create counts and
what else can I do. I can create alts. All right.
What have I done created counts which looks like this it's a tuple within a tuple within
a tuple but with a particular structure with the first element of what's left over is always
the element of some rlist so there's 1 right here and that's a rest of this rlist which
is 1 length and longer alts looks like that that's 1 and 2 and 12, so in a sequence you
can repeated things but it has to be finite length.
What else can I create? Well both together by saying that there's a relationship list
whose first element is alt and then after that we have counts, and after that we have
3.
And we are done okay so what's both of the there is both if you want to know the representation.
But what we know is that it's a rlist that starts with alt and is has counts and then
3 in it. Here's a question to talk about with the person
next to you. If I wanted to write an expression that only contained the following 3 functions,
3 names I have both, first, and rest.
How do I write a compound call expression that evaluates to the number 3?
Evaluates. So you don't need paper, you can think it's
1 of these 4. Take a look at those and discuss if I had both, which is a rlist that contains
rlists within it how do I get the number 3 which by the way, is in there somewhere? Try
figure it out all we are allowed to using is first list and both. What have I done I
said I want the first of the rest of the rest of the rest of both. Okay let's think about
what both is. Here it's too complicated so we should think of both as 3 elements: alts,
counts and 3. We know the number 3 which is what we want
at the end of the day is in counts. It was the element at index 2 of counts. How do we
get that? Let's think about it. First we start with both. And then next we want is ignore
the first element which has a bunch of ones and 2, and instead get the rest of the list.
So there's the rest of the list we created. It's an rlist whose first element is counts
and the rest of the list is 3. Now of course we could get in 3 by saying: rest first. How?
I will start with both. And then the first thing I do is take the rest of both. That
will give me this.
And then I can also take the rest of both and that would give me just this recursive
list which starts with the element 3 and then ends with the empty list.
And then I could take the first of that. That would give 3. But since I was sly I didn't
give you that as option. There's another way to get this 3. How? Let's
think about it. We start with both get the rest of both. That's this guy.
Now we want the first thing in there, which is the counts recursive list.
Let's see how we are doing. Oh now we have something that has 3 in it. How. We want the
rest of that, that's the thing that starts with 2 and followed by other stuff. We want
the rest of that. That's the thing that starts with 3 and followed
by a recursive list that starts with 4. That has a first element of 3. First rest rest
first rest the. . .the answer was D.
Go D! Multiple choice I usually make the answer D. That's my thing.
Question?
(INAUDIBLE). We'll talk after good question.
Okay questions about how that works? We can build recurs I list in this way now implement
the sequence abstraction. We created this way we think in codes list of things of arbitrary
length but finite length using pairs alone. But we are still missing the actual behavior
conditions that are required for implementing the sequence abstraction. We have to write
2 functions and remember away they do. 1 is supposed to compute the length of the sequence.
We are writing a function that computes the function of a recursive list and 1 selects
particular elements out of the list which we did by hands just now but we want a function
that does that for us. To write 1. . .
Okay. So here's where we were this is the code we wrote today the rlist constructor
2 select ors empty rlist with examples. Now we will define a new function calledﾊ"LEN
rlist. It works by starting saying the length is 0 then creates a while statement. The while
statement isn't going to necessarily keep track of statements like the ones in the past.
But instead it's going to walk down the list grabbing the rest each time until we run out
of list to enumerate. Then we get at the end and we've reached the length. What does that
look like? We are keeping going until it's the case that S is empty.
As long as we have a list with stuff in it, we are going to change what S the name is
bound to and change the length. How? Well S is bound now to the rest of the list.
And length is going to be bound to whatever the length was before plus 1 then we return
the length. The idea here is that a recursive list is always 1 longer than the rest of the
list. And the length of an empty list is 0.
Now what about getting a particular tell me out of a recursive list.
Well, we want to be able to do the following: Change what S is bound to until it's bound
to the thing where the first element is what we want then return the first element.
What getitem is supposed to do isﾊ huh.
Return the element at index I of recursive list S.
And we do that by saying while I is greater than 0, I am change both S, i, is is, S is
the rest of the list and I is 1 less than before. The property we are enforcing here
the element at index I of a list is the element at index I minus 1 of the rest of the list.
And then once we get down to just I = 0. That means we want the element at index 0 at whatever
list we are considering at this point we can return that how do we get element 0. That's
the first element of the list. Now we have an implementation that allows recursive lists
to satisfy the sequence abstraction. And we can get the length and the particular
tells me from them. Let's test it make sure it works.
We still have counts and we might want to be interested in the length counts is 4.
What about getitem rlist countsﾊ let's get the tell me at index. That would be 3. That
was the 1 we did work with first and rest and first and rest in order to get before.
So if I created both which was rlist of Ales followed by rlist of counts followed by empty
rlist. It's a shorter verse. Now I want the 3. How? Perhaps getitem rlist of both. At
index 1. That's my counts rlist. Then I can get the tell me at index 2 of that. And I
hear write down another expression which give me the 3 I wanted before. Now using the sequence
abstraction function getitem.
Questions? Let's just for clarity let's look Ott getitem
and how it's working. It's easier to understand if you see it go.
Skip that guy.
Okay so I defined first and rest and I've done getitem rlist then done something that
should cause you to light my correct on fire. I will define recurs live list according to
implementation. Why. What am I supposed to be write here? Counts (On screen)before.
That's using the abstract data type that we developed here. I am cheating with the implementation
it simplify it is environment diagram so much that it will save you all just exceeding amounts
of headaches for me to do it this way. So whatever rule I give you about always make
sure you use abstract data type, et cetera, et cetera. There are conditions under which
it's a good idea to avoid that rule. STUDENT: For finding the length after recursive
list if first element is tuple of multiple elements is that length considered just 1
or do you still add the length to overall. JOHN DENERO: What's going on with lists inside
of lists what does testimony to have the length of lists that have others. The length is in
general how many elements it has. That doesn't pay attention to what kind of element is in
there. Even if I have other sequences within that sequence as elements, those don't add
to the length anymore than if they were numbers. Which means for instance of for instance if
we want to compute the length of both here. Where both contains 1 element there, and is
second 1 there. Those happen to be sequences themselves. But the idea of what the length
operate means is to say how many things are in both regardless of what they are. That
gives us 2. Okay.
So what have I cone created counts using a shortcut. In order to get a nice layout otherwise
I would do a lot of frames that are confusing it's a recurs live list with elements 1, 2,
3, 4. And then we get getitem rlist on counts of the index 1, now if we think about this
as abstract sequence, where this is the element at index 0 and this is at index 1 then we
should be returning to at the end of this computation.
Let's see what happens.
When we call getitem rlist we bind to name S, which is the formal parameter of the function,
to the argument we passed in which is whatever value is bound to counts. Which is this spire
recursive list. We look up counts and we passed that in as the argument to getitem_rlist.
And I we passed as second argument, that's 1.
So now what happens?
It's hard to get everything on the screen at the same time. So let's look at pictures
first. And let's memorize the code first. So getitem rlist does the following: while
I is still greater than 0 we bind S to the regulation of S and decrease I by 1. We will
do that over and over. And until I is 0 and then we return the first
thing in the list. Let's see how that works.
So we call rest in order to get the rest of the list. Rest's formal parameter is bound
to the. What returns that is the recurs live list
2, 3, 4 Ks that's the return value that we bound to. Now S which was the entire list
is now just the rest of the list. And since I is now 0, we return the first
element in that list. So we now call first on what S is now in order to get the 2 out.
That's the return value of first which is the return value of all of get_rlist.
Questions? STUDENT: What happens if you type getitem
that's longer. JOHN DENERO: What happens if you call getitem
on something that's longer than the list we haven't added an error checking yet. So what's
happening is eventually we end up with rlist that's empty. Which in implementation is none
value we try to get the first of retained earnings of that. And that's not going to
work. Because you can't take the rest of none, there's no such thing we get error that says
cannot subscript. STUDENT: What advantage does rlist have.
JOHN DENERO: Why would we use rlist rather than built in lists or tuples and they don't
have the recursive structure. The nice thing about this you can in fact share sub smarts
among other parts of function. I didn't have to create anything new when referring to the
rest of the list I just refer directly. But if you want to refer to other parts of structure
like a tuple you kind of have to create a new tuple to describe.
Question is: is none always empty is that the question.
Is none always the thing at the end. Yeah so we define the rlist they always end in
none. This is an old tradition much old than am I to have none value that represents the
empty recursive list sew you shouldn't expect that to change a lot.
Okay so we have our length function and getitem function. The demo is done. Questions are
answered. We looked at the environment diagram. Oh there
it is on the screen at the same time. So now we can finally see what's going on the critical
part was when we had S originally bound here. To the entire recursive list and then in this
line of the code, where we said I have 2 names S I and rebinding to the rest of the list
in I 1. That's how we got rebound now at 0 and rebound S not to the whole list but just
to the rest of the list and simultaneously so we are tracking together at the same time
what's going on with the recursive list we are considering. And how many times have I
BROPD the first element to just consider the rest of the list. As long as we do those together
we end up with the right answer at the end of the day.
STUDENT: Do we always have to assign the last tell me to the list to none or does Python
do that automatically. JOHN DENERO: Does none show up automatically
or do we explicitly create. The latter. We define the abstract data type that called
the empty rlist none and built this thing up piece by piece. By building recursive lists.
Now that you've seen how this works in way that's interpretable I will go back and fix
the mess I've done. Here's a way to use the abstract data type
as we defined it. And grabbing these definitionses, you will now see 1 of the reasons why I took
a shortcut. Is that there are actually many function calls
involved in creating this recursive list. What are they? Every time we are building
a longer list out of shorter list this is the rest in element that involves introducing
a new frame in environment diagram. So in order to build here's a big call expression.
In order to evaluate I have to evaluate the operand, et cetera, et cetera. This is the
first operand I evaluate that evaluates to none. And here's a function call where first
is bound to 4 the rest to none that creates the tuple as return value which is passed
in argument to another call the to rlist which creates the next next next piece. So in order
to build up you get the same structure as before, before!
After. It's laid out different because woed to introduce a bunch of frames and build it
piece by piece. So the procedure for getting the element at index 1 is the same we get
the rest of list there and return it as the return value but it goes for a while. So excuse
me for taking the shortcut this is the proper way to use your list abstract data type.
Okay. That box that says not on midterm 1. Because everything for the rest of the lecture
all 6ﾊminutes is stuff you need to know eventually but if you don't want to know it
right now. I won't blame you. The reason I say you don't know you don't need to know
right now in order to fully understand what I'm showing you takes more time and more lectures.
So Python works in a particular way of sequence iterationﾊ I will show youﾊ what am I
doing. You are all ready to leave. You will care eventually you might as well
learn now. Another operations we can use based on our sequence abstraction is that we can
count the number of times a particular element shows up in a sequence. I'm using a while
statement in order to do that. I start with some sequence S, and I'm looking for some
value and return the number of times that value shows up in the sequence S. How I do
that I do with while statement that looks like others that we've written by writing
down the total number of times I've seen value. And then what index I'm on right now.
And 1 way to write this is to say: While index is less than LEN (S) then what
do I want to do? I want to see what happens if I get the tell
me at of S at index. And if it happens to be the same as value, then I'm increment my
total. And I'm always going to increment my index
and at the end I will return the total number of times I saw this thing.
What can I do now? I can create use the built in Type A is 12, 1, 2, 1 and how many times
that I see within A the value 1. Depends on whether I defined getitem yet.
So that's from operate import getitem. Oh forget that guy.
Bloop.
And we get it 3 times. How can I use this same function with my other sequence abstraction?
If I use higher order functions to define exactly LEN and getitem. Of course I can do
like this. LEN is usually built in length type but if I want to substitute the particular
length for sequences then I'll do that.
And likewise what isﾊ"getitem". Well by default let's call it the built in getitem
we import from operator. I have A which looks like that I have also
that look like that. And if I want to use while loop I can in order to get the number
of times A shows up in (On screen)in order to do that I need to make sure I pass in the
2 functions that implement the sequence abstraction for our recursive sequence and those were
called LEN rlist and getitem_rlist. We see it shows up 3 times in here. 1, 1, 1. And
3 times in here. 1, 1, 1. But it turns out there's a an easier way to do this. If you
use it 1 of the built in sequence types in Python there's a new kind of statement calledﾊ"for"
statement. I suspect you have seen this in other languages. You say for and bind elem
to each value in the sequence. Each element in the sequence elem can be arbitrary name
but the special wordﾊ"in" then I get the sequence I want to consider each element in
turn for. And I can just talk about that element between body of the for statement. So I can
say if element equals value total equals total+ 1 then I return total.
So here's a different implementation that computes the number of times that an element
shows up in a sequence. And count the number A and we get back 3. Here we are. And we have
talked about for statements but you don't need to know it for exam.
STUDENT: (INAUDIBLE).
JOHN DENERO: Question is does my account while function just call too many functions to be
efficient, and yes it does but it does what it's supposed to do. All right have a good
weekend.
4