ML编译器Caml Featherweight——概览

24th Dec 2014
6 min read
Tags:
compiler,
ocaml,
ml

索引
代码
完成度
介绍
项目采用的Caml语言变体
- 内置类型
- 操作符
- 元组
- 列表
- 数组
- option
- 函数
- 代数数据类型和模式匹配
- 异常
工具链使用说明
学位论文

索引

代码

编译器的设计和实现大量参考了 @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。

元组

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

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

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

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

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

列表

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

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

数组

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

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

访问数组中的一个元素：

  a.(3)

修改数组中的一个元素：

  a.(3) <- 'a'

`option`

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

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

函数

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

  let plus_one x = x + 1

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

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

  let sum_of_three x y z = x + y + z

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

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

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

  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)

代数数据类型和模式匹配

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

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

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

  match a with
  | A t ->
      match t with
      | Zero -> 0
      | One i -> i
      | Two(ch,i) -> i

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

  match s with
  | "hello" -> true
  | _ -> false

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

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

异常

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

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

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

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

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

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

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

工具链使用说明

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

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

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

使用camlfwrun执行：

% ./camlfwrun /tmp/a.out

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

% ./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