在上周的文章中，我们讨论了一种新的类型推理方法，称为立方双合一 ，并介绍了 cubiml，这是一种用 Rust 编写的类 ML 的简单语言，它演示了立方双合一。本周，我们将介绍实现 cubiml 的第一步，以及对双合一的高层次概述。

解析

编译器的第一步是解析输入的源代码，并将其从纯文本转换为抽象语法树（AST）。我强烈建议使用解析器生成器来完成这一步。解析器生成器是一种工具，它可以接收语言语法的声明性的、高层次的描述，并自动生成代码来解析它。

一些流行的编程语言则使用手写的解析器，它允许对诸如编译器错误信息之类的东西进行更精细的控制，但代价是大大增加了维护负担。然而，如果你正在研究一种业余编程语言，你的时间是很宝贵的，所以尽可能提高可维护性是很重要的。如果你的语言获得了成功，你可以忧心以后写一个自定义的解析器，由你的崇拜者军团的志愿者努力相助。

此外，使用解析器生成器可以让你很容易地对语言语法的变化进行试验，这对于新生的编程语言来说是极其重要的，而对于真正有用户的语言来说，基本上是无关紧要的。有了解析器生成器，对语言语法的改变几乎就像简单地描述这种改变一样简单，因为生成器为你做了所有繁重的工作。

在 cubiml 的例子中，我使用的是解析器生成器 LALRPOP，它以下面这样的格式接收语言语法的描述。

use super::ast; // super 而不是 self，因为 lalrpop 将其封装在一个内部模块中。


grammar;

Ident: String = <r"[a-z_]\w*"> => String::from(<>);
Tag: String = <r"`[A-Z]\w*"> => String::from(<>);

// 确保 __proto__ 不被视为有效的标识符。
Illegal = "__proto__";

SepList<T, Sep>: Vec<T> = {
    <v:(<T> Sep)*> <e:T> => {
        let mut v = v;
        v.push(e);
        v
    }
};
SepListOpt<T, Sep>: Vec<T> = {
    SepList<T, Sep>,
    => Vec::new(),
};

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)),
            _ => ast::Expr::Variable(<>)
        }
    ),
}

If: Box<ast::Expr> = {
    "if" <Expr> "then" <Expr> "else" <Expr> => Box::new(ast::Expr::If(<>)),
}

FuncDef: Box<ast::Expr> = {
    "fun" <Ident> "->" <Expr> => Box::new(ast::Expr::FuncDef(<>)),
}
Call: Box<ast::Expr> = {
    CallExpr CaseExpr => Box::new(ast::Expr::Call(<>)),
}


KeyPairExpr = {
    <Ident> "=" <Expr>,
}
Record: Box<ast::Expr> = {
    "{" <SepListOpt<KeyPairExpr, ";">> "}" => Box::new(ast::Expr::Record(<>)),
}
FieldAccess: Box<ast::Expr> = {
    <SimpleExpr> "." <Ident> => Box::new(ast::Expr::FieldAccess(<>)),
}

Case: Box<ast::Expr> = {
    <Tag> <CaseExpr> => Box::new(ast::Expr::Case(<>)),
}

CaseMatchPattern = {
    Tag Ident,
}
MatchArm = {
    <CaseMatchPattern> "->" <CallExpr>,
}
Match: Box<ast::Expr> = {
    "match" <Expr> "with" <SepList<MatchArm, "|">> => Box::new(ast::Expr::Match(<>)),
}

LetLHS = {
    "let" <Ident> "=" <Expr>,
}
LetRHS = {
    "in" <Expr>,
}
Let: Box<ast::Expr> = {
    <LetLHS> <LetRHS> => Box::new(ast::Expr::Let(<>)),
}


LetRecDef = {
    <Ident> "=" <FuncDef>,
}
LetRecLHS = {
    "let" "rec" <SepList<LetRecDef, "and">>,
}
LetRec: Box<ast::Expr> = {
     <LetRecLHS> <LetRHS> => Box::new(ast::Expr::LetRec(<>)),
}


SimpleExpr = {
    FieldAccess,
    Record,
    VarOrLiteral,
    "(" <Expr> ")",
}
CaseExpr = {
    SimpleExpr,
    Case,
}
CallExpr = {
    CaseExpr,
    Call,
}
Expr = {
    CallExpr,
    FuncDef,
    If,
    Let,
    LetRec,
    Match,
}

TopLevelItem: ast::TopLevel = {
    <LetLHS> => ast::TopLevel::LetDef(<>),
    <LetRecLHS> => ast::TopLevel::LetRecDef(<>),
    <Expr> => ast::TopLevel::Expr(*<>),
}

pub Script = {
   <SepList<TopLevelItem, ";">>
}

解析器的输出是一棵抽象语法树，一棵由代表了输入源代码中的表达式和其他一些语法的节点组成的树。由于 Rust 是静态类型的，我们必须为 AST 定义类型。

首先，我们有一个字面量类型。enum 是 Rust 的 sum 类型的形式。一个 enum 类型声明给出了一个命名变体的列表，以及与每个变体相关的数据。在本例中，我们只有一种类型的字面量 - 布尔，但稍后会添加更多类型。标签是 Bool ，相关的数据只是一个 bool 值，给出了解析后的字面量值。

#[derive(Debug)]
pub enum Literal {
    Bool(bool),
}

AST 的主要类型是 Expr，代表 cubiml 表达式。它有函数调用、case 对象、字段访问、函数定义等变体。

type VarDefinition = (String, Box<Expr>);
type CaseMatchPattern = (String, String);

#[derive(Debug)]
pub enum Expr {
    Call(Box<Expr>, Box<Expr>),
    Case(String, Box<Expr>),
    FieldAccess(Box<Expr>, String),
    FuncDef(String, Box<Expr>),
    If(Box<Expr>, Box<Expr>, Box<Expr>),
    Let(VarDefinition, Box<Expr>),
    LetRec(Vec<VarDefinition>, Box<Expr>),
    Literal(Literal),
    Match(Box<Expr>, Vec<(CaseMatchPattern, Box<Expr>)>),
    Record(Vec<(String, Box<Expr>)>),
    Variable(String),
}

由于表达式可以递归地包含其他表达式，我们必须将它们装箱。在 Rust 中，默认情况下，所有的东西都是按值包含在结构或枚举中的（而不是像 Java、Python 等那样按指针包含），所以一个递归地包含自己类型值的结构或枚举必须是无限大的，因此编译器不允许这样做。为了打破这种循环，我们到处使用 Box<Expr>，它是一个指向堆分配的 Expr 的指针。

Cubiml 在编写过程中，强调简单性和代码的清晰性，而不是性能。例如，AST 中的每一个节点都会导致一个单独的分配。在实践中，Rust 项目很可能会考虑在竞技场中分配树节点以提高效率，但这样做会给代码增加噪音和混乱，有损于解释如何实现类型推理的目标。同样，cubiml 使用 String，一个指向堆上单独分配的字符串的指针，来引用源代码中的标识符和标记，而不是像典型的 Rust 项目那样，简单地将指针存储到输入源代码缓冲区中。

最后，我们有一个 AST 节点类型用于顶层定义。这可以是普通的表达式，或者是 let 或 let rec 的定义，它没有右手边（in <expr> 部分）。

#[derive(Debug)]
pub enum TopLevel {
    Expr(Expr),
    LetDef(VarDefinition),
    LetRecDef(Vec<VarDefinition>),
}

类型检查器核心接口

现在我们有了 AST，下一步就是对它进行类型检查。在 cubiml 中，类型检查器分为前端和核心。前端处理语言的语法特定细节，将每个表达式转换为内部类型，并向类型检查器核心发出调用。然后核心会处理这些调用，如果有不一致的地方就返回类型错误。

我们稍后将介绍类型检查器核心的实现，现在，你只需要知道前端将调用的接口。它看起来像这样：

pub struct Value;
pub struct Use;

impl TypeCheckerCore {
    pub fn var(&mut self) -> (Value, Use);

    pub fn bool(&mut self) -> Value;
    pub fn bool_use(&mut self) -> Use;

    pub fn func(&mut self, arg: Use, ret: Value) -> Value;
    pub fn func_use(&mut self, arg: Value, ret: Use) -> Use;

    pub fn obj(&mut self, fields: Vec<(String, Value)>) -> Value;
    pub fn obj_use(&mut self, field: (String, Use)) -> Use;

    pub fn case(&mut self, case: (String, Value)) -> Value;
    pub fn case_use(&mut self, cases: Vec<(String, Use)>) -> Use;

    pub fn flow(&mut self, lhs: Value, rhs: Use) -> Result<(), TypeError>;
}

这需要一点解释。在 cubiml 中，类型有两种不同的种类 - Value 和 Use。前者是针对程序值的类型，后者是针对值使用的类型，也就是给定表达式对其操作数的约束。

双合一

传统的 Hindley-Milner 类型推理是基于合一，即连续迫使两个未知类型相等的过程，直到遇到矛盾或满足所有程序约束。子类型推理历来具有很大的挑战性，其中一个原因是半合一定理，该定理非常宽泛地指出，求解一个任意的相等和子类型约束系统是无法确定的。在代数子类型中，Dolan 介绍了一个过程，他称之为双合一，同样是非常宽泛地讲，通过只有子类型约束而不允许有相等约束，解决了不可确定性问题。

然而这本身并不足以使类型推理变得可决断，因为你可以用一对子类型约束 a <= b 和 b <= a 来模拟相等约束 a = b。双合一的另一个关键部分是极化类型系统。极化的意思是将类型分为两种，传统上称为正型和负型，但我在这里将其称为值和用，以便于理解。为了避免使半合一无法确定的无限循环，双合一限制所有子类型约束的形式为 v <= u，其中 v 是值类型，u 是使用类型。这些约束可以自然地解释为要求程序值与其使用方式兼容。

类型变量

本系统下类型检查的基本原理相当简单。为每个表达式创建一个值类型，为每个表达式操作数创建一个使用类型，并在每个值类型和每个使用它的上下文之间创建一个子类型约束，以确保一致性。我们把这些约束条件 v <= u 称为值跟随其用法，它们是用 TypeCheckerCore 上的 flow 方法创建的。

然而，系统中还有一个小问题 - 变量。在双合一下，变量是由一对类型来表示的 - 一个值类型和一个使用类型。这就是为什么上面的 TypeCheckerCore 的 var 方法返回的是一对 (Value，Use)。从概念上讲，值类型代表了从变量中读取的类型，而使用类型代表了分配给该变量的类型。自然地，我们需要约束 u <= v，即对变量的每一次写入都与从该变量的每一次读取兼容。然而，这种类型的约束是不允许的，因为当它与 v <= u 约束结合在一起时，可能会在类型检查器中产生无限循环。

解决的办法是，我们不直接表示这种约束，而只是确保跟随关系的传递性。对于每个变量 (v1，u1)，以及每个跟随 u1 的值类型 v2 和每个 v1 跟随的使用类型 u2，我们都添加 v2 跟随 u2 的约束。本质上，变量的行为就像类型图中的小隧道或虫洞。无论从一端进入的是什么，都会从另一端出来。

理论讲完了，类型检查器前端的实际实现就相当简单了。然而，仍然有相当多的代码需要处理，所以我将在下周的文章中介绍。

旁白：类型打印和简化

眼尖的人可能已经注意到，上面的类型检查器核心接口没有任何打印或显示类型的方法。它只是返回一个 TypeError 或者在成功时不返回任何内容。这是故意的。虽然可以修改系统来打印出类型，但我认为除了调试类型检查器之外，这并没有什么用。

在显式类型系统中，由于人类要不断地写类型，所以类型很短，也很好记，因此自然会以某种方式保持短小（尽管有 C++ 模板爆炸的问题）。然而，在大规模类型推理的情况下，类型反而是自动生成的保证程序一致性所需的信息摘要，没有选择压力来保持类型描述的简洁，因此往往非常大，不适合人类使用。从某种意义上说，推断的类型是检测程序中 bug 的过程中的副产品，而不是产品。这意味着，一般来说，显式显示推断类型是没用的。

现有的类型推导语言如 Haskell 和 OCaml 已经在一定程度上存在这个问题，但由于现实世界的代码往往会大量使用显式类型注释，这个问题得到了缓解。此外，传统的基于合一的推理往往会导致更小的推断类型，因为类型变量被人为地限制为等值，因此可以被识别和简化。然而，在使用子类型化时，推断的类型更加通用，因此要大得多，也更难理解。

自然而然地，我们会尝试简化类型，或者将它们转换为更小的等价表示，既是为了使它们在打印出来时更容易阅读，也是为了在类型检查器的正常操作中减少被操作类型的大小，从而提高性能。然而，在这样做的时候，你必须非常小心，让简化过程不比类型检查本身慢！使用 O(n^4) 简化算法来加速 O(n^3) 类型推理算法是没有意义的。

特别是，代数子类型化中描述的主要简化算法实际上具有指数级的最坏情况复杂度，病态情况经常出现在实践中，也出现在理论上。事实上，cubiml 比代数子类型化快的原因之一就是不做任何简化。

简化无法改善立方双合一的最坏情况复杂度，因为病理情况无论如何也无法简化。但是，现实世界代码往往包含很多重复的代码构造，这些构造很容易被简化掉，所以简化有可能提高现实世界代码的类型检查性能。想出既快速又实用的简化过程是一个挑战，但我认为这是个值得探索的途径。

不管怎么说，这个题外话/引子说完了，是时候继续教程了。在下一篇中，我们将介绍 cubiml 的类型检查器前端的实现。