ML编译器Caml Featherweight——设计

编译器的设计

编译器的设计和实现大量参考了 @Zinc。

执行方法

编译器的执行方法大致分成四类：

  1. 解释执行语法树。容易实现，解析得到语法树后再做较少的工作即可实现。运行时解释执行，但性能很低。
  2. 生成本地代码，处理器可以直接执行。优点是性能较高。
  3. 生成在抽象机器上执行的字节码。类似于本地代码，但生成的代码基于一个抽象机器。优点是移植性强，只需把运行时系统移植到目标架构上即可。
  4. 翻译到其他高级语言。和生成抽象机器的字节码类似，但前者过于低级，实现很多结构需要大量指令。编译到一门高级语言在很多地方上能得到简化。

语法树设计和类型信息表示

表达式

我们需要一个表示表达式的类型，为了提供更具体的解析错误信息，需要把位置信息放在附在节点信息里。表示位置信息有两种方法，一种是在所有构造器里设置一个域表示：

1
2
3
4
type expression =
  | Pexpr_apply of location * expression * expression list
  | Pexpr_array of location * expression list
  | ...

这样在所有模式匹配的地方都要匹配位置域，很不方便。如果把构造器都改成record类型的话，模式匹配也会不方便。

比较好的方式是拆分为两个类型：

1
2
3
4
type expression = { e_desc: expression_desc; e_loc: location }
and expression_desc =
  | Pexpr_apply of expression * expression list
  | Pexpr_array of expression list

如果前端工作复杂的话，那么expression还可以考虑设计成参数化的。但在我们的实现中只需要使用到一种语法树表示，没必要使用参数化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type expression = { e_desc: expression_desc; e_loc: location }
and expression_desc =
  | Pexpr_apply of expression * expression list
  | Pexpr_array of expression list
  | Pexpr_constant of constant
  | Pexpr_constraint of expression * type_expression
  | Pexpr_constr of long_ident * expression option
  | Pexpr_for of string * expression * expression * bool * expression
  | Pexpr_function of (pattern * expression) list
  | Pexpr_ident of long_ident
  | Pexpr_if of expression * expression * expression option
  | Pexpr_let of bool * (pattern * expression) list * expression
  | Pexpr_sequence of expression * expression
  | Pexpr_try of expression * (pattern * expression) list
  | Pexpr_tuple of expression list

模式匹配

模式匹配和表达式共享了一些语法单元，比如字面量、元组、构造器、变量等，但其中不允许出现for、;等，和表达式还是有一些差别，因此需要为它定义一个类型pattern。

pattern是个和expression平级的概念，同样出于错误信息的考量，添加位置信息并拆分为两个类型：

1
2
3
4
5
6
7
8
9
10
11
and pattern = { p_desc: pattern_desc; p_loc: location }
and pattern_desc =
  | Ppat_alias of pattern * string
  | Ppat_any
  | Ppat_array of pattern list
  | Ppat_constant of constant
  | Ppat_constraint of pattern * type_expression
  | Ppat_constr of long_ident * pattern option
  | Ppat_or of pattern * pattern
  | Ppat_tuple of pattern list
  | Ppat_var of string

类型表达式

expression和pattern中允许出现类型限定(如int、’a list)，为此需要一个type_expression类型表示，这也是一个和expression平级的概念。

1
2
3
4
5
6
and type_expression = { te_desc: type_expression_desc; te_loc: location }
and type_expression_desc =
  | Ptype_var of string
  | Ptype_arrow of type_expression * type_expression
  | Ptype_tuple of type_expression list
  | Ptype_constr of long_ident * type_expression list

Type constructor、具体类型

解析阶段以外用到的、类型相关 由于Caml支持参数化类型，因此如何表示类型、构造器等的描述变得很复杂。

考虑如何统一表示无参数的类型(如int、string)和参数化类型(如’a option)，它们都是由type constructor(int、string、option)接受零或多个参数得到的，type constructor可以看作是一个独一无二的标识符，我们用type_constr表示。

具体的类型用typ表示，可以由type constructor应用到参数上得到(Tconstr)，也可以通过product类型或arrow类型等方式得到，也可以是一个generic类型(Tvar，typ_level为-1)或者是一个尚未确定的类型(Tvar，level非-1)。

另外Caml支持type abbreviation，type constructor可能指向另一个具体类型。

综合上述考量得到下面的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
type typ = { typ_desc: typ_desc; mutable typ_level: int }
and typ_desc =
  | Tarrow of typ * typ
  | Tconstr of type_constr global * typ list
  | Tproduct of typ list
  | Tvar of typ_link ref
and typ_link =
  | Tnolink
  | Tlink of typ
and type_constr = { ty_stamp: int; mutable ty_abbr: type_abbrev }
and type_abbrev =
  | Tnotabbrev
  | Tabbrev of typ list * typ

类型描述和构造器描述

对于类似type t = A这样的类型定义，以及一些内置类型(如float)等，用type_desc表示，并存储在一个全局的表里，供编译的后续阶段引用。参数化类型允许参数为任意类型，因此type_desc中只需要记录参数个数(ty_arity)。等号右边的描述则用type_components类型表示，可以是abstract type、variant type或是type abbreviation。

与type_desc关联的是构造器描述constr_desc，表达式或模式匹配中出现构造器时会用到这个类型，它需要的域是所表示的具体类型(typ)，是否接受参数(cs_kind: constr_kind)及接受的参数的类型(of后面的)等。另外需要一个域cs_tag: constr_tag用于区分同一个具体类型的不同构造器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type type_desc =
  { ty_constr: type_constr global; ty_arity: int; mutable ty_desc: type_components }
and type_components =
  | Abstract_type
  | Variant_type of constr_desc global list
  | Abbrev_type of typ list * typ

and constr_desc =
  { cs_arg: typ; cs_res: typ; cs_tag: constr_tag; cs_kind: constr_kind }

and constr_kind =
  | Constr_constant
  | Constr_regular
  | Constr_superfluous of int

其中constr_tag描述构造器的类型。考虑模式匹配的代码生成场景，我们需要一种办法能区分同一个类型的不同构造器。如果构造器是closed type的，那么区分不同的构造器只需要一个信息，即构造器的标号，同一个类型的不同构造器标号互不相同。为了代码生成方便，构造器的数目也编码到标号中，可以用一个元组int * int来表示标号。

为了一致性，exception类型也应看作构造器，而exception类型是开放的，即构造器可以定义在不同地方，数目不受限制，可以实现为一种extensible type，这些类型用标识符表示。

1
2
3
type constr_tag =
  | Constr_tag_regular of int * int
  | Constr_tag_extensible of long_ident * int

词法分析

词法分析

使用工具ocamllex。这一部分实现在lexer.mll中。

Caml支持自定义操作符，它们的优先级由第一个字符决定，优先级会对语法分析产生影响，因此把优先级不同的操作符表示为不同的词素。

Caml Light没有对大写和小写开头的标识符进行区分，但参阅OCaml源码可以看到区分后语法分析会更加容易。因此我们的项目中也按大小写进行区分。

还有一些需要注意的地方是字符串、字符、注释等的解析，需要考虑转义字符等问题，但都不是难点。

语法分析

这一部分实现在parser.mly中。使用工具ocamlyacc或menhir。我还不知道如何使用这两个工具产生友好的错误信息。

多数yacc实现都采用了操作符优先级来解决移入/规约冲突，http://caml.inria.fr/pub/docs/manual-ocaml-4.00/manual026.html描述了这一解决过程。在实现中我们碰到一些典型问题并得以解决。

解析逗号分割的列表

考虑表示表达式的非终结符expr，它的其中两个产生式是逗号分割的表达式和分号分割的表达式，约定逗号(COMMA)优先级高于分号(SEMI)，可以如下实现：

expr:
  | ...
  | expr_comma_list %prec below_COMMA { Pexpr_tuple($1) }
  | expr SEMI expr { Pexpr_seq($1,$3) }
  | ...

expr_comma_list:
  | expr COMMA expr_comma_list { $1 :: $3 }
  | expr COMMA expr { [$1; $3] }

其中%prec below_COMMA是指定第一条产生式的优先级，从而在栈为expr_comma_list且向前看符号为COMMA时，menhir选择移入而不是规约expr_comma_list -> expr。

但这种语法描述还有一个问题。当栈内当前为expr COMMA expr_comma_list且向前看符号为SEMI时，规约expr_comma_list -> expr和规约expr COMMA expr_comma_list -> expr的优先级均大于SEMI，均为有效的规约，无法确定选取哪一个，产生规约/规约冲突。

解决方案是把左递归改写为右递归：

expr_comma_list:
  | expr_comma_list COMMA expr { $3 :: $1 }
  | expr COMMA expr { [$3; $1] }

在使用expr_comma_list时要注意反转列表。考虑到函数式语言中在列表头部添加元素比较容易，描述文法时通常用左递归而非右递归，但在上述情形下就不得已采用右递归。OCaml的语法解析更为复杂，在parsing/parser.mly中也能看到一些这样的例子。

解析标识符，区分构造器和变量

Caml Light的语法分析文件中把实现文件划分为用双分号分割的多个phrase，解析完一个phrase后立即进行类型检查、代码生成等工作，并导入全局的值、类型、构造器信息。在解析模式匹配的地方遇到一个标识符时，通过查询之前是否定义过该标识符的构造器来区分该标识符是构造器还是变量。Caml Light把部分变量是否定义的工作糅合到了解析阶段。

我们希望能完整解析源文件后再进行变量定义判断的工作，因此借鉴了OCaml的解析器实现，区分大小写两种标识符，大写视为构造器，小写视为变量。

在这里也能一窥语言实现的考量，了解为什么很多支持模式匹配的语言规定构造器使用大写、变量使用小写。

这里也能看到为了语言的一致性，false和true应该看作构造器，使用大写，实现中如果要摈弃Caml Light中解析阶段判断是否定义的做法，比较好的方式是在词法分析中把false和true也作为词法单元。

可省略的双分号

Caml Light中要求每一个phrase(表达式、let定义、type定义或exception定义)后面必须跟双分号，而OCaml中，非表达式phrase前的双分号是可省略的。

方法是区分表达式开始的实现和非表达式开始的实现。我们用用一个非终结符structure_item表示单个非表达式phrase。

实现文件有三种可能：

  • 只包含一个表达式phrase。
  • 以表达式phrase开头，之后接双分号。
  • 以非表达式phrase开头(用structure_tail表示)

structure_tail可以看作是实现和表达式开头的实现的差集，有几种可能：

  • 空或仅包含双分号
  • SEMISEMI seq_expr structure_tail
  • SEMISEMI structure_item structure_tail
  • structure_item structure_tail，这种情况对应了省略双分号的情形
implementation:
  | structure EOF { $1 }

structure:
  | structure_tail { $1 }
  | seq_expr { [make_impl(Pimpl_expr $1)] }
  | seq_expr SEMISEMI structure_tail { make_impl(Pimpl_expr $1)::$3 }

structure_tail:
  | /* emtpy */ { [] }
  | SEMISEMI { [] }
  | SEMISEMI seq_expr structure_tail { make_impl(Pimpl_expr $2)::$3 }
  | SEMISEMI structure_item structure_tail { $2::$3 }
  | structure_item structure_tail { $1::$2 }

structure_item:
  | TYPE type_decl_list { make_impl(Pimpl_typedef $2) }
  | LET rec_flag let_binding_list { make_impl(Pimpl_letdef($2, $3)) }
  | EXCEPTION constr_decl { make_impl(Pimpl_excdef $2) }
Caml Light语法分析的一些缺陷

Caml Light的语法分析文件还存在其他一些缺陷，包括符号优先级定义比较混乱，很多地方应该用%nonassoc而不是%left或%right等。

数据表示

First-class function的实现

支持first-class function需要支持把函数作为值传递，可以存储在变量中、用作返回值，支持内嵌的函数。内嵌函数作为值传递时，它仍可以访问上层函数的局部变量，因此如果作为传递到外界，需要提供一种方式访问那些变量。

一种方式是闭包，把需要访问的变量和函数代码一起存储。函数代码可以用指向待执行指令的指针表示，而内嵌函数需要访问的上层函数的局部变量就需要保存在一个数据结构里，称为环境。@Compiling中提到了一些闭包实现策略的考量。函数应用时没有访问环境，只有构建闭包的代码和访问相应变量的代码需要。在选择环境的表示上我们有相当的自由度。

另一种方式是lambda lifting，可以实现first-class function的部分特性。

编译流程概览

  • 解析源代码得到抽象语法树
  • 类型推导得到带类型的语法树
  • 翻译成使用de Bruijn index的扩充-calculus。原始的无类型-calculus中唯一的值类型是抽象，该扩充-calculus提供了let、原语操作(如加法、比较、创建数组、创建boxed data等)。这一部分还包括一个编译模式匹配的子系统。
  • 把扩充-calculus翻译到Zinc抽象机器
  • 运行时系统解释执行Zinc抽象机器字节码