ThinkLab

编译器课程里最容易“碎片化”的内容，往往不是某一条规则本身，而是这些规则之间的因果关系：为什么前端要做名字解析，为什么中间表示偏爱 SSA，为什么 tail call 和 non-tail call 会把实现复杂度拉开，为什么动态类型最终会逼出 tagging、heap allocation 和 closure conversion。

把这些主题串起来，会得到一条非常清晰的实现主线：

源程序的名字与结构先被前端规范化， 语义再由解释器或形式化规则定义清楚， 随后被降低到一种更利于分析和代码生成的 IR（这里是 SSA）， 最后再映射到 x86 这样的目标机器模型上执行。当语言从“只有整数表达式”逐渐扩展到条件、循环、函数、动态类型、数组、闭包时，这条主线也会层层加厚。

下面按这个顺序，对六个主题做一次系统讲解。

一、Well-formedness 与 Name Resolution：编译器前端真正做的第一件事

1. 解析成功，不代表程序合法

很多初学者会把“语法正确”和“程序合法”混在一起。实际上，parser 只负责回答一件事：这串字符能否被某个 grammar 归约成 AST。

但很多真正关键的约束，并不适合放在 parser 里做。例如：

let x = 1 in x + y

这串程序从语法上完全合法，却依然是错误程序，因为 y 没有绑定来源。

因此，编译器前端通常分成三层：

词法分析：把字符流切成 token
语法分析：把 token 归约成 AST
语义分析：检查“语法树是否真的表示一个合法程序”

well-formedness 本质上就是第三层中的一部分：它关心的不是“像不像程序”，而是“是不是一个在静态上自洽的程序”。

2. Scope：名字到底在什么地方有效

作用域（scope）回答的问题是：

一个变量名的某次使用，究竟对应哪个绑定点？

先看最基本的例子：

let x = 3 in
  x + 1

这里 x 的 let 是 binding site，后面的 x 是 use site。如果某次 use site 落在某个 binding 的作用域内，这次使用就是 bound 的；否则就是 free 的。

因此：

bound variable：能追溯到某个 binding site 的使用
free variable：找不到对应 binding site 的使用

例如：

x + 1

这里的 x 是 free variable。对大多数非交互式语言，这通常是前端错误。

3. Shadowing：同名绑定不是同一个变量

再看：

let x = 1 in
  let x = 2 in
    x

这里有两个名字都叫 x，但它们不是同一个变量。第二个绑定把第一个绑定“遮蔽”了，这叫 shadowing。

shadowing 的核心不是“覆盖值”，而是：

内层出现了一个新的绑定，它恰好复用了同一个字符串名字。

这点非常重要。因为从语义上说，shadowing 不是赋值，不是更新，而是引入了一个新的变量实体。

这也是为什么很多编译器后续会把“可变变量更新”也类比成“产生新版本变量”——后面讲 SSA 时会再次看到这个思想。

4. Free / Bound 的意义，不只是报错

free 和 bound 的区分，不只是为了抓未声明变量。

它还决定了很多变换是否正确。最经典的是 capture 问题。看一个 beta-reduction 风格的替换：

let x = e1 in e2

如果把它“内联”为“把 e2 中的 x 全部替换成 e1”，听起来很自然，但这只有在不会发生变量捕获时才成立。

例如：

let x = y in
  let y = 10 in
    x

如果直接把 x 替换成 y，会得到：

let y = 10 in
  y

这时原来那个 free 的 y 被内层 let y = 10 捕获了，程序语义改变了。

因此，名字问题绝不是“字符串匹配”那么简单；它本质上是在维护绑定关系。

5. Name resolution：把字符串名字解析成唯一身份

为了彻底摆脱“同名字符串”的麻烦，编译器前端通常会做一件关键变换：

把程序里每个绑定都重命名成全局唯一标识符。

例如：

let x = 1 in
  let x = x + 1 in
    x

经过解析与重命名后，可以变成：

let x#1 = 1 in
  let x#2 = x#1 + 1 in
    x#2

此时：

shadowing 仍然被保留为语义事实
但“名字冲突”从实现层面消失了
每次 use site 都能唯一指向某个 binding site

这一步常被叫做：

name resolution
alpha-renaming
uniquification
name mangling（某些语境下）

为什么唯一化这么重要？

因为它立刻带来几个巨大的工程收益：

第一，避免 capture。 后续做代码移动、内联、lambda lifting、closure conversion 时，不再需要担心“搬过去以后撞名”。

第二，简化环境实现。 解释器、SSA 生成器、优化器都不必再处理“当前这个 x 是哪一个 x”。

第三，和 SSA 的哲学天然一致。 SSA 要求每个绑定只赋值一次，名字全局唯一正好是理想起点。

6. well-formedness 在命令式语言里会继续扩展

当语言加入 while、break、continue、return 等构造时，well-formedness 不再只包括“变量声明后使用”，还会多出一批控制流约束，例如：

break / continue 只能出现在某个 enclosing loop 内
过程若声明“必须返回值”，则每条控制路径都必须以 return 结束
变量不能在未声明前使用
shadowing 允许，但应在语义上视为新变量

这说明 well-formedness 本质上是：

前端对“后续阶段愿意接收什么程序”的静态承诺。

二、Interpreters 与 Language Semantics：解释器不是“玩具”，而是可执行语义

1. 为什么实现解释器很重要

解释器的价值不在于“方便运行程序”，而在于：

它把语言语义写成了一个可执行的参考实现。

对于一个编译器项目，最稳的路线通常是：

先定义 AST
再写解释器
再写编译器
用解释器结果对拍编译器结果

这样，编译器不是在“猜语言行为”，而是在实现一个已经明确的语义模型。

2. 语义要回答的核心问题

对任何语言构造，语义都至少要说明：

先算什么，后算什么
哪些表达式会产生值
哪些表达式会报错
报错发生在什么时候
控制流如何转移

举例：

if e1 then e2 else e3

语义至少要明确：

先求值 e1
根据 e1 的结果选择分支
只求值其中一个分支
整个 if 表达式的值，就是所选分支的值

第三点非常关键。因为如果实现错成“两个分支都算，再挑一个结果”，很多程序会立刻语义错误，尤其当分支里有副作用或错误时。

3. evaluation order：求值顺序是语义的一部分，不是实现细节

考虑：

f(g(), h())

如果语言规定参数按从左到右求值，那么必须先执行 g()，再执行 h()。如果 g() 和 h() 有打印、抛错、修改状态，那么顺序不同，程序行为就不同。

编译器里一个常见误区是：把“表达式树”看成天然无序。实际上，只要语言不是纯函数式且无副作用，求值顺序就是语义的一部分。

这也是为什么后续 lowering 到 SSA 时，需要显式编码 evaluation order，而不能只保留“依赖关系”。

4. compile-time errors 与 runtime errors 的边界

编译期错误（compile-time errors）

编译器前端就能确定程序必错，因而拒绝生成目标代码。典型例子：

free variable
函数实参数量与形参数量不符（在一阶函数语言中可静态决定）
不合法的 break
某些静态类型错误

例如静态类型语言中的：

true + 5

前端就可以拒绝。

运行期错误（runtime errors）

程序是否出错，取决于运行时值。典型例子：

动态类型检查失败
数组越界
除零
空指针/非法地址（若语言允许）

例如动态类型语言中的：

x + 5

若 x 的类型只有运行时才知道，那么错误只能在执行到 + 时触发。

5. 动态类型里，错误时机也依赖求值顺序

考虑：

true + (let _ = print(3) in 3)

一个看似简单、实际非常关键的问题是：

是先打印 3，再报类型错误？还是先报错，根本不打印？

如果语言规定从左到右求值，那么过程通常是：

求值左操作数 true
求值右操作数 (let _ = print(3) in 3)，打印 3
执行 + 前做类型检查
发现不是两个整数，于是报 runtime error

这里“何时报错”不是后端随意决定的，而是语义的一部分。因此，动态类型实现不只是“加标签”，而是“在正确时机做标签检查”。

三、x86 Abstract Machine：理解目标机器，才能理解后端设计

很多编译器课程并不直接教“真实 CPU 微架构”，而是教一个足够精确的 x86 abstract machine。它不是硬件电路图，而是后端代码生成所需的语义接口。

1. 机器状态：寄存器、内存、指令指针、标志位

可以把 x86 抽象机理解成包含以下状态：

寄存器（registers）
内存（memory）
指令指针 rip
标志寄存器 rflags

Registers

64 位通用寄存器包括：

rax, rbx, rcx, rdx
rsi, rdi
rsp, rbp
r8 到 r15

寄存器访问快，但数量少。因此寄存器本质上是“最贵、最快、最稀缺”的存储资源。

Memory

内存是一个巨大的按字节寻址空间。栈、堆、代码段，本质上都只是内存里的不同区域。

2. rip：为什么大多数指令“顺序执行”

顺序执行不是魔法，而是因为：

当前要执行哪条指令，由 rip 决定。

每一步执行时：

取出 [rip] 所指向的机器指令
执行它
大多数指令会把 rip 自动更新为“下一条指令地址”

所以 mov、add、sub 等看起来像“顺序执行”，本质上只是它们默认把控制流交给后继地址。

3. Labels：汇编里的“名字”，其实是地址别名

汇编代码中写：

loop:
  ...

这里 loop 不是高级语言意义上的变量名，而是某个代码地址的符号名字。因此：

label 是地址的符号别名
jmp loop 实际上就是把 rip 改成 loop 所对应地址

这点极其重要，因为中间表示里的 basic block、join point、function entry，最后都会被编译成 label。

4. jmp 与条件跳转：控制流的基础原语

无条件跳转 jmp

jmp loc

语义很直接：

把 rip 设为 loc

也就是立刻转移控制流。

条件跳转 jcc

jz loc
jnz loc
jl loc
jle loc
jg loc
...

jcc 是一族指令，cc 表示 condition code。它们读取 rflags 中的标志位，根据条件决定是否跳转。

所以条件跳转的本质不是“自己做比较”，而是：

先由某条指令设置 flags
再由 jcc 读取 flags 决定去向

这也是为什么 cmp/test 如此重要。

5. rflags：很多控制流其实是“副作用驱动”的

最相关的几个 flag 通常是：

ZF（zero flag）：结果是否为 0
SF（sign flag）：结果是否为负
OF（overflow flag）：是否发生有符号溢出

像 add、sub、imul 这样的算术指令，除了写回结果，还会顺手更新 flags。后续条件跳转就能用这些副作用。

例如：

sub rax, rcx

不仅算出 rax - rcx，还会更新 ZF/SF/OF。

6. cmp：只比较，不保存结果

cmp a, b

可以把它理解为：

像执行 a - b 一样设置 flags，但不写回结果

因此，cmp 的目标不是得到差值，而是准备条件判断。例如：

cmp rax, rbx
jl less

意思就是：如果 rax < rbx，跳到 less。

7. test：按位与式的“探针”

test a, b

它像按位 and 一样设置 flags，但也不写回结果。

最常见用法是检查某些 bit 是否被置位。例如动态类型标签检查中，常见：

test rax, 1
jnz not_int

如果最低位是 1，说明它不是“整数格式”，于是跳错。

因此：

cmp 擅长“大小/相等比较”
test 擅长“看某几位是否满足位模式”

8. 栈与 rsp：函数调用进入后端核心

rsp 是 stack pointer。栈通常向低地址增长，所以：

push x：先 rsp -= 8，再写入值
pop rax：先读 [rsp]，再 rsp += 8

而：

call f

本质上相当于：

把“下一条指令地址”压栈
跳到 f

ret

本质上相当于：

从栈顶弹出返回地址
跳过去

因此，non-tail call 的本质就是：控制流跳走之前，必须把“回来以后从哪继续”保存起来。

四、Translation into SSA：把树状语义变成线性、可分析的控制流图

SSA（Static Single Assignment）是现代编译器最核心的 IR 思想之一。

其直觉可以概括为：

每个变量只绑定一次；控制流合流处用显式参数或 ϕ 来表达“值从哪里来”。

1. 为什么需要 SSA

源语言中的表达式通常是树：

(2 - 3) + (4 * 5)

而目标机器代码通常是线性的：

x0 = 2
x1 = 3
x2 = sub x0 x1
x3 = 4
x4 = 5
x5 = mul x3 x4
x6 = add x2 x5
ret x6

SSA 的价值就在于：

把树打平为顺序代码
显式暴露数据依赖
保持变量不可变
让优化更容易做

2. 用 continuations 编码求值顺序

把表达式 lowering 到 SSA 时，最关键的问题是：

当前子表达式算完之后，结果要放哪？接下来又要执行什么？

这正是 continuation 的角色。可以把 continuation 理解为：

一个“结果目的地变量”
一段“结果写好以后继续执行的代码”

例如编译 e1 + e2 时：

先编译 e1
再编译 e2
再发出 add
再接上原 continuation

于是，continuation-passing style（CPS 风格 lowering）本质是在把树的求值顺序显式化。

这一步尤其重要，因为“左到右求值”之类的语义，在 AST 里往往是隐含的，在 SSA 里必须变成显式顺序。

3. 条件分支会暴露 continuation 的共享问题

考虑：

if c then e1 else e2

若整个 if 的结果后面还要继续参与更大表达式，例如：

(if c then e1 else e2) * x

那么 e1 和 e2 算完后，都要继续执行同一段“乘以 x”的代码。也就是说，两个分支共享同一个 continuation。

最笨的方法是：把 continuation 复制进两个分支。这样语义是对的，但代码大小会爆炸；多个嵌套/串联的 if 会导致指数级复制。

4. Join point：把“共享 continuation”变成显式控制流节点

更好的办法是：

新建一个 block
让 then / else 都跳到这个 block
在这个 block 里继续执行后续代码

这个 block 就是 join point。

join point 不是普通“代码片段”，而是：

多条控制流汇合后，继续同一段后续计算的节点

问题是：then 和 else 产生的结果可能不同，join point 如何知道该用哪个值？

5. Parameterized blocks / ϕ nodes：合流点的值流显式化

解决方案是让 join point 带参数：

join(v):
  ...

then 分支跳过去时传 v1：

br join(v1)

else 分支跳过去时传 v2：

br join(v2)

这和传统 SSA 里的 ϕ-node 是同一思想的两种写法：

传统 CFG SSA：在 block 开头写 v = phi(v1, v2)
参数化 block SSA：分支跳转时显式带参数

参数化 block 的优点是语义非常直接：

join point 本身就是 continuation，continuation 有一个输入值，于是 block 就有一个参数。

6. branch with arguments：语义上是“同时赋值”

当写：

br f(a, b)

并且 f(x, y) 是目标 block 时，语义上应理解为：

x := a
y := b
jump f

而且 x := a 与 y := b 必须是同时生效的。否则会出现覆盖问题。

例如：

f(a, b)
br f(b, a)

如果后端天真地顺序翻译成：

mov x, y
mov y, x

第二条读到的 x 已经不是旧值了，结果错误。

因此，branch with arguments 的 lowering 必须小心处理，通常要靠：

额外 temporaries
move scheduling
或更复杂的 parallel copy 消解算法

这也是 SSA 到 x86 代码生成的一个经典坑点。

7. 命令式更新如何翻译到 SSA：把“赋值”看成“新版本”

在命令式语言里：

x := x + 1

和函数式语言中的 shadowing 非常像。 SSA 的处理方式通常是：

x1 = ...
x2 = x1 + 1

所以“变量更新”在 SSA 里并不是真的“改写旧变量”，而是：

产生该变量的新版本

对 straight-line code，这几乎就等价于 shadowing。对 if / while，则需要在 join point 上把不同版本重新汇合。

这正是 SSA 为什么擅长编译命令式程序：它把“可变状态”转换成了“不可变版本流”。

8. 循环本质上也是 join point

对 while：

while cond {
  body
}

循环头通常有两个前驱：

进入循环前的入口
一次迭代结束后的回边

因此循环头天然是 join point。如果循环体中会更新变量，那么这些变量就应成为循环头参数。

这也是为什么很多教材里，循环翻到 SSA 后会长成：

loop(x_cur, y_cur):
  ...
  cbr cond body(...) done(...)

循环头参数本质上就是“跨迭代携带的状态”。

9. Minimal SSA：不是所有 block 参数都值得保留

粗糙的做法是：只要一个 join point 可能用到某些变量，就把“所有在 scope 中的变量”都当成参数传进去。这叫一种非常保守的 ϕ-node insertion 思路。

它一定正确，但往往很臃肿。

minimal SSA 的目标

用尽可能少的 block arguments（或 phi nodes）表达同样的值流。

为什么重要？

因为每个 block 参数最终都可能编译成 move。参数越多，代码越冗余，优化空间越差。

10. 最小化通常分两步：block sinking 与 parameter dropping

block sinking

把 block 定义尽量往下沉，让更多变量天然处在它的定义作用域中。这样有些本来必须通过参数传入的值，就不需要传了。

parameter dropping

如果某个 block 参数其实永远只会被同一个变量实例化，或者只会传自己，那么这个参数是冗余的，可以删掉，并把 block 内部引用直接改成那个变量。

例如某参数 x 在所有来路上总是由 y 传入，那么 x 和 y 就没有必要并存。

对结构化命令式程序，有一个非常实用的结论：

用粗糙的参数插入先得到一个正确但臃肿的 SSA，再做 parameter dropping，往往就足够得到最小 SSA；不必额外做复杂 block sinking。

这也是实际实现里很常见的路线：先保证正确，再做瘦身。

11. Lambda lifting：局部函数进入真实调用世界之前的“去嵌套化”

当局部函数只被局部 tail call 使用时，它和参数化 block 几乎是同一回事。因为：

不需要真实 call/ret
不需要单独栈帧
控制流只是 branch
外层变量仍然在当前上下文可访问

但一旦局部函数出现 non-tail call，事情就变了。

看：

def main(x):
  def pow(n):
    if n == 0: 1 else: x * pow(n - 1)
  in
  pow(3)

这里 pow 捕获了 x，而且递归调用不是 tail position。随着每次 call 建立新栈帧，当前 rsp 不断变化，于是“捕获变量 x 相对当前栈指针的偏移”不再静态固定。

此时局部函数若仍依赖外层局部变量的“原地访问”，实现会非常麻烦。

两种经典方案

Static links 额外传一个指向外层栈帧的指针，调用时沿链往外找捕获变量。
Lambda lifting 直接把所有捕获变量变成显式参数，并把局部函数提升到顶层。

上例 lifting 后可变成：

def pow(x, n):
  if n == 0: 1 else: x * pow(x, n - 1)

def main(x):
  pow(x, 3)

好处非常明显：

局部函数不再依赖外围词法环境
每个函数只依赖自己的参数
代码生成更简单
与顶层函数的处理方式统一

哪些函数需要 lifting？

不是所有局部函数都必须 lift。一个很自然的判据是：

若函数只被 tail-called 且只在局部控制流里使用，可直接编译成 block
若函数会被真正 call，或要脱离定义点使用，则需要 lifting

要加哪些捕获变量？

最简单的正确方法是：

把定义点所有 in-scope 变量都加进去

但这会过度捕获。更精细的方法是做 liveness / free-variable 分析，只传真正需要的变量。工程上常见折中是：先全加，再在 SSA 层做 parameter dropping。

五、Functions / Procedures：tail call、non-tail call 与 calling convention 的分水岭

1. tail call 与 non-tail call 的本质区别

考虑：

return f(x)

这是 tail call，因为调用结果被立刻返回，调用者在调用之后没有任何剩余工作。

而：

1 + f(x)

不是 tail call，因为 f(x) 返回后还要继续做 + 1。

这两者的实现差异非常深：

tail call：不必保留“回来继续做什么”的信息
non-tail call：必须保存 return address、局部状态等

因此：

tail call 更像跳转（branch/jmp） non-tail call 才是真正的调用（call/ret）

2. 为什么 tail call 可以直接编译成 branch

若某函数调用处在 tail position，调用者栈帧后续没有用处。于是可以直接把当前控制流“转交”给被调函数，而不是：

压返回地址
建新栈帧
将来再返回

这就是 tail-call optimization 的本质。在中间表示层，它往往表现为：

局部函数定义编译成参数化 block
tail call 编译成 branch with arguments

这也解释了为什么 tail-recursive 函数可以像循环一样高效。

3. non-tail call 为什么一定会引入栈

一旦调用后还有工作未完成，就必须知道“返回后从哪条指令继续”。这个 continuation 不能只留在脑海里，必须变成运行时数据。

于是：

call 把返回地址压栈
callee 执行
ret 再把返回地址弹出来跳回去

这就是调用栈存在的根本原因。栈不是为了“存参数”而生的，首先是为了存 continuation。

4. second-class 与 first-class functions

second-class functions

函数可以被定义和调用，但不能当值用：

不能赋给普通变量
不能作为参数传递
不能作为返回值返回

这时编译器会轻松很多，因为每个 call site 都能静态解析到某个定义点。

于是可以：

静态做 arity check
把函数名解析成唯一标识
把局部 tail-called 函数直接当 block

first-class functions

函数本身也是值：

可以赋值
可以传参
可以返回

此时“函数调用”就不再只是“跳到某个已知 label”，而变成：

先求出一个函数值，再在运行时决定调谁

这会直接把实现推进到 function pointers、closures、dynamic arity metadata 等层面。

5. Calling convention：函数间必须签同一份“接口协议”

calling convention 规定了 caller 和 callee 之间的责任分工。例如：

参数放哪
返回值放哪
哪些寄存器调用后必须保持不变
栈对齐如何保证
谁负责清理参数

没有 calling convention，单个函数内部代码再正确，也无法和外部代码互相调用。

6. System V AMD64 调用约定的关键点

在 64 位 Unix-like 系统里，常见约定是 SysV AMD64 ABI。关键事实包括：

返回值

通常放在 rax

非易失寄存器（non-volatile / callee-save）

rbx, rbp, r12-r15

callee 若要用这些寄存器，必须先保存，返回前恢复。

易失寄存器（volatile / caller-save）

其值可能在调用中被破坏。如果 caller 还想保留这些值，就必须自行保存。

对一个“所有局部变量都放栈上，寄存器只当 scratch”的简单编译器来说，优先使用 volatile scratch registers 会更自然，因为无需额外保存。

7. 栈对齐：最容易被忽视、最容易炸的细节

SysV AMD64 中，一个关键约束是：

执行 call 之前，rsp % 16 == 0
因为 call 会再压一个 8 字节返回地址
所以 callee 开始执行时，常见状态是 rsp % 16 == 8

若栈没对齐，某些库函数或 SSE 指令可能直接崩溃，而且 bug 常常表现得很“玄学”：本地没事，评测机炸掉。

8. caller cleanup：为什么有些 tail call 做不到

SysV AMD64 里，caller 负责清理自己压到栈上的参数。这意味着，如果被调函数参数更多、需要更多栈空间，caller 往往没法简单地“原地转身”变成它。

所以：

“理论上的 tail position” 不一定总能在某种 ABI 下无条件实现成机器级 tail call。

这也是“语言级 tail call”与“具体 ABI 约束”之间的一个现实摩擦点。

9. 函数与 block 在 SSA 里为什么要区分

在很多 SSA 设计中：

function：只能成为 call 的目标，遵守 ABI
block：只能成为 branch 的目标，参数通过本地约定传递

二者都“有 label 和参数”，但含义不同：

function 是外部可调用边界
block 是函数体内部控制流节点

这层区分非常有用，因为它恰好对应：

non-tail calls → functions
tail local control flow → blocks

六、Datatypes：动态类型、tagging、heap allocation 与 closures

语言一旦不再只有整数，运行时表示就从“算术编译”进入“值表示设计”。

1. 静态类型与动态类型：错误发生在什么时候

静态类型

类型约束在编译期检查。例如：

true + 5

可直接拒绝。

动态类型

值的真实类型由运行时标签区分。因此：

true + 5

在前端未必报错，但执行到 + 时必须检查两个操作数是否是整数，否则抛 runtime error。

动态类型实现的关键难点不是“支持多种值”，而是：

怎样表示这些值
怎样在正确时机检查它们
怎样让这些检查仍能编译成高效代码

2. tagging scheme：把类型信息塞进机器字里

一种经典方案是 tagged value。

设运行时所有值都是 64 位。利用低位 bit 作为 tag，把不同类别编码进同一机器字。

一个常见设计是：

整数

最低位为 0：

encoded_int = n << 1

于是机器里的整数其实是“真实值乘二”。

优点：

test x, 1 即可快速判断是不是整数
63 位带符号整数仍然够用

布尔值

最低两位用 01：

false 编成某个以 01 结尾的模式
true 也编成某个以 01 结尾的模式

boxed heap data

最低两位用 11，高位存 heap pointer：

数组
闭包
结构体
其他大型对象

都走 boxed 路线。

这样，一个 64 位值就同时携带了：

它是什么类型
如果是立即数，值本身
如果是 boxed 值，指向堆对象的位置

3. 为什么 heap object 的指针能拿来打 tag

因为堆分配通常按对齐粒度进行，例如 8 字节对齐。这意味着合法对象地址的最低几位本来就是 0。于是可以把低 2 位改成 11 作为 tag，而实际访问时再把 tag 去掉：

raw_ptr = tagged_ptr ^ 0b11

这就是“pointer tagging”的经典技巧。

4. 动态类型原语的实现：先验 tag，再做操作

例如整数加法 x + y：

检查 x 是不是整数
检查 y 是不是整数
取出编码后的整数值直接相加，或在需要时修正 tag 影响
做溢出/错误处理

汇编里常见：

mov rax, x
test rax, 1
jnz err_not_int

因为整数最低位应为 0。若最低位为 1，说明不是整数。

这正体现了前面说的 test 在动态类型实现中的重要性。

5. isInt / isBool / assertInt 的角色

动态类型语言中，很多检查最好不要“隐式散落”在 codegen 各处，而应在 IR 中显式出现，例如：

assertInt(x)
assertBool(x)
isInt(x)
isArray(x)

这样做的好处是：

语义更清楚
SSA 层就能看见这些检查
后续优化有机会消除冗余检查
x86 codegen 保持相对薄

这也是“把动态类型实现放在 SSA lowering，而不是全塞进最终 codegen”的一大优势。

6. Heap allocation：为什么数组不能继续住栈上

数组这类值有两个特征：

体积可能很大
长度运行时才知道

这意味着它不适合继续用“固定大小局部变量”的方式放在栈帧里。因此需要：

调 runtime allocator 在 heap 上分配对象
用一个 tagged pointer 指向该对象

典型数组布局会包含：

长度字段
后续元素槽位

例如：

[arr_len | elem0 | elem1 | ...]

访问 a[i] 时要做：

assertArray(a)
assertInt(i)
去 tag 得到原始地址
读长度
检查越界
计算槽位地址
load/store

因此，数组支持不是“加两个语法糖”而已，它要求：

运行时分配器
bounds checking
load/store 指令支持
boxed representation
打印/错误处理扩展

7. 闭包之前，先理解 function pointer 为什么不够

若函数是 first-class value，最简单想法是：

函数值就是代码地址

这就是 function pointer。

对不捕获环境的函数，这完全可行。但一旦函数体引用定义点的外部变量，就不够了。

例如：

def adder(x):
  lambda y: x + y

返回的这个函数值，在以后被调用时，必须仍然知道 x 是多少。但一个裸代码指针只知道“执行哪段代码”，不知道“自由变量绑定了哪些值”。

所以：

function pointer 只能表示“代码” closure 才能表示“代码 + 环境”

8. Closure：函数值的标准实现

闭包通常表示为一个 heap object，内部包含：

code pointer：指向实际函数代码
environment / captures：保存被捕获变量的值

构造闭包时，把捕获变量拷贝到堆对象里；调用闭包时：

解包出 code pointer
把 captures 指针作为隐藏参数传给代码
再传显式实参

于是函数代码本身会变成类似：

lambda_fun(captures, y):
  captures[0] + y

而原来的：

lambda y: x + y

会被 closure conversion 成：

一个顶层函数 lambda_fun
一个运行时构造出来的闭包对象 [code_ptr, captures]

9. Closure conversion：把“隐式捕获”翻译成“显式环境操作”

closure conversion 的本质是：

把词法作用域中的自由变量访问，改写成对显式环境对象的访问。

例如：

lambda y: x + y

可改写为：

lambda_fun(captures, y):
  captures[0] + y

而闭包值则是：

[lambda_fun, [x]]

调用时：

f(5)

改写成：

f.code(f.env, 5)

或等价数组风格：

f[0](f[1], 5)

这样，“在定义点捕获、在调用点使用”的需求就被堆对象连接起来了。

10. Lambda lifting 与 closures 的关系

二者都在解决“自由变量如何变显式”的问题，但适用场景不同。

Lambda lifting

把自由变量改成显式参数。适合：

局部函数仍受静态调用结构控制
second-class 或受限 first-class 场景
编译期可决定调用点并补全额外参数

Closures

把自由变量打包进运行时对象。适合：

真正 first-class 函数
调用者在运行时才知道拿到的是哪个函数值
调用者未必知道或能访问原始 captures

因此，一旦函数成为真正 first-class value，单靠 lambda lifting 已经不够；closure 基本不可避免。

11. recursive closures：闭包还能引用自己

若闭包体内部还要递归调用自身，那么环境里还需要某种方式拿到“自己”。这会引入更复杂的递归闭包表示，例如：

环境中包含自引用
先分配空壳再回填
或使用更专门的递归闭包布局

这已经进入真实语言实现的深水区：此时“函数值”不再只是代码块，而是完整运行时对象。

七、把六个主题连成一条线

现在回头看，这六部分其实是一条完整链路。

1. 前端：先把名字讲清楚

哪些变量合法
哪些 use 是 free / bound
shadowing 怎么处理
如何把名字解析成唯一标识

这是后续一切变换的前提。

2. 语义层：再把程序行为讲清楚

表达式怎么求值
顺序是什么
什么时候报 compile-time error
什么时候报 runtime error

解释器是这层语义的可执行版本。

3. 中间表示层：把语义变成显式控制流与数据流

continuation 把求值顺序写出来
join point 共享 continuation
parameterized blocks / phi 处理合流
SSA 版本化变量消解赋值
minimal SSA 删除冗余参数

这一步把“语言意义”变成“优化友好结构”。

4. 后端：再把 IR 放进真实机器约束里

rip 决定控制流
jmp / jcc / cmp / test 实现分支
call / ret / stack 实现 non-tail call
calling convention 规定跨函数接口
stack alignment、volatile/non-volatile 保证和外界兼容

5. 运行时表示层：当值开始复杂，就需要 tag、heap、closure

动态类型需要 tagged values
大对象需要 heap allocation
数组需要边界检查与 load/store
first-class functions 需要 closure

这一步把“语言里的值”落到“机器里的比特”。

八、一个总视角：编译器实现，本质上是在不断“显式化”

如果只用一句话概括这些主题，可以说：

编译器的核心工作，就是把源语言中隐含的信息，逐步变成显式结构。

具体来说：

名字绑定关系，显式化成 unique identifiers
求值顺序，显式化成 continuations 和 SSA 顺序代码
控制流合流，显式化成 join points / block parameters
变量更新，显式化成 SSA 新版本
函数调用约定，显式化成 ABI
动态类型，显式化成 tag bits
词法环境，显式化成 closure object

这也是为什么编译器越往后端走，代码越“啰嗦”—— 它不是变笨了，而是在把高级语言默认替程序员隐去的东西，一层层摊平给机器看。

结语

从作用域、名字解析到 SSA，再到调用约定、动态类型和闭包，表面上看是六个主题，实际上它们共同回答的是同一个问题：

一个带有词法作用域、控制流、函数和值语义的高级程序，怎样被系统地翻译成一台只认识寄存器、内存、跳转和位模式的机器所能执行的形式？

真正掌握这一套内容之后，很多“局部技巧”会自然统一起来：

shadowing 为什么像 SSA versioning
tail call 为什么像 branch
join point 为什么像 continuation 的实体化
lambda lifting 为什么是把自由变量参数化
closure conversion 为什么是把自由变量对象化
tagging 为什么是把类型信息比特化

当这些联系建立起来，编译器就不再是一堆零散 pass 的集合，而是一套非常紧密的语义重编码过程。