OCaml

OCaml（oʊ），是一個函數式、指令式、模塊化、面向對象的通用的程式語言。在Xavier Leroy和Damien Doligez，於1990年和1991年實現的ML方言Caml Light之上，Didier Rémy和Jérôme Vouillon，於1996年增加了面向對象特徵，從而形成了「Objective Caml」，在2011年時重命名為「OCaml」。

OCaml工具鏈包括交互式頂層解釋器、字節碼編譯器、優化的本機代碼編譯器，可逆調試器和一個包管理器（OPAM）。OCaml最初開發於自動定理證明的場景中，並在靜態分析和形式方法軟體中有超凡的存在感。此外，它在系統編程、網頁編程和金融工程及其他應用領域都有嚴肅的應用。

歷史上，Ascánder Suárez於1987年基於Guy Cousineau的範疇抽象機器（CAM），重新實現了Gérard Huet早先的ML方言，並用「範疇抽象機語言」的首字母簡寫將其命名為Caml，Caml Light放棄了這個抽象機器又進行了重新實現。OCaml是開放原始碼項目，此項目的管理和大部分維護工作，已經交由法國國家資訊與自動化研究所（INRIA）。在2000年代早期，來自OCaml的元素被很多語言接納，特別是F#和Scala。

## 哲學

ML派生語言最著稱的是靜態類型系統和類型推論編譯器。OCaml將函數式、指令式和面向對象編程統一於類ML的類型系統之下。因此編程者不需要為了使用OCaml而非常熟悉純函數式編程范型。

通過要求編程者在靜態類型系統的約束下工作，OCaml消除了關聯於動態類型語言的很多有關於類型的運行時間問題。還有，OCaml的類型推論編譯器，極大的減少了在多數靜態類型語言中對手工類型標註的需要。例如，變量的數據類型和函數的簽名，通常不需要像Java和C#語言中那樣顯式的聲明，因為它們可以從應用於這個變量和代碼中其他值的算符和其他函數推論出來。有效的使用OCaml的類型系統可能要求一個編程者面對一些複雜性，但是這種規矩能得到可靠的、高性能軟體作為回報。

OCaml與源於學術界的其他語言的最顯著區別可能是強調了性能。它的靜態類型系統防止了運行時間類型不匹配，從而排除了動態類型語言運行時間類型和安全檢查的性能負擔，卻在除了關閉陣列邊界檢查，和使用一些類型不安全特徵比如序列化之外的情況下，仍能保證運行時間安全性。這些運行時間檢查需求足夠罕見，在實踐中完全可以避免。

在類型檢查開銷之外，函數式程式語言，要編譯成高效的機器語言代碼，由於如函數參數問題這樣的要點，一般而言是具有挑戰性的。與標準的循環、寄存器和指令優化一起，OCaml的優化編譯器採用靜態程序分析方法，來優化值對象類型 (面向對象編程)（boxing）和閉包分配，幫助結果代碼得到最大化的性能，即使它大量使用了函數式編程構造。

Xavier Leroy曾經宣稱：「OCaml至少提供了像樣的C編譯器的50%的性能」，儘管直接比較是不可能的。在OCaml標準庫中的一些函數，是採用比在其他語言標準庫中等價的函數更快的演算法實現的。例如，在OCaml標準庫中集合併集的實現，在理論上比指令式語言（例如C++、Java）的標準庫中的等價函數，要漸進性的更快，因為OCaml實現利用了集合的不可變性，而在輸出中重用了輸入集合的一些部份（參見可持久化數據結構）。

## 特徵

OCaml的特徵包括：靜態類型系統、類型推論、參數多態、尾遞歸、模式匹配、頭等詞法閉包、函子（參數化模塊）、例外處理和增量分代自動垃圾回收。

OCaml著稱於將ML風格類型推論，擴展到通用語言中的對象系統。這允許了結構類型系統，這裡的對象類型是兼容的，如果它們的方法簽名是兼容的，不用管它們聲明的繼承，這是在靜態類型語言中不尋常的特徵。

OCaml提供了連結到C原語的外界函數接口，包括了兼容於C和Fortran二者格式的對高效數值陣列的語言支持。OCaml還支持建立可以連結到用C寫的`main`程序的OCaml函數庫。

OCaml發行包含了：

- 詞法分析和語法解析工具分別叫做`ocamllex`和`ocamlyacc`。
- 支持步進回溯的調試器用來調查錯誤。
- 文檔生成器。
- 剖析器用來測量性能。
- 很多通用函數庫。

本機代碼編譯器可以在很多平台上獲得，包括Unix、Microsoft Windows和Apple macOS。可移植性是通過至此主要架構的本機代碼生成 (編譯器)實現的：IA-32、X86-64（AMD64）、Power ISA、RISC-V、ARM和ARM64。

OCaml字節碼和本機代碼程序可以用多線程風格書寫，具有搶占式上下文切換。但是由於當前唯一可得的語言完全實現INRIA OCaml的垃圾回收器，不是為並發性而設計的，對稱多處理是不支持的。在相同進程中的OCaml線程只能分時執行。但是有一些分布式計算庫比如Functory和Plasma。

## 代碼例子

OCaml的代碼片段可以通過鍵入到頂層REPL中來很容易的研習。OCaml頂層是一個交互式的OCaml會話，它列印結果或定義的表達式的推論出的類型。它可以通過簡單執行OCaml程序來啟動：

```console
$ ocaml
OCaml version 5.4.0
Enter #help;; for help.

# 
```

可以接著在`#`提示符處鍵入代碼。例如計算`1+2*3`:

```OCaml
# 1 + 2 * 3;;
- : int = 7
```

OCaml推論出這個表達式的類型是`int`（機器精度整數）並給出結果`7`。

### Hello World

下面的程序`hello.ml`:

```OCaml
print_endline "Hello World!"
```

可以被編譯成字節碼可執行文件：

```console
$ ocamlc hello.ml -o hello
```

或者被編譯成優化的本地代碼可執行文件：

```console
$ ocamlopt hello.ml -o hello
```

接著執行它：

```console
$ ./hello
Hello World!
```

給ocamlc的第一個實際參數`hello.ml`，指定要編譯的源文件而`-o hello`標誌指定了輸出文件。

### 階乘函數

很多數學函數，比如階乘，可以很自然的表示為純粹的函數形式：

```OCaml
let rec fact n =
  if n=0 then 1 else n * fact(n - 1);;
```

這個函數可以使用模式匹配等價的寫為：

```OCaml
let rec fact = function
  | 0 -> 1
  | n -> n * fact(n - 1);;
```

後者形式是階乘作為遞推關係的數學定義。

編譯器將這個函數的類型推論為`int -> int`，意味著這個函數將`int`映射到`int`。例如，`12!`：

```OCaml
# fact 12;;
- : int = 479001600
```

### 斐波那契序列

下列代碼計算輸入數`n`的斐波那契數列。它使用了尾遞歸和模式匹配。

```OCaml
let fib n =
  let rec fib_aux m a b =
    match m with
    | 0 -> a
    | _ -> fib_aux (m - 1) b (a + b)
  in fib_aux n 0 1;;
```

### 生日問題

下列程序計算在一個屋子裡面有完全唯一的生日機率小於50%的最少人數，在生日問題中，對於1個人這個機率是365/365（或100%），對於2個人是364/365，對於3個人是364/365 × 363/365，最終答案是23個人：

```OCaml
let year_size = 365.
let rec birthday_paradox prob people =
  let prob = (year_size -. float people) /. year_size *. prob  in
  if prob < 0.5 then
    Printf.printf "answer = %d\n" (people+1)
  else
    birthday_paradox prob (people+1);;
```

```OCaml
# birthday_paradox 1.0 1;;
answer = 23
- : unit = ()
```

### 合計整數列表

列表是OCaml中的基礎數據類型之一。下面的代碼例子定義遞歸函數`sum`，它接受一個實際參數`integers`，而它被假定為整數的列表。注意關鍵字`rec`指示了這個函數是遞歸的。這個函數遞歸的在給定整數列表之上進行迭代，並提供這些元素的一個總和。`match`語句類似於C的`Switch语句`語句，但要更加一般性。

```ocaml
let rec sum integers =                   (* 关键字rec含义为递归。 *)
  match integers with
  | [] -> 0                              (* 产生0，如果integers为空列表 []。 *)
  | first :: rest -> first + sum rest;;  (* 递归调用，如果integers是非空列表。
                                            first是这个列表的第一个元素。
                                            而rest是余下元素的列表，可能是[]。 *)
```

```OCaml
# sum [1;2;3;4;5];;
- : int = 15
```

另一種方式是對列表使用標準的fold高階函數:

```ocaml
let sum integers =
  List.fold_left (fun accumulator x -> accumulator + x) 0 integers;;
```

```OCaml
# sum [1;2;3;4;5];;
- : int = 15
```

因為匿名函數是簡單的`+`算符應用，它可以簡寫為：

```ocaml
let sum integers =
  List.fold_left (+) 0 integers
```

進一步的，還可以通過採用部份應用省略列表實際參數：

```OCaml
let sum =
  List.fold_left (+) 0
```

### 快速排序

OCaml自身可提供對遞歸演算法的簡介表達。下列代碼例子實現了類似於以升序排序一個列表的quicksort的一個演算法：

```OCaml
 let rec qsort = function
   | [] -> []
   | pivot :: rest ->
     let is_less x = x < pivot in
     let left, right = List.partition is_less rest in
     qsort left @ [pivot] @ qsort right;;
```

### 高階函數

函數可以接受函數作為參數並且返回函數作為結果。例如，應用`twice`到函數`f`產生應用`f`到它的實際參數兩次的一個函數：

```OCaml
let twice (f : 'a -> 'a) = fun (x : 'a) -> f (f x);;
let inc (x : int) : int = x + 1;;
let add2 = twice inc;;
let inc_str (x : string) : string = x ^ " " ^ x;;
let add_str = twice(inc_str);;
```

```OCaml
# add2 98;;
- : int = 100
# add_str "Test";;
- : string = "Test Test Test Test"
```

函數`twice`使用類型變量`'a`，來指示它可以應用於映射一個類型`'a`到自身的任何`f`，而非只應用於`int->int`函數。特別是，`twice`甚至可以應用於自身：

```OCaml
# let fourtimes f = (twice twice) f;;
val fourtimes : ('a -> 'a) -> 'a -> 'a = <fun>
# let add4 = fourtimes inc;;
val add4 : int -> int = <fun>
# add4 98;;
- : int = 102
```

### 邱奇數

下列代碼定義自然數的邱奇編碼，具有後繼（succ）和加法（add）。邱奇數`n`是接受一個函數`f`和一個值`x`的一個高階函數，它應用`f`到`x`精確的`n`次：

```OCaml
let zero f x = x
let succ n f x = f (n f x)
let one = succ zero
let two = succ (succ zero)
let add n1 n2 f x = n1 f (n2 f x)
let to_string n = n (fun k -> "S" ^ k) "0";;
```

為了將一個邱奇數從函數值轉換成一個字串，這裡把它傳遞給向其輸入和常量字串`"0"`前置上字串`"S"`的函數`to_string`：

```OCaml
# let _ = to_string (add (succ two) two);;
- : string = "SSSSS0"
```

### 對象例子

在OCaml中對象，通過它們的方法的名字和類型，按結構來確定類型。對象可以直接創建（立即對象），而不用通過有名稱的類。例如：

```ocaml
# let x =
    object
      val mutable x = 5
      method get_x = x
      method set_x y = x <- y
    end;;
val x : < get_x : int; set_x : int -> unit > = <obj>
```

這裡OCaml交互式運行時間系統列印出這個對象的推論類型。它的類型`< get_x : int; set_x : int -> unit >`，只由它的方法來定義。換句話說，`x`的類型由方法類型`get_x : int`和`set_x : int -> unit`而非任何名字來定義。類只充當建立對象的函數，例如上例中的對象可以用類來定義，並接著用`new`算符來建立：

```ocaml
# class simple_cls =
    object (self)
      val mutable x = 5
      method get_x = x
      method set_x y = x <- y
    end;;
  let x = new simple_cls;;
```

要定義有相同的方法和方法類型的另一個對象：

```ocaml
# let y =
    object
      method get_x = 2
      method set_x y = Printf.printf "%d\n" y
    end;;
val y : < get_x : int; set_x : int -> unit > = <obj>
```

OCaml將它們視為有相同的類型。例如，等式算符被確定類型為只接受有相同類型的兩個值：

```ocaml
# x = y;;
- : bool = false
```

所有儘管它們有不同的值，卻必定是相同類型的，否則連類型檢查都不會做完。這展示了類型等價是結構性的。可以定義調用一個方法的函數：

```ocaml
# let set_to_10 a = a#set_x 10;;
val set_to_10 : < set_x : int -> 'a; .. > -> 'a = <fun>
```

第一個實際參數的推論類型`< set_x : int -> 'a; .. >`是值得關注的。`..`意味著第一個實際參數，可以是有接受一個`int`作為實際參數的`set_x`方法的任何對象。所以它可以用在對象`x`之上：

```ocaml
# set_to_10 x;;
- : unit = ()
```

另一個對象可以碰巧有這個方法和方法類型；其他方法是無關緊要的：

```ocaml
# let z =
    object
      method blahblah = 2.5
      method set_x y = Printf.printf "%d\n" y
    end;;
val z : < blahblah : float; set_x : int -> unit > = <obj>
```

`set_to_10`函數對它也有效：

```ocaml
# set_to_10 z;;
10
- : unit = ()
```

這展示了對於事物比如方法調用的兼容性是由結構來確定的。下面為只有一個`get_x`方法而沒有其他方法的對象定義一個類型同義詞（synonym）：

```ocaml
# type simpler_obj = < get_x : int >;;
type simpler_obj = < get_x : int >
```

對象`x`不是這個類型的；但在結構上`x`是這個類型的一個子類型，因為`x`包含它的方法的一個超集。所以`x`可以強制（coerce）成這個類型：

```ocaml
# (x :> simpler_obj);;
- : simpler_obj = <obj>
# (x :> simpler_obj)#get_x;;
- : int = 10
```

但是對象`z`不行，因為它不是一個結構子類型：

```console
# (z :> simpler_obj);;
Error: Type < blahblah : float; set_x : int -> unit > is not a subtype of
         simpler_obj = < get_x : int > 
       The first object type has no method get_x
```

這展示了拓寬強制的兼容性是結構性的。

### 任意精度階乘函數

可以從OCaml訪問各種各樣的庫。比如，OCaml有內建的任意精度算術。由於階乘函數增長得非常迅速，會很快溢出機器精度的整數。因此階乘很適合選用任意精度算術。

在OCaml中，`Num`模塊（現在被`ZArith`所取代）提供了任意精度算術，比如在Ubuntu中安裝它：`sudo apt install libnum-ocaml-dev`，它可以如下這樣裝載到運行中的頂層中：

```ocaml
#use "topfind";;
#require "num";;
open Num;;
```

階乘函數可以使用任意精度算符`/`、`*/`和`-/`寫為：

```OCaml
let rec fact n =
  if n =/ Int 0 then Int 1 else n */ fact(n -/ Int 1);;
```

這個函數可以計算非常大的階乘比如`120!`：

```OCaml
# string_of_num (fact (Int 120));;
- : string =
"6689502913449127057588118054090372586752746333138029810295671352301633557244962989366874165271984981308157637893214090552534408589408121859898481114389650005964960521256960000000000000000000000000000"
```

### 繪製圖形例子

下列程序`simple.ml`使用OpenGL呈現一個緩慢旋轉的2D三角形:

```OCaml
let () =
  ignore (Glut.init Sys.argv);
  Glut.initDisplayMode ~double_buffer:true ();
  ignore (Glut.createWindow ~title:"OpenGL Demo");
  let angle t = 10. *. t *. t in
  let render () =
    GlClear.clear [ `color ];
    GlMat.load_identity ();
    GlMat.rotate ~angle: (angle (Sys.time ())) ~z:1. ();
    GlDraw.begins `triangles;
    List.iter GlDraw.vertex2 [-1., -1.; 0., 1.; 1., -1.];
    GlDraw.ends ();
    Glut.swapBuffers () in
  GlMat.mode `modelview;
  Glut.displayFunc ~cb:render;
  Glut.idleFunc ~cb:(Some Glut.postRedisplay);
  Glut.mainLoop ()
```

需要事先安裝負責綁定到OpenGL的LablGL，比如在Ubuntu中安裝它：`sudo apt install liblablgl-ocaml-dev`，這個程序可以如下這樣編譯成字節碼：

```console
$ ocamlc -I +lablGL lablglut.cma lablgl.cma simple.ml -o simple
```

或編譯成本機代碼：

```console
$ ocamlopt -I +lablGL lablglut.cmxa lablgl.cmxa simple.ml -o simple
```

或者簡單的使用`ocamlfind`建造命令：

```console
$ ocamlfind opt simple.ml -package lablgl.glut -linkpkg -o simple
```

然後運行：

```console
$ ./simple
```

可以使用OCaml開發非常複雜、高性能的2D和3D圖形程序。使用OpenGL和OCaml，結果的程序可以跨平台編譯而在主要平台上無需改動。

## 用OCaml寫成的程序

- Coq，一個形式證明輔助器。
- HOL Light，一個形式證明輔助器。
- Coccinelle，用於C程序原始碼程序變換的實用工具。
- Frama-C，分析C程序的一個框架。
- Flow，Facebook創建的用於推論和檢查JavaScript的靜態類型的一個靜態分析器。
- Infer，Facebook創建的用於Java、C、C++和Objective-C的靜態分析器，用來檢測iOS和Android應用中的缺陷。
- pyre-check，Facebook創建的用於Python的類型檢查器。
- Hack程式語言編譯器，Facebook創建，擴展PHP具有靜態類型。
- Haxe程式語言編譯器。
- WebAssembly參考解釋器，它是意圖在web瀏覽器內執行的低層字節碼。
- FFTW，C的FFT庫，它的多數性能關鍵代碼是由用OCaml寫的一個程序生成的。
- Owl科學計算，用於科學和工程計算的專用系統。
- MirageOS，用純OCaml寫的一個單一內核編程框架。
- Ocsigen，一個OCaml的web應用框架。
- Opa (程式語言)，用於Web開發的自由和開源的一個程式語言。
- Zero Install，一個多平台包管理器。
- MLDonkey，一個多網路P2P程序。
- Unison (軟體)，一個文件同步器。

## 參見

- Caml，OCaml的先驅語言。
- F#，由MSR開發，是一個基於OCaml的一個以.NET為目標的程式語言。
- F*，由MSR和INRIA主導開發，是一個基於OCaml的依賴類型函數式程序語言。
- Reason，OCaml的語法擴展和工具鏈，也可以轉譯成JavaScript。

## 外部連結

- OCaml manual
- OCaml Package Manager
- Awesome OCaml

## 基本資料

- 編程范型：多范型：函數式，指令式，模塊化，面向對象
- 語言家族：ML
- 發行日期：1996年
- 類型系統：靜態，強，類型推論
- 設計者：Xavier Leroy, Damien Doligez, Didier Rémy, Jérôme Vouillon
- 開發者：INRIA
- 作業系統：跨平台
- 受影響於：C, Caml, Modula-2, Standard ML
- 施影響於：ATS (程式語言), Coq, Elm, F#, F*, Haxe, Opa (程式語言), Rust, Scala
- dialects：F#, JoCaml, MetaOCaml
- 許可證：GNU寬通用公共許可證