OCaml

提供: testwiki
ナビゲーションに移動 検索に移動

テンプレート:混同 テンプレート:Infobox プログラミング言語

OCaml(オーキャムル、オーキャメル、旧称: Objective Caml)は、汎用、高水準、マルチパラダイムのプログラミング言語であり、MLのテンプレート:仮リンク方言にオブジェクト指向の機能を追加したものである。1996年にグザヴィエ・ルロワ、テンプレート:仮リンク[1]、テンプレート:仮リンク、テンプレート:仮リンク[2]、Ascánder Suárezらによって開発された。

OCamlのツールチェーンには、対話型のトップレベルインタプリタ、バイトコードコンパイラ、最適化を行うネイティブコードコンパイラ、リバーシブルなデバッガ、パッケージ管理システム(OPAM)、および組み合わせ可能なビルドシステム(Dune)が含まれている。OCamlは当初、自動定理証明の文脈で開発され、静的解析や形式手法のソフトウェアで利用されている。これらの分野を超えて、テンプレート:仮リンク、Web開発、特定の金融ユーティリティなど、様々なアプリケーション領域で活用されている。

名称の「CAML」は元々「Categorical Abstract Machine Language(圏論的抽象機械言語)」の頭字語であったが、OCamlではこの抽象機械を省略している[3]。OCamlはフランス国立情報学自動制御研究所(Inria)によって管理および主に保守されているフリーかつオープンソースのプロジェクトである。2000年代初頭、OCamlの要素は多くの言語、特にF#やScalaなどに採用された。

設計思想

ML派生の言語は、その静的な型システムと型推論コンパイラで最もよく知られている。OCamlは、ML風の型システムの下で関数型、命令型、およびオブジェクト指向のパラダイムを統合している。そのため、プログラマはOCamlを使用するにあたって、純粋関数型言語のパラダイムに精通している必要はない。

プログラマに対し、その静的型システムの制約内で作業することを要求することにより、OCamlは動的型付け言語によく見られる型に関連した実行時の多くの問題を排除する。また、OCamlの型推論コンパイラは、多くの静的型付け言語で必要とされる手動による型アノテーションの必要性を大幅に減らす。たとえば、変数のデータ型や関数のテンプレート:仮リンクは、コード内の変数や他の値に適用される演算子や他の関数から推論できるため、JavaやC#などの言語のように明示的に宣言する必要がない場合が多い。OCamlの型システムを効果的に使用するには、プログラマに一定の熟練が求められることがあるが、この規律は信頼性の高い高性能なソフトウェアという形で報われる。

学術界に起源を持つ他の言語と比較して、OCamlを最も特徴づけているのはパフォーマンスへの重点かもしれない。その静的型システムは実行時の型の不一致を防ぐため、動的型付け言語のパフォーマンスの負担となる実行時の型チェックや安全性チェックを不要にしつつも、テンプレート:仮リンクをオフにした場合や、シリアライズのような型安全でない機能を使用した場合を除いて、実行時の安全性を保証する。これらは極めて稀であるため、実際には避けることが十分に可能である。

型チェックのオーバーヘッドを別としても、関数型言語は一般に、Funarg問題などの問題により、効率的な機械語コードにコンパイルするのが難しい。標準的なループ、レジスタ、命令の最適化に加えて、OCamlのテンプレート:仮リンクは静的プログラム解析手法を用いて値のボクシング(boxing)とクロージャの割り当てを最適化し、関数型プログラミングの構造を多用した場合でも、生成されるコードのパフォーマンスを最大化するよう支援する。

グザヴィエ・ルロワは「OCamlは、まともなCコンパイラの少なくとも50%のパフォーマンスを発揮する」と述べているが[4]、直接的な比較は不可能である。OCamlの標準ライブラリのいくつかの関数は、他の言語の標準ライブラリにおける同等の関数よりも高速なアルゴリズムで実装されている。たとえば、OCaml標準ライブラリにおける集合の和集合の実装は、OCamlの実装が集合の不変性(immutability)を利用して入力集合の一部を出力で再利用できるため(永続データ構造を参照)、理論的には命令型言語(C++、Javaなど)の標準ライブラリにおける同等の関数よりも漸近的に高速である。

歴史

プログラミング言語の原理に関するシンポジウム (POPL)2024で賞を受け取るOCaml開発チーム

ML(Meta Language)の開発

1970年代から1980年代にかけて、イギリスの計算機科学者でありチューリング賞受賞者のロビン・ミルナーは、エディンバラ大学のテンプレート:仮リンクで研究を行っていた[5][6]。ミルナーらは定理証明器の開発に取り組んでおり、これらは歴史的にLispなどの言語で開発されていた。ミルナーは、定理証明器が証明ではないものを組み合わせることで証明が有効であると主張しようとする問題に繰り返し直面した[6]。その結果、彼は自身のテンプレート:仮リンク(LCF)のためのメタ言語(meta language)を開発することになった。これは多相型システムによって、プログラマが有効な証明のみを構築できるようにする言語であった[7]。MLは、異なるマシンでのLCFの使用を簡素化するためにコンパイラへと変えられ、1980年代までにはそれ自体が完全なシステムとなった[7]。MLは最終的にOCamlの基盤として機能することになる。

1980年代初頭、フランス国立情報学自動制御研究所(Inria)のFormelチームがMLに関心を持つきっかけとなるいくつかの進展があった。オックスフォード大学の研究教授であったテンプレート:仮リンクは、自身の「関数型抽象機械(functional abstract machine)」を使用してMLのより高速な実装を開発し、ロビン・ミルナーは様々な実装間の相違を避けるためにMLの新しい定義を提案した。同時に、パリ・ディドロ大学(現・パリ・シテ大学)の上級研究員であったピエール=ルイ・キュリアン(Pierre-Louis Curien)は圏論的コンビネータ(categorical combinators)の計算を開発し、それをラムダ計算に結びつけた。これにより「テンプレート:仮リンク(CAM)」の定義が導かれた。パリ・ディドロ大学の研究者ガイ・クジノー(Guy Cousineau)は、これがMLのコンパイル手法として適用できることを認識した[8]。

初期の実装

テンプレート:仮リンクは、テンプレート:仮リンク率いるInriaのFormelチームによって最初に設計および開発された。Camlの最初の実装は1987年に作成され、1992年までさらに開発が続けられた。開発はAscánder Suárezによって主導されていたが、1988年に彼が去った後はピエール・ワイスとミシェル・モーニー(Michel Mauny)が開発を引き継いだ[8]。

Caml Light

1990年から1991年にかけて、グザヴィエ・ルロワはC言語で書かれたバイトコードインタプリタに基づくテンプレート:仮リンクの新しい実装を設計した。これに加えて、テンプレート:仮リンクはこの実装のために、シーケンシャルなガベージコレクションとして知られるメモリ管理システムを記述した[7]。テンプレート:仮リンクとして知られるこの新しい実装は、古いCamlの実装を置き換え、小型のデスクトップマシンで動作した[8]。その後数年で、ミシェル・モーニーの構文操作ツールなどのライブラリが登場し、教育や研究チームでのCamlの使用を促進するのに役立った[7]。

Caml Special Light

1995年、グザヴィエ・ルロワはテンプレート:仮リンクの改良版であるCaml Special Lightをリリースした[8]。バイトコードコンパイラに最適化されたネイティブコードコンパイラが追加され、これによりパフォーマンスがC++などの主要言語と同等レベルにまで大幅に向上した[7][8]。また、ルロワはStandard MLのモジュールシステムに触発された高水準モジュールシステムを設計した。これにより、抽象化とパラメータ化のための強力な機能が提供され、より大規模なプログラムの構築が容易になった[7]。

Objective Caml

ディディエ・レミとジェローム・ヴイヨンは、オブジェクトとクラスのための表現力豊かな型システムを設計し、それがCaml Special Lightに統合された。これにより、1996年に初めてリリースされたObjective Caml言語が誕生し、後に2011年にOCamlへと改名された。このオブジェクトシステムは、C++やJavaなどの言語では型の不健全性(unsoundness)を引き起こしたり、実行時のチェックを必要としたりするような、普及している多くのオブジェクト指向のイディオムを、静的かつ型安全な方法でサポートしていた。2000年にジャック・ガリグ(Jacques Garrigue)は、多相メソッド、バリアント、ラベル付きおよびオプションの引数など、複数の新機能でObjective Camlを拡張した[7][8]。

継続的な開発

増大するOCamlの商業的および学術的なコードベースをサポートするため、過去20年間にわたり言語の改善が段階的に追加されてきた[7]。2012年のOCaml 4.0のリリースでは、言語の柔軟性を高めるために、一般化代数的データ型(GADT)とファーストクラス・モジュールが追加された[7]。2022年のOCaml 5.0.0リリース[9]は言語ランタイムの完全な書き直しであり、テンプレート:仮リンク(グローバルGCロック)が削除され、限定継続(delimited continuations)を介したテンプレート:仮リンク(effect handlers)が追加された。これらの変更により、それぞれ共有メモリ並列処理と、カラーブラインド並行性(color-blind concurrency)のサポートが可能になる。

OCamlの開発は2005年までInriaのCristalチーム内で行われていたが、その後Galliumチームに引き継がれた[10]。続いて、2019年にGalliumはCambiumチームに引き継がれた[11][12]。2023年現在、コンパイラ配布のコア開発者は様々な組織からの23名で構成されており[13]、幅広いOCamlツーリングおよびパッケージング・エコシステムには41名の開発者がいる[14]。2023年、OCamlコンパイラはテンプレート:仮リンク(ACM SIGPLAN Programming Languages Software Award)を受賞した。

特徴

OCamlは、静的な型システム、型推論、テンプレート:仮リンク、末尾再帰、パターンマッチング、ファーストクラスの静的クロージャ、ファンクタ(パラメータ化されたモジュール)、例外処理、テンプレート:仮リンク(effect handling)、およびインクリメンタルな世代別ガベージコレクションを特徴としている。

OCamlは、汎用言語においてMLスタイルの型推論をオブジェクトシステムに拡張していることで知られている。これにより、宣言された継承に関係なく、メソッドのシグネチャが互換であればオブジェクト型に互換性があるという、テンプレート:仮リンク(structural subtyping)が可能になる(これは静的型付け言語では珍しい機能である)。

CやFORTRANと互換性のある形式の効率的な数値配列(array)の言語サポートを含む、C言語のプリミティブをリンクするためのForeign function interface(FFI)が提供されている。OCamlは、Cの「main」プログラムにリンクできるOCaml関数のライブラリの作成もサポートしており、OCamlの知識がない、またはインストールしていないCプログラマにもOCamlライブラリを配布することができる。

OCamlには、言語の不可分な一部としてのマクロシステム(メタプログラミング)、すなわちプリプロセッサによる前処理の組み込みサポートはないが、OCamlプラットフォームは公式に、そのようなプリプロセッサを記述するためのライブラリをサポートしている。これらには2つの種類がある。1つは(C言語のように)ソースコードレベルで機能するもの、もう1つは抽象構文木(AST)レベルで機能するものである。後者は「PPX」(Pre-Processor eXtensionの略)と呼ばれ、推奨されている方式である。

OCamlのディストリビューションには以下が含まれる:

ネイティブコードコンパイラは、UNIX、Microsoft Windows、Apple macOSを含む多くのプラットフォームで利用できる。主要なアーキテクチャに対するネイティブコード生成のサポートにより、移植性が実現されている:

バイトコードコンパイラは、ネイティブコード生成が利用できない場合でも、Cコンパイラさえあれば、任意の32ビットまたは64ビットアーキテクチャでの動作をサポートする。

OCamlのバイトコードおよびネイティブコードプログラムは、プリエンプティブなコンテキストスイッチを備えたマルチスレッドスタイルで記述できる。同じドメイン[16]内のOCamlスレッドは、タイムシェアリングによってのみ実行される。ただし、1つのOCamlプログラムには複数のドメインを含めることができる。

その他の派生実装および方言

Caml Light

前述の通り、OCamlの前身である実装。正確には名前だけでなく、新しい手法で再実装されたものであり、OCamlよりCaml Lightのほうが古くからある。現在もCaml Lightとして配布され続けている。

MinCaml

MinCamlは、ペンシルベニア大学(当時)の住井英二郎がOCamlで実装した、Caml似のMLの小型版である。同作者により、コンパイラがOCaml自身で書かれている。MinCamlは、2004年度の未踏ソフトウェア創造事業に採択された。

MinCamlコンパイラは教育目的での利用を主眼としている。わずか2000行前後のコードで書かれており、実装されている機能はMLのサブセットである。バックエンドはSPARCとx86に対応しており、ある程度の学習をすれば比較的容易に改造を行うことができる(有志によってPowerPC用に出力できるバージョンも提供されている。バックエンドをLLVMに置き換えた例も報告されている[17])。実際に東京大学理学部情報科学科などで教育目的に利用され、国内におけるOCamlおよび関数型言語の普及と理解に一定の役割を果たしているテンプレート:要出典。

Moscow ML

CamlやOCamlのような方言ではなく、SML(Standard ML)の処理系の実装にCaml Lightを利用している。完全なSMLを実装する。

その他

OchaCamlなど、研究用の改造のベースとして、規模の大きくなったOCamlではなくCaml(Caml Light)を利用する例がみられる。

派生言語

MetaOCaml

MetaOCaml[18] は、実行中に新しい機械語コードのインクリメンタルなコンパイルを可能にする、OCamlのテンプレート:仮リンク拡張である。いくつかの状況下では、多段階プログラミングを使用することで大幅な高速化が可能になる。これは、通常のコンパイル時よりも実行時の方が処理するデータに関する詳細な情報が得られるため、インクリメンタルコンパイラが条件チェックなどの多くのケースを最適化して排除できるためである。

例として、コンパイル時に何らかの冪乗関数x -> x^nが頻繁に必要になることがわかっているが、nの値はランタイム時にしかわからない場合、MetaOCamlでは2段階の冪乗関数を使用できる。

let rec power n x =
  if n = 0
  then .<1>.
  else
    if even n
    then sqr (power (n/2) x)
    else .<.~x *. .~(power (n - 1) x)>.

実行時にnが判明するとすぐに、特化された非常に高速な冪乗関数を作成できる。

.<fun x -> .~(power 5 .<x>.)>.

その結果、以下のようになる。

fun x_1 -> (x_1 *
    let y_3 = 
        let y_2 = (x_1 * 1)
        in (y_2 * y_2)
    in (y_3 * y_3))

新しい関数は自動的にコンパイルされる。

その他の派生言語

プログラム例

以下の例は、プログラム自体としてはMLと比べ特別なものでもないし、オブジェクト指向を活用したものでもないが、OCamlを含むCamlでは旧来のMLやStandard MLからの記法や演算子や名前の変更が多く、簡単なプログラムでもそのままではエラーになるものが多いので、ここではOCamlのコードを示す。

特徴として、型推論の活用により、多くの場合に型の宣言が必要なく、一部の静的型付き言語にありがちな煩雑さがないことが挙げられる。

OCamlのコード・スニペットは、トップレベルの対話型環境(REPL)に入力することで最も簡単に学習できる。これは、結果または定義された式の推論された型を出力する対話型のOCamlセッションである[19]。OCamlのトップレベルは、単にテンプレート:Monoプログラムを実行することで起動する。

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

#

その後、プロンプト "#" にコードを入力できる。例えば、1+2×3を計算するには:

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

OCamlは式の型を "int" (マシン精度の整数型)と推論し、"7" という結果を返す。

Hello World

Hello world の例を示す。以下のプログラムhello.mlは、

print_endline "Hello world!";;

直接実行することができる。

$ ocaml hello.ml

バイトコード実行可能ファイルにコンパイルする場合:

$ ocamlc hello.ml -o hello

最適化されたネイティブコード実行可能ファイルにコンパイルする場合:

$ ocamlopt hello.ml -o hello

実行結果:

$ ./hello
Hello world!
$

ocamlcへの最初の引数である "hello.ml" はコンパイルするソースファイルを指定し、"-o hello" フラグは出力ファイルを指定する[20]。

Option型

OCamlにおけるoption型コンストラクタは、HaskellのMaybe型に似ており、与えられたデータ型を拡張して、そのデータ型の何らかの値(Some)を返すか、何も返さない(None)ようにする[21]。これは値が存在するかしないかを表現するために使用される。

# Some 42;;
- : int option = Some 42
# None;;
- : 'a option = None

以下の関数は、オプションの内部に整数があればそれを抽出し文字列に変換し、なければ空の文字列を返す例である。

let extract o =
  match o with
  | Some i -> string_of_int i
  | None -> "";;
# extract (Some 42);;
- : string = "42"
# extract None;;
- : string = ""

リストの合計

リストはOCamlの基本的なデータ型の1つである。以下のコード例では、整数のリストを引数に取る再帰関数 sum を定義している。関数が再帰的であることを示すキーワードrecに注目してほしい。この関数は与えられた整数のリストを再帰的に反復処理し、要素の合計を提供する。matchステートメントはC言語のswitch文と似ている部分があるが、はるかに汎用性が高い。

let rec sum integers =                   (* キーワード rec は「再帰的」を意味する *)
  match integers with
  | [] -> 0                              (* integers が空のリスト [] の場合は 0 を返す *)
  | first :: rest -> first + sum rest;;  (* integers が空でないリストの場合は再帰呼び出し。
                                            first はリストの最初の要素、
                                            rest は残りの要素のリスト([] の場合もある) *)
  # sum [1;2;3;4;5];;
  - : int = 15

別の方法として、リストに対して機能する標準的なテンプレート:仮リンクを使用することもできる。

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

さらに、テンプレート:仮リンクを利用することでリストの引数を省略することもできる。

let sum =
  List.fold_left (+) 0

クイックソート

OCamlは再帰的なアルゴリズムを簡潔に表現するのに適している。以下のコード例は、リストを昇順にソートするクイックソートに似たアルゴリズムを実装している。Haskellなどにも見られるパターンマッチの機能がここでも使われている。

 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

または、テンプレート:Mono演算子の部分適用を使用する。

 let rec qsort = function
   | [] -> []
   | pivot :: rest ->
     let is_less = (>=) pivot in
     let left, right = List.partition is_less rest in
     qsort left @ [pivot] @ qsort right

誕生日のパラドックス

以下のプログラムは、部屋にいる人全員の誕生日が完全に異なる確率が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

チャーチ数

以下は、ラムダ計算の教科書などに見られる、自然数のテンプレート:仮リンクのコード例である。後者(succ)および加算(add)が定義されている。チャーチ数nは、関数fと値xを受け取り、xに正確にn回fを適用する高階関数である。チャーチ数を関数値から文字列に変換するために、入力に文字列"S"を先頭に追加する関数と、定数文字列"0"を渡す。以下の例では、5のチャーチ数として"SSSSS0"を出力する。

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"
let church_5 = to_string (add (succ two) two)
;;
print_endline church_5;

任意精度階乗関数(ライブラリ)

様々なライブラリにOCamlから直接アクセスできる。たとえば、OCamlには任意精度演算のための組み込みライブラリがある。階乗関数は非常に急速に増加するため、すぐにマシン精度の数値(通常は32ビットまたは64ビット)をオーバーフローする。したがって、階乗は任意精度演算の適切な候補となる。

OCamlでは、Numモジュール(現在はZArithモジュールに置き換えられている)が任意精度演算を提供しており、次のように入力することで実行中のトップレベルに読み込むことができる。

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

すると、任意精度数値演算子=/, */, -/を使用して階乗関数を記述できる。

# let rec fact n =
    if n =/ Int 0 then Int 1 else n */ fact(n -/ Int 1);;
val fact : Num.num -> Num.num = <fun>

この関数は、120!のようなはるかに大きな階乗を計算できる。

# string_of_num (fact (Int 120));;
- : string =
"6689502913449127057588118054090372586752746333138029810295671352301633
55724496298936687416527198498130815763789321409055253440858940812185989
8481114389650005964960521256960000000000000000000000000000"

三角形(グラフィックス)

以下のプログラムは、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バインディングが必要である。その後、プログラムは以下のようにバイトコードにコンパイルできる。

$ 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のおかげで、結果として得られるプログラムはクロスプラットフォームになり、変更を加えることなく多くの主要プラットフォームでコンパイルできる。

フィボナッチ数列

以下のコードは、入力された数値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

高階関数

関数は関数を入力として受け取り、結果として関数を返すことができる。たとえば、twiceを関数fに適用すると、引数にfを2回適用する関数が生成される。

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を使用して、int->int関数だけでなく、型'aからそれ自身へのマッピングを行う任意の関数fに適用できることを示している。特に、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

OCamlで書かれたソフトウェア

ユーザー

少なくとも数十の企業がある程度OCamlを使用している[28]。代表的な例として以下の企業が挙げられる。

学術教育および研究の文脈において、OCamlは大学やカレッジのコンピュータサイエンス教育プログラムで顕著な存在感を示している。教育リソースとこれらの教育プログラムのリストは、ocaml.orgで確認できる。

参考文献

脚注

テンプレート:Reflist

関連項目

外部リンク

テンプレート:プログラミング言語一覧

テンプレート:Authority control テンプレート:Normdaten