类型系统的力量

前置问题

为什么 Rust 程序不需要运行时类型信息（RTTI）就能工作？泛型代码如 fn foo<T>(x: T) 在编译后，T 去哪了？
数学中的”命题即类型，证明即程序”（Curry-Howard同构）与 Rust 的类型系统有什么深层联系？Result<T, E> 对应什么逻辑命题？
如果你写了 vec![1, 2, 3].iter().map(|x| x + 1).collect()，编译器在生成机器码之前进行了多少次”类型推导”和”类型擦除”？

1. 柯里-霍华德同构：类型即命题

1.1 基本原理

柯里-霍华德同构揭示了逻辑与编程语言之间的深层对应：

逻辑	编程语言	Rust 示例
命题 $A$	类型 `A`	`i32`
合取 $A \land B$	积类型 `(A, B)`	`(i32, String)`
析取 $A \lor B$	和类型 `Either A B`	`Result<T, E>` 或 `enum`
蕴涵 $A \to B$	函数类型 `fn(A) -> B`	`fn f(x: i32) -> bool`
全称量词 $\forall x . P (x)$	多态类型 `for<T> fn(T)`	`fn foo<T>(x: T)`
存在量词 $\exists x . P (x)$	存在类型	`dyn Trait` / `impl Trait`
$⊥$ （假）	空类型（无值）	`!`（never 类型）
$⊤$ （真）	单元类型	`()`

1.2 程序即证明

当你写出一个函数：

fn identity<T>(x: T) -> T {
    x
}

你不仅写了一个程序——你还提供了一个证明：对于任意类型 T，如果给我一个 T，我可以还你一个 T（即蕴含式 $T \to T$ 的证明）。

fn compose<A, B, C>(f: fn(B) -> C, g: fn(A) -> B) -> impl Fn(A) -> C {
    move |x| f(g(x))
}

这段代码证明了函数是可以复合的——对应逻辑中的假言三段论： $((B \to C) \land (A \to B)) \to (A \to C)$

2. Hindley-Milner 类型推导

2.1 基本原理

Rust 的类型推导基于 Hindley-Milner 类型系统（扩展了子类型、trait边界等）：

let mut v = Vec::new();  // v: Vec<_> — 类型变量 ?0
v.push(42i32);           // 合一约束: ?0 = i32
                         // 推导结果: v: Vec<i32>

2.2 合一算法

编译器内部的合一算法工作方式：

初始类型变量:
  v: Vec<?0>
  push 参数: i32
  
约束:
  ?0 = i32  （元素类型匹配）

解:
  替换 ?0 → i32
  
结果:
  v: Vec<i32>

2.3 Rust 不完全 Hindley-Milner

Rust 不能在一切地方进行完整的类型推导。这源于以下特性：

trait 多态：From<i32> 可能有多个 impl
Deref 强制转换：自动解引用影响了类型信息流
类型标注位置：函数签名通常需要显式类型以便回溯推导

// 需要显式类型标注的情况
let v: Vec<i32> = vec![];    // 编译器无法从 vec![] 推导 elem type
let x = "hello".parse();     // 编译错误：需要标注 parse::<F>() 的 F
let x: i32 = "42".parse().unwrap(); // OK：标注了解析目标类型

3. 单态化：泛型的零成本实现

3.1 什么是单态化

单态化（Monomorphization）是编译器对每个泛型函数的具体类型组合生成独立的机器码副本。

fn identity<T>(x: T) -> T { x }
 
fn main() {
    let a = identity(42i32);     // 生成 identity::<i32>
    let b = identity("hello");   // 生成 identity::<&str>
}

编译器生成（概念上）：

// 编译器生成的单态副本
fn identity_i32(x: i32) -> i32 { x }
fn identity_ref_str(x: &str) -> &str { x }

3.2 单态化的汇编视角

; 调用 identity(42i32)
mov  edi, 42
call identity_i32
 
identity_i32:
    mov  eax, edi    ; i32 通过 edi 传递，通过 eax 返回
    ret
 
; 调用 identity("hello")
lea  rdi, [rip + .L_str]  ; 加载字符串指针
mov  esi, 5               ; 字符串长度
call identity_ref_str
 
identity_ref_str:
    mov  rax, rdi    ; &str 的指针部分
    mov  rdx, rsi    ; &str 的长度部分（&str 是胖指针）
    ret

3.3 单态化 vs 装箱（Boxing）

策略	单态化（Monomorphization）	装箱/擦除（Erasure）
代码大小	增大（每个类型组合一份）	小（一份泛型代码）
运行速度	快（直接调用、可内联）	慢（虚表分发、无法内联）
缓存行为	可能更差（更多代码 → I-cache 压力）	可能更好（更小代码）
优化潜力	高（类型信息完整）	低（类型信息丢失）
代表语言	Rust, C++	Java, Haskell（默认）

3.4 单态化与二进制大小

// 产生 5 份不同的机器码：
vec![1i32, 2, 3];          // Vec::<i32>::new 等
vec![1u64, 2, 3];          // Vec::<u64>::new 等
let _ = vec![true, false]; // Vec::<bool>::new 等

缓解方案：Rust 社区使用 sccache、增量编译、LTO 优化等减少单态化的代码膨胀影响。

4. `Sized` trait：编译时大小的秘密

4.1 大小已知 vs 未知

// Sized 类型：编译器知道大小
let x: i32 = 5;            // 4 bytes
let y: [i32; 3] = [1,2,3]; // 12 bytes
 
// !Sized 类型：编译器不知道大小
let z: &[i32] = &[1,2,3];  // 16 bytes (胖指针：ptr + len)
let t: &dyn Display = &42; // 16 bytes (胖指针：ptr + vtable)
let s: &str = "hello";     // 16 bytes (胖指针：ptr + len)

4.2 `Sized` 作为默认约束

// 以下两者等价
fn foo<T>(x: T) { }
fn foo<T: Sized>(x: T) { }  // 默认约束是 T: Sized
 
// 放宽 Sized 约束
fn foo<T: ?Sized>(x: &T) { }  // T 可以是 !Sized 类型

?Sized 读作”可选 Sized”或”放宽 Sized 约束”。

4.3 胖指针的内部结构

// &dyn Trait 的内部布局（概念）
struct TraitObject {
    data_ptr: *mut (),
    vtable_ptr: *const VTable,
}
 
struct VTable {
    drop: unsafe fn(*mut ()),
    size: usize,
    align: usize,
    method1: fn(*const ()),
    method2: fn(*const (), i32) -> bool,
    // ... 更多方法指针
}

; 调用 trait 对象上的方法
; rdi = data_ptr, rsi = vtable_ptr
mov  rax, [rsi + 24]   ; 从虚表中加载第3个方法指针（偏移24=3×8）
call rax               ; 间接调用（间接跳转有分支预测惩罚）

5. Never 类型 `!`：类型论的底类型

5.1 底类型的数学意义

在类型论中， $⊥$ （底类型）是没有值的类型——它意味着计算永远不会成功返回。

// ! 类型（never type）尚未完全稳定，但已经在多处使用
fn never_returns() -> ! {
    loop {}  // 无限循环
}
 
fn always_panics() -> ! {
    panic!("crash")
}

5.2 应用：Result 和 Option 的类型魔法

// ! 可以自动转换为任何类型（这是底类型的关键性质）
let x: Result<i32, String> = Ok(42);
let val = match x {
    Ok(v) => v,
    Err(e) => panic!("error: {}", e),  // panic! 返回 !，自动适配为 i32
};

在类型论中： $⊥$ 是范畴的初始对象，存在从 $⊥$ 到任何类型的唯一态射（morphism）。

5.3 底层实现：没有值的返回

; fn panic() -> ! 的汇编
panic:
    ; ... 调用 panic handler ...
    ud2  ; 未定义指令（CPU 会触发异常），确保绝对不会返回
    ; 或者:
    int3 ; 断点指令

编译器知道 ! 类型没有返回值，因此可以：

省略 panic 之后的不可达代码
合并控制流（因为 ! 分支不会返回，不需要设置返回值寄存器）

6. 类型状态编程模式

6.1 将状态编码为类型

// 类型状态模式：在编译时追踪状态
struct Open;
struct Closed;
 
struct Connection<State> {
    state: PhantomData<State>,
    fd: i32,
}
 
impl Connection<Closed> {
    fn new() -> Self { Connection { state: PhantomData, fd: -1 } }
    fn open(self) -> Connection<Open> {
        let fd = unsafe { libc::open(b"/dev/null\0".as_ptr(), libc::O_RDONLY) };
        Connection { state: PhantomData, fd }
    }
}
 
impl Connection<Open> {
    fn read(&self, buf: &mut [u8]) -> usize {
        unsafe { libc::read(self.fd, buf.as_mut_ptr(), buf.len()) as usize }
    }
    fn close(self) -> Connection<Closed> {
        unsafe { libc::close(self.fd); }
        Connection { state: PhantomData, fd: -1 }
    }
}

对应出价：不能对 Connection<Closed> 调用 read（编译错误），不能对 Connection<Open> 调用 open（编译错误）。

6.2 PhantomData 的零大小

PhantomData<T> 的大小是 0 字节——它在运行时不存在。它是一种编译时”标记”，告诉类型系统：

$sizeof (PhantomData < T >) = 0$

7. 类型驱动的代码生成

7.1 std::mem::size_of 和对齐

// 编译器在编译时计算布局
#[repr(C)]
struct Foo {
    a: u8,   // 1 byte, offset 0
    // 1 byte padding
    b: u16,  // 2 bytes, offset 2
    c: u32,  // 4 bytes, offset 4
}
// size = 8, align = 4

// C 中同样的结构
struct Foo {
    uint8_t  a;
    // padding
    uint16_t b;
    uint32_t c;
};
// sizeof(struct Foo) == 8, alignof == 4

两个编译器（rustc 和 clang/gcc）生成相同的布局，因为都遵循相同的平台 ABI（System V AMD64）。

7.2 判别联合（enum）的布局优化

enum Option<Box<i32>> {
    None,        // 空指针优化: None 用 null 表示
    Some(Box<i32>),  // Box 永不为 null
}
// size_of::<Option<Box<i32>>>() == 8  ← 仅一个指针！

enum Result<u32, u32> {
    Ok(u32),   // 表示：tag=0 + u32
    Err(u32),  // 表示：tag!=0 + u32
}
// size_of::<Result<u32, u32>>() == 8 (4 for data, 4 for discriminant...)

Rust 编译器的布局优化器寻找：

空指针优化：NonZero 类型、Box、&T、&mut T 等永不为空的值
判别式压缩：将判别式（tag）放入未使用的比特位
字段合并：重叠不能同时有效的变体字段

8. ASM 深度分析：泛型 vs 具体类型

8.1 泛型函数

pub fn max<T: Ord>(a: T, b: T) -> T {
    if a > b { a } else { b }
}

; 泛型 max 本身不产生任何机器码（在 Rust 中）
; 实际上，泛型 max 的代码以 MIR 形式存储，在单态化时被复制
 
; 调用 max::<i32> 后生成的代码：
max_i32:
    cmp edi, esi      ; 比较 a 和 b
    cmovg eax, edi    ; 如果 a > b，选 a
    cmovle eax, esi   ; 如果 a <= b，选 b
    ret

8.2 对比：运行时多态（dyn Trait）

fn polymorphic_max(a: &dyn Ord, b: &dyn Ord) -> bool {
    a.gt(b)
}

; 动态分发版
polymorphic_max:
    ; a 的胖指针在 (rdi, rsi): (data_ptr, vtable_ptr)
    ; b 的胖指针在 (rdx, rcx)
    mov  rax, [rsi + 24]  ; 从 a 的虚表加载第3个方法（假设 gt 的偏移是24）
    call rax              ; 间接调用 — 目标地址到运行时才知道
    ret

9. 对比：C++ 模板 vs Rust 泛型

特性	C++ 模板	Rust 泛型
实例化时机	编译时（懒惰）	编译时（早期）
错误消息	模板定义时无检查，实例化时报错（长且混乱）	定义时即检查 trait 边界
概念/约束	C++20 concepts（后添加的）	trait bounds（从一开始就有）
SFINAE	支持	不直接支持（但有 trait 技巧）
特化	全特化 + 偏特化	无偏特化（用 trait + 泛型模拟）
代码膨胀	常见（每个实例化一份）	相同（单态化本质相同）

// C++ 模板：调用方才知道是否合法
template<typename T>
T max(T a, T b) {
    return a > b ? a : b;  // 如果 T 没有 operator>，在这里报错
}

// Rust 泛型：定义时就检查约束
fn max<T: Ord>(a: T, b: T) -> T {
    if a > b { a } else { b }  // T: Ord 必须已在 impl 时提供
}

本章考查

概念考查（每题2分，共20分）

根据柯里-霍华德同构，Result<T, E> 对应什么逻辑命题？
- A) $T \land E$
- B) $T \lor E$ （析取）
- C) $T \to E$
- D) $\neg T$
单态化（Monomorphization）与类型擦除（Type Erasure）的核心区别是：
- A) 单态化为每个具体类型生成独立代码，类型擦除使用一份泛型代码 + 类型转换
- B) 单态化在运行时进行，类型擦除在编译时进行
- C) 两者完全相同
- D) 类型擦除比单态化更快
Sized trait 的默认约束意味着：
- A) 所有类型必须是堆分配的
- B) 编译器在编译时知道该类型的大小
- C) 类型的大小在运行时计算
- D) 类型必须用 Box 包装
PhantomData<T> 在运行时的内存大小是：
- A) 与 T 相同
- B) 8 字节（一个指针大小）
- C) 0 字节（编译时标记，无运行时表示）
- D) 1 字节
从不返回的函数（返回 ! 类型）的机器码通常会：
- A) 在结尾处添加 ret 指令
- B) 添加 ud2 指令或等效的不可达标记
- C) 正常返回到调用者
- D) 跳转到程序入口
Rust 编译器对 enum 进行的布局优化包括：
- A) 只是简单的 tag + union，无优化
- B) 空指针优化、判别式压缩、字段重叠等
- C) 总是使用 64 位对齐
- D) 将所有枚举转换为虚表
dyn Trait 的胖指针由什么组成？
- A) 一个指针和引用计数
- B) 一个数据指针和一个虚表（vtable）指针
- C) 只有数据指针
- D) 数据指针和长度
C++ 模板与 Rust 泛型的主要区别是：
- A) Rust 泛型有 trait 约束，在定义时即检查；C++ 模板通常在使用时检查
- B) C++ 模板更快
- C) Rust 泛型不支持整数类型
- D) 完全一样
在 Hindley-Milner 类型推导中，“合一（unification）“的作用是：
- A) 生成汇编代码
- B) 求解类型变量之间的等式约束以推导具体类型
- C) 编译宏
- D) 链接目标文件
为什么 Rust 需要在某些地方显式标注类型？
- A) 因为编译器偷懒
- B) 因为 trait 多态和 Deref 强制等特性导致某些场景的类型无法完全推导
- C) 因为所有类型都必须显式标注
- D) 因为 LLVM 的要求

点击查看答案

B — Result<T, E> 是 T | E 的析取（sum type），对应逻辑中的析取命题 $T \lor E$ 。
A — 单态化产生多份代码（每类型一份），类型擦除用一份代码 + 运行时类型转换。
B — Sized 约束表示类型在编译时大小已知，可以放在栈上。
C — PhantomData<T> 是零大小的类型标记，仅在编译时存在。
B — 返回 ! 的函数在结尾处使用 ud2 等指令，向 CPU 和 LLVM 表明此代码永远不可达。
B — Rust 编译器对枚举进行多种布局优化以减小内存占用。
B — dyn Trait 的胖指针 = 数据指针（指向具体值）+ 虚表指针（指向方法表）。
A — Rust 泛型通过 trait 约束在定义时即进行类型检查，C++ 模板通常在使用（实例化）时才检查。
B — 合一是类型推导的核心算法，通过解类型变量之间的等式来确定具体类型。
B — 由于 trait 多态（多个可能的 impl）和 Deref 强制转换等因素，部分场景类型信息不足。

判断正误（每题2分，共20分）

单态化导致每个泛型类型组合生成独立的机器码副本，会增加二进制文件大小。
dyn Trait 的虚表方法调用与直接函数调用在 CPU 层面延迟相同。
柯里-霍华德同构揭示了类型系统中的 () 对应逻辑中的 $⊤$ （真），! 对应 $⊥$ （假）。
Rust 的类型推导是完整且全局的，无需任何类型标注。
#[repr(C)] 确保结构体布局与 C ABI 兼容，可以安全地传递给 C FFI。
PhantomData<T> 的大小为 8 字节，以存储对 T 的引用。
C++ 的 SFINAE 和 Rust 的 trait bounds 解决了相同的泛型约束问题，但机制不同。
在 Option<&T> 中，None 变体通过 null 指针表示，因此 sizeof(Option<&T>) = sizeof(usize)。
泛型函数在 Rust 中不产生任何二进制代码——只有被实际使用的具体类型才生成代码。
!（never 类型）不能作为泛型的类型参数。

点击查看答案

正确 — 单态化为每个 <T> 组合生成独立副本，这是性能与代码大小的权衡。
错误 — 虚表调用需要间接跳转（call [rax+offset]），有分支预测惩罚和 I-cache 压力。
正确 — 在 CH 同构中，() 是单元类型只有一个值对应”永真”，! 无值对应”永假”。
错误 — Rust 使用 Hindley-Milner 风格推导但仍需函数签名、集合类型等标注。
正确 — #[repr(C)] 确保与 C 编译器的布局和 ABI 兼容。
错误 — PhantomData<T> 大小为零，仅存在于编译时类型检查中。
正确 — 两者都解决泛型约束但 SFINAE 基于替换失败、trait bounds 基于显式边界。
正确 — 空指针优化使 Option<&T> 大小仅为指针大小。
正确 — 泛型函数在 MIR 中存储、在单态化时才生成机器码。
错误 — ! 可以作为类型参数，例如 Result<(), !> 表示永不失败的 Result。

代码分析（每题3分，共15分）

以下代码的 size_of 结果是什么？

use std::mem::size_of;
enum E { A(u8), B(u16), C }
println!("{}", size_of::<Option<E>>());

A) 1 字节
B) 2 字节
C) 4 字节
D) 8 字节

点击查看答案

**C** — E 本身需要 4 字节（1 tag + 2 最大变体 + 对齐），`Option` 使用 E 的一个未使用的 tag 值表示 `None`（判别式压缩），所以大小不变。

泛型函数 fn foo<T>(x: T) -> T { x } 在以下调用中生成几份代码？

foo(1i32);
foo(2i32);
foo(3u64);

A) 1 份
B) 2 份
C) 3 份
D) 0 份

点击查看答案

**B** — 2 份：`foo::` 和 `foo::`。同一具体类型的多次调用共享同一份机器码。

以下代码体现了什么类型优化？

let x: Option<Box<i32>> = None;
assert_eq!(size_of_val(&x), 8);

A) 尾递归优化
B) 空指针优化（Null Pointer Optimization）
C) 死代码消除
D) 内联优化

点击查看答案

**B** — `Box` 从不为 null，所以 None 可以用 null 指针表示。

&dyn Display 作为胖指针时占据多少字节？

let x: &dyn Display = &42;
size_of_val(x)  // ?

A) 8 字节（仅数据指针）
B) 16 字节（数据指针 + 虚表指针）
C) 24 字节（加上引用计数）
D) 取决于所指类型

点击查看答案

**B** — 胖指针 = 8 字节数据指针 + 8 字节虚表指针 = 16 字节。

以下代码中的类型状态模式用什么防止错误使用？

let conn = Connection::<Closed>::new();
conn.read(&mut buf);  // 编译错误！
let conn = conn.open();
conn.read(&mut buf);  // OK

A) 运行时状态检查
B) PhantomData + 泛型参数在编译时将状态编码为不同类型
C) 虚表分发
D) 反射

点击查看答案

**B** — 类型状态模式将状态编码在类型参数中，编译时确保方法调用合法性。

编程大题（15分）

题目: 使用类型状态（typestate）模式实现一个 Builder，在编译时保证构建顺序的完整性。

// 要求：
// 1. HttpRequest 有三个必需步骤：set_method → set_url → set_body
// 2. 每个步骤只能在特定状态下调用
// 3. 只有完成所有步骤后才能 build
// 4. 使用 PhantomData 和零大小标记类型
 
pub struct HttpRequest {
    method: String,
    url: String,
    body: Vec<u8>,
}
 
// 状态标记类型
pub struct NoMethod;
pub struct HasMethod { method: String }
pub struct HasUrl { method: String, url: String }
 
// 构建器
pub struct RequestBuilder<State> {
    state: State,
}
 
impl RequestBuilder<NoMethod> {
    pub fn new() -> Self {
        RequestBuilder { state: NoMethod }
    }
 
    // TODO: 实现 set_method，将状态推进到 HasMethod
    // pub fn set_method(self, method: &str) -> RequestBuilder<HasMethod>
}
 
impl RequestBuilder<HasMethod> {
    // TODO: 实现 set_url，将状态推进到 HasUrl
    // pub fn set_url(self, url: &str) -> RequestBuilder<HasUrl>
}
 
impl RequestBuilder<HasUrl> {
    // TODO: 实现 set_body 和 build
    // pub fn set_body(self, body: Vec<u8>) -> RequestBuilder<HasUrl>
    // pub fn build(self) -> HttpRequest
}

点击查看答案

pub struct HttpRequest {
    method: String,
    url: String,
    body: Vec<u8>,
}
 
pub struct NoMethod;
pub struct HasMethod { method: String }
pub struct HasUrl { method: String, url: String }
 
pub struct RequestBuilder<State> {
    state: State,
}
 
impl RequestBuilder<NoMethod> {
    pub fn new() -> Self {
        RequestBuilder { state: NoMethod }
    }
 
    pub fn set_method(self, method: &str) -> RequestBuilder<HasMethod> {
        RequestBuilder {
            state: HasMethod { method: method.to_string() }
        }
    }
}
 
impl RequestBuilder<HasMethod> {
    pub fn set_url(self, url: &str) -> RequestBuilder<HasUrl> {
        RequestBuilder {
            state: HasUrl {
                method: self.state.method,
                url: url.to_string(),
            }
        }
    }
}
 
impl RequestBuilder<HasUrl> {
    pub fn set_body(mut self, body: Vec<u8>) -> Self {
        // body 直接存在 state 里或暂时不管
        self
    }
 
    pub fn build(self) -> HttpRequest {
        HttpRequest {
            method: self.state.method,
            url: self.state.url,
            body: Vec::new(),
        }
    }
}

评分标准：

实现 RequestBuilder<NoMethod>::set_method（4分）
实现 RequestBuilder<HasMethod>::set_url（4分）
实现 RequestBuilder<HasUrl>::build（4分）
代码风格和文档（3分）

填空题（每题1分，共5分）

柯里-霍华德同构中，函数类型 A → B 对应于逻辑中的 ____ 命题。
单态化在 Rust 编译管线中发生在 ____ 到 ____ 的阶段。
! 类型在类型论中称为 ____ 类型。
dyn Trait 的胖指针由 ____ 和 ____ 两部分组成。
#[repr(C)] 确保结构体布局与 ____ 兼容。

点击查看答案

蕴涵（implication）
MIR，LLVM IR（泛型 MIR 在单态化时展开为具体类型的 MIR）
底（bottom）
数据指针（data pointer），虚表指针（vtable pointer）
C ABI（或 C 语言调用约定）

代码补全（共5分）

使用 ?Sized 放宽类型约束（1分）：

// 使得该函数接受任何类型的引用，包括 unsized 类型
fn print_ref<T: ____>(x: &T) where T: std::fmt::Display {
    println!("{}", x);
}

点击查看答案

fn print_ref<T: ?Sized>(x: &T) where T: std::fmt::Display {
    println!("{}", x);
}

利用 ! 类型的性质（2分）：

// 补全使 match 通过类型检查
let val: i32 = match result {
    Ok(v) => v,
    Err(e) => ____,  // 此分支返回 !，自动适配为 i32
};

点击查看答案

Err(e) => panic!("error: {}", e),
// 或
Err(e) => return Err(e),
// 或
Err(e) => loop {},
// 任何返回 ! 类型的表达式

类型状态模式的标记（2分）：

use std::marker::____;
 
struct File<State> {
    fd: i32,
    _marker: ____<State>,
}

点击查看答案

use std::marker::PhantomData;
 
struct File<State> {
    fd: i32,
    _marker: PhantomData<State>,
}

本章小结

Rust 的类型系统不仅是”避免运行时错误”的工具——它是程序正确性的形式化框架：

柯里-霍华德同构：类型即命题，程序即证明；每一个正确类型的函数都是一个逻辑证明
Hindley-Milner：类型推导通过合一算法自动求解类型变量，减少标注
单态化：泛型的零成本实现——每个具体类型产生独立代码，运行时无虚表开销
Sized/?Sized：编译时大小的静态追踪，区分栈上值和胖指针
! 类型：底类型在类型论中对应假命题，在 Rust 中用于表达不可达控制流
类型状态：利用泛型和 PhantomData 在编译时编码状态机，消除运行时检查

理解类型系统就是理解 Rust 在”编译前”与”编译后”之间建立的桥梁：一个从逻辑到代码的翻译机制。

下一章：05-Trait系统的计算机科学 — 从 Haskell 的类型类继承到 LLVM 的虚表生成，全面理解 trait。

深度阅读：Philip Wadler, “Theorems for Free!”; Benjamin C. Pierce, “Types and Programming Languages”; Rust Compiler Dev Guide — Type System

练习

题号	题目	链接	知识点
146	LRU 缓存	https://leetcode.cn/problems/lru-cache/	双向链表 + 哈希表
23	合并 K 个升序链表	https://leetcode.cn/problems/merge-k-sorted-lists/	链表、分治
21	合并两个有序链表	https://leetcode.cn/problems/merge-two-sorted-lists/	链表、递归
102	二叉树的层序遍历	https://leetcode.cn/problems/binary-tree-level-order-traversal/	BFS、队列
236	二叉树的最近公共祖先	https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/	递归、树

RootStack

探索

04-类型系统的力量

类型系统的力量

前置问题

1. 柯里-霍华德同构：类型即命题

1.1 基本原理

1.2 程序即证明

2. Hindley-Milner 类型推导

2.1 基本原理

2.2 合一算法

2.3 Rust 不完全 Hindley-Milner

3. 单态化：泛型的零成本实现

3.1 什么是单态化

3.2 单态化的汇编视角

3.3 单态化 vs 装箱（Boxing）

3.4 单态化与二进制大小

4. Sized trait：编译时大小的秘密

4.1 大小已知 vs 未知

4.2 Sized 作为默认约束

4.3 胖指针的内部结构

5. Never 类型 !：类型论的底类型

5.1 底类型的数学意义

5.2 应用：Result 和 Option 的类型魔法

5.3 底层实现：没有值的返回

6. 类型状态编程模式

6.1 将状态编码为类型

6.2 PhantomData 的零大小

7. 类型驱动的代码生成

7.1 std::mem::size_of 和对齐

7.2 判别联合（enum）的布局优化

8. ASM 深度分析：泛型 vs 具体类型

8.1 泛型函数

8.2 对比：运行时多态（dyn Trait）

9. 对比：C++ 模板 vs Rust 泛型

本章考查

概念考查（每题2分，共20分）

判断正误（每题2分，共20分）

代码分析（每题3分，共15分）

编程大题（15分）

填空题（每题1分，共5分）

代码补全（共5分）

本章小结

练习

练习

关系图谱

目录

反向链接

4. `Sized` trait：编译时大小的秘密

4.2 `Sized` 作为默认约束

5. Never 类型 `!`：类型论的底类型