实验6: 非局部, 可变性
Lab 6: Nonlocal, Mutability

Due by 11:59pm on Tuesday, October 6.

查看英文原文

初始文件

下载 lab06.zip。 在压缩包中,你可以找到本实验问题的初始文件,以及一份 Ok 自动评分器。

主要内容

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 variables defined 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.


Mutability

We say that an object is mutable if its state can change as code is executed. The process of changing an object's state is called mutation. Examples of mutable objects include lists and dictionaries. Examples of objects that are not mutable include tuples and functions.

We have seen how to use the == operator to check if two expressions evaluate to equal values. We now introduce a new comparison operator, is, that checks whether two expressions evaluate to the same values.

Wait, what's the difference? For primitive values, there is none:

>>> 2 + 2 == 3 + 1
True
>>> 2 + 2 is 3 + 1
True

This is because all primitives have the same identity under the hood. However, with non-primitive values, such as lists, each object has its own identity. That means you can construct two objects that may look exactly the same but have different identities.

>>> lst1 = [1, 2, 3, 4]
>>> lst2 = [1, 2, 3, 4]
>>> lst1 == lst2
True
>>> lst1 is lst2
False

Here, although the lists referred to by lst1 and lst2 have equal contents, they are not the same object. In other words, they are the same in terms of equality, but not in terms of identity.

This is important in our discussion of mutability because when we mutate an object, we simply change its state, not its identity.

>>> lst1 = [1, 2, 3, 4]
>>> lst2 = lst1
>>> lst1.append(5)
>>> lst2
[1, 2, 3, 4, 5]
>>> lst1 is lst2
True

必答题

非局部代码练习

Q1: 递增加法器

编写一个函数,该函数接收一个整数 a 并返回一个单参数函数。 这个函数应该接收一个值 b,第一次调用时返回 a + b,类似于 make_adder。 但是第二次调用时,它应该返回 a + b + 1, 第三次调用时返回 a + b + 2,以此类推。

def make_adder_inc(a):
    """
    >>> 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 ***"

使用 Ok 来测试你的代码:

python3 ok -q make_adder_inc --local

Q2: 下一个斐波那契数

编写一个函数 make_fib,它返回一个函数,该函数每次被调用时都会返回下一个斐波那契数。 (斐波那契数列从 0 开始,然后是 1,之后的每个元素都是前两个元素之和。) 使用 nonlocal 语句!此外,不要使用 Python 列表来解决此问题。

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 ***"

使用 Ok 来测试你的代码:

python3 ok -q make_fib --local

可变性

Q3: 列表变更

通过以下问题来测试你对列表变更 (List Mutation) 的理解。Python 会输出什么?如果卡住了,可以在 Python 解释器中输入代码进行测试!

python3 ok -q list-mutation -u --local

注意:如果 Python 不会输出任何内容,请输入 Nothing

>>> lst = [5, 6, 7, 8]
>>> lst.append(6)
______
Nothing
>>> lst
______
[5, 6, 7, 8, 6]
>>> lst.insert(0, 9) >>> lst
______
[9, 5, 6, 7, 8, 6]
>>> x = lst.pop(2) >>> lst
______
[9, 5, 7, 8, 6]
>>> lst.remove(x) >>> lst
______
[9, 5, 7, 8]
>>> a, b = lst, lst[:] >>> a is lst
______
True
>>> b == lst
______
True
>>> b is lst
______
False

Q4: 插入元素

编写一个函数,该函数接受一个列表 lst,一个参数 entry,以及另一个参数 elem。 该函数会遍历 lst 中的每个元素,检查它是否与 entry 相等。 如果找到与 entry 相等的元素,则在其后面插入 elem。 最终,返回修改后的列表。请参考 doctests 以了解该函数的具体用法。 该函数必须使用列表变更(List Mutation) 来修改原始列表,不能创建或返回新的列表。

请注意:如果传入的 entryelem 具有相同的值, 可能会导致无限循环,因为每次插入 elem 后都会遇到新的 entry,从而不断插入。 如果发现代码运行时间超过几秒钟,很可能是函数进入了无限插入的循环。

def insert_items(lst, entry, elem):
    """
    >>> test_lst = [1, 5, 8, 5, 2, 3]
    >>> new_lst = insert_items(test_lst, 5, 7)
    >>> new_lst
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> large_lst = [1, 4, 8]
    >>> large_lst2 = insert_items(large_lst, 4, 4)
    >>> large_lst2
    [1, 4, 4, 8]
    >>> large_lst3 = insert_items(large_lst2, 4, 6)
    >>> large_lst3
    [1, 4, 6, 4, 6, 8]
    >>> large_lst3 is large_lst
    True
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码:

python3 ok -q insert_items --local

Submit

Make sure to submit this assignment by running:

python3 ok --submit