[译]通过例子学子类型推理（九）：匹配通配符、记录扩展和行多态
上周，我们为 cubiml 添加了可变性。本周我们将介绍通配符匹配模式和记录扩展。
匹配通配符
到目前为止，我们的匹配表达式一直是详尽的，这意味着它们需要列出一系列的 case 来检查，如果向匹配表达式传递任何不在 case 列表中的内容，都会导致编译时错误。例如，下面的代码
let area = fun arg ->
match arg with
| `Square x -> x.len *. x.len
| `Rect x -> x.height *. x.width;
area `Circle {radius=1.2}
导致类型错误，因为 Circle 不在匹配表达式处理的 case 列表中。
TypeError: Unhandled case `Circle
Note: Case originates here
| `Rect x -> x.height *. x.width;
area `Circle {radius=1.2}
^~~~~~~
But it is not handled here.
let area = fun arg ->
match arg with
^~~
| `Square x -> x.len *. x.len
| `Rect x -> x.height *. x.width;
大多数情况下，这就是你想要的。然而，有时你可能不知道全部可能的 case，你只想有个“默认”或“其他”分支，并对任何意外 case 进行通用处理。或者，你可能知道完整的可能 case 集，但希望以同样的方式处理其中的大部分情况。这些情况可以通过通配符匹配模式来处理。
let area = fun arg ->
match arg with
| `Square x -> x.len *. x.len
| `Rect x -> x.height *. x.width
| _ -> "error: unexpected case";
area `Circle {radius=1.2}
不在匹配模式中列出标签(如 `Square x)，而只列出标识符，(上例中的 _)。这样的通配符模式可以匹配任何可能的标签值。
在上面的例子中，“默认”处理器实际上并没有使用输入值，所以我们只是在匹配模式中把它绑定到 _。然而，任何标识符都可以在这里使用，并且像往常一样在匹配臂的主体中创建一个带有该名称的变量。例如，下面的例子会打印出错误值（使用在其他地方定义的假设的 debug 函数）。
let area = fun arg ->
match arg with
| `Square x -> x.len *. x.len
| `Rect x -> x.height *. x.width
| x -> "Error: Expected a Square or Rect, got " ^ (debug x) ^ " instead.";
area `Circle {radius=1.2}
上面的例子其实根本不关心 _ 或 x 变量的类型。然而，当我们把类型系统做得更聪明一些，在知道没有采取的分支时给绑定变量一个改善的类型，也就是没有显式匹配的 case，这时，“通配符”的真正威力就来了。例如，我们希望上面的 x 具有“与 arg 相同的类型，并且不是 Square 或 Rect ”的类型。
let area = fun arg ->
match arg with
| `Square x -> x.len *. x.len
| `Rect x -> x.height *. x.width;
area `Square {len=4.};
area `Rect {height=4.; width=2.5};
let area2 = fun arg ->
match arg with
| `Circle x -> x.radius *. x.radius *. 3.1415926
| x -> area x;
area2 `Square {len=4.};
area2 `Rect {height=4.; width=2.5};
area2 `Circle {radius=1.2}
这允许我们做一些像上面的例子一样的事情，即把通配符变量传给其他地方的第二个匹配。由于 area2 中的 x 是静态已知的，不是 Circle，编译器允许我们将它传递给原始 area 函数中的匹配，即使 area 不处理 Circle 情况。
这使得我们可以做一些事情，像上面的例子一样，以完全类型安全和静态检查的方式，在一个地方匹配一些 case，并将其他 case 的处理推迟到代码的其他部分。然而，它实际上比这更强大，因为我们不需要单一、线性的匹配链。我们可以添加、删除和更改 case，在中间添加任意的条件逻辑等等，并且仍然可以在编译时让编译器检查一切。
说完了这些，是时候实现通配符匹配了。
语法和 AST
这一次，所需要的解析器改变比平时更大。首先，抽象语法树。
@@ -36,7 +36,12 @@ pub enum OpType {
}
type VarDefinition = (String, Box<Expr>);
-type CaseMatchPattern = (String, String);
+
+#[derive(Debug)]
+pub enum Pattern {
+ Case(String, String),
+ Wildcard(String),
+}
#[derive(Debug)]
pub enum Expr {
@@ -49,7 +54,7 @@ pub enum Expr {
Let(VarDefinition, Box<Expr>),
LetRec(Vec<VarDefinition>, Box<Expr>),
Literal(Literal, Spanned<String>),
- Match(Box<Expr>, Vec<(Spanned<CaseMatchPattern>, Box<Expr>)>, Span),
+ Match(Box<Expr>, Vec<(Spanned<Pattern>, Box<Expr>)>, Span),
NewRef(Box<Expr>, Span),
Record(Spanned<Vec<(Spanned<String>, Box<Expr>)>>),
RefGet(Spanned<Box<Expr>>),
表达可能在最后有通配符匹配的自然方法是，像之前那样，只有 case 匹配列表，再在后面加上可选的通配符匹配字段。然而，试图确保一个匹配中最多只有一个通配符模式，并且通配符只能出现在匹配的最后，这在语法级别上很难做到。相反，我们在语法层面将匹配指定为模式列表，每个模式都可以是 case 或通配符，然后在类型检查器前端确保上述有效性约束。
因此，我们用新的 Pattern 枚举代替 CaseMatchPattern，它可以容纳 Case 或 Wildcard 模式，并更新语法来匹配。
<Spanned<Tag>> <CaseExpr> => Box::new(ast::Expr::Case(<>)),
}
-CaseMatchPattern = {
- Tag Ident,
+MatchPattern: ast::Pattern = {
+ Tag Ident => ast::Pattern::Case(<>),
+ Ident => ast::Pattern::Wildcard(<>),
}
MatchArm = {
- <Spanned<CaseMatchPattern>> "->" <CompareExpr>,
+ "|" <Spanned<MatchPattern>> "->" <CompareExpr>,
}
我还借此机会稍微修改了一下匹配语法，要求在初始匹配臂前加一个 | ，简化了语法，避免了在重新排列匹配臂时需要增删 | ，这是我希望在 cubiml 的原始版本中想到的另一个改变。
-MatchSub = "match" <Spanned<Expr>> "with" <SepList<MatchArm, "|">>;
+MatchSub = "match" <Spanned<Expr>> "with" <MatchArm+>;
类型检查器前端
匹配的前端代码也有不少变化。
Match(match_expr, cases, span) => {
let match_type = check_expr(engine, bindings, match_expr)?;
let (result_type, result_bound) = engine.var();
// Result types from the match arms
let mut case_type_pairs = Vec::with_capacity(cases.len());
let mut wildcard_type = None;
// Pattern reachability checking
let mut case_names = HashMap::with_capacity(cases.len());
let mut wildcard = None;
for ((pattern, pattern_span), rhs_expr) in cases {
if let Some(old_span) = wildcard {
return Err(SyntaxError::new2(
"SyntaxError: Unreachable match pattern",
*pattern_span,
"Note: Unreachable due to previous wildcard pattern here",
old_span,
));
}
use ast::Pattern::*;
match pattern {
Case(tag, name) => {
if let Some(old_span) = case_names.insert(&*tag, *pattern_span) {
return Err(SyntaxError::new2(
"SyntaxError: Unreachable match pattern",
*pattern_span,
"Note: Unreachable due to previous case pattern here",
old_span,
));
}
let (wrapped_type, wrapped_bound) = engine.var();
case_type_pairs.push((tag.clone(), wrapped_bound));
let rhs_type = bindings.in_child_scope(|bindings| {
bindings.insert(name.clone(), wrapped_type);
check_expr(engine, bindings, rhs_expr)
})?;
engine.flow(rhs_type, result_bound)?;
}
Wildcard(name) => {
wildcard = Some(*pattern_span);
let (wrapped_type, wrapped_bound) = engine.var();
wildcard_type = Some(wrapped_bound);
let rhs_type = bindings.in_child_scope(|bindings| {
bindings.insert(name.clone(), wrapped_type);
check_expr(engine, bindings, rhs_expr)
})?;
engine.flow(rhs_type, result_bound)?;
}
}
}
let bound = engine.case_use(case_type_pairs, wildcard_type, *span);
engine.flow(match_type, bound)?;
Ok(result_type)
}
这主要是由于需要报告通配符匹配的非法组合的语法错误（即通配符模式之后出现的任何内容都是语法错误，因为通配符之后的任何内容都是无法到达的）。
回顾下之前，我们报告了重复的 case 标签的语法错误，维护了从标签到跨度的映射 case_names 以便于实现这一点。每当处理 case 模式时，我们首先对照 case_names 检查标签。如果该标签已经存在，我们会返回错误 "SyntaxError: Repeated match case"，使用新跨度和从映射中得到的前一次出现的跨度。
// Pattern reachability checking
let mut case_names = HashMap::with_capacity(cases.len());
let mut wildcard = None;
if let Some(old_span) = wildcard {
return Err(SyntaxError::new2(
"SyntaxError: Unreachable match pattern",
*pattern_span,
"Note: Unreachable due to previous wildcard pattern here",
old_span,
));
}
新代码相当类似。除了 case_names 映射之外，还有变量 wildcard: Option<Span>，它可选地持有一个指向之前看到的通配符模式（如果有的话）的跨度。除了重复的 case 检查之外，我们还有第二个通配符的有效性检查。每当处理一个模式时，不管它是 case 还是通配符模式，我们首先检查 wildcard 变量。如果是 Some，即已经看到了通配符模式，我们就会报错，因为通配符模式之后的任何东西都是无法到达的。此外，错误信息文本也已更新。
Wildcard(name) => {
wildcard = Some(*pattern_span);
let (wrapped_type, wrapped_bound) = engine.var();
wildcard_type = Some(wrapped_bound);
let rhs_type = bindings.in_child_scope(|bindings| {
bindings.insert(name.clone(), wrapped_type);
check_expr(engine, bindings, rhs_expr)
})?;
engine.flow(rhs_type, result_bound)?;
}
除此之外，我们还有检查通配符模式匹配臂右侧的实际代码。这与 case 模式的代码几乎完全相同，但 Rust 的借用检查器使得这里的代码难以避免重复。
let bound = engine.case_use(case_type_pairs, wildcard_type, *span);
最后，我们当然需要将通配符匹配的变量（如果有的话）传递给 case 类型构造器。
类型检查器核心
首先，我们在 UCase 用类型头添加新字段 wildcard，如果有通配符模式，则给出绑定变量的用类型，否则为 None。
UCase {
cases: HashMap<String, Use>,
wildcard: Option<Use>,
},
pub fn case_use(&mut self, cases: Vec<(String, Use)>, wildcard: Option<Use>, span: Span) -> Use {
let cases = cases.into_iter().collect();
self.new_use(UTypeHead::UCase { cases, wildcard }, span)
}
我们还更新了构造器函数来传递它。
现在到了最有趣的部分 - check_heads 的实现。这一部分比较棘手。考虑下面的代码。
match (`Tag x) with
| `CaseA a -> _
| `CaseB b -> _
回顾一下，在现有的系统下，这将导致对 check_heads 的调用，大致可以用下面的伪代码来描述：
lhs = VCase{case=("Tag", x)}
rhs = UCase{cases=Map{"CaseA" => a, "CaseB" => b}}
check_heads(lhs, rhs)
其中 x、a、b 等是同名变量类型节点的替身。
目前我们在 check_heads 中检查的方法是，取左边的标签（"Tag"）并在右边的 cases 映射中查找。如果标签不存在，返回类型错误。否则，将从左边的子节点向右边的相应子节点添加一个流约束。因此，如果标签是 "CaseA"，我们将添加流关系 x -> a，如果是 "CaseB"，我们将添加 x -> b。
为了实现具有所需语义的通配符匹配，我们必须稍微改变一下。对于像下面这样的代码
match (`Tag x) with
| `CaseA a -> _
| `CaseB b -> _
| c -> _
我们将有以下伪代码。
lhs = VCase{case=("Tag", x)}
rhs = UCase{cases=Map{"CaseA" => a, "CaseB" => b}, wildcard=Some(c)}
check_heads(lhs, rhs)
check_heads 的处理方式与之前类似，只是当左侧的标签不在右边的 cases 映射中时，我们会查阅右边的 wildcard 字段。如果它是 None，我们会像之前一样返回类型错误。如果它不是 none，我们从 lhs（不是 x！）向该变量添加一个流约束，即 lhs -> c，其中 lhs = VCase{case=("Tag", x)} 是包含要检查的头部的整个类型节点。
在这点上，我们遇到了问题 - lhs 实际上并没有传递给 check_heads。到目前为止，check_heads 只在被检查的两个节点的子节点之间建立了流关系。这意味着不需要传递父节点本身，只需要传递它们的头。然而，现在我们需要得到整个 lhs 节点的指针（即索引）。
这意味着必须改变 check_heads 的签名，并添加新的 lhs_index 和 rhs_index 参数。我们现在实际上并没有使用 rhs_index，但保持一致挺好，以后会使用它。
fn check_heads(
lhs_ind: ID,
lhs: &(VTypeHead, Span),
rhs_ind: ID,
rhs: &(UTypeHead, Span),
out: &mut Vec<(Value, Use)>,
) -> Result<(), TypeError> {
while let Some((lhs, rhs)) = type_pairs_to_check.pop() {
if let TypeNode::Value(lhs_head) = &self.types[lhs] {
if let TypeNode::Use(rhs_head) = &self.types[rhs] {
- check_heads(lhs_head, rhs_head, &mut pending_edges)?;
+ check_heads(lhs, lhs_head, rhs, rhs_head, &mut pending_edges)?;
}
}
}
现在我们把所需的数据传给了 check_heads，是时候更新 check_heads 中的 case 分支了，它实现了上面描述的逻辑。
(
&VCase { case: (ref name, lhs2) },
&UCase {
cases: ref cases2,
wildcard,
},
) => {
// Check if the right case is handled
if let Some(&rhs2) = cases2.get(name) {
out.push((lhs2, rhs2));
Ok(())
} else if let Some(rhs2) = wildcard {
out.push((Value(lhs_ind), rhs2));
Ok(())
} else {
Err(TypeError::new2(
format!("TypeError: Unhandled case {}\nNote: Case originates here", name),
lhs.1,
"But it is not handled here.",
rhs.1,
))
}
}
记录扩展
到目前为止，记录类型和 case 类型之间有一个显著的对称性。特别是，case 值类型与记录用类型具有完全相同的结构，case 用类型与记录值类型具有相同的结构。既然我们给 case 用类型添加了新功能，那么问题自然而然就来了，记录值类型的等价功能是什么呢？答案是记录扩展。
回顾一下，在添加通配符匹配之后，case 用类型头现在看起来是这样的
UCase {
cases: HashMap<String, Use>,
wildcard: Option<Use>,
},
之前只是添加了字符串到用类型的映射，但今天我们添加了可选的额外的用类型，名为 wildcard。对记录的相应改变是增加可选的额外的值类型，我们将其命名为 proto。
VObj {
fields: HashMap<String, Value>,
proto: Option<Value>,
},
对于 case，其语义是我们根据 case 映射检查每个值，如果不存在，就给通配符添加一个流约束（如果存在）。本质上，wildcard 是一个额外的值，如果所有的 case 不在显式列出的 case 中，我们就把它们委托给它。
对于记录来说，相当于我们有一个显式列出的字段集，任何不在该列表中的字段查找都会被委托给 proto 值来代替。这基本上是同一种说法“如果你在这里没有找到你要找的字段，这里是另一个寻找的地方”。
这听起来很像继承，在 JavaScript 中，继承是用原型来完成的，因此使用这个名字。至于用户可见的语言功能，实际的效果是，我们可以取一条记录，扩展它来创建一条有额外字段的新记录，这条记录也拥有旧记录的所有字段，或者等价于把缺失的字段查找委托给旧记录。因此，我们把这叫做记录扩展。
很遗憾，OCaml 不支持记录扩展，所以我们必须自己编造一些语法，或者更准确的说，借用 Elm 的记录扩展语法来代替。在 Elm 中，在 0.16 版本之前，你可以用 { foo | 开始一条记录，把 foo 的所有字段都包含在新记录中。
let foo = {a=1; b=""; c=false};
let bar = {foo | a=true; d=-23}
请注意，“prototype” 值不一定是静态已知的。事实上，它可以是任何任意的表达式，只要你把它放在括号里。
>> let baz = {(if foo.c then foo else bar) | c=true}
{a=true; b=""; c=true; d=-23}
前面，我们描述了使用原型进行记录扩展，但实际上并不一定是这样实现的。事实上，有两种不同的方式来查找记录扩展。
第一种视图是我们已经介绍过的继承视图，每条记录都包含了在其定义中明确定义的字段，同时还有一个可选的到原型值的链接，缺失的字段将在运行时进行查找。另一个视图是复制视图，在创建记录时，记录复制其原型的所有字段，之后不维护任何与原型的链接。
由于我们的记录是不可变的，所以这两种视图之间没有可观察到的行为差异。事实上，cubiml 在类型检查器中使用继承视图，在实际生成的代码中使用复制视图。生成的代码在创建时复制了父对象的所有字段，而不是使用 JavaScript 原型，所以 {a=1; b=2} 和 {{a=1; b=6}。| b=2} 在运行时产生同样的值。
这也是为什么在上面的 baz 例子中，REPL 打印出 {a=true; b=""; c=true; d=-23}，而不是 {{{a=1; b=""; c=false} | a=true; d=-23} | c=true} 这样的东西，就像在运行时跟踪链接一样。
实现
总之，说完了这些，就该真正实现记录扩展了。这和通配符匹配的实现非常相似，所以我就不做太详细的介绍了。
像往常一样，我们从 AST 和语法开始。
- Record(Spanned<Vec<(Spanned<String>, Box<Expr>)>>),
+ Record(Option<Box<Expr>>, Vec<(Spanned<String>, Box<Expr>)>, Span),
+RecordExtension = {
+ <CallExpr> "|"
+}
KeyPairExpr = {
<Spanned<Ident>> "=" <Expr>,
}
-RecordSub = "{" <SepListOpt<KeyPairExpr, ";">> "}";
+RecordSub = "{" <RecordExtension?> <SepListOpt<KeyPairExpr, ";">> "}";
Record: Box<ast::Expr> = {
- Spanned<RecordSub> => Box::new(ast::Expr::Record(<>)),
+ Spanned<RecordSub> => {
+ let ((proto, fields), span) = <>;
+ Box::new(ast::Expr::Record(proto, fields, span))
+ }
}
之后，是类型检查器前端。在这种情况下，实现就简单多了，因为我们不必像以前那样费心去追踪无法到达的匹配模式的语法错误。我们要做的就是当 proto 值存在的话对其进行类型检查，并将其传递给值类型构造器。
- Record((fields, span)) => {
+ Record(proto, fields, span) => {
+ let proto_type = match proto {
+ Some(expr) => Some(check_expr(engine, bindings, expr)?),
+ None => None,
+ };
+
let mut field_names = HashMap::with_capacity(fields.len());
@@ -223,7 +259,7 @@ fn check_expr(engine: &mut TypeCheckerCore, bindings: &mut Bindings, expr: &ast:
let t = check_expr(engine, bindings, expr)?;
field_type_pairs.push((name.clone(), t));
}
- Ok(engine.obj(field_type_pairs, *span))
+ Ok(engine.obj(field_type_pairs, proto_type, *span))
}
最后，是类型检查器核心。在核心类型系统中的实现和上面的通配符匹配的实现是一样的，只是极性反转了。
(
&VObj {
fields: ref fields1,
proto,
},
&UObj { field: (ref name, rhs2) },
) => {
// Check if the accessed field is defined
if let Some(&lhs2) = fields1.get(name) {
out.push((lhs2, rhs2));
Ok(())
} else if let Some(lhs2) = proto {
out.push((lhs2, Use(rhs_ind)));
Ok(())
} else {
Err(TypeError::new2(
format!("TypeError: Missing field {}\nNote: Field is accessed here", name),
rhs.1,
"But the record is defined without that field here.",
lhs.1,
))
}
}
- VObj { fields: HashMap<String, Value> },
+ VObj {
+ fields: HashMap<String, Value>,
+ proto: Option<Value>,
+ },
- pub fn obj(&mut self, fields: Vec<(String, Value)>, span: Span) -> Value {
+ pub fn obj(&mut self, fields: Vec<(String, Value)>, proto: Option<Value>, span: Span) -> Value {
let fields = fields.into_iter().collect();
- self.new_val(VTypeHead::VObj { fields }, span)
+ self.new_val(VTypeHead::VObj { fields, proto }, span)
}
行多态
到目前为止，我们一直在类型系统中实现有用的功能，而不用担心用什么语法来描述它。不过，今天展示的功能用传统的类型语法写起来有点不方便，就像前面“与 arg 相同的类型，只是它不是 Square 或 Rect”的绕口令所提示的那样。
为了描述记录扩展等操作的类型，人们发明了行多态。这就像常规的多态（即泛型）一样，只不过我们没有可以替代不同类型的类型变量，而是有行变量，可以替代字段集。
这意味着，像 fun x -> {x | foo=4} 这样的操作可以用 row R: {R} -> {R | foo: int} 这样的行类型来描述。
传统上，记录扩展的形式化处理包括一个限制，即输入行不包含任何新定义字段的标签。然而，在 cubiml 中，我们没有这样的限制，只是让子代中定义的字段覆盖任何从父代复制的字段，因为这在实践中更有意义，尤其是应用于通配符匹配的双重情况。但是，如果你愿意的话，可以在类型检查器中使用类似于上面所示的技术轻松实现重复字段限制。
Let 多态
虽然记录扩展的抽象操作是行多态的，但使用它的任何特定的 cubiml 代码都不是多态的，因为我们目前所介绍的 cubiml 版本还不支持多态。
考虑以下代码
let f = fun x -> {x | foo=4};
let _ = f {a=5; b="hello"};
(f {c=8.3}).c
这将导致类型错误（“缺失字段 c”），因为编译器不够聪明，没有将函数的不同输入分开。目前，类型检查器将函数调用视为给定函数的所有调用混合在一起，所以它认为第二次调用 f 时的 .c 可能会看到第一次调用 f 时产生的 {a=5; b="hello"; foo=4}。
目前我们所拥有的 cubiml 版本有行多态的行部分，但是没有多态部分。上面的代码只是下面代码的一个特例，下面的代码也有完全相同的问题。
let f = fun x -> x;
let _ = f {a=5; b="hello"};
(f {c=8.3}).c
为了让这样的代码能够进行类型检查，我们需要让类型分析上下文敏感，让它把对函数的每一次调用都视为独立类型，这样，一个函数调用的输入就不会污染该函数的每次其他调用所看到的结果，类型方面。下周，我们将介绍 let 多态，处理这个问题的标准方法。