Triton

用 Python 写 GPU 代码，底层自动编译为高度优化的 CUDA/PTX。核心思想是基于 Block（块） 编程，而不是基于单个线程。定位是深度学习算子开发：比手写 CUDA 省力，比 PyTorch 自定义算子更灵活、性能更接近峰值。

两条生命线： …

Computation Graph 优化

ML 程序的两种视角

• Computation Graph：算子级别，宏观，把整个模型看成一个个 operator 连起来
  • 主要优化方式：图变换，算子融合，并行策略等
  • 主要工具层：TorchInductor，XLA，TensorRT，TVM graph pass 等
• Loop-Intensive Code：循环级别，微观，把最终的所有算子看成大量 nested loops
  • 主要优化方式：向量化、分块、软件流水等
  • 主要工具层：CUDA，Triton，CUTLASS，LLVM backend 等

ML 应用的分类

• Deep Learning 任务特定模型：
  • 计算机视觉（ResNet、ViT）
  • 语音识别、NLP 分类
• Large Language Models（LLMs）：
  • GPT 系列、Gemini 系列 …

最近我做了一个小项目，测量我的笔记本 RTX 4060 GPU 上 4-bit 量化推理的真实性能。这个项目是我的第一个 AI Infra 项目，在此之前我没有任何 AI Infra 或 MLSys 的基础。我为此补充了一些基础知识，会整理成笔记之后发出来。

大模型在生成文本时，decode 阶段每生成一个 token，模型的大量权重都要从显存读一遍，而这些权重大多只参与当前 token 的一次计算。计算量不大，访存压力大，典型的 memory-bound。

所以我一开始的假设很简单：LLM 权重从 FP16 变成 4-bit（FP4 / NF4 / INT4）之后，显存占用下降，decode 又是 memory-bound，推理速度应该变快才对。至少不该明显变慢。

实际测下来：Qwen2.5-1.5B-Instruct + RTX 4060 Laptop 8GB …

MLSys 定义和特点

定义：任何能运行 ML 程序的 system，可以是运行 training/fine-tuning/inference 任意一个

• Shared Memory System：通常指单台机器，如配有多 GPU 的服务器
• Distributed Memory Systems：多台机器通过网络连接，读取对方内存需要数据传输，如 GPU 集群/数据中心
• 内存拓扑决定通信成本，通信成本决定训练和推理能不能高效扩展

特点：

• 大量 Compute
• 大量 Memory
• 大量 Communication

Training：输入数据 → 前向传播 → 计算损失 → 反向传播 → 更新权重

• 计算量最大
• 数据量最大
• 时间最长
• 成本最高
• 通常需要大量 GPU/TPU

Fine-tuning：预训练模型 → 特定任务数据 → 少量再训练 → 专用模型

• 成本低于完整训练
• 数据量更少
• 时间更短
• 通常针对一个具体任务做一次 …

算法课真正要训练什么

算法课表面上有很多具体算法：Dijkstra、Bellman-Ford、Kruskal、Ford-Fulkerson、Simplex、Knapsack DP。

但最重要的不是把它们的代码背下来。

更核心的问题是：

• 一个自然语言问题怎样变成 formal problem
• 约束应该编码成状态、边、容量，还是不等式
• 为什么这个算法适用
• 为什么它不会错
• 它的成本由什么决定

很多看似和编程完全无关的问题，比如排课、分配、运输、活动选择、网络容量、路径限制，最后都可以转成一个算法问题。

这个转化过程才是 Design and Analysis of Algorithms 的中心。

问题建模：先把对象拆开

看到一个问题，先不要急着套算法。先把它拆成四件事： …

复数的几何意义

复数有两个基本视角。代数上，$z=x+iy$；几何上，$z\leftrightarrow(x,y)$。在复平面上，实部是横坐标，虚部是纵坐标。

模长 $|z|=\sqrt{x^2+y^2}$ 表示点到原点的距离。辐角 $\arg z=\theta$ 表示从正实轴转到 $z$ 的方向。

因此复数可以写成极坐标形式 $z=r(\cos\theta+i\sin\theta)$。借助 Euler formula $e^{i\theta}=\cos\theta+i\sin\theta$，得到更紧凑的指数形式：

这个形式是复分析的入口。很多计算如果留在 $a+bi$ 里，会变成代数展开；写成 $re^{i\theta}$ 后，几何结构直接显出来。

乘法即旋转

如果 $z_1=r_1e^{i\theta_1}$，$z_2=r_2e^{i\theta_2}$，那么 $z_1z_2=r_1r_2e^{i(\theta_1+\theta_2)}$。也就是说，复数相乘时模长相乘，辐角相加。

这就是你笔记里的核心直觉：乘法即旋转。

不要总去想 …

DP 不是公式库

DP 最容易被学成公式库。背包一套公式，LIS 一套公式，LCS 一套公式。

这样短期有用，但遇到变体很容易崩。

更好的理解是：把所有 DP 问题看作 DAG 上的最短路、最长路或最优路径问题。

状态是节点，决策是边，递推是在沿着边传播最优值。

所以 DP 设计的核心问题是：

• 状态里必须记住哪些信息
• 哪些状态依赖哪些更小状态
• 依赖关系有没有环
• 每个状态从哪些候选转移取 min / max

DP 四步

看到一个 DP 问题，按顺序落实四步。

第一步：定义子问题

这是最关键的一步。常见定义方式：

• $T[k]$：以第 $k$ 个元素结尾的最优值
• $T[k,l]$：只看前 $k$ 个物品、容量为 $l$ 的最优值
• $T[i,j]$：子串 $S[i..j]$ 上的最优值
• $T[u]$：DAG 上从 $u$ 到终点的最优值

状态定义必须能唯一确定一个子问题。信息少了，递推不成立；信息多了，状态空间爆炸。

第二步：明确最后一步决策

DP 的递推通常来自最后一步：

• 最后一个元素取还是不取
• 最后一条边从哪里来
• 最后一个活动选不选
• 区间最后一次合并在哪里切
• 最后一个字符来自字符串 A 还是 B

如果说不清最后一步，就很难写出可靠递推。

第三步： …

语言和机器

Theory of Computation 关心计算本身的边界，不限定在某一门编程语言怎么写。

一个 language 是字符串的集合。比如：

这个语言包含所有 1 的个数为偶数的二进制字符串。机器的任务是读入一个字符串，然后判断它是否属于这个语言。

所以每一种计算模型都可以对应一类语言：

复导数为什么更强

实函数的导数只需要从一条线的左右逼近。

复函数的导数定义看起来类似：

但 $\Delta z$ 是复数。它可以从平面上的任意方向趋近 0。

所以这个极限必须对所有逼近路径都一致。

这就是复可导比实可导强很多的原因。

一个函数如果只在某个方向上表现好，不够。它要在二维平面所有方向上都给出同一个线性近似。

Analyticity

函数在某点解析，意思是它在该点的某个邻域内可导。

注意这里不是只在一个点可导。

解析性是局部性质，需要一整个小圆盘。

如果函数在整个复平面解析，叫 entire function。

常见 entire functions：

• polynomial
• $e^z$
• $\sin z$
• $\cos z$

解析函数在复分析里是“完美”的函数。它不只是有一阶导数，后面会 …

Greedy 的问题意识

Greedy 算法的形式很简单：每一步都做当前局部最好的选择。

难点不在算法怎么写，而在这个局部选择是否值得相信。

很多问题看起来都可以 greedy：

• 每次选最短的活动
• 每次选价值最大的物品
• 每次选当前最短的边
• 每次选最近的节点

但只有一部分是对的。

Greedy 成功的核心条件是：当前这个选择不会破坏某个全局最优解。换句话说，总存在一个最优解包含 greedy 的第一步选择。

这就是 greedy-choice property。

Exchange argument

Greedy 最常用的证明是 exchange argument。

标准思路：

1. 设 $G$ 是 greedy 解，$O$ 是某个最优解
2. 找到 $G$ 和 $O$ 第一个不同选择
3. 把 $O$ 中对应部分换成 greedy 的选择
4. 证明换完后仍然可行，且目标值不变差
5. 重复交换，最后得到一个和 greedy 解一致的最优解

这类证明的 …

从有限状态到 stack

Regular language 的机器只有有限状态。它可以记住“现在处于哪一种情况”，但不能记住任意长的历史。

比如：

这个语言要求 a 的数量和 b 的数量相同。DFA 只能有有限个状态，没办法记住任意大的 $n$。

如果机器多一个 stack，情况就变了。读到 a 时压栈，读到 b 时弹栈，最后栈刚好清空，就说明数量匹配。

这就是 context-free language 的核心能力：它可以处理一类结构化的、嵌套式的记忆。

CFG：生成语言的规则系统

CFG（Context-Free Grammar）是从生成角度定义语言。一个 CFG 写作：

• $V$：临时变量 …

Contour integral

复积分沿路径进行。

如果路径 $C$ 可以参数化为：

那么：

这叫暴力参数化积分。

它是最底层的方法：把复积分转成实变量积分。

但复分析真正有意思的地方是，很多时候你不需要真的积分。解析性会让路径积分大幅简化。

Antiderivative and path independence

如果 $f$ 在区域内有 antiderivative $F$，也就是：

那么：

积分只看起点和终点。

于是任何闭合路径都有：

这和实变量积分里的基本定理很像。

但复分析里更强的是：在合适区域中，解析性本身就会导致闭合积分为 0。 …

图算法的重点是建模

很多图算法题表面上不说图。

它可能说的是：

• 使用一次折扣券，找最便宜路线
• 选择一组课程，使先修关系满足
• 给学生分配项目
• 判断城市之间是否能互相到达
• 从起点到终点，路径边数必须是 3 的倍数
• 搬运供需，最小化运输成本

这些题的核心都不是“写 BFS”或“写 Dijkstra”。

核心是把原问题里的对象、状态、约束、目标，编码成图。

最重要的一句话：

节点 = 状态，边 = 状态转移，权重 = 代价。

建图五问

不管什么题，先问这五个问题：

1. 我最终需要知道什么？
        ↓
2. 这个“什么”依赖哪些中间状态？
        ↓
3. 每个状态如何从已知量转移过来？
        ↓
4. 图的节点/边应该编码什么信息？
        ↓
5. 起点终点是什么？跑什么算法？

如果题目只是标准最短路，节点就是原图节点，边就是道路，权重就是距离。

如果题目多了限制，节点通常就不能只表示位置。它还要表示“当前已经用了几次操作”“上一条边是什么颜色”“当前步数 mod k 是多少”。

这就是状态扩张。

先看图的基本结构

建模后，先按结构 …

图灵机解决了什么问题

DFA 只有有限状态。PDA 多了一个 stack。它们都能解释一部分语言，但仍然很受限。

Turing machine 的目标是把“算法”这个直觉概念形式化。

一台 TM 有：

• 有限状态控制器
• 一条可以无限延伸的 tape
• 一个读写头
• 每一步根据当前状态和当前格子内容，决定写什么、往哪走、进入哪个状态

它看起来很原始，但能力足够表达我们通常意义上的算法。

TM 的形式定义

标准 TM 可以写成七元组：

• $Q$：状态集合
• $\Sigma$：输入字母表，不含空白符 …

Power series 的几何

复分析里，power series 不是单纯的形式展开。

如果函数在 $z_0$ 附近解析，它可以写成：

这个级数的收敛域在复平面上是一个圆盘 $|z-z_0|

这里最重要的直觉是：

收敛半径 $R$ 等于从展开中心 $z_0$ 到最近奇点的距离。

也就是说，power series 可以一直扩展，直到撞上第一个奇点。

这比实分析更几何。实轴上的收敛区间，其实是复平面里收敛圆盘和实轴的交集。

Taylor series

如果 $f$ 在圆盘 $|z-z_0| $$ f(z)=\sum_{n=0}^{\infty} \frac{f^{(n)}(z_0)}{n!}(z-z_0)^n $$

Taylor series 描述的是函数在一个正常点附近的局部结构。

常见基础展开是 $e^z=\sum_{n=0}^{\infty}\frac{z^n}{n!}$、$\sin …

从算法到约束模型

有些问题不像路径问题，也不像 DP。

它们通常长这样：

• 给每个人分配一个任务
• 每条道路有运输容量
• 每个仓库有供给，每个城市有需求
• 要在预算、比例、质量约束下最大化收益
• 要证明某个方案已经最优

这类问题的核心是约束。

Flow、matching、LP 都是在回答同一个问题：如何把约束写成一个可求解的优化模型。

Matching：一对一配对

Matching 适合处理“每个对象最多用一次”的配对问题。

最典型的是 bipartite matching。

左边一类对象，右边一类对象。边表示兼容。

例子：

• 学生可以做哪些项目
• 工人可以执行哪些任务
• 行和列之间是否可以放一个棋子
• 人和时间段是否兼容

目标通常是最大化匹配数量，或者找到完美匹配。

建模步骤：

1. 确定二部图两侧
2. 确定什么时候连边
3. 每个点最多匹配一次
4. 求 maximum matching 或 perfect matching

Bipartite matching = Max flow

Bipartite matching 可以转成 max flow。

构造：

• 加超级源点 $s$
• $s$ 连到左侧所有点， …

不可判定性从哪里来

在 DFA 和 CFG 那里，很多问题都可以被判定。到了 TM，情况变了。

原因在于 TM 已经强到可以描述程序本身，不是因为它太弱。程序可以读程序、模拟程序、构造程序，也就会出现自指和对角化。

最粗的 counting argument 是：

• 所有字符串 $\Sigma^*$ 是可数的
• 所有 TM 都可以编码成字符串 $\langle M\rangle$，所以 TM 的集合可数
• 所有语言是 $\Sigma^*$ 的所有子集，也就是 power set，所以不可数

因此语言比 TM 多。必然存在没有任何 TM 能识别的语言。

但 counting argument 只告诉我们“存在”。真正有用的是给出具体问题，比如 $A_{TM}$，并证明它不可判定。

A_TM

定义：

Residue 是什么

如果 $z_0$ 是孤立奇点，函数在 $z_0$ 附近有 Laurent expansion：

Residue 是其中：

也就是：

这一项的系数。

记作：

为什么偏偏是 $z^{-1}$ 项重要？

因为：

对所有 $n\neq -1$ 都成立，而：

所以整个 Laurent series 里，闭合积分只会“看见”$-1$ 次幂项。

留数 = 过路费

可以用你笔记里的说法：

留数 = 过路费。

每当路径绕着一个奇点转一圈，这个奇点就贡献一次：

如果路径围住多个 …

算法设计不总能找到高效精确解

前面几篇都在讲怎么设计算法。

但算法课还有一条很重要的线：有些问题可能没有多项式时间精确算法。

这不是说完全不能算。可以暴力搜索，可以用指数算法，可以在小规模上跑，可以近似，可以随机化，可以限制输入结构。

复杂性理论给的是边界意识：什么时候我们应该停止寻找普通的 polynomial-time exact algorithm，转而换目标。

P 和 NP

$\mathbf{P}$ 是多项式时间可解的问题。

也就是存在一个算法，可以在输入规模 $n$ 的多项式时间内给出答案。

$\mathbf{NP}$ 是多项式时间可验证的问题。

给你一个 certificate，你能在多项式时间内检查它是否证明答案为 yes。

例子：

从可判定到高效可判定

前面讨论 decidability 时，只问一个问题：有没有算法能在有限时间内给出答案。

复杂性理论继续问：如果能算，要花多少资源。

这里的资源主要是：

• Time：运行多少步
• Space：使用多少 tape cell / memory

很多 decidable 问题虽然理论上能算，但可能需要指数时间，实际完全不可用。所以复杂性理论的第一条分界线是 polynomial time。

多项式时间通常被当成“可高效求解”的数学近似。它不等于工程上一定快，但比指数时间稳定得多。

Time complexity

定义：

为什么实积分能用复分析算

Residue theorem 计算的是闭合路径上的复积分。

实积分看起来只在实轴上。

关键技巧是：把实轴上的积分嵌入一个闭合 contour 中。

如果闭合 contour 由几段组成：

实轴部分 + 大圆弧部分 + 小凹槽部分 + branch cut 两侧

那么 residue theorem 给出整体积分。

只要能证明其他部分消失或可以表达，实轴积分就被解出来。

所以实积分题的核心在于 contour 怎么选；留数计算是 contour 确定后的局部步骤。

先看积分范围

积分范围通常直接提示 contour。

这组 notes 整理自 Programming Language Pragmatics 课程复习内容，覆盖类型系统、复合类型、子程序、面向对象、函数式语言、并发、编译与运行时系统等主题。

重点是把编程语言里的概念放回几个核心问题中：

• 一个值如何被分类、检查和解释？
• 复杂数据结构如何映射到内存？
• 函数调用在运行时到底发生了什么？
• 对象、继承和动态分派如何实现？
• 函数式语言如何组织计算？
• 并发程序如何管理多个控制流和共享状态？
• 编译器、虚拟机和运行时系统如何支撑高级语言抽象？

编程语言的概念初看往往很抽象，但大多数都和具体的实现选择紧密相关。类型系统影响安全性和代码复用。record 布局影响内存对齐和比较。函数调用影响栈帧和寄存器。虚方法影响对象布局和分派开销。coroutine 影响调度和控制流。垃圾回收同时影响内存安全和停顿时间。

这组 notes 的目标是把这些概念串起来，看清语言设计背后的 tradeoffs。

01 类型系统

Types 这一篇讨论语言如何理解一个值"是什么"。

核心问题包括：

• 类型在语言中起什么作用？
• strongly typed 和 statically typed 有什么区别？
• type equivalence 和 type compatibility 如何区分？
• structural equivalence 和 name equivalence 分别适合什么场景？
• polymorphism、generics、overloading、duck typing 之间有什么关系？
• type inference，尤其 Hindley-Milner，如何从约束中推导类型？
• equality testing 为什么比表面上更复杂？

这一篇的重点是：类型不只是变量标签。它同时影响合法操作、错误检查、内存表示、代码复用和抽象边界。 …

这一篇的核心问题是：一段源代码如何变成可以运行的程序，以及程序运行时，语言系统还需要继续做哪些管理工作。

前面几章讨论的是语言特性：类型、对象、函数、并发、内存。这里关注的是这些特性如何落地：

source code
-> front end
-> intermediate form
-> optimization
-> code generation
-> executable / bytecode
-> run-time system / virtual machine
-> execution

可以把这一篇分成两半：

• Building a runnable program：编译器如何分析、优化和生成代码。
• Run-time program management：运行时系统、虚拟机和 JIT 如何支持程序运行。

它们共同回答一个问题：高级语言的抽象，最终如何被机器执行。

Basic block

Basic block 是一段连续的指令序列。

它有两个关键性质：

• 只能从第一条指令进入。
• 只能从最后一条指令离开。

也就是说，basic block 中间不会有别的入口，也不会在中间突然跳走。

例如：

x = a + b
y = x * 2
z = y - 1

如果这三条指令之间没有 branch、jump、return、exception edge，它们可以构成一个 basic block。

Basic block 是编译器做局部优化的基本单位。因为 block 内部控制流是直线的，编译器可以比较容易地分析：

• 哪些表达式重复了
• 哪些变量不再使用
• 哪些计算可以提前
• 哪些临时变量可以消掉

Control flow graph

Control flow graph，简称 CFG，用图表示程序的所有可能执行路径。

在 CFG 里： …

Concurrency 这一章的核心问题是：当程序里有多个控制流同时推进时，语言和运行时如何组织它们、调度它们，并防止它们互相破坏共享状态。

单线程程序的执行顺序通常比较直接。一步一步往下走，状态变化也比较容易追踪。并发程序的难点在于：多个任务的执行顺序可能交错，而且这个交错顺序不完全由程序员控制。

所以并发编程关心的不只是"怎样让程序更快"，还包括：

• 多个任务如何同时推进
• 哪些任务真的同时运行
• 共享数据如何保护
• 等待条件如何表达
• OS 和 runtime 如何调度控制流
• 如何避免 race condition、deadlock、starvation
• 如何在性能和安全之间取舍

Concurrent、Parallel 和 Distributed

这三个词很容易混在一起，但它们关注的层次不同。

Concurrent 指多个任务在同一段时间内都在推进。它们不一定真的同时运行，可以是在一个 CPU 上交替执行。

例如，一个 Web server 同时处理多个请求。哪怕只有一个核心，只要它在请求 A 等 I/O 时去处理请求 B，也可以称为 concurrent。

Parallel 指多个任务真的在同一时刻运行。它通常需要多核 CPU、多处理器或 GPU。

例如，把一个大矩阵计算切成多个部分，在多个核心上同时执行，这就是 parallel。

Distributed 指任务运行在通过网络连接的多台机器上。

例如，一个系统由多台服务器组成，每台机器负责不同服务或不同数据分片。Distributed system 还要处理网络延迟、机器故障、消息丢失、一致性等问题。

可以粗略记：

concurrent  = 多个任务交错推进
parallel    = 多个任务同时执行
distributed = 多个任务分布在多台机器上

Concurrency 是结构问题 …

Functional languages 这一章的核心问题是：如果把"函数"当成语言的中心，而不是把"状态修改"当成程序的中心，编程语言会变成什么样。

在 imperative programming 里，程序通常被理解成一系列命令：

改变变量
更新状态
执行循环
修改对象

Functional programming 更关注表达式、函数组合、值的变换和引用透明性。它关心的是：

• 函数能否像普通值一样被传递
• 数据是否可以保持不可变
• 表达式是否可以被它的值替换
• 求值顺序是否影响结果
• 函数调用能否被缓存
• 代码本身能否作为数据处理

这一章不只是介绍 Lisp、Scheme、ML、Haskell 这些语言，也是在讨论一种不同的程序组织方式。

Lambda calculus

Functional programming 的基础数学形式体系是 lambda calculus。

Lambda calculus 用非常小的一组规则表达计算：

• 变量
• 函数抽象
• 函数应用

例如：

λx. x + 1

表示一个接收 x 并返回 x + 1 的函数。

函数应用则是：

(λx. x + 1) 3

结果是：

4

Lambda calculus 的重要性在于：它说明"函数定义"和"函数调用"本身就足以表达计算。很多 functional language 的核心语义都可以追溯到这个模型。

Functional programming 的显著特征

Functional programming languages 通常有一些共同特征，但不是每一种语言都全部具备。

常见特征包括：

• 函数是 first-class values。
• 倾向使用 pure functions。
• 倾向使用 immutable data。
• 强调 …

Object orientation 这一章的核心问题是：语言如何把数据和操作绑定在一起，以及如何让同一段代码在运行时根据对象的真实类型执行不同逻辑。

OOP 表面上是 class、object、inheritance、method 这些语法。更底层一点看，它关心的是几件事：

• 如何封装状态
• 如何隐藏实现细节
• 如何复用已有代码
• 如何通过父类型引用子类型对象
• 如何在运行时决定调用哪个方法
• 如何初始化和销毁对象
• 如何实现 interface、abstract class、dynamic dispatch 和 vtable

所以这一章不是单纯的"面向对象编程思想"，而是对象模型如何被语言和运行时实现。

OOP 的三个定义特征

通常认为 object-oriented programming 有三个核心特征：

• Encapsulation
• Inheritance
• Polymorphism

Encapsulation

Encapsulation 指把数据和操作这些数据的代码绑定在一起，形成 object。

对象内部可以有自己的状态，比如字段、属性、成员变量。对象对外暴露一组方法，外部通过这些方法操作对象，而不是直接随意改内部状态。

它的作用包括：

• 隐藏实现细节。
• 降低模块之间的耦合。
• 防止外部代码破坏对象内部不变式。
• 让对象可以在不改变外部接口的情况下修改内部实现。

例如一个 Stack 对象对外暴露 push 和 pop，但内部到底用 array 还是 linked list，可以被隐藏起来。

Inheritance

Inheritance 指一个 class 可以继承另一个 class 的属性和方法，并在此基础上扩展或修改行为。

例如：

class Student extends Person {
    ...
}

Student 可以复用 …

Subroutines 这一章的核心问题是：语言如何把一段代码封装成可调用的单元，以及一次函数调用在运行时到底发生了什么。

表面上，函数调用只是：

f(x)

但实现层面要处理很多事情：

• 参数如何传进去
• 返回值如何传回来
• 局部变量放在哪里
• 调用结束后如何回到原位置
• 嵌套函数如何访问外层变量
• 异常发生时如何清理栈帧
• coroutine 和 thread 如何保存与恢复控制流

所以这一章连接的是"语言里的函数抽象"和"机器上的控制流与栈帧"。

Calling sequence

Calling sequence 是一次子程序调用时，caller 和 callee 需要共同完成的一组步骤。

它的作用是让函数调用变成一个可恢复、可嵌套、可返回的过程。程序进入子程序之前，要保存足够的信息；子程序执行完之后，要恢复到调用前的状态，并把返回值交回去。

可以把 calling sequence 分成两个方向：

on entry: 进入子程序
on return: 离开子程序

On entry

进入子程序时，通常要做这些事：

1. 传递参数。
2. 保存 return address，也就是函数结束后应该回到哪里。
3. 调整 stack pointer，为新栈帧分配空间。
4. 保存必要的寄存器，比如 frame pointer、callee-saved registers。
5. 初始化局部变量或局部对象。
6. 把 program counter 跳转到子程序入口。

其中有些工作由 caller 做，有些由 callee 的 prologue 做。

On return

离开子程序时，通常要做这些事：

1. 放置 return value。
2. 清理局部变量或局部对象。
3. 恢复 stack pointer。
4. 恢复保存过的寄存器。
5. 恢复 frame pointer。
6. 根据 return …

Composite types 这一章的核心问题是：语言如何把多个值组织成更复杂的数据结构，以及这些结构在内存里到底如何表示。

如果 Types 这一章关注"一个值是什么"，Composite Types 这一章关注的就是"多个值如何被放在一起"。这不只是语法设计问题，也会直接影响内存布局、访问效率、安全性、赋值语义、比较语义和垃圾回收。

可以把本章理解成一组语言层和机器层之间的连接：

• record / struct：多个字段如何排列
• union / variant record：同一块内存如何表示不同形态的数据
• array / slice：连续数据如何被寻址和切分
• pointer / reference：对象之间如何互相连接
• garbage collection：程序如何处理不再可达的 heap object

Records 和 holes

Record，也就是很多语言里的 struct，是把多个字段组合成一个整体。

例如 C 里的结构体：

struct MyRecord {
    char a;
    int b;
};

直觉上，char 占 1 字节，int 占 4 字节，所以整个 struct 应该占 5 字节。但实际情况通常不是这样。编译器可能会在 char a 和 int b 之间插入几个空字节，让 int b 的地址满足对齐要求。

这些不存实际数据、只用来占位的字节，就叫 holes 或 padding。

holes 是怎么产生的

holes 主要来自 data alignment。

现代 CPU 访问内存时，通常更喜欢按照某些边界读取数据。比如一个 4 字节的 int 如果放在 4 字节对齐的地址上，读取会更快，也更符合硬件要求。如果字段紧密排列导致某个字段跨越不合适的边界，CPU 可能需要更多次读取，甚至在某 …

类型系统这章的核心问题是：语言如何理解一段数据"是什么"，它能做什么操作，错误应该在什么时候被发现，以及代码如何在不同数据之间安全复用。

可以把 types 理解成编程语言里的约束系统。它一方面帮助程序员表达意图，另一方面帮助编译器或运行时发现不合理的操作。一个值如果被看成 int，它就可以参与整数运算；如果被看成 string，它就可以进行字符串拼接、索引、匹配等操作。同一段二进制数据，在不同类型解释下会有完全不同的意义。

类型的作用

类型在编程语言里主要有几类作用：

• 告诉编译器或运行时，一段数据应该如何被解释，比如 int、float、string、bool。
• 做安全检查，防止无效操作，比如让字符串除以数字，或者把一个不支持某方法的对象传给函数。
• 帮助决定内存分配和数据布局，比如一个 int 占多少字节，一个 record 如何对齐。
• 提供抽象，让程序员不必关心底层二进制细节，只需要关心值支持哪些操作。

所以类型不是单纯的标签。它同时影响语义、安全性、内存表示和程序结构。

Strongly typed 和 Statically typed

Strongly typed 指语言会严格执行类型规则，限制不兼容类型之间的操作。比如如果一个函数需要 Integer，你不能随便传一个 Boolean 或 String 进去，除非语言明确允许某种转换。

Statically typed 指类型检查发生在编译期。程序运行之前，编译器就已经知道大多数表达式、变量和函数返回值的类型。

这两个概念不一样：

• Java：通常是 strongly typed + statically typed。
• Python：通常是 strongly typed + dynamically typed。
• C：statically typed，但不是非常 strong，因为它允许很多绕 …