思考可变值语义

这是关于zest设计的系列内容的一部分。zest 有两个相互冲突的目标：

成为一种相当高效的命令式语言（如 go、julia）。
将值视为数据（如 erlang、clojure，见数据的形状)。
特别地，对于目标 2，希望保证deserialize(serialize(x)) == x。
满足这两个目标很棘手，因为一旦允许可变引用，就可能创建循环数据结构，并必须处理标识与值的问题。例如，Javascript 即使有广泛的 json 序列化形式，也不满足目标 2：
```
> let x = []
undefined
> JSON.parse(JSON.stringify(x)) == x
false

> let y = new Date()
undefined
> typeof(JSON.parse(JSON.stringify(y))) == typeof(y)
false
```
解决此问题的唯一方法是可变值语义，核心思想是允许变异，但防止可变引用被观察或别名。有三种实现方式：隐式复制、动态别名跟踪和静态别名跟踪。
隐式复制
最简单的方法是在移入或移出可变值时总是要求复制：
```
var xs = list[string]['a','b','c']
let ys = xs // 深复制 xs
append(xs@, ys)
print(length(xs)) // 深复制 xs?!
print(length(ys)) // 深复制 ys?!
```
在可变性地使用可变值时效果不错，但对于length(xs)不需要最后一次复制。
动态别名跟踪
原始论文中玩具语言 swiftlet 使用的解决方案是通过引用计数来动态跟踪别名，对于大型值如列表。之前会复制xs，现在只需增加其引用计数。但每次变异值时都必须检查引用计数并可能进行防御性复制。
```
var xs = list[string]['a','b','c']
let ys = xs // 增加 xs 的引用计数
append(xs@, ys) // 浅复制 xs 并增加字符串的引用计数
print(length(xs)) // 增加 xs 的引用计数
print(length(ys)) // 增加 ys 的引用计数
```
引用计数使代码编写很容易，但也有问题：容易意外地复制大型值，需要复杂的优化来消除始终修改引用计数的性能开销。
静态别名跟踪
swiftlet 论文的作者正在开发一种名为hylo的系统语言。hylo 静态跟踪别名，所有值都有移动语义，语言扩展了不可变引用和可变引用。
```
var xs = list[string]['a','b','c']
let ys = deep-copy(xs) // 移除此复制会产生编译错误
append(xs@, ys) 
print(length(xs&)) // 传递 xs 的不可变引用
print(length(ys&)) // 编译错误 - ys 被 append 消耗 - 改为写入 append(xs@, deep-copy(ys))
```
这样 hylo 可以有可变值语义，同时完全避免隐式复制和引用计数开销，但代价是增加了程序员的标注负担，也增加了无法类型检查的程序数量。
还考虑了其他可能的设计轮廓：
如果引用可被观察，透明序列化就很难实现，它们必须始终是二等公民。
移动会传播。添加移动语义后也需要借用，最终进入 rust/hylo 的领域。
借用不会传播。似乎有借用而没有移动语义是完全合理的。
尝试将世界分为“需要移动语义的事物”和“可以松散的事物”，会导致所有移动语义的复杂性以及另一个世界和它们之间移动的规则，并不比直接做 rust/hylo 加Rc<T>更简单。
还发现一个与现有选项不同的山谷：
在类型系统中不出现拥有与借用的区别，而是每个堆分配值的引用都包含一个位来指示是拥有还是借用。在许多情况下，编译器可以推断此位的值，避免在释放时分支。当 l 值转换为 r 值时，根据目标的生命周期和是否为可变引用进行不同处理。*T（读作shared T）被视为小值并可以隐式复制。
这个山谷有一些有趣的权衡：
由于函数参数总是借用，只有在引用计数的值实际逃逸时才需要支付引用计数的开销。
如果x被借用，deserialize(serialize(x))是拥有的，但程序员无法观察到差异，仍能实现透明序列化。
不需要远程部分或类似功能，因为字段可以根据类型是拥有或借用，不逃逸就不需要复制。
对可变引用赋值总是需要复制，但在过去编写的代码中，值通常要么是内联存储的值（int/float/struct 等），要么是从不被修改的可以标记为共享的值。
还考虑了对 swiftlet 的一些调整：
闭包捕获可变引用
允许闭包捕获可变引用，如计算列表运行总和的内部迭代器代码：
```
var total = 0
each(nums@, (i, num@) {
   total@ += num
   num@ = total
})
```
但这种闭包不能逃逸所捕获的引用，视为别名。
不可变地闭包捕获可变引用
对于之前计算运行总和的代码，在常规命令式语言中没问题，但在 rust 中会报错。在 swiftlet 规则下代码被接受但结果错误，因为创建闭包会增加nums的引用计数，然后each-mut会进行防御性复制。改为通过引用捕获可变变量：
```
// compile error - closure aliases nums
each(nums@, (i, num@) {
  if i > 0 {
num@ += nums.{i-1}
  }
})
```
如果要按值捕获可以显式复制。
允许别名闭包
更谨慎地考虑允许闭包可变异地别名，如用于抽象分支控制流：
```
if(
  i > 0, 
  () { i@ = 1 }, 
  () { i@ = -1 },
)

while(
  () i > 0,
  () i@ -= 1,
)

visit(
  tree,
  on-branch: (branch) handle-branch(@compiler, branch),
  on-leaf: (leaf) handle-leaf(@compiler, leaf),
)
```
但这样会牺牲一些表达性，如f = (g, h) g(h)可能不再安全。
启用按引用调用
对于函数调用，如f(x@, really-big-struct)希望编译器按引用传递really-big-struct以更高效，但对于f(x@, x.big)不安全，可能导致可观察的别名。可以处理为x.big是别名。
结果位置语义
对于大结构体的返回，通常不会按值返回，而是在结构体中分配空间并传递指针。但对于x.big@ = big-to-big(y.big)可能存在别名问题，需要避免复制或显式复制。

如果能实现每种方法并比较人体工程学和性能，做出决策会更容易，但只有一个生命周期，所以在推进实际实现的同时也在编写想象中的代码来了解每种方法的感受。

隐式复制

动态别名跟踪

静态别名跟踪

闭包捕获可变引用

不可变地闭包捕获可变引用

允许别名闭包

启用按引用调用

结果位置语义