高级编程语言设计与实现复习

复习指南：

本资料归纳总结了课程课件，仅用于简单复习；如若奔着拿高分满分，还请回归原 PPT 教材。

资料总结借助了 Gemini 3 Pro 和 ChatGPT 5.1 Thinking 的神力，并且由本人简单核查归纳了一下。

0. 课程导论 (Course Overview)

0.1 编程语言的定义与本质

定义：连接现实世界和计算机世界的桥梁，人与计算机交流的工具。
交流内容：计算、通信、世界建模。
核心观点 (SICP名言)：计算机科学本质上是构建恰当描述性语言的学科。

0.2 编程语言的核心关注点

易用性（Usability）：
- 语言设计（语法、语义、抽象级）。
- 工具支持（IDE、调试、构建）。
高性能（Performance）：
- 编译器/解释器优化、运行时效率、并行化。
软件质量（Reliability/Safety）：
- 类型安全、内存安全、并发安全。
- 动静态检查、形式化验证。

1. 编程语言导论 (Introduction)

1.0 编程语言发展史

演进路径：机器语言 (0101) -> 汇编语言 -> 高级语言。
关键语言里程碑：
- 1957 Fortran：科学计算，第一个高级语言。
- 1958 Lisp：函数式编程鼻祖，AI 领域，引入 GC、Lambda。
- 1967 Simula：面向对象鼻祖。
- 1972 C：系统编程，影响深远。
- 1972 Smalltalk：纯面向对象，消息传递。
- 1995 Java：虚拟机，跨平台，安全性。
- 2010s：Rust (内存安全), Go (云原生), Swift/Kotlin (移动端), TypeScript (前端类型安全)。

1.1 核心概念

编程语言的定义：人与计算机交流的工具。
- 人：追求简单、高效、易读（Write & Read）。
- 机器：追求执行效率、资源消耗少（Execute）。
三个核心维度：
1. 效率（Efficiency）：开发效率，表达力强，易于抽象。
2. 性能（Performance）：运行速度快，内存/能耗少。
3. 安全（Safety）：类型安全，内存安全，并发安全。
- 权衡（Trade-off）：通常难以兼顾三者（如 C++ 重性能轻安全，Python 重效率轻性能）。

1.2 语言分类

按应用场景：
- 轻量业务：JS, Python, Lua, Ruby
  - 动态脚本语言：“串珠子的绳子”；代码量小、快速编写、解释执行；不追求安全与性能；语言开发容易，种类繁多
- 重业务：Java, Go, C#, Swift
  - 静态类型App开发语言：面向开放场景，追求应用生态：吸引开发者；代码规模较大，平衡性能、安全与易用性；静态类型、类型安全、自动内存管理
- 系统编程：C, C++, Rust
  - 性能优先，底层控制能力（内存/硬件），对开发者要求高。
按计算模型/编程风格：
- 命令式（Imperative）：
  - 计算模型：图灵机；
  - 通过命令序列修改机器状态（变量赋值）完成计算。
  - 例：C, Java, Go
- 函数式（Functional）：
  - 计算模型： $λ$ -演算
  - 通过函数组合完成计算，强调无副作用，数据不可变。
  - 例：Lisp, Haskell, ML
- 面向对象（Object-Oriented）：
  - 数据 (属性)与计算 (行为)封装。
  - 例：Smalltalk, Java
- 逻辑式（Logic）：基于谓词逻辑。例：Prolog
按执行方式：
- 静态编译（Static Compilation）：源码 -> 机器码 -> 硬件执行。
  - 优点：快；
  - 缺点：开发周期长，难以动态修改。
  - 例：C, C++, Rust
- 动态解释（Dynamic Interpretation）：源码 -> 解释器/虚拟机执行。
  - 优点：灵活，跨平台；
  - 缺点：慢。
  - 例：Python, JS
- 字节码/虚拟机（Bytecode/VM）：源码 -> 字节码 -> 虚拟机 (JIT编译为机器码)。
  - 折中方案。
  - 例：Java, C#, Lua
按类型系统：
- 静态类型 vs 动态类型：编译期检查 vs 运行期检查。
- 强类型 vs 弱类型：是否允许隐式类型转换（弱类型如 C/C++ 允许指针乱转，不安全）。

1.3 编程范式 (Paradigms)

命令式（Imperative）：
- 关注 “怎么做”（How）。
- 基于冯·诺依曼模型，通过修改状态（变量赋值）完成计算。
- 典型：C, Pascal, Assembly。
面向对象（OO）：
- 封装数据（属性）与行为（方法）。
- 核心：封装、继承、多态。
- 典型：Java, Smalltalk。
函数式（Functional）：
- 关注 “做什么”（What）。
- 基于 $λ$ -演算，无副作用 (Side-effect free)，不可变数据。
- 核心：高阶函数、闭包、模式匹配。
- 典型：Haskell, Lisp, ML。

1.4 语言发展趋势

多范式融合：OO与FP的界限模糊，如Rust、Scala、Swift。
安全性增强：
- 内存安全：Rust的所有权机制。
- Null Safety：消除“十亿美元的错误”（Null Pointer Exception），如Kotlin, Swift, Cangjie中的 Option/? 类型。
类型系统进化：从动态向静态靠拢（TypeScript, Python Type Hints），Gradual Typing（渐进式类型）。
大模型的影响：自然语言不会完全取代编程语言，因为编程语言是无二义性的数学语言，是精确表达逻辑的工具。未来编程语言需更易于AI生成和人类审核（易读 > 易写）。

2. 仓颉语言概览 (Cangjie Overview)

仓颉是一门多范式、静态强类型、高性能的现代编程语言。

2.1 基础语法

变量与常量：
- var: 可变变量 (Variable)。
  - 支持类型推断：var x = 0 （推断为 Int64 ）
- let: 不可变变量 (Value)，运行时求值。
- const: 常量，编译时求值。
类型：
- 基础类型：
  - 整数 (Int64, UInt8…), 浮点 (Float64), 布尔 (Bool).
  - 字符 (Rune ，支持以 Unicode 值定义字符), 字符串 (String).
  - 数组 (Array<Rune>)
  - 元组 ((Int64, Float64))
  - 区间 (Range<Int64>, 0…10).
- Unit：类似 void，字面量为 ()。
- Option 类型 (?T)：解决空指针问题。值要么是 Some(T)，要么是 None。
  - 解包：getOrThrow(), match 匹配。

2.2 流程控制

一切皆表达式：if, match, try-catch, 代码块 {} 都有返回值（即最后一条语句的值）。
Match 表达式 🔥：
- 支持常量模式、类型模式、绑定模式 (case Red(v)), where 守卫。
- 编译器检查穷尽性 (Exhaustiveness)。

2.3 函数 (Functions)

定义：func name(p1: T1, p2!: T2): RetType { ... }
命名参数：p2!: T2 表示调用时必须写参数名 (name(1, p2: 2))。func f(x!: Int) -> 调用 f(x: 1)。
一等公民：函数可以赋值给变量，作为参数或返回值。
Lambda 表达式：{ p1 => body }。支持尾随 Lambda (Trailing Lambda) 语法（如果最后一个参数是函数，可写在括号外）。
管道操作符：|> (e.g., data |> fn1 |> fn2)。

2.4 代数数据类型与模式匹配

Enum（Sum Types）：

代码段

enum Expr {
    | Number(Float64)
    | Add(Expr, Expr) // 递归定义
}

Pattern Matching：

代码段

match (expr) {
    case Number(v) => v
    case Add(a, b) => ...
    case _ => ... // 通配符
}

Option 类型：Option<T> 分为 Some(T) 和 None。使用 getOrThrow 或 match 处理。

2.5 面向对象与类型系统

Struct（结构体）：
- 值类型，Copy语义，栈分配。
- 不能继承，但可以实现接口。
- mut 修饰符：修改struct成员的函数必须标记为 mut。
Class（类）：
- 引用类型，Reference语义，堆分配。
- open 关键字：修饰类表示可继承，修饰成员表示可覆盖 (override)。
Enum（枚举）：Sum Type（和类型）。
- 可以携带参数（关联值），支持成员函数和属性。
- 例：enum Expr { Num(Float64) | Add(Expr, Expr) }。
Interface（接口）：定义行为规范，支持默认实现。
扩展（Extend）：extend String { ... }，可以为已有类型（包括系统类型）添加方法或实现接口，不改变原有类定义。
Prop（属性）：prop 关键字，通过 get/set 访问，封装字段。

2.6 泛型 (Generics)

支持类型参数：class List<T> where T <: ToString。
支持泛型约束 (where)。

2.6 并发 (Concurrency)

模型：M:N 轻量级线程模型，用户线程（协程）映射到少量系统线程。
关键字：
- spawn { ... }：启动一个新线程（协程）。
- Future<T>：spawn 的返回值，代表未来的计算结果。
- future.get()：等待结果（同步点）。

2.7 宏 (Macros)

编译期代码生成与转换。
输入 Tokens，输出 Tokens。
用途：代码插桩、DSL实现（如LINQ）、静态反射。

2.8 跨语言互操作 (FFI)

C Interop：
- @C struct 映射 C 结构体。
- foreign func 声明 C 函数。
- unsafe 块中调用 C 函数。
- 类型映射：Int64 <-> long, CString <-> char*.

3. 作用域与函数运行时 (03-Scopes)

3.1 代码块与作用域（Blocks & Scopes）

内联（in-line）：代码出现的位置就是它被执行的位置

作用域 (Scope) vs 生存期 (Lifetime)

作用域：变量在代码文本中可见的区域（静态概念，看代码即可确定）。
- 遮蔽：内部块可以遮蔽 (Shadow) 外部块的同名变量。
生存期：变量在运行时占有内存的时间段（动态概念，运行时决定）。

3.2 活动记录 (Activation Record / Stack Frame)

定义：函数调用时，保存在运行时栈上的数据结构，存储单次调用信息（局部变量）。
内容：
1. 参数（Parameters）：调用者传递的值。
2. 局部变量（Locals）：函数内定义的变量。
3. 返回地址（Return Address）：函数结束后跳回代码段的哪里。
4. 函数返回时，在上一级活动中保存返回值地址
5. 动态链（Control Link / Dynamic Link）：指向调用者 (Caller) 的活动记录。用于函数返回时恢复栈顶指针 (EBP/ESP)。
6. 静态链（Access Link / Static Link）：指向定义该函数的外层环境的活动记录。用于实现静态作用域（访问非局部变量）。

3.3 作用域规则

静态作用域（Static/Lexical Scoping）：
- 变量引用取决于函数定义的位置。
- 现代语言（C, Java, Python, Cangjie）几乎都使用静态作用域。
- 实现：通过 Access Link 向上查找。
动态作用域（Dynamic Scoping）：
- 变量引用取决于函数调用的位置。
- 例子：Shell脚本, Emacs Lisp, Perl (local)。
- 实现：通过 Control Link 向上查找。

3.4 参数传递 (Parameter Passing)

传值（Call by Value）：复制右值（R-value）。Cangjie, Java, C采用此方式。Callee无法修改Caller的变量本身。
传引用（Call by Reference）：传递左值（L-value/地址）。Callee可以修改Caller的变量。

3.5 尾调用与尾递归 (Tail Call & Tail Recursion)

定义：函数 $g$ 的最后一个动作是调用函数 $f$ ，且直接返回 $f$ 的结果。
优化：不需要为 $f$ 创建新的栈帧，直接复用 $g$ 的栈帧。
意义：尾递归为特殊的尾调用，可以将递归转化为循环，避免栈溢出（Stack Overflow）。

3.6 高阶函数与闭包 (Higher-order Functions & Closures)

高阶函数：函数作为参数或返回值。
函数作为参数：需要传递函数代码指针 + 环境指针 (Access Link)，指向栈上函数定义处的活动记录。
函数作为返回值：需要赋值并额外保存函数定义处的活动记录
- 问题：返回的函数可能引用了已退出函数的局部变量（栈上数据已销毁）。
- 栈失效（Stack Limitation）：传统的栈式内存管理无法支持函数作为返回值。
- 解决方案：闭包（Closure） = 代码 + 环境。环境必须分配在堆（Heap） 上，通过 GC 管理。
闭包（Closure）：
- 定义：代码（Code） + 环境（Environment）。
- 必要性：当函数作为一等公民（First-class）被传递时，它可能引用了定义处的自由变量（Free Variables）。必须把定义时的环境（Access Link指向的记录）打包带走。
- 难点：当函数作为返回值返回时，其依赖的栈帧可能已被销毁。解决方案：将活动记录分配在堆（Heap 上，配合垃圾回收（GC）。

4. 类型系统 (04-Types)🔥

4.1 类型系统的作用

安全性：提供一组约束，避免非法操作。
可读性：让程序更好读，更易维护。
优化：编译器利用类型信息做更多优化。

4.2 类型的分类

分类：
- 基本类型：Int, Float, Bool 等
- 复合类型：
  - Array, Struct, Class 等
  - 积类型、和类型

4.2.1 代数数据类型 (Algebraic Data Types, ADT)

积类型

\frac{⊢ e_{1} : τ_{1} ⊢ e_{2} : τ_{2}}{⊢ (e_{1}, e_{2}) : τ_{1} \times τ_{2}} \frac{⊢ e : τ_{1} \times τ_{2}}{⊢ fst e : τ_{1}} \frac{⊢ e : τ_{1} \times τ_{2}}{⊢ snd e : τ_{2}}

积类型 (Product Types)：pairs and tuples, 多元 tuple 可以看成是 pair 的泛化。
- $T_{1} \times T_{2}$ 。
  - 我们需要 $T_{1}$ 和 $T_{2}$ 。
- 例子：
  - Tuple (Int, Float),
  - struct / records 可以看做是带标签的tuple（即labelled tuples）
    - ${d_{1} : τ_{1} = e_{1}, d_{2} : τ_{2} = e_{2}, \dots, d_{n} : τ_{n} = e_{n}} : struct M y S t r u c t {d_{1} : τ_{1}, d_{2} : τ_{2}, \dots, d_{n} : τ_{n}}$
- unit 类型：代数中的 “1”
  - 定义：unit 类型只有一个值，通常写作 ()。
  - 视作特殊的 Tuple：图片提到它可以被视作特殊的 tuple 类型（空元组）。在很多语言（如 Rust, Haskell, Swift）中，它就是空的圆括号 ()。
  - 代数性质： $T \times unit \sim T$ 。
    - 解释：就像数学里的 $x \times 1 = x$ 。
    - 如果你有一个 Pair，其中一个是类型 $T$ ，另一个是 unit，形式如 (value, ())。因为 () 是唯一且确定的，所以这个 Pair 包含的信息量并没有增加，它等价于只有 $T$ 。
  - 作用：
    - 表示“无返回值”：类似于 C/Java 中的 void。当一个函数只执行副作用（如打印、修改全局变量）而不产生具体计算结果时，它实际上返回的是 unit（即“完成”这一单一状态）。
    - 泛型占位符：比如你需要一个 Map<Key, Value> 来实现一个 Set<Key>，你可以定义为 Map<Key, Unit>，这样就只有键而忽略了值。

和类型

\begin{array}{l} (Types) τ ::= \dots ∣ τ_{1} + τ_{2} \\ (Terms) e ::= \dots ∣ left e ∣ right e ∣ case e do e_{1} e_{2} \end{array}

\begin{matrix} \frac{⊢ e : τ_{1}}{⊢ {left}_{τ_{1} + τ_{2}} e : τ_{1} + τ_{2}} (left) \frac{⊢ e : τ_{2}}{⊢ {right}_{τ_{1} + τ_{2}} e : τ_{1} + τ_{2}} (right) \\ \frac{⊢ e : τ_{1} + τ_{2} ⊢ e_{1} : τ_{1} \to τ ⊢ e_{2} : τ_{2} \to τ}{⊢ case e do e_{1} e_{2} : τ} (case) \end{matrix}

和类型 (Sum Types)：sum types and enum。
- $T_{1} + T_{2}$
  - 我们需要 $T_{1}$ 或 $T_{2}$ 。
- 例子：C中的 union (不安全)，Rust/Swift/Cangjie中的 enum (带参数的枚举)。
- 模式匹配 (Pattern Matching) 是处理和类型的标准方式。

示例（伪代码）

规则	伪代码示例
$(left)$	`let x: Int = 5; let y: Int + String = left(x);`
$(right)$	`let s: String = "Hello"; let z: Int + String = right(s);`
$(case)$	`case y do {` `(i: Int) -> return i + 1` (这里的 $e_{1}$ 是 $Int \to Int$ ) `(s: String) -> return s.length` (这里的 $e_{2}$ 是 $String \to Int$ ) `}` 结果类型： $Int$

nothing 类型：代数中的 “0”
- 定义：图片指出 nothing 类型 没有值（No value）。这意味着你永远无法创建一个该类型的实例变量。在不同语言中它可能叫 Never (Rust/Swift), Nothing (Scala), 或 Void (Haskell/Logic)。
- 视作特殊的 Sum：图片提到它可以视作 0个分支的 sum 类型。如果你定义一个枚举（Enum），但里面一个成员都不写，那它就是 nothing。
- 代数性质： $T + nothing \sim T$ 。
  - 解释：就像数学里的 $x + 0 = x$ 。
  - 求和类型表示“要么是 A，要么是 B”。如果 B 是 nothing（不可能存在），那么这个类型实际上只能是 A。
- 作用
  - 表示“函数不返回”：注意这与 unit 不同。unit 表示“函数正常结束但没带回数据”，而 nothing 表示“控制流永远回不到调用者”。例如：
    - 无限循环 while(true) {}。
    - 程序崩溃或退出 exit()。
    - 抛出异常 throw e。
  - 死代码消除：编译器知道如果代码走到了 nothing 类型的地方，后面的代码就绝对不可能被执行，因此可以优化掉或报警告。
  - 类型系统的完整性：在 case 表达式中，如果一个分支是 nothing，它就不需要返回值，因为它根本不会正常结束。

4.2.2 函数类型

类型推断

核心概念：Typing Context (类型上下文) 与 Judgment (判断)

Judgment 类型判断： $Γ ⊢ e : τ$
- 读作：在环境 $Γ$ 下，表达式 $e$ 的类型是 $τ$ 。
Typing Context ( $Γ$ ): $Γ ::= \cdot ∣ Γ, x : τ$
- 定义： $Γ$ （Gamma）是一个列表或字典，记录了当前作用域内所有非局部变量 (non-local variables) 的类型。
- 结构：
  - $\cdot$ ：表示空上下文（没有任何变量）。
  - $Γ, x : τ$ ：表示在现有的上下文 $Γ$ 中，新增加一个变量 $x$ ，其类型为 $τ$ 。
规则示例：
- If-Else: 如果 $e_{c o n d}$ 是 Bool，且 $e_{1}$ 是 $T$ ， $e_{2}$ 也是 $T$ ，则 if 表达式类型为 $T$ 。
- App (函数应用): 如果 $f : A \to B$ ，且 $x : A$ ，则 $f (x) : B$ 。

函数类型

函数定义规则 (Abstraction / Introduction)
这是第一条规则，描述了如何创建一个匿名函数（Lambda）：

\frac{Γ, x : τ_{1} ⊢ e : τ_{2}}{Γ ⊢ (λ x : τ_{1} . e) : τ_{1} \to τ_{2}}

含义：如果你想证明一个函数 $λ x . e$ 的类型是 $τ_{1} \to τ_{2}$ （输入 $τ_{1}$ ，输出 $τ_{2}$ ）。
前提 (分子)：你需要做一个假设。假如允许我们引入一个新的、类型为 $τ_{1}$ 的参数 $x$ （把它加入到上下文 $Γ$ 中，变成 $Γ, x : τ_{1}$ ），在这个新环境下，就可以推导出函数体 $e$ 的类型为 $τ_{2}$ 。
结论 (分母) ：在当前的类型环境 $Γ$ 下，这个匿名函数 $(λ x : τ_{1} . e)$ 的类型被判定为函数类型 $τ_{1} \to τ_{2}$ 。
- $(λ x : τ_{1} . e)$
  - 含义：这是我们要检查的代码主体——一个匿名函数定义（Lambda Abstraction）。
  - $λ$ ：表示这是一个函数。
  - $x : τ_{1}$ ：表示函数的输入参数是 $x$ ，且我们显式声明了它的类型是 $τ_{1}$ 。
  - $. e$ ：表示函数的函数体 (Body) 是表达式 $e$ 。
  - 总结：这一段是在说“这个定义了参数 $x$ 为 $τ_{1}$ 、函数体为 $e$ 的函数”。
直观理解：编译器会说：“我假装 $x$ 是整数，看看函数体能不能算出个字符串。如果能，那这个函数就是 Int -> String。”

函数应用规则 (Application / Elimination)
这是第二条规则，描述了如何调用一个函数：

\frac{Γ ⊢ f : τ_{1} \to τ Γ ⊢ e : τ_{1}}{Γ ⊢ f (e) : τ}

含义：如果你要调用函数 $f (e)$ ，最终结果是什么类型？
前提（分子）：
1. 检查 $f$ ：它必须是一个函数类型，且输入要求是 $τ_{1}$ ，输出是 $τ$ 。
2. 检查参数 $e$ ：它的类型必须严格匹配函数的输入要求 $τ_{1}$ 。
结论（分母）：如果上述两条都满足，那么调用结果 $f (e)$ 的类型就是 $τ$ 。

变量查找规则 (Variable)
这是第三条规则（最下面那条横线），它是递归推导的基准情况（Base Case）：

\overset{―}{Γ, x : τ ⊢ x : τ}

注意：这条规则上方没有前提（或者说前提是空的），意味着这是公理。
含义：如果在当前的上下文（环境）中，已经记录了 $x$ 的类型是 $τ$ （写作 $Γ, x : τ$ ），那么推导结论 $x$ 的类型自然就是 $τ$ 。
作用：当你推导到代码的最底层（变量名）时，你需要去查表 ( $Γ$ )，这条规则就是查表的数学表达。

4.3 类型系统特性

强类型 vs 弱类型：是否允许隐式的、不安全的类型转换（如C语言把int当指针用是弱类型行为；Cangjie/Java是强类型）。
静态类型 vs 动态类型：
- 静态：编译期检查，性能高，安全。
- 动态：运行期检查，灵活。
Null Safety：
- 传统：Null 也是一种值，容易导致崩溃。
- 现代（Cangjie/Rust）：使用 Option<T> (Sum Type: Some(T) | None)，强制程序员处理空值情况。

5 类型推导与 Hindley-Milner 算法 (05-Types-Hindley-Milner)🔥

核心目标：在不写类型标注的情况下，自动推导出最通用的类型（Most General Type / Principal Type）。

5.1 算法流程 (以 `f x = 2 + x` 为例)

解析（Parse）：构建语法树（AST）。将中缀表达式转换为函数应用((+) 2) x。
- 中缀转前缀：从 2 + x 变成 (+) 2 x。
- 柯里化（Currying）拆解：从 (+) 2 x 变成 ((+) 2) x。
分配类型变量（Assign Type Variables）：
- 给AST中的每个节点分配一个唯一的类型变量（如 $t_{0}, t_{1}, t_{2} \dots$ ）。
  - $f : t_{0}$ 。
  - $x : t_{1}$
  - $2 : t_{3}$
  - $+ : t_{2}$
  - $(2 + x)$ 的结果: $t_{4}$
生成约束（Generate Constraints）：
- 函数应用（Application） $f x$ ：如果 $f : t_{f}, x : t_{x}$ ，结果为 $t_{r e s}$ ，则约束为 $t_{f} = t_{x} \to t_{r e s}$ 。
  - 调用 $f x$ ，（题目中为调用 +: $Int \to Int \to Int$ ）
  - 逻辑：我们手里有一个函数 $f$ （类型 $t_{f}$ ）和一个参数 $x$ （类型 $t_{x}$ ），我们期望得到一个结果（类型 $t_{r e s}$ ）。为了让这次调用合法，函数 $f$ 的类型必须长得像 “接受 $t_{x}$ ，返回 $t_{r e s}$ ”。
- 函数定义（Abstraction） fun x -> e：如果 $x : t_{x}, e : t_{e}$ ，函数整体为 $t_{f u n}$ ，则 $t_{f u n} = t_{x} \to t_{e}$ 。
  - 定义 fun x -> e
  - 逻辑：既然输入参数是 $x$ （类型 $t_{x}$ ），函数体算出来的结果是 $e$ （类型 $t_{e}$ ），那么这个函数本身的类型 $t_{f u n}$ 自然就是从 $t_{x}$ 到 $t_{e}$ 的映射。
- 根据语法规则建立等式。
  - 对于常量 2：我们已知 $t_{3} = Int$ 。
    
    对于操作符 +：我们已知 $t_{2} = Int \to Int \to Int$ 。
    
    对于应用 (+) 2：
    - 这是一个函数应用。函数是 + ( $t_{2}$ )，参数是 2 ( $t_{3}$ )。
    - 根据函数应用规则：函数类型 = 参数类型 $\to$ 结果类型。
    - 约束 1: $t_{2} = t_{3} \to t_{t e m p}$ (设 + 2 的中间结果为 $t_{t e m p}$ )。
    对于应用 ((+) 2) x：
    - 函数是 (+) 2 ( $t_{t e m p}$ )，参数是 x ( $t_{1}$ )，结果是整个表达式 ( $t_{4}$ )。
    - 约束 2: $t_{t e m p} = t_{1} \to t_{4}$ 。
    对于函数定义 f x = ...：
    - 这是一个函数定义 (Abstraction)。参数是 $x$ ( $t_{1}$ )，函数体是结果 ( $t_{4}$ )，函数本身是 $f$ ( $t_{0}$ )。
    - 根据函数定义规则：函数整体类型 = 参数类型 $\to$ 函数体类型。
    - 约束 3: $t_{0} = t_{1} \to t_{4}$ 。
解约束（Solve Constraints）：
- 使用 Unification (统一) 算法求解方程组。
  - 从约束 1 ( $t_{2} = t_{3} \to t_{t e m p}$ ) 开始：
    - 已知 $t_{2} = Int \to Int \to Int$ 。
    - 已知 $t_{3} = Int$ 。
    - 代入方程： $Int \to (Int \to Int) = Int \to t_{t e m p}$ 。
    - 解得： $t_{t e m p} = Int \to Int$ 。
  - 解约束 2 ( $t_{t e m p} = t_{1} \to t_{4}$ )：
    - 代入 $t_{t e m p}$ ： $Int \to Int = t_{1} \to t_{4}$ 。
    - 对比箭头左边： $t_{1} = Int$ (所以 x 必须是整数)。
    - 对比箭头右边： $t_{4} = Int$ (所以函数体返回整数)。
  - 解约束 3 ( $t_{0} = t_{1} \to t_{4}$ )：
    - 代入 $t_{1}$ 和 $t_{4}$ 。
    - 最终结果： $t_{0} = Int \to Int$ 。
  结论：f 的类型推导为 Int -> Int。
确定最终类型：
- 无法被约束为具体类型（如Int）的变量保留为类型参数（如 $α, β$ 或 $t_{1}$ ），从而实现参数化多态 (Parametric Polymorphism)。

5.2 多态 (Polymorphism)

Let-polymorphism（Let 多态）：Hindley-Milner算法支持 let 绑定的多态。
- let id = \x -> x，类型为 $\forall α . α \to α$ 。
  - let 绑定：let 关键字标志着一个值的定义完成，此时编译器会检查这个值或函数是否包含任何尚未确定的类型变量。如果有，编译器就会将其泛化（generalize），使其成为多态类型。
  - id：是这个函数的名称（通常称为 Identity Function，恒等函数）。
  - \x -> x：这是函数的定义（ $λ$ -演算写法）。它表示一个匿名函数，(\x 表示) 接收一个输入 x，并原封不动地返回 x。
  - $α$ ：代表一个类型变量（Type Variable），它可以是任何类型。
  - $\forall$ 的存在，是将一个临时的、待确定的类型变量 (Free) 转化为一个永久的、可复用的泛型参数 (Bound) 的唯一且必需的标记。
  - $α \to α$ ：这是函数本身的类型结构。它表示“接收一个 $α$ 类型的输入，并返回一个 $α$ 类型的输出”。
- 推导过程：
  - HM 算法分析函数体 x，得出 id 的类型是 $t_{x} \to t_{x}$ 。
  - 算法发现 $t_{x}$ 没有被任何具体类型（如 Int）约束。
  - 因此，在 let 绑定时，算法将 $t_{x}$ 替换为通用的 $α$ ，并加上 $\forall$ 量词，宣告这个函数是泛型的。
- id 3 (Int) 和 id true (Bool) 可以在同一作用域内有效。
  - 当执行 id 3 时 ( $Int$ )， $α$ 被实例化为 $Int$ ，函数类型暂时变为 $Int \to Int$ 。
  - 当执行 id true 时 ( $Bool$ )， $α$ 被实例化为 $Bool$ ，函数类型暂时变为 $Bool \to Bool$ 。
最通用类型（Principal Type）
- HM算法保证只要程序在逻辑上是类型正确的，一定能推导出最通用的那个类型。
  - 最通用：意味着推导出的类型具有最大的泛型潜力。
- 例如，如果一个函数只是简单地对一个列表进行操作，它不需要知道列表里具体是什么类型。
  - 推导出 List<T> 而不是 List<Int>，除非用法限制了它必须是Int。
- 何时丧失通用性？
  只有当代码用法对类型施加了新的约束时，HM 才会把通用变量（ $α$ 或 $T$ ）收窄为具体类型。
  - 例：如果你写了一个函数 f(list) = list * 2（伪代码，对列表执行标量乘法），那么：
    1. * 操作符的类型是 $Int \to Int \to Int$ (假设)。
    2. 算法立即约束：list 里的元素必须是 $Int$ 。
    3. 此时，算法推导出的类型就会从 $List < T >$ 变为 $List < Int >$ 。

6. 面向对象编程

6.1 面向对象编程基础与历史 (06-OOP-1)

6.1.1 核心概念

对象：封装了
- 内部状态（state）：实例变量 / 字段 / 成员变量 / 属性
- 对外操作（behavior）：方法 / 成员函数
- 常见规则：内部状态通常是私有的（private），只能通过方法间接访问（封装）。
消息传递（Messaging）：OOP 的本质是对象间通过发送消息进行交互。x.add(y) 可以看作向对象 x 发送 add 消息，参数为 y
- Alan Kay（Smalltalk 主要发明人）给 OOP 的定义重点是：
  - only messaging（只有消息传递）
  - state-process hiding（状态与过程隐藏）
  - extreme late-binding（极致的晚绑定）。
OOP 四大核心概念：
1. 动态派遣（Dynamic Dispatch）：运行时根据对象的实际类型决定调用哪个方法。
2. 封装（Encapsulation）：隐藏内部实现细节（private/public）。
3. 多态（Polymorphism/Subtyping）：子类型的对象可以被当作父类型使用。
4. 继承（Inheritance）：代码复用机制（注：现代观点中继承有较大争议，组合优于继承）。

6.1.2 语言演变历史

Simula 67 (OOP鼻祖)

起源：挪威计算中心，最初用于仿真。
贡献：引入了类（Class）、对象（Object）、继承、虚方法、协程（Coroutine）、GC。
对象模型：对象被视为活动记录 (Activation Record)。
- 过程调用产生活动记录，通常调用结束即销毁。
- Simula的对象是“返回后仍保留”的活动记录（通过指针/引用访问）。
缺点：缺乏封装、self/super、类成员变量（静态变量）、异常。

Simula 中的类与对象实现 🔥

类（class）= 返回其活动记录指针的函数（过程）：
- 调用类（像调用函数）：分配一个新的“活动记录”；
- 这个活动记录就是对象。
对象（object）：可以看作“带有 Access Link 的活动记录”，Access link 用于访问外层环境（全局变量/静态数据）。
- “每次调用类之后产生的活动记录”；
- 内含字段（局部变量）、指向方法代码的指针等。
对象访问：
- 使用点运算符（dot notation）：o.var / o.proc(...)
内存管理：
- 使用 垃圾收集（GC） 自动管理对象生命周期。

Smalltalk (纯OOP)

起源：Xerox PARC，Alan Kay主导，伴随Dynabook概念（现代笔记本/平板雏形）。
特点：
- 一切皆对象：连类本身也是对象（元类 Metaclass）
- 纯消息传递：所有计算都是向对象发送消息的过程
  - 控制流结构（如if-else, loop）都是通过向Boolean或Block对象发送消息实现的。
- 动态类型：无编译期类型检查。
实现：
- 对象结构：类指针 + 实例变量。
- 方法查找：在类的方法字典中查找 -> 找不到则去父类找 -> 直到Object类 -> 报错（DoesNotUnderstand）。

6.2 C++ 与 Java 的对象模型 (06-OOP-2)

6.2.1 C++ 对象模型

设计目标：在C的基础上增加OOP特性，不牺牲效率（“Zero-overhead principle”：如果不使用某特性，就不应为此付费）。
内存布局：
- 对象像 struct 一样在栈上或堆上分配。
- Vtable（虚函数表）：如果有虚函数，对象中会多一个 vptr 指向 vtable。
- Vptr：指向类的虚函数表，表中存储了虚函数的地址。
方法调用：
- 非虚函数：编译期确定地址（静态绑定），效率等同C函数。
- 虚函数：运行时通过 vptr 间接寻址（动态绑定）。代码：(*(p->vptr[0]))(p, args)。
多重继承（Multiple Inheritance）：
- 问题：
  1. 命名冲突：两个父类有同名方法。解决：显式指定 A::f()。
  2. 菱形继承（Diamond Problem）：D继承B和C，B和C都继承A。D中会有两份A的数据。
- 解决：虚继承（Virtual Inheritance） class B : virtual public A。保证D中只有一份A，但引入了复杂的指针偏移计算，降低效率。

6.2.2 Java 对象模型

设计目标：简单、可靠、安全、可移植（Write Once, Run Anywhere）、简洁性与熟悉感（类似 C++）、效率（次要但考虑）
特点：几乎一切是对象；
- 所有对象都在**堆（Heap）**上分配，通过引用访问。
- 单继承：避免了C++多重继承的复杂性（特别是菱形问题）。
- 接口（Interface）：实现多重类型的机制。一个类可以实现多个接口，但只继承一个实现。
- 没有 goto，没有运算符重载；
- 静态类型检查 + 运行时检查 + GC。
垃圾回收（GC）：解决了C++手动内存管理的安全性问题（悬垂指针、内存泄漏）。
Finalizer：类似析构函数，但不保证立即执行（甚至不保证执行），主要用于释放非内存资源（如文件句柄）。

6.3 对象类型与子类型 (06-OOP-3)

6.3.1 子类型 (Subtyping) vs 继承 (Inheritance)

把对象看成“支持某些方法的实体”，这些方法集合就是对象的接口（interface），也就是对象的类型。

子类型定义：如果接口 A 包含接口 B 的所有成员，那么 A 类型的对象在任何需要 B 类型对象的地方都可以用。
因此，Colored_point 是 Point 的子类型。

接口（Interface）：对象的外部视图（能接收什么消息）。
实现（Implementation）：对象的内部表示。
继承：实现的复用。
子类型：接口的兼容性（A是B的子类型 $⟹$ A可以用在任何需要B的地方，即里氏替换原则 LSP）。
结论：继承 $\neq$ 子类型。但在C++/Java中，通过类继承通常自动产生子类型关系。

子类型与继承的关系

在 Smalltalk/JS 中：
- 继承（inheritance）是显式语言机制：用于代码复用；
- 子类型（subtyping）是一种“接口包含关系”：语言规范里没特意写，但系统设计中是默认假设。
在 C++ / Java 中：
- 通常约定：
  - 类继承 class B : public A / class B extends A ⇒ B 是 A 的子类型（public 继承，单继承）。
- 但要注意：
  - 多继承、多态构造时，容易在“语义上不是好子类型”——即违反 Liskov 替换原则。

解释 “subtyping != inheritance”，给出反例

比如继承只为了复用代码但改变方法语义：Rectangle / Square

Square 为了复用 Rectangle 的代码而继承它，但通过重写 setWidth/setHeight 改变了这些方法的语义。

对 Rectangle 的使用者来说，setWidth 只应改变宽度，不应影响高度；但 Square 违反了这一约定。

所以在需要 Rectangle 的地方，用 Square 替换可能破坏原来程序的不变式，不满足 LSP。

于是，这里有继承，但没有合理的子类型关系，从而体现了 “subtyping != inheritance”。

6.3.2 子类型🔥

定义：如果 A 是 B 的子类型 ( $A <: B$ )，则 A 的对象可以替代 B 的对象使用 (Liskov 替换原则)。
宽度子类型（Width）：子类型包含父类型的所有方法/字段，且可能更多。
深度子类型（Depth）：字段类型也是子类型，如果字段类型是协变的（Covariant），通常是不安全的（针对可变数据）。
函数子类型：
参数是逆变（Contravariant）： $T_{1} <: T_{2} ⟹ (T_{2} \to R) <: (T_{1} \to R)$ 。
返回值是协变（Covariant）： $R_{1} <: R_{2} ⟹ (T \to R_{1}) <: (T \to R_{2})$
口诀：输入更宽容，输出更严格。

6.3.3 Java 数组的协变性 (Covariance)🔥

现象：在Java中，如果 Circle <: Shape，则 Circle[] <: Shape[]。

问题：这是类型不安全的。（运行时可能写入非 Circle 对象抛出异常），但为了实用性（如 System.arraycopy）被允许。因此需要运行时检查，代价不小，语义也不“干净”.

Circle[] circles = new Circle[10];

Shape[] shapes = circles;     // 编译期通过，允许（协变），因为 Circle[] <: Shape[]
shapes[0] = new Square();     // 编译通过，但运行时抛 ArrayStoreException

原因：早期Java为了写通用的数组拷贝函数（如 System.arraycopy）而妥协。现代泛型（List<Circle> 不是 List<Shape>）修正了这个问题。

6.3.4 接口（Interface）与多重子类型

接口是“完全抽象的类”：
- 只声明方法，不包含实现（Java 8+ 支持 default 方法，但 PPT 里作为“无实现的接口”来讲）

例：

interface Shape {
  public float center();
  public void rotate(float degrees);
}

interface Drawable {
  public void setColor(Color c);
  public void draw();
}

class Circle implements Shape, Drawable {
  // 必须实现两个接口中的所有方法
}

接口可以多继承 / 多实现 → 构成子类型图而不是树；
解决/绕过 C++ 多继承的“钻石问题”：多继承的是“类型”，而不是“实现”。
代价：
- 接口方法的调用在 JVM 内部需要额外的查找（invokeinterface）：
  - 方法在类中的偏移量编译期不固定；
  - 运行时查找后加缓存。

6.3.5 异常类型 (Exceptions)

java.lang.Object
  └── java.lang.Throwable
       ├── java.lang.Exception
       │    ├── checked 异常（大多数业务相关异常）
       │    └── RuntimeException 及其子类（unchecked）
       └── java.lang.Error（JVM 或系统级严重错误）

Checked Exceptions 受检异常 (Exception 下除了 RuntimeException 及其子类之外的所有类)：必须显式捕获或声明抛出。属于方法签名的一部分。
- 强制检查。代码编译时，编译器会检查是否处理了该异常。
- 必须显式处理：要么用 try-catch 捕获，要么在方法签名用 throws 声明。
- “可预见的意外”。通常由外部环境引起，程序应该预料到并有备选方案。
- IOException (文件读写失败)、SQLException (数据库查询失败)、ClassNotFoundException
Unchecked Exceptions 非受检异常 (**RuntimeException**及其子类, **Error**及其子类)：无需显式处理。
- 忽略。编译器不强制要求处理，编译能通过。
- 无需显式声明，也无需强制捕获（但可以捕获）。
- “程序员的逻辑错误”。通常是因为代码写错了，应该通过修改代码来修复，而不是捕获。
- NullPointerException (空指针)、IndexOutOfBoundsException (数组越界)、OutOfMemoryError (严重错误)

6.4 Java 虚拟机与安全 (06-OOP-4)

6.4.1 JVM 架构

Compiler：把 Java 源代码编译成字节码（.class 文件）；
类加载器（Class Loader）：加载 .class 文件。
验证器（Verifier） 🔥：安全的关键，在类被装载前，对字节码做静态检查
- 确保字节码安全（无栈溢出、无非法类型转换、跳转指令合法）。
- 数据流分析：确保变量在使用前已初始化（即便是跳转后）。
Bytecode Interpreter / JIT Compiler：
- 逐条解释执行字节码。
- 运行时热点代码编译为本地机器码，提升性能。

6.4.2 方法调用指令（Method Lookup）

invokevirtual：调用类实例方法（根据对象实际类型动态查找，基于类 vtable，较快）。
invokeinterface：调用接口方法（需要搜索，较慢，有 Inline Cache 优化）。
invokestatic：静态方法（编译期确定）。
invokespecial：构造函数、私有方法、super 调用。

“动态绑定”在 JVM 层面是通过不同的 invoke 字节码 + vtable / itable 查找实现的。

6.4.3 方法查找优化

内联缓存（Inline Caches, IC）：
- 缓存上次调用的方法地址。
- Morphic（单态）：缓存上一次调用的（类，方法地址）。如果下次调用对象类型相同，直接跳转。
- Polymorphic（多态 PIC）：缓存多个（类，方法地址）对。遇到多种类型，生成类型判断树 (if type==A jump targetA else ...)。
OSR（On-Stack Replacement）：在循环中进行解释执行到编译执行的切换。

6.4.4 Java 安全模型 (Sandbox / Stack Inspection)

Security：防止未经授权使用计算资源。

Java Security：防止粗心用户 / 恶意攻击者的输入。

沙箱模型（Sandboxing）：限制代码对本地资源的访问：限制程序的加载器、验证器、解释器的功能。
类型安全：
- 强类型源语言 + 字节码；
- Verifier 保证字节码遵守类型规则
安全管理器（Security Manager）：运行时权限检查（如文件读写、网络访问）。
栈检查（Stack Inspection）：
- 权限检查不仅看当前方法，还看调用栈上的所有方法。
- 防止“特权代码”（如JDK库）被恶意代码调用去执行危险操作。恶意代码在栈上，会导致权限检查失败。
- doPrivileged：允许受信任代码截断栈检查（即“我对此操作负责，不需检查我的调用者”）。

6.5 仓颉语言 OOP (06-OOP-5-Cangjie)

6.5.1 类型系统

仓颉类型系统

统一类型：所有类型（包括基础类型Int、Struct、Class）都是 Any 的子类型。
- 所有类型都是 Any 的子类型
- 所有的 class 都是 Object 的子类
Struct vs Class：
- struct：值类型（栈分配，Copy语义）。
- class：引用类型（堆分配，Reference语义）。

6.5.2 类与接口

继承：单继承。默认类（类缺省）是不可继承的（类似 Java 中的 “final”）

只有 open 修饰的类才可继承
只有 open 修饰的方法才能被 override
- override 关键字可以省略
- Interface 中的方法都是 open 的
- 动态派遣机制，open method 的调用采用动态派遣

open class Shape <: Equitable, ToString {
  open func move(x: Int, y: Int): Unit {
    print("Shape moved to ($x, $y)")
  }
  // Other common methods for shapes
}

class Circle <: Shape {
  override func move(x: Int, y: Int): Unit {
    print("Circle moved to ($x, $y)")
  }
  // Other common methods for circles
}

class Rectangle <: Shape {
  override func move(x: Int, y: Int): Unit {
    print("Rectangle moved to ($x, $y)")
  }
  // Other common methods for rectangles
}

let s1: Shape = Circle()
let s2: Shape = Rectangle()
s1.move(10, 20) // Should print "Circle moved to (10, 20)"
s2.move(30, 40) // Should print "Rectangle moved to (30, 40)"

接口：支持多继承，可以包含默认实现（Default Implementation）
- 仅提供方法签名
- 但可以提供 default 实现
- 多继承问题：多个interface中对于同名函数，有多个缺省实现 ——编译报错
Constructor：
- init函数，可以重载
- 调用顺序规定与Java类似
Finalizer：
~init
不允许this逃逸

interface Comparable<T> {
  func lt(other: T): Bool
  func ge(other: T): Bool{
    return !lt(other)
  }
// Other comparison methods can be defined here
}

class MyClass <: Comparable<MyClass> {
  override func lt(other: MyClass): Bool{
  // Implement less-than logic here
  return true // Placeholder implementation
  }
}

7. 模板与泛型 (07-Templates-and-Generics)

7.1 多态的对比

参数化多态 / 泛型（Parametric Polymorphism）：
- 函数体对所有类型一视同仁（不依赖具体类型），类型只作为占位符。
- 例：
  - List<T>, swap<T>。
  - Java generic <T> f(T x) 或 Haskell f :: t -> t；
子类型多态（Subtype Polymorphism）：
- 编译时只有一个函数体，通过动态派发处理不同子类。
- 基于继承关系（ $S <: T$ ），操作父类类型的代码可以应用于子类对象。
- 例：void f(Object x) 可以接受 String。
重载（Overloading）：
- 同一个符号（如 +）指代不同的算法，取决于上下文类型。
- 这不是真正的多态，而是“特设多态 (Ad-hoc Polymorphism)”。
- 区别：
  - 多态：一个算法适用于多种类型；
  - 重载：同一名字关联多个不相关的算法，由上下文选择。

既然有子类型多态，为什么还要引入类型参数（泛型）？

泛型更适合表达“与具体类型无关，只要求一定接口（如比较、哈希）”的算法。

子类型多态通常要求把所有值包装成某个公共 superType，会丢失精确类型、需要强制转换。

7.2 C++ 模版 (Templates)

7.2.1 机制与实现

编译期实例化（Compile-time Instantiation）：
- 编译器根据使用的具体类型（如 Vector<int>, Vector<double>），生成该类型的专用代码副本。
- 异构实现：vector<int> 和 vector<float> 是完全不同的两个类，代码通过拷贝生成。
- 优点：
  - 运行效率极高（零开销抽象）
  - 支持特化：可以为特定类型（如 Vector<bool>）提供优化实现
  - 支持元编程（Template Metaprogramming）
- 缺点：
  - 代码膨胀 (Code Bloat)
  - 编译时间长
  - 编译错误信息晦涩

Haskell 多态：

多态函数只编译为一个函数；

通过类型推导 + 字典传递（对于 type class）在调用点选择具体实现。

7.2.2 特化 (Specialization)

全特化（Full Specialization）：为特定类型提供完全不同的实现。
- 例：Set<char> 可能用位图实现，而通用的 Set<T> 用树实现。
偏特化（Partial Specialization）：为一类类型提供特定实现。
- 例：Set<T*>（针对所有指针类型）使用哈希表实现。

7.2.3 模版元编程 (Template Metaprogramming)

利用模版实例化过程在编译期进行计算。
示例：编译期计算阶乘（通过递归模版实例化）。
Policy-based Design：将策略（如内存分配策略、锁策略）作为模版参数传入类中，实现行为的组合（Mixin 风格）。

7.2.4 标准模版库 (STL)

核心组件：
1. 容器（Container）：vector, list。
2. 迭代器（Iterator）：泛化的指针，连接容器与算法的桥梁。
3. 算法（Algorithm）：sort, find，通过迭代器操作容器。
优势：将算法与数据结构解耦 (Decoupling)。

7.3 Java 泛型 (Java Generics)

7.3.1 机制与实现

类型擦除 (Type Erasure) 🔥：
- 同构实现：所有泛型实例在运行时共享同一份字节码。
- 编译过程：
  1. 编译期类型检查保证安全
  2. 生成字节码时，擦除类型参数：List<T> -> List，T -> Object（或上界类型）。
  3. 在必要时插入强制类型转换。
  4. 因此运行时不会保存泛型实参类型。
- 优点：
  - 保持了旧版本 JVM 的兼容性
  - 节省代码空间
- 缺点：
  - 运行时丢失类型信息，无法区分 List<String> vs List<Integer>；
    - 无法 new T(), new T[]，不能有 static T field 等。
  - 基本类型（int）需要装箱 (Integer) 导致性能损耗。

7.3.2 通配符 (Wildcards)

?：任意类型。
? extends T：上界通配符（协变），适合读取（生产者 Producer：只读不写）
? super T：下界通配符（逆变），适合写入（消费者 Consumer：只写不读）
PECS 原则：Producer Extends, Consumer Super.

7.3.3 F-Bounded Polymorphism

定义：类型参数递归地出现在约束中。
典型场景：interface Comparable<T> { int compareTo(T o); }
- 约束写法：<T extends Comparable<T>>
- 含义：T 必须能和它自己进行比较。

7.3.4 协变与数组🔥

Java 数组是协变的：Integer <: Number 所以 Integer[] <: Number[]
- 导致运行时错误：nums[0] = 3.14， ArrayStoreException 问题
Java 泛型是不变的（Invariant）：List<Integer> 不是 List<Number> 的子类。
- 更安全，编译期报错。

7.4 C++ 模版 vs Java 泛型 (核心考点) 🔥

特性	C++ Templates	Java Generics
实例化方式	异构（Heterogeneous）：每个类型生成一份独立代码。	同构（Homogeneous）：类型擦除，共享一份代码。
执行阶段	编译期 / 链接期。	编译期检查，运行时无泛型信息。
基本类型支持	直接支持 (`vector<int>`)。	不支持，需装箱 (`List<Integer>`)。
特化	支持全特化和偏特化。	不支持特化。
代码大小	可能导致代码膨胀。	代码紧凑。
灵活性	极高（可用于元编程）。	较低（受限于类型擦除）。

8. 类型类 - Haskell(08-TypeClasses)

8.1 解决的问题

重载（Overloading） 的需求：有些函数不能对“所有类型”都工作，只能对支持某些操作的类型：
- member :: [w] -> w -> Bool 只对支持相等性比较的类型有意义；
- sort :: [w] -> [w] 只对支持大小比较的类型有意义；
- serialize :: w -> String 需要 w 可序列化；
- sumOfSquares :: [w] -> w 需要 w 是“数值型”。
传统方案的缺陷：
- 传统的重载（Overloading）无法很好地处理多态函数（如 sort 需要比较操作，print 需要序列化操作）。
- 简单的参数化多态无法限制类型必须支持某些操作（如 a + b 要求 a 是数字）。
- Ad-hoc 重载 (SML)：仅支持内置类型，不可扩展。
- 完全多态 (Miranda)：运行时检查，对不支持的类型抛异常（不安全）。
Haskell 的方案：类型类（Type Class） —— 有原则的重载。

8.2 Haskell 的解决方案：Type Classes

Type Class：定义一组操作（接口），类似 Java Interface，但更强大。
1
2
class Eq a where
(==) :: a -> a -> Bool

Instance：为具体类型实现这些操作。

1 2	instance Eq Int where x == y = intEq x y

Qualified Types：在函数签名中添加约束。

1	member :: Eq a => a -> [a] -> Bool -- 读作："对于任何支持 Eq 的类型 a，member 函数..."

8.3 实现原理：字典传递 (Dictionary Passing) 🔥

编译期翻译：编译器将 Type Class 转换为 字典 (Dictionary) 数据结构。
- 字典：本质上是一个包含函数指针的记录 struct 。
- 带有约束的函数（如 square :: Num n => n -> n）会被编译成接收一个额外参数（字典 d）的函数。
- 调用时，编译器根据具体类型自动传入对应的字典（如 dNumInt）。
函数重写：
- square :: Num n => n -> n
- 被编译为：square :: NumDict n -> n -> n
- 即：函数多接收一个字典参数，通过字典调用具体的操作（如 +, *）。
实例生成：instance Num Int 会被编译为一个具体的字典值 dNumInt。

8.4 高级特性

Constructor Classes：
- Typy Class 的参数可以是类型构造器（如 List, Tree 而不是 List a）。
- 例：Functor (即 PPT 中的 HasMap)
  - ```
  class Functor f where
  fmap :: (a -> b) -> f a -> f b
```
- 这里 f 是像 List, Tree, Option 这样的容器（类型构造器），而不是具体类型。这允许 map 操作对各种容器通用
- map :: (a -> b) -> f a -> f b，其中 f 可以是 [] (List), Tree, Option。
Deriving：编译器自动生成常见 Type Class (Eq, Show) 的实例代码。