5 Control

Control statements are statements that control the flow of a program’s execution based on the results of logical comparisons.

5.1 Statements

Rather than being evaluated, statements are executed. Each statement describes some change to the interpreter state, and executing a statement applies that change.

Expressions can also be executed as statements, in which case they are evaluated, but their value is discarded. Executing a pure function has no effect, but executing a non-pure function can cause effects as a consequence of function application.

5.2 Compound Statements

In general, Python code is a sequence of statements. A simple statement is a single line that doesn’t end in a colon(冒号).

Compound statements typically span multiple lines and start with a one-line header ending in a colon, which identifies the type of statement. Together, a header and an indented suite of statements is called a clause. A compound statement consists of one or more clauses.

We can understand the statements we have already introduced in these terms.

  1. Expressions, return statements, and assignment statements are simple statements.
  2. A def statement is a compound statement. The suite that follows the def header defines the function body.

5.3 Defining Functions Ⅱ: Local Assignment

In fact, functions can define a sequence of operations that extends beyond a single expression.

A return statement redirects control: the process of function application terminates whenever the first return statement is executed, and the value of the return expression is the returned value of the function being applied.

The effect of an assignment statement is to bind a name to a value in the first frame of the current environment. As a consequence, assignment statements within a function body cannot affect the global frame.

1
2
3
4
def pd(x, y):
    difference = abs(x-y)
    return 100 * difference
result = pd(40, 50)

5.4 Conditional Statements

A conditional statement in Python consists of a series of headers and suites: a required if clause, an optional sequence of elif clauses, and finally an optional else clause.

1
2
3
4
5
6
if <expression>:
    <suite>
elif <expression>:
    <suite>
else:
    <suite>

The computational process of executing a conditional clause follows.

  1. Evaluate the header’s expression.
  2. If it is a true value, execute the suite. Then, skip over all subsequent clauses in the conditional statement.

Boolean contexts. Above, the execution procedures mention “a false value” and “a true value.” The expressions inside the header statements of conditional blocks are said to be in boolean contexts: their truth values matter to control flow, but otherwise their values are not assigned or returned. Python includes several false values, including 0, None, and the boolean value False. All other numbers are true values.

Boolean values. Python has two boolean values, called True and False. Boolean values represent truth values in logical expressions.

1
2
3
4
>>> 4 < 2
False
>>> 5 == 5
True

Boolean operators. Three basic logical operators are built into Python.

1
2
3
4
5
6
>>> not False
True
>>> True and False
False
>>> True or False
True

Logical expressions have corresponding evaluation procedures.
这里要注意short-circuiting
To evaluate the expression <left> and <right>:

  1. Evaluate the subexpression <left>.
  2. If the result is a false value v, then the expression evaluates to v.
  3. Otherwise, the expression evaluates to the value of the subexpression <right>.

To evaluate the expression <left> or <right>:

  1. Evaluate the subexpression <left>.
  2. If the result is a true value v, then the expression evaluates to v.
  3. Otherwise, the expression evaluates to the value of the subexpression <right>.

5.5 Iteration

In addition to selecting which statements to execute, control statements are used to express repetition.

1
2
3
4
5
6
7
8
9
def fib(n):
    """Comopute the nth Fibonacci number, n>=2."""

    pred, curr = 0, 1
    k = 2 # Which Fib number is curr
    while k < n:
        pred, curr = curr, pred + curr
        k = k + 1
    return curr

5.6 Testing

Assertions. Programmers use assert statements to verify expectations, such as the output of a function being tested. An assert statement has an expression in a boolean context, followed by a quoted line of text (single or double quotes are both fine, but be consistent) that will be displayed if the expression evaluates to a false value.

1
2
3
4
>>> assert 6==5, "no"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError: no

When writing Python in files, rather than directly into the interpreter, tests are typically written in the same file or a neighboring file with the suffix _test.py.

Doctests. Python provides a convenient method for placing simple tests directly in the docstring of a function. The first line of a docstring should contain a one-line description of the function, followed by a blank line. A detailed description of arguments and behavior may follow. In addition, the docstring may include a sample interactive session that calls the function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def fib(n):
    """Comopute the nth Fibonacci number, n>=2.
    
    >>> fib(2)
    1
    >>> fib(5)
    3
    """

    pred, curr = 0, 1
    k = 2 # Which Fib number is curr
    while k < n:
        pred, curr = curr, pred + curr
        k = k + 1
    return curr

>>> from doctest import testmod
>>> testmod()
TestResults(failed=0, attempted=2)
>>> from doctest import run_docstring_examples
>>> run_docstring_examples(fib,globals(),True)
Finding tests in NoName
Trying:
    fib(2)
Expecting:
    1
ok
Trying:
    fib(5)
Expecting:
    3
ok

To verify the doctest interactions for only a single function, we use a doctest function called run_docstring_examples. Its first argument is the function to test. The second should always be the result of the expression globals(), a built-in function that returns the global environment. The third argument is True to indicate that we would like “verbose” output: a catalog of all tests run.

When writing Python in files, all doctests in a file can be run by starting Python with the doctest command line option:

python3 -m doctest <python_source_file>

6 Higher-Order Functions

这节比较重要

Functions that manipulate functions (accept other functions as arguments or return functions as values) are called higher-order functions.

6.1 Functions as Arguments

我们先来看这三个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def sum_naturals(n):
    total, k = 0, 1
    while k <= n:
        total, k = total + k, k + 1
    return total

def sum_cubes(n):
    total, k = 0, 1
    while k <= n:
        total, k = total + k*k*k, k+1
    return total

def pi_sum(n):
    total, k = 0, 1
    while k <= n:
        total, k = total + 8 / ((4*k-3)*(4*k-1)), k+1
    return total

They are for the most part identical, differing only in name and the function of k used to compute the term to be added.

1
2
3
4
5
def <name>(n):
    total, k = 0, 1
    while k <= n:
        total, k = total + <term>(k), k+1
    return total

Each of these functions is a summation of terms. As program designers, we would like our language to be powerful enough so that we can write a function that expresses the concept of summation itself rather than only functions that compute particular sums.

We can do so readily in Python by taking the common template shown above and transforming the “slots” into formal parameters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
'''
在online python tutor里试试
term是一个函数，它作为了summation的形式参数
'''

def summation(n, term):
    total, k = 0, 1
    while k <= n:
        total, k = total + term(k), k + 1
    return total

def cube(x):
    return x*x*x

def sum_cubes(n):
    return summation(n, cube)

def pi_term(x):
    return 8 / ((4*x-3) * (4*x-1))

def pi_sum(n):
    return summation(n, pi_term)

# 试试pi_sum(1e6), 1e6是10的6次方的简写

6.2 Functions as General Methods

计算golden ratio，用online python tutor试一试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def improve(update, close, guess=1):
    while not close(guess):
	    guess = update(guess)
    return guess
	
def golden_update(guess):
	return 1/guess + 1
	
def square_close_to_successor(guess):
	return approx_eq(guess * guess, guess + 1)
	
def approx_eq(x, y, tolerance=1e-3):
	return abs(x - y) < tolerance
	
phi = improve(golden_update, square_close_to_successor)

This example illustrates two related big ideas in computer science.

  1. Naming and functions allow us to abstract away a vast amount of complexity. While each function definition has been trivial, the computational process set in motion by our evaluation procedure is quite intricate.
  2. It is only by virtue of(因为) the fact that we have an extremely general evaluation procedure for the Python language that small components can be composed into complex processes.

6.3 Defining Functions Ⅲ: Nested Definitions

我们想计算一个数a的平方根，可以这样逼近

1
2
3
4
5
def average(x, y):
    return (x + y) / 2

def sqrt_update(x, a):
    return average(x, a/x)

但是，improve里的update函数只能接受一个参数

1
2
3
4
5
6
def sqrt(a):
    def sqrt_update(x):
        return average(x, a/x)
    def sqrt_close(x):
        return approx_eq(x*x, a)
    return improve(sqrt_update, sqrt_close)

Like local assignment, local def statements only affect the current local frame. These functions are only in scope while sqrt is being evaluated. Consistent with our evaluation procedure, these local def statements don’t even get evaluated until sqrt is called.

Lexical scope. Locally defined functions also have access to the name bindings in the scope in which they are defined. In this example, sqrt_update refers to the name a, which is a formal parameter of its enclosing function sqrt. This discipline of sharing names among nested definitions is called lexical scoping(词法作用域). Critically, the inner functions have access to the names in the environment where they are defined (not where they are called).

现在可以再回看上一篇文章的高阶函数的例子了，那个例子中，adder被调用(call)，创建一个新的frame，f2，但可以访问f1里的n

这里有个小点，第一次写的时候写成adder在f2里被evaluate，这是错误的，evaluate仅仅是求值，函数被调用时才会创建新的frame
例如c=add(1,2)

  1. 求值operator，这个时候是对add进行evaluate，看看当前frame里这个名字绑定的对象
  2. 求值operands
  3. 调用函数add，创建一个frame

对于一个user-defined function，我们总结一下

We require two extensions to our environment model to enable lexical scoping.

  1. Each user-defined function has a parent environment: the environment in which it was defined.
  2. When a user-defined function is called, its local frame extends its parent environment.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def average(x, y):
    return (x + y) / 2

def improve(update, close, guess=1):
    while not close(guess):
	    guess = update(guess)
    return guess
	
def golden_update(guess):
	return 1/guess + 1
	
def square_close_to_successor(guess):
	return approx_eq(guess * guess, guess + 1)
	
def approx_eq(x, y, tolerance=1e-3):
	return abs(x - y) < tolerance

def sqrt(a):
    def sqrt_update(x):
        return average(x, a/x)
    def sqrt_close(x):
        return approx_eq(x*x, a)
    return improve(sqrt_update, sqrt_close)

result = sqrt(256) # 看看environment diagram

在调用sqrt(256)时，environment第一次加入sqrt的local frame，并执行 sqrt_update和sqrt_close的def语句

Function values each have a new annotation(注解) that we will include in environment diagrams from now on, a parent. The parent of a function value is the first frame of the environment in which that function was defined. Functions without parent annotations were defined in the global environment. When a user-defined function is called, the frame created has the same parent as that function.

Extended Environments. An environment can consist of an arbitrarily long chain of frames, which always concludes with the global frame.

By calling functions that were defined within other functions, via nested def statements, we can create longer chains. The environment for this call to sqrt_update consists of three frames: the local sqrt_update frame, the sqrt frame in which sqrt_update was defined (labeled f1), and the global frame.

The return expression in the body of sqrt_update can resolve a value for a by following this chain of frames. Looking up a name finds the first value bound to that name in the current environment. Python checks first in the sqrt_update frame —— no a exists. Python checks next in the parent frame, f1, and finds a binding for a to 256.

Hence, we realize two key advantages of lexical scoping in Python.

  1. The names of a local function do not interfere with names external to the function in which it is defined, because the local function name will be bound in the current local environment in which it was defined, rather than the global environment.(在上个例子中，我们可以在global frame里定义a=2019，这完全不会影响sqrt内部的函数找a，它们在f1(sqrt的frame)里找到a=256后就会停下了)
  2. A local function can access the environment of the enclosing function, because the body of the local function is evaluated in an environment that extends the evaluation environment in which it was defined.

The sqrt_update function carries with it some data: the value for a referenced in the environment in which it was defined. Because they “enclose” information in this way, locally defined functions are often called closures(闭包).

6.4 Functions as Returned Values

The environment diagram for this example shows how the names f and g are resolved correctly, even in the presence of conflicting names.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def square(x):
    return x * x

def successor(x):
    return x + 1

def compose1(f, g):
    def h(x):
        return f(g(x))
    return h

def f(x):
    """Never Called"""
    return x

square_successor = compose1(square, successor)
result = square_successor(12)

6.5 Example: Newtonw’s Method

Newton’s method is a classic iterative approach to finding the arguments of a mathematical function that yield a return value of 0. These values are called the zeros(零点) of the function.

我们可以用牛顿法求平方根，事实上，求平方根并不是一件理所当然的事
牛顿法是一个迭代的算法，它对于可微函数的零点进行猜测，然后不断改进。在当前的点(xk,f(xk))(x_k, f(x_k))作切线，切线与xx轴的交点为xk+1x_{k+1}，重复操作，{x}\{x\}会收敛到方程的根

其中

xk+1=xk−f(xk)f′(xk)x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def newton_update(f, df):
    def update(x):
        return x - f(x) / df(x)
    return update

def improve(update, close, guess=1):
    while not close(guess):
	    guess = update(guess)
    return guess
	
def approx_eq(x, y, tolerance=1e-3):
	return abs(x - y) < tolerance

def find_zero(f, df):
    def near_zero(x):
        return approx_eq(f(x), 0)
    return improve(newton_update(f, df), near_zero)

下面我们来计算n次方根

1
2
3
4
5
6
7
8
9
10
11
12
13
def power(x, n):
    result, k = 1, 1
    while k <= n:
        total = total * x
        k = k + 1
    return result

def nth_root_of_a(n, a):
    def f(x):
        return power(x, n) - a
    def df(x):
        return n*power(x, n-1)
    return find_zero(f, df)

牛顿法的初值选择比较重要，需要接近零点，否则可能不收敛。牛顿法是很重要的，至于它在计算机科学领域的应用，目前我也不大看得懂。

6.6 Currying

We can use higher-order functions to convert a function that takes multiple arguments into a chain of functions that each take a single argument. This transformation is called currying.

1
2
3
4
5
6
7
def curried_pow(x):
    def h(y):
        return pow(x, y)
    return h

result = pow(45, 2)
another_result = curried_pow(45)(2)

Actually, we can define functions to automate currying, as well as the inverse uncurrying transformation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def curry2(f):
    """
    Return a curried version of the given two-argument function.

    f -- the given two-argument function

    >>> curry2(45)(2)
    2025
    """
    def g(x):
        def h(y):
            return f(x, y)
        return h
    return g

def uncurry2(g):
    """
    Return a two-argument version of the given curried function.

    g -- the given curried function
    """
    def f(x, y):
        return g(x)(y)
    return f

6.7 Lambda Expressions

In Python, we can create function values on the fly using lambda expressions, which evaluate to unnamed functions. A lambda expression evaluates to a function that has a single return expression as its body. Assignment and control statements are not allowed.

1
2
lambda x: f(g(x))
# A function that takes x and returns f(g(x))

The result of a lambda expression is called a lambda function. It has no intrinsic name (and so Python prints <lambda> for the name), but otherwise it behaves like any other function.

1
2
3
4
5
>>> s = lambda x,y : x*y
>>> s
<function <lambda> at 0x73b36815d5e0>
>>> s(3, 673)
2019

看一下这个的environment diagram

1
2
3
4
5
6
def compose1(f, g):
    return lambda x: f(g(x))

f = compose1(lambda x: x * x, lambda y: y + 1)

result = f(12)

In an environment diagram, the result of a lambda expression is a function as well, named with the greek letter λ (lambda).

6.8 Abstractions and First-Class Functions

We began this section with the observation that user-defined functions are a crucial abstraction mechanism, because they permit us to express general methods of computing as explicit elements in our programming language. Now we’ve seen how higher-order functions permit us to manipulate these general methods to create further abstractions.

In general, programming languages impose restrictions on the ways in which computational elements can be manipulated. Elements with the fewest restrictions are said to have first-class status. Some of the “rights and privileges” of first-class elements are:

  1. They may be bound to names.
  2. They may be passed as arguments to functions.
  3. They may be returned as the results of functions.
  4. They may be included in data structures.
    Python awards functions full first-class status, and the resulting gain in expressive power is enormous.

6.9 Function Decorators

Python provides special syntax to apply higher-order functions as part of executing a def statement, called a decorator. Perhaps the most common example is a trace.

1
2
3
4
5
6
7
8
9
def trace(fn):
    def wrapped(x):
        print('->', fn, '(', x, ')')
        return fn(x)
    return wrapped

@trace
    def triple(x):
        return 3 * x

The def statement for triple has an annotation, @trace, which affects the execution rule for def. As usual, the function triple is created. However, the name triple is not bound to this function. Instead, the name triple is bound to the returned function value of calling trace on the newly defined triple function. In code, this decorator is equivalent to:

1
2
3
4
5
6
7
8
9
@trace
    def triple(x):
        return 3 * x

'''等价于'''

def triple(x):
    return 3 * x
triple = trace(triple)

Extra for experts. The decorator symbol @ may also be followed by a call expression. The expression following @ is evaluated first (just as the name trace was evaluated above), the def statement second, and finally the result of evaluating the decorator expression is applied to the newly defined function, and the result is bound to the name in the def statement. A short tutorial on decorators by Ariel Ortiz gives further examples for interested students.

7 Recursive Functions

A function is called recursive if the body of the function calls the function itself, either directly or indirectly. That is, the process of executing the body of a recursive function may in turn require applying that function again.

1
2
3
4
5
6
7
8
9
def sum_digits(n):
    """Return the sum of the digits of positive integer n."""
    if n < 10:
        return n
    else:
        all_but_last, last = n // 10, n % 10
        return sum_digits(all_but_last) + last

result = sum_digits(738)

When sum_digits is called on 738:

  1. A local frame for sum_digits with n bound to 738 is created, and the body of sum_digits is executed in the environment that starts with that frame.
  2. Since 738 is not less than 10, the assignment statement is executed, splitting 738 into 73 and 8.
  3. In the following return statement, sum_digits is called on 73, the value of all_but_last in the current environment.
  4. Another local frame (Its parent is global frame, 因为在f1里evaluate sum_digits时，现在f1找这个name，没找到，在global frame里找到了，而sum_digits的parent在定义时就明确了是global frame，所以调用sum_digits时创建的f2的parent是global frame) for sum_digits is created, this time with n bound to 73. The body of sum_digits is again executed in the new environment that starts with this frame.
  5. Since 73 is also not less than 10, 73 is split into 7 and 3 and sum_digits is called on 7, the value of all_but_last evaluated in this frame.
  6. A third local frame for sum_digits is created, with n bound to 7.
  7. In the environment starting with this frame, it is true that n < 10, and therefore 7 is returned.
  8. In the second local frame, this return value 7 is summed with 3, the value of last, to return 10.
  9. In the first local frame, this return value 10 is summed with 8, the value of last, to return 18.

7.1 The Anatomy of Recursive Functions

A common pattern can be found in the body of many recursive functions. The body begins with a base case, a conditional statement that defines the behavior of the function for the inputs that are simplest to process.

The base cases are then followed by one or more recursive calls. Recursive calls always have a certain character: they simplify the original problem. Recursive functions express computation by simplifying problems incrementally.

Treating a recursive call as a functional abstraction has been called a recursive leap of faith. We define a function in terms of itself, but simply trust that the simpler cases will work correctly when verifying the correctness of the function.

7.2 Mutual Recursion

When a recursive procedure is divided among two functions that call each other, the functions are said to be mutually recursive.

1
2
3
4
5
6
7
8
9
10
11
12
def is_even(n):
    if n==0:
        return True
    else:
        return is_odd(n-1)

def is_odd(n):
    if n==0:
        return False
    else:
        return is_even(n-1)
result = is_even(4)

Mutually recursive functions can be turned into a single recursive function by breaking the abstraction boundary between the two functions.

1
2
3
4
5
6
7
8
9
def is_even(n):
    if n == 0:
        return True
    else:
        if (n-1) == 0:
            return False
        else:
            return is_even((n-1)-1) 
    # 直接把is_odd的body搬过来，n替换为n-1

7.3 Printing in Recursive Functions

The computational process evolved by a recursive function can often be visualized using calls to print.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def cascade(n):
    """Print a cascade of prefixes of n."""
    if n < 10:
        print(n)
    else:
        print(n)
        cascade(n//10)
        print(n)

❯ python -i ex.py
>>> cascade(5)
5
>>> cascade(12345)
12345
1234
123
12
1
12
123
1234
12345
>>>

Example:Inverse Cascade

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def inverse_cascade(n):
    grow(n)
    print(n)
    shrink(n)

def grow(n):
    if n >= 10:
        grow(n//10)
        print(n//10)

def shrink(n):
    if n >= 10:
        print(n//10)
        shrink(n//10)
#再抽象一下
def grow_or_shrink(f,g,n):
    if n >= 10:
        f(n//10)
        g(n//10)
grow = lambda n:grow_or_shrink(grow,print,n)
shrink = lambda n:grow_or_shrink(print,shrink,n)

#############################

def inverse_cascade(n):
    grow(n)
    print(n)
    shrink(n)


def f_then_g(f,g,n):
    if n:
        f(n)
        g(n)

grow = lambda n:f_then_g(grow,print,n//10)

shrink = lambda n:f_then_g(print,shrink,n//10)
1
2
3
4
5
6
7
8
9
10
11
12
❯ python -i ex.py
>>> inverse_cascade(12345)
1
12
123
1234
12345
1234
123
12
1
>>>

7.4 Tree Recursion

Another common pattern of computation is called tree recursion, in which a function calls itself more than once.

A function with multiple recursive calls is said to be tree recursive because each call branches into multiple smaller calls, each of which branches into yet smaller calls, just as the branches of a tree become smaller but more numerous as they extend from the trunk.

1
2
3
4
5
6
7
8
9
10
11
12
def fib(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    else:
        return fib(n-2) + fib(n-1)

'''
调用两次fib，出现树状递归
画出递归树可以看出，算fib(5)时算了2次fib(3)，效率比较低
'''

7.5 Example: Partitions

We will define a function count_partitions(n, m) that returns the number of different partitions of n using parts up to m.

Notice that all the ways of partitioning n can be divided into two groups: those that include at least one m and those that do not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def count_partitions(n, m):
    if n == 0:
        return 1
    '''
    n是正整数，n变成0说明是前面n-m时n-m=0了
    这时n=m或者拆分中带了一个m，也算一种
    从这里可以看到，n=0并不是我们想象中简单的base case，即只考虑n=0到底有几种

    而是要根据下面的递推，看最后到什么地步要停下来，并以此确定base case的取值

    例如，对于count_partitions(2,1)
    我们画出递归树，得到这些base case：
    (其实就是leaf)
    (0, 1), (1, 0), (2, 0)
    对于递归树的(1, 1)来说，(0, 1)是否为0似乎只是规定了1=1算不算一种
    但是如果(0, 1)规定为0，2=1+1就会被漏掉，所以一定不能规定为0

    事实上，这种“一定”来源于我们使用的递推公式
    如果我们用递推公式的思路想问题，n=0代表一种某个分割方式结束的状态
    它不知道上一步是什么，如果直接设置为0，那么如果有上一步，这种分割就被忽略了
    '''

    elif n < 0:
        return 0
    elif m == 0:
        return 0
    else:
        return count_partitions(n-m, m) + count_partitions(n, m-1)