1

ML编译器Caml Featherweight——概览

 3 years ago
source link: http://maskray.me/blog/2014-12-24-caml-compiler-overview
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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。

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

# 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
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：

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

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

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

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

output_int (try
let Some 3 = None in
with Division_by_zero ->
with Match_failure _ ->

工具链使用说明

在项目目录下执行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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK