无类型检查的生命周期借用检查

# 无类型检查的借用检查 原文：https://www.scattered-thoughts.net/writing/borrow-checking-without-type-checking 这是一个玩具语言的演示，它具备动态类型、内联值、栈分配、内部指针、单一所有权以及受限的借用——表达能力不及 Rust，但远胜“二等引用”（例如我们可以写出外部迭代器）。由于没有静态类型，借用规则必须在运行时检查。 demo 的亮点在于：我们可以以极低成本完成检查，并给出有用的报错信息。 代码在这里：https://github.com/jamii/jams/blob/main/0007-borrowing-without-types/lib.zig ## 背景 我正在探索一种由 Julia 与 Zig 体现的类型系统风格：两者都先提供一个靠动态检查保证的动态类型系统，再叠上一层静态类型系统，用于证明多数动态检查其实可以省略。动态部分带来灵活性与元编程便利，静态部分则把开销消灭在日常代码里。 Julia 与 Zig 在处理“无法静态检查”的代码时略有不同：Zig 直接拒绝编译；Julia 则保留必要的动态检查，并在将来获得更多信息时再次尝试静态化。 在我为 Zest（https://github.com/jamii/zest）设计的第三种方案中，代码要么动态（解释执行），要么静态（编译执行），切换需显式标注。目标：大部分代码享受静态类型的保障，但仍可自愿接入动态胶水，用于 REPL、热重载、运行时代码生成、可塑软件等场景。 棘手之处在于我还希望强制“可变值语义”（mutable value semantics）。目前主流策略两条： - 引用计数 + 写时复制：性能开销大，且难以配合内部指针与显式栈分配。 - 静态类型系统：对我的动态语言没用。 于是只能另辟蹊径： - 借用检查的开销仅限于创建/销毁/复制引用时的几次引用计数操作。 - 引用计数本身永远放在栈上，缓存友好。 - 引用计数不跨线程，无需原子操作。 - 只有动态栈帧才付引用计数代价；堆上不分配计数器，静态代码看不见它们。 - 一旦违反借用规则，运行时立即抛错，并精确指出“元凶”值。 而且，我至少有 60% 的把握这套方案是 sound 的 :) ## REPL 提示 如果下面看到绿色勾，则所有示例可交互：改代码→点 eval 看结果。 若见红叉，多半是禁了 JS 或我没在你浏览器上测试，只能看代码框末尾的离线输出。 ✗ ## 值 玩具语言很迷你：整数、元组、函数、基本控制流。 ``` let nums = [1, 5]; let inc = fn (i) {i + 1}; while {nums[0] < nums[1]} { nums[0] = inc(nums[0]); }; nums [5, 5] ``` 每个变量都是独立值。改一个变量绝不会影响别的变量。 ``` let a = [1, [2, 3]]; // `b` 是 `a` 的独立副本 let b = a; b[1][0] = 42; // `a` 保持不变 [a, b] [[1, [2, 3]], [1, [42, 3]]] ``` 块结束时，块内定义的变量全部 drop，释放对应内存。 ``` let a = [1, [2, 3]]; { let b = [4, 5]; let c = 6; // c 在此 drop // b 在此 drop }; // a 在此 drop [] ``` 这种“值语义 + 可变”实现简单，但毫无实用性：每次使用都深拷贝，大结构吃不消。我们需要在不破坏值语义的前提下表达共享。 ## 引用 引用让我们表达“值存在别处”的概念。`box` 函数把内容放堆上，例如 `[2, 3]` 进堆，`[1, box(...)]` 留在栈。 ``` [1, box([2, 3])] [1, box([2, 3])] ``` 解引用 `*` 钻到引用内部。 ``` let a = [1, box([2, 3])]; a[1]*[0] 2 ``` 下面代码该干啥？ ``` let a = [1, box([2, 3])]; let b = a; // 这算啥？ b*[0] = 42; a ``` 要么拷整个堆内容——GB 级数据说拷就拷？ 要么只拷指针共享堆——可 `b*[0]=42` 会漏到 `a`，值语义破功。 默认策略：不加显式标注，甭想拷 box。 ``` let a = [1, box([2, 3])]; let b = a[1]; b*[0] = 42; b* Error at 2:9 Can't copy an owned reference ``` 想玩引用，得说清楚“到底想干啥”。 选项一：**move** 用 `^`——拿到引用副本，但原值销毁！ ``` let a = [1, box([2, 3])]; let b = a[1]^; b*[0] = 42; b* [42, 3] ``` 图里那些 `XXX` 表示原引用已毁，暂未回填。（我可不想给所有类型硬塞一个零值，那是十亿美元错误。） 毁掉的槽可被新值覆盖。 ``` let a = [1, box([2, 3])]; let b = a[1]^; a = [4, box([5, 6])]; a[1]* [5, 6] ``` 如此可（笨拙地）把引用传进函数：move 进去、函数内 mutate、返回、再贴回原变量。 ``` let inc_first = fn (x) { x*[0] = {x*[0] + 1}; x^ }; let a = [1, box([2, 3])]; let [a0, a1] = a^; a = [a0^, inc_first(a1^)]; a^ [1, box([3, 3])] ``` 选项二：**借用** `!`——像把值 move 进新 `box(...)`，但 drop 时把值还回原处。（有借有还！） ``` let inc_first = fn (x) { x*[0] = {x*[0] + 1}; // `x` 在此 drop，变异后的内容 move 回 `a` }; let a = [1, box([2, 3])]; inc_first(a[1]*!); a^ [1, box([3, 3])] ``` 选项三：**共享** `&`——行为像借用，但原主人保留副本，不被销毁。 ``` let a = [1, box([2, 3])]; let b = a[1]*&; [a[1]*, b*] [[2, 3], [2, 3]] ``` 为维持“两值互不干扰”的幻觉，任一副本都禁止写入。 ``` let a = [1, [2, 3]]; let b = a[1]&; b*[0] = 7; Error at 3:1 Can't assign through a shared reference ``` ``` let a = [1, [2, 3]]; let b = a[1]&; a[1][0] = 7; Error at 3:1 Can't assign to `a` because it is shared by `b` ``` ## 闭包 支持闭包，但不隐式捕获作用域变量。 ``` let iter_copy = fn (tuple_ref) { let index = 0; fn () { if index < len(tuple_ref*) { let elem = tuple_ref*[index]; index = {index + 1}; elem } else { [] } } }; let a = [1,2]; let next = iter_copy(a&); [next(), next(), next()] Error at 4:8 Can't refer to `index` here because it is defined outside this function - try using an explicit capture instead. ``` （Rust 式隐式捕获当然能做，但显式捕获讲借用规则时省心。） 先看不靠闭包怎么写：把状态打包成元组，再传给一个独立 `next` 函数。 ``` let iter_copy = fn (tuple_ref) { let index = 0; [index, tuple_ref] }; let next = fn (state_ref) { let [index, tuple_ref] = state_ref^; if index* < len(tuple_ref**) { let elem = tuple_ref**[index*]; index* = {index* + 1}; elem } else { [] } }; let a = [1,2]; let state = iter_copy(a&); [next(state!), next(state!), next(state!)] [1, 2, []] ``` 闭包只是语法糖：写明要捕获哪些状态 (`index, tuple_ref`) 及访问方式 (`!`)，编译器就展开成上面那样。 ``` let iter_copy = fn (tuple_ref) { let index = 0; fn [index, tuple_ref]! () { if index* < len(tuple_ref**) { let elem = tuple_ref**[index*]; index* = {index* + 1}; elem } else { [] } } }; let a = [1,2]; let next = iter_copy(a&); [next!(), next!(), next!()] [1, 2, []] ``` ## 安全性 底层实现里，借用/共享引用就是指向原值的指针，那些 `XXX` 并不存在。 借用检查的目标是“既要值语义简单，又要引用性能，且绝不让你看出破绽”。 静态类型系统下这出奇地容易；动态系统里想做得又便宜又正确就难得多。 下面先列“禁止清单”，再聊实现。 最大限制：**owned 引用（box）不得指向借用/共享引用**。 这保证借用/共享引用只活在栈上，后续规则动态执行才轻松。 ``` let a = 1; let b = box(a&); Error at 2:9 Can't box a shared ref ``` ``` let a = box(box(1)); let b = 2; a* = b&; Error at 3:1 Can't assign a value of type `number&` to a location of type `box(number)` ``` 只要存在借用引用，就不能再对该值创建新的借用/共享引用。 ``` let a = 1; let b = a!; let c = a!; Error at 3:9 Can't borrow `a` because it is borrowed by `b` ``` 运行时会跟踪借用引用的 drop。 ``` let a = 1; { let b = a!; // `b` 在此作用域结束处 drop }; let c = a!; // 现在又能借 [] ``` ``` let a = 1; let b = a!; b^; // `b` 被 move 然后 drop let c = a!; // 现在又能借 [] ``` 可对借用引用解构，一次性拿到多个部分借用。 ``` let a = [1,2]; let [b, c] = a!; b* = 42; c* = 101; b^; c^; // drop `b` and `c` a [42, 101] ``` 只要存在共享引用，就只能再创建共享引用。 ``` let a = 1; let b = a&; let c = a&; // 可以，想建多少都行 let d = a!; // 不行，写 `d` 会同时改 `b` 与 `c` Error at 4:9 Can't borrow `a` because it is shared by `c` ``` ``` let a = 1; let b = a&; let c = a&; b^; c^; // 全部共享引用 drop 后又能借 let d = a!; [] ``` 只要还有借用/共享引用，就算不重叠，也禁止 move 值任何部分。 ``` let a = [1,2]; let b = a[0]&; a[1]^ Error at 3:1 Can't move out of `a` because it is shared by `b` ``` 一旦值被 move（即使部分），整值都进入“已 move”状态，必须整体替换后才能再用。 ``` let a = [1,2]; a[0]^; a[1] Error at 3:1 Can't refer to `a` because it has been moved ``` ``` let a = [1,2]; a[0]^; a[0] = 3; // 只补回一部分不够 Error at 3:1 Can't refer to `a` because it has been moved ``` ``` let a = [1,2]; a[0]^; a = [3, 4]; // 整体替换即可 a [3, 4] ``` 变量只能持有指向“更长生命周期”变量的借用/共享引用。 ``` let a = 1; let b = 2; let c = a&; // ok，`a` 比 `c` 后 drop c = b&; // 也 ok，`b` 比 `c` 后 drop let d = 3; c = d&; // 糟糕，`d` 会比 `c` 先 drop Error at 6:1 This value can't be owned by `c` because it shares from `d`, which will be destroyed before `c` ``` 块返回的值，不得包含指向块内变量的借用/共享引用。 ``` let a = { let b = 1; b& }; Error at 1:9 This value shares from `b`, but `b` will be destroyed at the end of this block ``` 虽是动态类型，变量一旦赋值就不能改类型（因为栈分配大小固定）。 ``` let a = [1]; // 栈上分配 8 字节 a = [1, 2]; // 无法把分配扩成 16 字节 Error at 2:1 Can't assign a value of type `[number, number]` to a location of type `[number]` ``` 引用本身也不能改类型，即便大小相同。这让我们无需给每块内存存类型标签——总能从引用类型反推值类型。 ``` let a = box([1]); a = box([1, 2]); a* Error at 2:1 Can't assign a value of type `box([number, number])` to a location of type `box([number])` ``` 不过，像 Julia 一样，可在需要动态性的地方显式加类型标签。`any` 函数拿引用返回其动态版本。 ``` let a = box([1]); // 8 字节，类型 box([number]) let b = any(a^); // 16 字节，类型 box(any) b = any(box([1, 2])); b* [1, 2] ``` 但分配本身的类型仍不能变。 ``` let a = any(box([1])); a* = [1, 2]; a* Error at 2:1 Can't assign a value of type `[number, number]` to a location of type `[number]` ``` ## 表达能力 说完“不能”，再看“能”——仅靠二等引用做不到的事。 引用可以塞进元组。换到现实语言，就是 `Option<&mut T>` 这类类型能用了。 ``` let a = 1; let b = 2; let c = [a!, b!]; c[0]* = 3; c[1]* = 4; c^; [a, b] [3, 4] ``` 引用可以从函数返回。现实语言里就能写 `fn(&[T], usize) -> Option<&T>` 这种签名。 ``` let get = fn (tuple, index) { tuple*[index]& }; let a = [1, 2, 3]; get(a&, 1)* 2 ``` 甚至借用引用也能返回，但有点微妙。下面这个不行： ``` let get = fn (tuple, index) { tuple*[index]! }; let a = [1, 2, 3]; get(a!, 1)* = 5; a Error at 5:1 This value bor