Lab 6: Nonlocal and Object-Oriented Programming
Due at 11:59pm on 03/04/2016.
Starter Files
Download lab06.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.
Submission
By the end of this lab, you should have submitted the lab with
python3 ok --submit
. You may submit more than once before the
deadline; only the final submission will be graded.
- To receive credit for this lab, you must complete Questions 1, 2, and 3, and submit through OK.
- Question 3 can be found in
data.py
, and Questions 4-8 and 10 inclasses.py
. - The adventure game (Questions 4-8) is for extra practice (and fun!).
- Question 9 and 10 are also for extra practice.
Nonlocal
Before we get to object-oriented programming, let's do a quick introduction on how to use the nonlocal
keyword. Consider the following function:
def make_counter():
"""Makes a counter function.
>>> counter = make_counter()
>>> counter()
1
>>> counter()
2
"""
count = 0
def counter():
count = count + 1
return count
return counter
Running this function's doctests, we find that it causes the following error:
UnboundLocalError: local variable 'count' referenced before assignment
Why does this happen? When we execute an assignment statement, remember that we are either creating a new binding in our current frame or we are updating an old one in the current frame. For example, the line count = ...
in counter
, is creating the local variable count
inside counter
's frame. This assignment statement tells Python to expect a variable called count inside counter
's frame, so Python will not look in parent frames for this variable. However, notice that we tried to compute count + 1
before the local variable was created! That's why we get the UnboundLocalError
.
To avoid this problem, we introduce the nonlocal
keyword. It allows
us to update a variable in a parent frame! Note we cannot use nonlocal
to modify variables in the global frame. Consider this improved example:
def make_counter():
"""Makes a counter function.
>>> counter = make_counter()
>>> counter()
1
>>> counter()
2
"""
count = 0
def counter():
nonlocal count
count = count + 1
return count
return counter
The line nonlocal count
tells Python that count
will not be local to this frame, so it will look for it in parent frames. Now we can update count
without running into problems.
Question 1: Vending Machine
Implement the function vending_machine
, which takes
in a sequence of snacks (as strings) and returns a zero-argument
function. This zero-argument function will cycle through the
list of snacks, returning one element from the list in order.
def vending_machine(snacks):
"""Cycles through list of snacks.
>>> vender = vending_machine(['chips', 'chocolate', 'popcorn'])
>>> vender()
'chips'
>>> vender()
'chocolate'
>>> vender()
'popcorn'
>>> vender()
'chips'
>>> other = vending_machine(['brownie'])
>>> other()
'brownie'
>>> vender()
'chocolate'
"""
"*** YOUR CODE HERE ***"
index = 0
def vender():
nonlocal index
result = seq[index]
index = (index + 1) % len(snacks)
return result
return vending_machine
Use OK to test your code:
python3 ok -q vending_machine
What is OOP?
Now, let's dive into object-oriented programming (OOP), a model of programming that allows you to think of data in terms of "objects" with their own characteristics and actions, just like objects in real life! This is incredibly powerful and allows you to create an object that is specific to your program — you can read up on all the details here. For now, we'll guide you through it as you build your very own text-based adventure game!
Prologue
It's the day of the CS 61A silly hat lecture, and Professor Hilfinger needs to get from San Francisco to Berkeley without messing up his silly hat. He'd take the BART, but his silly hat is too tall! It'd be great if he had a car. A monster truck would be best, but a car will do.
In car.py
, you'll find a class called Car
. A class is a blueprint for
creating objects of that type. In this case, the Car
class statement tells us
how to create Car
objects.
So let's build Professor Hilfinger a car! Don't worry, you won't need to do
any physical work — the constructor will do it for you. The constructor
of a class is a function that creates an instance, or one single
occurence, of the object outlined by the class. In Python, the constructor
method is named __init__
. Note that there must be two underscores on each
side of init
. The Car
class' constructor looks like this:
def __init__(self, make, model):
self.make = make
self.model = model
self.color = 'No color yet. You need to paint me.'
self.wheels = Car.num_wheels
self.gas = Car.gas
The __init__
method for Car
has three parameters. The first one, self
,
is automatically bound to the newly created Car
object. The second and
third parameters, make
and model
, are bound to the arguments passed to the
constructor, meaning when we make a Car
object, we must provide two arguments.
Don't worry about the code inside of the constructor for now.
Let's make our car. Professor Hilfinger would like to drive a Tesla Model S to lecture. We can construct an instance of Car
with 'Tesla'
as the make
and 'Model S'
as the model
.
Rather than calling __init__
explicitly, Python allows us to make an
instance of a class by using the name of the class.
>>> hilfingers_car = Car('Tesla', 'Model S')
Here, 'Tesla'
is passed in as the make
, and 'Model S' as the model
. Note
that we don't pass in an argument for self
, since its value is always the
object being created. An object is an instance of a class. In this case,
hilfingers_car
is now bound to a Car
object or, in other words, an instance
of the Car
class.
So how are the make
and model
of Professor Hilfinger's car actually
stored? Let's talk about attributes of instances and classes. Here's a
snippet of the code in car.py
of the instance and class attributes in the Car
class:
class Car(object):
num_wheels = 4
gas = 30
headlights = 2
size = 'Tiny'
def __init__(self, make, model):
self.make = make
self.model = model
self.color = 'No color yet. You need to paint me.'
self.wheels = Car.num_wheels
self.gas = Car.gas
def paint(self, color):
self.color = color
return self.make + ' ' + self.model + ' is now ' + color
In the first two lines of the constructor, the name self.make
is bound to
the first argument passed to the constructor and self.model
is bound to the
second. These are two examples of instance attributes. An instance attribute
is a quality that is specific to an instance, and thus can only be accessed
using dot notation (separating the instance and attribute with a period) on
an instance. In this case, self
is bound to our instance, so self.model
references our instance's model.
Our car has other instance attributes too, like color
and wheels
. As
instance attributes, the make, model, and color of hilfingers_car
do not
affect the make, model, and color of other cars.
On the other hand, a class attribute is a quality that is shared among all
instances of the class. For example, the Car
class has four class
attributes defined at the beginning of a class: num_wheels = 4
, gas = 30
,
headlights = 2
and size = 'Tiny'
. The first says that all cars have 4
wheels. Class attributes can also be accessed using dot notation, both on an
instance and on the class name itself.
Use OK to test your understanding as you read the text. You can always load another terminal window and type
python3 -i car.py
if you are stuck!python3 ok -q prologue -u
In the following line, we access hilfingers_car
's color
attribute:
>>> hilfingers_car.color
______'No color yet. You need to paint me.'
Looks like we need to paint hilfingers_car
!
Let's use the paint
method defined above. Methods are functions that are specific to a
class; only an instance of the class can use them. We've already seen one
method: __init__
! Think of methods as actions or abilities of objects. You
can think of the paint
method as the car painting itself. How do we call
methods on an instance? You guessed it, dot notation!
>>> hilfingers_car.paint('black')
______'Tesla Model S is now black'
>>> hilfingers_car.color
______'black'
Awesome! But if you take a look at the paint
method, it takes two parameters.
So why don't we need to pass two arguments? Just like we've seen with __init__
,
all methods of a class have a self
parameter to which Python automatically binds the
instance that is calling that method. Here, hilfingers_car
is bound to self
so that the body of paint
can access its attributes!
Professor Hilfinger's black Tesla is pretty cool, but there's not quite enough
room for his silly hat (look at the class attribute size
, it's 'Tiny'
!).
How about we create a monster truck for him instead? In car.py
, we've
defined a MonsterTruck
class. Let's look at the code for MonsterTruck
:
class MonsterTruck(Car):
size = 'Monster'
def rev(self):
print('Vroom! This Monster Truck is huge!')
def drive(self):
self.rev()
return Car.drive(self)
Wow! The truck may be big, but the source code is tiny! Let's make sure that the truck still does what we expect it to do. Let's create a new instance of Professor Hilfingers's monster truck:
>>> hilfingers_truck = MonsterTruck('Monster Truck', 'XXL')
Does it behave as you would expect a Car
to? Can you still paint it?
Is it even drivable?
Well, the class MonsterTruck
is defined as class MonsterTruck(Car):
,
meaning its superclass is Car
. Likewise, the class MonsterTruck
is a *
subclass* of the Car
class. That means the MonsterTruck
class inherits
all the attributes and methods that were defined in Car
, including its constructor!
Inheritance makes setting up a hierarchy of classes easier because the amount of code you need to write to define a new class of objects is reduced. You only need to add (or override) new attributes or methods that you want to be unique from those in the superclass.
>>> hilfingers_car.size
______'Tiny'
>>> hilfingers_truck.size
______'Monster'
Wow, what a difference in size! This is because the class attribute size
of
MonsterTruck
overrides the size
class attribute of Car
, so all
MonsterTruck
instances are 'Monster'
-sized.
In addition, the drive
method in MonsterTruck
overrides the one in Car
.
To show off all MonsterTruck
instances, we defined a rev
method specific to
MonsterClass
. Regular Car
s cannot rev
! Everything else — the
constructor __init__
, paint
, num_wheels
, gas
— are inherited from Car
.
Question 2: WWPP: Using the Car class
Make sure to have read and completed the Prologue before moving on.
python3 ok -q prologue -u
Use OK to test your knowledge with the following What would Python print questions. Each code block is a seperate question.
python3 ok -q car -u
Hint: Check
car.py
if you are stuck. If an error occurs, writeError
.
>>> hilfingers_car = Car('Tesla', 'Model S')
>>> hilfingers_car.model
______'Tesla'
>>> hilfingers_car.gas = 10
>>> hilfingers_car.drive()
______'Tesla Model S goes vroom!'
>>> hilfingers_car.drive()
______'Tesla Model S cannot drive!'
>>> hilfingers_car.fill_gas()
______Your car is full.
>>> hilfingers_car.gas
______30
>>> Car.headlights
______2
>>> hilfingers_car.headlights
______2
>>> Car.headlights = 3
>>> hilfingers_car.headlights
______3
>>> hilfingers_car.headlights = 2
>>> Car.headlights
______3
>>> hilfingers_car.wheels = 2
>>> hilfingers_car.wheels
______2
>>> Car.num_wheels
______4
>>> hilfingers_car.drive()
______'Tesla Model S cannot drive!'
>>> Car.drive()
______Error (TypeError)
>>> Car.drive(hilfingers_car)
______'Tesla Model S cannot drive!'
>>> MonsterTruck.drive(hilfingers_car)
______Error (AttributeError)
>>> sumukhs_car = MonsterTruck('Monster', 'Batmobile')
>>> sumukhs_car.drive()
______Vroom! This Monster Truck is huge!
'Monster Batmobile goes vroom!'
>>> Car.drive(sumukhs_car)
______'Monster Batmobile goes vroom!'
>>> MonsterTruck.drive(sumukhs_car)
______Vroom! This Monster Truck is huge!
'Monster Batmobile goes vroom!'
>>> Car.rev(sumukhs_car)
______Error (AttributeError)
Variables
Wait! Before you go on your adventure, you must take this handy chart with you... Now that you've learned OOP, this chart notes the three types of variables you should be aware of.
Class Attributes | Instance Attributes | Local Variables | |
---|---|---|---|
Trait | A class attribute is a variable specific to the class and is accessed using dot notation on the class name or on an instance. All instances of a class share the same class attributes. | An instance attribute is a variable that is specific to each instance of a class and is only accessible by using dot notation on a particular instance. Instance attributes of one instance have no effect on another's. | A local variable is a variable you see inside functions or methods. The scope resides in the block it is defined in. |
Example |
|
|
|
Explanation |
num_wheels is a class attribute of the
Car class. On the other hand, wheels
is an instance attribute that is initialized to be the value of
num_wheels when the instance was constructed.
|
We construct two Car instances. Each has its own
self.make and self.model instance
attributes. Changing the model of car1
does not affect the model of car2 .
|
In the first line of code, x is a global variable,
not a local variable. The three local variables
are self , x , and i ; they
are local to some_method and can only be accessed
inside of a frame of a call to some_method .
|
Note: The format to access class attributes is <class name>.<class
attribute>
, such as Car.num_wheels
, or <instance>.<class attribute>
, such
as car1.num_wheels
.
Adventure Game!
The rest of the lab is implementing a text adventure game. These questions, except for Question 3, are not required for submission, but are a great way to learn OOP (and have fun!). To start the game, type
python3 adventure.py
The ZIP archive provided at the start of lab contains all the starter code. All
of your changes will be made to classes.py
, although you have to create
yourself as a player in data.py
before implementing anything else.
classes.py
: Implementation for classes used in the gamedata.py
: All of the objects used in the gameadventure.py
: Interpreter of the game
Question 3: Who am I?
It is time for you to enter a world of adventure! First, you need to create
yourself as a Player
object in data.py
. Take a look at the Player
class in
classes.py
and create a Player
object at the bottom of data.py
.
The Player
constructor takes two arguments:
name
should be your preferred name (as a string)- the starting
place
Your Player
should start at sather_gate
.
# Player:
# The Player should start at sather_gate.
me = None
me = Player('Your Name', sather_gate)
Use OK to test your code:
python3 ok -q me
Question 4: Where do I go?
Once you've created your player, you can start the adventure game:
python3 adventure.py
You will see the following output:
Welcome to the adventure game!
It's a bright sunny day.
You are a cute little squirrel named [your name],
wandering around Berkeley campus looking for food.
Let's go to FSM (Free Speech Movement Cafe)
and see what we can find there!
There are 7 possible commands:
talk to [character]
unlock [place]
help
take [thing]
go to [place]
look
check backpack
adventure>
First, we need to be able to go to places. If you try the go to
command, you'll
notice it doesn't do anything.
In classes.py
, implement the go_to
method in the Player
class. go_to
takes in a location
that you want to go to and changes the player's
instance attribute place
to point to the new place. At the end of the method
you should also print some text saying you are at the name of the place. Note the
place's description may not always include the name of the place.
Hint: The
get_neighbor
method inPlace
will return the correspondingPlace
object iflocation
is among your available exits. Otherwise,get_neighbor
will return the currentPlace
and will print "Can't go to [destination place] from [starting place]. Take a look at the doctest for more details.
def go_to(self, location):
"""Go to a location if it's among the exits of player's current place.
>>> sather_gate = Place('Sather Gate', 'You are at Sather Gate', [], [])
>>> gbc = Place('GBC', 'You are at Golden Bear Cafe', [], [])
>>> sather_gate.add_exits([gbc])
>>> sather_gate.locked = True
>>> gbc.add_exits([sather_gate])
>>> me = Player('player', sather_gate)
>>> me.go_to('GBC')
You are at GBC
>>> me.place is gbc
True
>>> me.place.name
'GBC'
>>> me.go_to('GBC')
Can't go to GBC from GBC.
Try looking around to see where to go.
You are at GBC
>>> me.go_to('Sather Gate')
Sather Gate is locked! Go look for a key to unlock it
You are at GBC
"""
destination_place = self.place.get_neighbor(location)
if destination_place.locked:
print(destination_place.name, 'is locked! Go look for a key to unlock it')
"*** YOUR CODE HERE ***"
else:
self.place = destination_place
print('You are at', self.place.name)
Use OK to test your code:
python3 ok -q Player.go_to
Question 5: How do I talk?
Now you can go wherever you want! Try going to Wheeler Hall. There, you'll find
Derrick. Try talking to him with the talk to
command. This also doesn't work
:(
Next, implement the talk_to
method in Player
. talk_to
takes in the name of
a Character
object, and prints out the Character
's response. Take a look at
the doctest for more details.
Hint:
talk_to
takes in an argumentperson
, which is a string. Thecharacters
instance attribute inself.place
is a dictionary mappingCharacter
names (strings) toCharacter
objects.Once you've got the
Character
object, what method in theCharacter
class will make them talk?
def talk_to(self, person):
"""Talk to person if person is at player's current place.
>>> john = Character('John', 'Have to run for lecture!')
>>> sather_gate = Place('Sather Gate', 'You are at Sather Gate', [john], [])
>>> me = Player('player', sather_gate)
>>> me.talk_to(john)
Person has to be a string.
>>> me.talk_to('John')
John says: Have to run for lecture!
>>> me.talk_to('Albert')
Albert is not here.
"""
if type(person) != str:
print('Person has to be a string.')
"*** YOUR CODE HERE ***"
elif person not in self.place.characters:
print(person, 'is not here.')
else:
print(person,'says:', self.place.characters[person].talk())
Use OK to test your code:
python3 ok -q Player.talk_to
Question 6: How do I take items?
Now you can talk to people in adventure world! To make it even better, let's
implement the take
method in the Player
class so you can put things in your
backpack
. Currently, you don't have a backpack, so let's create an instance
variable backpack
and initialize it to an empty list.
After you've initialized your empty backpack
, implement take
, which takes in
a name of an object as a name, checks if the Place
you are at contains the
Thing
object corresponding to the input name, and then puts it into your
backpack
. Take a look at the doctests for more details.
Hint: the
things
instance attribute in thePlace
class is a dictionary that mapsThing
names (strings) toThing
objects.The
take
method in thePlace
class will also come in handy.
def take(self, thing):
"""Take a thing if thing is at player's current place
>>> hotdog = Thing('Hotdog', 'A hot looking hotdog')
>>> gbc = Place('GBC', 'You are at Golden Bear Cafe', [], [hotdog])
>>> me = Player('Player', gbc)
>>> me.backpack
[]
>>> me.take(hotdog)
Thing should be a string.
>>> me.take('dog')
dog is not here.
>>> me.take('Hotdog')
Player takes the Hotdog
>>> me.take('Hotdog')
Hotdog is not here.
>>> isinstance(me.backpack[0], Thing)
True
>>> len(me.backpack)
1
"""
if type(thing) != str:
print('Thing should be a string.')
"*** YOUR CODE HERE ***"
elif thing not in self.place.things:
print(thing, 'is not here.')
else:
taken = self.place.take(thing)
print(self.name, 'takes the', taken.name)
self.backpack.append(taken)
Use OK to test your code:
python3 ok -q Player.take
Question 7: No door can hold us back!
FSM is locked! There's no way for us to get in, and you're getting pretty desperate for that sweet, delicious, caffeinated nectar of the gods.
We'll need to do two things in order to get into FSM and get our caffeine fix.
Firstly, define a new class Key
, that is a subclass of Thing
, but
overwrites the use
method to unlock the door to FSM.
Hint 1: Refer back to the
MonsterTruck
example if you need a refresher on how to define a subclass and overwrite methods. Make sure you define Key after you've defined Thing.Hint 2: Place has a
locked
instance attribute that you may need to change.
class Thing(object):
def __init__(self, name, description):
self.name = name
self.description = description
def use(self, place):
print("You can't use a {0} here".format(self.name))
""" Implement Key here! """
class Key(Thing):
def use(self, place):
if place.locked:
place.locked = False
print(place.name, 'is now unlocked!')
else:
print(place.name, 'is already unlocked!')
You'll also need to finish the implementation of unlock
in
Player
. It takes a string place
that you want to unlock, and if
you have a key, call the key's use
method to unlock the place. If
you have no key, then the method should print that the place can't be
unlocked without a key.
You'll need to implement both Key
and unlock
for the doctests to pass.
def unlock(self, place):
"""If player has a key, unlock a locked neighboring place.
>>> key = Key('SkeletonKey', 'A Key to unlock all doors.')
>>> gbc = Place('GBC', 'You are at Golden Bear Cafe', [], [key])
>>> fsm = Place('FSM', 'Home of the nectar of the gods', [], [])
>>> gbc.add_exits([fsm])
>>> fsm.locked = True
>>> me = Player('Player', gbc)
>>> me.unlock(fsm)
Place must be a string
>>> me.go_to('FSM')
FSM is locked! Go look for a key to unlock it
You are at GBC
>>> me.unlock(fsm)
Place must be a string
>>> me.unlock('FSM')
FSM can't be unlocked without a key!
>>> me.take('SkeletonKey')
Player takes the SkeletonKey
>>> me.unlock('FSM')
FSM is now unlocked!
>>> me.unlock('FSM')
FSM is already unlocked!
>>> me.go_to('FSM')
You are at FSM
"""
if type(place) != str:
print("Place must be a string")
return
key = None
for item in self.backpack:
if type(item) == Key:
key = item
"*** YOUR CODE HERE ***"
if not key:
print(place, "can't be unlocked without a key!")
else:
place_to_unlock = self.place.get_neighbor(place)
key.use(place_to_unlock)
Use OK to test your code:
python3 ok -q Player.unlock
Question 8: Win the game!
Good job! Now you can explore around campus and try to win the game. Talk to the people at different places in order to get hints. Can you save the day and make it to the 61A project party in time?
Enjoy!
Extra Practice
Question 9: Count calls
When testing software, it can be useful to count the number of times
that a function is called. Define a higher-order function
count_calls
that returns two functions:
- A counted version of the input function
f
that counts the number of times it has been called, but otherwise behaves identically to the original function, and - A function of zero arguments that returns the number of times that the counted function has been called.
Your implementation should not include any lists or dictionaries.
Hint: Remember that you can use the
*args
keyword to define an arbitrary number of parameters for a function.
def count_calls(f):
"""A function that returns a version of f that counts calls to f and can
report that count to how_many_calls.
The returned function responds to a special string argument,
'how many calls?'
to return the number of calls.
>>> from operator import add
>>> counted_add, add_count = count_calls(add)
>>> add_count()
0
>>> counted_add(1, 2)
3
>>> add_count()
1
>>> add(3, 4) # Doesn't count
7
>>> add_count()
1
>>> counted_add(5, 6)
11
>>> add_count()
2
"""
"*** YOUR CODE HERE ***"
calls = 0
def counted(*args):
nonlocal calls
calls = calls + 1
return f(*args)
return counted, lambda: calls
Use OK to test your code:
python3 ok -q count_calls
Question 10: Knapsack
You've successfully completed your adventure, and as a reward Professor Hilfinger leads you to the first floor of Soda, unlocks a small wooden door, and offers you your choice of the treasures of Berkeley Computer Science. Shiny electronics, relics of a forgotten time, stacks of punch cards, Software Engineering books from 2009. Your small backpack can only carry so much, you should come up with a strategy to take the max possible value!
Each treasure is an instance of the class Treasure
, which has
instance attributes weight
and value
. Complete the definition of
the method knapsack
, which takes a max_weight
and a
list_of_treasures
, and returns the most valuable combination of
treasures that have a combined weight less than or equal to
max_weight
.
Hint: Tree recursion.
Hint Hint: Think about two cases for each treasure, either take it, or leave it.
def knapsack(self, max_weight, list_of_treasures):
"""Return the total value of the most valuable combination of treasures
which have a combined weight less than max_weight
>>> t1 = Treasure('Treasure 1', 'Software Engineering 2008', 5, 6)
>>> t2 = Treasure('Treasure 2', "Paul Hilfinger's First Computer", 10, 50)
>>> t3 = Treasure('Treasure 3', "John's Silly Hat", 6, 3)
>>> t4 = Treasure('Treasure 4', 'Whiteboard Marker', 4, 2)
>>> t5 = Treasure('Treasure 5', 'USB with a Linux Distro', 2, 4)
>>> treasure_list = [t1, t2, t3, t4, t5]
>>> soda = Place('Soda', 'Soda', [], [])
>>> me = Player('Player', soda)
>>> me.knapsack(10, treasure_list) # Treasures 3, 4, 5
12
>>> me.knapsack(2, treasure_list) # Treasure 4
4
>>> me.knapsack(100, treasure_list) # Treasures 1, 2, 3, 4, 5
27
"""
"*** YOUR CODE HERE ***"
list_of_treasures = [t for t in list_of_treasures if t.weight <= max_weight]
if len(list_of_treasures) == 0 or max_weight < 0:
return 0
leave_treasure = self.knapsack(max_weight, list_of_treasures[1:])
treasure = list_of_treasures[0]
take_treasure = treasure.value + self.knapsack(max_weight - treasure.weight,
list_of_treasures[1:])
return max(take_treasure, leave_treasure)
Use OK to test your code:
python3 ok -q Player.knapsack