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,函数可以像intstring那样的值一样自由传递、创建。
  • 实现了静态类型检查,并能自动推导类型,无需C中的类型注解。
  • 提供了immutable programming的良好支持。
  • 参数多态,提供了一些通用编程支持,类似于Java中的generic。
  • 支持代数数据类型和模式匹配以处理复杂的数据结构。

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

项目采用的Caml语言变体

内置类型

基本类型:

  • bool,如truefalse
  • char,如’a’’\n’
  • int,如120x0e
  • float,如3.02e-5
  • string,如helloworld

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

  • ’a option,如NoneSome (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,它有三个构造器:ZeroOneTwo,接受不同的参数。

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

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

模式匹配也可用于intstring等基本类型。_是通配符,可以匹配任意值:

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