ML编译器Caml Featherweight——概览

索引

代码

编译器的设计和实现大量参考了 @Zinc 和Caml Light 0.75，因此取名Caml Featherweight了……实现方面更接近于 @Zinc ，Caml Light有些晦涩复杂的地方我换成自己乱想的实现了。

tl;dr的话可以直接读源码：https://github.com/MaskRay/CamlFeatherweight

完成度

介绍

ML是个一门通用的函数式编程语言，有如下一些特点：

  • 采用call-by-value的求值策略，允许副作用和imperative programming。
  • 使用垃圾收集。
  • 支持first-class function，函数可以像int、string那样的值一样自由传递、创建。
  • 实现了静态类型检查，并能自动推导类型，无需C中的类型注解。
  • 提供了immutable programming的良好支持。
  • 参数多态，提供了一些通用编程支持，类似于Java中的generic。
  • 支持代数数据类型和模式匹配以处理复杂的数据结构。

本项目是@Zinc 提到的Zinc实验的一个实现，并大量参考了Caml Light 0.75的源码，实现了ML方言Caml的一个变体，以上提到的特性均已使用，在某些细节语法方面有省略和改动。

项目采用的Caml语言变体

内置类型

基本类型：

  • bool，如true、false
  • char，如’a’、’\n’
  • int，如12、0x0e
  • float，如3.0、2e-5
  • string，如hello、world

语言内置了一些类型构造器。

  • ’a option，如None、Some (4,true,7,’a’)

操作符

  • =，类型为’a -> ’a -> bool
  • <>，类型为’a -> ’a -> bool
  • ==，类型为’a -> ’a -> bool
  • !=，类型为’a -> ’a -> bool
  • <，类型为’a -> ’a -> bool
  • <=，类型为’a -> ’a -> bool
  • >，类型为’a -> ’a -> bool
  • >=，类型为’a -> ’a -> bool

int类型支持的额外操作符：+,-,*,/,mod，分别表示加、减、乘、除、和模运算，类型均为int -> int -> int。 float类型支持的额外操作符：+.,-.,*.,/.，即加减乘除，类型均为float -> float -> float。

元组

元组是几种类型的复合，可以看成几种不同类型的有序集合。元组的各个成分用逗号分割，外面套圆括号，比如：

1
2
# let a_tuple = (3,"three");;
val a_tuple : int * string

某些地方可以省略圆括号。

可以用模式匹配抽取元组的各个成分：

1
2
3
# let (x,y) = a_tuple;;
val x : int
val y : string

列表

元组可以把固定数目的不同元组聚合在一起，列表则可以表示相同类型的任意数目元素，语言提供的表示列表字面量的语法，如表示空列表的[]，带有两个元素的列表[3; 4]。

列表可以看成是一个单链表，单个节点可以为空([])，或者包含一个元素和一个指向后继节点(对应的构造器为::，比如：3::[])。::构造器是一个操作符，是右结合的，之前提到的[3; 4]可以看作3::4::[]的语法糖。

数组

数组类似于列表，可以表示相同类型的任意数目元素，并提供了随机访问的功能：

1
2
let a = [|3; 4; 7|]
let b = [|"a",('c',false); "b",('d',true)|]

访问数组中的一个元素：

1
a.(3)

修改数组中的一个元素：

1
a.(3) <- 'a'

option

option代表可能缺失的值，比如：

1
2
3
let divide x y =
  if y = 0 then None
  else Some(x/y)

函数

接受一个参数，返回参数加一的函数如下：

1
let plus_one x = x + 1

和类C语言不同，函数名和参数间用空格分割，并且函数体前使用=，因为ML中没有像C那样区分语句和表达式。

如果要定义多参数的函数，参数间也用空格分割：

1
let sum_of_three x y z = x + y + z

函数允许自递归，这时需要使用let rec：

1
2
3
4
5
let rec fib n =
  if n < 2 then
    n
  else
    fib (n-1) + fib (n-2)

如果要定义互递归的函数，必须在一个let rec中同时定义各个函数，它们之间用and分割：

1
2
3
4
let rec is_even x =
  if x = 0 then true else is_odd (x-1)
and is_odd x =
  if x = 0 then false else is_even (x-1)

代数数据类型和模式匹配

1
2
type t = Zero | One of int | Two of char * int
type tt = A of t

上面定义了一个类型t，它有三个构造器：Zero、One和Two，接受不同的参数。

模式匹配和代数数据类型配套使用，可以抽取构造器的参数：

1
2
3
4
5
6
match a with
| A t ->
    match t with
    | Zero -> 0
    | One i -> i
    | Two(ch,i) -> i

模式匹配也可用于int、string等基本类型。_是通配符，可以匹配任意值：

1
2
3
match s with
| "hello" -> true
| _ -> false

模式匹配也可用于复杂的类型，各分支中以以小写字母开头的表示符表示变量，可以匹配任意值，从而可以在->后的表达式中引用：

1
2
3
4
match s, 'a', 3+2 with
| "a", 'a', v -> "a"
| g, h, 5 -> g
| _ -> "b"

异常

异常提供了一种中断当前的计算，报告错误，捕获错误的机制。

除数为零时会触发Division_by_zero异常，下面的程序捕获了该异常并输出12：

1
2
3
4
try
  output_int (1/0)
with Division_by_zero ->
  output_int 12

如果模式匹配失败，则会产生Match_failure异常：

1
2
3
4
5
output_int (try
  let Some 3 = None in
  1
with Match_failure _ ->
  0)

try实质上形成了一个动态作用域，如果最近的try无法捕获的话，异常会交给外层的try：

1
2
3
4
5
6
7
8
output_int (try
  try
    let Some 3 = None in
    1
  with Division_by_zero ->
    0
with Match_failure _ ->
  2)

工具链使用说明

在项目目录下执行make生成字节码编译器camlfwc、字节码解释器camlfwrun、字节码查看器camlfwod。

编译并链接源文件得到可执行的字节码文件：

1
2
3
4
% ./camlfwc -v /tmp/a.ml -o /tmp/a.out
Compiling /tmp/a.ml
- : unit
Linking /tmp/a.zo -> /tmp/a.out

使用camlfwrun执行：

1
% ./camlfwrun /tmp/a.out

camlfwod可以显示目标文件或字节码可执行文件的指令列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
% ./camlfwod /tmp/a.zo
%File /tmp/a.zo
Relocatable file

Offset 8
Length 33
0008: PUSHMARK
...

% ./camlfwod /tmp/a.out
File /tmp/a.out
Executable

Length 34
000c: PUSHMARK
%File /tmp/a.zo
Relocatable file

Offset 8
Length 33
0008: PUSHMARK
...

学位论文

thesis.pdf