[译]通过例子学子类型推理（八）：可变性
上周，我们为 cubiml 编译器添加了改进的错误信息。本周，我们将回归到功能开发，并为语言和类型系统添加可变性。
到目前为止，cubiml 中的所有东西都是不可变的，这意味着一旦创建了值，就不能改变。可变性经常被人诟病，因为它增加了出现问题的可能性，但它也让很多算法的表达更自然，对于编写高效代码来说是必不可少的。我们将以 ML 风格引用的形式实现可变性。
引用
传统的命令式语言支持多种形式的可变性 - 可变的局部变量、可变的结构字段等。然而，为了保持 cubiml 的简单性，我们在类型系统中用单一的专用功能和最小的语法糖来实现每个概念。例如，cubiml 函数总是只接收一个参数。如果你想让函数接收多个参数，可以通过向函数传递含多个字段的记录来模拟。
同样，在 cubiml 中所有的可变性都是通过引用类型来实现的。你可以通过在记录字段中存储引用来模拟传统的可变字段，通过在变量中存储引用来模拟可变的变量，以此类推。
ML 引用和你可能习惯的不太一样。它们是指向堆上一个可变的、垃圾回收的存储位置的指针，支持三种操作：
ref x创建新引用，初始值是x。注意，这将把x的值复制到新位置，并返回指向该位置的指针。ref foo.bar返回指向用foo.bar值初始化的位置的指针，而不是指向foo字段本身的指针。！r解引用引用r并返回当前存储在里面的任何值。这是另一个 ML 风格和 C 风格语法不同的令人困惑的例子。r := x将x存储在引用r内，覆盖之前存储的任何值。传统上，这个操作会返回单元值（即空记录），但我们会像 JavaScript 一样遵循 C 风格赋值的方法，赋值会返回新值，因为在编译成 JavaScript 时，这样更容易实现。你可能会想在自己的语言中做不同的事情，这是一个简单的改变。
请注意，引用可以被别名。例如，我们可以创建引用 a 并将其复制到变量 b 中。然后通过 b 所做的任何更改都可以通过 a 看到，反之亦然，如下面的 REPL 会话所示。
>> let a = ref 42
ref 42
>> let b = a
ref 42
>> b := 77
77
>> !a
77
我们还看到，创建引用并不影响原值。
>> let foo = {bar = 12}
{bar=12}
>> let r = ref foo.bar
ref 12
>> r := 77
77
>> foo.bar
12
变体
对核心类型系统添加引用之前，我们需要先介绍变体的概念。我们在前面的文章中，在处理函数类型时简单地提到了这一点，现在是时候更深入地解释它了。
在考虑泛型子类型时，主要有两种类型的类型参数，协变和逆变。
协变类型是指父类型与类型参数遵循相同的子类型关系。例如，如果有一个含协变类型参数 T 的泛型 Foo[T]，并有类型 A 和 B ，其中 A 是 B 的子类型，那么 Foo[A] 就是 Foo[B] 的子类型。大多数情况下，这就是你想要的。
逆变类型是指子类型关系被反转的类型。如果有类型 A 和 B ，其中 A 是 B 的子类型，那么 Foo[B] 就是 Foo[A] 的子类型。最常见的例子是函数的参数类型。假设你有一个函数，它的参数是 A。你可以用 A 来调用它，但不能用 B 来调用，因为 B 是 A 的超类型，也就是说，它比 A 更不细化。现在考虑一个函数，它参数是 B。你可以用 A 来调用它，也可以用 B 来调用它。这个函数严格来说比以前更通用，所以它是需要 A 的函数的子类型。事实上，函数的参数类型是逆变的，返回类型是协变的。
然而，还有第三种可能的变体：不变的类型参数。顾名思义，不变类型参数不会在其父类中引起任何子类型关系。如果有类型 A 和 B，其中 A 是 B 的子类型，那么 Foo[A] 和 Foo[B] 之间在任何一个方向上都不存在子类型关系。只有当它们的类型参数相等的时候，我们才能把一个 Foo 赋给另一个 Foo。
不变类型通常用于可变数据结构。例如，考虑列表类型 List[T] 应该是什么变体。如果列表是不可变的（只读），那么答案很简单 - T 应该是协变的。假设又有类型 A < B，考虑 List[A] 和 List[B]。由于我们谈论的是不可变的列表，唯一可用的操作就是从它们中读取。List[B] 的约束是 get() 总是返回 B。现在看看 List[A]。get() 返回 A，但是 A 是 B 的子类型，所以它也返回 B! 因此，List[A] 严格来说更通用，我们有 List[A] < List[B]。
当列表可变时，一切都会改变。List[B] 的约束是 set() 接收 B。然而 List[A] 的 set() 方法不能处理任意的 B。它只能处理 A，它是 B 的子类型。因此，List[A] 不能成为 List[B] 的子类型。但是，List[B] 也不能是 List[A] 的子类型，因为它的 get() 方法只返回 B，而不是 A。因此，当涉及到可变数据结构时，相关类型参数必须是不变的。
说句题外话，Java 在设计最初的语言时，在数组上就臭名昭著地搞错了这一点。尽管 Java 的数组是实际上是可变的，但他们还是决定让它们成为协变的，而不是不变的。这意味着
Object[] foo = new String[1];
foo[0] = new Integer(0);
是有效的 Java 代码，编译时没有错误。当你试图将 Integer 存储在不能实际处理它的数组中时（由于被创建为只能容纳 String），你会在运行时得到一个 ArrayStoreException。
死亡不变性！
此时，你可能已经注意到一个问题。双合一算法就是要传播子类型约束。在 check_heads 函数中，当检查非原生类型时，我们会在组件类型之间创建新的流（即子类型）关系，要么是协变类型的的同一方向，要么是逆变类型的相反方向。然而，对于不变类型，我们必须以某种方式在组件类型之间创建相等约束来代替，而双合一与相等约束是不兼容的。
这个难题的解决方案是认识到，不变性并不是真正的基本概念，只是在描述类型和合并该类型的协变和逆变部分时不精确的结果。
为了说明这一点，我们以之前的可变列表为例，为它写出一个伪代码接口。
class List[T] {
get(index: int) -> T;
set(index: int, value: T) -> void;
}
如果单独看每个方法，就没有任何问题。在 get 中，T 只作为返回类型出现，这意味着它可以安全地协变。在 set 中，T 只作为参数出现，这意味着它可以安全地逆变。需要 T 不变的唯一原因是，我们在这两种情况下都使用了单一类型参数。
因此，消除不变性的解决方案是将每个不变的类型参数替换成一对类型参数，一个是协变，一个是逆变。在这种情况下，我们可能有 List[W，R] 类型，其中协变 R 参数描述了可以从列表中读取的类型，而逆变 W 参数描述了可以写入列表的类型。
如果这听起来很像之前在类型检查器中处理变量的方式，那么恭喜，你已经上手了。实际上，这也是我们如何解决确保新的 W 参数被约束为 R 参数的子类型的问题 - 也就是说，从列表中的每一次读取都可以看到写入该列表的每一个类型。我们可以利用现有的类型检查器设计，只需创建一个变量节点，并将其两个“端”作为两个类型参数即可!
实现
像往常一样，我们先将新的操作添加到 AST 中。
LetRec(Vec<VarDefinition>, Box<Expr>),
Literal(Literal, Spanned<String>),
Match(Box<Expr>, Vec<(Spanned<CaseMatchPattern>, Box<Expr>)>, Span),
+ NewRef(Box<Expr>, Span),
Record(Spanned<Vec<(Spanned<String>, Box<Expr>)>>),
+ RefGet(Spanned<Box<Expr>>),
+ RefSet(Spanned<Box<Expr>>, Box<Expr>),
Variable(Spanned<String>),
}
语法
当要在语言中加入新语法时，主要的复杂问题是决定使用哪个优先级。当我在选择优先级的时候，有几个考虑因素。
- 解引用是简单操作，你很可能想经常做，而且是在更复杂的表达式中。例如，如果有两个整型引用
a和b，你可能希望能够相加它们的值，所以像!a + !b这样的东西应该可以使用，而不需要括号。同样，p := !p + 1也需要可以工作。 - 你应该能够很容易地解引用嵌套的引用链，例如
!!r。 - 然而，解引用
SimpleExpr会导致与字段访问的冲突，因为它使!a.b这样的代码变得模棱两可 - 应该是(!a).b还是!(a.b)？我想大多数人都会期待后者，所以我把它放在SimpleExpr和CaseExpr之间的新优先级中。 ref x使用与函数调用相同的语法（f x），所以给它与函数调用相同的优先级似乎是有道理的，但这样做会引起冲突，而且在任何情况下都不会有很好的效果，因为函数调用是左结合的。因此，我把它放在CaseExpr下的级别上，它仍然允许期望的语法，比如传递对函数调用的引用（f ref x），创建对 case 类型的引用（ref `Foo {}）。- 很少会用到获取引用赋值的值(
r := x)，所以我把它放在最低的优先级。 - 在
a := b := c的情况下，将其解析为(a := b) := c是没有意义的，所以左边至少需要是CompareExpr。然而，赋值给运算符的结果是没有意义的（反正它们只返回基础类型），所以我把左边一直提升到CallExpr。
总之，说完了这些，下面是新的语法规则。
@@ -113,6 +113,20 @@ LetRec: Box<ast::Expr> = {
}
+NewRef: Box<ast::Expr> = {
+ Spanned<("ref" CaseExpr)> => {
+ let ((_, expr), span) = <>;
+ Box::new(ast::Expr::NewRef(expr, span))
+ }
+}
+RefGet: Box<ast::Expr> = {
+ "!" <Spanned<RefExpr>> => Box::new(ast::Expr::RefGet(<>))
+}
+RefSet: Box<ast::Expr> = {
+ <Spanned<CallExpr>> ":=" <Expr> => Box::new(ast::Expr::RefSet(<>))
+}
+
+
MultOpSub: (ast::OpType, ast::Op) = {
"*" => (ast::OpType::IntOp, ast::Op::Mult),
"/" => (ast::OpType::IntOp, ast::Op::Div),
@@ -167,9 +181,14 @@ SimpleExpr = {
VarOrLiteral,
"(" <Expr> ")",
}
-CaseExpr = {
+RefExpr = {
SimpleExpr,
+ RefGet,
+}
+CaseExpr = {
+ RefExpr,
Case,
+ NewRef,
}
CallExpr = {
CaseExpr,
@@ -194,6 +213,8 @@ Expr = {
Let,
LetRec,
Match,
+ RefSet,
}
TopLevelItem: ast::TopLevel = {
类型节点
现在到了最有趣的部分 - 为类型系统添加引用。这当然涉及到类型节点头枚举中的新变体。
VFunc { arg: Use, ret: Value },
VObj { fields: HashMap<String, Value> },
VCase { case: (String, Value) },
+ VRef { write: Option<Use>, read: Option<Value> },
}
#[derive(Debug, Clone)]
enum UTypeHead {
@@ -31,6 +32,7 @@ enum UTypeHead {
UFunc { arg: Value, ret: Use },
UObj { field: (String, Use) },
UCase { cases: HashMap<String, Use> },
+ URef { write: Option<Value>, read: Option<Use> },
}
回顾一下，引用包含两个组件类型：一个协变类型，表示从引用中读取的值的类型，另一个是逆变类型，表示可写入该引用的值的类型。然而，在我们的语言中，引用的任何给定的使用要么是读，要么是写，而不是两者都是。因此，我们需要让用类型头参数成为可选的。这让我们可以用 UTypeHead{write: None, read: Some(T)} 表示对引用的读，而用 UTypeHead{read: None, write: Some(T)}表示对引用的写。
至于值类型头，并没有特别需要把参数做成可选的，但为了保持一致性，我们在这里还是这样做了。这样还有一个好的副作用，就是让表示只读或只写的引用值变的可能了。我们的语言没有任何语法来实际创建这样的值，但如果你想把它们添加到自己的语言中，这仍然是一个有用的示范。
在支持显式类型注释的语言中（简单起见，cubiml 中暂时省略了），只读和只写的引用类型特别有用。例如，你可以创建一个可变引用，然后在把它传递给其他代码之前，手动给它分配一个只读的引用类型，以静态地确保该代码不会修改你传递给它的引用。
接下来，为 check_heads 实现添加引用。
(&VRef { read: r1, write: w1 }, &URef { read: r2, write: w2 }) => {
if let Some(r2) = r2 {
if let Some(r1) = r1 {
out.push((r1, r2));
} else {
return Err(TypeError::new2(
"TypeError: Reference is not readable.\nNote: Ref is made write-only here",
lhs.1,
"But is read here.",
rhs.1,
));
}
}
if let Some(w2) = w2 {
if let Some(w1) = w1 {
// flip the order since writes are contravariant
out.push((w2, w1));
} else {
return Err(TypeError::new2(
"TypeError: Reference is not writable.\nNote: Ref is made read-only here",
lhs.1,
"But is written here.",
rhs.1,
));
}
}
Ok(())
}
如前所述，cubiml 没有任何创建只读或只写引用的语法，所以实际上无法到达这些检查。然而，为了说明起见，我还是把它们包含在这里。
@@ -88,6 +118,7 @@ fn check_heads(lhs: &(VTypeHead, Span), rhs: &(UTypeHead, Span), out: &mut Vec<(
VFunc { .. } => "function",
VObj { .. } => "record",
VCase { .. } => "case",
+ VRef { .. } => "ref",
};
let expected = match rhs.0 {
UBool => "boolean",
@@ -97,6 +128,7 @@ fn check_heads(lhs: &(VTypeHead, Span), rhs: &(UTypeHead, Span), out: &mut Vec<(
UFunc { .. } => "function",
UObj { .. } => "record",
UCase { .. } => "case",
+ URef { .. } => "ref",
};
Err(TypeError::new2(
为了完成类型检测器核心中的实现，我们需要添加对匹配表达式对的引用，用于在生成错误信息时显示类型，并在公共接口中添加构造函数。
pub fn reference(&mut self, write: Option<Use>, read: Option<Value>, span: Span) -> Value {
self.new_val(VTypeHead::VRef { write, read }, span)
}
pub fn reference_use(&mut self, write: Option<Value>, read: Option<Use>, span: Span) -> Use {
self.new_use(UTypeHead::URef { write, read }, span)
}
前端
最后，我们需要在类型检查器前端中添加支持。(我们还必须在代码生成和演示 UI 中添加支持，但和以往一样，我在这里不涉及这些内容)。
NewRef(expr, span) => {
let expr_type = check_expr(engine, bindings, expr)?;
let (read, write) = engine.var();
engine.flow(expr_type, write)?;
Ok(engine.reference(Some(write), Some(read), *span))
}
如果你到目前为止一直在关注的话，前台的实现应该是非常简单的。像往常一样，首先对子表达式进行类型检查，然后创建相关的用类型并为其添加流约束。
唯一棘手的部分是在 NewRef 中，我们创建变量，将变量的两个“端”作为引用的两个类型参数，如前所述。就其它而言，RefGet 和 FieldAccess 差不多，只是用引用用类型代替了记录用类型，而 RefSet 则和函数调用的处理有点类似。
RefGet((expr, span)) => {
let expr_type = check_expr(engine, bindings, expr)?;
let (cell_type, cell_bound) = engine.var();
let bound = engine.reference_use(None, Some(cell_bound), *span);
engine.flow(expr_type, bound)?;
Ok(cell_type)
}
RefSet((lhs_expr, lhs_span), rhs_expr) => {
let lhs_type = check_expr(engine, bindings, lhs_expr)?;
let rhs_type = check_expr(engine, bindings, rhs_expr)?;
let bound = engine.reference_use(Some(rhs_type), None, *lhs_span);
engine.flow(lhs_type, bound)?;
Ok(rhs_type)
}
本周的内容就到这里。下周，我们将介绍如何添加不完全的 case 匹配和记录扩展到类型系统中（以及扩展到语言）。