[译]通过例子学子类型推理（十五）：单态类型注释
上周，我们讨论了静态类型注释背后的理论。本周，我们将介绍它们在 cubiml 中的实际实现。
类型注释设计
在 Ocaml 中，你可以通过写 (expr : type) 来注释表达式的类型，例如 (foo.bar : string) 或者 (fun x -> x : int -> int)。然而，虽然我们将在 cubiml 中使用的语法是相似的，但子类型和极化类型系统的引入使得类型注释的实际设计变得更加复杂。
回顾上周，cubiml 中的类型注释有两个目的：增加编译器错误的数量以及改善性能和错误信息。如果只关心第一个目标，可以直接将 type 解析为值类型，并与 expr 的推断类型合一。这很容易实现，也很琐碎，并且实现了类型扩展的目标，即增加编译器错误的数量。请注意，在这个系统下，类型注释不需要“匹配”。它只是被“添加”到推断类型中。例如，(42 : string) 只会导致类型 int | string。
然而，满足第二个目标比较棘手，因为它要求我们替换推断类型，而不仅仅是添加到它。这里的诀窍是解析类型注释，创建值类型和用类型，然后从推断的（值）类型向显式用类型添加流约束，并将显式值类型作为整个表达式的类型返回。
假设有一些像下面这样没有类型注释的流约束序列：
int_v -> var1 -> var2 -> var3 -> var4 -> var5 -> var6 -> bool_u
这将导致类型错误，因为整数值类型与布尔用类型不兼容。然而，编译器不知道链中的哪一点可能代表了程序员的实际错误，从而导致非特定的错误信息，并可能导致糟糕的类型检查性能。
现在假设程序员给 var3 添加了显式类型注解，说它的预期是整型。现在从显式类型注解中创建用和值类型，并使用它们来“断开链”，有点像这样。
int_v -> var1 -> var2 -> int_u XXX int_v -> var4 -> var5 -> var6 -> bool_u
现在，我们有两条较短的链，而不是一条长链。程序员的错误现在可以定位到 int_v -> var4 -> var5 -> var6 -> bool_u 部分，导致更具体的错误信息。
这意味着在解析类型注释时，需要产生一个（用类型，值类型）对，其中前者是后者的子类型。实际上，这意味着类型注释仅限于可以映射到两极的类型。幸运的是，这在实践中并不是什么限制。
类型化的表达式
首先，我们将为类型化的表达式添加语法规则和 AST 类型，(expr: type)。
SimpleExpr = {
FieldAccess,
Record,
VarOrLiteral,
"(" <Expr> ")",
+ "(" <Expr> ":" <Type> ")" => Box::new(ast::Expr::Typed(<>)),
}
RefExpr = {
SimpleExpr,
@@ -60,9 +60,27 @@ pub enum Expr {
Record(Option<Box<Expr>>, Vec<(Spanned<String>, Box<Expr>)>, Span),
RefGet(Spanned<Box<Expr>>),
RefSet(Spanned<Box<Expr>>, Box<Expr>),
+ Typed(Box<Expr>, Box<TypeExpr>),
Variable(Spanned<String>),
}
类型检查器的实现很简单：只需要解析 TypeExpr 得到 (Value，Use) 类型对，然后从推断的类型向解析的用类型添加流约束，并将解析的值类型作为整个表达式的类型返回。所有有趣的部分都在 TypeExpr 和新的 parse_type_signature 函数中，我们接下来会介绍。
Typed(expr, sig) => {
let expr_type = check_expr(engine, bindings, expr)?;
let sig_type = parse_type_signature(engine, sig)?;
engine.flow(expr_type, sig_type.1)?;
Ok(sig_type.0)
}
类型注释
接下来，要实现类型注释本身。这是完整的代码，作为一点预览，我将在后面一步步讲解。
语法
RecordTypeExtension = <Type> "with";
KeyPairType = {
<Spanned<Ident>> ":" <Type>,
}
RecordTypeSub = "{" <RecordTypeExtension?> <SepList<KeyPairType, ";">> "}";
RecordType: Box<ast::TypeExpr> = {
Spanned<RecordTypeSub> => {
let ((ext, fields), span) = <>;
Box::new(ast::TypeExpr::Record(ext, fields, span))
}
}
CaseTypeExtension = <Type> "|";
VariantType = <Spanned<Tag>> "of" <NoFunType>;
CaseTypeSub = "[" <CaseTypeExtension?> <SepList<VariantType, "|">> "]";
CaseType: Box<ast::TypeExpr> = {
Spanned<CaseTypeSub> => {
let ((ext, cases), span) = <>;
Box::new(ast::TypeExpr::Case(ext, cases, span))
}
}
FuncTypeSub = <NoFunType> "->" <Type>;
FuncType: Box<ast::TypeExpr> = {
Spanned<FuncTypeSub> => Box::new(ast::TypeExpr::Func(<>)),
}
RefReadability: ast::Readability = {
"readonly" "ref" => ast::Readability::ReadOnly,
"writeonly" "ref" => ast::Readability::WriteOnly,
"ref" => ast::Readability::ReadWrite,
}
RefType: Box<ast::TypeExpr> = {
NoFunType Spanned<RefReadability> => Box::new(ast::TypeExpr::Ref(<>)),
}
QMark: spans::Span = Spanned<"?"> => <>.1;
NullableType: Box<ast::TypeExpr> = {
NoFunType QMark => Box::new(ast::TypeExpr::Nullable(<>)),
}
TypeVar = "'" <Ident>;
NoFunType: Box<ast::TypeExpr> = {
Spanned<Ident> => Box::new(ast::TypeExpr::Ident(<>)),
<NoFunType> "as" <Spanned<TypeVar>> => Box::new(ast::TypeExpr::Alias(<>)),
Spanned<TypeVar> => Box::new(ast::TypeExpr::TypeVar(<>)),
RecordType,
CaseType,
RefType,
NullableType,
"(" <Type> ")",
}
Type: Box<ast::TypeExpr> = {
NoFunType,
FuncType,
}
AST
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Readability {
ReadWrite,
ReadOnly,
WriteOnly,
}
#[derive(Debug, Clone)]
pub enum TypeExpr {
Alias(Box<TypeExpr>, Spanned<String>),
Case(Option<Box<TypeExpr>>, Vec<(Spanned<String>, Box<TypeExpr>)>, Span),
Func(Spanned<(Box<TypeExpr>, Box<TypeExpr>)>),
Ident(Spanned<String>),
Nullable(Box<TypeExpr>, Span),
Record(Option<Box<TypeExpr>>, Vec<(Spanned<String>, Box<TypeExpr>)>, Span),
Ref(Box<TypeExpr>, Spanned<Readability>),
TypeVar(Spanned<String>),
}
类型检查器
fn parse_type(
engine: &mut TypeCheckerCore,
bindings: &mut HashMap<String, ((Value, Use), Span)>,
tyexpr: &ast::TypeExpr,
) -> Result<(Value, Use)> {
use ast::TypeExpr::*;
match tyexpr {
Alias(lhs, (name, span)) => {
let (utype_value, utype) = engine.var();
let (vtype, vtype_bound) = engine.var();
let old = bindings.insert(name.to_string(), ((utype_value, vtype_bound), *span));
if let Some((_, old_span)) = old {
return Err(SyntaxError::new2(
format!("SyntaxError: Redefinition of type variable '{}", name),
*span,
"Note: Type variable was already defined here",
old_span,
));
}
let lhs_type = parse_type(engine, bindings, lhs)?;
engine.flow(lhs_type.0, vtype_bound)?;
engine.flow(utype_value, lhs_type.1)?;
Ok((vtype, utype))
}
Case(ext, cases, span) => {
// Create a dummy variable to use as the lazy flow values
let dummy = engine.var();
let (vtype, vtype_bound) = engine.var();
let utype_wildcard = if let Some(ext) = ext {
let ext_type = parse_type(engine, bindings, ext)?;
engine.flow(ext_type.0, vtype_bound)?;
Some((ext_type.1, dummy))
} else {
None
};
let mut utype_case_arms = Vec::new();
for ((tag, tag_span), wrapped_expr) in cases {
let wrapped_type = parse_type(engine, bindings, wrapped_expr)?;
let case_value = engine.case((tag.clone(), wrapped_type.0), *tag_span);
engine.flow(case_value, vtype_bound)?;
utype_case_arms.push((tag.clone(), (wrapped_type.1, dummy)));
}
let utype = engine.case_use(utype_case_arms, utype_wildcard, *span);
Ok((vtype, utype))
}
Func(((lhs, rhs), span)) => {
let lhs_type = parse_type(engine, bindings, lhs)?;
let rhs_type = parse_type(engine, bindings, rhs)?;
let utype = engine.func_use(lhs_type.0, rhs_type.1, *span);
let vtype = engine.func(lhs_type.1, rhs_type.0, *span);
Ok((vtype, utype))
}
Ident((s, span)) => match s.as_str() {
"bool" => Ok((engine.bool(*span), engine.bool_use(*span))),
"float" => Ok((engine.float(*span), engine.float_use(*span))),
"int" => Ok((engine.int(*span), engine.int_use(*span))),
"null" => Ok((engine.null(*span), engine.null_use(*span))),
"str" => Ok((engine.str(*span), engine.str_use(*span))),
"number" => {
let (vtype, vtype_bound) = engine.var();
let float_lit = engine.float(*span);
let int_lit = engine.int(*span);
engine.flow(float_lit, vtype_bound)?;
engine.flow(int_lit, vtype_bound)?;
Ok((vtype, engine.int_or_float_use(*span)))
}
"top" => {
let (_, utype) = engine.var();
let (vtype, vtype_bound) = engine.var();
let float_lit = engine.float(*span);
let bool_lit = engine.bool(*span);
engine.flow(float_lit, vtype_bound)?;
engine.flow(bool_lit, vtype_bound)?;
Ok((vtype, utype))
}
"bot" => {
let (vtype, _) = engine.var();
let (utype_value, utype) = engine.var();
let float_lit = engine.float_use(*span);
let bool_lit = engine.bool_use(*span);
engine.flow(utype_value, float_lit)?;
engine.flow(utype_value, bool_lit)?;
Ok((vtype, utype))
}
"_" => Ok(engine.var()),
_ => Err(SyntaxError::new1(
"SyntaxError: Unrecognized simple type (choices are bool, float, int, str, number, null, top, bot, or _)",
*span,
)),
},
Nullable(lhs, span) => {
let lhs_type = parse_type(engine, bindings, lhs)?;
let utype = engine.null_check_use(lhs_type.1, *span);
let (vtype, vtype_bound) = engine.var();
let null_lit = engine.null(*span);
engine.flow(lhs_type.0, vtype_bound)?;
engine.flow(null_lit, vtype_bound)?;
Ok((vtype, utype))
}
Record(ext, fields, span) => {
let (utype_value, utype) = engine.var();
let vtype_wildcard = if let Some(ext) = ext {
let ext_type = parse_type(engine, bindings, ext)?;
engine.flow(utype_value, ext_type.1)?;
Some(ext_type.0)
} else {
None
};
let mut vtype_fields = Vec::new();
for ((name, name_span), wrapped_expr) in fields {
let wrapped_type = parse_type(engine, bindings, wrapped_expr)?;
let obj_use = engine.obj_use((name.clone(), wrapped_type.1), *name_span);
engine.flow(utype_value, obj_use)?;
vtype_fields.push((name.clone(), wrapped_type.0));
}
let vtype = engine.obj(vtype_fields, vtype_wildcard, *span);
Ok((vtype, utype))
}
Ref(lhs, (rw, span)) => {
use ast::Readability::*;
let lhs_type = parse_type(engine, bindings, lhs)?;
let write = if *rw == ReadOnly {
(None, None)
} else {
(Some(lhs_type.1), Some(lhs_type.0))
};
let read = if *rw == WriteOnly {
(None, None)
} else {
(Some(lhs_type.0), Some(lhs_type.1))
};
let vtype = engine.reference(write.0, read.0, *span);
let utype = engine.reference_use(write.1, read.1, *span);
Ok((vtype, utype))
}
TypeVar((name, span)) => {
if let Some((res, _)) = bindings.get(name.as_str()) {
Ok(*res)
} else {
Err(SyntaxError::new1(
format!("SyntaxError: Undefined type variable {}", name),
*span,
))
}
}
}
}
fn parse_type_signature(engine: &mut TypeCheckerCore, tyexpr: &ast::TypeExpr) -> Result<(Value, Use)> {
let mut bindings = HashMap::new();
parse_type(engine, &mut bindings, tyexpr)
}
详细的类型注释
回顾一下，解析类型签名需要产生值类型和用类型。最显而易见的方法是为用类型和值类型注释制定单独的语法，并将类型签名语法定义为两者的对。然而，这样做非常啰嗦，对于习惯于使用非极化类型系统语言的用户来说是很困惑的，而且实际上也没有必要。在我们的系统中，程序员通常认为几乎所有的作为类型的东西(int, {a: string; b: float}, bool -> int -> int 等)都可以解释为用类型和值类型。
因此，我们的类型注释语法只涵盖了与有效用和值类型均对应的类型，在我们的类型系统中，除了联合和交集类型之外，基本上就是所有了。幸运的是，在处理单型时，这实际上并不是一个限制(在处理类型归并和多态类型签名时，这个限制更为显著，但这是一个巨大的麻烦，我不打算涉及)。
基本类型
首先，我们有原始类型：bool, float, int, str, 和 null。这些只是在语法中用它们的名字来表示。为了避免将这些类型名变成关键字（并使语法对用户定义类型有更多的未来证明），语法只是接受任何标识符，并将其存储在 TypeExpr::Ident 节点中，检查稍后进行。
Spanned<Ident> => Box::new(ast::TypeExpr::Ident(<>)),
一旦进入 parse_type_signature，当匹配 Ident 节点时，只需对类型进行匹配，并返回相应的类型对，如果标识符不是有效的基本类型名，则返回语法错误。除了 bool, float, int, str, 和 null 之外，还有 bot, top, number 和 _，我们后面会讲到。
Ident((s, span)) => match s.as_str() {
"bool" => Ok((engine.bool(*span), engine.bool_use(*span))),
"float" => Ok((engine.float(*span), engine.float_use(*span))),
"int" => Ok((engine.int(*span), engine.int_use(*span))),
"null" => Ok((engine.null(*span), engine.null_use(*span))),
"str" => Ok((engine.str(*span), engine.str_use(*span))),
"number" => // todo
"top" => // todo
"bot" => // todo
"_" => // todo
_ => Err(SyntaxError::new1(
"SyntaxError: Unrecognized simple type (choices are bool, float, int, str, number, null, top, bot, or _)",
*span,
)),
},
parse_type_signature 返回 (Value, Use) 对。对于原始类型来说，这微不足道 - 只需调用类型检查器核心中相应的构造函数。例如对于 bool，只需做 (engine.bool(*span), engine.bool_use(*span))。
然而，有一个复杂的问题 - 以前，我们没有费心去创建空用类型，因为没有必要。没有类型注释，就没有办法利用一个值被保证为空的事实。然而，现在情况不同了。程序员可能想把一个值（只）注释为空，为了像上面讨论的那样“断开链”，我们需要值和用类型。因此，我们需要按照通常的模式，快速进入并添加空用类型：
@@ -42,6 +42,7 @@ enum UTypeHead {
UBool,
UFloat,
UInt,
+ UNull,
UStr,
UIntOrFloat,
UFunc {
@@ -78,6 +79,7 @@ fn check_heads(
(&VBool, &UBool) => Ok(()),
(&VFloat, &UFloat) => Ok(()),
(&VInt, &UInt) => Ok(()),
+ (&VNull, &UNull) => Ok(()),
(&VStr, &UStr) => Ok(()),
(&VInt, &UIntOrFloat) => Ok(()),
(&VFloat, &UIntOrFloat) => Ok(()),
@@ -188,6 +190,7 @@ fn check_heads(
UBool => "boolean",
UFloat => "float",
UInt => "integer",
+ UNull => "null",
UStr => "string",
UIntOrFloat => "float or integer",
UFunc { .. } => "function",
@@ -291,6 +294,9 @@ impl TypeCheckerCore {
pub fn int_use(&mut self, span: Span) -> Use {
self.new_use(UTypeHead::UInt, span)
}
+ pub fn null_use(&mut self, span: Span) -> Use {
+ self.new_use(UTypeHead::UNull, span)
+ }
pub fn str_use(&mut self, span: Span) -> Use {
self.new_use(UTypeHead::UStr, span)
}
数字
回想一下，有序比较运算符(<, >, <=, and >=)比较类型为 "int | float "的值，也就是说，它们既接受整数，也接受浮点数。尽管这并不常见，但只使用输入值进行比较的代码会希望使用这种类型，因此，我们需要在类型系统中公开它。例如，考虑以下函数。
let compare = fun args ->
if args.x < args.y then
-1
else if args.x == args.y then
0
else
1;
这样的函数应该有类型签名 {x: number; y: number} -> int，其中 number 是 int | float 的简写。我反反复复地考虑是把这个类型称为 "comparable"，它反映了它的真正含义（可以比较的类型），还是称为 "number"，它反映了在 cubiml 中什么类型恰好实现了它，但最终决定后一种类型会减少混乱。然而，这只是为了说明问题 - 根据你为自己的语言选择的类型系统的精确细节，你可能会做不同的事情。
总之，从语法上看，这只是使用 Ident 节点，就像上面的基础类型一样。唯一的区别在于 parse_type_signature。
"number" => {
// form the union vtype = float | int
let (vtype, vtype_bound) = engine.var();
let float_lit = engine.float(*span);
let int_lit = engine.int(*span);
engine.flow(float_lit, vtype_bound)?;
engine.flow(int_lit, vtype_bound)?;
Ok((vtype, engine.int_or_float_use(*span)))
}
对于用类型，只需返回 engine.int_or_float_use()。然而，在我们的类型系统中并没有 int_or_float 值类型这种东西。取而代之的是，我们只是取整型和浮点型的常规值类型的联合（分别是 engine.int() 和 engine.float()）。回顾一下，要取两个值类型的联合，只需创建一个临时类型变量，然后从每个类型中向该变量添加流约束。(我们也可以通过同样的过程取用类型的交集，只是边反过来)。
占位符
有时，可以只指定类型的部分是很有用的。为此，我们支持占位符类型，写成 _。例如，如果有函数 f，想指定它接受 int 作为参数，但不想指定关于返回类型的任何内容，你可以直接写 (f : int -> _)。
占位符有效地被推断类型的相应部分所填充。这意味着当使用占位符时，类型注解不再完全“断开链”。它只对明确指定的类型部分进行断链。事实上，写 (e : _) 相当于只写 e，根本没有类型注释。
总之，从实现上来说，这是所有类型中最容易实现的类型。只需要创建一个新类型变量然后返回。这将导致链中一个额外的环节，但其他方面表现的就像没有类型注解一样。
"_" => Ok(engine.var()),
可空类型
接下来是可空类型，即可能是空或一些非空值的值类型。这使用语法 T?，其中 T 是另一种类型。例如 string? 表示 string | null，而 number? 表示 int | float | null。
QMark: spans::Span = Spanned<"?"> => <>.1;
NullableType: Box<ast::TypeExpr> = {
NoFunType QMark => Box::new(ast::TypeExpr::Nullable(<>)),
}
在类型检查方面，可空类型与 number 类似。然而，AST 中的 Nullable 节点包含另一个类型签名（T? 中的 T）。因此，我们首先解析子类型签名，为子类型创建一个类型对。对于用类型，我们把子用类型封装进 null_check_use 并返回它。对于值类型，我们组成联合 T | null，其中 T 是子值类型，类似于前面的 number 例子。
Nullable(lhs, span) => {
let lhs_type = parse_type(engine, bindings, lhs)?;
let utype = engine.null_check_use(lhs_type.1, *span);
// form the union vtype = lhs_type.0 | null
let (vtype, vtype_bound) = engine.var();
let null_lit = engine.null(*span);
engine.flow(lhs_type.0, vtype_bound)?;
engine.flow(null_lit, vtype_bound)?;
Ok((vtype, utype))
}
函数类型
函数类型使用语法 T1 -> T2，其中 T1 是参数类型，T2 是返回类型。
FuncTypeSub = <NoFunType> "->" <Type>;
FuncType: Box<ast::TypeExpr> = {
Spanned<FuncTypeSub> => Box::new(ast::TypeExpr::Func(<>)),
}
类型检查很简单 - 只需解析子类型签名，并从中创建一个函数用和值类型。唯一稍微棘手的部分是，函数参数是逆变的，所以需要将参数类型的顺序反过来。
Func(((lhs, rhs), span)) => {
let lhs_type = parse_type(engine, bindings, lhs)?;
let rhs_type = parse_type(engine, bindings, rhs)?;
let utype = engine.func_use(lhs_type.0, rhs_type.1, *span);
let vtype = engine.func(lhs_type.1, rhs_type.0, *span);
Ok((vtype, utype))
}
引用类型
这里有趣的部分实际上是语法。回想一下，在为 cubiml 添加引用类型时，我们在类型系统中留下了空间来支持只读和只写引用，尽管语言没有定义实际创建它们的方法。除了类型系统的一致性之外，主要原因是一旦添加了类型注释，你可能希望能够显式地放宽一个到只读或只写类型的引用。好了，现在就是做这个的时候了。
在 Ocaml 中，引用总是读写式的，使用 T ref 的语法。由于某些原因（显然可以追溯到 70 年代 CS 论文中的符号约定），通用类型参数在 Ocaml 中是反的，即引用值写成 ref 1，但引用类型写成 int ref。
由于 Ocaml 不支持只读或只写的引用，所以在这里必须为它们创造我们自己的语法。我采用 T ref 来表示读写引用，而 T readonly ref 和 T writeonly ref 分别表示只读和只写引用。
RefReadability: ast::Readability = {
"readonly" "ref" => ast::Readability::ReadOnly,
"writeonly" "ref" => ast::Readability::WriteOnly,
"ref" => ast::Readability::ReadWrite,
}
RefType: Box<ast::TypeExpr> = {
NoFunType Spanned<RefReadability> => Box::new(ast::TypeExpr::Ref(<>)),
}
我们在 AST 中还有一个单独的枚举来存储引用类型签名的可读性状态。
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Readability {
ReadWrite,
ReadOnly,
WriteOnly,
}
现在是类型检查器部分。基本思路很简单 - 只需解析子类型签名并将其传递给引用类型构造器。唯一复杂的一点是，引用类型构造器的读和写参数是可选的。当引用类型是只读时，我们传递为写参数传递 None，否则像往常一样传递 Some(lhs_type)，同样的，对于只写引用也是如此。
Ref(lhs, (rw, span)) => {
use ast::Readability::*;
let lhs_type = parse_type(engine, bindings, lhs)?;
let write = if *rw == ReadOnly {
(None, None)
} else {
(Some(lhs_type.1), Some(lhs_type.0))
};
let read = if *rw == WriteOnly {
(None, None)
} else {
(Some(lhs_type.0), Some(lhs_type.1))
};
let vtype = engine.reference(write.0, read.0, *span);
let utype = engine.reference_use(write.1, read.1, *span);
Ok((vtype, utype))
}
注意，可读性是特定引用的属性（或者说是它的静态类型），而不是存储位置。拥有只读的引用仍然允许可能存在其他可写引用到该位置，反之亦然。例如，考虑下面的代码，其中有 add 函数，它通过输出指针“返回”它的答案，这在 C 代码中很常见。
let add = (
(* the type annotation ensures that this function does not read from args.out *)
fun args ->
args.out := args.x + args.y
: {x: int; y: int; out: int writeonly ref} -> _);
let r = ref 0;
add {x=91; y=101; out=r};
(* let's check what answer we got *)
!r
我们在输出指针上加了 writeonly 注解，以确保 add 函数不会试图从中读取和访问未初始化的数据。试图这样做会导致预期的类型错误：
TypeError: Reference is not readable.
Note: Ref is made write-only here
let _ = !args.out in
args.out := args.x + args.y
: {x: int; y: int; out: int writeonly ref} -> _);
^~~~~~~~~~~~~
let r = ref 0;
But is read here.
(* the type annotation ensures that this function does not read from args.out *)
fun args ->
let _ = !args.out in
^~~~~~~~
args.out := args.x + args.y
: {x: int; y: int; out: int writeonly ref} -> _);
然而，我们仍然可以在随后从 r 读取，来看 add 的输出，即使它指向与 args.out 相同的位置。特别是，这意味着持有 readonly 类型的引用并不能保证连续的读取返回相同的值，因为有别名的可能性。如果你想做这样的保证，你就需要一个 Rust 风格的所有权系统，其中有仿射类型和借用。
记录类型
记录类型与记录值类似，但字段名用 : 而不是 = 分开。例如，记录类型有名为 a 的整型字段和名为 b 的可空字符串字段，它将是 {a: int; b: string?}。
然而，还有两个其他皱褶。首先，我们要求字段列表是非空的。如果你想输入一个空记录（{}），你需要写 top 来代替，原因我后面解释。
其次，我们使用类似记录扩展语法来支持行多态。回想一下，占位符类型 _ 允许你只指定类型的一部分。例如，类型签名 {a: int; b: _} 确保 a 是一个 int，同时对字段 b 的类型没有任何限制。
但是，字段名的列表仍然是完全指定的。如果你想指定单独字段的类型，同时不对可能存在或不存在的任何其他字段施加任何限制，你可以写 {_ with a: int}，类似于记录扩展语法 {foo with a=4}。
注： 上一篇，我以为 Ocaml 不支持记录扩展，所以用类似 Elm 的语法代替。然而，事实证明，虽然 Ocaml 不支持记录扩展，但它有一个类似的功能，叫做功能更新，使用的语法是
{old_record with foo=new_val}。Ocaml 的版本限制很多 - 它只能改变现有字段的值，而不能遮蔽或添加新的字段，但它足够相似，所以我决定将 cubiml 切换到使用with进行记录扩展，而不是|。
请注意，只有当左边是占位符类型时，记录类型扩展语法才真正有意义。例如，没有理由写类似于 { {a: int} with b: bool } 这样的类型签名，因为你可以轻松地写 {a:int; b: bool} 来代替。然而，为了保持语法的简单性，我们仍然允许左边是任意类型签名，因为这比试图限制它是占位符要容易。同样，T? 中的 T 可以是任何类型，允许多余的类型签名，如 string?? 甚至 null?，因为这样可以保持语法简单。
RecordTypeExtension = <Type> "with";
KeyPairType = {
<Spanned<Ident>> ":" <Type>,
}
RecordTypeSub = "{" <RecordTypeExtension?> <SepList<KeyPairType, ";">> "}";
RecordType: Box<ast::TypeExpr> = {
Spanned<RecordTypeSub> => {
let ((ext, fields), span) = <>;
Box::new(ast::TypeExpr::Record(ext, fields, span))
}
}
在类型检查器中，我们像往常一样解析每个字段（以及通配符，如果存在的话）的子类型签名，并从中创建记录值类型来返回。用类型侧比较复杂 - 对于每个（字段、类型签名）对，我们用该字段和解析后的用类型创建记录用类型，然后取所有这些用类型的交集并返回。
如果存在通配符，我们将其用类型也添加到交集中。例如，在类似 (expr: {T with foo: int; bar: bool}) 这样的类型注解中，T 被解析为产生类型对 (V, U)，我们从 expr 的推断类型添加一个到 U 的流约束，和到 {foo: int} 和 {bar: bool} 一样。（或者更具体地说，我们创建交集类型 U & {foo: int} & {bar: bool}，然后向其添加流约束。）
Record(ext, fields, span) => {
let (utype_value, utype) = engine.var();
let vtype_wildcard = if let Some(ext) = ext {
let ext_type = parse_type(engine, bindings, ext)?;
engine.flow(utype_value, ext_type.1)?;
Some(ext_type.0)
} else {
None
};
let mut vtype_fields = Vec::new();
for ((name, name_span), wrapped_expr) in fields {
let wrapped_type = parse_type(engine, bindings, wrapped_expr)?;
let obj_use = engine.obj_use((name.clone(), wrapped_type.1), *name_span);
engine.flow(utype_value, obj_use)?;
vtype_fields.push((name.clone(), wrapped_type.0));
}
let vtype = engine.obj(vtype_fields, vtype_wildcard, *span);
Ok((vtype, utype))
}
顶和底类型
如前所述，我们的类型注释语法被限制在可以同时映射到值类型和用类型的类型上，以减少啰嗦，避免程序员的混淆。这样做的主要效果是在类型签名中不允许联合类型和交集类型，只有少数特定的例外（number = int | float, T? = T | null 等等）。
乍一看，这似乎是一个严重的限制。例如，假设你有一个函数，它可以返回 int 或 bool。当 int | bool 不被允许时，你将如何给它一个类型注释？关键的见解是，虽然编译器在内部跟踪这个值可能是整型或布尔型的事实，但程序员没有办法实际观察到这一点。从程序员的角度来看，唯一重要的值类型是可以由某些用类型区分的值类型，反之亦然。
例如，如果你拿着那个 int | bool 的值，并试图使用它，你会发现，除了可以做无论什么类型的任何值都可以做的事情外，你实际上不能用它做任何事情。如果你试图相加它，你会得到一个错误，因为布尔不能被相加。如果你试图将它用作 if 条件，你会得到一个错误，因为整型不是有效的条件，只有布尔才是。
从程序员的角度来看，没有办法将这个值的类型与诸如 string | float 类型的值，甚至 {a:int} | (bool -> bool) 类型的值区分开来。他们只知道有一个值，这个值没有允许的类型特定操作。（好吧，错误信息显然会有所不同，但它们可以被使用的实际程序集是一样的。它们是上下文相等的。)
顺便说一下，这就是我们之前必须定义 number 和 T? 类型的原因。类型 int | float 的值是可以区分的，因为你可以用比较运算符(a < b)来使用它，不像类型 int | bool 的值。不用说，这在很大程度上取决于你实现的类型系统的细节。如果你添加了一些同时接受整型和布尔型的用类型（也许你喜欢使用整型作为 if 条件，C 风格），那么突然间 int | bool 就可以区分了，你需要在类型注释语法中处理它。
因此，除了已经讨论过的特殊情况外，我们不需要在注释语法中支持联合和交集类型。然而，我们仍然需要某种方法来注释含有像 int | bool 这样不可用类型的表达式的类型。答案是添加两个特殊的新基础类型：top 和 bot。
top 是所有类型的超类型。它表示一个可以是任何类型的值，因此没有支持的操作（除了像 == 这样接受任何类型的操作）。
bot 正好相反 - 是所有类型的子类型。它表示一个是所有类型的值，因此可以用于任何操作。由于没有值具有所有类型，这意味着不可能真正构造 bot 类型的值。bot 的用处主要是表示不可能调用的函数的参数类型（因为不可能产生 bot 值来调用它们），或者表示永远不会返回的函数的返回类型。
这也是为什么要用 top 来输入前面提到的空记录。一个有字段的记录可以通过访问这些字段来区分，但是（在 cubiml 当前实现中）仅仅基于空记录是一个记录的事实，你实际上无法对它做什么。没有用类型会关心独立于字段的记录。从程序员的角度来看，一个空记录可能就是一个 int | bool。
Case 类型
像往常一样，case 类型是记录的对偶 - 它们非常相似，只是极性相反。然而，有两个明显的区别 - 首先是语法明显不同，其次，case 类型现在支持条件流，这在记录类型中是没有对应的。
首先，语法。遵循 Ocaml，case 类型对于可能标签的固定列表的写法是这样的 [`Tag1 of int | `Tag2 of bool]。如果你想包含一些标签，加上没有提到的可能的任何数量的标签，你可以写成 [_ | `Tag1 of int | `Tag2 of bool]。与记录通配符一样，对于语法来说，开头的 _ 可以是任何类型，但只有当它是占位符时才有意义。
CaseTypeExtension = <Type> "|";
VariantType = <Spanned<Tag>> "of" <NoFunType>;
CaseTypeSub = "[" <CaseTypeExtension?> <SepList<VariantType, "|">> "]";
CaseType: Box<ast::TypeExpr> = {
Spanned<CaseTypeSub> => {
let ((ext, cases), span) = <>;
Box::new(ast::TypeExpr::Case(ext, cases, span))
}
}
接下来，就是如何处理条件流的问题了。回想一下，条件流开启了存在多态，即在存在或不存在类型的情况下，类型都是多态的。然而，在单态代码中，条件流实际上并没有什么用处，因为你可以直接删除死代码来达到同样的效果。
幸运的是，我们的类型注释只处理单态类型，所以根本不需要担心存在多态。类型构造器仍然需要我们为条件流提供一个类型对，所以只需要为此创建一个虚变量。除此之外，代码和记录类型的代码是一样的，只是极性反转了。
Case(ext, cases, span) => {
// Create a dummy variable to use as the lazy flow values
let dummy = engine.var();
let (vtype, vtype_bound) = engine.var();
let utype_wildcard = if let Some(ext) = ext {
let ext_type = parse_type(engine, bindings, ext)?;
engine.flow(ext_type.0, vtype_bound)?;
Some((ext_type.1, dummy))
} else {
None
};
let mut utype_case_arms = Vec::new();
for ((tag, tag_span), wrapped_expr) in cases {
let wrapped_type = parse_type(engine, bindings, wrapped_expr)?;
let case_value = engine.case((tag.clone(), wrapped_type.0), *tag_span);
engine.flow(case_value, vtype_bound)?;
utype_case_arms.push((tag.clone(), (wrapped_type.1, dummy)));
}
let utype = engine.case_use(utype_case_arms, utype_wildcard, *span);
Ok((vtype, utype))
}
递归类型
类型注释已经基本完成，但还有一种情况需要处理 - 递归类型。有时，从自身的角度定义类型是很有用的。例如，考虑以下创建了一个简单递归链表的代码。
let rec build_list = fun n ->
if n < 0 then
null
else
{val=n; next=build_list (n - 1)};
let list = (build_list 4 : (* what goes here??? *))
事实证明，用目前定义的语法是不可能写出这个表达式的。build_list 函数要么返回 null，要么返回包含整型值和指向另一个列表节点（可能是空）的指针的列表节点。在伪代码中，我们可以将其定义为类似于 type list = null | {val: int; next=list} 的东西，其中的 list 类型是从自身角度定义的。
递归类型的实际语法类似，但工作方式略有不同。它由两部分组成。首先，你可以通过写 T as 'name 来别名一个类型，这就定义了一个等于 T 的类型变量 'name。然后，你可以通过名字来使用类型变量，如，写做 'name。使用这种语法，我们现在可以像这样写出上面的列表示例。
let list = (build_list 4 : {val: int; next: 'list}? as 'list)
像往常一样，我们从语法开始。在这种情况下，它只是两个简单的规则。
<NoFunType> "as" <Spanned<TypeVar>> => Box::new(ast::TypeExpr::Alias(<>)),
Spanned<TypeVar> => Box::new(ast::TypeExpr::TypeVar(<>)),
然而将它添加到类型检查器中却需要进行较大的重构。眼尖的人可能已经注意到，我之前将类型解析函数定义为 parse_type_signature，但每当一个类型签名需要递归解析另一个类型时，它反而会调用 parse_type，此外使用了一个添加的神秘的 bindings 参数。
这样做是因为现在类型解析需要跟踪类型变量定义集和它们对应的类型对。为了简化事情，我们禁止对类型变量进行遮蔽或重定义，所以可以使用简单的 HashMap 来跟踪这些。
parse_type_signature 是解析类型签名的顶层函数。它创建类型变量绑定的空映射，然后用它调用 parse_type。
fn parse_type_signature(engine: &mut TypeCheckerCore, tyexpr: &ast::TypeExpr) -> Result<(Value, Use)> {
let mut bindings = HashMap::new();
parse_type(engine, &mut bindings, tyexpr)
}
parse_type 又是递归函数，我们之前讨论的所有代码其实都在这里。
fn parse_type(
engine: &mut TypeCheckerCore,
bindings: &mut HashMap<String, ((Value, Use), Span)>,
tyexpr: &ast::TypeExpr,
) -> Result<(Value, Use)> {
use ast::TypeExpr::*;
match tyexpr {
Alias(lhs, (name, span)) => // ...
Case(ext, cases, span) => // ...
Func(((lhs, rhs), span)) => // ...
Ident((s, span)) => // ...
Nullable(lhs, span) => // ...
Record(ext, fields, span) => // ...
Ref(lhs, (rw, span)) => // ...
TypeVar((name, span)) => // ...
}
}
现在，bindings 参数已经通过线程，我们只需要定义 Alias 和 TypeVar 的解析代码。我们将从后面的开始。
TypeVar((name, span)) => {
if let Some((res, _)) = bindings.get(name.as_str()) {
Ok(*res)
} else {
Err(SyntaxError::new1(
format!("SyntaxError: Undefined type variable {}", name),
*span,
))
}
}
我们只需在 bindings 映射中查找变量名，并返回其对应的类型对，如果变量没有定义，则返回错误。很标准。
接下来，是 Alias 的情况。
Alias(lhs, (name, span)) => {
let (utype_value, utype) = engine.var();
let (vtype, vtype_bound) = engine.var();
let old = bindings.insert(name.to_string(), ((utype_value, vtype_bound), *span));
if let Some((_, old_span)) = old {
return Err(SyntaxError::new2(
format!("SyntaxError: Redefinition of type variable '{}", name),
*span,
"Note: Type variable was already defined here",
old_span,
));
}
let lhs_type = parse_type(engine, bindings, lhs)?;
engine.flow(lhs_type.0, vtype_bound)?;
engine.flow(utype_value, lhs_type.1)?;
Ok((vtype, utype))
}
由于别名和类型变量的整个目的是为了启用递归类型，我们需要在知道相应别名的完整类型之前允许用类型变量。处理这个问题的方式与之前处理类型检查 let rec 表达式的方式大致相同。当输入别名类型时，我们在求值别名类型的主体之前，在绑定映射中为该变量名创建一个临时变量来存储。然后，在求值完主体并得到一个类型对之后，从该类型对添加一个流边到之前定义的临时变量中，以关闭循环。
最后，如果变量已经在 bindings 中定义，我们也会返回错误。为此，我们在绑定中为每个变量存储一个 Span 以及它的 (Value，Use) 类型对，这样在需要显示错误信息时，就有跨度指向之前的定义。
请注意，与程序表达式不同，类型变量没有作用域，以保持简单（或者更准确地说，它们的作用域限制在它们出现的类型注释中）。类型注解通常比程序更简单，更小，所以缺乏作用域不太可能是一个问题。如果你确实发现自己在处理巨大的类型注释，你可能应该添加某种可重用的类型声明语法，在这种情况下，你无论如何都要对设计进行更大的修改。
无论如何，我们现在已经完成了在 cubiml 中实现类型注释的工作! 万岁! 至少对于单态类型来说是这样 ...
多态类型注释
目前为止，我们一直关注于单态类型的类型注释。然而，有了 let 多态性，变量可以是多态性类型方案的类型，如果我们也有办法手动注释类型方案，那就更好了。遗憾是，这有多个问题。
首先是语法。对于单态类型来说，没有必要支持显式的联合或交集类型，因为它们总是可以被简化掉，但是对于多态类型来说就不是这样了，所以你需要以某种方式支持它们。
与其支持显式的交集和联合，不如考虑将它们隐藏在约束语法之后。例如，与其使用 forall T => (T & {x: int}) -> T 这样的语法，不如使用 forall T => T -> T where T <: {x: int} 这样的，从类型的角度看是等价的，但对用户来说可能更直观。
然而，一个更严重的问题是实现的复杂性，在两个意义上都是。对于单态类型，我们可以离开复杂性，把每个类型注解当作 (Value, Use) 对，只需添加 v < u 约束来验证类型，这已经得到了类型系统的支持。然而，类型方案之间并没有这样的东西作为流约束。
当涉及到类型方案时，我们不是简单地添加流约束，而是要决定类型归并，这涉及到更多的问题。基本上，类型归并意味着寻找两个多态（值）类型方案，并决定一个是否归并了另一个，即，在后面的绑定类型变量的任何可能实例中，一个是否为另一个的子类型。
由于我们的类型被表示为（可能是循环的）图，检查归并涉及到将每个类型图转换为规范形式，然后试图在规范图中找到变量之间的映射，并在相应图中检查每对节点之间的子类型。
遗憾是，在最坏的情况下，规范形式可能是指数级的大，这意味着检查类型归并需要指数级的时间。而且即使不是因为时间复杂度，代码复杂度也是相当可怕的 - 为了实现这个，我很可能要花几周的时间才能涵盖所需的所有代码变化。因此，我不打算在 cubiml 中涵盖类型归并检查。
总结
这标志着我为 cubiml 计划的话题到此为止。如果你还有什么想让我讲的，欢迎在 Reddit 上评论。否则，这将是这个系列的最后一篇文章。我希望这篇文章能被证明有助于演示如何在新语言中实现类型推理，以及子类型推理在编程和语言设计中开启一些可能性。