Lab 6 Solutions

Solution Files

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 the next 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:

      1. Enter the function and run until the line with yield.
      2. Return the value in the yield statement, but remember the state of the function for future next calls.
    • And subsequent next calls work like this:

      1. Re-enter the function, start at the line after the yield statement that was previously executed, and run until the next yield statement.
      2. Return the value in the yield statement, but remember the state of the function for future next calls.
  • 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
    """
def adder(x): nonlocal n value = n + x n = n + 1 return value return adder

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
    """
cur, next = 0, 1 def fib(): nonlocal cur, next result = cur cur, next = next, cur + next return result return fib

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]
    """
for elem in it: yield elem * multiplier # Alternate solution def scale(it, multiplier): yield from map(lambda x: x*multiplier, it)

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:

  1. Pick a positive integer n as the start.
  2. If n is even, divide it by 2.
  3. If n is odd, multiply it by 3 and add 1.
  4. 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
    """
while n > 1: yield n if n % 2 == 0: n //= 2 else: n = n * 3 + 1 yield n # Alternate Solution def hailstone_alt(n): yield n if n > 1: if n % 2 == 0: yield from hailstone_alt(n // 2) else: yield from hailstone_alt(n * 3 + 1) # Video Walkthrough: https://youtu.be/fQlIJa2_yqw?t=1h18m52s

Use Ok to test your code:

python3 ok -q hailstone

Submit

Make sure to submit this assignment by running:

python3 ok --submit