Lab 6: Nonlocal & Generators
Due by 11:59pm on Friday, March 6.
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.
Check that you have successfully submitted your code on
okpy.org.
Topics
Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.
Nonlocal
We say that a variable defined in a frame is local to that frame. A variable is nonlocal to a frame if it is defined in the environment that the frame belongs to but not the frame itself, i.e. in its parent or ancestor frame.
So far, we know that we can access variables in parent frames:
def make_adder(x):
""" Returns a one-argument function that returns the result of
adding x and its argument. """
def adder(y):
return x + y
return adder
Here, when we call make_adder
, we create a function adder
that is able to
look up the name x
in make_adder
's frame and use its value.
However, we haven't been able to modify variable in parent frames. Consider the following function:
def make_withdraw(balance):
"""Returns a function which can withdraw
some amount from balance
>>> withdraw = make_withdraw(50)
>>> withdraw(25)
25
>>> withdraw(25)
0
"""
def withdraw(amount):
if amount > balance:
return "Insufficient funds"
balance = balance - amount
return balance
return withdraw
The inner function withdraw
attempts to update the variable balance
in its
parent frame. Running this function's doctests, we find that it causes the
following error:
UnboundLocalError: local variable 'balance' 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 balance = ...
in withdraw
,
is creating the local variable balance
inside withdraw
's frame. This
assignment statement tells Python to expect a variable called balance
inside
withdraw
's frame, so Python will not look in parent frames for this variable.
However, notice that we tried to compute balance - amount
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!
Some important things to keep in mind when using
nonlocal
nonlocal
cannot be used with global variables (names defined in the global frame).- If no nonlocal variable is found with the given name, a
SyntaxError
is raised.- A name that is already local to a frame cannot be declared as nonlocal.
Consider this improved example:
def make_withdraw(balance):
"""Returns a function which can withdraw
some amount from balance
>>> withdraw = make_withdraw(50)
>>> withdraw(25)
25
>>> withdraw(25)
0
"""
def withdraw(amount):
nonlocal balance
if amount > balance:
return "Insufficient funds"
balance = balance - amount
return balance
return withdraw
The line nonlocal balance
tells Python that balance
will not be local to this frame, so it will look for it in parent frames. Now we can update balance
without running into problems.
Generators
We can create our own custom iterators by writing a generator function, which
returns a special type of iterator called a generator. Generator functions
have yield
statements within the body of the function instead of return
statements. Calling a generator function will return a generator object and
will not execute the body of the function.
For example, let's consider the following generator function:
def countdown(n):
print("Beginning countdown!")
while n >= 0:
yield n
n -= 1
print("Blastoff!")
Calling countdown(k)
will return a generator object that counts down from k
to 0. Since generators are iterators, we can call iter
on the resulting
object, which will simply return the same object. Note that the body is not
executed at this point; nothing is printed and no numbers are output.
>>> c = countdown(5)
>>> c
<generator object countdown ...>
>>> c is iter(c)
True
So how is the counting done? Again, since generators are iterators, we call
next
on them to get the next element! The first time next
is called,
execution begins at the first line of the function body and continues until the
yield
statement is reached. The result of evaluating the expression in the
yield
statement is returned. The following interactive session continues
from the one above.
>>> next(c)
Beginning countdown!
5
Unlike functions we've seen before in this course, generator functions can
remember their state. On any consecutive calls to next
, execution picks up
from the line after the yield
statement that was previously executed. Like
the first call to next
, execution will continue until the next yield
statement is reached. Note that because of this, Beginning countdown!
doesn't
get printed again.
>>> next(c)
4
>>> next(c)
3
The next 3 calls to next
will continue to yield consecutive descending
integers until 0. On the following call, a StopIteration
error will be
raised because there are no more values to yield (i.e. the end of the function
body was reached before hitting a yield
statement).
>>> next(c)
2
>>> next(c)
1
>>> next(c)
0
>>> next(c)
Blastoff!
StopIteration
Separate calls to countdown
will create distinct generator objects with their
own state. Usually, generators shouldn't restart. If you'd like to reset the
sequence, create another generator object by calling the generator function
again.
>>> c1, c2 = countdown(5), countdown(5)
>>> c1 is c2
False
>>> next(c1)
5
>>> next(c2)
5
Here is a summary of the above:
- A generator function has a
yield
statement and returns a generator object. - Calling the
iter
function on a generator object returns the same object without modifying its current state. - The body of a generator function is not evaluated until
next
is called on a resulting generator object. Calling thenext
function on a generator object computes and returns the next object in its sequence. If the sequence is exhausted,StopIteration
is raised. A generator "remembers" its state for the next
next
call. Therefore,the first
next
call works like this:- Enter the function and run until the line with
yield
. - Return the value in the
yield
statement, but remember the state of the function for futurenext
calls.
- Enter the function and run until the line with
And subsequent
next
calls work like this:- Re-enter the function, start at the line after the
yield
statement that was previously executed, and run until the nextyield
statement. - Return the value in the
yield
statement, but remember the state of the function for futurenext
calls.
- Re-enter the function, start at the line after the
- Calling a generator function returns a brand new generator object (like
calling
iter
on an iterable object). - A generator should not restart unless it's defined that way. To start over from the first element in a generator, just call the generator function again to create a new generator.
Another useful tool for generators is the yield from
statement (introduced in
Python 3.3). yield from
will yield all values from an iterator or iterable.
>>> def gen_list(lst):
... yield from lst
...
>>> g = gen_list([1, 2, 3, 4])
>>> next(g)
1
>>> next(g)
2
>>> next(g)
3
>>> next(g)
4
>>> next(g)
StopIteration
Required Questions
Nonlocal Codewriting
For the following question, write your code in lab06.py
.
Q1: Make Adder Increasing
Write a function which takes in an integer n
and returns a one-argument function.
This function should take in some value x
and return n + x
the first time it is called,
similar to make_adder
. The second time it is called, however, it should return n + x + 1
,
then n + x + 2
the third time, and so on.
def make_adder_inc(n):
"""
>>> adder1 = make_adder_inc(5)
>>> adder2 = make_adder_inc(6)
>>> adder1(2)
7
>>> adder1(2) # 5 + 2 + 1
8
>>> adder1(10) # 5 + 10 + 2
17
>>> [adder1(x) for x in [1, 2, 3]]
[9, 11, 13]
>>> adder2(5)
11
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q make_adder_inc
Q2: Next Fibonacci
Write a function make_fib
that returns a function that returns the
next Fibonacci number each time it is called. (The Fibonacci sequence begins with 0
and then 1, after which each element is the sum of the preceding two.)
Use a nonlocal
statement!
def make_fib():
"""Returns a function that returns the next Fibonacci number
every time it is called.
>>> fib = make_fib()
>>> fib()
0
>>> fib()
1
>>> fib()
1
>>> fib()
2
>>> fib()
3
>>> fib2 = make_fib()
>>> fib() + sum([fib2() for _ in range(5)])
12
>>> from construct_check import check
>>> # Do not use lists in your implementation
>>> check(this_file, 'make_fib', ['List'])
True
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q make_fib
Generators
Generators also allow us to represent infinite sequences, such as the sequence of natural numbers (1, 2, ...).
def naturals():
"""A generator function that yields the infinite sequence of natural
numbers, starting at 1.
>>> m = naturals()
>>> type(m)
<class 'generator'>
>>> [next(m) for _ in range(10)]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
"""
i = 1
while True:
yield i
i += 1
Q3: Scale
Implement the generator function scale(it, multiplier)
, which yields elements of the
given iterable it
, scaled by multiplier
. As an extra challenge, try writing this
function using a yield from
statement!
def scale(it, multiplier):
"""Yield elements of the iterable it scaled by a number multiplier.
>>> m = scale([1, 5, 2], 5)
>>> type(m)
<class 'generator'>
>>> list(m)
[5, 25, 10]
>>> m = scale(naturals(), 2)
>>> [next(m) for _ in range(5)]
[2, 4, 6, 8, 10]
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q scale
Q4: Hailstone
Write a generator that outputs the hailstone sequence from homework 1.
Here's a quick reminder of how the hailstone sequence is defined:
- Pick a positive integer
n
as the start. - If
n
is even, divide it by 2. - If
n
is odd, multiply it by 3 and add 1. - Continue this process until
n
is 1.
For some extra practice, try writing a solution using recursion. Since
hailstone
returns a generator, you can yield from
a call to hailstone
!
def hailstone(n):
"""
>>> for num in hailstone(10):
... print(num)
...
10
5
16
8
4
2
1
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q hailstone
Submit
Make sure to submit this assignment by running:
python3 ok --submit