思维导图

值 Values

在 Python 中0o20为八进制的16，0b1101为二进制13，0x为十六进制。

还有字符串 string，元组 tuple，范围 range，列表 list，字典 dictionary，集合 set

函数 Functions，表达式 Expressions，环境 Environments

定义函数：

def saxb(a, x, b):
    return a * x + b

写成 λ 表达式（能当作表达式的函数）：

lambda a, x, b: a * x + b

Environment 是名称对值的映射
在环境中名称被绑定到值上
最外层环境叫 global environment frame

函数被称为第一类值 first-class values，可以作为某一函数的参数或返回值：

def add_func(f, g):

    def adder(x):
        return f(x) + g(x)

    return adder

>>> from math import sin,cos,pi
>>> h=add_func(sin,cos)
>>> sin(pi/4)+cos(pi/4)
1.414⋯
>>> h(pi/4)
1.414⋯

控制 Control

有if，while，for等。

双分支：True部分 if 条件 else False部分，类似于 C 语言的?:运算符

多分支：

if 条件1:
    语句1
elif 条件2:
    语句2
⋯
else:
    语句n

注：and和or有短路作用

注意缩进

递归 Recursion

一个函数只调用一次的叫做线性递归 Linear Recursion，在函数末尾调用的叫做尾递归 Tail Recursion，尾递归往往能写成循环形式。

如以下求平方和的程序：

"""循环形式："""
def sum_squares(N):
    """1^2+2^2+⋯N^2"""
    accum = 0
    k = 1
    while k <= N:
        accum = accum + k**2  #Python中两个乘号代表求幂
        k = k + 1
    return accum

"""尾递归（同时也是线性递归）形式："""
def sum_squares(N):

    def part_sum(accum, k):
        if k <= N:
            return part_sum(accum + k**2, k + 1)
        else:
            return accum

    return part_sum(0, 1)

防止无限递归的方法：确保每一次递归都减少了问题规模，直到最小的问题能被解决。

子问题与自我相似，例如分形问题

树递归 Tree Recursion：单次递归中多次调用递归函数

异常 Exception

可以使用try语句检查异常：

try:
    input = open(myfile).read()
except FileNotFoundError:
    print("Warning:could not open", myfile)
    input = ""

修饰器 Decorator

@ATTR
def afunc(⋯):
    ⋯

相当于：


def afunc(⋯):
    ⋯
afunc=ATTR(afunc)

容器 Container

Python 中的序列 Sequence有：

类型	元素	可编号	可变	可迭代
元组 tuple	任何类型	✓	×	✓
列表 list	任何类型	✓	✓	✓
字符串 string	str	✓	×	✓
范围 range	整形 integer	✓	×	✓
迭代器 iterator	任何类型	×	×	✓
生成器 generator	任何类型	×	×	✓

构造：

类型	写法	值
tuple	(1,4,"Hello",(2,3)) ()	1,4,"Hello",(2,3) 空序列
list	[1,4,"Hello",(2,3)] []	1,4,"Hello",(2,3) 空序列
range	range(4) range(1,12,2)	0,1,2,3 1,3,5,7,9,11

string 类型即可用''，也可用""

切片 slicing：

t = (2, 0, 9, 10, 11)

t[1:4] == (0, 9, 10)
t[2:] == (9, 10, 11)
t[::-1] == t[0:len(t):-1] == (11, 10, 9, 0, 2)

序列之间可以嵌套，相同序列可以相加：

A = [1, 2]
B = [7, 8, 9]
A + B == [1, 2, 7, 8, 9]
A * 3 == [1, 2, 1, 2, 1, 2]

for 循环

使用 for 循环可对可迭代对象迭代:

for x in range(10):
    print(x)

多变量迭代：

L = [(1, 9), (2, 8), (3, 7)]
for x, y in L:
    print(f"x,y=({x},{y})")

x,y=(1,9)
x,y=(2,8)
⋯

zip函数能将多个序列合并为一个，返回一个 generator

>>> list(zip([1,2,5,3],[9,2,6,3,10]))
[(1,9),(2,2),(5,6),(3,3)]

for，if，list综合应用：

[表达式 for 变量 in 序列表达式 if boolean表达式]

可以嵌套for循环：
>>> [(a,b)for a in range(10,13) for b in range(2)]
[(10, 0), (10, 1), (11, 0), (11, 1), (12, 0), (12, 1)]

所以 Python 程序总是写成一行，让人很难理解。

数据抽象 Data Abstraction

抽象数据类型 Abstract data type（ADT）
接口 interface
API：Application Programming Interface 应用编程接口
constructor：例如 pair
accessor：例如 left 和 right
mutator：例如 set_left 和 set_right

字典 dictionary，矩阵 matrix，树 tree

dictionary相当于键值对的映射，排序方式为插入顺序：

words={"ljkadf":"fadjosodfsij","jfoe":"aewffe"}
words["ljkadf"]=="fadjosodfsij"

矩阵实现：

def matrix(rows, cols):
    return [[0 for col in range(cols)] for row in range(rows)]
def value(matrix, row, col):
    return matrix[row][col]
def set_value(matrix, row, col, val):
    matrix[row][col] = val

树的实现（list+tuple）：

def tree(label, children=[]):
    return (label, children)
def label(tree):
    return tree[0]
def children(tree):
    return tree[1]
def is_leaf(tree):
    return len(children(tree)) == 0
def count_leaves(t):
    if (is_leaf(t)):
        return 1
    else:
        children_leaves = 0
        for c in children(t):
            children_leaves += count_leaves(c)
        return children_leaves

将树上的值翻倍：

非破坏性操作 Non-destructive：

def tree(label, children=[]):
    return (label, children)
def label(tree):
    return tree[0]
def children(tree):
    return tree[1]
def is_leaf(tree):
    return len(children(tree)) == 0
def double(t):
    """返回一棵树"""
    if (is_leaf(t)):
        return tree(label(t) * 2)
    else:
        doubled_children = []
        for c in children(t):
            doubled_children.append(double(c))
        return tree(label(t) * 2, doubled_children)

破坏性操作 Destructive：

def tree(label, children=[]):
    return [label] + children
def label(tree):
    return tree[0]
def children(tree):
    return tree[1:]
def is_leaf(tree):
    return len(children(tree)) == 0
def set_label(tree, label):
    tree[0] = label
def set_children(tree, children):
    tree[1] = children

def double(t):
    """直接在原树上修改"""
    set_label(t, label(t) * 2)
    if not is_leaf(t):
        for c in children(t):
            double(c)

方法一中的树为不可变的 immutable，方法二中的是可变的 mutable

tuple 不可变，但可以修改其中的 list 中的值（因为 tuple 中存的类似于 list 的内存地址）

append()：在 list 后添加一个元素
extend()：在 list 后添加另一个 list 中的所有元素
pop()：删除并返回最后一个元素
remove(x)：删除第一个和x相同的参数

相等 Equality 和同一 Identity

Identity: a is b
Equality: a == b

Identity 可以理解为指向同一位置的指针

迭代器 Iterator 和生成器 Generator

iter(可迭代对象)返回一个迭代器
next(迭代器)返回迭代器的下一个元素

L = [1, 2, 3, 4]
it1 = iter(L)
next(it1)  #1

"""本质上调用了__iter__()和__next__()对象"""
it2 = L.__iter__()
it2.__next__()  #1

返回 iterator 的函数：

reversed(序列)：返回相当于反迭代器
map(func,可迭代对象)：对于每一个可迭代对象中的元素x调用func(x)，相当于[func(x) for x in 可迭代对象
filter(func,可迭代对象)：返回满足func(x)的可迭代对象中的每一个元素x，相当于[x for x in 可迭代对象 if func(x)

sorted(可迭代对象,key=None,reverse=False)：返回按照key函数排序好的列表

generator是一种 iterator，其由 generator function 生成

generator function使用yield代替return

def evens():
    num = 0
    while num < 10:
        yield num
        num += 2

使用时：
>>> evengen=evens()
>>> next(evengen)
0
>>> next(evengen)
2
>>> next(evengen)
4

generator 的优点在于只在需要的时候生成下一项

对象 Object 和类 Class

Python 中使用__和_给变量命名表示私有变量，但仍可强行从外部访问

继承 Inheritance 和组合 Composition

继承的声明方法：class Lion(Animal):

可使用super().__init__()调用基类的__init__()方法

Inheritance 表示"is-a"关系，Composition 表示"has-a"关系

特殊对象方法 Special Object Methods

Python 中所有类型都是对象，都继承自object类

dir()返回所有对象属性的列表

__init__(self)方法在对象被实例化时调用，第一个参数为自身
__str__()控制print()的输出，str()的转换之类
__repr__()返回构造相同对象的字符串
getattr(对象,变量名[,默认值])在对象中查找该名称的变量值，若没有找到，返回AttributeError或默认值，背后调用的是__getattribute__()方法
hasattr(对象,变量名)在对象中查找该名称的变量值并返回是否找到，背后调用的也是__getattribute__()

还有其它的：

方法	实现	方法	实现
`__setattr__(obj,"n",v)`	`x.n=v`	`__delattr__(obj,"n")`	`del x.n`
`__eq__(obj,x)`	`obj==x`	`__ne__(obj,x)`	`obj!=x`
`__ge__(obj,x)`	`obj>=x`	`__gt__(obj,x)`	`obj>x`
`__le__(obj,x)`	`obj<=x`	`__lt__(obj,x)`	`obj<x`
`__getitem__(S,k)`	`S[k]`	`__setitem__(S,k,v)`	`S[k]=v`
`__len__(S)`	`len(S)`	`__sub__(S,x)`	`S-x`
`__mul__(S,x)`	`S*x`

复杂度 Complexity

无论 $n$ 有多大，总有 $K_1g(n) ≤ f(n) ≤ K_2g(n)$ ，记作 $f(n) ∈ Θ(g(n))$ （有的也写作 $f(n) = Θ(g(n))$ ）

记忆化 Memoization

凑钱问题：

普通递归解法：

def count_change(amount, coins=(50, 25, 10, 5, 1)):
    if amount == 0:
        return 1
    elif amount < 0 or len(coins) == 0:
        return 0
    else:
        return count_change(amount, coins[1:]) + count_change(amount - coins[0], coins)

观察到有大量的重复计算，可使用记忆表 memorize table储存已算出的值：

def count_change(amount, coins=(50, 25, 10, 5, 1)):
    memo_table = [[-1] * (len(coins) + 1) for i in range(amount + 1)]

    def count_change(amount, coins):
        if amount < 0:
            return 0
        elif memo_table[amount][len(coins)] == -1:
            memo_table[amount][len(coins)] = full_count_change(amount, coins)
        return memo_table[amount][len(coins)]

    def full_count_change(amount, coins):
        if amount == 0:
            return 1
        elif amount < 0 or len(coins) == 0:
            return 0
        else:
            return count_change(amount, coins[1:]) + count_change(amount - coins[0], coins)

    return count_change(amount, coins)

观察到总是 amount 小且使用 coins 少的先计算出，所以可以用循环控制顺序，即动态规划 Dynamic Programming：

def count_change(amount, coins=(50, 25, 10, 5, 1)):
    memo_table = [[-1] * (len(coins) + 1) for i in range(amount + 1)]

    def count_change(amount, coins):
        if amount < 0:
            return 0
        return memo_table[amount][len(coins)]

    def full_count_change(amount, coins):
        if amount == 0:
            return 1
        elif amount < 0 or len(coins) == 0:
            return 0
        else:
            return count_change(amount, coins[1:]) + count_change(amount - coins[0], coins)

    for a in range(0, amount + 1):
        memo_table[a][0] = full_count_change(a, ())
    for k in range(1, len(coins) + 1):
        for a in range(0, amount + 1):
            memo_table[a][k] = full_count_change(a, coins[-k:])
    return count_change(amount, coins)

泛型 Generics

鸭子类型 Duck typing通过鸭子测试，即多种类型具有相同的性质，都适用于同一个函数

def sum(items, initial_value):
    sum = initial_value
    for item in items:
        sum += item
    return sum

该函数就是一个泛型函数，只要items满足能迭代，可相加即可

f string：使用{变量名}表示变量值而不是字符串

str.join(可迭代对象)用法：

print("\n".join((1,2)))

"""
1
2
"""

Scheme

Scheme是Lisp的一种方言

applicative programming应用程序编程：没有副作用、破坏性操作、赋值的程序，更便于并行编程

scheme 的数据有atom 原子和pair

atom 包括：

数字：整数、浮点、复数、有理数
symbol：类似于 string
boolean：#t，#f
空列表：()
procedure

列表表示为：(V1.(V2.(⋯(Vn.()))))，~~数不尽的括号~~

Scheme programs are Scheme data，都类似于(OP E1 ⋯ En)，例如：表达式(+(* 3 7) (- x))也是一个列表，在 Scheme 中，其已经是一棵abstract syntax tree 抽象语法树了

quotation 引用：

scm> (+ 1 2)
3
scm> '(+ 1 2)
(+ 1 2)
scm> (quote (1 2 '(3 4)))
(1 2 '(3 4))

其它特别的形式：

(if (> x y) x y)
(define pi 3.14)
(define (f x) (* x x))
(lambda (x y) (/ (* x x) y))
(cond ((< x 1)'small)
    (< x 3)'medium)
    (< x 5)'large)
    (#t 'big))

对应于 python 中的：

x if x > y else y
pi = 3.14
def f(x):
    return x * x
lambda x, y: x * x / y
"small" if x < 1 else "medium" if x < 3 else "large" if x < 5 else "big"

一些表达式：

scm> (/ 3 2)
1.5
scm> (quotient 3 2) ;向0取整
1
scm> (integer? 5)
#t
scm> (= 1 (- 2 1));只对数字有效
#t
scm> (eqv? 1 2);对数字，空列表，bool，symbols都有效
#f

pairs：

scm> (cons 'a (cons 'b '()))
(a b)
scm> (define L '(a b c))
scm> (car L)
a
scm> (cdr L)
(b c)

Let 形式：

scm> (let ((x 5)
    (y (+ x 2)))
    (+ x y))
相当于：
scm> ((lambda (x y) (+ x y)) 5 (+ x 2))

不可判定性 Undecidability

停机问题 halting problem研究的是：是否存在一个「程序」，能够判断另外一个「程序」在特定的「输入」下，是会给出结果（停机），还是会无限执行下去（不停机）。

类似于理发师悖论，解决方法为：

"""假设有一个程序is_halt能实现该功能："""
def is_halt(program, input) -> bool:
  # 返回 True  如果 program(input) 会返回
  # 返回 False 如果 program(input) 不返回

def loop():
  while(True):
      pass

def hack(program):
  if is_halt(program, program):
    loop()
  else:
    return

"""你会发现，如果「停机程序」认为 hack(hack) 会给出结果，即 is_halt(hack, hack)返回 True ，那么实际上 hack(hack) 会进入无限循环。
而如果「停机程序」认为 hack(hack) 不会给出结果，即 is_halt(hack, hack) 返回 false，那么实际上 hack(hack) 会立刻返回结果……"""

is_halt(hack, hack)

所以：程序不是万能的！，也没有完美的防毒软件

哥德尔不完全性定理：任意一个包含一阶谓词逻辑与初等数论的形式系统，都存在一个命题，它在这个系统中既不能被证明为真，也不能被证明为否。

宏 Macro

在 C 语言中在预编译器中进行，类似于查找替换。在 scheme 中功能更强大，相当于写了一个程序但并不执行它，其中操作数并不计算，但要注意变量名字不要和代码中的重复了。

;与其写
(if (not (list? x)) (displayln x))

;可以用宏代替
(define-macro (unless cond body)
`(if (not ,cond) ,body))

(unless (list? x) (displayln x))

声明式编程 Declarative Programming

与之相对的是命令式编程 Imperative Programming，注重如何实现一些计算~~相当于只能苦苦码字的程序员~~；而声明式编程关注结果，让计算机思考如何得到结果~~相当于只会下命令给员工的老板~~。

正则表达式 Regular Expressions

详见：正则表达式

注意：Python 中记得在字符串之前加r，表示为原字符串，否则\会被转义

巴科斯范式 BNF

巴科斯范式（BNF）所描述的语法是与上下文无关的。它具有语法简单，表示明确，便于语法分析和编译的特点。

图形化表示：铁路图 Railroad Diagram

以一个算术表达式为例：

expression = term , {"+" term};
term = factor , {"*" factor};
factor = constant | variable | "(" , expression , ")";
variable = "x" | "y" | "z";
constant = digit , {digit};
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";

对应的铁路图为：