[译]通过例子学子类型推理（六）：数字类型和运算符
上周，我们以语言 cubiml 为例，完成了对如何实现立方双合一类型推理算法的讲解。不过，为了保持初始教程的精简和易懂，cubiml 的初始版本非常简陋。今天我们将开始扩展 cubiml 的新功能，使其更加实用和有趣。我们将从简单的开始，为语言（和类型系统）添加整数、浮点数和字符串字面量，以及使用它们的操作符。
设计数字
在开始之前，我们必须决定要实现什么。在现有的编程语言中，数字类型和运算符的工作方式存在巨大的差异，它们的混乱和便利性、严格性和灵活性，以及对类型推理的冗长和顺从性都各不相同。
Int 与 i32
第一个问题是支持哪种数字类型。许多老式的和/或低级的编程语言都支持固定宽度的整数类型，因为它们很容易在编译器中实现。如果对固定宽度的整数进行操作，产生的结果不符合所选择的宽度，它就会被默默地截断，甚至更糟糕的是，产生未定义的行为。这个整数溢出问题导致了这类语言中非常常见的一类错误。
因此，cubiml 提供了单一的、任意精度的整数类型，这使得语言更简单、更容易理解，并大大降低了发生 bug 的可能性。对于这种方法，主要有两个反驳的理由。
第一，在固定宽度整数运算所引起的模运算是程序逻辑中所需要的部分的情况下，它可以导致更短的代码。然而，由此产生的代码容易出错，而且难以阅读，无论如何，让你的语言语义由 50 年前对编译器实现者方便的东西来定义是没有意义的。保持模运算和截断在极少数情况下期望的明确性要好得多。
更合理的抱怨是，任意精度的整数很难优化，默认情况下提供的性能很差。这对于 cubiml 来说不是问题，因为它是编译成 JavaScript 的，但是对于强调性能的低级语言来说，这可能是个问题。
对于这样的语言，我建议在语言规范中保留整数作为数学（任意精度）整数，并简单地要求程序员在必要时插入显式封装指令和/或注释，这样每个整数变量都被静态地知道只持有可以在底层机器存储中有效表示的值。这不仅简化了语言，还保证了用户考虑到整数溢出可能发生的时间和地点，以及如何恰当地处理，消除了一大类错误。
运算符
接下来的问题是运算符的设计。用户可以定义它们吗？它们只是对象上的特殊命名方法，还是全局函数，或者是编译器固有的？在后两种情况下，它们的类型签名应该是什么？
用户定义的运算符语义在动态语言中很好用，因为在动态语言中，所有的东西都只是对象上的方法，但在静态类型的语言中，由于编译器中如何确定源代码中任何给定的运算符应该代表什么代码的问题，它就不那么好用了。一种方法是显式地传递要使用的函数列表。这是很啰嗦的，所以语言通常提供了一种隐式传递函数列表的方法，就像 Haskell 的类型类或 Scala 的 givens 一样。然而，这极大地使语言复杂化了，所以我们在 cubiml 中暂时避开它。
为了教学目的，cubiml 保持简单，整型、浮点型和字符串在类型系统中作为原始类型来实现（就像已经对布尔型做的那样），而运算符是在编译器中处理的内在类型，而不是在库代码中。然而，这仍然留下了每个运算符应该接收和产生什么类型的问题。
运算符类型签名
最简单的要实现的类型是接收并产生单一、特定类型的运算符。例如，你可以有类型签名为 (int, int) -> bool 的整数比较运算符。同样，你可以有整数加法运算符 (int, int) -> int。因为这很容易实现，而且不需要在类型系统中添加任何新概念，所以在 cubiml 中我们将暂时采用这种方法。
有了特定类型的操作符，就必须为每个类型使用不同的操作符。例如，在许多流行的语言中，整数加法、浮点加法和字符串连接都使用 + 运算符。在 cubiml 中，我们遵循 OCaml 的方法，通过给浮点运算符添加一个句号来消除运算符的歧义。这意味着 + 保留给整数加法，而 +. 必须用于浮点加法(在OCaml中字符串连接是 ^)。这种方法显然只有在数字类型相对较少的情况下才行得通 - 如果你的语言有通常的大小不一、符号不一的固定宽度的整数，这种方法就完全行不通了，不过话说回来，我认为一开始有这些类型是个坏主意。
按照实现难度和复杂度递增的顺序，接下来是可以接收多个类型值的运算符，包括不同类型的值。例如，我们不需要类型为 (int, int) -> bool 的整数比较运算符 >，也不需要类型为 (float, float) -> bool 的浮点比较运算符 >.，我们可以用单一的比较运算符来让你自由比较整数和浮点数，类型为 (int | float, int | float) -> bool，其中 | 是类型联合。这只需要对类型检查器稍作修改就可以实现，但它需要修改类型检查器，并且增加了复杂性，所以我避免了它，暂时将比较运算符分开。
注意，这只适用于产生固定结果类型的运算符。理论上，你可以按照这种方法，用 (int | float, int | float) -> int | float 这样的类型来做一个通用的加法运算符，但这并没有任何意义，而且 int | float 的结果值几乎没有用。同时注意，类型签名 (int | float, int | float) -> bool 允许你比较整数和浮点数。如果你想限制运算符，使它只能比较整数和整数，以及浮点数和浮点数，那么类型签名将是 ((int, int) -> bool) & (((float, float) -> bool)，一个复杂得多的野兽。同样，假设的加法/连接组合 + 运算符将需要有类型签名 ((int, int) -> int) & (((float, float) -> float) & (((string, string) -> string)。这将我们带入特设多态。
特设多态
目前为止，我们所做的一切都基于参数多态。这种代码重用的方法包括找到一个接口（或者让编译器帮你计算），它代表了对函数输入的要求，然后编写函数代码只使用这个接口，使任何兼容该接口的类型可以代码重用。
多态的另一种形式，特设多态，指的是只能与特定列举的类型列表一起使用的代码。这是 C++ 和 Java 等语言中传统的方法重载的结果，例如，你可以定义一个接收整数的方法 foo，另外定义一个接收浮点数的 foo 方法，然后你可以在整数和浮点数上调用 foo，但不能是其他类型。不幸的是，特设多态除了从用户的角度来看是脆弱和不可维护的之外，还对类型推理造成了破坏。
特设多态可以表达几乎任意的约束，这与使全局类型推理起作用的所有事物背道而驰。相对于传播流边和类型并迭代直到收敛来为表达式找到单一的最通用类型，编译器必须要解决一个任意的约束系统，这通常是无法确定的。例如，我们之前看到，相等约束和子类型的结合使得类型推理在一般情况下是不可确定的，但这里讨论的特设多态的整个要点就是支持相等约束。
也就是说，我相信可以处理这种特殊情况，并将其塞进当前的类型检查器设计中。原因是这里不需要任意的相等约束，只需要基本类型的相等，这可以通过要求所有流向给定用法的值共享同一个类型构造器头来表达。(递归相等约束，它可以到达类型构造器内部来强制组件类型之间相等，这将使类型推理无法确定)。
然而，这样做是一个可怕的 hack，违背了系统设计之下的所有原则。事实上，它是如此的丑陋，以至于我将在这里继续概述它，而不是将它保存在未来的文章中，因为我没有任何计划在 cubiml 中实现它。诀窍是在图中添加一个使用头节点的新类型，其头是可变的。每当一个值头流向该使用头并调用 check_heads 时，我们就会将值类型构造器存储在使用头的可变存储中。然后，如果它与之前流向该头的任何类型构造器不同，我们可以抛出一个类型错误。
相等运算符
在 cubiml 中，相等运算符 == 和 != 可以用于任何类型的操作数，甚至是两种不同类型的操作数。与 <、+ 等不同的是，能够在对象、函数等上使用它们很有用。一些语言强制两个操作数必须具有相等类型的额外限制，但如上所述，这与子类型推理是不兼容的。此外，一开始这就是个可疑的决定，因为比较不相关类型的值仍然有意义（它们是不等的），如果你试图使类型系统更精确，过度热衷的限制会引起问题。例如，你可能想在类型系统中跟踪常量值，给整型常量一个特殊的类型，它是一般整型的子类型。然而，在这种情况下，你仍然希望能够将整型变量与常量进行比较!
实现
所有的理论都讲完了，是时候真正实现新的类型、字面量和操作符了。
增加基本类型
至于类型系统，唯一的变化是增加了三个新的基本类型：整型、浮点型和字符串。由于这些都是基本类型，所以实现方式与布尔型完全相同，所需的改变简单明了。
首先添加头构造器。
#[derive(Debug, Clone)]
enum VTypeHead {
VBool,
+ VFloat,
+ VInt,
+ VStr,
VFunc { arg: Use, ret: Value },
VObj { fields: HashMap<String, Value> },
VCase { case: (String, Value) },
#[derive(Debug, Clone)]
enum UTypeHead {
UBool,
+ UFloat,
+ UInt,
+ UStr,
UFunc { arg: Value, ret: Use },
UObj { field: (String, Use) },
UCase { cases: HashMap<String, Use> },
接下来，在 check_heads 函数中处理它们。
match (lhs, rhs) {
(&VBool, &UBool) => Ok(()),
+ (&VFloat, &UFloat) => Ok(()),
+ (&VInt, &UInt) => Ok(()),
+ (&VStr, &UStr) => Ok(()),
+
(&VFunc { arg: arg1, ret: ret1 }, &UFunc { arg: arg2, ret: ret2 }) => {
out.push((ret1, ret2));
// flip the order since arguments are contravariant
最后，添加公共构造器方法。
pub fn bool(&mut self) -> Value {
self.new_val(VTypeHead::VBool)
}
+ pub fn float(&mut self) -> Value {
+ self.new_val(VTypeHead::VFloat)
+ }
+ pub fn int(&mut self) -> Value {
+ self.new_val(VTypeHead::VInt)
+ }
+ pub fn str(&mut self) -> Value {
+ self.new_val(VTypeHead::VStr)
+ }
+
pub fn bool_use(&mut self) -> Use {
self.new_use(UTypeHead::UBool)
}
+ pub fn float_use(&mut self) -> Use {
+ self.new_use(UTypeHead::UFloat)
+ }
+ pub fn int_use(&mut self) -> Use {
+ self.new_use(UTypeHead::UInt)
+ }
+ pub fn str_use(&mut self) -> Use {
+ self.new_use(UTypeHead::UStr)
+ }
pub fn func(&mut self, arg: Use, ret: Value) -> Value {
self.new_val(VTypeHead::VFunc { arg, ret })
字面量
下一步是给语言添加字面量。首先将它们添加到 AST 中。
#[derive(Debug)]
pub enum Literal {
- Bool(bool),
+ Bool,
+ Float,
+ Int,
+ Str,
}
type VarDefinition = (String, Box<Expr>);
以前，我们解析布尔字面量，并将字面量值作为 bool 存储在 ast::Literal 枚举中。然而对于新的字面量类型，解析和序列化它们需要一堆复杂的逻辑，而实际上并不需要。由于类型检查器并不关心字面量值，所以我们只将字面量值表示为源代码的 String，并原封不动地传递给代码生成。这样做也避免了需要添加对大数库的依赖来表示整数字面量值。
If(Box<Expr>, Box<Expr>, Box<Expr>),
Let(VarDefinition, Box<Expr>),
LetRec(Vec<VarDefinition>, Box<Expr>),
- Literal(Literal),
+ Literal(Literal, String),
Match(Box<Expr>, Vec<(CaseMatchPattern, Box<Expr>)>),
Record(Vec<(String, Box<Expr>)>),
Variable(String),
由于现在无论类型如何所有的字面量值都以同样的方式表示（String），我们也将它们移到 ast::Literal 枚举之外，直接存储在 ast::Expr::Literal 变体中。很羞愧我没有在 cubiml 上进一步努力，这样就可以避免做出这样的让我看起来很愚蠢的以后不得不撤销的设计决定，但这就是软件工程师的生活。
语法
接下来，我们在解析器中添加字面量，这主要包括编写一堆巨大的正则表达式。这里与 OCaml 的字面量语法有一些小的不同 - 我们不允许额外的前导零，浮点字面量需要小数点，即使指定了指数（需要写成 1.e3 或 1.0e3 而不是 1e3）。
最后，我们将负数字面量的减号视为字面量本身的一部分，而不是像大多数语言那样，将一元减号应用于正数字面量。这极大地简化了代码，但代价是偶尔会导致对模糊语法的反直觉行为。例如，5-3 将被解析为无意义的功能调用 5 (-3) 而不是预期的 5 - 3 ，因为 -3 是一个有效的标识。这主要是使用函数式函数调用(func arg)的结果，其参数周围没有括号会给语法带来很多歧义和混乱，而对于更传统的语法来说，这基本上不是问题。
Ident: String = <r"[a-z_]\w*"> => String::from(<>);
Tag: String = <r"`[A-Z]\w*"> => String::from(<>);
+IntLiteral: String = <r"-?(?:0|[1-9][[:digit:]]*)"> => String::from(<>);
+FloatLiteral: String =
+ <r"-?(?:0|[1-9][[:digit:]]*)\.[[:digit:]]*(?:[eE]-?[[:digit:]]+)?"> => String::from(<>);
+StringLiteral: String =
+ <r#""[^\\"]*(?:\\[tn'"\\][^\\"]*)*""#> => String::from(<>);
VarOrLiteral: Box<ast::Expr> = {
Ident => Box::new(
match <>.as_str() {
- "true" => ast::Expr::Literal(ast::Literal::Bool(true)),
- "false" => ast::Expr::Literal(ast::Literal::Bool(false)),
+ "false" | "true" => ast::Expr::Literal(ast::Literal::Bool, <>),
_ => ast::Expr::Variable(<>)
}
),
+
+ FloatLiteral => Box::new(ast::Expr::Literal(ast::Literal::Float, <>)),
+ IntLiteral => Box::new(ast::Expr::Literal(ast::Literal::Int, <>)),
+ StringLiteral => Box::new(ast::Expr::Literal(ast::Literal::Str, <>)),
}
If: Box<ast::Expr> = {
前端
最后一步是在类型检查器前端中添加字面量支持。
check_expr(engine, bindings, rest_expr)
}),
- Literal(val) => {
+ Literal(type_, code) => {
use ast::Literal::*;
- Ok(match val {
- Bool(_) => engine.bool(),
+ Ok(match type_ {
+ Bool => engine.bool(),
+ Float => engine.float(),
+ Int => engine.int(),
+ Str => engine.str(),
})
}
Match(match_expr, cases) => {
运算符
现在我们在语言中拥有整型、浮点型和字符串字面量，但对它们没做操作。是时候添加一些运算符了。我们将为整型数学添加 +、-、* 和 / 运算符，为整型比较添加 <、<=、> 和 >=。对于浮点数，我们遵循 OCaml 的做法，使用不同的都以 . 为后缀（+.、*.、>=. 等）的运算符集。最后，是字符串连接运算符 ^ 和通用相等运算符 == 和 ！=。
像往常一样，第一步是扩展 AST。
Str,
}
+#[derive(Debug)]
+pub enum Op {
+ Add,
+ Sub,
+ Mult,
+ Div,
+
+ Lt,
+ Lte,
+ Gt,
+ Gte,
+
+ Eq,
+ Neq,
+}
+
+#[derive(Debug)]
+pub enum OpType {
+ IntOp,
+ FloatOp,
+ StrOp,
+
+ IntCmp,
+ FloatCmp,
+ AnyCmp,
+}
+
type VarDefinition = (String, Box<Expr>);
type CaseMatchPattern = (String, String);
#[derive(Debug)]
pub enum Expr {
+ BinOp(Box<Expr>, Box<Expr>, OpType, Op),
Call(Box<Expr>, Box<Expr>),
Case(String, Box<Expr>),
FieldAccess(Box<Expr>, String),
新的 BinOp AST 节点类型有两个额外的字段 - OpType 和 Op。OpType 提供了操作的类型签名，而 Op 则跟踪它是哪种操作，忽略类型。这样拆分很方便，因为类型检查器只需要前者，而代码生成只需要担心后者。
接下来，将新的操作符添加到语言语法中。
+MultOp: Box<ast::Expr> = {
+ <MultExpr> "*" <CallExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::IntOp, ast::Op::Mult)),
+ <MultExpr> "/" <CallExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::IntOp, ast::Op::Div)),
+ <MultExpr> "*." <CallExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::FloatOp, ast::Op::Mult)),
+ <MultExpr> "/." <CallExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::FloatOp, ast::Op::Div)),
+}
+AddOp: Box<ast::Expr> = {
+ <AddExpr> "+" <MultExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::IntOp, ast::Op::Add)),
+ <AddExpr> "-" <MultExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::IntOp, ast::Op::Sub)),
+ <AddExpr> "+." <MultExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::FloatOp, ast::Op::Add)),
+ <AddExpr> "-." <MultExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::FloatOp, ast::Op::Sub)),
+ <AddExpr> "^" <MultExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::StrOp, ast::Op::Add)),
+}
+CmpOp: Box<ast::Expr> = {
+ <AddExpr> "<" <AddExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::IntCmp, ast::Op::Lt)),
+ <AddExpr> "<=" <AddExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::IntCmp, ast::Op::Lte)),
+ <AddExpr> ">" <AddExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::IntCmp, ast::Op::Gt)),
+ <AddExpr> ">=" <AddExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::IntCmp, ast::Op::Gte)),
+
+ <AddExpr> "<." <AddExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::FloatCmp, ast::Op::Lt)),
+ <AddExpr> "<=." <AddExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::FloatCmp, ast::Op::Lte)),
+ <AddExpr> ">." <AddExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::FloatCmp, ast::Op::Gt)),
+ <AddExpr> ">=." <AddExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::FloatCmp, ast::Op::Gte)),
+
+ <AddExpr> "==" <AddExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::AnyCmp, ast::Op::Eq)),
+ <AddExpr> "!=" <AddExpr> => Box::new(ast::Expr::BinOp(<>, ast::OpType::AnyCmp, ast::Op::Neq)),
+}
运算符分为三个部分 - 乘法、加法和比较运算符。这使得我们可以将正确的优先规则编码到语法中。传统上，相等运算符的优先级低于关系运算符（<，>=. 等），但 OCaml 给予它们同样的优先级，所以我决定也这样做，以节省时间并简化语法。
然而，通过使比较运算符不具有关联性，我们确实偏离了大多数语言的实践。(请注意，上面 CmpOp 规则的两个操作数都是 AddOp，这意味着不可能比较比较的结果)。在 JavaScript 和 OCaml 等语言中，a < b < c 是有效的语法，它被解析为 (a < b) < c，但这样的代码是无意义的，所以在 cubiml 中是不允许的。
CaseExpr,
Call,
}
-Expr = {
+MultExpr = {
CallExpr,
+ MultOp,
+}
+AddExpr = {
+ MultExpr,
+ AddOp,
+}
+CompareExpr = {
+ AddExpr,
+ CmpOp,
+}
+Expr = {
+ CompareExpr,
FuncDef,
If,
Let,
最后，需要在类型检查器前端添加对 BinOp 节点的支持。这也是很简单直接的。
BinOp(lhs_expr, rhs_expr, op_type, op) => {
use ast::OpType::*;
let lhs_type = check_expr(engine, bindings, lhs_expr)?;
let rhs_type = check_expr(engine, bindings, rhs_expr)?;
Ok(match op_type {
IntOp => {
let bound = engine.int_use();
engine.flow(lhs_type, bound)?;
engine.flow(rhs_type, bound)?;
engine.int()
}
FloatOp => {
let bound = engine.float_use();
engine.flow(lhs_type, bound)?;
engine.flow(rhs_type, bound)?;
engine.float()
}
StrOp => {
let bound = engine.str_use();
engine.flow(lhs_type, bound)?;
engine.flow(rhs_type, bound)?;
engine.str()
}
IntCmp => {
let bound = engine.int_use();
engine.flow(lhs_type, bound)?;
engine.flow(rhs_type, bound)?;
engine.bool()
}
FloatCmp => {
let bound = engine.float_use();
engine.flow(lhs_type, bound)?;
engine.flow(rhs_type, bound)?;
engine.bool()
}
AnyCmp => engine.bool(),
})
}
演示
现在我们已经在 cubiml 中加入了数字和基本数学，这门语言更加有用了。我们终于可以尝试像第一篇文章中的斐波那契例子那样的东西了。
演示中有一个常规的编辑器窗格以及一个 REPL 提示。你可以在左边的窗口中输入你的代码，然后点击 Compile and run，也可以在右边输入代码并按回车键。注意 Compile and run 也会清除 repl 的历史记录。如果出现问题，需要完全重置演示，只需刷新页面。
错误消息
到目前为止，我们还没有担心过编译器的错误信息。目前，编译器的错误信息通常都是无用的，只是在发生类型错误时说“意外类型”。下周，我们将看到如何实现更好的错误信息。