CS61A Python Notes

http://composingprograms.com/pages/13-defining-new-functions.html

Chapter 1: Building Abstractions with Functions

1.1 Getting Started

1.1.4 First Example

Statement describe actions. statement are not evaluated but executed.

Expression describe computations.
All expressions can use function call notation.

1.2 Elements of Programming

Data is stuff that we want to manipulate, and functions describe the rules for manipulating the data.

1.2.3 Importing Library Functions

Import from the math module:

>>> from math import sqrt 

The interpreter must maintain some sort of memory that keeps track of the names, values, and bindings. This memory called a environment.

We can use assignment statements to give new names to existing functions.

f = max

Assining multiple values to multiple names in a single statement:

area, circumference = pi * radius * radius, 2 * pi * radius

1.2.5 Evaluating Nested Expressions

To evaluate a call expression, Python will do the following:
1. Evaluate the operator and operand subexpressions, then
2. Apply the function that is the value of the operator subexpression to the arguments that are the values of the operand subexpressions.

1.2.6 The Non-Pure Print Function

Distinguish between two types of functions:

Pure functions: Functions have some input(their arguments) and reutrn some output(the result of applying them).

Non-pure functions: make some change to the state of the interpreter or computer, a common side effect is to generate additional output beyond the return value.

None is a special Python value that represents nothing.

Be careful with print. The fact that it returns None means that it should not be the expression in an assignment statement.

1.3 Defining New Functions

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

The x in this definitions is called a “formal parameter”

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

1.3.1 Environments

An environments in which an expression is evaluated consists of a sequence of frames.

Each frame contains bindings, each of which associates a name with its corresponding value.
There is a global environment.

The name appearing in the function is called the intrinsic name.
The name in a frame is a bound name.
Different names may refer to the same function, but that function itself has only one intrinsic name.

A description of the formal parameters of a function is called the function’s signature.

1.3.2 Calling User-Defined Functions

Applying a user-defined function introduces a second local frame, which is only accessible to that function.

Name Evaluation. A name evaluates to the value bound to that name in the earliest frame of the current environment in which that name is found.

Names are bound to values, which are distributed across many independent local frames, along with a single global frame that contains shared names. A new local frame is introduced every time a function is called.

1.3.4 Local Names

1.3.5 Choosing Names

1.3.6 Functions as Abstractions

The three core attributes of a function: The domain of a function is the set of arguments it can take. The range of a function is the set of value it can return. The indent of a function is the relationship it computes between inputs and output.

1.3.7 Operators

The // operator, rounds the result down to an integer.

The operator can be seen as shorthand for function, like: + is the shorthand of add().

1.4 Designing Function

The qualities of good functions all reinforce the idea that functions are abstractions.
- Each function should have exactly one job
- Don’t repeat yourself is a central tenet of software engineering
- Functions should be defined generally

1.4.1 Documentation

Dostring, using triple quoted. The first line describes the job of the function in one line. The following lines can describe arguments and clarify the behavior of the function. 这是制作help页，when you call help with the name of a function as an argument, you see its docstring.

def pressure(v, t, n):
        """Compute the pressure in pascals of an ideal gas.

        Applies the ideal gas law: http://en.wikipedia.org/wiki/Ideal_gas_law

        v -- volume of gas, in cubic meters
        t -- absolute temperature in degrees kelvin
        n -- particles of gas
        """
        k = 1.38e-23  # Boltzmann's constant
        return n * k * t / v

Comments use #.

1.4.2 Default Argument Values

def pressure(v, t, n=6.022e23)

1.5 Control

Python code is a sequence of statements.

Practical Guidance
When indenting a suite, all lines must be indented the same amount and in the same way(use spaces, not tabs). Any variation in indentation will cause an error.

1.5.3 Defining Functions II: Local Assignment

The process of function application terminates whenever the first return statement is excuted.

1.5.4 Conditional Statements

Conditional statements

if <expression>:
     <suite>
elif <expression>:
     <suite>
else:
     <suite>]

Python includes several false value, including 0, None, and the boolean value false.

The built-in comparison operations: <, >, >=, <=, ==, !=.

Three basic logical operators are also built into Python: and, or, not.

Functions that perform comparisons and return boolean values typically begin with is.

1.5.5 Iteration

while <expression>:
  <suite>

1.5.6 Testing

Assertions. Programmers use assert statements to verify expectations, such as the output of a function being tested.

assert fib(8) == 13, 'The 8th Fibonacci number should be 13'

如果为 false 则打印后面的 expression.

doctest module. 利用 docstring 来测试.

def sum_naturals(n):
      """Return the sum of the first n natural numbers.

      >>> sum_naturals(10)
      55
      >>> sum_naturals(100)
      5050
      """
      total, k = 0, 1
      while k <= n:
          total, k = total + k, k + 1
      return total

Starting Python with the doctest command line option:

python3 -m doctest <python_source_file>

1.6 Higher-Order Functions

Functions that manipulate functions are called higher-order functions.

Frames which are no longer needed are removed to save space.

在函数被调用时才会创建 local frame.

1.6.1 Functions as Arguments

1.6.2 Functions as General Methods

1.6.3 Defining Functions III: Nested Definitions

To place function definitions inside the body of other definitions:

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)

Lexical scope
A discipline of sharing names among nested definitions. The inner functions have access to the names in the environment where they are defined.

Two extensions to the environment model:
- Each user-defined function has a parent environment: the environment in which it was defined
- When a user-defined function is called, its local frame extends its parent environment.

1.6.4 Functions as Returned Values

1.6.5 Example: Newton’s Method

1.6.6 Currying

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

Currying is a transformation, like:

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

>>> curried_pow(2)(3)
8

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

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

1.6.8 Abstractions and First-Class Functions

1.6.9 Function Decorators

The decorator symbol @.

@ 后面跟一个 expression, this expression is evaluated first, the def statement second, and finally the result of evaluating the decorator expression is applied to the newly defined function, and the result if bound to the name in the def statement.

作用:

1. 使函数的功能得到补充，而同时不用修改函数本身的代码
2. 增加函数执行前、后的行为，而不需对调用函数的代码做任何改变。

感觉就是在当前函数的基础上添加功能。减少重复。

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

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

在调用triple时就会同时执行trace和triple中的内容。

1.7 Recursive Functions

The operators % and // can be used to separate a number into two parts: its last digit and all but its last digit.

>>> 18117 % 10
7
>>> 18117 // 10
1811

The process of excuting the body of a recursive function may in turn require applying that function again.

1.7.1 The Anatomy of Recursive Functions

A common pattern: the body begins with a base case, a conditional statement that define the behavior of the function for the inputs that are simplest to process.

1.7.2 Mutual Recursion

A recursive procedure is divided among two functions that call each other.

1.7.3 Printing in Recursive Functions

1.7.4 Tree Recursion

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

1.7.5 Example: Partitions

Project 1: The Game of Hog

Champter 2: Building Abstractions with Data

2.1 Introduction

2.1.1 Native Data Types

The built-in type function allows us inspect the class of any value.

>>> type(2)
<class 'int'>

Native data types have the following properties:

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

Python has three native numeric types: integers(int), real numbers(float), and complex numbers(complex).

int objects represent integers exactly, without any approximation or limits on their size.

float objects have minimum and maximum values.

2.2 Data Abstraction

Data abstraction isolates how a compound data value is used from the details of how it is constructed.

2.2.1 Example: Rational Numbers

Dividing integers produces a float approximation, losing the exact precision of integers.

A powerful strategy for designing programs: wishful thinking.

2.2.2 Pairs

Python provides a compound structure called a list.

>>> [10, 20]
[10, 20]

Two ways to 使用 the elements in list:

1. assignment, 赋值
2. element selection operator, 使用 index

The equivalent function for element selection operator is called getitem.

>>> from operator import getitem
>>> getitem(pair, 0)
10
>>> getitem(pair, 1)
20

2.2.3 Abstraction Barriers

These functions are called by a higher level and implemented using a lower level of abstraction.

The fewer functions that depend on a particular representation, the fewer changes are required when one wants to change that representation. 也就是用函数去构建另一个函数.

2.2.4 The Properties of Data

2.3 Sequences

Sequences is a collection of behavious that are shared among several different types of data.

• Length
• Element selection

2.3.1 Lists

A list value is a sequence that can have arbitrary length.

The built-in len function returns the length of a sequence.

Lists can be added together and multiplied by integer:

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

2.3.2 Sequence Iteration

The for statement:

>>> def count(s, value):
      """Count the number of occurrences of value in sequence s."""
      total = 0
      for elem in s:
          if elem == value:
              total = total + 1
      return total

The will be bound to the last element of the sequence after the for statement is executed.

The pattern of binding multiple names to multiple values in a fixed-length sequence is called sequence unpacking:

>>> for x, y in pairs:
      if x == y:
          same_count = same_count + 1

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

Ranges are created with range:

>>> range(1, 10)  # Includes 1, but not 10
range(1, 10)

Calling the list constructor on a range evaluates to a list:

>>> list(range(5, 8))
[5, 6, 7]

A common convention is to use a single underscore character for the name in the for header if the name is unused in the suite:

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

Go Bears!
Go Bears!
Go Bears!

2.3.3 Sequence Processing

List Comprehensions:

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

The general form is:

[<map expression> for <name> in <sequence expression> if <filter expression>]

Aggregation, to aggregate all value in a sequence into a single value.
Higher-Order Functions
Conventional Names
In Python programs, it is more common to use list comprehension directly rather than higher-order functions, but both approaches to sequence processing are widely used.

2.3.4 Sequence Abstraction

Membership, A value can be tested for membership in a sequence. 就是看一个元素是否在 list 中.

Python has two operators in and not in:

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

Slicing, sequences contain smaller sequences within them. 就是把 list 拆分.

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

2.3.5 Strings

The constructor str.

String literals are surrounded by either single or double quotation marks.

Strings have a length and they support element selection.

Like lists, strings can also be combined via addtion and multiplication:

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

Membership, it matches substrings rather than elements:

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

Multiple Literals, use triple quoting.
String Coerction, a string can be created from any object in Python by calling the str constructor function.

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

2.3.6 Trees

The data abstraction for a tree consists of the constructor tree and theselectors label and branches.

A tree is well-formed only if it has a root label and all branches are also trees.

The type function:

if type(tree) != list or len(tree) < 1:
          return False

tree 是 nested list, 第一个元素为 root/label, 后面的为 branches.
Patition trees,

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.

Linked list have recursive structure: the rest of a linked list is a linked list or ‘empty’. 这个 ‘empty’ 是字符串 ‘empty’.

2.4 Mutable Data

One powerful technique for creating modular programs is to incorporate data that may change state over time.

Adding state to data is a central ingredient of a paradigm called object-oriented programming.

2.4.1 The Object Metaphor

The distinguish between functions and data: functions performed operations and data were operated upon.

Objects combine data values with behavior.

A class represents a kind of value. Individual dates are called instances of that class.

Objects have attributes, which are named values that are part of the object. We use dot notation to designated an attribute of an object.

<expression>.<name>

Objects also have methods, which are function-valued attributes.

In fact, all values in Python are objects. That is, all values have behavior and attributes. They act like the values they represent.

2.4.2 Sequence Objects

Instances of primitive built-in values such as numbers are immutable. The values themsleves cannot change over the course of program execution.

Mutable objects are used to represent values that change over time.

  >>> 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 = chinese 这里 suits 相当于 chinese 这个列表的引用, 修改 suits 会引起 chinese 的值改变.

但:

suits = list(chinese)

就不会将二者联系在一起.

>>> suits.insert(2, 'Joker')  # Insert an element at index 2, shifting the rest
>>> nest[0].pop(2)
'Joker'

To test whether two objects are the same, Python includes two comparison operator, called is and is not, that test whether two expressions in fact evaluate to the identical object.

Two onjects are identical if they are equal in their current value, and any change to one will always be reflected in the other.

区分 == 和 is.

Tuples
An instance of the built-in tuple type, is an immutable sequence. 使用 parentheses.

tuple也是 finite length and support element selection:

>>> code = ("up", "up", "down", "down") + ("left", "right") * 2
>>> len(code)
8
>>> code[3]
'down'
>>> code.count("down")
2
>>> code.index("left")
4

While it is not possible to change which elements are in a tuple, it is possible to change the value of a mutable element contained within a tuple.

nest = (10, 20, [30, 40])
2	nest[2].pop()

2.4.3 Dictionaries

A dictionary contains key-value pairs, where both 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.

Adding new key-value pairs and changing the existing value for a key can both be achieved with assignment statements:

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

Dictionaries are unordered collections of key-value pairs.

The methods keys, values, and items all return iterable values.

A list of key-value pairs can be converted into a dictionary by calling the dict constructor function:

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

Restrictions:

• A key of a dictionary cannot be or contain a mutable value.
• There can be at most one value for a given key.

A useful method implemented by dictionaries is get, which returns either the value for a key, if the key is present, or a default value. The arguments to get are the key and the default value.

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

Dictionaries also have a comprehension syntax analogous to those of lists. A key expression and a value expression are separated by a colon. Evaluating a dictionary comprehension creates a new dictionary object.

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

The nonlocal statement indicates that the name appears somewhere in the environment other than the first(local) frame or the last(global) frame. 也就是说, 假如有个test变量在这个函数之外已经被定义了, 然而要在这个函数里面修改这个test的值, 如果nonlocal test, 那么这个test就不是函数里面的局部变量,而是外面那个.

nonlocal用于声明外部函数的局部变量.

high-order function, 就是把需要多个参数的一个函数拆分为, 每次只需要一个参数的迭代函数.

Assignment has a dual role: they either created new bindings or re-bound existing names.

Python has an unusual restriction regarding the lookup of names: within the body of a function, all instances of a name must refer to the same frame.

Adding a nonlocal statement can correct the UnboundLocalError: local variable 'balance' referenced before assignment error.

2.4.5 The Benefits of Non-Local Assignment

2.4.6 The Cost of Non-Local Assignment

Our values did not change, only our names and bindings changed.

We must be very careful to understand the effect of a change on other names that might refer to thos values.

Only function calls can introduce new frames.

2.4.7 Implementing Lists and Dictionaries

Two empty lists are not identical values.

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.

Linked list, 是链表.

2.4.9 Propagating Constraints

Mutable data allows us to simulate systems with change, but also allows us to build new kinds of abstractions.

A connector is an object that “holds” a value and may participate in one or more constraints.

2.5 Object-Oriented Programming

Objects have local state that is not directly accessible from the global environment.

Each objects bundles together local state and behavior in a way that abstracts the complexity of both.

Every object also has a type, called its class.

2.5.1 Objects and Classes

A class serves as a template for all objects whose type is that class.

Every object is an instance of some particular class.

The syntax in Python for instantiating a class is identical to the syntax of calling a function:

>>> a = Account('Kirk')

The attributes specific tot a particular object, as opposed to all objects of a class, are called instance attributes. Instance attributes may also be called field, properties, or instance variable.

Functions that operate on the object or perform object-specific computations are called methods. Methods are invoked on a particular object.

2.5.2 Defining Classes

class <name>:
    <suite>

The method that initializes objects has a special name in Python, _init_, and is called the constructor for the class.

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

第一个self参数是 bound to the newly created object. 使用self是一个 convention.

第二个参数是我们传入的.

Object identity is compared using the is and is not operators.

>>> a is a
True
>>> a is not b
True

Binding an object to a new name using assignment does not create a new object:

>>> c = a
>>> c is a
True

Methods’definition:

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

注意都有self 参数.

2.5.3 Message Passing and Dot Expressions

Dot notation is a syntactic feature of Python that formalizes the message passing metaphor.

Dot expression, consists of an expression, a dot, and a name.

<expression> . <name>

The built-in function getattr will return an attribute for an object by name:

>>> getattr(spock_account, 'balance')
10

To test whether an object has a named attribute with hasattr:

>>> hasattr(spock_account, 'deposit')
True

Methods and function. WWhen a method is invoked on an object, that object is implicitly passed as the first argument to the method. As a result, the object is bound to the parameter self.

We can call deposit(example in the text) in two ways: as a function and as a bound method.

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

也就是说, 使用 dot operator 是自动传入self参数.

Naming Conventions, 首字母大写.

Python’s convention dictates that if an attribute name starts with an underscore, it should only be accessed within methods of the class itself, rather than by users of the class.

2.5.4 Class Attributes

Some attribute values are shared across all objects of a given class. Such attributes are associated with the class itself, rather than any individual instance of the class. 也就是说这个 attribute 是和整个 class 关联在一起的. 使用class改变. class attributes may also be called class variables or static variables.

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

分有 class attribute 和 instance attribute.

Instance attributes are found before class attributes, just as local names have priority over global in an environment.

2.5.5 Inheritance

Two classes may have similar attributes, but one represents a special case of the othor.

The terms parent class and superclass are also used for the base class, while child class is also used for the subclass.

2.5.6 Using Inheritance

>>> class CheckingAccount(Account):

Placing an expression that evaluates to the base class in parentheses after the class name. subclass 可以覆盖 superclass 的 attributes.

To look up a name in a class:

1. If it names an attribute in the class, return the attribute value.
2. Otherwise, look up the name in the base class, if there is one.

An object interface is a collection of attributes and conditions on those attributes.

2.5.7 Multiple Inheritance

Python supports the concept of a subclass inheriting attributes from multiple base classes, a language feature called multiple inheritance. 也就是说从多个 class 中继承.

>>> class AsSeenOnTVAccount(CheckingAccount, SavingsAccount):

在继承图中, Python resolves names from left to right, then upwards.

Python resolves this name using a recursive algorithm called the C3 Method Resolution Ordering.

2.5.8 The Role of Objects

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

2.6 Implementing Classes and Objects

Programs can be object-oriented, even in programming languages that do not have a built-in object system.

2.6.1 Instances

An instance has named attributes, such as the balance of an account, which can be set and retrieved.

2.6.2 Classes

A class is also an object, both in Python’s object system and the system we are implementing here.

In Python, classes do have classes, almost all classes share the same class, called type.

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
• type coercion

2.7.1 String Conversion

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

• humen-interpretable text
• Python-interpretable expression
  The constructor str returns a human-readable string. The repr function returns a Python expression that evaluates to an equal object.

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

  The repr function always invokes a method called _repr_ on its argument:

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

  The str function always invokes a method called _str_ on its argument:

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

2.7.2 Special Methods

In Python, certain special names are invoked by the Python interpreter in special circumstances. For example, the _init_ method of a class is automatically invoked whenever an object is constructed.

定义_bool_来判断一个object的 true or false.

The len function invokes the _len_ method of its argument to determine its length.

>>> 'Go Bears!'._len_()
9

Python uses a sequence’s length to determine its truth value, if it does not provide a _bool_ method. Empty sequences are false, while non-empty sequences are true:

>>> bool('')
False
>>> bool([])
False
>>> bool('Go Bears!')
True

The _getitem_ method is invoked by the element selection operator, but it can also be invoked directly:

>>> 'Go Bears!'[3]
'B'
>>> 'Go Bears!'.__getitem__(3)
'B'

Using _call_ method we can define a class that behaves like functions:

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

2.7.3 Multiple Representations

How numbers can be added or multiplied is abstracted by the method names add and mul:

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

Special method names
和行为挂钩, 比如:_add_ 和 + 相关, 做+运算时会自动调用_add_.

An interface is a set of shared attribute names, along with a specification of their behavior.

The @property decorator allows functions to be called without call expression syntax. 也就是调用 method 时后面不用加括号.

Multiple representations of data, 也就是一种数据用多种表示方法.

2.7.4 Generic Functions

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

The built-in function isinstance takes an object and a class. It returns true if the object has a class that either is or inherits from the given class.

>>> c = ComplexRI(1, 1)
>>> isinstance(c, ComplexRI)
True
>>> isinstance(c, Complex)
True
>>> isinstance(c, ComplexMA)
False

使用 type_tag attribute.

>>> Rational.type_tag = 'rat'
>>> Complex.type_tag = 'com'

Coercion

Often the different data types are not completely independent, and there may be ways by which objects of one type may be viewed as being of another type. This process is called coercion.

Here is a typical coercion function, which transforms a rational number to a complex number with zero imaginary part:

>>> def rational_to_complex(r):
        return ComplexRI(r.numer/r.denom, 0)

It is not generally possible to coerce an arbitrary data object of each type into all other types.

This coercion scheme has some advantages over the method of defining explicit cross-type operations.

Although we still need to write coercion functions to relate the types, we need to write only one function for each pair of types rather than a different function for each set of types and each generic operation.

Some more sophisticeted coercion schemes do nut just try to coerce one type into another, but instead may try to coerce two different types each into a third common type.

2.8 Efficiency

2.8.1 Measuring Efficiency

Inspecting how many times fib is called:

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

Space

The interpreter preserves all active environment 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 ceated finally returns.

2.8.2 Memoization

Tree-recursive computational processes can often be made more efficient through memoization.

A memoized function will store the return value for any arguments it has previously received. 就是以前计算过的值在 recursive computation 中不会被计算第二次.

2.8.3 Orders of Growth

2.9 Recursive Objects

Objects can have other objects as attribute values. When an object of some class has an attribute value of that same class, it is a recursive object.

2.9.1 Linked List Class

The empty list is a special case of a linked list that has no first element or rest.

A linked list is a sequence: it has a finite length and supports element selection by index.

These bulit-in functions invoke special method names of a class: length is computed by _len_ and element selection is computed by _getitem_.

2.9.3 Sets

Sets are unordered collections, and so the printed ordering may differ from the element ordering in the set literal.

Python sets support a vatiety of operations, including membership tests, length computation, and the standard set operations of union and intersection.

>>> 3 in s
True
>>> len(s)
4
>>> s.union({1, 5})
{1, 2, 3, 4, 5}
>>> s.intersection({6, 5, 4, 3})
{3, 4}

Sets comparison:

• isdisjoint
• issubset
• issuperset
  Mutable, change one element at a time:
• add
• remove
• discard
• pop
  Multi-element mutations:
• clear
• update

Chapter 3: Interpreting Computer Programs

3.1 Introduction

3.1.1 Programming Language

3.2 Functional Programming