下面拿OCaml手册的导论部分的前两章缩译了一下，这里涵盖了核心语言和模块系统两方面的内容。
* Chapter 1 The core language
这部分是OCaml语言的简明教程，需要有某一编程语言的使用基础，但不一定是函数式语言。
** 1.1 Basics
下面将在交互模式中演示，“#”开头的行表示用户输入。输入以“;;”终止，交互系统会随即解析表达式或定义语句并返回执行结果。
#1+2*3;;
- : int = 7
#let pi = 4.0 *. atan 1.0;;
val pi : float = 3.14159265358979312
#let square x = x *. x;;
val square : float -> float = <fun>
#square(sin pi) +. square(cos pi);;
- : float = 1.
值和类型会被执行，函数中未显式声明的参数系统会根据其定义中的语句来推断。要注意整数和浮点数是不同的类型，前者用“+”和“*”而后者用“+.”和“*.”。
#1.0 * 2;;
Error: This expression has type float but an expression was expected of type int
递归函数有“let rec”绑定：
#let rec fib n =
if n < 2 then n else fib(n-1) + fib(n-2);;
val fib : int -> int = <fun>
#fib 10;;
- : int = 55
** 1.2 Data types
除了整数和浮点数，Caml中还提供了其他的常用基本类型：布尔型、字符型、字符串型。
#(1 < 2) = false;;
- : bool = false
#’a’;;
- : char = ’a’
#"Hello world";;
- : string = "Hello world"
预定义的数据结构包括元组、数组、列表，此外也可创建自定义类型。列表是由“[”和“]”包裹“;”分割，或者由空表“[]”（读作nil）前面用“::”操作符添加元素构成。
#let l = ["is"; "a"; "tale"; "told"; "etc."];;
val l : string list = ["is"; "a"; "tale"; "told"; "etc."]
#"Life" :: l;;
- : string list = ["Life"; "is"; "a"; "tale"; "told"; "etc."]
列表的内存管理将自动进行，不需要显式地分配或回收。指针由Caml编译器负责，也不需要显式的处理。
列表（以及大部分Caml数据结构）的检查和解析通过模式匹配进行。列表的模式与列表的定义形式相同，以标识符表示列表中未定义的部分。以下是用列表进行插入排序的例子：
#let rec sort lst =
match lst with
[] -> []
| head :: tail -> insert head (sort tail)
and insert elt lst =
match lst with
[] -> [elt]
| head :: tail -> if elt <= head then elt :: lst else head :: insert elt tail
;;
val sort : ’a list -> ’a list = <fun>
val insert : ’a -> ’a list -> ’a list = <fun>
#sort l;;
- : string list = ["a"; "etc."; "is"; "tale"; "told"]
这里sort推断得到的类型是“’a list -> ’a list”，表示作用于任意类型的列表并返回相同类型的列表。其中“’a ”是类型变量，代表任意类型。之所以sort可以用于任意类型列表，是因为比较操作（“=”“<=”等等）在Caml中是多态的。
#sort [6;2;5;3];;
- : int list = [2; 3; 5; 6]
#sort [3.14; 2.718];;
- : float list = [2.718; 3.14]
上面的sort函数没有修改它的输入列表，而是创建并返回一个元素个数相同的递增列表。列表创建后是无法在原地修改的，在Caml中列表是不可变的结构。大部分Caml中的数据结构是不可变的，而少部分（如数组）是可变的（可以在任何时候原地修改）。
** 1.3 Functions as values
Caml是一种函数式语言，支持数学意义上的函数并可以和其他数据片段一样被自由地传递。例如这里的deriv函数以浮点函数为参数并返回它的导函数的逼近函数：
#let deriv f dx = function x -> (f(x +. dx) -. f(x)) /. dx;;
val deriv : (float -> float) -> float -> float -> float = <fun>
#let sin’ = deriv sin 1e-6;;
val sin’ : float -> float = <fun>
#sin’ pi;;
- : float = -1.00000000013961143
Even function composition is definable:
#let compose f g = function x -> f(g(x));;
val compose : (’a -> ’b) -> (’c -> ’a) -> ’c -> ’b = <fun>
#let cos2 = compose square cos;;
val cos2 : float -> float = <fun>
以其他函数作为参数的函数称为“泛函數”（functionals）或者“高阶函数”（higher-order functions）。泛函数可用于对数据结构的迭代或类似的操作。例如Caml的标准库中提供“List.map”将给定函数应用于列表中的每个元素并返回结果列表：
#List.map (function n -> n * 2 + 1) [0;1;2;3;4];;
- : int list = [1; 3; 5; 7; 9]
常用的列表和数组相关的函数已经定义好了，或者也可以按照下面的方式自行定义。
#let rec map f l =
match l with
[] -> []
| hd :: tl -> f hd :: map f tl;;
val map : (’a -> ’b) -> ’a list -> ’b list = <fun>
** 1.4 Records and variants
用户定义的数据结构包括记录和变体。它们都通过类型声明来定义。这里我们声明了一个表示有理数的记录类型。
#type ratio = {num: int; denum: int};;
type ratio = { num : int; denum : int; }
#let add_ratio r1 r2 =
{num = r1.num * r2.denum + r2.num * r1.denum;
denum = r1.denum * r2.denum};;
val add_ratio : ratio -> ratio -> ratio = <fun>
#add_ratio {num=1; denum=3} {num=2; denum=5};;
- : ratio = {num = 11; denum = 15}
变体类型的声明列出了该类型所有值的形状。每种情况用一个名称作为标识符，称为构造器，既用来在构造那种变体类型的值，也用来在模式匹配中检查它们。构造器的首字母大写，用来和变量名区分（必须以小写字母开头）。例如这里是一个用来进行混合运算（整数和浮点）的变体类型：
#type number = Int of int | Float of float | Error;;
type number = Int of int | Float of float | Error
这个声明表示number类型的值或者是一个整数，或者是一个浮点数，或者是表示无效运算结果的常量Error（比如被零除）。
枚举类型是变体类型的一种特殊情况，是当所有的选择支都是常量的时候：
#type sign = Positive | Negative;;
type sign = Positive | Negative
#let sign_int n = if n >= 0 then Positive else Negative;;
val sign_int : int -> sign = <fun>
要定义number类型的算数运算，我们需要对用到的两个number使用模式匹配：
#let add_num n1 n2 =
match (n1, n2) with
(Int i1, Int i2) ->
(* Check for overflow of integer addition *)
if sign_int i1 = sign_int i2 && sign_int(i1 + i2) <> sign_int i1
then Float(float i1 +. float i2)
else Int(i1 + i2)
| (Int i1, Float f2) -> Float(float i1 +. f2)
| (Float f1, Int i2) -> Float(f1 +. float i2)
| (Float f1, Float f2) -> Float(f1 +. f2)
| (Error, _) -> Error
| (_, Error) -> Error;;
val add_num : number -> number -> number = <fun>
#add_num (Int 123) (Float 3.14159);;
- : number = Float 126.14159
变体类型的最常见的用途是描述递归的数据结构。考虑二叉树的例子：
#type ’a btree = Empty | Node of ’a * ’a btree * ’a btree;;
type ’a btree = Empty | Node of ’a * ’a btree * ’a btree
该定义这样来读：一个包含类型'a（任意类型）的值二叉树或者是空的或者是一个节点，节点有一个类型'a的值和两个也包含类型'a的子树（即两个 'a btree）。
二叉树上的操作的操作依照其定义自身很自然的用递归函数表达出来。例如这里的函数用来在有序二叉树（元素又左至右递增）上查找和插入。
#let rec member x btree =
match btree with
Empty -> false
| Node(y, left, right) ->
if x = y then true else
if x < y then member x left else member x right;;
val member : ’a -> ’a btree -> bool = <fun>
#let rec insert x btree =
match btree with
Empty -> Node(x, Empty, Empty)
| Node(y, left, right) ->
if x <= y then Node(y, insert x left, right)
else Node(y, left, insert x right);;
val insert : ’a -> ’a btree -> ’a btree = <fun>
** 1.5 Imperative features
尽管目前的例子都写为纯函数的风格，Caml也具有命令式的特性。这包括了常见的while和for循环，以及可变的数据结构比如数组。数组用“[|”“|]”包围的形式来书写，或者通过“Array.create”函数来分配并初始化然后再赋值。例如，下面的函数即求两个向量（实现为浮点数组）的部分的和。
#let add_vect v1 v2 =
let len = min (Array.length v1) (Array.length v2) in
let res = Array.create len 0.0 in
for i = 0 to len - 1 do
res.(i) <- v1.(i) +. v2.(i)
done;
res;;
val add_vect : float array -> float array -> float array = <fun>
#add_vect [| 1.0; 2.0 |] [| 3.0; 4.0 |];;
- : float array = [|4.; 6.|]
通过来定义中声明为可变的，记录的字段也可以通过赋值操作来修改：
#type mutable_point = { mutable x: float; mutable y: float };;
type mutable_point = { mutable x : float; mutable y : float; }
#let translate p dx dy =
p.x <- p.x +. dx; p.y <- p.y +. dy;;
val translate : mutable_point -> float -> float -> unit = <fun>
#let mypoint = { x = 0.0; y = 0.0 };;
val mypoint : mutable_point = {x = 0.; y = 0.}
#translate mypoint 1.0 2.0;;
- : unit = ()
#mypoint;;
- : mutable_point = {x = 1.; y = 2.}
Caml没有内置变量（可以通过赋值改变当前值的标识）的概念。（let绑定不是赋值，它在新作用域里建立了新的标识。）不过标准库中通过间接地使用可变字段（或者单元素数组）来提供了引用类型，并可通过操作符“!”获取引用的当前内容以及“:=”来赋值。变量可以通过绑定一个引用来模拟。例如，这里是一个数组的原地插入排序的例子：
#let insertion_sort a =
for i = 1 to Array.length a - 1 do
let val_i = a.(i) in
let j = ref i in
while !j > 0 && val_i < a.(!j - 1) do
a.(!j) <- a.(!j - 1);
j := !j - 1
done;
a.(!j) <- val_i
done;;
val insertion_sort : ’a array -> unit = <fun>
函数也可用于书写需要维持两次调用中的当前状态的函数。例如下面的伪随机数生成器通过引用记录了最后返回的数值：
#let current_rand = ref 0;;
val current_rand : int ref = {contents = 0}
#let random () =
current_rand := !current_rand * 25713 + 1345;
!current_rand;;
val random : unit -> int = <fun>
再次说明，引用没什么特别的：它们是通过下面这样的一个可变字段的记录来实现的。
#type ’a ref = { mutable contents: ’a };;
type ’a ref = { mutable contents : ’a; }
#let (!) r = r.contents;;
val ( ! ) : ’a ref -> ’a = <fun>
#let (:=) r newval = r.contents <- newval;;
val ( := ) : ’a ref -> ’a -> unit = <fun>
有时会需要在数据结构中存放多态函数并保持多态。除非用户提供类型标记，不然是不允许的，因为多态仅在全局类型中引入。不过你可以给记录的字段给出显式的多态类型。
#type idref = { mutable id: ’a. ’a -> ’a };;
type idref = { mutable id : ’a. ’a -> ’a; }
#let r = {id = fun x -> x};;
val r : idref = {id = <fun>}
#let g s = (s.id 1, s.id true);;
val g : idref -> int * bool = <fun>
#r.id <- (fun x -> print_string "called id\n"; x);;
- : unit = ()
#g r;;
called id
called id
- : int * bool = (1, true)
** 1.6 Exceptions
Caml提供异常机制用来指示和处理例外的状况。异常也可用于通用的非局部控制结构。异常通过异常构造来声明，并用raise操作符来指示。例如，下面这个取列表头的函数使用异常来指示遇到空表的情况。
#exception Empty_list;;
exception Empty_list
#let head l =
match l with
[] -> raise Empty_list
| hd :: tl -> hd;;
val head : ’a list -> ’a = <fun>
#head [1;2];;
- : int = 1
#head [];;
Exception: Empty_list.
在标准库中异常用来指示库函数不能被正常完成的情况。例如，“List.assoc”函数，用来返回一个“(键, 数据)”对的列表中给定键关联的值，在键没有在列表中出现的时候将引起预定义的异常"Not_found":
#List.assoc 1 [(0, "zero"); (1, "one")];;
- : string = "one"
#List.assoc 2 [(0, "zero"); (1, "one")];;
Exception: Not_found.
Exceptions can be trapped with the try…with construct:
#let name_of_binary_digit digit =
try
List.assoc digit [0, "zero"; 1, "one"]
with Not_found ->
"not a binary digit";;
val name_of_binary_digit : int -> string = <fun>
#name_of_binary_digit 0;;
- : string = "zero"
#name_of_binary_digit (-1);;
- : string = "not a binary digit"
with部分其实是异常值的正则模式匹配。因此，若干异常可以用一个try...with结构来捕获。此外，终止可以通过捕获所有的异常来进行，执行终止操作，然后再次引起该异常：
#let temporarily_set_reference ref newval funct =
let oldval = !ref in
try
ref := newval;
let res = funct () in
ref := oldval;
res
with x ->
ref := oldval;
raise x;;
val temporarily_set_reference : ’a ref -> ’a -> (unit -> ’b) -> ’b = <fun>
** 1.7 Symbolic processing of expressions
我们通过一个较完整的例子来结束这次介绍：使用Caml进行符号处理，形式化的操作包含变量的算术表达式。下列的变体类型描述了我们将操作的表达式：
#type expression =
Const of float
| Var of string
| Sum of expression * expression (* e1 + e2 *)
| Diff of expression * expression (* e1 - e2 *)
| Prod of expression * expression (* e1 * e2 *)
| Quot of expression * expression (* e1 / e2 *)
;;
type expression =
Const of float
| Var of string
| Sum of expression * expression
| Diff of expression * expression
| Prod of expression * expression
| Quot of expression * expression
我们首先定义一个函数在所给变量由名称映射到值的环境下计算表达式的值。为了简化，环境用关联列表表示。
#exception Unbound_variable of string;;
exception Unbound_variable of string
#let rec eval env exp =
match exp with
Const c -> c
| Var v ->
(try List.assoc v env with Not_found -> raise(Unbound_variable v))
| Sum(f, g) -> eval env f +. eval env g
| Diff(f, g) -> eval env f -. eval env g
| Prod(f, g) -> eval env f *. eval env g
| Quot(f, g) -> eval env f /. eval env g;;
val eval : (string * float) list -> expression -> float = <fun>
#eval [("x", 1.0); ("y", 3.14)] (Prod(Sum(Var "x", Const 2.0), Var "y"));;
- : float = 9.42
现在为了进行真正的符号处理，我们定义关于变量dv的表达式的导数：
#let rec deriv exp dv =
match exp with
Const c -> Const 0.0
| Var v -> if v = dv then Const 1.0 else Const 0.0
| Sum(f, g) -> Sum(deriv f dv, deriv g dv)
| Diff(f, g) -> Diff(deriv f dv, deriv g dv)
| Prod(f, g) -> Sum(Prod(f, deriv g dv), Prod(deriv f dv, g))
| Quot(f, g) -> Quot(Diff(Prod(deriv f dv, g), Prod(f, deriv g dv)),
Prod(g, g))
;;
val deriv : expression -> string -> expression = <fun>
#deriv (Quot(Const 1.0, Var "x")) "x";;
- : expression =
Quot (Diff (Prod (Const 0., Var "x"), Prod (Const 1., Const 1.)),
Prod (Var "x", Var "x"))
** 1.8 Pretty-printing and parsing
上面的例子显示，表达式的内部结构（通常也称为抽象语法）在表达式变长的时候很快就难以读写。我们需要打印和解析过程在抽象语法和具体语法（这里指表达式用熟悉的代数符号，例如“2*x+1”）之间来回转换。
在打印函数中，我们考虑通常的优先规则（比如*比+绑定地更紧）来避免打印不必要的括号。在实现上，我们记录当前操作符的优先级并只当操作符的优先级低于当前优先级的时候在周围打印出括号。
#let print_expr exp =
(* Local function definitions *)
let open_paren prec op_prec =
if prec > op_prec then print_string "(" in
let close_paren prec op_prec =
if prec > op_prec then print_string ")" in
let rec print prec exp = (* prec is the current precedence *)
match exp with
Const c -> print_float c
| Var v -> print_string v
| Sum(f, g) ->
open_paren prec 0;
print 0 f; print_string " + "; print 0 g;
close_paren prec 0
| Diff(f, g) ->
open_paren prec 0;
print 0 f; print_string " - "; print 1 g;
close_paren prec 0
| Prod(f, g) ->
open_paren prec 2;
print 2 f; print_string " * "; print 2 g;
close_paren prec 2
| Quot(f, g) ->
open_paren prec 2;
print 2 f; print_string " / "; print 3 g;
close_paren prec 2
in print 0 exp;;
val print_expr : expression -> unit = <fun>
#let e = Sum(Prod(Const 2.0, Var "x"), Const 1.0);;
val e : expression = Sum (Prod (Const 2., Var "x"), Const 1.)
#print_expr e; print_newline();;
2. * x + 1.
- : unit = ()
#print_expr (deriv e "x"); print_newline();;
2. * 1. + 0. * x + 0.
- : unit = ()
解析（将具体语法转换为抽象语法）通常更精巧些。Caml提供若干工具来帮助编写解析器：一方面，Caml版本的Lex词法生成器和Yacc解析生成器，可以使用下推自动机处理啦LALR(1)语言。另一方面，预定义的（字符或标志）流类型和流的模式匹配，可以为LL(1)语言方便地编写递归下降的解析器。后面的章节中有使用ocamllex和ocamlyacc的例子。这里我们将使用流解析器。流解析器的语法支持由Camlp4预处理器提供，它可以在交互模式中由下面的“#load”指令载入。
##load "camlp4o.cma";;
Characters -1–1:
Error: Reference to undefined global ‘Dynlink’
#open Genlex;;
let lexer = make_lexer ["("; ")"; "+"; "-"; "*"; "/"];;
val lexer : char Stream.t -> Genlex.token Stream.t = <fun>
在词法分析阶段（将输入文本转换为标志流），我们使用标准库中Genlex模块的“通用”的词法解析器。“make_lexer”接受关键词列表并返回“标志化”字符输入流的词法解析函数。标志是标识符、关键词或者是字面义（整数、浮点、字符、字符串）。空白和评论跳过。
#let token_stream = lexer(Stream.of_string "1.0 +x");;
val token_stream : Genlex.token Stream.t = <abstr>
#Stream.next token_stream;;
- : Genlex.token = Float 1.
#Stream.next token_stream;;
- : Genlex.token = Kwd "+"
#Stream.next token_stream;;
- : Genlex.token = Ident "x"
解析器通过在在标志流上执行自身的操作。和常见的递归下降解析器一样，我们使用若干中间解析函数来反映操作符的优先级和结合性。流上的模式匹配比正则的数据结构更为强大，因为它允许在模式里递归的调用解析函数，用以匹配输入流的子部件。更多的细节见Camlp4的文档。
#let rec parse_expr = parser
[< e1 = parse_mult; e = parse_more_adds e1 >] -> e
and parse_more_adds e1 = parser
[< ’Kwd "+"; e2 = parse_mult; e = parse_more_adds (Sum(e1, e2)) >] -> e
| [< ’Kwd "-"; e2 = parse_mult; e = parse_more_adds (Diff(e1, e2)) >] -> e
| [< >] -> e1
and parse_mult = parser
[< e1 = parse_simple; e = parse_more_mults e1 >] -> e
and parse_more_mults e1 = parser
[< ’Kwd "*"; e2 = parse_simple; e = parse_more_mults (Prod(e1, e2)) >] -> e
| [< ’Kwd "/"; e2 = parse_simple; e = parse_more_mults (Quot(e1, e2)) >] -> e
| [< >] -> e1
and parse_simple = parser
[< ’Ident s >] -> Var s
| [< ’Int i >] -> Const(float i)
| [< ’Float f >] -> Const f
| [< ’Kwd "("; e = parse_expr; ’Kwd ")" >] -> e;;
Error: Syntax error
#let parse_expression = parser [< e = parse_expr; _ = Stream.empty >] -> e;;
Error: Syntax error
通过组合来词法和语法解析器，我们最终获得了一个从字符串中读取表达式的函数：
#let read_expression s = parse_expression(lexer(Stream.of_string s));;
Error: Unbound value parse_expression
#read_expression "2*(x+y)";;
Error: Unbound value read_expression
小问题：为什么在下面两个例子中我们得到了不同的结果？
#read_expression "x - 1";;
Error: Unbound value read_expression
#read_expression "x-1";;
Error: Unbound value read_expression
解答：由Genlex提供的通用的词法解析器把负数识别为一个整数标志。因此“x-1”被读取为标志Ident "x" 跟着标志Int(-1)；该序列不匹配任何解析规则。另一方面“x - 1”中的第二个空格导致词法解析器返回三个期望的标志：Ident "x"然后Kwd "-"然后Int(1)。
** 1.9 Standalone Caml programs
目前所有给出的例子是在交互系统下执行的。Caml代码也可以通过编译器“ocamlc”或“ocamlopt”单独地编译并非交互的执行。源代码需要放在以“.ml”为扩展名的文件中。源文件包含一序列的代码，并在运行时按照排列的顺序执行。不同于交互模式，类型和值不会自动打印；程序需要调用打印函数来显式地输出。这里是一个打印斐波纳契数列的独立的示例程序。
(* File fib.ml *)
let rec fib n =
if n < 2 then 1 else fib(n-1) + fib(n-2);;
let main () =
let arg = int_of_string Sys.argv.(1) in
print_int(fib arg);
print_newline();
exit 0;;
main ();;
“Sys.argv”是包含命令行参数的字符串数组。“Sys.argv.(1)”因此是命令行的第一个参数。上面这个程序通过下列命令编译并执行：
$ ocamlc -o fib fib.ml
$ ./fib 10
89
$ ./fib 20
10946
* Chapter 2 The module system
这一章介绍Objective Caml的模块系统。
** 2.1 Structures
模块的主要动机是是将相关的定义（比如定义了一种数据类型和那个类型关联的操作符）打包在一起并为这些定义执行一致的命名策略。这样避免的用尽名称或者意外的命名冲突。这样的包称为一个结构通过“struct…end”结构引入，并包含任意定义语句的序列。结构通常给予一个模块绑定的名称。这里的例子是用结构把优先列队的类型和操作打包在一起：
#module PrioQueue =
struct
type priority = int
type ’a queue = Empty | Node of priority * ’a * ’a queue * ’a queue
let empty = Empty
let rec insert queue prio elt =
match queue with
Empty -> Node(prio, elt, Empty, Empty)
| Node(p, e, left, right) ->
if prio <= p
then Node(prio, elt, insert right p e, left)
else Node(p, e, insert right prio elt, left)
exception Queue_is_empty
let rec remove_top = function
Empty -> raise Queue_is_empty
| Node(prio, elt, left, Empty) -> left
| Node(prio, elt, Empty, right) -> right
| Node(prio, elt, (Node(lprio, lelt, _, _) as left),
(Node(rprio, relt, _, _) as right)) ->
if lprio <= rprio
then Node(lprio, lelt, remove_top left, right)
else Node(rprio, relt, left, remove_top right)
let extract = function
Empty -> raise Queue_is_empty
| Node(prio, elt, _, _) as queue -> (prio, elt, remove_top queue)
end;;
module PrioQueue :
sig
type priority = int
type ’a queue = Empty | Node of priority * ’a * ’a queue * ’a queue
val empty : ’a queue
val insert : ’a queue -> priority -> ’a -> ’a queue
exception Queue_is_empty
val remove_top : ’a queue -> ’a queue
val extract : ’a queue -> priority * ’a * ’a queue
end
在结构的外面，它的组件可以用“.”点号标记来引用，也就是由结构名限制的标识符。例如“PrioQueue.insert”的在值的上下文中是结构“PrioQueue”中定义的一个函数。类似的，“PrioQueue.queue”在类型的上下文中是“PrioQueue”中定义的列队类型。
#PrioQueue.insert PrioQueue.empty 1 "hello";;
- : string PrioQueue.queue =
PrioQueue.Node (1, "hello", PrioQueue.Empty, PrioQueue.Empty)
** 2.2 Signatures
签名是结构的界面。签名指定了结构的哪些组件可以从外部访问，并通过何种类型。它可以用来隐藏结构中的一些组件（例如局部函数定义）或者由受限的类型导出相关组件。例如下面的签名指定了三个优先列队的操作符“empty”、“insert”和“extract”，但是没有辅助函数“remove_top”。类似的，它使得列队类型抽象化（通过不以具体的类型提供实际的表现形式）。
#module type PRIOQUEUE =
sig
type priority = int (* still concrete *)
type ’a queue (* now abstract *)
val empty : ’a queue
val insert : ’a queue -> int -> ’a -> ’a queue
val extract : ’a queue -> int * ’a * ’a queue
exception Queue_is_empty
end;;
module type PRIOQUEUE =
sig
type priority = int
type ’a queue
val empty : ’a queue
val insert : ’a queue -> int -> ’a -> ’a queue
val extract : ’a queue -> int * ’a * ’a queue
exception Queue_is_empty
end
通过该签名限制“PrioQueue”结构的结果是“PrioQueue”结构的另一种使用视角，其中“remove_top”函数不可访问同时有限列队的实际表现是隐藏的：
#module AbstractPrioQueue = (PrioQueue : PRIOQUEUE);;
module AbstractPrioQueue : PRIOQUEUE
#AbstractPrioQueue.remove_top;;
Error: Unbound value AbstractPrioQueue.remove_top
#AbstractPrioQueue.insert AbstractPrioQueue.empty 1 "hello";;
- : string AbstractPrioQueue.queue = <abstr>
限制也可以在定义结构的时候执行，就像
module PrioQueue = (struct ... end : PRIOQUEUE);;
上面的另一种可选语法是：
module PrioQueue : PRIOQUEUE = struct ... end;;
** 2.3 Functors
函子使用由结构到结构的”函数“。它们用来表达参数化的结构：以结构B作为参数的结构A，简单地说就是以B为形式参数（依照对B期望的签名）的函子F返回实际的结构A自身。函子F随后可以使用到B的若干实现B1...Bn上面，对应的产生结构A1...An。
例如这里是一个用有序列表作为集合的结构实现，以一个提供集合元素的类型的结构和该类型的排序函数（用来保持集合是有序的）为参数：
#type comparison = Less | Equal | Greater;;
type comparison = Less | Equal | Greater
#module type ORDERED_TYPE =
sig
type t
val compare: t -> t -> comparison
end;;
module type ORDERED_TYPE = sig type t val compare : t -> t -> comparison end
#module Set =
functor (Elt: ORDERED_TYPE) ->
struct
type element = Elt.t
type set = element list
let empty = []
let rec add x s =
match s with
[] -> [x]
| hd::tl ->
match Elt.compare x hd with
Equal -> s (* x is already in s *)
| Less -> x :: s (* x is smaller than all elements of s *)
| Greater -> hd :: add x tl
let rec member x s =
match s with
[] -> false
| hd::tl ->
match Elt.compare x hd with
Equal -> true (* x belongs to s *)
| Less -> false (* x is smaller than all elements of s *)
| Greater -> member x tl
end;;
module Set :
functor (Elt : ORDERED_TYPE) ->
sig
type element = Elt.t
type set = element list
val empty : ’a list
val add : Elt.t -> Elt.t list -> Elt.t list
val member : Elt.t -> Elt.t list -> bool
end
通过把函子“Set”应用到一个实现有序类型的结构上，我们获得了该类型的集合操作符：
#module OrderedString =
struct
type t = string
let compare x y = if x = y then Equal else if x < y then Less else Greater
end;;
module OrderedString :
sig type t = string val compare : ’a -> ’a -> comparison end
#module StringSet = Set(OrderedString);;
module StringSet :
sig
type element = OrderedString.t
type set = element list
val empty : ’a list
val add : OrderedString.t -> OrderedString.t list -> OrderedString.t list
val member : OrderedString.t -> OrderedString.t list -> bool
end
#StringSet.member "bar" (StringSet.add "foo" StringSet.empty);;
- : bool = false
** 2.4 Functors and type abstraction
在“PrioQueue”例子中，隐藏集合类型的实际实现会是一个良好的习惯，这样该结构的用户就不依赖于集合是一个列表，并我们能够随后切换到其他更高效的集合的表现形式而不破坏它们的代码。这可以通过合适的函子签名限制“Set”来实现：
#module type SETFUNCTOR =
functor (Elt: ORDERED_TYPE) ->
sig
type element = Elt.t (* concrete *)
type set (* abstract *)
val empty : set
val add : element -> set -> set
val member : element -> set -> bool
end;;
module type SETFUNCTOR =
functor (Elt : ORDERED_TYPE) ->
sig
type element = Elt.t
type set
val empty : set
val add : element -> set -> set
val member : element -> set -> bool
end
#module AbstractSet = (Set : SETFUNCTOR);;
module AbstractSet : SETFUNCTOR
#module AbstractStringSet = AbstractSet(OrderedString);;
module AbstractStringSet :
sig
type element = OrderedString.t
type set = AbstractSet(OrderedString).set
val empty : set
val add : element -> set -> set
val member : element -> set -> bool
end
#AbstractStringSet.add "gee" AbstractStringSet.empty;;
- : AbstractStringSet.set = <abstr>
试图更优雅的书写类型约束，有人会希望命名函子返回的结构的签名，然后在约束中使用那个签名：
#module type SET =
sig
type element
type set
val empty : set
val add : element -> set -> set
val member : element -> set -> bool
end;;
module type SET =
sig
type element
type set
val empty : set
val add : element -> set -> set
val member : element -> set -> bool
end
#module WrongSet = (Set : functor(Elt: ORDERED_TYPE) -> SET);;
module WrongSet : functor (Elt : ORDERED_TYPE) -> SET
#module WrongStringSet = WrongSet(OrderedString);;
module WrongStringSet :
sig
type element = WrongSet(OrderedString).element
type set = WrongSet(OrderedString).set
val empty : set
val add : element -> set -> set
val member : element -> set -> bool
end
#WrongStringSet.add "gee" WrongStringSet.empty;;
Error: This expression has type string but an expression was expected of type
WrongStringSet.element = WrongSet(OrderedString).element
这里的问题是“Set”制定的类型元素是抽象的，使得在函子结果的元素和参数的“t”之间类型相等被遗忘了。所以“WrongStringSet.element”和字符串是不同的类型，“WrongStringSet”上的操作不能使用到字符串上。正如上述演示，签名“Set”中的类型元素声明为和“Elt.t”相等是很重要；不幸地，由于“SET”定义在“Elt”不存在的上下文中上面的想法是不可能的。为了克服这个困难，Objective Caml提供了签名上的类型约束来允许使用额外的类型相等来扩充一个签名：
#module AbstractSet =
(Set : functor(Elt: ORDERED_TYPE) -> (SET with type element = Elt.t));;
module AbstractSet :
functor (Elt : ORDERED_TYPE) ->
sig
type element = Elt.t
type set
val empty : set
val add : element -> set -> set
val member : element -> set -> bool
end
和简化结构定义的情况一样，定义函子并约束其结果提供有另一种语法：
module AbstractSet(Elt: ORDERED_TYPE) : (SET with type element = Elt.t) =
struct ... end;;
抽象函子结果的类型组件是一个强大的技术来提供我们所描述的这样提供了高度的类型安全。考虑一个字符串序不同于在“OrderedString”结构中实现的标准顺序。例如我们忽略大小写来比较字符串。
#module NoCaseString =
struct
type t = string
let compare s1 s2 =
OrderedString.compare (String.lowercase s1) (String.lowercase s2)
end;;
module NoCaseString :
sig type t = string val compare : string -> string -> comparison end
#module NoCaseStringSet = AbstractSet(NoCaseString);;
module NoCaseStringSet :
sig
type element = NoCaseString.t
type set = AbstractSet(NoCaseString).set
val empty : set
val add : element -> set -> set
val member : element -> set -> bool
end
#NoCaseStringSet.add "FOO" AbstractStringSet.empty;;
Error: This expression has type
AbstractStringSet.set = AbstractSet(OrderedString).set
but an expression was expected of type
NoCaseStringSet.set = AbstractSet(NoCaseString).set
注意“AbstractStringSet.set”和“NoCaseStringSet.set”这两个类型是不兼容的，这两个类型的值不相匹配。这是正确的行为：即使两个集合包含相同类型（字符串），两者构建于该类型的不同的顺序，操作符需要维护不同的不变量（标准顺序的严格递增和忽略大小写的顺序）。把“AbstractStringSet”的操作应用到类型“NoCaseStringSet.set”的值会给出错误的结果，或创建了违背“NoCaseStringSet”的不变量的列表。
** 2.5 Modules and separate compilation
目前所有的模块的例子都是在交互系统的上下文中给出。不过模块对大型的批量编译程序格外有用。对这样的程序，存在实践的必要性把源代码分割到若干文件中，称为编译单元，可以单独的编译，由此最小化修改后的重编译。
在Objective Caml中，编译单元是结构和签名的特例，单元之间的关系可以从模块系统的方面容易地解释。一个编译单元A包含两个文件：
实现文件A.ml，包含一序列定义，相当于在“struct…end”构造之内；
界面文件A.mli，包含一序列规格，相当于在“sig…end”构造之内。
两个文件定义了一个名为A的结构如同下面的定义插入在顶层环境中：
module A: sig (* contents of file A.mli *) end
= struct (* contents of file A.ml *) end;;
文件定义的编译单元可以用“ocamlc -c”命令（-c选项表示“只编译，不要连接”）单独编译；这样产生了编译的界面文件（以.cmi为扩展名）和编译的目标代码文件（以.cmo为扩展名）。当所有的单元都被编译，它们的“.cmo”文件使用“ocaml"连接在一起。例如下列命令编译并连接一个由两个编译单元“Aux”和“Main”组成的程序：
$ ocamlc -c Aux.mli # produces aux.cmi
$ ocamlc -c Aux.ml # produces aux.cmo
$ ocamlc -c Main.mli # produces main.cmi
$ ocamlc -c Main.ml # produces main.cmo
$ ocamlc -o theprogram Aux.cmo Main.cmo
这个程序的行为正如同下列语句插入到顶层环境：
module Aux: sig (* contents of Aux.mli *) end
= struct (* contents of Aux.ml *) end;;
module Main: sig (* contents of Main.mli *) end
= struct (* contents of Main.ml *) end;;
特别地，“Main”可以引用“Aux”：“Main.ml”和“Main.mli”所包含的定义和声明可以引用“Aux.ml”的定义，使用“Aux.ident”标记，如果“Aux.mli”导出了这些定义的话。
在连接阶段给“ocaml”的“.cmo”文件的顺序决定了模块定义发生的顺序。因此在上面的例子中，“Aux”先出现并且“Main”可以引用它，但是“Aux”不能引用“Main”。
注意仅仅顶层的结构可以映射到单独编译的文件，并且不是函子或者模块类型。不过所有的模块类对象可以以结构的组件出现，所以解决方法是把函子和模块类型放在结构内，这样就能映射为文件了。
* 翻译说明
** 什么是OCaml/ML语言
OCaml是ML语言（当初作为可计算理论证明的工具产生的）的主要方言之一Caml语言当前的实现和扩展，是由INRIA开发的多范式语言。相比于ML另一方言SML，Caml语言是由它的实现（目前是OCaml）所描述的一种语言而没有基于某一报告或标准。但是OCaml在ML的基础上作出有用的扩展和尝试，使之在函数式编程语言中较适合做实际的应用。虽然ML系的语言并不广为使用（貌似仅在一些性能有关的金融数据分析的场合），但是这无法掩盖其设计上存在优异之处。并且OCaml目前在众Linux发行版中得到了较重点的支援，也影响到了F#和Scala语言的产生。关于编程语言类型的一书《Types And Programming Languages》中以OCaml作为描述语言。
个人觉得OCaml的代码十分清晰易读，至少从上面出现的例子中可以感知一二。它比Lisp更接近数学表达式，而比Haskell语法糖要少。在编译过程中编译为带类型的Lambda表达式的，这是它和它之前的函数式语言相通的地方。
** 和Standard ML的比较
SML当前是依据97年的修订报告，其功能和OCaml的核心加上模块这两部分是一致的，在语法上有些许差异。例如SML区分地除type外用datatype声明变体类型，用fun代替let绑定函数类型，用case...of而不是match...with进行模式匹配，用访问方法而不是下标的形式取记录的元素，有单独的eqtype表示可以判断相等的类型，在不同的内置类型重载了同样的算数运算符。
SML更关注于语言自身的规范和设计，在ML系语言中SML更加适合在教学场合中使用，并且不像OCaml受到法国文化的影响。
** 关于所翻译内容的说明
这里翻译的是OCaml手册中An introduction to Objective Caml部分的前两章节，这部分的原理是对所有ML系语言都使用，并且涵盖了编写程序时需要使用到的特性。其中核心部分用于编写一般的程序逻辑，而模块系统用于使用标准库和创建自己的库。其他特性如面向对象部分在很多实际应用中并没有用到。如果想通过实际的例子来获得一些感受的话：
简略的参考发卡片可以看
http://www.ocamlpro.com/code/2011-06-03-cheatsheets.html
这次有许多小的算法片段
http://rosettacode.org/wiki/Category:OCaml
一些开源项目的代码也可以拿来阅读，例如
形式语言系统Coq和P2P客户端Mldonkey。
** OCaml中提供的其他特性
其他特性的话，首先要说到面向对象特性，其围绕object,、class和type这三个关键词展开。注意OCaml在运行式已经擦除了类型信息，所以类型转换只能往父类单向进行，不过type仅代表接口上的关系而与class无关。在OCaml中继承表示句法关系而子类型表示语义关系，两者使用了不相干的语法。
至于常用的而上面没有说到的特性，一个是Labels，作为函数的关键词参数使用，另一个是Polymorphic variants，类似于Scheme中的Symbol。
此外还包含了一个标准库，和若干哦你工具如创建解析器的ocamllex和ocamlyacc以及从代码中生成文档的ocamldoc还有调试和性能测试工具。
另外有个语言扩充允许match语句中用when表示以条件来匹配还是一个较有用的特性。
** 有关的参考文档和阅读资料
首先是官网上的文档，包括OCaml和Caml Light的手册。它们侧重于对语言和实现本身的描述，这是书写程序时所必备的参考。
http://caml.inria.fr/resources/
还有oreilly的书名为《Developing Applications With Objective Caml》在官网是也免费的提供，涵盖了语言的教程和若干经验。
http://caml.inria.fr/pub/docs/oreilly-book/
** 可以使用的IDE工具
良好的缩进对代码的可读性相当重要，有编辑器帮助的话会很方便的。
这年头程序语言貌似都有强制缩进格式的倾向，让不同的人写出缩进完全一样的代码。
在Emacs中可以使用Tuareg Mode；在Ecliipse中可以使用OcaIDE，Scite也自带了OCaml的语法高亮。
** 和Haskell语言的区别
语法的外表上有继承关系倒是了，况其也是随着ML系的强类型函数式语言这一范式发展过来的。
区别在于Haskell是non-strict的，求值仅在需要是进行（注意一下此时的内存分配情况）；是核心部分是纯函数语言，命令式借助于函数的continuation约束执行的次序并由强类型机制约束发生的范围；支持函数的重载，通过typeclass使得同样名称的操作符可以用到不同类型的实例上。此外，Haskell的模块机制和类型无关，仅表示标识符的可见性。
现在Haskell的关注度于已经有超越ML系的趋势，并且自身发展和用户群体更为活跃。
** 关于此次翻译的说明
本来是想根据官方文档的内容来简要的表述一下，后来发觉以自身的能力想说清楚是有难度的，所以就演变成了字面的直译了。
这样可能产生了莫名其妙的曲解，在此也只能暂且就这样了。虽然翻译的曲解不会影响到原文的意思，但是给不幸接触到此文的人误导就不好了。
