今天我学到了

2024 年 9 月 29 日

Cyclone: 基于区域的内存管理

现如今，Rust 已经变成了一门备受欢迎的编程语言，在它诸多设计中，允许对生命周期的标注与推导可以说是颇具特色、让人又爱又恨的特性。 追溯到学术研究上，那就不能不提 2002 年发表的 Region-Based Memory Management in Cyclone。 这篇出版物描述了作者们在 Cyclone（一个基于 C 语言的 Safe-C 方言）中引入和实现的基于区域的内存管理系统，在之后 Rust 的开发发展有着深远的意义。

在文章中，作者基于之前关于区域内存管理的工作，额外做出了以下贡献：

• 使用后进先出原则，在不同区域间形成一个 outlives 关系，这也是一个子类型关系，从而便利了很多情况下对区域中指针的使用。
• 通过 regions_of 运算符减少了效果变量的使用。
• 为函数推导出默认的效果标注，减轻显式标注的负担。
• 和存在类型相集成。

Cyclone 将内存分为众多的区域，其中一个是特殊的堆区域，具有无限长的生命周期。在 Cyclone 中可以使用 malloc 进行分配（尽管并不能释放。作者推荐了 Boehm GC 用于这个区域的自动垃圾回收）。 然后是栈区域，对应着 C 中的局部块。函数参数和局部变量都位于这一区域内。 最后是动态区域，具有词法作用域范围的生命周期，并允许在其中进行无限制的内存分配。动态区域需要使用 region r {s} 式的语法显式创建。 为了从该区域分配一块内存，需要使用 rnew(r) 3。

Rust 中有类似但不完全对应的构造。 （据我目测估计）Cyclone 的堆和 Rust 的一般堆上对象还是挺不一样的， Cyclone 的堆对象相当于具有 'static 的生命周期，而 Rust 的 Box 所指向的内存块的生命周期则是和 Box 对象本身的生命周期相关联。 如果 Box 对象的生命周期结束，那么它指向的内存块的生命周期也将很快结束。为了实现 Cyclone 类似的生命周期，要使用 Box::leak 显式泄漏该内存块。 栈区域，完全一致，没啥好说的。最后是动态区域，这里 Rust 其实并没有像 Cyclone 一样，将内存分配功能实现为区域的一项基本功能。 当然，配合 Rust 强大的生态系统，你可以使用任意一个 arena 库，创建一个 arena，并在对应的区域中获得具有相应生命周期的内存块，并在区域结束后自动释放。

Cyclone 的区域类型系统有着如下的设定：

• 区域标注：Cyclone 里的所有指针都关联着一个区域。如 int*\(\rho\) 就表示一个指向 \(\rho\) 区域中的一个 int 的指针。 标记为 L 的块 (L: {int x = 0; s}) 具有名称 \(\rho_L\)，对应着该块创建的块区域。 而语句 region r {s} 则定义了名为 \(\rho_r\) 的区域。区域名字的作用范围对应着区域的生命周期。 在动态区域里用 rnew 创建的指针和在堆区域里取引用获得的指针都将被关联对应的区域。
• 阻止悬垂引用：当指针被解引用时，类型系统可以确保这个指针关联的区域在此刻是存活的，否则就会产生类型错误。
• 区域多态：允许在函数签名上使用抽象区域参数。
• 多态递归：可以用不同的区域名去实例化递归函数中的区域参数（本人注：从类型系统的角度来说，这点似乎不值一提？）
• 类型定义中的区域参数：允许定义类型时其中包含的指针由区域名参数化。例子：struct Lst<r1, r2> { int*r1 hd; struct Lst<r1, r2>*r2 tl; }

为了让以上设计变得实用，必须引入区域间的子类型关系。因此，Cyclone 规定，如果区域 \(\rho_1\) outlives \(\rho_2\)，则允许在任何能使用 int*r2 的地方使用 int*r1。 Cyclone 会自动进行这种 coercion。

Cyclone 额外地追踪函数产生的效果。这一做法的动机是需要避免一个具有较短或者说局部生命周期的指针，通过隐藏在存在类型、闭包（虽然 Cyclone 没有直接支持闭包，但可以用存在类型模拟）中，逃逸至更外层的区域中并被使用。 因此，在每个控制流点，Cyclone 都追踪所有存活区域名称的子集。这个集合被称作 capability。为了允许解引用指针，必须确保指针关联的类型位于 capability 中。类似地，为了允许函数调用，Cyclone 确保函数可能访问的区域都必须是存活的。 为此，Cyclone 要求在函数上标注效果，记录函数可能会使用的区域集。

和之前工作不同，Cyclone 会从函数原型（而无论函数体是什么）为函数推导出一个默认的效果。 工作原理是收集所有原型中提到的区域名或者隐式产生的区域参数。当然用户也可以通过手动标注覆盖这个默认推导的结果。

另外一个不同是，Cyclone 并不使用效果变量。对于需要类型变量的地方，使用一个内置的 regions_of 类型运算符代替。（本人注：是好设计吗？Rust 是如何规避的？）

例子：

struct Set<a, r, e> {
  list_t<a, r> elts;
  int (*cmp)(a, a; e);
}
    

这里的 e 就是一个效果变量，然而 Cyclone 并不支持。用 regions_of 运算符，可以改写为：

 struct Set<a, r> {
  list_t<a, r> elts;
  int (*cmp)(a, a; regions_of(e));
}
    

2024 年 9 月 25 日

Cranelift 中的指令选择 DSL (ISLE)

Cranelift 编译器项目中有一个名为“指令选择降低表达式”的 DSL, 也就是 ISLE, 用于解决指令选择过程中最为常见的、对中间语言进行模式匹配并将其重写为更低层级语言（例如，特定架构的机器语言）的问题。

作者表示这一 DSL 的设计融合了很多来自术语重写系统和 Prolog 的想法。尽管如此，这一语言和现有的术语重写系统 (Term Rewriting System) 并不完全相同，因为它具有一个“强大”的类型系统， 允许不同项具有不同类型（例如可以为和类型）。

在这里，我不想过多谈论它的设计哲学，而是转向这一语言本身的定义与规范。

在 ISLE 中，我们用 S-表达式表示一个术语：

(a (b c 1 2) (d) (e 3 4))
    

每个术语要么为一个原语；要么为一个构造；要么为一个提取。构造由构造器和参数组成。参数也是术语。构造器可以接受元数个参数。类似地，提取由提取器和参数组成，其中参数为模式。

TRS 的核心为一套规则集，我们可以使用规则集中某个最“合适”的规则来转换术语到另一个术语，直到满足某些条件。类似地，在 ISLE 中也同样定义了规则与规则集的概念。

一条规则会被分为两个部分，其中左侧被称作模式，右侧被称作表达式。术语被看待为构造还是提取，取决于它出现在规则的哪一侧。

例如，可以在 ISLE 中编写一条规则如下所示：

(rule
;; left-hand side (pattern): if the input matches this ...
(A (B _ x) (C y))
;; ... then rewrite to this:
(D x y))
    

其中，左侧模式可以由以下内容归纳定义得出

• 通配符_
• 整数常量
• 导入的外部符号常量 $...
• 变量捕获（标识符），其中第一次出现为捕获语义，之后出现则表示应该匹配与第一次捕获相等的值
• 命名的子模式 name @ PAT
• 子模式连接 (and PAT1 PAT2 ...), 表示任何子模式都和术语匹配，该模式才能匹配成功。
• 术语提取 (etor PAT1 PAT2 ...)

而右侧的表达式则允许以下内容

• 整数和符号常量
• 布尔变量（使用 Scheme 语法）
• 在模式中被绑定的变量
• 术语构造 (ctor EXPR1 EXPR2 ...)
• 变量绑定 (let ((var1 type1 EXPR1) (var2 type2 EXPR2) ...) BODY ...)

ISLE 使用启发式方法决定应用适用规则中的某一条。 例如，当多条规则匹配同一个术语时，会优先选择更具体的那条，也就是说，如果规则 1 已经完成匹配，而规则 2 有相同前缀，但可以继续执行后续匹配并成功，则选择规则 2 进行重写。

如果确实需要，也可以手动指定优先级。优先级为一个有符号整数，数值大小表示优先级高低，默认情况下规则的优先级为 0。

ISLE 中存在类型。

类型要么是一个原语（如整数类型或者导入的类型），要么是一个枚举（和类型）

(type u32 (primitive u32))
(type MyType
  (enum
    (A (x u32) (y u32))
    (B (z u32)
    C)))
(type MyType2 extern (enum (A)))

    

对应地，我们可以在 ISLE 中声明构造器、参数和返回值的类型。

(decl Term1 (u32 u32) MyType)
(decl Term2 () u32)

    

(decl MyType.A (u32 u32) MyType)
(decl MyType.B (u32) MyType)
(decl MyType.C () MyType)

(decl MyType2.A () MyType2)

    

由于一种类型的术语只能被重写为同一类型的另一术语，因此可能会让人困惑，如何将其中一种类型的术语转换为另外一种类型的术语

对此的解决方案是定义一个顶级的构造器作为“驱动程序”

(type T1 ...)
(type T2 ...)

(decl Translate (T1) T2)

(rule (Translate (T1.A ...))
      (T2.X ...))
(rule (Translate (T1.B ...))
      (T2.Y ...))
    

构造器和提取器都分为外部和内部。在上文中提到的 decl 声明的是内部构造器。

我们可以使用如下方法声明内部提取器。

(decl A (u32 u32) T)
(extractor (A pat1 pat2)
           (and
             (extractArg1 pat1)
             (extractArg2 pat2)))

    

其作用类似于语法宏，也就是任何模式 (A PAT1 PAT2) 都会被拓展为 (and (extractArg1 PAT1) (extractArg2 PAT2))

而外部构造器、提取器，则对应宿主语言中的一个函数。

如果构造器具有类型 T1 -> T2, 则要求宿主语言中也有一个相同类型的函数； 如果提取器具有类型 T1 -> T2，则要求宿主语言中具有对应的 T2 -> Option[T1] 类型的函数，其中 Option 可以用来表示提取（匹配）是否成功。

外部提取器可以被声明为 infallible 的，可以提高生成代码的效率。在这种情况下，对应的外部函数具有签名 T2 -> T1

除此之外，ISLE 具有一些语法糖：

rule 被允许包含子匹配，其语法如下：

(rule LHS_PATTERN
  (if-let PAT2 EXPR2)
  (if-let PAT3 EXPR3)
  ...
  RHS)
    

匹配过程变为，在完成主模式匹配后，依次评估表达式并尝试用对应的子模式进行匹配，如果不成功，则该规则匹配失败。

由于在匹配过程中会发生函数调用，因此我们要求表达式是纯的。由于无法自动确定外部构造器的纯度，因此需要手动进行 pure 标记来确保表达式是无副作用的。

partial 用于标注会失败的外部构造器。这里和外部提取器的区别是，它可以被用在表达式侧来提前结束规则的匹配。（问题：通配符可以匹配失败的构造么？）

if-let可以被进一步省略为 if，其中要求对应表达式返回结果 #t | #f

2024 年 9 月 5 日

可快照数据结构

ICFP 24 的论文 Snapshottable Stores 描述了一种可快照的数据结构。

这里可快照的意思就是，可在任意时刻去保存数据结构的一个状态，称之为快照，并允许之后将数据结构恢复到这一快照对应的状态。这两个操作都应该是相对廉价的。（否则你总是可以复制整个数据结构并在之后进行替换，但这样操作的时间和空间开销都太大了！）

本文只考虑了对可变引用的快照。对于不可变引用，其本身就是可持久化的，因此并不需要做特殊的处理。尽管如此，还有有一些可以拓展的地方，比如对可变数组的修改等。

核心算法来自于 Baker 的 Version Tree (1978)。我们需要一个树状的 store 结构来记录历史信息。快照也就是特定时刻的版本树，捕获快照只需要记录特定时刻的树根即可。

对任意可变引用 \([r \mapsto x_1]\)，若要更新其新值为 \(x_2\)，我们创建一个新树根 new_root = ref Mem，将旧树根代表的节点对应内容更新为 Diff(r, \(x_1\), new_root)，同时将 Store 的树根更新为 new_root。因为我们已经记录了引用之前指向的值，此时即可覆写引用指向新值 \(x_2\)。

恢复快照可以分为两种情况，其中一种为快照即是当前状态，所以我们什么都不需要做。

另一种情况下，快照的节点指向了一棵子树（包含快照后所做的修改历史），引用的新值即为快照树节点中记录的值。此外，我们需要遍历历史，将这一历史反向链接。也就是说， 对于修改链 \([r \mapsto x_1][r \mapsto x_2][r \mapsto x_3]\)，若要恢复到 \(x_2\) 状态，我们会生成一个新的树，包含有两条链，分别为 \([r \mapsto x_1][r \mapsto x_2]\) 和 \([r \mapsto x_3][r \mapsto x_2]\)。

以上内容大致概括了 Baker 的工作，而这篇 ICFP 24 的新贡献包括一个被称作 Record Elision 的重要优化。

Record Elision

其核心思想是，如果我们可以确定两次 set 间并没有快照发生，那我们根本不需要分别为两次 set 创建对应的日志节点，而是共享一个节点。

为此我们需要为引用、快照、树节点和 store 树都增加一个 field 记录当前代数。如果进行了快照，则递增代数。当进行 set 操作时，我们先检查当前树根的代数，如果发现相等，则直接进入 fast path，更新引用即可。否则进入 slow path，更新引用、记录修改并更新代数。

2024 年 8 月 26 日

OCaml 的一些新加入或即将加入的语言特性

OCaml 这个语言就是有一点神奇，说古老也古老，但是这几年在 Jane Street 财主的扶持下也开始加了很多有意思的新特性，这里简单总结一下。

代数效果

重量级特性，介绍的文本有很多，就不多说了。

模态内存管理

名字来源自 Graded Modal Calculus 分级模态演算，具体是啥咱也不知道。

在这个类型系统里有三个Mode 模式，分别为 Affinity, Uniqueness, 和 Locality

• Affinity: Many | Once
• Uniqueness: Unique | Shared
• Locality: Global | Local

模式作为类型修饰符的时候，可以放到函数类型的箭头的任意一侧，或者同时两侧。如果没有模式的修饰符，则认为有遗留/默认模式 （分别为 many, shared, global, 对应经典 OCaml 的行为。如 graph @ local -> string @ unique

模式也可以附着于变量绑定时的模式上，如 let f (x @ unique) = ... in ...

但是在没有函数箭头时使用是没有意义的，如 type t = string @ shared

同时定义三个模态 many, shared, global 来表示模式三元组间的变换

shared (a, u, l) = (a, shared, l)
many (a, u, l) = (many, u, l)
global (a, u, l) = (a, shared, global)
    

注意到这里 global 模态会同时将 uniqueness 变为 shared，这是为了允许借用 borrowing 存在的健全性考虑的。

可以给 record 的 field 标注模态，如 type 'a shared = { s : 'a @@ shared }。

如果 record r 本身具有模式 m，且 field f 具有模态 n，则称 r.f 具有模式 n(m)。

Uniqueness 单一性

其中 uniqueness 允许安全的进行 in-place 更新，也就是最近很火的 reuse。 这里不等同于传统 OCaml 的 mut 关键词带来的可变性。 基于 uniqueness 的可变性在语义上仍然是函数式的，不会引起外部状态的改变。

有一个示例如下：

type 'a list = Nil | Cons of { hd : 'a; tl : 'a list }
let rec rev_append xs acc =
  match xs with
  | Nil -> acc
  | Cons x_xs -> rev_append x_xs.tl (Cons { overwrite x_xs with tl = acc })
    

上述片段如果传入的列表并不是 unique 的话，则是有问题的，因此我们希望 reverse 具有如下类型：

let reverse xs = rev_append xs Nil
val reverse : 'a list @ unique -> 'a list @ unique
    

这里的 unique 表明，在任意时间，程序里只存在一个对 unique 值的引用。

Uniqueness 是一个 深 属性，也就是说 unique 值的各个组成部分必须也是 unique 的。

Affinity 仿射性

需要注意到光有 uniqueness 是不够的，因为我们仍然轻松构造出有问题的代码。

let rejected =
  let xs @ unique : int list = [1;2;3] in
  let f = fun zs -> rev_append xs zs in
  let ys = f [4] in
  let zs = f [5] (* Oh no! zs and ys refer to the same memory! *)
  in ...
    

例如这里的函数闭包 f，持有了唯一的对 xs 的引用； 即便我们让 f 亦为 unique，我们也不能阻止对 unique 调用两次，最终获得预期之外的结果（因为 xs 被反转了两次）。

因此引入了 affinity，我们使用此模式来限制对值使用的次数。

它和 uniqueness 的核心区别在于，uniqueness 是对过去的总结；而 affinity 是对未来的限制。

为了让上文代码正确，我们选择让 f 变为 once 模式，从而拒绝以上代码。

... let f @ once = fun zs -> rev_append xs zs in ...
    

Locality 局部性

最后一个模式为 locality, 用于控制值的生命周期不能超过当前 region。

如果能确保这一性质，那就自然地可以将不逃逸出 region 的值分配在 stack 上，获取一定的性能优势并降低对 GC 的压力。

Borrowing 借用

由于现在我们可以确保值不会逃逸出区域，我们可以在某个 region 内安全地借用一个 unique 的值。

例如我们可以定义如下的 borrow 函数

val borrow : 'a @ unique -> ('a @ local -> 'b) -> ('a * 'b shared) @ unique
let borrow x f =
  let result = f &x in
  x, { s = result }
    

之前我们提到 global 隐含了 shared, 这是为了避免我们将一个 unique 值放入具有 global 模态的 record field, 然后又将其作为 unique 值提取出来，从而导致 unsound 的程序语义。

or_null 类型

很多语言都会使用可以为 null 的值来作为 option 类型的一种替代品，但是对于 int option option 这种嵌套类型来说只有一个 null 就显得无能为力了。

那如果反其道而行之，我们只需要一个 null，应该如何设计对应的类型呢？这个 or_null 类型的设计很好地体现了相关的一些考量。

为了区分我们是否还可以使用 null，我们将类型分为两类，一种被称作 no-null type， 也就是说其对应的底层表示中并没有使用和 null 相同的模式（例如为一个全 0 的值）， 例如 string, int 等。 另一种是 with-null type，和上述内容刚好相反。 所以对于 'a or_null 类型，我们希望 'a 是 no-null 的。

在拥有 or_null 类型后，自然地我们可以利用 OCaml 里全 0 表示并不对应任何值的现状，使用该模式表示 null，有效减少了堆分配。

不过在抽象类型和类型参数的默认类别应该是 no-null 还是 with-null 的问题上，还有一些问题需要澄清。 另外 OCaml 的 float array 非常特别，也需要特殊处理。

扁平化字段

这是一个比较简单的改动，允许用户手动指定一些 field 为未装箱或不需要扫描的。代价是牺牲了 generic 的 compare 操作。

实现上需要在对象头里记录一个数值指定需要扫描的 field 数量。此外需要 layout 重排，将不需要 scan 和需要 scan 的 field 分为两个区域。

2024 年 8 月 24 日

关键词：SIMD, SWAR, Parsing

问：给定二进制串 \(00010010\)，如何获取两个 1 之间的位全置为 1 的二进制串？

答：使用 \(\oplus\) 操作计算前缀和： $$ 00010010 \oplus 00100100 \oplus 01001000 \oplus 10010000 \oplus 00100000 \oplus 01000000 \oplus 10000000 = 00001110 $$ 这一操作也等价于 Carry-less Multiplication 或 Xor Multiplication。

问：给定二进制串 \(00110100\), 如何判断一或多个 1 的起点（终点）？

答：左（右）移取反后按位与即可。 $$ \~~(00110100 \verb|<<| 1)~\&~00110100 = 10010111~\&~00110100 = 00010100 \\ \~~(00110100 \verb|>>| 1)~\&~00110100 = 11100101~\&~00110100 = 00100100 $$

关于内联优化：有一个 g x，其中我们将 j x 视为一个汇合点

      
g x = let j x = f x
      in case x of A → j 1
                   B → j 2
      
    

如果在另一个函数 a 中我们调用 h (g x)，那么在内联 g 后可能会想到将的调用推入 g 的分支：

      
a x = h (g x)
→
a x = let j x = f x
      in case x of A → h (j 1)
                   B → h (j 2)
      
    

但这样我们就失去了对汇合点可以尾调用的性质。为了避免这种情况，我们需要将 h 直接推入汇合点。

      
a x = let j x = h (f x)
      in case x of A → j 1
                   B → j 2
      
    

从另一个角度理解（将跳转到汇合点视为跳转到一个 basic block）：

flowchart TD;
he(h _) --> ge
ge(g x = case x) -->|case A| cA(j 1)
ge -->|case B| cB(j 2)
cA --> gexit(f x)
cB --> gexit
    

正确的变换会产生如下的控制流图：

flowchart TD;
he(h _) --> gexit(f x)
ge(g x = case x) -->|case A| cA(j 1)
ge -->|case B| cB(j 2)
cA --> he
cB --> he
    

而只推一半意味着（在保证是跳转到汇合点而不是调用函数的前提下）会产生如下的不可能存在的控制流图：

flowchart TD;
gexit(f x) -->|case A?| heA(h _)
gexit --> |case B| heB(h _)
ge(g x = case x) -->|case A| cA(j 1)
ge -->|case B| cB(j 2)
cA --> gexit
cB --> gexit