跳轉到

1990：CAML 誕生#

事件#

1990 年，法國國家資訊與自動化研究所（INRIA）的 Gérard Huet、Guy Cousineau、Michel Mauny 等人發表了 CAML——名稱來自 Categorical Abstract Machine Language。CAML 把 Standard ML 的語言設計帶入工業級實作，是 ML 家族從學術原型走向生產環境的關鍵一步，也為 1996 年的 1996-OCaml誕生 鋪路。

語法/特性加入的理論與實用原因#

1. Categorical Abstract Machine（CAM）作為編譯目標#

  • 理論原因：Cousineau、Curien 與 Mauny 在 1980 年代中期設計的 CAM，是一套以範疇論（category theory）為理論基礎的抽象機——lambda 項先編譯為範疇組合子（categorical combinators），再由簡單的堆疊機執行。理論上它提供了 lambda 演算的可執行語意，證明正確性可直接以範疇論論證。
  • 實用原因：CAM 實作簡單、正確性有保證，適合快速打造出可用的 ML 編譯器。
  • 彌補缺陷：當時 ML 實作（Edinburgh ML、LML）多為直譯或實驗性質，缺乏嚴謹又高效的編譯模型。
(* lambda 項 → 範疇組合子 → CAM 指令 *)
(*   λx. x      ⟶  id                        *)
(*   λx. x x    ⟶  dup ; app                 *)
(* CAM 機僅有 hd、tl、swap、cons、cur、app 等少數指令 *)

編譯流程示意：lambda 項先轉為範疇組合子，再由只有少數指令的堆疊機執行——正確性可純以範疇論論證：

原始式   (fun f x -> f x) 5
   ↓ 編譯（lambda 項 → 範疇組合子）
CAM 指令  cur(Snd ; App) ; Push 5 ; App
   ↓ CAM 堆疊機執行（state ⟶ C . S）
結果     5

2. 繼承 Standard ML 的型別與模組設計#

  • 理論原因：CAML 採用完整化的 Hindley–Milner 型別推斷（見 1983-StandardML誕生）與 ML 的模式匹配、代數資料型別，並配備模組系統。
  • 實用原因：Formel 計畫（Formel, 1983–1989）需要 ML 語言發展 Coq 定理證明器的前身（CoC 實作），型別安全與高階函數是形式化驗證的基礎。
  • 彌補缺陷：Edinburgh ML 非正式、可攜性差；法國需要自己的 ML 實作做形式化與教學。

Caml Light 風格的基本函數與模式匹配——完整化 Hindley–Milner 型別推斷的展現：

let rec map f = function
    [] -> []
  | x::l -> f x :: map f l ;;
(* 型別：('a -> 'b) -> 'a list -> 'b，自動推斷 *)

map (function x -> x * x) [1; 2; 3] ;;
(* - : int list = [1; 4; 9] *)

代數資料型別與模式匹配——CAML 用它為 Coq 前身表示語法樹與證明項：

type expr =
    Const of int
  | Var of string
  | Plus of expr * expr ;;

let rec eval env = function
    Const n -> n
  | Var name -> env name
  | Plus (a, b) -> eval env a + eval env b ;;

eval (function "x" -> 5 | _ -> 0) (Plus (Const 3, Var "x")) ;;
(* - : int = 8 *)

列表遞迴是 CAML 的基本慣用法——高階函數與尾遞迴皆可自然表達：

let rec fact n = if n = 0 then 1 else n * fact (n - 1) ;;
(* 尾遞迴版本：不增長堆疊 *)
let fact n =
  let rec loop acc n = if n = 0 then acc else loop (acc * n) (n - 1) in
  loop 1 n ;;

fact 10 ;;
(* - : int = 3628800 *)

3. 工業級實作的可攜性#

  • 理論原因：以 CAM 為中間語言，只要移植 CAM 直譯器即可把整個編譯器帶到新平台——理論上「一次設計、處處實作」。
  • 實用原因：INRIA 的目標是讓 ML 實作能在當時各式工作站與迷你電腦上執行，服務教學與工程。
  • 彌補缺陷：當時 ML 實作速度慢、可攜性差，難以走出學術實驗室。

「一次設計、處處實作」：編譯器只需產生 CAM（或後來的位元組碼）指令，移植時只要重寫那層薄薄的抽象機直譯器：

(* 編譯器架構層次示意 *)
(* Caml 原始程式 → CAM 位元組碼 → 各平台的 CAM 直譯器（數百行 C 即可） *)
(* 對照：直譯式實作需在每個平台重寫整個語意層 *)

後續發展#

  • 1992 年 Caml Light：Xavier Leroy 以位元組碼（bytecode）重寫，捨棄 CAM 抽象機與重型模組系統，打造出輕量、快速、可攜的實作，可執行於一般 PC。
  • 1996 年 OCaml：Didier Rémy 加入物件層，Caml Special Light 演化為 OCaml，成為 ML 家族最成功的工業級語言。

彌補了什麼缺陷#

CAML 彌補了 ML 實作速度慢、可攜性差的缺陷：以範疇論抽象機提供嚴謹而簡單的編譯模型，並由法國自主建立 ML 實作以支撐形式化驗證（Formel 計畫、Coq）與教學。其工業化路線最終結晶於 1996-OCaml誕生。

相關條目#