Study Guide: Mutation

Instructions

This is the companion guide to Quiz 5 with links to past lectures, assignments, and handouts, as well as isomorphic quiz problems and additional practice problems to assist you in learning the concepts.

Assignments

Handouts

Lectures

Readings

Guides

Quiz Rubric

View your work on Gradescope.

We identified common misconceptions and categorized student solutions for each frame of the environment diagram.

Common Misconceptions

  • Remember that we represent lists with box-and-pointer notation in environment diagrams. Non-standard notation will not receive credit. You can always refer to Python Tutor to figure out how to draw diagrams!
  • Remember that, when we refer to compound values like lists, we really mean a reference to that list which is not exactly the same as the list itself. When we need the value of a name like cache that is bound to a list, we're really working with a reference to that list.
  • Remember that nonlocal modifies the lookup and binding rules to refer to an existing name in a parent frame! The names shouldn't be included in the local frame.
  • Remember that def statements bind the name of the function to the function value. It's kind of like assigning the name to a lambda function.
  • Remember order of operations when evaluating cache(lambda x: cache)(1)! f in f1 is bound to the lambda function because that's what passed into the cache function from the expression cache(lambda x: cache). This evaluates to a one-argument function that accepts the number 1.
  • Remember to trust your work and copy the parent frame of a function exactly as it appears on your diagram! We're prone to making lookup errors when we don't keep track of the frames carefully.
  • Remember that, whenever we call a user-defined function, we create a new frame for it. Even in the case of a simple lambda function like in this problem, we still need to draw a frame for it to represent the work Python does to evaluate the lambda expression.
  • Remember that, by convention, compound values like functions and lists are pointed to, while all other primitive values are drawn directly in the bracket. With nested lists, we point to the nested list.
  • Remember that append only ever adds a single element to the end of a list.

f1

  • (-) Incorrect box-and-pointer representation for cache.
  • (-) hits should not be 0 because def hits(hits) reassigns to the nonlocal hits in f1.
  • (-) The parent of the function run was global instead of f1.
  • (-) The cache in nonlocal hits, cache only affects the lookup process in the frame in which it is declared. nonlocal cache doesn't affect f4.
  • (-) Missing return value. Every frame, unless an error occurs, must have a return value.

f2

  • (-) Extra bindings, especially for nonlocal names like hits or cache. Remember that the name and value can never be an expression like hits(hits).
  • (-) y is bound to a list or the lambda itself.
  • (-) Missing return value, or returned True, False, or anything else instead of following the evaluation procedure for or.

f3

  • (-) Missing a frame. Remember that we open a frame (f3) whenever we call a user-defined function, even a short one like lambda x: cache.
  • (-) Compound values written directly in the return value, rather than pointed-to with an arrow.
  • (-) Returned the wrong value of cache in f1 rather than the global frame.

f4

  • (-) Missing the frame due to a misconception earlier in the diagram.
  • (-) Binding of hits to 0 instead of the function suggest problem with with nonlocal rules.
  • (-) Compound values written directly as the value of a binding, rather than pointed-to with an arrow.
  • (-) Calling lst1.append(lst2) adds a single element to lst1 with the value of a pointer to lst2. It should not concatenate the two lists; the operation you might be thinking of is lst1.extend(lst2).
  • (-) Return value should point to the same object as cache, rather than making a copy of it.

Mutable Values

Mutation is the act of changing a value's attributes. Previously, we've seen immutable values like numbers and strings. Every time we work with numbers and strings, Python creates an entirely new number or string to represent the result.

n = 0
def no_effect(n):
    n += 1
no_effect(n)

Invoking no_effect(n) doesn't affect the value of n in the global frame.

In constrast, mutable values can change existing attributes. Changes to mutable values are globally-visible: any name which references that value will see the same changes. The list l can be mutated which will be seen in the global frame.

l = [0]
def effective(l):
    l.append(1)
effective(l)

Mutation is dangerous! It's not necessarily clear just from the function call effective(l) that our own l will be changed. When designing systems, we often prefer to write in a more functional style that makes it clear when the value of a name might change.

l = [0]
def add_one(l):
    return l + [1]
l = add_one(l)

The re-assignment to l makes it clear that the value of l might change, whereas, in the previous example, we would need to be a lot more careful with remembering whether or not effective mutates the values we pass to it.

What further complicates the situation is that not all operations are mutative! Some operations on lists, like append, will mutate the original list. But many other operations, like the + operator, will create a new list.

Lists

Lists are a type of mutable sequence. Because lists are also compound values, we represent them in environment diagrams with a pointer just like we do with function values.

>>> a = [1, 2, 3]
>>> b = a
>>> b.append(4)
>>> a
[1, 2, 3, 4]
>>> b
[1, 2, 3, 4]

In this example, both a and b refer to the same underlying list so changes to the list are visible to both names.

Identity

Two separate lists that have the same contents are equal but not necessarily identical. It could be the case that we happen to have two copies of a list with the exact same elements.

>>> a = [1, 2, 3, 4]
>>> b = [1, 2, 3]
>>> b.append(4)
>>> b
[1, 2, 3, 4]
>>> a == b
True
>>> a is b
False

Operations

The following is a list of common expressions which mutate the original lst. While nowhere near complete, it covers the majority of the cases you should be familiar with. Come up with examples in Python Tutor to learn how each expression affects the list.

  • Index and slice replacement

    • lst[i] = elem
    • lst[i:j] = seq
  • Element insertion

    • lst.append(elem)
    • lst.insert(i, elem)
  • Sequence insertion

    • lst.extend(seq)
    • lst += lst but not lst = lst + lst
  • Element removal

    • lst.pop() and lst.pop(i)
    • lst.remove(elem)

And a few expressions which create new lists.

  • lst + lst
  • lst * n
  • lst[i:j]
  • list(lst)

Mutable Functions

The nonlocal keyword tells Python to modify the binding in the nearest non-global parent frame rather than the current local frame. More formally, our environment diagram rules change slightly.

Assignment Statements

  1. Evaluate the expression to the right of the assignment operator =.
  2. If nonlocal, find the nearest parent frame which contains the name but not including the global frame. If not nonlocal, use the current local frame. (Note that it is a syntax error if the nonlocal keyword is used and the name doesn't exist in a non-global parent frame.)
  3. Bind the variable name to the value of the expression in the frame. Be sure you override the variable name if it had a previous binding.

Local State

While nonlocal only slightly modifies Python's execution rules, it has a big effect on how we reason about programs. Before nonlocal and mutable values, we've only written pure functions, or functions that, when called, have no effects other than returning a value. The most useful consequence of writing pure functions is that they are referentially transparency. In other words, they can be entirely replaced by the value that they return, without any change in the behavior of the program.

def add(x, y):
    return x + y

add(1, add(2, 3)) == add(1, 5) == 6

Referential transparency is important because of how we've approached concepts in this course. We can trust that a recursive call will return the right result because of how we can imagine replacing the recursive call with its return value.

With nonlocal, we can no longer rely upon this behavior. The same call to a function at different times in a program can produce different results.

def cumulative_adder(x):
    def add(y):
        nonlocal x
        x += y
        return x
    return add

add = cumulative_adder(1)
add(1)
add(1)
add(1)

We can now start to view functions as objects that can change over time, which allows for greater control, but makes our programs harder to understand.

Isomorphic Quiz Questions

Q1: Sun and Moon

Draw the environment diagram that results from running the following code.

def moon(f):
    sun = 0
    moon = [sun]
    def run(x):
        nonlocal sun, moon
        def sun(sun):
            return [sun]
        y = f(x)
        moon.append(sun(y))
        return moon[0] and moon[1]
    return run

moon(lambda x: moon)(1)

Q2: Digits

Draw the environment diagram that results from executing the following code.

def three(x):
    three = [x]*3
    nine = [three]*3
    def what(x):
        nonlocal what, three, nine
        three[x] += 1
        three = [[x]]*3
        nine[x] = three[x]
        def what(b):
            if b:
                return sum(nine[0])
            return sum(nine[2])
        return x + what(nine[x] is three[x-1])
    return what

three(2)(2)

Practice Problems

Easy

Q3: Funny Adder

Predict what Python will display when the following lines are typed into the interpreter:

>>> def make_funny_adder(n):
...     def adder(x):
...         if x == 'new':
...             nonlocal n
...             n = n + 1
...         else:
...             return x + n
...     return adder
>>> h = make_funny_adder(3)
>>> h(5)
______
8
>>> j = make_funny_adder(7) >>> j(5)
______
12
>>> h('new') >>> h(5)
______
9

Q4: Swap

Implement swap, which takes two lists and swaps their contents.

def swap(a, b):
    """Swap the contents of lists a and b.

    >>> a = [1, 'two', 3]
    >>> b = [4, [5, 6]]
    >>> swap(a, b)
    >>> a
    [4, [5, 6]]
    >>> b
    [1, 'two', 3]
    """
"*** YOUR CODE HERE ***"
a[:], b[:] = list(b), list(a)

Video walkthrough: https://youtu.be/RslfuKp5Ziw

Q5: List Accumulator

Although we can't change variables outside of our frame without a nonlocal statement, we can update values stored in mutatable objects in parent frames. Define a function make_accumulator that returns an accumulator function, which takes one numerical argument and returns the sum of all arguments ever passed to accumulator. Use a list and not a nonlocal statement:

def make_accumulator():
    """Return an accumulator function that takes a single numeric argument and
    accumulates that argument into total, then returns total.

    >>> acc = make_accumulator()
    >>> acc(15)
    15
    >>> acc(10)
    25
    >>> acc2 = make_accumulator()
    >>> acc2(7)
    7
    >>> acc3 = acc2
    >>> acc3(6)
    13
    >>> acc2(5)
    18
    >>> acc(4)
    29
    """
"*** YOUR CODE HERE ***"
total = [0] def accumulator(amount): total[0] += amount return total[0] return accumulator

Q6: Nonlocal Accumulator

Now, define a function make_accumulator_nonlocal that returns an accumulator function, which takes one numerical argument and returns the sum of all arguments ever passed to accumulator. Use a nonlocal statement.

def make_accumulator_nonlocal():
    """Return an accumulator function that takes a single numeric argument and
    accumulates that argument into total, then returns total.

    >>> acc = make_accumulator_nonlocal()
    >>> acc(15)
    15
    >>> acc(10)
    25
    >>> acc2 = make_accumulator_nonlocal()
    >>> acc2(7)
    7
    >>> acc3 = acc2
    >>> acc3(6)
    13
    >>> acc2(5)
    18
    >>> acc(4)
    29
    """
"*** YOUR CODE HERE ***"
total = 0 def accumulator(amount): nonlocal total total += amount return total return accumulator

Medium

Q7: Dice

Recall make_test_dice from the Hog project. make_test_dice takes in a sequence of numbers and returns a zero-argument function. This zero-argument function will cycle through the list, returning one element from the list every time. Implement make_test_dice.

def make_test_dice(seq):
    """Makes deterministic dice.

    >>> dice = make_test_dice([2, 6, 1])
    >>> dice()
    2
    >>> dice()
    6
    >>> dice()
    1
    >>> dice()
    2
    >>> other = make_test_dice([1])
    >>> other()
    1
    >>> dice()
    6
    """
"*** YOUR CODE HERE ***"
count = 0 def dice(): nonlocal count result = seq[count] count = (count + 1) % len(seq) return result return dice

Q8: Mutants

Draw environment diagrams to determine what Python would display.

>>> wolf = [1, 2, 3]
>>> def dog(lst):
...     def animal(ele):
...         ele = [ele] + lst
...         return [ele] + [beast[0]]
...     beast = [2, 3, animal]
...     return beast
>>> x = dog(wolf)[2](4)
>>> x
______
[[4, 1, 2, 3], 2]
>>> x = 18
>>> def it(i):
...     i = x
...     def shifty(getting):
...         nonlocal i
...         i = getting + x
...         def shiftier(y):
...             nonlocal getting
...             gettting = y*i
...             return i
...         return shiftier
...     return shifty
>>> shift = it('is')(x)(4)
>>> shift
______
36
>>> def piper(chapman):
...     chapman.append('state')
...     def alex(vause):
...         nonlocal chapman
...         chapman[1] = vause[1]
...         return chapman
...     return alex
>>> orange = piper(['litchfield', 'new york'])(['federal', 'prison'])
>>> orange
______
['litchfield', 'prison', 'state']