rnl.org

Chapter 1: Building Abstractions with Functions

Funcs

Expressions

Types of expressions

An expression describes a computation and evaluates to a value

Primitive expressions

2 + 1

Call expressions

max(2,3)

Call Expressions in Python

All expressions can use func call notation max(2,3)

Anatomy of a Call Expression

Evaluation procedure for call expressions: add(2, 3) Operators and operands are also expressions, so they evaluate to values.

Evaluate the operator and then the operand subexpressions

operator	add
operand1	2
operand2	3

Apply the func that is the value of the operator subexpression to the args that are the values of the operand subexpression

func	value of add
arg1	value of 2
arg2	value of 3

Evaluating Nested Expressions

mul(add(4,mul(4, 6)), add(3, 5))

Funcs, Values, Objects, Interpreters, and Data

Objects

from urllib.request import urlopen
shakes = urlopen('http://composingprograms.com/shakespeare.txt')
text = shakes.read().split()

print(len(text),'\n',text[:25],'\n', text.count(b'the'), '\n', text.count(b','))

Sets

words = set(text)
print(len(words),'\n',max(words))

Reversals

print('draw'[::-1])
print({w for w in words if w == w[::-1] and len(w)>4})
print({w for w in words if w[::-1] in words and len(w) == 4})
print({w for w in words if w[::-1] in words and len(w) > 6})

Names

Env Diagrams

Env Diagrams

Env diagrams visualize the interpreter’s process.

Code

Statements and expressions

from math import pi
tau = 2 * pi
return pi, tau

Frames

Each name is bound to a value. Within a frame, a name cannot be repeated

Global frame
name	value
pi	3.1416
tau	6.2832

Assignment Statements

Execution rule for assignment statements:

• Evaluate all expressions to the right of = from left to right.
• Bind all names to the left of = to those resulting values in the current frame.

a = 1
b = 2
b, a = a + b, b
print(a,b)

Defining Funcs

Defining Funcs

Assignment is a simple means of abstraction: binds names to values Func def is a more powerful means of abstraction: binds names to expressions

def <name>(<formal parameters>): 
    return <return expression>

Execution procedure for def statements:

1. Create a func with signature <name>(<formal parameters>), func signature indicates how many args a func takes, it has all the

information needed to create a local frame.

1. Set the body of that func to be everything indented after the first line, func body defines the computation performed when the func is applied
2. Bind <name> to that func in the current frame

Calling User-Defined Funcs

Procedure for calling/applying user-defined funcs

1. Add a local frame, forming a new env
2. Bind the func’s formal parameters to its args in that frame
3. Execute the body of the func in that new env

Looking Up Names In Env

Every expression is evaluated in the context of an env. So far, the current env is either:

• The global frame alone, or
• A local frame, followed by the global frame.

Most important two things:

1. An env is a sequence of frames.
2. A name evaluates to the value bound to that name in the earliest frame of the current env in which that name is found.

Control

Print and None

None Indicates that Nothing is Returned

• The special value None represents nothing in Python
• A func that does not explicitly return a value will return None
• Careful: None is not displayed by the interpreter as the value of an expression

  def does_not_return_square(a):
      a*a
  x = does_not_return_square(4) + 3 
  return x
      

Pure Funcs & Non-Pure Funcs

Pure Funcs

just return values: abs()

return abs(-2)

Non-Pure Funcs

return values(None) and have side effects: print()

a = print(2)
print(a)

Nested Expressions with Print

a = print(print(1), print(2))
print(a)

Multiple Envs

Life Cycle of a User-Defined Func

Def statement:

def square(x):
    return mul(x, x)

• A new func is created!
• Name bound to that func in the current frame

Call expression:

square(2+2)

• Operator & operands evaluated
• Func (value of operator) called on args (values of operands):

Calling/Applying:

• A new frame is created!
• Body is executed in that new env

Multiple Envs in One Diagram!

from operator import mul
def square(x):
    return mul(x, x);
print(square(square(3)))

An env is a sequence of frames.

• The global frame alone
• A local, then the global frame

One env per frame here

ENV1

Frames	Global
funcs	mul, square

ENV2

Frames	f2: square [parent=Global
x	3
return value	9

ENV3

Frames	f3: square [parent=Global
x	9
return value	81

Names Have No Meaning Without Envs

• Every expression is evaluated in the context of an env.
• A name evaluates to the value bound to that name in the earliest frame of the current env in which that name is found.

Names Have Different Meanings in Different Envs

from operator import mul
def square(square):
    return mul(square, square)
print(square(4))

A call expression and the body of the func being called are evaluated in different envs

call of square(4)	ENV1:Global
body of square(4)	ENV2:f1 followed by Global

Miscellaneous Python Features

Operators

Addition

print(2+3*4+5,'\n',(2+3)*(4+5))

Division

print(618 / 10, 618 // 10, 618 % 10)
from operator import truediv, floordiv, mod
print(truediv(618, 10), floordiv(618, 10), mod(618, 10))

Multiple Return Values

def divide_exact(n, d):
    return n // d, n % d
quotient, remainder = divide_exact(618, 10)
print(quotient, remainder)

Docstrings, doctests, & default args

use python3 -m doctest test.py to doctest.

def divide_exact(n, d=10):
    """Return the quotient and remainder of dividing N by D.

    >>> quotient, remainder = divide_exact(618, 10)
    >>> quotient
    61
    >>> remainder
    8
    """
    return floordiv(n, d), mod(n, d)

Conditional Statements

Statements

A statement is executed by the interpreter to perform an action

Compound statements

The first header determins a statement’s type: def if while…

Conditional Statements

def absolute_value(x):
    if x < 0:
        return -x
    elif x == 0:
        return0
    else:
        return x

1 statement, 3 clauses, 3 headers, 3 suites.

Boolean Contexts

In python

False	False, 0, ”, None, [], …
True	Not false

Iteration

While Statements

i,total = 0, 0
while i < 3:
    i = i + 1
    total = total + 1

Example: The Fibonacci Sequence

def fib(n):
    """Compute the nth Fibonacci number"""
    pred, curr = 0, 1 #--> pred, curr = 1, 0
    k = 1             #--> k = 0
    while k < n:
        pred, curr = curr, pred + curr
        k = k + 1
    return curr

1.6 Higher-Order Funcs

Funcs that manipulate funcs are called higher-order funcs

1.6.1 Funcs as Args

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

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

def identity(x):
        return x

def sum_naturals(n):
        return summation(n, identity)

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)

1.6.2 Funcs as General Methods

A more powerful kind of abstraction in higher-order funcs

Some funcs express general methods of computation, independent of the particular funcs they call.

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-15):
        return abs(x - y) < tolerance

phi = improve(golden_update,square_close_to_successor)

• This improve func is a general expression of repetitive refinement.It doesn’t specify what problem is being solved: those details are left to the update and close funcs passed in as args.
• When a user-defined func is applied to some args, the formal parameters are bound to the values of those arguments (which may be funcs) in a new local frame.

Two related big ideas in computer science

• Naming and funcs allow us to abstract away a vast amount of complexity.
• Only an extremely general evaluation procedure for the Python language can make small components composed into complex processes.

A test to check its correctness.

from math import sqrt
phi = 1/2 + sqrt(5)/2
def improve_test():
        approx_phi = improve(golden_update, square_close_to_successor)
        assert approx_eq(phi, approx_phi), 'phi differs from its approximation'

improve_test()

1.6.3 Defining Funcs III: Nested Defs

Problems of passing funcs as args

Pass functions as arguments significantly enhances the expressive power of python.

Two problems

• Global frame becomes cluttered with names of small functions, which must all be unique.
• We are constrained by particular function signatures.(the update argument to improve must take exactly one argument.)

Nested func def address problems above

Example: square root of a number

def average(x, y):
    return (x + y)/2

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 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)

Env review

Most important two things:

1. An env is a sequence of frames.
2. A name evaluates to the value bound to that name in the earliest frame of the current env in which that name is found.

Life Cycle of a User-Defined FuncDef statement:

• Name bound to that func in the current frame

Calling/Applying:

• A new frame is created!
• Body is executed in that new env

Env analysis

Env	Frame(created when calling func)	Func evaluated within frame	Arg evaluted within frame
Env1	Global	average, improve, approx_eq, sqrt	None
Env2 extended from Env1	f1: sqrt [parent=Global	sqrt_update, sqrt_close	a=256
Env3 extended from Env1	f2: improve [parent=Global	None	update= sqrt_update, close= sqrt_close , guess=1
Env4 extended from Env2	f3: sqrt_close [parent=f1 [parent=Global	None	x=1, a=256(from parent f1)
Env5 extended from Env1	f4: approx_eq [parent=Global	None	x=1, y=256, tolerance=0.001

Env	Frame(created when calling func)	Func evaluated within frame	Arg evaluted within frame
Env1	Global	average, improve, approx_eq, sqrt	None
Env2 extended from Env1	f1: sqrt [parent=Global	sqrt_update, sqrt_close	a=256
Env3 extended from Env1	f2: improve [parent=Global	None	update= sqrt_update, close= sqrt_close , guess=1
Env6 extended from Env2	f5: sqrt_update [parent=f1 [parent=Global	None	x=1, a=256(from parent f1)
Env7 extended from Env1	f6: average [parent=Global	None	x=1, y=256

Lexical scope

The inner funcs have access to the names in the env where they are defined (not where they are called).

Two extensions to our env model to enable lexical scoping

• Each user-defined func has a parent env: the environment in which it was defined.
• When a user-defined func is called, its local frame extends its parent env.

Two key advantages of lexical scoping in Python

• The names of a local func 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 env in which it was defined, rather than the global environment.
• A local func can access the env of the enclosing func, because the body of the local func is evaluated in an env that extends the evaluation environment in which it was defined.

1.6.4 Funcs as Returned Values

Funcs as returned values can achieve more expressive power.

Example: function composition h(x) = f(g(x))

def square(x):
    return x*x

def successor(x):
    return x + 1

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

def f(x):
    """Never called"""
    return -x

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

Env analysis

Env	Frame(created when calling func)	Func evaluated within frame	Arg evaluted within frame
Env1	Global	square, successor, compose1, f, square_successor	None
Env2 extended from Env1	f1: compose1 [parent=Global	h	f= square, g= successor
Env3 extended from Env2	f2: h [parent=f1 [parent=Global	None	x=12
Env4 extended from Env1	f3: successor [parent=Global	None	x=12
Env5 extended from Env1	f4: square [parent=Global	None	x=13

• f and g are resolved correctly, even in the presence of conflicting names(f defined in Global frame).
• An important feature of lexically scoped programming languages: locally defined functions maintain their parent environment when they are returned (when return f(g(x)), f and g are found from parent frame f1)

Question:

1. 怎么结合env分析比较好的描述程序执行过程？包括环境之间的跳转，返回等。用哪种方式，dot画环境跳转、参数传递、返回值和拓展关系图可行吗？

1.6.5 Example: Newton’s Method

This extended example shows how function return values and local definitions can work together to express general ideas concisely.

Square root

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 newton_update(f, df):
    def update(x):
        return x - f(x) / df(x)
    return update

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

def square_root_newton(a):
    def f(x):
        return x * x - a
    def df(x):
        return 2 * x
    return find_zero(f, df)

square_root_newton(64)

Nth root

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 newton_update(f, df):
    def update(x):
        return x - f(x) / df(x)
    return update

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

def power(x, n):
    """Return x*x*x*...*x for x repeated n times."""
    product, k = 1, 0
    while k < n:
        product, k = product * x, k + 1
    return product

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)

nth_root_of_a(3, 64)

Question:

1. 仍然是怎么结合env分析清晰的整理程序执行过程？特别是在参数传递和返回值环节。

1.6.6 Currying

Use higher-order functions to convert a function that takes multiple arguments into a chain of functions that each take a single argument.

Example 1: manual currying

def curried_pow(x):
    def h(y):
        return pow(x, y)
    return h


def map_to_range(start, end, f):
    while start < end:
        print(f(start))
        start = start + 1


map_to_range(0, 10, curried_pow(2))

• curried_pow(x)(y) = pow(x, y)

Example 2: automate currying

def curry2(f):
    """Return a curried version of the given two-argument function."""
    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."""
    def f(x, y):
        return g(x)(y)
    return f


def map_to_range(start, end, f):
    while start < end:
        print(f(start))
        start = start + 1


pow_curried = curry2(pow)
map_to_range(0, 10, pow_curried(2))
uncurry2(pow_curried)(2, 5)

• curry2(f)(x)(y) = f(x, y)
• uncurry2(curry2(f)) = f

Question:

1. 什么情况下需要curry？为何不直接最外用多个形参？结合嵌套函数的参数传递方式理解curry的传参方式？
2. 结合env分析？

1.6.7 Lambda Expressions

A lambda expression evaluates to a function that has a single return expression as its body. Assignment and control statements are not allowed.

• 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: <function <lambda> at 0xf3f490>.

Example 1: compose with lambda expressions

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

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

result = f(12)

Env analysis

Example 2: compound lambda expressions

compose1 = lambda f,g: lambda x: f(g(x))

Question:

1. Example 1中结合env分析过程？
2. Example 2的理解？

1.6.8 Abstractions and First-Class Funcs

• Higher-order funcs can represent abstractions explicitly as elements so they can be handled like other computational elements.
• 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.

1.6.9 Func Decorators

Python provides special syntax to apply higher-order functions as part of executing a def statement, called a decorator.

Example 1: trace

def trace(fn):
    def wrapped(x):
        print('-> ', fn, '(', x, ')')
        return fn(x)
    return wrapped

@trace  # or triple = trace(triple)
def triple(x):
    return 3 * x

triple(12)

• A higher-order function trace returns a function that precedes a call to its argument with a print statement that outputs the argument.
• With @trace, name triple is bound to the returned function value of calling ~trace~ on the newly defined ~triple~ function: trace(triple(12)).

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.

Question:

1. Extra for experts的理解？decorator用在什么地方？用内存去追踪程序吗？

1.7 Recursive Funcs

A function is called recursive if the body of the function calls the function itself, either directly or indirectly.

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

Two steps:

• Summing all but the last digit: sum_digits(all_but_last).
• Adding the last digit: sum_digits(all_but_last) + last.

Env analysis:

1.7.1 The Anatomy of Recursive Functions

Base cases + recursive calls: to express computation by simplifying problems incrementally.

Example: Recursion vs Iteration

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

def fact(n):
    if n == 1:
        return 1
    else:
        return n * fact(n-1)

Env analysis(only recursion)

Differences

Recursive functions leverage the rules of evaluating call expressions to bind names to values, often avoiding the nuisance of correctly assigning local names during iteration.

Computation cases

• Recursion

final to base: complicate to simple.

• Iteration

final to base or base to final: identical.

Name and frame numbers:

• Recursion

less names(usually one) but more frames: bind different values to less names in different frames to track to characterize computation state and return values from all frames one by one(base to final).

• Iteration

more names but less frames(usually one): explicitly track some names to characterize computation state and return other names once in less frames.

Correctness varification:

• Recursion

trust simpler cases and only check final: treat recursive calls(simpler cases) as functional abstraction, a form of proof by induction.

• Iteration

Question:

1. 怎么检查iteration的正确?检查base开头和final结尾并trust中间过程？

1.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.

Example: even or odd for non-negative integers

• a number is even if it is one more than an odd number
• a number is odd if it is one more than an even number
• 0 is even

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)

Env analysis

Multually recursive to single recursive

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

def is_even(n):
    if n == 0:
        return True
    else:
        if (n-1) == 0:
            return False
        else:
            return is_even((n-1)-1)

• put base cases together and pass next updated para to the remaining func.
• mutual recursion provides a mechanism for maintaining abstraction within a complicated(single) recursive program.

Question:

1. 怎么理解 breaking the abstraction boundary ？是不是就是 put base cases together ？

1.7.3 Printing in Recursive Functions

Using calls to print to visualize the computational process evolved by a recursive function

Example: cascade to print all prefixes of a number from largest to smallest to largest.

def cascade(n):
    """Print a cascade of prefixes of n."""
    if n < 10:
        print(n)
    else:
        print(n)
        cascade(n//10)
        print(n)
    """simplify"""
    print(n)
    if n >= 10:
        cascade(n//10)
        print(n)

Example: multual recursion for two-player game

def play_alice(n):
    if n == 0:
        print("Bob wins!")
    else:
        play_bob(n-1)
    
def play_bob(n):
    if n == 0:
        print("Alice wins!")
    elif is_even(n):
        play_alice(n-2)
    else:
        play_alice(n-1)

• A natural decomposition: encapsulating each strategy in its own func
  • Modifying one strategy without affecting the other, maintaining the abstraction barrier between the two.
• Turn-by-turn: these two funcs call each other at the end of each turn.

1.7.4 Tree Recursion

Tree Recursive: A func with multiple recursive calls

def fib(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    else:
        return fib(n-2) + fib(n-1)

result = fib(6)

• As for Fibonacci, iterative is more efficient than recursive.

1.7.5 Example: Partitions

The number of partitions of a positive integer n, using parts up to size m, is the number of ways in which n can be expressed as the sum of positive integer parts up to m in increasing order.

• Strategy: the number of ways to partition n using integers up to m equals
  1. the number of ways to partition n-m using integers up to m, and
  2. the number of ways to partition n using integers up to m-1

def count_partitions(n, m):
    """Count the ways to partition n using parts up to m."""
    if n == 0:
        return 1
    elif n < 0:
        return 0
    elif m == 0:
        return 0
    else:
        return count_partitions(n-m, m) + count_partitions(n, m-1)

• Recursively reducing the problem of partitioning n using integers up to m into two simpler problems:
  1. partition a smaller number n-m
  2. partition with smaller components up to m-1
• Base cases:
  1. There is one way to partition 0: include no parts.
  2. There are 0 ways to partition a negative n.
  3. There are 0 ways to partition any n greater than 0 using parts of size 0 or less.
• Thinking of a tree-recursive func as exploring different possibilities: using a part of size m and not m in this case

Question:

1. 从数学上怎么解决上面的拆数问题？递归&非递归思路？
2. 怎么理解上面的递归思路？包括base cases的确定？
3. 怎么用非递归方法实现代码?

Chapter 2: Building Abstractions with Data

2.1 Introduction

2.1.1 Native Data Types

Native data types’ properties:

1. There are expressions that evaluate to values of native types, called literals.
2. There are built-in functions and operators to manipulate values of native types.

Native numeric types:

1. int for integers
2. float for real numbers (approximation)
   1. there are minimum and maximum values
   2. only a finite amount of precision
   3. dividing one int by another yields a float value
   4. combining float values can lead to approximation errors: 7 / 3 * 3 => 7.0; 1 / 3 * 7 * 3 => 6.999999999999999
   5. Problems with this approximation appear when conducting equality tests: 1/3 == 0.333333333333333312345 => True
3. complex for complex numbers

Non-numeric types

Values can represent many other types of data, such as sounds, images, locations, web addresses, network connections, and more.

• A few are represented by native data types, such as the bool class for values True and False
• The type for most values must be defined by programmers using the means of combination and abstraction

2.2 Data Abstraction

1. The general technique of isolating
   • the parts of a program that deal with how data are represented from
   • the parts that deal with how data are manipulated
2. func vs data abstraction
   • func abstraction: make an abstraction that separates the way the function is used from the details of how the function is implemented
   • data abstraction: make an abstraction that isolates how a compound data value is used from the details of how it is constructed
3. basic idea of data abstraction: structure programs as two parts which are connected by a small set of funcs that implement abstract data in terms of the concrete representation
   1. the part that operates on abstract data
   2. the part that defines a concrete representation

2.2.1 Example: Rational Numbers

Rational numbers: <numerator>/<denominator>

wishful thinking assumptions before defining:

• rational(n, d) returns the rational number with numerator n and denominator d.
• numer(x) returns the numerator of the rational number x.
• denom(x) returns the denominator of the rational number x.
• operations on rational nums:

  def add_rationals(x, y):
      nx, dx = numer(x), denom(x)
      ny, dy = numer(y), denom(y)
      return rational(nx * dy + ny * dx, dx * dy)
  
  def mul_rationals(x, y):
      return rational(numer(x) * numer(y), denom(x) * denom(y))
  
  def print_rational(x):
      print(numer(x), '/', denom(x))
  
  def rationals_are_equal(x, y):
      return numer(x) * denom(y) == numer(y) * denom(x)
      

2.2.2 Pairs

Compound structure list

def rational(n, d):
    return [n, d]

def numer(x):
    return x[0]

def denom(x):
    return x[1]

Reduce rational nums constructed above to lowest terms

changing the constructor rational() without changing any of the functions that implement the actual arithmetic operations

from fractions import gcd
def rational(n, d):
    g = gcd(n, d)
    return (n//g, d//g)

2.2.3 Abstraction Barriers

• General underlying idea of data abstraction:
  1. identify a basic set of operations in terms of which all manipulations of values of some kind will be expressed
  2. then to use only those operations in manipulating the data

  By restricting the use of operations in this way, it is much easier to change the representation of abstract data without changing the behavior of a program.

• An abstraction barrier is a rule that funcs should be called by a higher level and implemented using a lower level of abstraction instead of called directly by a lower level of abstraction when possible.
  • Abstraction barrier violation example: computing the square of a rational num
    • Implemented by mul_rational

      def square_rational(x):
          return mul_rational(x, x)
                  

    • Referring directly to numerators and denominators would violate one abstraction barrier

      def square_rational_violating_once(x):
          return rational(numer(x) * numer(x), denom(x) * denom(x))
                  

    • Assuming that rationals are represented as two-element lists would violate two abstraction barriers

      def square_rational_violating_twice(x):
          return [x[0] * x[0], x[1] * x[1]]
                  

  • Abstraction barriers make programs easier to maintain and to modify The fewer functions that depend on a particular representation, the fewer changes are required when one wants to change that representation
    • square_rational doesn’t require updating even if the representation of rational nums changed
    • square_rational_violating_once require updating whenever the selector or constructor signatures changed
    • square_rational_violating_twice require updating whenever the implementation of rational numbers changed

2.2.4 The Properties of Data

As long as behavior conditions are met (no matter how implementation details below an abstraction barrier changes) $⇒$ selectors and constructors can constitute and remain a valid representation of abstract data

• Example: functional representation for rational nums
  • “pair” behavior condition: If a pair p was constructed from values x and y, then select(p, 0) returns x, and select(p, 1) returns y
  • implement two functions pair and select that met behavior condition above

    def pair(x, y):
        """Return a function that represents a pair."""
        def get(index):
            if index == 0:
                return x
            elif index == 1:
                return y
        return get
    
    def select(p, i):
        """Return the element at index i of pair p."""
        return p(i)
            

  • Functional representations are sufficient but obscure to represent compound data (“pair” here)
• The practice of data abstraction allows switching among representations easily.

2.3 Sequences

A sequence is an ordered collection of values. Sequences are instances of a collection of behaviors that are shared among several different types of data. In particular,

• Length - A sequence has a finite length. An empty sequence has length 0.
• Element selection - A sequence has an element corresponding to any non-negative integer index less than its length, starting at 0 for the first element

2.3.1 Lists

• len and element seletion

  digits = [1, 8, 2, 8]
  len(digits)
  4
  digits[3]
  8
      

• Addition and multiplication

  [2, 7] + digits * 2
  [2, 7, 1, 8, 2, 8, 1, 8, 2, 8]
      

• Lists can be included in a list

  pairs = [[10, 20], [30, 40]]
  pairs[1]
  [30, 40]
  pairs[1][0]
  30
      

2.3.2 Sequence Iteration

• for statement

  for <name> in <expression>:
      <suite>
      

  • <expression> refers to iterable values. Lists are a type of sequence, and sequences are iterable values
  • The for loop introduces yet another way in which the environment can be updated by a statement
• Sequence unpacking A for statement may include multiple names in its header to “unpack” each element sequence into its respective elements

  pairs = [[1, 2], [2, 2], [2, 3], [4, 4]]
  same_count = 0
  for x, y in pairs:
          if x == y:
              same_count = same_count + 1
  
  same_count
  2
      

• Ranges A range is another built-in type of sequence in Python, which represents a range of integers

  list(range(5, 8))
  [5, 6, 7]
  list(range(4))
  [0, 1, 2, 3]
      

  • Ranges commonly appear as the expression in a for header to specify the number of times that the suite should be executed

    for _ in range(3):
        print('Go Bears!')
    
    Go Bears!
    Go Bears!
    Go Bears!
            

    • A common convention among programmers: using _ for the name in the for header if the name is unused in the suite

2.3.3 Sequence Processing

• Common patterns in sequence processing
  • List Comprehensions: Evaluating a fixed expression for each element in a sequence and collecting the resulting values in a result sequence

    odds = [1, 3, 5, 7, 9]
    [x+1 for x in odds]
    [2, 4, 6, 8, 10]
            

  • Selecting a subset of values that satisfy some condition

    [x for x in odds if 25 % x == 0]
    [1, 5]
            

    • General form [<map expression> for <name> in <sequence expression> if <filter expression>]
      • <sequence expression> must return an iterable value
      • Values of the map expression are collected into a list
  • Aggregation: aggregating all values in a sequence into a single value
    • Divisors

      def divisors(n):
          return [1] + [x for x in range(2, n) if n % x == 0]
       divisors(4)
      [1, 2]
       divisors(12)
      [1, 2, 3, 4, 6]
                  

    • Perfect numbers

      [n for n in range(1, 1000) if sum(divisors(n)) == n]
      [6, 28, 496]
                  

    • Given a rectangle’s area, finding the minimum premeter of it with integer side lengths

      def width(area, height):
          assert area % height == 0
          return area // height
       def perimeter(width, height):
          return 2 * width + 2 * height
       def minimum_perimeter(area):
          heights = divisors(area)
          perimeters = [perimeter(width(area, h), h) for h in heights]
          return min(perimeters)
       area = 80
      width(area, 5)
      16
      perimeter(16, 5)
      42
      perimeter(10, 8)
      36
      minimum_perimeter(area)
      36
      [minimum_perimeter(n) for n in range(1, 10)]
      [4, 6, 8, 8, 12, 10, 16, 12, 12]
                  

      • heights = divisors(area) and perimeters = [perimeter(width(area, h), h) for h in heights] return lists
• Using Higher-Order Function
  • Evaluating an expression for each element (List Comprehensions)

    def apply_to_all(map_fn, s):
        return [map_fn(x) for x in s]
            

  • Selecting only elements for which some expression is true

    def keep_if(filter_fn, s):
        return [x for x in s if filter_fn(x)]
            

  • Repeatedly applying a two-argument function to the reduced value so far and each element (Aggregation)

    def reduce(reduce_fn, s, initial):
        reduced = initial
        for x in s:
            reduced = reduce_fn(reduced, x)
        return reduced
            

    • Multiplying together all elements of a sequence

      reduce(mul, [2, 4, 8], 1)
      64
                  

    • Perfect num

      def divisors_of(n):
          divides_n = lambda x: n % x == 0
          return [1] + keep_if(divides_n, range(2, n))
      
      divisors_of(12)
      [1, 2, 3, 4, 6]
      
      from operator import add
      def sum_of_divisors(n):
          return reduce(add, divisors_of(n), 0)
      
      def perfect(n):
          return sum_of_divisors(n) == n
      
      keep_if(perfect, range(1, 1000))
      [1, 6, 28, 496]
                  

• Conventional Names
  • map for apply_to_all and filter for keep_if In Python, the built-in map and filter are generalizations of these functions that do not return lists.

    apply_to_all = lambda map_fn, s: list(map(map_fn, s))
    keep_if = lambda filter_fn, s: list(filter(filter_fn, s))
            

  • The reduce function is built into the functools module of the Python standard library

    from functools import reduce
    from operator import mul
    def product(s):
        return reduce(mul, s)
    
    product([1, 2, 3, 4, 5])
    120
            

2.3.4 Sequence Abstraction

Two native data types that satisfy the sequence abstraction: lists and ranges

• Length and element selection: length and []
• Membership: in and not in

  digits
  [1, 8, 2, 8]
  2 in digits
  True
  1828 not in digits
  True
      

• Slicing: [:]

  digits[0:2]
  [1, 8]
  digits[1:]
  [8, 2, 8]
  digits[:2]
  [1,8]
      

2.3.5 Strings

• Length and element selection

  city = 'Berkeley'
  len(city)
  8
  city[3]
  'k'
      

  • Python does not have a separate character type
• Addition and multiplication

  'Berkeley' + ', CA'
  'Berkeley, CA'
  'Shabu ' * 2
  'Shabu Shabu '
      

• Membership

  'here' in "Where's Waldo?"
  True
      

  • The string abstraction does not conform to the full sequence abstraction that we described for lists and ranges, in in String matches substrings rather than elements
• Multiline Literals

  """The Zen of Python
  claims, Readability counts.
  Read more: import this."""
  'The Zen of Python\nclaims, "Readability counts."\nRead more: import this.'
      

  • \n is a single element that represents a new line, len('\n')=1 and '\n'[0]='\n'
• String Coercion A string can be created from any object in Python by calling the str constructor function with an object value as its argument

  str(2) + ' is an element of ' + str(digits)
  '2 is an element of [1, 8, 2, 8]'
      

2.3.6 Trees

Closure property of a method: result of a combination method can itself be combined using the same method -> hierarchical structure

one_two = [1, 2]
nested = [[1, 2], [],
          [[3, False, None],
           [4, lambda: 5]]]

Nesting lists within lists can introduce complexity -> tree The tree is a fundamental data abstraction that imposes regularity on how hierarchical values are structured and manipulated, it consists of the constructor tree and the selectors label and branches

def tree(root_label, branches=[]):
    for branch in branches:
        assert is_tree(branch), 'branches must be trees'
    return [root_label] + list(branches)

def label(tree):
    return tree[0]

def branches(tree):
    return tree[1:]

def is_tree(tree):
    if type(tree) != list or len(tree) < 1:
        return False
    for branch in branches(tree):
        if not is_tree(branch):
            return False
    return True

def is_leaf(tree):
    return not branches(tree)

t = tree(3, [tree(1), tree(2, [tree(1), tree(1)])])
t
[3, [1], [2, [1], [1]]]
label(t)
3
branches(t)
[[1], [2, [1], [1]]]
label(branches(t)[1])
2
is_leaf(t)
False
is_leaf(branches(t)[0])
True

• Tree-recursive func
  • Constructing trees

    def fib_tree(n):
            if n == 0 or n == 1:
                return tree(n)
            else:
                left, right = fib_tree(n-2), fib_tree(n-1)
                fib_n = label(left) + label(right)
                return tree(fib_n, [left, right])
    fib_tree(5)
    [5, [2, [1], [1, [0], [1]]], [3, [1, [0], [1]], [2, [1], [1, [0], [1]]]]]
            

    • fib_tree(n) illustrates the tree-recursive computation of a Fibonacci number
  • Processing trees <<1>>

    def count_leaves(tree):
          if is_leaf(tree):
              return 1
          else:
              branch_counts = [count_leaves(b) for b in branches(tree)]
              return branch_counts
              # return sum(branch_counts)
    count_leaves(fib_tree(5))
    8
            

    • branch_counts for fib_tree(5) = [[1, [1, 1]], [[1, 1], [1, [1, 1]]]]
  • Partition trees <<2>> A partition tree for n using parts up to size m is a binary (two branch) tree that represents the choices taken during computation.
    • Representing the partitions of an integer

      def partition_tree(n, m):
              """Return a partition tree of n using parts of up to m."""
              if n == 0:
                  return tree(True)
              elif n < 0 or m == 0:
                  return tree(False)
              else:
                  left = partition_tree(n-m, m)
                  right = partition_tree(n, m-1)
                  return tree(m, [left, right])
      
      partition_tree(2, 2)
      [2, [True], [1, [1, [True], [False]], [False]]]
                  

      • Non-leaf partition tree:
        • the left (index 0) branch contains all ways of partitioning n using at least one m: left = partition_tree(n-m, m)
        • the right (index 1) branch contains partitions using parts up to m-1: right = partition_tree(n, m-1)
        • the root label is m
      • The labels at the leaves of a partition tree express whether the path from the root of the tree to the leaf represents a successful partition of n
    • Printing the partitions from a partition Another tree-recursive process that traverses the tree, constructing each partition as a list. Whenever a True leaf is reached, the partition is printed.

      def print_parts(tree, partition=[]):
              if is_leaf(tree):
                  if label(tree):
                      print(' + '.join(partition))
              else:
                  left, right = branches(tree)
                  m = str(label(tree))
                  print_parts(left, partition + [m])
                  print_parts(right, partition)
      
      print_parts(partition_tree(6, 4))
      4 + 2
      4 + 1 + 1
      3 + 3
      3 + 2 + 1
      3 + 1 + 1 + 1
      2 + 2 + 2
      2 + 2 + 1 + 1
      2 + 1 + 1 + 1 + 1
      1 + 1 + 1 + 1 + 1 + 1
                  

      • str.join(sequence): '+'.join[1,2,3,4] returns 1+2+3+4
  • Slicing on branches <<3>> A common tree transformation called binarization finds a binarized tree with the same labels as an original tree by grouping together branches.

    def right_binarize(t):
        """Construct a right-branching binary tree."""
        return tree(label(t), binarize_branches(branches(t)))
    
    def binarize_branches(bs):
        """Binarize a list of branches."""
        if len(bs) > 2:
            first, rest = bs[0], bs[1:]
            return [right_binarize(first), binarize_branches(rest)]
        else:
            return [right_binarize(b) for b in bs]
    
    right_binarize(tree(0, [tree(x) for x in [1, 2, 3, 4, 5, 6, 7]]))
    [0, [1], [[2], [[3], [[4], [[5], [[6], [7]]]]]]]
            

    • right_binarize to construct a right-branching binary tree
    • binarize_branches to binarize a list of branches

Question:

1. 进一步理解 1 2 3 的代码，特别是最后两点，对树结构递归的深刻理解？补充代码解释
2. is_tree 中 len(tree) < 1 能否用 not tree 替换？即均指 tree 为空

2.3.7 Linked Lists

A linked list is a pair containing the first element of the sequence and the rest of the sequence. The second element is also a linked list

• Recursive structure for linked lists: the rest of a linked list is a linked list or ‘empty’

  empty = 'empty'
  def is_link(s):
      """s is a linked list if it is empty or a (first, rest) pair."""
      return s == empty or (len(s) == 2 and is_link(s[1]))
    
  def link(first, rest):
      """Construct a linked list from its first element and the rest."""
      assert is_link(rest), "rest must be a linked list."
      return [first, rest]
    
  def first(s):
      """Return the first element of a linked list s."""
      assert is_link(s), "first only applies to linked lists."
      assert s != empty, "empty linked list has no first element."
      return s[0]
    
  def rest(s):
      """Return the rest of the elements of a linked list s."""
      assert is_link(s), "rest only applies to linked lists."
      assert s != empty, "empty linked list has no rest."
      return s[1]
    
  four = link(1, link(2, link(3, link(4, empty))))
  first(four)
  1
  rest(four)
  [2, [3, [4, 'empty']]]
      

  • Implementation of abstract data above uses pairs that are two-element list values
  • Pairs can also be implemented using function -> function can also implement linked list alone
• Iterative length and element selections

  def len_link(s):
      """Return the length of linked list s."""
      length = 0
      while s != empty:
          s, length = rest(s), length + 1
      return length
  
  def getitem_link(s, i):
      """Return the element at index i of linked list s."""
      while i > 0:
          s, i = rest(s), i - 1
      return first(s)
  
  four = [1, [2, [3, [4, 'empty']]]]
  len_link(four)
  4
  getitem_link(four, 1)
  2
      

  

• Recursive manipulation
  • Length and element selections

    def len_link_recursive(s):
        """Return the length of a linked list s."""
        if s == empty:
            return 0
        return 1 + len_link_recursive(rest(s))
      
    def getitem_link_recursive(s, i):
        """Return the element at index i of linked list s."""
        if i == 0:
            return first(s)
        return getitem_link_recursive(rest(s), i - 1)
      
    len_link_recursive(four)
    4
    getitem_link_recursive(four, 1)
    2
            

    • Methods above can manipulate a linked list as a sequence (still can not use the built-in len function, element selection syntax, or for statement)
    • Incremental methods above for take some time to compute, unlike built-in length and selection methods for Python sequences, which does not have a large cost for computing
  • Transforming and combining linked lists <<4>>

    def apply_to_all_link(f, s):
        """Apply f to each element of s."""
        assert is_link(s)
        if s == empty:
            return s
        else:
            return link(f(first(s)), apply_to_all_link(f, rest(s)))
    
    apply_to_all_link(lambda x: x*x, four)
    [1, [4, [9, [16, 'empty']]]]
    
    def keep_if_link(f, s): #<<13>>
        """Return a list with elements of s for which f(e) is true."""
        assert is_link(s)
        if s == empty:
            return s
        else:
            kept = keep_if_link(f, rest(s))
            if f(first(s)):
                return link(first(s), kept)
            else:
                return kept
    
    keep_if_link(lambda x: x%2 == 0, four)
    [2, [4, 'empty']]
    
    def join_link(s, separator):
        """Return a string of all elements in s separated by separator."""
        if s == empty:
            return ""
        elif rest(s) == empty:
            return str(first(s))
        else:
            return str(first(s)) + separator + join_link(rest(s), separator)
    
    join_link(four, ", ")
    '1, 2, 3, 4'
            

  • Construction <<5>>

    def partitions(n, m):
        """Return a linked list of partitions of n using parts of up to m.
        Each partition is represented as a linked list.
        """
        if n == 0:
            return link(empty, empty) # A list containing the empty partition
        elif n < 0 or m == 0:
            return empty
        else:
            using_m = partitions(n-m, m)
            with_m = apply_to_all_link(lambda s: link(m, s), using_m)
            without_m = partitions(n, m-1)
            return extend_link(with_m, without_m)
    
    def print_partitions(n, m):
        lists = partitions(n, m)
        strings = apply_to_all_link(lambda s: join_link(s, " + "), lists)
        print(join_link(strings, "\n"))
    
    print_partitions(6, 4)
    4 + 2
    4 + 1 + 1
    3 + 3
    3 + 2 + 1
    3 + 1 + 1 + 1
    2 + 2 + 2
    2 + 2 + 1 + 1
    2 + 1 + 1 + 1 + 1
    1 + 1 + 1 + 1 + 1 + 1
            

Question:

1. linked list与sequence的有区别吗？为什么一直强调linked list不能用sequence的内置函数？linked list不还是个list，不还是属于sequence吗？
2. 4 5 代码理解，特别是 5，构造了什么sequence？为什么要构造成这样？联系之前的tree partition比较异同？

2.4 Mutable Data

2.4.1 The Object Metaphor

All values in Python are objects, they all have behavior and attibutes

from datetime import date
tues = date(2014, 5, 13)
print(date(2014, 5, 19) - tues)
6 days, 0:00:00

tues.year
2014

tues.strftime('%A, %B %d')
'Tuesday, May 13'

'1234'.isnumeric()
True
'rOBERT dE nIRO'.swapcase()
'Robert De Niro'
'eyes'.upper().endswith('YES')
True

2.4.2 Sequence Objects

Imutable objects are used to represent values that themselves cannot change over the course of program execution. Instances of primitive built-in values such as numbers are immutable. Mutable objects are used to represent values that change over time due to mutating operations. Lists are mutable

• Sharing and Identity
  • Changing rather than creating

    chinese = ['coin', 'string', 'myriad']  # A list literal
    suits = chinese                         # Two names refer to the same list
    suits.pop()             # Remove and return the final element
    'myriad'
    suits.remove('string')  # Remove the first element that equals the argument
    suits.append('cup')              # Add an element to the end
    suits.extend(['sword', 'club'])  # Add all elements of a sequence to the end
    suits[2] = 'spade'  # Replace an element
    suits
    ['coin', 'cup', 'spade', 'club']
    suits[0:2] = ['heart', 'diamond']  # Replace a slice
    suits
    ['heart', 'diamond', 'spade', 'club']
    chinese  # This name co-refers with "suits" to the same changing list
    ['heart', 'diamond', 'spade', 'club']
            

    

    • = do not create a new list
  • Changes to one list do not affect another, unless they share structure

    nest = list(suits)  # Bind "nest" to a second list with the same elements
    nest[0] = suits     # Create a nested list
    suits.insert(2, 'Joker')  # Insert an element at index 2, shifting the rest
    nest
    [['heart', 'diamond', 'Joker', 'spade', 'club'], 'diamond', 'spade', 'club']
    joke = nest[0].pop(2)
    joke
    'Joker'
    suits
    ['heart', 'diamond', 'spade', 'club']
            

    

    • list constructor func to create a new list
    • Two different lists can affect each other if they share structure
  • is, is not and ==

    suits is nest[0]
    True
    suits is ['heart', 'diamond', 'spade', 'club']
    False
    suits == ['heart', 'diamond', 'spade', 'club']
    True
            

    • is and is not check for identity
    • == checks for the equality of contents not identity
• List Manipulation
  • Slicing
    • Slicing a list creates a new list and leaves the original list unchanged

      a = [11, 12, 13]
      b = a[1:]
      b[1] = 15
                  

      

    • Mutating a list within a sliced list will affect the original list <<6>>

      a = [11, [12, 13], 14]
      b = a[:]
      b[1][1] = 15
                  

      

      • Slice copies the contents of a list but not the values contained within the list. Instead, a new list is constructed that contains a subset of the same values as the sliced list.
      • The built-in list function creates a new list that contains the values of its argument, which must be an iterable value such as a sequence. Again, the values placed in this list are not copied. list(s) = s[:] for a list s
  • +, append, extend
    • + Adding two lists together creates a new list that contains the values of the first list, followed by the values in the second list

      a = [[11], 12]
      b = [13, 14]
      c = a + b
      d = b + a
      a[0][0] = 15
      b[0] = 16
                  

      

      • In lists, a + b != b + a
    • append The append method of a list takes one value as an argument and adds it as a whole item to the end of the list

      a = [1, [2, 3]]
      b = [4, [5, 6]]
      c = 7
      a.append(b)
      a.append(c)
      b.append(c)
      d = a.append(a)
                  

      

      • Argument can be any value
      • Always returns None
      • Mutating the list by increasing its length by one
    • extend The extend method of a list takes an iterable value as an argument and adds each of its elements to the end of the list

      a = [1, 2]
      b = [1, 2]
      c = [1, 2]
      d = [3, [4]]
      a.extend(d)
      b += d
      c.append(d)
                  

      

      • Mutating the list by increasing its length by the length of the iterable argument
      • x += y for a list x and iterable y = x.extend(y)
      • TypeError if not iterable
      • Not return anything
  • pop, remove, index, insert, count
    • pop

      a = [0, 1, [2, 3], 4]
      b = a.pop(2)
      c = a.pop()
                  

      

      • Mutating the list by reducing its length by one
      • IndexError for an empty list
    • remove The remove method takes one argument that must be equal to a value in the list.

      a = [10, 11, 10, 12, [13, 14]]
      a.remove([13, 14])
      a.remove(10)
                  

      

      • Removes the first equal item
      • ValueError for no equal items
    • index The index method takes one argument that must be equal to a value in the list

      >>> a = [13, 14, 13, 12, [13, 14], 15]
      >>> a.index([13, 14])
      4
      >>> a.index(13)
      0
                  

      • Returns the index for the first equal item
      • ValueError for no equal items
    • insert The insert method takes two arguments: an index and a value to be inserted

      a = [0, 1, 2]
      a.insert(0, [3, 4])
      a.insert(2, 5)
      a.insert(5, 6)
                  

      

      • Mutating by increasing size by one
      • Returns None
    • count The count method of a list takes in an item as an argument and returns how many times an equal item apears in the list.

      a = [1, [2, 3], 1, [4, 5]]
      a.count([2, 3])
      1
      a.count(1)
      2
      a.count(5)
      0
                  

      • Returns 0 for no equal items
• List comprehensions A list comprehension always creates a new list

  from unicodedata import lookup
  [lookup('WHITE ' + s.upper() + ' SUIT') for s in suits]
  ['♡', '♢', '♤', '♧']
      

  • Not share structure with suits -> list comprehension evaluation won’t modify the suits
• Tuples A tuple, an instance of the built-in tuple type, is an immutable sequence.

  1, 2 + 3
  (1, 5)
  ("the", 1, ("and", "only"))
  ('the', 1, ('and', 'only'))
  type( (10, 20) )
  <class 'tuple'>
  
  ()    # 0 elements
  ()
  (10,) # 1 element
  (10,)
  
  code = ("up", "up", "down", "down") + ("left", "right") * 2
  len(code)
  8
  code[3]
  'down'
  code.count("down")
  2
  code.index("left")
  4
  
  nest = (10, 20, [30, 40])
  nest[2].pop()
      

  • Any objects can be placed within tuples.
  • Empty and one-element tuples have special literal syntax: (), (a,)
  • Mutating operations are not available
  • Not possible to change which elements are in a tuple, while possible to change the value of a mutable element contained within a tuple

    

  • Tuples are used implicitly in multiple assignment (a,b = 1,2) . An assignment of two values to two names creates a two-element tuple and then unpacks it.

Question:

1. 6 中关于 slice 和 list ，啥叫list is copied but the values are not？？？contens 和 values有毛区别？上面关于values are not copied在扯犊子？

2.4.3 Dictionaries

A dictionary contains key-value pairs, where both the keys and values are objects. The purpose of a dictionary is to provide an abstraction for storing and retrieving values that are indexed not by consecutive integers, but by descriptive keys.

• Since Python 3.6, dicts’ contents will be ordered by insertion

  numerals = {'I': 1.0, 'V': 5, 'X': 10}
  numerals['X']
  10
  
  numerals['I'] = 1
  numerals['L'] = 50
  numerals
  {'I': 1, 'X': 10, 'V': 5, 'L': 50}
      

• The dictionary type also supports various methods of iterating over the contents of the dictionary as a whole. The methods keys, values, and items all return iterable values.

  numerals.keys()
  dict_keys(['I', 'X', 'V', 'L'])
  numerals.values()
  dict_values([1, 10, 5, 50])
  sum(numerals.values())
  66
  numerals.items()
  dict_items([('I', 1), ('X', 10), ('V', 5), ('L', 50)])
      

• A list of key-value pairs can be converted into a dictionary by calling dict

  dict([(3, 9), (4, 16), (5, 25)])
  {3: 9, 4: 16, 5: 25}
      

• Two restrictions of dictionaries
  • A key of a dictionary cannot be or contain a mutable value.
  • There can be at most one value for a given key.
• The arguments to get are the key and the default value

  numerals.get('A', 0)
  0
  numerals.get('V', 0)
  5
      

• Dictionaries have a comprehension syntax analogous to those of lists

  {x: x*x for x in range(3,6)}
  {3: 9, 4: 16, 5: 25}
      

2.4.4 Local State

Lists and dictionaries have local state: they are changing values that have some particular contents at any point in the execution of a program. Functions can also have local state.

def make_withdraw(balance):
    """Return a withdraw function that draws down balance with each call."""
    def withdraw(amount):
        nonlocal balance                 # Declare the name "balance" nonlocal
        if amount > balance:
            return 'Insufficient funds'
        balance = balance - amount       # Re-bind the existing balance name
        return balance
    return withdraw

wd = make_withdraw(20)
wd(5)
wd(3)

• withdraw is non-pure.
• The name balance is bound in the parent frame of f2 - f1
• Without nonlocal statement, an assignment statement would always bind a name in the first frame of the current environment
• The nonlocal statement indicates that the name appears somewhere in the environment other than the first (local) frame or the last (global) frame.
• Python Particulars
  • non-local assignment: No nonlocal statement is required to access a non-local name, but need nonlocal for assignment statements to change in funcs (non-local assignment is often the default behavior of assignment statements for most other languages)
  • Lookup of names: within the body of a function, all instances of a name must refer to the same frame

    def make_withdraw(balance):
        """Return a withdraw function that draws down balance with each call."""
        def withdraw(amount):
            if amount > balance:
                return 'Insufficient funds'
            balance = balance - amount       # Re-bind the existing balance name
            return balance
        return withdraw
            

    • This restriction allows Python to pre-compute which frame contains each name before executing the body of a function
    • Python cannot look up the value of a name in a non-local frame, then bind that same name in the local frame
    • UnboundLocalError: local variable 'balance' referenced before assignment: pre-compute in line 3 and line 6 finds balance in different frames
      • balance in line 4 belongs to non-local
      • balance - amount in line 6 belongs to non-local
      • balance = in line 6 assigned locally
• Error for nonlocal if not previously been bound
• Dual role of assignment statements: either creat new bindings or re-bound existing names

2.4.5 The Benefits of Non-Local Assignment

Non-local assignment has given us the ability to maintain some state that is local to a function, but evolves over successive calls to that function

def make_withdraw(balance):
    def withdraw(amount):
        nonlocal balance
        if amount > balance:
            return 'Insufficient funds'
        balance = balance - amount
        return balance
    return withdraw

wd = make_withdraw(20)
wd2 = make_withdraw(7)
wd2(6)
wd(8)

2.4.6 The Cost of Non-Local Assignment

• Only function calls can introduce new frames.
• Assignment statements always change bindings in existing frames
• Previously, values did not change; only names and bindings changed, while funcs with state do not behave this way
• An expression that contains only pure function calls is referentially transparent; its value does not change if we substitute one of its subexpression with the value of that subexpression
• Re-binding operations violate the conditions of referential transparency because they do more than return a value; they change the environment
• … reference the book

Question:

1. 这节讲了写啥。。。

2.4.7 Iterators

An iterator is an object that provides sequential access to values, one by one.

• Two components of iterator abstraction
  • A mechanism for retrieving the next element in the sequence being processed
  • A mechanism for signaling that the end of the sequence has been reached and no further elements remain
• iter to obtain an iterator and next to access the contents of the iterator for any container (list or range) or iterator

  primes = [2, 3, 5, 7]
  type(primes)
  <class 'list'>
  iterator = iter(primes)
  type(iterator)
  <class 'list_iterator'>
  next(iterator)
  2
  next(iterator)
  3
  next(iterator)
  5
  next(iterator)
  7
  next(iterator)
  Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
  StopIteration
      

  • StopIteration can be handled using a try statement
• An iterator maintains local state to represent its position in a sequence

  r = range(3, 13)
  s = iter(r)  # 1st iterator over r
  next(s)
  3
  next(s)
  4
  t = iter(r)  # 2nd iterator over r
  next(t)
  3
  next(t)
  4
  u = t        # Alternate name for the 2nd iterator
  next(u)
  5
  next(u)
  6
  next(s)
  5
  next(t)
  7
  
  v = iter(t)  # Another alterante name for the 2nd iterator
  next(v)
  8
  next(u)
  9
  next(t)
  10
      

  • Calling iter on an iterator will return that iterator, not a copy: v = iter(t) = v = t, v is just an alterante name of iterator t, not a copy
• Usefulness of iterators
  • Allowing for lazy generation of a much broader class of underlying sequential datasets, from existing to next
  • Underlying series of data for an iterator may not be represented explicitly in memory (all do not need to be stored simultaneously)

2.4.8 Iterables

Any value that can produce iterators is called an iterable value. In Python, an iterable value is anything that can be passed to the built-in iter function: sequence values such as strings and tuples, other containers such as sets and dictionaries, iterators

d = {'one': 1, 'two': 2, 'three': 3}
d
{'one': 1, 'three': 3, 'two': 2}
k = iter(d)
next(k)
'one'
next(k)
'three'
v = iter(d.values())
next(v)
1
next(v)
3

d.pop('two')
2
next(k)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: dictionary changed size during iteration

r = range(3, 6)
s = iter(r)
next(s)
3
for x in s:
    print(x)
4
5
list(s)
[]
for x in r:
    print(x)
3
4
5

• Python guarantees the order of iterators from dictionaries
• Changing the structure like adding or removing a key will invalidate all iterators, while changing the value of an existing key does not invalidate iterators or change the order of their contents.
• for can iterate over the contents of any iterable or iterator.

2.4.9 Built-in Iterators

Several built-in functions take as arguments iterable values and return iterators, extensively used for lazy sequence processing

• map is lazy

  def double_and_print(x):
      print('***', x, '=>', 2*x, '***')
      return 2*x
  s = range(3, 7)
  doubled = map(double_and_print, s)  # double_and_print not yet called
  next(doubled)                       # double_and_print called once
  *** 3 => 6 ***
  6
  next(doubled)                       # double_and_print called again
  *** 4 => 8 ***
  8
  list(doubled)                       # double_and_print called twice more
  *** 5 => 10 ***
  *** 6 => 12 ***
  [10, 12]
      

• filter returns an iterator over a subset of the values in another iterable
• zip returns an iterator over tuples of values that combine one value from each of multiple iterables.

2.4.10 Generators

A generator is an iterator returned by a special class of function called a generator function.

def letters_generator():
    current = 'a'
    while current <= 'd':
        yield current
        current = chr(ord(current)+1)

for letter in letters_generator():
    print(letter)
a
b
c
d

letters = letters_generator()
type(letters)
<class 'generator'>
next(letters)
'a'
next(letters)
'b'
next(letters)
'c'
next(letters)
'd'
next(letters)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

• yield indicates generator func
• The generator does not start executing any of the body statements of its generator function until the first time next is called
• Generators do not use attributes of an object to track their progress through a series. Instead, they control the execution of the generator function, which runs until the next yield statement is executed each time next is called on the generator.
• Calling next on the generator continues execution of the generator function from wherever it left off previously until another yield statement is executed.
• yield statements do not destroy the newly created environment, the values of current and of any other bound names in the scope of letters_generator are preserved across subsequent calls to next
• The generator raises a StopIteration exception whenever its generator function returns.

Question:

1. 以上能不能简化，不就是一个在 generator 上每次调用 next 就执行一次 generator func 中的 yield 语句吗
2. generator function 什么时候return啊？里面不是没有return吗？那 StopIteration 什么抛出呢？

2.4.11 Implementing Lists and Dictionaries

• Representing a mutable linked list by a function that has a linked list as its local state

  def mutable_link():
     """Return a functional implementation of a mutable linked list."""
     contents = empty
     def dispatch(message, value=None):
         nonlocal contents
         if message == 'len':
             return len_link(contents)
         elif message == 'getitem':
             return getitem_link(contents, value)
         elif message == 'push_first':
             contents = link(value, contents)
         elif message == 'pop_first':
             f = first(contents)
             contents = rest(contents)
             return f
         elif message == 'str':
             return join_link(contents, ", ")
     return dispatch
    
  def to_mutable_link(source):
      """Return a functional list with the same contents as source."""
      s = mutable_link()
      for element in reversed(source):
          s('push_first', element)
      return s
    
  s = to_mutable_link(suits)
  type(s)
  <class 'function'>
  print(s('str'))
  heart, diamond, spade, club
    
  s('pop_first')
  'heart'
  print(s('str'))
  diamond, spade, club
      

  • Lists need to have an identity, None can’t be used for empty mutable list, as None is None while two empty lists or funcs are not identical
  • Message passing: encapsulates the logic for all operations on a data value within one function (dispatch) that responds to different messages
  • A general pattern in programming: the function is a dispatch function and its arguments are first a message, followed by additional arguments to parameterize that method
  • to_mutable_link a convenience function to construct a functionally implemented linked list from any built-in sequence by adding each element in reverse order
  • reversed takes and returns an iterable value
  • The linked list s itself is a func <class 'function'>
• Implementing Dictionaries Using a list of key-value pairs to store the contents of the dictionary

  def dictionary():
      """Return a functional implementation of a dictionary."""
      records = []
      def getitem(key):
          matches = [r for r in records if r[0] == key]
          if len(matches) == 1:
              key, value = matches[0]
              return value
      def setitem(key, value):
          nonlocal records
          non_matches = [r for r in records if r[0] != key]
          records = non_matches + [[key, value]]
      def dispatch(message, key=None, value=None):
          if message == 'getitem':
              return getitem(key)
          elif message == 'setitem':
              setitem(key, value)
      return dispatch
    
  d = dictionary()
  d('setitem', 3, 9)
  d('setitem', 4, 16)
  d('getitem', 3)
  9
  d('getitem', 4)
  16
      

  • This implementation is not optimized for fast record lookup, the built-in dictionary type is considerably more efficient

2.4.12 Dispatch Dictionaries

Instead of using conditionals, use dictionaries with string keys to implement dispatching

def account(initial_balance):
    def deposit(amount):
        dispatch['balance'] += amount
        return dispatch['balance']
    def withdraw(amount):
        if amount > dispatch['balance']:
            return 'Insufficient funds'
        dispatch['balance'] -= amount
        return dispatch['balance']
    dispatch = {'deposit':   deposit,
                'withdraw':  withdraw,
                'balance':   initial_balance}
    return dispatch

def withdraw(account, amount):
    return account['withdraw'](amount)
def deposit(account, amount):
    return account['deposit'](amount)
def check_balance(account):
    return account['balance']

a = account(20)
deposit(a, 5)
withdraw(a, 17)
check_balance(a)

• The local state (balance) of the account is stored in the dictionary alongside the functions that implement its behavior.
  • withdraw and deposit defined in account have access to the dispatch dictionary to read and change the balance (local state) as dictionary is mutable
  • withdraw, deposit and check_balance are just helper funcs
  • Storing the balance in the dispatch dictionary (dictionary is mutable) rather than in the account frame directly to avoid the need for nonlocal statements in deposit and withdraw

Question:

1. 以上分析有何简化or补充的地方？关于 “dictionary is mutable 所以把 local state 以及操作它的 funcs 存放到 dictionary 里，因为这样可以缺省 nonlocal statement 而直接通过 funcs 访问改变 local state”的想法or说法对吗？更简化梳理清晰些？
2. local state 具体指什么？mutable data type 都有 local state ？不同的 mutable date type 的 local state 有何异同？（比如 lists dictionaries funcs）

2.4.13 Propagating Constraints <<8>>

• Intro
  • Expressing programs as constraints is a type of declarative programming, in which a programmer declares the structure of a problem to be solved, but abstracts away the details of exactly how the solution to the problem is computed.
  • Computer programs are traditionally organized as one-directional computations
  • A general model of linear relationships (not one-directional computations): defining primitive constraints that hold between quantities
  • Defining a means of combination, so that primitive constraints can be combined to express more complex relations
    • Constraints are combined by constructing a network in which constraints are joined by connectors
    • A connector is an object that “holds” a value and may participate in one or more constraints.
  • Example

    

    • Computation: set a value for a connector (by the user or by a constraint box to which it is linked) –> awakening all of its associated constraints –> Each awakened constraint box then polls its connectors and trys to set values for new connectors –> awakening all of new setted connectors’ constraints, and so on
• Using the Constraint System
  • Linking connectors into a network that mirrors the figure above

    celsius = connector('Celsius')
    fahrenheit = connector('Fahrenheit')
      
    def converter(c, f):
        """Connect c to f with constraints to convert from Celsius to Fahrenheit."""
        u, v, w, x, y = [connector() for _ in range(5)]
        multiplier(c, w, u)
        multiplier(v, x, u)
        adder(v, y, f)
        constant(w, 9)
        constant(x, 5)
        constant(y, 32)
      
    converter(celsius, fahrenheit)
            

    • Calling connector constructor to create celsius and fahrenheit connectors
    • converter assembles the various connectors and constraints in the network
  • Using a message passing system to coordinate constraints and connectors
    • Constraints are dictionaries that do not hold local states themselves. Their responses to messages are non-pure functions that change the connectors that they constrain.
    • Connectors are dictionaries that hold a current value and respond to messages that manipulate that value (map message names to function and data values)
    • Constraints will change the value of connectors by sending messages (instead of changing directly), so that the connector can notify other constraints in response to the change <<7>>
    • A connector represents a number, but also encapsulates connector behavior

    celsius['set_val']('user', 25)
    Celsius = 25
    Fahrenheit = 77.0
    
    fahrenheit['set_val']('user', 212)
    Contradiction detected: 77.0 vs 212
    
    celsius['forget']('user')
    Celsius is forgotten
    Fahrenheit is forgotten
    
    fahrenheit['set_val']('user', 212)
    Fahrenheit = 212
    Celsius = 100.0
            

    • celsius changed <–> propagating through the network <–> fahrenheit changed: This non-directionality of computation is the distinguishing feature of constraint-based systems.
    • 'user' means we
• Implementing the Constraint System
  • Three constraints: adder, multiplier, constant

    from operator import add, sub
    from operator import mul, truediv
    
    def adder(a, b, c):
        """The constraint that a + b = c."""
        return make_ternary_constraint(a, b, c, add, sub, sub)
    
    def multiplier(a, b, c):
        """The constraint that a * b = c."""
        return make_ternary_constraint(a, b, c, mul, truediv, truediv)
    
    def constant(connector, value):
        """The constraint that connector = value."""
        constraint = {}
        connector['set_val'](constraint, value)
        return constraint
            

  • Generic ternary (three-way) constraint Using the three connectors (a, b ,c) and three constraints (ab, ca, cb) to create a generic ternary constraint that accepts new_val and forget

    def make_ternary_constraint(a, b, c, ab, ca, cb):
        """The constraint that ab(a,b)=c and ca(c,a)=b and cb(c,b) = a."""
        def new_value():
            av, bv, cv = [connector['has_val']() for connector in (a, b, c)]
            if av and bv:
                c['set_val'](constraint, ab(a['val'], b['val']))
            elif av and cv:
                b['set_val'](constraint, ca(c['val'], a['val']))
            elif bv and cv:
                a['set_val'](constraint, cb(c['val'], b['val']))
        def forget_value():
            for connector in (a, b, c):
                connector['forget'](constraint)
        constraint = {'new_val': new_value, 'forget': forget_value}
        for connector in (a, b, c):
            connector['connect'](constraint)
        return constraint
            

    • Dictionariy constraint is a dispatch dictionary but also the constraint object itself
    • Constraint constraint passes itself as the source argument in calls to its connectors
• Representing connectors A connector is represented as a dictionary that contains a value, but also has response functions with local state. The connector must track the informant that gave it its current value, and a list of constraints in which it participates.

  def connector(name=None):
      """A connector between constraints."""
      informant = None
      constraints = []
      def set_value(source, value):
          nonlocal informant
          val = connector['val']
          if val is None:
              informant, connector['val'] = source, value
              if name is not None:
                  print(name, '=', value)
              inform_all_except(source, 'new_val', constraints)
          else:
              if val != value:
                  print('Contradiction detected:', val, 'vs', value)
      def forget_value(source):
          nonlocal informant
          if informant == source:
              informant, connector['val'] = None, None
              if name is not None:
                  print(name, 'is forgotten')
              inform_all_except(source, 'forget', constraints)
      connector = {'val': None,
                   'set_val': set_value,
                   'forget': forget_value,
                   'has_val': lambda: connector['val'] is not None,
                   'connect': lambda source: constraints.append(source)}
      return connector
  
  def inform_all_except(source, message, constraints):
      """Inform all constraints of the message, except source."""
      for c in constraints:
          if c != source:
              c[message]()
      

  • A connector is a dispatch dictionary for the five messages used by constraints to communicate with connectors
  • Only if informants == source (forget request is coming from the same constraint that set the value originally) will the connector forget its value and reset the informant
  • Constraints and connectors are both abstractions that are manipulated through messages.
  • When the value of a connector is changed, it is changed via a message that not only changes the value, but validates it (checking the source) and propagates its effects (informing other constraints)

Question:

1. 7 怎么理解？是 “connector 通知其他 constraints 来响应变化” 还是 “connector 响应变化并通知其他 constraints”？
2. 8 的进一步&全局理解并补充or简化笔记：
   1. 整体上connector、constrant、message具体是什么，共同工作通信机制？
   2. 什么是声明式编程的思想？用声明式编程的思想,使用dictionary dispatch、nonlocal、high-order func、func and data abstraction等来设计以上程序的思想？

2.5 Object-Oriented Programming

2.5.1 Objects and Classes

• Instantiating a class a = Account('Kirk')
• Instance attibutes . (fields, properties, or instance variables)

  a.holder
  'Kirk'
  a.balance
  0
      

• Methods

  a.deposit(15)
  15
  a.withdraw(10)  # The withdraw method returns the balance after withdrawal
  5
  a.balance       # The balance attribute has changed
  5
  a.withdraw(10)
  'Insufficient funds'
      

2.5.2 Defining Classes

A class statement defines the class name, then includes a suite of statements to define the attributes of the class

class <name>:
    <suite>

• Constructor for class __init__

  class Account:
      def __init__(self, account_holder):
          self.balance = 0
          self.holder = account_holder
      

  • self is bound to the newly created object
• Identity

  b = Account('Spock')
  b.balance = 200
  [acc.balance for acc in (a, b)]
  [0, 200]
  
  a is a
  True
  a is not b
  True
  
  c = a
  c is a
  True
      

  • Object identity is compared using the is and is not operators.
  • Binding an object to a new name using assignment does not create a new object.
  • New objects that have user-defined classes are only created when the constructor of this class is called
• Methods

  class Account:
      def __init__(self, account_holder):
          self.balance = 0
          self.holder = account_holder
      def deposit(self, amount):
          self.balance = self.balance + amount
          return self.balance
      def withdraw(self, amount):
          if amount > self.balance:
              return 'Insufficient funds'
          self.balance = self.balance - amount
          return self.balance
  
  spock_account = Account('Spock')
  spock_account.deposit(100)
  100
  spock_account.withdraw(90)
  10
  spock_account.withdraw(90)
  'Insufficient funds'
  spock_account.holder
  'Spock'
      

  • Methods are invoked via .
  • Each method definition includes a special first parameter self

2.5.3 Message Passing and Dot Expressions

Methods and instance attributes replicate much of the behavior of a dispatch dictionary in a message passing implementation of a data value, objects take messages using . Central idea in message passing: data values should have behavior by responding to messages that are relevant to the abstract type they represent

• Dot expressions

  spock_account.balance
  10
  getattr(spock_account, 'balance')
  10
  hasattr(spock_account, 'deposit')
  True
      

  • spock_account.balance = built-in getattr(spock_account, 'balance')
• Methods and functions

  type(Account.deposit)
  <class 'function'>
  type(spock_account.deposit)
  <class 'method'>
  
  Account.deposit(spock_account, 1001)  # The deposit function takes 2 arguments
  1011
  spock_account.deposit(1000)           # The deposit method takes 1 argument
  2011
      

  • deposit as a plain func, must supply self explicitly: Account.deposit = getattr(Account, 'deposit') = <class 'function'>
  • deposit as a bound method, self is bound automatically: spock_account.deposit = getattr(spock_account, 'deposit') = <class 'method'>
• Naming Conventions
  • CapWords for class names
  • Lowercased words separated by underscores for funcs
  • _ attibutes can only be accessed within methods of the class itself (object.method(_, ...)) , rather than by users of the class (object._)

Question:

1. 本节前两段主要讲什么？Message passing, dot expression, dispatch dictionary的关系？dot expression相比dispatch dictionary的优势？全面优势吗？各自适合怎样的情形？

2.5.4 Class Attributes

Class attributes (class variables or static variables) are created by assignment statements in the suite of a class statement, outside of any method definition

class Account:
    interest = 0.02            # A class attribute
    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder
    # Additional methods would be defined here

spock_account = Account('Spock')
kirk_account = Account('Kirk')
spock_account.interest
0.02
kirk_account.interest
0.02

Account.interest = 0.04
spock_account.interest
0.04
kirk_account.interest
0.04

• Attribute names To evaluate a dot expression <expression> . <name>
  • <expression> yield the object
  • <name> matches from instance attributes to class attribute, just as local names have priority over global in an environment
• Attribute assignment Assignment to an attribute of an object cannot affect the attributes of its class

  kirk_account.interest = 0.08  # creating a new instance attribute interest
  kirk_account.interest
  0.08
  spock_account.interest
  0.04
  Account.interest = 0.05  # changing the class attribute
  spock_account.interest     # changes instances without like-named instance attributes
  0.05
  kirk_account.interest     # but the existing instance attribute is unaffected
  0.08
      

  • kirk_account.interest finds interest as instance attribute while spock_account.interest finds it as class attribute

2.5.5 Inheritance

• Base class (parent class or superclass) and child class (subclass)
• is-a for inheritance and has-a for instance attribute

2.5.6 Using Inheritance

class Account:
    """A bank account that has a non-negative balance."""
    interest = 0.02
    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder
    def deposit(self, amount):
        """Increase the account balance by amount and return the new balance."""
        self.balance = self.balance + amount
        return self.balance
    def withdraw(self, amount):
        """Decrease the account balance by amount and return the new balance."""
        if amount > self.balance:
            return 'Insufficient funds'
        self.balance = self.balance - amount
        return self.balance

class CheckingAccount(Account):
    """A bank account that charges for withdrawals."""
    withdraw_charge = 1
    interest = 0.01
    def withdraw(self, amount):
        return Account.withdraw(self, amount + self.withdraw_charge)


checking = CheckingAccount('Sam')
checking.deposit(10)
10
checking.withdraw(5)
4
checking.interest
0.01

• To look up a name in a class: instance attributes –> class attributes –> parent class attributes
• The class of an object stays constant throughout
• Calling ancestors: Attributes that have been overridden are still accessible via class objects in child class Account.withdraw(self, amount + self.withdraw_charge)
• Interfaces: An object interface is a collection of attributes and conditions on those attributes
• The parts of program that use the object abstraction, rather than assuming anything about its implementation are more robust to future changes

  def deposit_all(winners, amount=5):
      for account in winners:
          account.deposit(amount)
  
  def deposit_all(winners, amount=5):
      for account in winners:
          Account.deposit(account, amount)
      

  • account.deposit assumes each account satisfies the account object abstraction and will work with any other account classes
  • Account.deposit violates the abstraction barrier of the account object abstraction, and will not necessarily work with new kinds of accounts

2.5.7 Multiple Inheritance

Multiple inheritance: a subclass inheriting attributes from multiple base classes

class SavingsAccount(Account):
    deposit_charge = 2
    def deposit(self, amount):
        return Account.deposit(self, amount - self.deposit_charge)

class AsSeenOnTVAccount(CheckingAccount, SavingsAccount):
    def __init__(self, account_holder):
        self.holder = account_holder
        self.balance = 1           # A free dollar!

such_a_deal = AsSeenOnTVAccount("John")
such_a_deal.balance
1
such_a_deal.deposit(20)            # $2 fee from SavingsAccount.deposit
19
such_a_deal.withdraw(5)            # $1 fee from CheckingAccount.withdraw
13

such_a_deal.deposit_charge
2
such_a_deal.withdraw_charge
1

• Python resolves names from left to right, then upwards: AsSeenOnTVAccount, CheckingAccount, SavingsAccount, Account, object
• No correct order, but need to select some ordering in a consistent way
• C3 Method Resolution Ordering: class.mro

  [c.__name__ for c in AsSeenOnTVAccount.mro()]
  ['AsSeenOnTVAccount', 'CheckingAccount', 'SavingsAccount', 'Account', 'object']
      

2.5.8 The Role of Objects

The Python object system is designed to make data abstraction and message passing both convenient and flexible

Question:

1. 这小节整体上主要讲了什么？

2.7 Object Abstraction

A central concept in object abstraction is a generic function, which is a function that can accept values of multiple different types Three different techniques for implementing generic functions: shared interfaces, type dispatching, and type coercion

2.7.1 String Conversion

Python stipulates that all objects should produce two different string representations:

1. Human-interpretable text: constructor func for strings str
2. Python-interpretable expression: repr returns the canonical string representation of the object (where possible)

Return the canonical string representation of the object.
For most object types, eval(repr(object)) == object.

12e12
12000000000000.0
print(repr(12e12))
12000000000000.0

repr(min)
'<built-in function min>'

from datetime import date
tues = date(2011, 9, 12)
repr(tues)
'datetime.date(2011, 9, 12)'
str(tues)
'2011-09-12'

tues.__repr__()
'datetime.date(2011, 9, 12)'

tues.__str__()
'2011-09-12'

• repr(object) -> string, For most object types, eval(repr(object)) = object
• a = print(repr(a)) in an interactive session
• Polymorphic func __repr__() and __str__(): repr(tues) = tue.__repr__() and str(tues) = tue.__str__()
• . provides a mechanism for extending the domain of existing functions to new object types.
• Certain functions should apply to multiple data types. One way to create such a function is to use a shared attribute name with a different definition in each class (like __repr__() and __str__())

2.7.2 Special Methods

Certain special names are invoked by the Python interpreter in special circumstances: __init__ for objects construction; __str__ for printing; __repr__ for interactively displaying values

• True and false values All objects (of built-in and user-defined classes) in Python have a truth value, while __bool__ method can be used to override in user-defined classes

  Account.__bool__ = lambda self: self.balance != 0
  
  bool(Account('Jack'))
  False
  if not Account('Jack'):
      print('Jack has nothing')
  Jack has nothing
      

• Sequence operations

  len('Go Bears!')
  9
  'Go Bears!'.__len__()
  9
  
  bool('')
  False
  bool([])
  False
  bool('Go Bears!')
  True
  
  'Go Bears!'[3]
  'B'
  'Go Bears!'.__getitem__(3)
  'B'
      

  • len invokes __len__ method of its argument. All built-in sequence types implement this method.
  • Python uses a sequence’s length to determine its truth value
  • __getitem__ method is invoked by the element selection operator []
• Callable objects In Python, functions are first-class objects, so they can be passed around as data and have attributes like any other object. A class which includes a __call__ method can behave like a higher-order function. <<9>>

  def make_adder(n):
      def adder(k):
          return n + k
      return adder
  
  add_three = make_adder(3)
  add_three(4)
  7
  
  class Adder(object):
      def __init__(self, n):
          self.n = n
      def __call__(self, k):
          return self.n + k
  
  add_three_obj = Adder(3)
  add_three_obj(4)
  7
      

  • Objects can be “called” with __call__ method defined
• Arithmetic Special methods can also define the behavior of built-in operators applied to user-defined objects.

Question:

1. 9 中 first-class 和 have attributes like any… 怎么理解？
2. Callable object 有什么意义？怎么理解 further blurred the line between data and functions ？

2.7.3 Multiple Representations

Abstraction barriers can separate the use and representation of data. Needing not only the data abstraction barriers that isolate representation from use but also abstraction barriers that isolate different design choices from each other and permit different choices to coexist in a single program.

• Superclass Number

  class Number:
      def __add__(self, other):
          return self.add(other)
      def __mul__(self, other):
          return self.mul(other)
      

  • No __init__ method -> Not instantiated directly but served as a superclass of other number classes
  • add and mul not defined
• Complex class inherits from Number class

  class Complex(Number):
      def add(self, other):
          return ComplexRI(self.real + other.real, self.imag + other.imag)
      def mul(self, other):
          magnitude = self.magnitude * other.magnitude
          return ComplexMA(magnitude, self.angle + other.angle)
      

  • Adding: ComplexRI constructs a complex number from real and imaginary parts.
  • Multiplying: ComplexMA constructs a complex number from a magnitude and angle.
  • add and mul are generic func as both ComplexRI and ComplexMA share an interface
• Interfaces <<10>> An interface is a set of shared attribute names (here are real, imag, magnitude, and angle), along with a specification of their behavior.
  • Object attributes, which are a form of message passing, allows different data types to respond to the same message in different ways
  • A shared set of messages that elicit similar behavior from different classes is a powerful method of abstraction
  • The Complex class implicitly defines this interface by determining how these attributes are used to add and mul complex numbers.
• Properties

  from math import atan2
  class ComplexRI(Complex):
      def __init__(self, real, imag):
          self.real = real
          self.imag = imag
      @property
      def magnitude(self):
          return (self.real ** 2 + self.imag ** 2) ** 0.5
      @property
      def angle(self):
          return atan2(self.imag, self.real)
      def __repr__(self):
          return 'ComplexRI({0:g}, {1:g})'.format(self.real, self.imag)
  
  ri = ComplexRI(5, 12)
  ri.real
  5
  ri.magnitude
  13.0
  ri.real = 9
  ri.real
  9
  ri.magnitude
  15.0
  
  from math import sin, cos, pi
  class ComplexMA(Complex):
      def __init__(self, magnitude, angle):
          self.magnitude = magnitude
          self.angle = angle
      @property
      def real(self):
          return self.magnitude * cos(self.angle)
      @property
      def imag(self):
          return self.magnitude * sin(self.angle)
      def __repr__(self):
          return 'ComplexMA({0:g}, {1:g} * pi)'.format(self.magnitude, self.angle/pi)
  
  
  ma = ComplexMA(2, pi/2)
  ma.imag
  2.0
  ma.angle = pi
  ma.real
  -2.0
  
  from math import pi
  ComplexRI(1, 2) + ComplexMA(2, pi/2)
  ComplexRI(1, 4)
  ComplexRI(0, 1) * ComplexRI(0, 1)
  ComplexMA(1, 1 * pi)
      

  • @property decorator allows functions to be called without call expression syntax (): ri.magnitude, ma.imag, ma.real
  • + in ComplexRI(1, 2) + ComplexMA(2, pi/2) is overridden by __add__ in class Number (* overridden by __mul__ also)
  • add in __add__ and mul in __mul__ are both defined in complex
  • Objects can find methods and attributes its class and superclass
• The interface approach to encoding multiple representations has appealing properties
  • The class for each representation can be developed separately; they must only agree on the names of the attributes they share, as well as any behavior conditions for those attributes.
  • The interface is also additive: creating another class with the same attributes to add a new representation
• Multiple representations of data are closely related to the idea of data abstraction
  • Data abstraction can change the implementation of a data type without changing the meaning of the program
  • Interfaces and message passing can have multiple different representations

  In both cases, a set of names and corresponding behavior conditions define the abstraction that enables this flexibility.

Question:

1. 为什么父类都没有 __init__ ？为什么 __add__ 和 __mul__ 要写在父类里？ + in ComplexRI(1, 2) + ComplexMA(2, pi/2) …(link) 分析对吗？
2. 结合 10 以及最后两点，梳理清楚 attributes, messages, interface 各自的定义以及之间的关系、 data abstraction, multiple representations, message passing 各自的定义以及之间的关系。

2.7.4 Generic Functions

Generic functions are methods or functions that apply to arguments of different types

from fractions import gcd
class Rational(Number):
    def __init__(self, numer, denom):
        g = gcd(numer, denom)
        self.numer = numer // g
        self.denom = denom // g
    def __repr__(self):
        return 'Rational({0}, {1})'.format(self.numer, self.denom)
    def add(self, other):
        nx, dx = self.numer, self.denom
        ny, dy = other.numer, other.denom
        return Rational(nx * dy + ny * dx, dx * dy)
    def mul(self, other):
        numer = self.numer * other.numer
        denom = self.denom * other.denom
        return Rational(numer, denom)

Rational(2, 5) + Rational(1, 10)
Rational(1, 2)
Rational(1, 4) * Rational(2, 3)
Rational(1, 6)

A tension between implementing a generic __add__ that can add all numeric types and separating the concerns of different numeric types to maintain a modular program

• Type dispatching Selecting behavior based on the types of the arguments to a function or method to implement cross-type operations at appropriate times

  c = ComplexRI(1, 1)
  isinstance(c, ComplexRI)
  True
  isinstance(c, Complex)
  True
  isinstance(c, ComplexMA)
  False
  
  def is_real(c):
      """Return whether c is a real number with no imaginary part."""
      if isinstance(c, ComplexRI):
          return c.imag == 0
      elif isinstance(c, ComplexMA):
          return c.angle % pi == 0
  
  is_real(ComplexRI(1, 1))
  False
  is_real(ComplexMA(2, pi))
  True
  
  Rational.type_tag = 'rat'
  Complex.type_tag = 'com'
  Rational(2, 5).type_tag == Rational(1, 2).type_tag
  True
  ComplexRI(1, 1).type_tag == ComplexMA(2, pi/2).type_tag
  True
  Rational(2, 5).type_tag == ComplexRI(1, 1).type_tag
  False
  
  def add_complex_and_rational(c, r):
      return ComplexRI(c.real + r.numer/r.denom, c.imag)
  
  def mul_complex_and_rational(c, r):
      r_magnitude, r_angle = r.numer/r.denom, 0
      if r_magnitude < 0:
          r_magnitude, r_angle = -r_magnitude, pi
      return ComplexMA(c.magnitude * r_magnitude, c.angle + r_angle)
  
  def add_rational_and_complex(r, c):
      return add_complex_and_rational(c, r)
  
  def mul_rational_and_complex(r, c):
      return mul_complex_and_rational(c, r)
  
  class Number:
      def __add__(self, other):
          if self.type_tag == other.type_tag:
              return self.add(other)
          elif (self.type_tag, other.type_tag) in self.adders:
              return self.cross_apply(other, self.adders)
      def __mul__(self, other):
          if self.type_tag == other.type_tag:
              return self.mul(other)
          elif (self.type_tag, other.type_tag) in self.multipliers:
              return self.cross_apply(other, self.multipliers)
      def cross_apply(self, other, cross_fns):
          cross_fn = cross_fns[(self.type_tag, other.type_tag)]
          return cross_fn(self, other)
      adders = {("com", "rat"): add_complex_and_rational,
                ("rat", "com"): add_rational_and_complex}
      multipliers = {("com", "rat"): mul_complex_and_rational,
                     ("rat", "com"): mul_rational_and_complex}
  
  ComplexRI(1.5, 0) + Rational(3, 2)
  ComplexRI(3, 0)
  Rational(-1, 2) * ComplexMA(4, pi/2)
  ComplexMA(2, 1.5 * pi)
      

  • isinstance(object, class) returns true if the object has a class that either is or inherits from the given class
  • Both addition and multiplication are commutative: (add_complex_and_rational, add_rational_and_complex) and mul also
  • Using type tags illustrates that type dispatching is not necessarily linked to the Python object system, but instead a general technique for creating generic functions over heterogeneous domains. <<11>>
• Coercion General situation of completely unrelated operations acting on completely unrelated types need explicit corss-type operations Coercion: Changing objects of one type to another type if different data types are not completely independent

  def rational_to_complex(r):
      return ComplexRI(r.numer/r.denom, 0)
  
  class Number:
      def __add__(self, other):
          x, y = self.coerce(other)
          return x.add(y)
      def __mul__(self, other):
          x, y = self.coerce(other)
          return x.mul(y)
      def coerce(self, other):
          if self.type_tag == other.type_tag:
              return self, other
          elif (self.type_tag, other.type_tag) in self.coercions:
              return (self.coerce_to(other.type_tag), other)
          elif (other.type_tag, self.type_tag) in self.coercions:
              return (self, other.coerce_to(self.type_tag))
      def coerce_to(self, other_tag):
          coercion_fn = self.coercions[(self.type_tag, other_tag)]
          return coercion_fn(self)
      coercions = {('rat', 'com'): rational_to_complex}
      

  • Advs n disadvs
    • Writing only one function for each pair of types rather than a different function for each set of types and each generic operation
    • Extending coercion
      • Coercing several different types each into another common type
      • Iterative coercion: one data type is coerced into another via intermediate types to reduce the total number of coercion functions
    • ~ Losing information when coercing
  • Particular operators apply coercion to their arguments as needed

Question:

1. 11 这句话怎么理解？

2.8 Efficiency

Computational resources used by a representation or process

2.8.1 Measuring Efficiency

• Time A more reliable way: To measure how many times some event occurs, such as a function call.

  def fib(n):
      if n == 0:
          return 0
      if n == 1:
          return 1
      return fib(n-2) + fib(n-1)
  
  def count(f):
      def counted(*args):
          counted.call_count += 1
          return f(*args)
      counted.call_count = 0
      return counted
  
  fib = count(fib)
  fib(19)
  4181
  fib.call_count
  13529
      

  • call_count = call nums of fib(n)
• Space In evaluating an expression, the interpreter preserves all active environments and all values and frames referenced by those environments. An environment is active if it provides the evaluation context for some expression being evaluated. An environment becomes inactive whenever the function call for which its first frame was created finally returns.

  def count_frames(f):
      def counted(*args):
          counted.open_count += 1
          counted.max_count = max(counted.max_count, counted.open_count)
          result = f(*args)
          counted.open_count -= 1
          return result
      counted.open_count = 0
      counted.max_count = 0
      return counted
    
  fib = count_frames(fib)
  fib(19)
  4181
  fib.open_count
  0
  fib.max_count
  19
  fib(24)
  46368
  fib.max_count
  24
      

  • open_count = the number of calls to the function f that have not yet returned
  • max_count = maximum value ever attained by open_count, corresponding to the maximum number of frames that are ever simultaneously active during the course of computation.

Question:

1. 这两个 count 函数怎么理解？计数器为什么可以正常工作？

2.8.2 Memoization

A powerful technique for increasing the efficiency of recursive functions that repeat computation. A memoized function will store the return value for any arguments it has previously received

def memo(f):
    cache = {}
    def memoized(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return memoized

counted_fib = count(fib)
fib  = memo(counted_fib)
fib(19)
4181
counted_fib.call_count
20
fib(34)
5702887
counted_fib.call_count
35

• Memoization can be expressed naturally as a higher-order function, which can also be used as a decorator
• fib function is actually only called once for each unique input to fib

Question:

1. 同 2.8.1 中的计数器函数，怎么理解这些 high-order function ？

2.8.3 Orders of Growth

2.8.4 Example: Exponentiation

2.8.5 Growth Categories

2.9 Recursive Objects

Objects can have other objects as attribute values. Object of some class has an attribute value of that same class

2.9.1 Linked List Class

• __len__ and __getitem__

  class Link:
      """A linked list with a first element and the rest."""
      empty = ()
      def __init__(self, first, rest=empty):
          assert rest is Link.empty or isinstance(rest, Link)
          self.first = first
          self.rest = rest
      def __getitem__(self, i):
          if i == 0:
              return self.first
          else:
              return self.rest[i-1]
      def __len__(self):
          return 1 + len(self.rest)
  
  s = Link(3, Link(4, Link(5)))
  len(s)
  3
  s[1]
  4
      

  • Recursive:
    • self.rest[i-1] = Link.__getitem__(self.rest, i-1)
    • len(self.rest) = Link.__len__(self.rest)
    • isinstance(a, b) returns True is object a is a instance of class b
    • Empty linked list is represented by an empty tuple empty = ()
• link_expression and __repr__

  def link_expression(s):
      """Return a string that would evaluate to s."""
      if s.rest is Link.empty:
          rest = ''
      else:
          rest = ', ' + link_expression(s.rest)
      return 'Link({0}{1})'.format(s.first, rest)
  
  link_expression(s)
  'Link(3, Link(4, Link(5)))'
  
  Link.__repr__ = link_expression
  s
  Link(3, Link(4, Link(5)))
      

  • Recursive: rest = ', ' + link_expression(s.rest) and 'Link({0}{1})'.format(s.first, rest)
  • '{0}...{n}'.format(Object1, ..., Objectn)
  • Link.__repr__ = link_expression = def __repr__(self) ...
  • s calls Link.__repr__(s)
• Closure property Just as an element of a list can itself be a list, a Link can contain a Link as its first element.

  s_first = Link(s, Link(6))
  s_first
  Link(Link(3, Link(4, Link(5))), Link(6))
  
  len(s_first)
  2
  len(s_first[0])
  3
  s_first[0][2]
  5
      

• extend_link and __add__ <<13>>

  def extend_link(s, t):
      if s is Link.empty:
          return t
      else:
          return Link(s.first, extend_link(s.rest, t))
  extend_link(s, s)
  Link(3, Link(4, Link(5, Link(3, Link(4, Link(5))))))
  Link.__add__ = extend_link
  s + s
  Link(3, Link(4, Link(5, Link(3, Link(4, Link(5))))))
      

  • Recursive: Link(s.first, extend_link(s.rest, t))
  • s + s calls Link.__add__(s, s)
  • is to compare objects
• map_link, filter_link and join_link

  def map_link(f, s):
      if s is Link.empty:
          return s
      else:
          return Link(f(s.first), map_link(f, s.rest))
  map_link(square, s)
  Link(9, Link(16, Link(25)))
  
  def filter_link(f, s):
      if s is Link.empty:
          return s
      else:
          filtered = filter_link(f, s.rest)
          if f(s.first):
              return Link(s.first, filtered)
          else:
              return filtered
  odd = lambda x: x % 2 == 1
  map_link(square, filter_link(odd, s))
  Link(9, Link(25))
  [square(x) for x in [3, 4, 5] if odd(x)]
  [9, 25]
  
  def join_link(s, separator):
      if s is Link.empty:
          return ""
      elif s.rest is Link.empty:
          return str(s.first)
      else:
          return str(s.first) + separator + join_link(s.rest, separator)
  join_link(s, ", ")
  '3, 4, 5'
      

  • Recursive:
    • Link(f(s.first), map_link(f, s.rest))
    • filter_link(f, s.rest)
    • str(s.first) + separator + join_link(s.rest, separator)
  • All methods or funcs above are imutable, objects of Link are imutable <<12>>
  • __...__ methods are class methods, not instance methods
• Recursive Construction: partition

  def partitions(n, m):
      """Return a linked list of partitions of n using parts of up to m.
      Each partition is represented as a linked list.
      """
      if n == 0:
          return Link(Link.empty) # A list containing the empty partition
      elif n < 0 or m == 0:
          return Link.empty
      else:
          using_m = partitions(n-m, m)
          with_m = map_link(lambda s: Link(m, s), using_m)
          without_m = partitions(n, m-1)
          return with_m + without_m
  
  def print_partitions(n, m):
      lists = partitions(n, m)
      strings = map_link(lambda s: join_link(s, " + "), lists)
      print(join_link(strings, "\n"))
  
  print_partitions(6, 4)
  4 + 2
  4 + 1 + 1
  3 + 3
  3 + 2 + 1
  3 + 1 + 1 + 1
  2 + 2 + 2
  2 + 2 + 1 + 1
  2 + 1 + 1 + 1 + 1
  1 + 1 + 1 + 1 + 1 + 1
      

Question:

1. 12 关于 imutable 的理解对吗？是因为本质上 Link 是由 tuple 构成而 tuple 是 imutable 而 list 是 mutable 的吧？

2.9.2 Tree Class

A tree is any data structure that has as an attribute a sequence of branches that are also trees.

class Tree:
    def __init__(self, label, branches=()):
        self.label = label
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = branches
    def __repr__(self):
        if self.branches:
            return 'Tree({0}, {1})'.format(self.label, repr(self.branches))
        else:
            return 'Tree({0})'.format(repr(self.label))
    def is_leaf(self):
        return not self.branches

• fib_tree and sum_lables

  def fib_tree(n):
      if n == 1:
          return Tree(0)
      elif n == 2:
          return Tree(1)
      else:
          left = fib_tree(n-2)
          right = fib_tree(n-1)
          return Tree(left.label + right.label, (left, right))
    
  fib_tree(5)
  Tree(3, (Tree(1, (Tree(0), Tree(1))), Tree(2, (Tree(1), Tree(1, (Tree(0), Tree(1)))))))
    
  def sum_labels(t):
      """Sum the labels of a Tree instance, which may be None."""
      return t.label + sum([sum_labels(b) for b in t.branches])
    
  sum_labels(fib_tree(5))
  10
    
  fib_tree = memo(fib_tree)
  big_fib_tree = fib_tree(35)
  big_fib_tree.label
  5702887
  big_fib_tree.branches[0] is big_fib_tree.branches[1].branches[1]
  True
  sum_labels = memo(sum_labels)
  sum_labels(big_fib_tree)
  142587180
      

  • Recursive:
    • Tree(left.label + right.label, (left, right))
    • t.label + sum([sum_labels(b) for b in t.branches])
  • memo(fib_tree) and memo(sum_labels) to save computation time and memory: repeated subtrees are only created once, 35 (n=35) instead of 18,454,929 altogether
  • big_fib_tree.branches[0] is big_fib_tree.branches[1].branches[1]

2.9.3 Sets

Abstractly, a set is a collection of distinct objects that supports membership testing, union, intersection, and adjunction

• Sets as unordered sequences <<14>>

  def empty(s):
      return s is Link.empty
  
  def set_contains(s, v):
      """Return True if and only if set s contains v."""
      if empty(s):
          return False
      elif s.first == v:
          return True
      else:
          return set_contains(s.rest, v)
  
  s = Link(4, Link(1, Link(5)))
  set_contains(s, 2)
  False
  set_contains(s, 5)
  True
  
  def adjoin_set(s, v):
      """Return a set containing all elements of s and element v."""
      if set_contains(s, v):
          return s
      else:
          return Link(v, s)
  
  t = adjoin_set(s, 2)
  t
  Link(2, Link(4, Link(1, Link(5))))
  
  def intersect_set(set1, set2): 
      """Return a set containing all elements common to set1 and set2."""
      return keep_if_link(set1, lambda v: set_contains(set2, v))
  
  intersect_set(t, apply_to_all_link(s, square))
  Link(4, Link(1))
  
  def union_set(set1, set2):
      """Return a set containing all elements either in set1 or set2."""
      set1_not_set2 = keep_if_link(set1, lambda v: not set_contains(set2, v))
      return extend_link(set1_not_set2, set2)
  
  union_set(t, s)
  Link(2, Link(4, Link(1, Link(5))))
      

  • Efficiency
    • $Θ(n)$ : set_contains, adjoin_set
    • $Θ(n²)$ : intersect_set, union_set
  • keep_if_link and apply_to_all_link 4, extend_link 13
  • keep_if_link(set1, lambda v: set_contains(set2, v)) and keep_if_link(set1, lambda v: not set_contains(set2, v))
• Sets as ordered sequences

  def set_contains(s, v):
      if empty(s) or s.first > v:
          return False
      elif s.first == v:
          return True
      else:
          return set_contains(s.rest, v)
  
  u = Link(1, Link(4, Link(5)))
  set_contains(u, 0)
  False
  set_contains(u, 4)
  True
  
  def intersect_set(set1, set2):
      if empty(set1) or empty(set2):
          return Link.empty
      else:
          e1, e2 = set1.first, set2.first
          if e1 == e2:
              return Link(e1, intersect_set(set1.rest, set2.rest))
          elif e1 < e2:
              return intersect_set(set1.rest, set2)
          elif e2 < e1:
              return intersect_set(set1, set2.rest)
  
  intersect_set(s, s.rest)
  Link(4, Link(5))
  
      

  • Recursive:
    • set_contains(s.rest, v)
    • Link(e1, intersect_set(set1.rest, set2.rest)) and intersect_set(set1.rest, set2)
  • Efficiency:
    • set_contains: still $Θ(n)$, but save some time
    • intersect_set, adjoin_set and union_set: $Θ(n^2)$ -> $Θ(n)$
• Sets as binary search trees

  

  def set_contains(s, v):
      if s is None:
          return False
      elif s.entry == v:
          return True
      elif s.entry < v:
          return set_contains(s.right, v)
      elif s.entry > v:
          return set_contains(s.left, v)
  
  def adjoin_set(s, v):
      if s is None:
          return Tree(v)
      elif s.entry == v:
          return s
      elif s.entry < v:
          return Tree(s.entry, s.left, adjoin_set(s.right, v))
      elif s.entry > v:
          return Tree(s.entry, adjoin_set(s.left, v), s.right)
  
  adjoin_set(adjoin_set(adjoin_set(None, 2), 3), 1)
  Tree(2, Tree(1), Tree(3))
      

  • Recursive:
    • set_contains(s.right, v)
    • Tree(s.entry, s.left, adjoin_set(s.right, v))
  • Efficiency:
    • set_contains: $Θ(n)$ -> $Θ(logn)$
    • adjoin_set: $Θ(n)$ -> $Θ(logn)$
    • intersect_set and union_set: still $Θ(n)$
  • Need to balance the tree after every few adjoin_set
• Python set implementation
  • Built-in set is also mutable, but does not use mutable data types (such as lists, dictionaries or other sets) for representation
  • Built-in set uses a representation that gives constant-time membership tests and adjoin operations based on a technique called hashing
  • To allow for nested sets, built-in set includes a built-in immutable frozenset class that shares methods with the set class but excludes mutation methods and operators.

Question:

1. intersect_set(t, apply_to_all_link(s, square)) 应该返回 Link(1) 吧？ 14

Chapter 3: Interpreting Computer Programs

3.1 Introduction

Many interpreters have an elegant common structure: two mutually recursive functions. The first evaluates expressions in environments; the second applies functions to arguments. These functions are recursive in that they are defined in terms of each other: applying a function requires evaluating the expressions in its body, while evaluating an expression may involve applying one or more functions.

3.2 Functional Programming

Scheme is a dialect of Lisp, the second-oldest programming language that is still widely used today (after Fortran)

3.2.1 Expressions

Scheme programs consist of expressions: call expressions + special forms

• Call expressions: primitives + combinations (sub-expressions), same evaluation procedure as python

  (+ (* 3 5) (- 10 6))
      

• Special forms: syntactically like a call expression, but different evaluation procedure

  (if <predicate> <consequent> <alternative>)
      

3.2.2 Definitions

• Values

  (define name value)
      

• Functions (procedures in Scheme)

  (define (<name> <formal parameters>) <body>)
  (lambda (<formal-parameters>) <body>)
      

  • Example

    (define (square x) (* x x))
    
    (define (average x y)
      (/ (+ x y) 2))
    
    (define (abs x)
      (if (< x 0)
          (- x)
          x))
    
    (define (sqrt x)
      (define (good-enough? guess)
        (< (abs (- (square guess) x)) 0.001))
      (define (improve guess)
        (average guess (/ x guess)))
      (define (sqrt-iter guess)
        (if (good-enough? guess)
            guess
            (sqrt-iter (improve guess))))
      (sqrt-iter 1.0))
    
    (define (plus4 x) (+ x 4))
    (define plus4 (lambda (x) (+ x 4)))
    
    ((lambda (x y z) (+ x y (square z))) 1 2 3)
            

3.2.3 Compound values

• Built-in pairs

  (define x (cons 1 2))
  
  x
  (1 . 2)
  (car x)
  1
  (cdr x)
  2
      

  • cons, car and cdr
• Built-in recursive lists: using pairs

  (cons 1
        (cons 2
              (cons 3
                    (cons 4 nil))))
  
  (1 2 3 4)
  (list 1 2 3 4)
  (1 2 3 4)
  (define one-through-four (list 1 2 3 4))
  (car one-through-four)
  1
  (cdr one-through-four)
  (2 3 4)
  (car (cdr one-through-four))
  2
  (cons 10 one-through-four)
  (10 1 2 3 4)
  (cons 5 one-through-four)
  (5 1 2 3 4)
      

  • list
  • nil or '() represents the empty list
  • length and getitem

    (define (length items)
      (if (null? items)
          0
          (+ 1 (length (cdr items)))))
    (define (getitem items n)
      (if (= n 0)
          (car items)
          (getitem (cdr items) (- n 1))))
            

    • null?

3.2.4 Symbolic Data

One of Scheme’s strengths is working with arbitrary symbols as data.

(define a 1)
(define b 2)

(list a b)
(1 2)
(list 'a 'b)
(a b)
(list 'a b)
(a 2)

(list 'define 'list)
(define list)

(car '(a b c))
a
(cdr '(a b c))
(b c)

• Quotation is the ability to quote a data object
• In Scheme, any expression that is not evaluated is said to be quoted
• In language, quotation allows talking about language itself
• Quotation allows typing in compound objects

Question:

1. 以上四点在表达什么？到底什么是 Quotation ？一种概念or一种表达？什么叫“任何未评估的表达都被称为引用”？第1 2点的 Question 是不同的概念？
2. Quotation 和其他语言里的字符串有什么区别？为什么说它能讨论语言本身？这与第2点“任何未评估的表达都被称为引用”有什么关系？
3. 第4点意味着 '... 就是Quotation ？这与第2点“任何未评估的表达都被称为引用”冲突吗？

3.2.5 Turtle graphics

> (define (repeat k fn) (if (> k 0)
                            (begin (fn) (repeat (- k 1) fn))
                            nil))
> (repeat 5
          (lambda () (fd 100)
                  (repeat 5
                          (lambda () (fd 20) (rt 144)))
                  (rt 144)))
nil

> (define (repeat k fn)
    (if (> k 0)
        (begin (fn) (repeat (- k 1) fn))
        nil))

> (define (tri fn)
    (repeat 3 (lambda () (fn) (lt 120))))

> (define (sier d k)
    (tri (lambda ()
           (if (= k 1) (fd d) (leg d k)))))

> (define (leg d k)
    (sier (/ d 2) (- k 1))
    (penup)
    (fd d)
    (pendown))

> (sier 400 6)

3.3 Exceptions

Chapter 4: Data Processing

4.2 Implicit Sequences

A sequence can be represented without each element being stored explicitly in the memory of the computer Lazy computation describes any program that delays the computation of a value until that value is needed

4.2.1 Iterators

4.2.2 Iterables

4.2.3 Built-in Iterators

4.2.4 For Statements

counts = [1, 2, 3]
for item in counts:
    print(item)
1
2
3

items = iter(counts)
try:
    while True:
        item = next(items)
        print(item)
except StopIteration:
    pass
1
2
3

• for <name> in <expression>:: iter(expression) –> <name> = iter(expression).next –> <name> = iter(expression).next.next –> … –> StopIteration –> existing for

4.2.5 Generators

4.2.6 Python Streams

Streams offer another way to represent sequential data implicitly, a Stream stores how to compute (a method) the rest of the Stream, rather than always storing the rest explicitly. A Stream is a lazily computed linked list. The rest of a Stream is itself a Stream, which is computed lazily (when it is looked up)

class Stream:
    """A lazily computed linked list."""
    class empty:
        def __repr__(self):
            return 'Stream.empty'
    empty = empty()
    def __init__(self, first, compute_rest=lambda: empty):
        assert callable(compute_rest), 'compute_rest must be callable.'
        self.first = first
        self._compute_rest = compute_rest
    @property
    def rest(self):
        """Return the rest of the stream, computing it if necessary."""
        if self._compute_rest is not None:
            self._rest = self._compute_rest()
            self._compute_rest = None
        return self._rest
    def __repr__(self):
        return 'Stream({0}, <...>)'.format(repr(self.first))

r = Link(1, Link(2+3, Link(9)))
s = Stream(1, lambda: Stream(2+3, lambda: Stream(9)))
r.first
1
s.first
1
r.rest.first
5
s.rest.first
5
r.rest
Link(5, Link(9))
s.rest
Stream(5, <...>)

• self._rest is None when a Stream instance is constructed, signifying that the rest of the Stream has not yet been computed
• r.rest itself is (stores explicitly) a Link: Link(5, Link(9)), while s.rest is calling a property method which calls the func (compute_rest) to compute the rest Stream, then caches as self._rest and finally returns it on demand: Stream(5, <...>)
• compute_rest is a non-arguements func which conputes a Stream or Stream.empty, it is stored in a Stream and only ever called once when the property method rest is called, then discarded. (<...> implies the non-arguements func compute_rest stored in Stream(5, <...>))
• Examples
  • Increasing integers

    def integer_stream(first):
        def compute_rest():
            return integer_stream(first+1)
        return Stream(first, compute_rest)
        
    positives = integer_stream(1)
    positives
    Stream(1, <...>)
    positives.first
    1
        
    positives.first
    1
    positives.rest.first
    2
    positives.rest.rest
    Stream(3, <...>)
            

    • <...> is compute_rest, once .rest is called, <...> will return integer_stream(first+1) -> Stream(2, <...>)
  • map and filter on stream

    def map_stream(fn, s):
        if s is Stream.empty:
            return s
        def compute_rest():
            return map_stream(fn, s.rest)
        return Stream(fn(s.first), compute_rest)
        
    def filter_stream(fn, s):
        if s is Stream.empty:
            return s
        def compute_rest():
            return filter_stream(fn, s.rest)
        if fn(s.first):
            return Stream(s.first, compute_rest)
        else:
            return compute_rest()
            

    • A common pattern in stream processing: a locally defined compute_rest function recursively applies a processing function (map_stream and filter_stream) to the rest of the stream whenever the rest is computed (.rest).
  • Using map_stream and filter_stream

    def first_k_as_list(s, k):
        first_k = []
        while s is not Stream.empty and k > 0:
            first_k.append(s.first)
            s, k = s.rest, k-1
        return first_k
        
    s = integer_stream(3)
    s
    Stream(3, <...>)
    m = map_stream(lambda x: x*x, s)
    m
    Stream(9, <...>)
    first_k_as_list(m, 5)
    [9, 16, 25, 36, 49]
        
    def primes(pos_stream):
        def not_divible(x):
            return x % pos_stream.first != 0
        def compute_rest():
            return primes(filter_stream(not_divible, pos_stream.rest))
        return Stream(pos_stream.first, compute_rest)
        
    prime_numbers = primes(integer_stream(2))
    first_k_as_list(prime_numbers, 7)
    [2, 3, 5, 7, 11, 13, 17]
        
    prime_numbers.first
    2
            

    • primes(filter_stream(not_divible, pos_stream.rest))
    • Unlike iterators, streams can be passed to pure functions multiple times and yield the same result each time
• Linked lists vs streams
  • Linked lists provide a simple implementation of the sequence abstraction
  • Streams provide a simple, functional, recursive data structure that implements lazy evaluation through the use of higher-order functions.