OCaml

Caml程式語言的擴充

OCaml/ˈkæməl/ oh-KAM-əl),是一个函数式指令式模块化[1]面向对象通用编程语言。在Xavier Leroy英语Xavier LeroyDamien Doligez英语Damien Doligez,于1990年和1991年实现的ML方言Caml Light之上[5],Didier Rémy和Jérôme Vouillon,于1996年增加了面向对象特征[2],从而形成了“Objective Caml”[6],在2011年时重命名为“OCaml”[7]

OCaml
编程范型多范型函数式指令式模块化[1]面向对象[2]
语言家族ML
设计者Xavier Leroy英语Xavier Leroy, Damien Doligez英语Damien Doligez, Didier Rémy, Jérôme Vouillon
实现者INRIA
发行时间1996年,​28年前​(1996
当前版本
  • 5.2.0(2024年5月13日;稳定版本)[3]
编辑维基数据链接
类型系统静态类型推论
操作系统跨平台
许可证GNU宽通用公共许可证
网站ocaml.org 编辑维基数据链接
派生副语言
F#, JoCaml英语JoCaml, MetaOCaml[4]
启发语言
C, Caml, Modula-2[1], Standard ML
影响语言
ATS英语ATS (programming language), Coq, Elm, F#, F*, Haxe, Opa英语Opa (programming language), Rust, Scala

OCaml工具链包括交互式顶层解释器字节码编译器、优化的本机代码编译器,可逆调试器和一个包管理器(OPAM)。OCaml最初开发于自动定理证明的场景中,并在静态分析形式方法软件中有超凡的存在感。此外,它在系统编程网页编程金融工程及其他应用领域都有严肃的应用。

历史上,Ascánder Suárez于1987年基于Guy Cousineau法语Guy Cousineau范畴抽象机器英语Categorical abstract machine(CAM)[8],重新实现了Gérard Huet英语Gérard Huet早先的ML方言[9],并用“范畴抽象机语言”的首字母简写将其命名为Caml[10],Caml Light放弃了这个抽象机器又进行了重新实现[11]。OCaml是开放原始码项目,此项目的管理和大部分维护工作,已经交由法国国家资讯与自动化研究所(INRIA)。在2000年代早期,来自OCaml的元素被很多语言接纳,特别是F#Scala

哲学

编辑

ML派生语言最著称的是静态类型系统类型推论编译器。OCaml将函数式指令式面向对象编程统一于类ML的类型系统之下。因此编程者不需要为了使用OCaml而非常熟悉纯函数式编程范型。

通过要求编程者在静态类型系统的约束下工作,OCaml消除了关联于动态类型语言的很多有关于类型的运行时间问题。还有,OCaml的类型推论编译器,极大的减少了在多数静态类型语言中对手工类型标注的需要。例如,变量的数据类型和函数的签名,通常不需要像JavaC#语言中那样显式的声明,因为它们可以从应用于这个变量和代码中其他值的算符和其他函数推论出来。有效的使用OCaml的类型系统可能要求一个编程者面对一些复杂性,但是这种规矩能得到可靠的、高性能软件作为回报。

OCaml与源于学术界的其他语言的最显著区别可能是强调了性能。它的静态类型系统防止了运行时间类型不匹配,从而排除了动态类型语言运行时间类型和安全检查的性能负担,却在除了关闭数组边界检查,和使用一些类型不安全特征比如序列化之外的情况下,仍能保证运行时间安全性。这些运行时间检查需求足够罕见,在实践中完全可以避免。

在类型检查开销之外,函数式编程语言,要编译成高效的机器语言代码,由于如函数参数问题英语funarg problem这样的要点,一般而言是具有挑战性的。与标准的循环、寄存器和指令优化一起,OCaml的优化编译器采用静态程序分析方法,来优化值包装英语Object type (object-oriented programming)(boxing)和闭包分配,帮助结果代码得到最大化的性能,即使它大量使用了函数式编程构造。

Xavier Leroy英语Xavier Leroy曾经宣称:“OCaml至少提供了像样的C编译器的50%的性能”[12],尽管直接比较是不可能的。在OCaml标准库中的一些函数,是采用比在其他语言标准库中等价的函数更快的算法实现的。例如,在OCaml标准库中集合并集的实现,在理论上比指令式语言(例如C++、Java)的标准库中的等价函数,要渐进性的更快,因为OCaml实现利用了集合的不可变性,而在输出中重用了输入集合的一些部分(参见可持久化数据结构)。

特征

编辑

OCaml的特征包括:静态类型系统类型推论参数多态尾递归模式匹配头等词法闭包函子(参数化模块)、例外处理和增量分代自动垃圾回收

OCaml著称于将ML风格类型推论,扩展到通用语言中的对象系统。这允许了结构子类型英语Structural type system,这里的对象类型是兼容的,如果它们的方法签名是兼容的,不用管它们声明的继承,这是在静态类型语言中不寻常的特征。

OCaml提供了链接C原语的外界函数接口英语foreign function interface,包括了兼容于C和Fortran二者格式的对高效数值数组的语言支持。OCaml还支持建立可以链接到用C写的main程序的OCaml函数库

OCaml发行包含了:

本机代码编译器可以在很多平台上获得,包括UnixMicrosoft WindowsApple macOS。可移植性是通过至此主要架构的本机代码生成英语code generation (compiler)实现的:IA-32X86-64(AMD64)、Power英语Power ISARISC-VARMARM64[13]

OCaml字节码和本机代码程序可以用多线程风格书写,具有抢占式上下文切换。但是由于当前唯一可得的语言完全实现INRIA OCaml的垃圾回收器,不是为并发性而设计的,对称多处理是不支持的[14]。在相同进程中的OCaml线程只能分时执行。但是有一些分布式计算库比如Functory[15]和Plasma[16]

代码例子

编辑

OCaml的代码片段可以通过键入到顶层REPL中来很容易的研习。这是一个交互式的OCaml会话,它打印结果或定义的表达式的推论出的类型[17]。OCaml顶层可以通过简单执行OCaml程序来启动:

$ ocaml
        OCaml version 4.13.1

#

可以接着在#提示符处键入代码。例如计算1+2*3:

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

OCaml推论出这个表达式的类型是int机器精度整数)并给出结果7

Hello World

编辑

下面的程序hello.ml:

print_endline "Hello World!"

可以被编译成字节码可执行文件:

$ ocamlc hello.ml -o hello

或者被编译成优化的本地代码可执行文件:

$ ocamlopt hello.ml -o hello

接着执行它:

$ ./hello
Hello World!

给ocamlc的第一个实际参数hello.ml,指定要编译的源文件而-o hello标志指定了输出文件[18]

阶乘函数

编辑

很多数学函数,比如阶乘,可以很自然的表示为纯粹的函数形式:

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

这个函数可以使用模式匹配等价的写为:

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

后者形式是阶乘作为递推关系的数学定义。

编译器将这个函数的类型推论为int -> int,意味着这个函数将int映射到int。例如,12!

# fact 12;;
- : int = 479001600

斐波那契序列

编辑

下列代码计算输入数n斐波那契数列。它使用了尾递归模式匹配

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个人:

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);;
# birthday_paradox 1.0 1;;
answer = 23
- : unit = ()

合计整数列表

编辑

列表是OCaml中的基础数据类型之一。下面的代码例子定义递归函数sum,它接受一个实际参数integers,而它被假定为整数的列表。注意关键字rec指示了这个函数是递归的。这个函数递归的在给定整数列表之上进行迭代,并提供这些元素的一个总和。match语句类似于Cswitch英语Switch statement语句,但要更加一般性。

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

另一种方式是对列表使用标准的fold高阶函数:

let sum integers =
  List.fold_left (fun accumulator x -> accumulator + x) 0 integers;;
# sum [1;2;3;4;5];;
- : int = 15

因为匿名函数是简单的+算符应用,它可以简写为:

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

进一步的,还可以通过采用部分应用英语Partial application省略列表实际参数:

let sum =
  List.fold_left (+) 0

快速排序

编辑

OCaml自身可提供对递归算法的简介表达。下列代码例子实现了类似于以升序排序一个列表的quicksort的一个算法:

 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到它的实际参数两次的一个函数:

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);;
# add2 98;;
- : int = 100
# add_str "Test";;
- : string = "Test Test Test Test"

函数twice使用类型变量'a,来指示它可以应用于映射一个类型'a到自身的任何f,而非只应用于int->int函数。特别是,twice甚至可以应用于自身:

# 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的一个高阶函数,它应用fx精确的n次:

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

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

对象例子

编辑

在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 : intset_x : int -> unit而非任何名字来定义[19]只充当建立对象的函数,例如上例中的对象可以用类来定义,并接着用new算符来建立:

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

要定义有相同的方法和方法类型的另一个对象:

# 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将它们视为有相同的类型。例如,等式算符被确定类型为只接受有相同类型的两个值:

# x = y;;
- : bool = false

所有尽管它们有不同的值,却必定是相同类型的,否则连类型检查都不会做完。这展示了类型等价是结构性的。可以定义调用一个方法的函数:

# 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之上:

# set_to_10 x;;
- : unit = ()

另一个对象可以碰巧有这个方法和方法类型;其他方法是无关紧要的:

# 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函数对它也有效:

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

这展示了对于事物比如方法调用的兼容性是由结构来确定的。下面为只有一个get_x方法而没有其他方法的对象定义一个类型同义词(synonym):

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

对象x不是这个类型的;但在结构上x是这个类型的一个子类型,因为x包含它的方法的一个超集。所以x可以强制(coerce)成这个类型:

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

但是对象z不行,因为它不是一个结构子类型:

# (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,它可以如下这样装载到运行中的顶层中:

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

阶乘函数可以使用任意精度算符=/*/-/写为:

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

这个函数可以计算非常大的阶乘比如120!

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

绘制图形例子

编辑

下列程序simple.ml使用OpenGL呈现一个缓慢旋转的2D三角形:

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,这个程序可以如下这样编译成字节码:

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

或编译成本机代码:

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

或者简单的使用ocamlfind建造命令:

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

然后运行:

$ ./simple

可以使用OCaml开发非常复杂、高性能的2D和3D图形程序。使用OpenGL和OCaml,结果的程序可以跨平台编译而在主要平台上无需改动。

用OCaml写成的程序

编辑

参见

编辑

有关书籍

编辑

引用

编辑
  1. ^ 1.0 1.1 1.2 Xavier Leroy. Manifest types, modules, and separate compilation (PDF). Principles of Programming Languages. 1994 [2021-09-06]. (原始内容 (PDF)存档于2021-10-22). 
  2. ^ 2.0 2.1 Didier Rémy. Type inference for records in a natural extension of ML. Research Report RR-1431, INRIA. 1991 [2021-09-10]. (原始内容存档于2022-04-06). 
    Didier Rémy, Jérôme Vouillon. Objective ML: a simple object-oriented extension of ML (PDF). 1997 [2021-09-06]. (原始内容 (PDF)存档于2022-01-21). 
    Didier Rémy, Jérôme Vouillon. Objective ML: An effective object-oriented extension to ML (PDF). 1998 [2021-09-06]. (原始内容 (PDF)存档于2022-01-20). 
  3. ^ OCaml 5.2.0 Release Notes. [2024年5月24日]. 
  4. ^ MetaOCaml -- an OCaml dialect for multi-stage programming. [2021-08-28]. (原始内容存档于2021-08-29). 
  5. ^ Xavier Leroy英语Xavier Leroy. The Caml Light system Release 0.74, documentation and user's guide. 1997 [2021-09-02]. (原始内容存档于2022-03-08). 
  6. ^ Xavier Leroy. The Objective Caml system release 1.07, Documentation and user's manual. 1997 [2021-09-02]. (原始内容存档于2022-01-23). 
  7. ^ A History of Caml. [2021-09-02]. (原始内容存档于2022-04-13). Our main reason for developing Caml was to use it for sofware development inside Formel. Indeed, it was used for developing the Coq system ……. We were reluctant to adopt a standard that could later prevent us from adapting the language to our programming needs. ……We did incorporate into Caml most of the improvements brought by Standard ML over Edinburgh ML. ……The first implementation of Caml appeared in 1987 and was further developed until 1992. It was created mainly by Ascander Suarez. ……
    In 1990 and 1991, Xavier Leroy designed a completely new implementation of Caml, based on a bytecode interpreter written in C. Damien Doligez provided an excellent memory management system. ……In 1995, Xavier Leroy released Caml Special Light, which improved over Caml Light in several ways. In 1995, Xavier Leroy released Caml Special Light, which improved over Caml Light in several ways. First, an optimizing native-code compiler was added to the bytecode compiler. ……Second, Caml Special Light offered a high-level module system, designed by Xavier Leroy and inspired by the module system of Standard ML. ……Didier Rémy, later joined by Jérôme Vouillon, designed an elegant and highly expressive type system for objects and classes. This design was integrated and implemented within Caml Special Light, leading to the Objective Caml language and implementation, first released in 1996 and renamed to OCaml in 2011.
     
  8. ^ G. Cousineau, P.-L. Curien, M. Mauny. The categorical abstract machine. 1985 [2021-09-03]. (原始内容存档于2021-09-03).  LNCS, 201, Functional programming languages computer architecture, pp.~50-64.
    Michel Mauny, Ascánder Suárez. Implementing functional languages in the Categorical Abstract Machine (PDF). 1986 [2021-09-07]. (原始内容 (PDF)存档于2022-01-28).  LFP '86: Proceedings of the 1986 ACM conference on LISP and functional programming, Pages 266–278.
  9. ^ G. Cousineau, M. Gordon, G. Huet, R. Milner, L. C. Paulson, C. Wadsworth. The ML Handbook, Version 6.2. Internal document. Project Formel, INRIA. July 1985. 
    Christoph Kreitz, Vincent Rahli. Introduction to Classic ML (PDF). 2011 [2021-09-11]. (原始内容 (PDF)存档于2022-01-29). This handbook is a revised edition of Section 2 of ‘Edinburgh LCF’, by M. Gordon, R. Milner, and C. Wadsworth, published in 1979 as Springer Verlag Lecture Notes in Computer Science no 78. ……The language is somewhere in between the original ML from LCF and standard ML, since Guy Cousineau added the constructors and call by patterns. This is a LISP based implementation, compatible for Maclisp on Multics, Franzlisp on VAX under Unix, Zetalisp on Symbolics 3600, and Le Lisp on 68000, VAX, Multics, Perkin-Elmer, etc... Video interfaces have been implemented by Philippe Le Chenadec on Multics, and by Maurice Migeon on Symbolics 3600. The ML system is maintained and distributed jointly by INRIA and the University of Cambridge. 
  10. ^ Guy Cousineau, Gérard Huet英语Gérard Huet. The CAML primer Version 2.6.1. 1990 [2021-09-07]. (原始内容存档于2022-05-04).  RT-0122, INRIA. pp.78.
    Pierre Weis, Maria Virginia Aponte, Alain Laville, Michel Mauny, Ascander Suarez. The CAML reference manual Version 2.6.1. 1990 [2021-09-07]. (原始内容存档于2022-04-06).  [Research Report] RT-0121, INRIA. pp.491.
  11. ^ Xavier Leroy. The ZINC experiment : an economical implementation of the ML language. 1990 [2021-09-06]. (原始内容存档于2022-04-06).  RT-0117, INRIA.
  12. ^ Linux Weekly News页面存档备份,存于互联网档案馆).
  13. ^ ocaml/asmcomp at trunk · ocaml/ocaml · GitHub. GitHub. [2 May 2015]. (原始内容存档于2022-05-07). 
  14. ^ Archives of the Caml mailing list > Message from Xavier Leroy. [2021-09-10]. (原始内容存档于2022-03-31). 
  15. ^ Functory. [2021-08-30]. (原始内容存档于2022-01-20). 
  16. ^ ocamlnet/Plasma. [2021-08-30]. (原始内容存档于2022-03-23). 
  17. ^ OCaml - The toplevel system or REPL (ocaml). ocaml.org. [2021-05-17]. (原始内容存档于2021-09-11). 
  18. ^ Batch compilation (ocamlc)页面存档备份,存于互联网档案馆).
  19. ^ Object types. [2021-09-10]. (原始内容存档于2022-03-10). 
  20. ^ Coq页面存档备份,存于互联网档案馆
  21. ^ Flow: A Static Type Checker for JavaScript. [2021-08-29]. (原始内容存档于2022-04-08). 
  22. ^ Infer static analyzer. [2021-08-29]. (原始内容存档于2022-05-12). 
  23. ^ GitHub - facebook/pyre-check: Performant type-checking for python.. 9 February 2019 [2021-08-29]. (原始内容存档于2022-05-05) –通过GitHub. 
  24. ^ WebAssembly/spec: WebAssembly specification, reference interpreter, and test suite.. World Wide Web Consortium. 5 December 2019 [2021-05-14]. (原始内容存档于2022-05-12) –通过GitHub. 
  25. ^ FFTW页面存档备份,存于互联网档案馆
  26. ^ MirageOS. [2021-08-29]. (原始内容存档于2022-04-20). 
  27. ^ Unison. [2021-08-28]. (原始内容存档于2021-07-12). 

外部链接

编辑