摘要

本文为《计算机程序的构造和解释》（SICP，CS61A 南大引进版）python部分期中后课程核心笔记，聚焦程序设计的底层逻辑与核心思想，旨在帮助学习者搭建“知其然更知其所以然”的编程认知框架。适合正在学习 CS61A 课程的学习者梳理知识体系，也可作为编程入门者夯实基础、理解程序设计本质的参考资料。

SICP_python_期中后笔记

拓展

1. Imperative Programming（命令式编程）

核心思想

通过一系列指令（statements）改变程序的状态（state）来完成计算。 关注 HOW（具体步骤）。

特征

• 有可变变量（variables）
• 通过赋值（assignment）改变状态
• 使用控制结构（control flow）：if / for / while
• 程序表现为逐步执行的过程

常见语言

C、C++、Java、Python、JavaScript、Go、Rust

适用场景

操作系统、游戏开发、需要精确流程控制或高性能的系统

2. Functional Programming（函数式编程）

核心思想

以数学函数为基础，不依赖可变状态，通过函数组合完成计算。 关注 WHAT（要做什么）。

特征

• 不可变性（immutability）
• 纯函数（pure functions），无副作用（side effects）
• 函数是一等公民（first-class functions）
• 常用递归（recursion）
• map / filter / reduce 是典型操作

常见语言

Haskell、Lisp、OCaml、F#；Python/JavaScript 可写函数式风格

示例（Python）

numbers = [1, 2, 3]
result = list(map(lambda x: x + 1, numbers))

适用场景

数学计算、并行计算、金融系统、需要高可预测性的程序

3. Logic Programming（逻辑式编程）

核心思想

使用事实（facts）和规则（rules）描述问题，由系统进行自动推理（inference）。 关注 WHAT（描述规则），系统决定 HOW（如何推导）。

特征

• 程序由 facts + rules + queries 组成
• 基于一阶逻辑（first-order logic）
• 使用分辨率（resolution）进行推理
• 强调声明式描述

常见语言

Prolog（代表性语言）

示例（Prolog）

parent(tom, bob).
parent(bob, ann).

grandparent(X, Y) :- parent(X, Z), parent(Z, Y).

适用场景

人工智能、知识库、规则引擎、专家系统

4. 三种范式对比总结

编译器理解: 词法 -> 语法 -> 语义

Lexical（词法）

把字符拆成最小有意义单位（token）。 识别：变量名、关键字、数字、字符串、运算符、符号等。 作用：告诉编译器“这串字符是什么词”。

Syntax（语法）

检查 token 是否能组成合法的结构。 作用：决定一句代码的结构是否符合语言规则（是否“通顺”）。

Semantics（语义）

代码表达的实际含义与执行效果。 作用：定义语句运行后会做什么、得到什么结果。

代码风格:类型提示(type hint)

检查 Python 版本：

import platform
print(platform.python_version())
3.12.7

安装 MyPy ：

$ python -m pip install mypy

使用 MyPy 进行类型检查：

$ mypy program.py

1. 变量 (Variables)

声明变量类型 使用冒号 : 来声明变量类型。

age: int = 1

未初始化的变量注解 不需要立即给变量赋值即可添加注解。这在条件分支赋值中非常有用（运行时直到赋值前没有具体值）。

a: int  # 合法

# 示例：在条件分支中使用
child: bool
if age < 18:
    child = True
else:
    child = False

2. 常用的内置类型 (Useful Built-In Types)

基本类型 大多数情况下，直接使用类型名称即可。 注意：mypy 通常能推断出变量类型，因此显式注解在技术上是冗余的，但有助于代码清晰。

x: int = 1
x: float = 1.0
x: bool = True
x: str = "test"
x: bytes = b"test"

集合类型 (Collections) - Python 3.9+ 集合内元素的类型放在方括号 [] 中。

• 列表 (List): x: list[int] = [1]
• 集合 (Set): x: set[int] = {6, 7}

映射类型 (Mappings) 需要同时指定键 (Key) 和值 (Value) 的类型。

• 字典 (Dict): x: dict[str, float] = {"field": 2.0}

元组 (Tuples)

• 固定大小: 需要指定所有元素的类型。 x: tuple[int, str, float] = (3, "yes", 7.5)
• 可变大小: 使用一种类型加上省略号 ...。 x: tuple[int, ...] = (1, 2, 3)

联合类型 (Union Types) - Python 3.10+ 当值可能是多种类型之一时，使用 | 运算符。

x: list[int | str] = [3, 5, "test", "fun"]

可选类型 (Optional Types) 对于可能为 None 的值，使用 X | None。

x: str | None = "something" if some_condition() else None

# 类型缩窄 (Type Narrowing)
if x is not None:
    print(x.upper())  # Mypy 知道此处 x 不为 None

# 如果逻辑上确定不为 None 但 mypy 无法推断，可使用 assert
assert x is not None
print(x.upper())

3. 函数 (Functions)

函数定义注解 使用 -> 指定返回类型。

def stringify(num: int) -> str:
    return str(num)

多个参数

def plus(num1: int, num2: int) -> int:
    return num1 + num2

无返回值 如果函数不返回值，返回类型使用 None。

• 默认值: 参数的默认值写在类型注解之后。

def show(value: str, excitement: int = 10) -> None:
    print(value + "!" * excitement)

动态类型 (Dynamic Typing)

• 未指定类型的参数会被视为 Any（动态类型）。
• 没有任何注解的函数不会被类型检查器检查。

def untyped(x):
    x.anything() + 1 + "string"  # 不会报错

可调用对象 (Callables) 用于注解函数作为参数传递的情况（需要从 collections.abc 导入）。 格式：Callable[[参数类型列表], 返回类型]

from collections.abc import Callable

def f(x: int, y: float) -> float:
    return x + y

x: Callable[[int, float], float] = f

生成器 (Generators) 生成器函数实际上是返回一个迭代器，因此使用 Iterator 进行注解。

from collections.abc import Iterator

def gen(n: int) -> Iterator[int]:
    i = 0
    while i < n:
        yield i
        i += 1

多行函数注解 当参数较多时，可以将注解拆分为多行。

def send_email(
    address: str | list[str],
    sender: str,
    cc: list[str] | None,
    bcc: list[str] | None,
    subject: str = '',
    body: list[str] | None = None,
) -> bool:
    ...

主题 1：面向对象编程基础 (Object-Oriented Programming, OOP)

主题概述

• OOP 是一种组织程序的方法，将数据（属性 Attributes）和行为（方法 Methods）捆绑在一起。每个对象拥有自己的局部状态 (Local State)，不同对象之间通过方法调用进行交互。

• 这是一种以“对象（objects）”为中心的程序设计方法。对象把数据（属性 attributes）和操作这些数据的行为（方法 methods）封装在一起，通过对象之间的交互来完成程序的功能。

• 每个对象都有两个特点：

1. 它有什么（属性 / 数据）

2. 它能做什么（行为 / 方法）

• OOP 的三要素（经典版本）

1. 封装（Encapsulation）：把数据与操作封在对象内部，对外提供有限接口。

2. 继承（Inheritance）：子类可以继承父类的属性和方法，实现代码复用。

3. 多态（Polymorphism）：同一方法名在不同对象上有不同实现，运行时动态决定调用哪个版本。

一句话总结

• 正经版：OOP = 用对象来组织程序，数据 + 行为一起封装，通过继承复用，通过多态扩展。

• 形象版：OOP = 把程序写成一堆“现实世界中的小东西”，每个东西都有属性、有行为，它们互相合作，程序就跑起来了。

创建对象，让对象自己按照规则做事

核心概念 (Core Concepts)

1. 类与实例 (Classes and Instances)

• 类 (Class): 对象的模板。定义了所有实例共享的属性和行为。
• 实例 (Instance): 类的具体实现。例如，Account 是类，tom_account 是一个实例。
• 构造函数 (__init__): 当创建一个新实例时自动调用的方法，用于初始化实例属性。
• self: 指向当前正在被操作的实例。在类内部定义方法时，第一个参数通常是 self。

2. 属性查找机制 (Attribute Lookup)

当我们求值 <expression>.<name> 时，解释器遵循以下顺序：

1. 求值点号左边的 <expression>，得到一个对象。
2. 查找实例属性: 在该对象的实例属性中查找 <name>。如果找到，返回其值。
3. 查找类属性: 如果实例中没找到，去创建该对象的类中查找。
4. 查找父类: 如果类中没找到，沿着继承链向上查找。
5. 如果找到的是一个函数，则返回一个绑定方法 (Bound Method)。

注意： 赋值操作 (obj.x = 1) 总是会在实例上创建或修改属性，而不会修改类属性。

3. 点表达式的评估（Evaluation of Dot Expression）

<expression>.<name>

• 求值点号左侧expression，返回对象
• 将 与该对象的实例属性进行匹配；如果存在具有该名称的属性，则返回其值。
• 否则，在类中一层一层向上查找 ，这将产生一个类属性值（如果不存在这样的类属性，则会报告 AttributeError）。
• 不是函数 -> 返回该值；
• 是函数 -> 返回绑定方法，且将self传入第一个参数。

• 例题

• 例1: 封装（Encapsulation）

• Why we need Encapsulation:

  • Protect data security
  • Reduce coupling

例1
    # class attribute
    interest = 0.02

    # constructor
    def __init__(self, account_holder): 
        self.balance = 0 # instance attribute
        self.holder = account_holder
    
    # methods
    def deposit(self, amount): 
        self.balance += amount
        return self.balance
    
    def withdraw(self, amount):
        if amount > self.balance:
            return 'Insufficient funds'
        self.balance -= amount
        return self.balance

jacy = Account('Jacy') 
"""
>>> jacy.balance
0
>>> jacy.deposit(10)
10
>>> jacy.withdraw(5)
5
"""

• 例2：类属性查找（Class attribute lookup）

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. 否则，在基类中查找该名称（如果有的话）。

例2
class A:
    z = -1
    def f(self, x):
        return B(x - 1)
    def __repr__(self):
        return 'A()'
    
class B(A):
    n = 4
    def __init__ (self, y):
        if y:
            self.z = self.f(y)
        else:
            self.z = C(y + 1)
    def __repr__(self):
        return f'B(z={self.z})'

class C(B):
    def f(self, x):
        return x
    def __repr__(self):
        return f'C(z={self.z})'

a = A()
b = B(1)
b.n = 5

>>> C(2).n
4
>>> a.z == C.z
True
>>> a.z == b.z
False
>>> b
B(z=B(z=C(z=1)))

#为什么C的z是1呢？
#B中的z是一个instance attribute，理论上C在B中找不到不应该去A中找然后得到z=-1吗？
#因为C没有init！！！所以C在创建instance 的时候就会调用一次B的init，
#从而在执行init的时候获得一个z！
#C 继承 B 的 init ，所以走 B.init：
# y = 1   非零
# self.z = self.f(1)
# 但这次 self 是 C 的实例，所以调用的是 C.f：
# C.f(self, 1) → return 1
# 因此：
# C(1).z = 1

>>> b.z
B(z=C(z=1))
>>> b.z.z
C(z=1)
>>> b.z.z.z
1
>>> b.z.z.z.z
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'int' object has no attribute 'z'

拓展:LSP: 里氏替换原则：

• 凡是出现基类的地方，都可以用子类替换它，而不会影响程序的功能。
• 这意味着子类可以使用基类的所有操作而不出现问题

>>>class T:
...    pass
...class S(T): # inheritance creats subtypes
...    pass
>>>t = T()
>>>s = S()	
>>>isinstance(t, T)	
True	
>>>isinstance(s, S)	
True
>>>isinstance(s, T)	
True

3. 方法 (Methods)

• 函数 (Function): 也就是普通的 Python 函数。
• 绑定方法 (Bound Method): 将函数与特定对象（实例）“绑定”在一起。调用时，Python 会自动将该对象作为第一个参数 (self) 传入。
• Account.deposit 是函数 (Function)。
• tom.deposit 是方法 (Method)。

主题 2：继承与组合 (Inheritance & Composition)

主题概述

继承允许我们基于已有的类创建新类，实现代码复用和特化。组合则是通过将其他对象作为属性来实现复杂功能。

核心概念 (Core Concepts)

1. 继承 (Inheritance)

• 子类 (Subclass) 继承 基类 (Base Class) 的所有属性和方法。
• 重写 (Overriding): 子类可以重新定义与父类同名的方法，从而改变行为。
• super(): 用于在子类中调用父类的方法，常用于扩展 __init__ 或复用父类逻辑。
• 代码示例：

class CheckingAccount(Account): # 继承 Account
    withdraw_fee = 1
    interest = 0.01

    def withdraw(self, amount):
        # 复用父类的 withdraw 方法，加上手续费
        return Account.withdraw(self, amount + self.withdraw_fee)

2. 多重继承 (Multiple Inheritance)

• 一个类可以继承自多个父类。
• 拓展：菱形问题 (Diamond Problem): 当多个父类继承自同一个祖先时，Python 使用 C3 线性化算法 确定 方法解析顺序 (MRO)，确保每个类只被访问一次。

3. 继承 vs. 组合 (Inheritance vs. Composition)

这是面向对象设计的核心权衡：

• 继承 (“Is-a” 关系): CheckingAccount 是一个 Account。用于特化。
• 组合 (“Has-a” 关系): Bank 有一个 Account 列表。用于通过聚合现有组件来构建复杂对象。

主题 3：多态(Ploymorphism)

分类

• 特设多态（Ad Hoc Ploymorphism）：同名methon但是不同实现规则

  • 操作符重载（operator overloading）: 同样运算符，不同操作方式

    e.g. x + y 本质上是 x.__add__(y) 。

    x == y 本质上是 x.__eq__(y) 。

  • 多态函数（polymorphism）: 函数根据输入类型改变行为

• 参数多态（parametric polymorphism）: 泛型多态（拓展）

from typing import TypeVar, List
T = TypeVar('T')

def first(lst: List[T]) -> T:
    return lst[0]

• 包含多态（inclusion polymorphism）: 继承多态，子类代替父类使用

主题 4：特殊方法 (Special Methods)

主题概述

特殊方法（也称魔术方法，以双下划线开头和结尾）允许自定义对象表现得像 Python 的内置类型。这是实现 多态 (Polymorphism) 的关键。

核心概念 (Core Concepts)

1. 字符串表示(repr & str)

区别

例题：

class Fraction:
    def __init__(self, n, d): self.n, self.d = n, d
    def __repr__(self): return f"Fraction({self.n}, {self.d})"
    def __str__(self): return f"{self.n}/{self.d}"

f = Fraction(1, 2)
print(f)       # 输出: 1/2 (调用 __str__)
f              # 输出: Fraction(1, 2) (调用 __repr__)

[易错]关于引号…

1. str和repr的区别

• 示例

s = "hello"
print(str(s))   # hello
print(repr(s))  # 'hello'

repr 的目标是 让结果能用于重新构造对象：

eval(repr(s)) == s  # True

2. print()和交互式解释器输出的区别

• 示例：

在 REPL 中：

>>> "hello"
'hello'

>>> print("hello")
hello

3. 自定义类的 __str__ 和 __repr__

如果类同时定义了 __str__ 和 __repr__：

eval() 是 Python 内置函数，用来 将字符串当作 Python 表达式求值，然后返回表达式的结果。 示例：

class A:
    def __str__(self):
        return "str display"
    def __repr__(self):
        return "repr display"

a = A()
print(a)   # str display
a          # repr display
#没有引号!!

repr函数会将接收到的参数变成一个字符串交给交互式解释器,然后交互式解释器去掉最外一层引号的内容把字符串里的内容显示出来

>>> a = 1
>>> a
1
>>> repr(a)
'1'
>>> repr('1')
"'1'"
>>> eval(repr('1'))
'1'
>>> eval(repr(a))
1
>>> eval(a)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
    eval(a)
    ~~~~^^^
TypeError: eval() arg 1 must be a string, bytes or code object

• 检验理解!

>>> class A:
...     def __init__(self, x):
...         self.x = x
...     def __repr__(self):
...         return self.x
...     def __str__(self):
...         return self.x * 2
>>> class B:
...     def __init__(self):
...         print('boo!')
...         self.a = []
...     def add_a(self, a):
...         self.a.append(a)
...     def __repr__(self):
...         print(len(self.a))
...         ret = ''
...         for a in self.a:
...              ret += str(a)
...         return ret
>>> A('one')
? one

>>> print(A('one'))
? oneone

>>> repr(A('two'))
? 'two'

>>> b = B()
? boo!

>>> b.add_a(A('a'))
>>> b.add_a(A('b'))
>>> b

(line 1)? 2
(line 2)? aabb

• repr() 的用途总结

2. 运算符重载 (Operator Overloading)

• __add__: 定义 + 操作符的行为。例如 obj1 + obj2 会变成 obj1.__add__(obj2)。
• 多态 (Polymorphism): 同一个操作符（如 +）可以根据操作数类型的不同（如整数相加 vs. 字符串拼接）表现出不同的行为。

主题 4：递归数据结构 (Linked Lists & Trees)

主题概述

链表和树是基于递归 (Recursion) 定义的数据结构。它们是 CS61A 中处理复杂数据的基石。

核心概念 (Core Concepts)

1. 链表 (Linked Lists)

链表要么是空的，要么由一个元素 (first) 和剩余链表 (rest) 组成。

• 处理技巧:

• 递归处理: Base case 通常是 lnk is Link.empty。

• 迭代处理: while lnk is not Link.empty: ... lnk = lnk.rest。

• 常用操作: map (映射), filter (过滤) 在链表上的实现。注意链表通常是可变 (Mutable) 的。

#链表结构实现
class Link:
    empty = ()
    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        """返回链表的可读字符串（如 <1 2 3>）"""
        def helper(lnk):
            if lnk is Link.empty:
                return []
            first_str = helper(lnk.first) if isinstance(lnk.first, Link) else [str(lnk.first)]
            rest_str = helper(lnk.rest)
            return first_str + rest_str
        elements = helper(self)
        return f"<{' '.join(elements)}>"
#链表操作方式
#求和
def sum_links(lnk):
    if self is Link.empty:
            return 0
        current = self.first.sum_links() if isinstance(self.first, Link) else self.first
        rest_sum = self.rest.sum_links() if isinstance(self.rest, Link) else 0
        return current + rest_sum

#表示
def display_link(link):
    str_num = ''
    while link is not Link.empty:
        if isinstance(link.first, Link):
            elem = display_link(link.first)
        elif isinstance(link.first, int):
            elem = str(link.first)
        str_num += elem
        link = link.rest
    print(f'<{' '.join(str_sum)}>')

#映射
def map(f, lnk):
    if lnk is Link.empty:
        return Link.empty
    
    return Link(f(lnk.first), map(f, lnk.rest))

2. 树 (Trees)

树由一个根标签 (Root Label) 和一组分支 (Branches) 组成。每个分支本身也是一棵树。

• Tree 类定义：

class Tree:
    def __init__(self, label, branches=[]):
        self.label = label
        # 确保每个分支都是 Tree 的实例，并复制列表以防副作用
        for b in branches:
            assert isinstance(b, Tree)
        self.branches = list(branches)

    def is_leaf(self):
        return not self.branches

• 核心术语:

• Node (节点): 树中的任何位置。

• Leaf (叶子): 没有分支的节点 (branches 为空)。

• 递归处理模式:

• 处理当前节点的 label。

• 使用 for b in t.branches: 循环递归处理每个分支。