0 写在前面

其实CS61A的学习，在大一上学期就开始了，寒假时写完了第二个project，之后搁置，其实期间学的也比较断断续续，笔记也不太完整，今天下学期的期末考试都结束了，这门课程半途而废不大好，所以打算结合reading和之前比较零散的笔记再做一点复习，之后把这门课学完。

希望自己能做下去，我想这也许是对我自己的一种肯定，某种意义上吧。

课程的教材写的很好，所以文章不少内容是复制的教材的原文，但也经过了个人的整理，不至于像教材那样那么长

1 Getting Started

The high productivity of computer science is only possible because the discipline is built upon an elegant and powerful set of fundamental ideas. All computing begins with representing information, specifying logic to process it, and designing abstractions that manage the complexity of that logic.

Mastering these fundamentals will require us to understand precisely how computers interpret computer programs and carry out computational processes.

1.1 Programming in Python

In order to define computational processes, we need a programming language; preferably one that many humans and a great variety of computers can all understand. In this text, we will work primarily with the Python language.

Statements & Expressions

Python code consists of expressions and statements. Broadly, computer programs consist of instructions to either

  1. Compute some value
  2. Carry out some action

Statements typically describe actions. When the Python interpreter executes a statement, it carries out the corresponding action.

On the other hand, expressions typically describe computations. When Python evaluates an expression, it computes the value of that expression.

Functions & Objects

Functions encapsulate(封装) logic that manipulates data

A set(集合，这里只是举例) is a type of object, one that supports set operations like computing intersections and membership. An object seamlessly bundles together data and the logic that manipulates that data, in a way that manages the complexity of both.

Interpreters

Evaluating compound expressions requires a precise procedure that interprets code in a predictable way. A program that implements such a procedure, evaluating compound expressions, is called an interpreter.

1.2 Errors

Learning to interpret errors and diagnose the cause of unexpected errors is called debugging. Some guiding principles of debugging are:

  1. Test incrementally: Every well-written program is composed of small, modular components that can be tested individually. Try out everything you write as soon as possible to identify problems early and gain confidence in your components.

  2. Isolate errors: An error in the output of a statement can typically be attributed to a particular modular component. When trying to diagnose a problem, trace the error to the smallest fragment of code you can before trying to correct it.

  3. Check your assumptions: Interpreters do carry out your instructions to the letter — no more and no less. Know your assumptions, then focus your debugging effort on verifying that your assumptions actually hold.

  4. Consult others: You are not alone!

2 Elements of Programming

A programming language is more than just a means for instructing a computer to perform tasks. The language also serves as a framework within which we organize our ideas about computational processes.

Every powerful language has three such mechanisms:

  • primitive expressions and statements, which represent the simplest building blocks that the language provides,
  • means of combination, by which compound elements are built from simpler ones, and
  • means of abstraction, by which compound elements can be named and manipulated as units.

In programming, we deal with two kinds of elements: functions and data. Informally, data is stuff that we want to manipulate, and functions describe the rules for manipulating the data.

2.1 Expressions

One kind of primitive expression is a number.

1
2
>>> 42
42

Expressions representing numbers may be combined with mathematical operators to form a compound expression, which the interpreter will evaluate:

1
2
>>> -1 - -1
0

2.2 Call Expressions

A call expression, which is the most important kind of compound expression, applies a function to some arguments.

1
max(7.5, 9.5)

This call expression has subexpressions: the operator is an expression that precedes parentheses, which enclose a comma-delimited(逗号分隔的) list of operand expressions.

The operator specifies a function. When this call expression is evaluated, we say that the function max is called with arguments 7.5 and 9.5, and returns a value of 9.5.

2.3 Importing Library Functions

1
2
3
>>> from math import sqrt
>>> sqrt(361)
19.0

2.4 Names and the Environment

A critical aspect of a programming language is the means it provides for using names to refer to computational objects. If a value has been given a name, we say that the name binds to the value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
'''
In Python, we can establish new bindings using the assignment statement, which contains 
a name to the left of = and a value to the right
'''
>>> r=20
>>> a=r*3
>>> r
20
>>> r=40
>>> a
60

'''
Names are also bound via import statements.
'''
>>> from math import pi
>>> pi*2
6.283185307179586

The possibility of binding names to values and later retrieving those values by name means that the interpreter must maintain some sort of memory that keeps track of the names, values, and bindings. This memory is called an environment.

Names can also be bound to functions.

In Python, names are often called variable names or variables because they can be bound to different values in the course of executing a program. When a name is bound to a new value through assignment, it is no longer bound to any previous value. One can even bind built-in names to new values.(比如max赋值为6)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
>>> max(3,4)
4
>>> max
<built-in function max>
>>> f=max # 此时取最大值函数有两个name，f和max
>>> max(3,4)
4
>>> f
<built-in function max>
>>> f(3,4)
4
>>> max=6 # max意义改变，这个name被赋值为6
>>> max(3,4)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'int' object is not callable

When executing an assignment statement, Python evaluates the expression to the right of = before changing the binding to the name on the left.

1
2
3
4
>>> x=6
>>> x=x+1
>>> x
7

With multiple assignment, all expressions to the right of = are evaluated before any names to the left are bound to those values.

1
2
3
4
5
6
7
8
9
10
11
>>> x=6
>>> x,y=4,x+1 # assign multiple values to multiple names in a single statement
>>> x
4
>>> y
7
>>> x,y = y,x # 1.(evaluate)y=7  2.(evaluate)x=4  3.(bind)x=7(y)  4.(bind)y=4(x) 
>>> x
7
>>> y
4

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.

反复执行第一步，最后我们只会碰到最原始的表达式，例如一个数字或者name，我们这样处理：

  • A numeral evaluates to the number it names (we actually mean that the Python interpreter evaluates a numeral to a number.)
  • A name evaluates to the value associated with that name in the current environment.

An expression tree

In general, statements are not evaluated but executed; they do not produce a value but instead make some change.

2.6 The Non-Pure Print Function

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

Non-pure functions. In addition to returning a value, applying a non-pure function can generate side effects, which make some change to the state of the interpreter or computer.

1
2
3
4
5
6
7
8
9
10
11
12
>>> 5
5
>>> None # None is not displayed by the interpreter as the value of an expression
>>> print(print(1),print(2))
1 # evaluate subexpression print(1) first
2 # the value is None, but it'll display 2 as an side effect
None None
>>> two = print(2)
2
>>> two
>>> print(two)
None

The value that print returns is always None, a special Python value that represents nothing.
In the case of print, the function itself is printing output as a side effect of being called.

A function that doesn’t explicitly return a value will return None.

3 Defining New Functions

We have identified in Python some of the elements that must appear in any powerful programming language:

  1. Numbers and arithmetic operations are primitive built-in data values and functions.
  2. Nested function application provides a means of combining operations.
  3. Binding names to values provides a limited means of abstraction.

Function is a much more powerful abstraction technique by which a name can be bound to compound operation, which can then be referred to as a unit.

How to define a function. Function definitions consist of a def statement that indicates a <name> and a comma-separated list of named <formal parameters>, then a return statement, called the function body, that specifies the <return expression> of the function, which is an expression to be evaluated whenever the function is applied

1
2
3
4
5
6
7
8
9
10
def twice(x):
    return x*x

'''
This defines a new function that has been given the name twice. 
This user-defined function is not built into the interpreter.
It represents the compound operation of multiplying something by itself. 
The x in this definition is called a formal parameter, which provides a name for the thing to be multiplied. 
The definition creates this user-defined function and associates it with the name square.
'''

We can also use twice as a building block in defining other functions.

1
2
def sum_square(x, y):
    return add(twice(x), twice(y))

User-defined functions are used in exactly the same way as built-in functions.
Both def statements and assignment statements bind names to values, and any existing bindings are lost.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
>>> def g():
...     return 1
...
>>> g
<function g at 0x773ce2b8e5e0>
>>> g()
1
>>> g=2
'''
第一个函数对象此时没有任何变量引用它，引用计数归零，
Python 的垃圾回收器（基于引用计数）会立即销毁这个函数对象，
并将其占用的内存（地址 0x773ce2b8e5e0）释放回 Python 的内存池（空闲链表）。
'''
>>> g
2
>>> def g(a,b):
...     return a+b
...
>>> g
<function g at 0x773ce2b8e5e0>
>>> g(1,2)
3

3.1 Environments

An environment in which an expression is evaluated consists of a sequence of frames, depicted as boxes. Each frame contains bindings, each of which associates a name with its corresponding value. There is a single global frame. Assignment and import statements add entries to the first frame of the current environment. So far, our environment consists only of the global frame.

The environment diagram shows the bindings of the current environment, along with the values to which names are bound.

Online Python Tutor, 非常好的可视化environment diagram
用这个代码试一下

1
2
3
4
5
6
7
from operator import add
def a():
    return 1

b = a
a = 6
c = add(b()+a, b())

The name of a function is repeated twice, once in the frame and again as part of the function itself. The name appearing in the function is called the intrinsic name. The name in a frame is a bound name.

The name bound to a function in a frame is the one used during evaluation. The intrinsic name of a function does not play a role in evaluation.

例如，上例中的a函数在定义时，a函数被绑定到名字a，同时这个函数的intrinsic name就是a，之后a函数被绑定到名字b

3.2 Calling User-Defined Functions

To evaluate a call expression whose operator names a user-defined function, the Python interpreter follows a computational process.

Applying a user-defined function introduces a second local frame, which is only accessible to that function. To apply a user-defined function to some arguments:

  1. Bind the arguments to the names of the function’s formal parameters in a new local frame.
  2. Execute the body of the function in the environment that starts with this frame.

Name Evaluation. A name evaluates to the value bound to that name in the earliest(注意这里最早找到的意思是从本地逐渐往上找(即往parent找)第一个找到的) frame of the current environment in which that name is found.

试试这个，需要高阶函数的知识，可以阅读后面的内容后再回来看

1
2
3
4
5
6
7
8
9
10
11
12
def make_adder(n):
    def adder(k):
        return k + n
    return adder

c = make_adder(1)(2)

'''
make_adder(1)既是一个call expression（调用make_adder，
即operator(的value为函数)为make_adder,
operand（的value为argument）为1），同时是一个operator
'''

注意到adder的frame，f2的parent是f1，所以在找n时，先在f2里找，找不到，去f1找，得到n=1

而在evaluate make_adder(1)时，就创建了一个local frame f1，这个frame里formal parameter n bound to the value 1

3.3 Example

1
2
3
4
5
6
7
8
from operator import add, mul
def square(x):
    return mul(x, x)
	
def sum_squares(x, y):
	return add(square(x), square(y))
	
result = sum_squares(5, 12)

All three local frames contain a binding for the name x, but that name is bound to different values in different frames. Local frames keep these names separate.

3.4 Local Names

We say that the scope of a local name is limited to the body of the user-defined function that defines it. When a name is no longer accessible, it is out of scope.

3.5 Choosing Names

Lowercase, with words separated by underscores

3.6 Functions as Abstractions

这里对abstraction的理解已经初现端倪

We can write sum_squares without concerning ourselves with how to square a number. The details of how the square is computed can be suppressed, to be considered at a later time.

square is not a particular function body, but rather an abstraction of a function, a so-called functional abstraction. At this level of abstraction, any function that computes the square is equally good.

这个程序和3.4节的程序完全等价

1
2
3
4
5
6
7
8
from operator import add, mul
def square(x):
	return x*(x-1) + x
	
def sum_squares(x, y):
	return add(square(x), square(y))
	
result = sum_squares(5, 12)

Aspects of a functional abstraction.

The domain of a function is the set of arguments it can take. The range of a function is the set of values it can return. The intent of a function is the relationship it computes between inputs and output (as well as any side effects it might generate).

For example, any square function that we use to implement sum_squares should have these attributes:

  • The domain is any single real number.
  • The range is any non-negative real number.
  • The intent is that the output is the square of the input.
    These attributes do not specify how the intent is carried out; that detail is abstracted away.

3.7 Operators

对于带有数学操作符的表达式，我们只需把它们看作是call expression，再利用call expression的evaluation procedure即可
例如(2+3)*(4+5)就等同于mul(add(2, 3), add(4, 5))

注意/结果是浮点数，//的结果是向下取整，例如-5 // 4 = -2

4 Designing Functions

Fundamentally, the qualities of good functions all reinforce the idea that functions are abstractions.

  1. Each function should have exactly one job. That job should be identifiable with a short name and characterizable in a single line of text. Functions that perform multiple jobs in sequence should be divided into multiple functions.
  2. Don’t repeat yourself is a central tenet of software engineering. The so-called DRY principle states that multiple fragments of code should not describe redundant logic. Instead, that logic should be implemented once, given a name, and applied multiple times. If you find yourself copying and pasting a block of code, you have probably found an opportunity for functional abstraction.
  3. Functions should be defined generally. Squaring is not in the Python Library precisely because it is a special case of the pow function, which raises numbers to arbitrary powers.

4.1 Documentation

A function definition will often include documentation describing the function, called a docstring, which must be indented(缩进) along with the function body.

1
2
3
4
5
6
7
8
def kinetic_energy(m, v):
    """
    Compute the kinetic energy of an object whose mass is m.

    v -- the velocity of the object
    m -- the mass of the object
    """
    return m * v * v / 2

可以在可交互解释器页面输入help(kinetic_energy)查看文档
docstring guidelines

4.2 Default Argument Values

In Python, we can provide default values for the arguments of a function. When calling that function, arguments with default values are optional. If they are not provided, then the default value is bound to the formal parameter name instead.

1
2
3
4
5
6
7
8
9
def pressure(v, t, n=6.022e23):
    """Compute the pressure in pascals of an ideal gas.

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