プログラミング言語のひとつであるOCamlで簡単なプログラムを書いてみる。

環境

Ubuntu 16.04.2 LTS 64bit版、OCaml 4.02.3

$ uname -a
Linux vm-ubuntu64 4.4.0-66-generic #87-Ubuntu SMP Fri Mar 3 15:29:05 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux

$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 16.04.2 LTS
Release:        16.04
Codename:       xenial

$ ocaml -version
The OCaml toplevel, version 4.02.3

OCamlの概要

OCamlはINRIA（フランス国立情報学自動制御研究所）によって開発されたプログラミング言語であり、関数型言語MLの方言であるCamlにオブジェクト指向の要素が取り入れられたものである。他の関数型言語と同様に、静的な型システム・型推論、パターンマッチ、末尾呼び出し最適化等を備えている。

関数型言語として比較的近いものにHaskellがあるが、Haskellとの違いのひとつに評価戦略がある。 Haskellが遅延評価であるのに対し、OCamlは正格評価である。遅延評価には不必要な計算が行われないという利点がある一方で、未評価の式（thunk）が溜まるとパフォーマンスが落ちる（スペースリーク）という難点がある。 OCamlは正格評価であるため、正格評価を行う多くのプログラミング言語と同様に考えることができる。なお、Haskellがseqや$!で正格評価を扱うことができる（参考）ように、OCamlもlazyによって遅延評価を扱うことができる。

OCamlが使われているプロジェクトとしては、以下が挙げられる。

OMake（ビルドシステム）
Haxe（AltJS）
Facebook Hack（PHP互換言語）
Facebook Flow（JavaScript型チェッカ）
Facebook Infer（静的コード解析ツール）
MirageOS（Unikernel）
Binary Analysis Platform（プログラム解析フレームワーク）
WebAssemblyインタプリタのリファレンス実装

OCamlのインストール

Install OCaml – OCaml

Ubuntuの場合、標準リポジトリからパッケージをインストールできる。 ocaml-noxはX11サポートなし、ocamlはX11サポートありである。

$ sudo apt install ocaml-nox

なお、OCamlにはパッケージマネージャとしてOPAMがあるが、ここではインストールしないことにする。

ocamlコマンドでインタプリタを起動し、適当な計算を行ってみる。インタプリタでは、;; で式の終わりを表す。

$ ocaml
        OCaml version 4.02.3

# let rec sigma a b f =
    if a > b then 0 else f a + sigma (a+1) b f;;
val sigma : int -> int -> (int -> int) -> int = <fun>
# sigma 1 10 (fun x -> x*x);;
- : int = 385
# [Ctrl+D]

上のコードでは、Σ_{i=1}^10 i^2 = 1^2 + 2^2 + ... + 10^2 = 385 を計算している。 OCamlにおいて、再帰関数は明示的に let rec で定義する。また、匿名関数（ラムダ式）は (fun PARAMETER_1 ... PARAMETER_n -> EXPR) と書く。

簡単なプログラムを書いてみる

プログラムの例として、素因数分解を行う factor.ml を書いてみる。

let rec factor n =
  if n < 2 then []
  else if n mod 2 = 0 then 2 :: factor (n/2)
  else if n mod 3 = 0 then 3 :: factor (n/3)
  else (
    let rec factor_gt d n =
      if n < d*d then [n]
      else if n mod d = 0 then d :: factor_gt d (n/d)
      else if n mod (d+2) = 0 then (d+2) :: factor_gt d (n/(d+2))
      else factor_gt (d+6) n in
    factor_gt 5 n
  )

let () =
  if Array.length Sys.argv < 2 then (
    Printf.printf "Usage: %s N\n" Sys.argv.(0);
    exit 1
  );
  let n = int_of_string Sys.argv.(1) in
  (* let n = int_of_string (read_line ()) in *)
  let factors = factor n in
  Printf.printf "%d: %s\n" n (String.concat " " (List.map string_of_int factors));

factor は一通り2と3で割った後、平方根以下の適当な整数で試し割りを行う関数である。 OCamlにはC言語におけるmain関数のような概念がないため、慣習的に let () = ... 等でエントリポイントが表わされる。ローカル変数の定義は let X = A in ... の形の式として表し、連続する式はシークエンス演算子 ; で区切って並べる。また、コメントは (* *) で表し、C++における // のような1行コメントはない。

ocamloptコマンドで実行ファイルにコンパイルし、実行してみると次のようになる。

$ ocamlopt factor.ml -o factor

$ file factor
factor: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=4a20beb80735f3abf4a7f6d85b343a7a737fcb87, not stripped

$ ./factor 360
360: 2 2 2 3 3 5

$ time ./factor 4611686018427387903
4611686018427387903: 3 715827883 2147483647

real    0m2.469s
user    0m2.464s
sys     0m0.004s

$ factor 4611686018427387903
4611686018427387903: 3 715827883 2147483647

上の結果から、正しく実行ファイルにコンパイルされ、素因数分解できていることが確認できる。

なお、64 bit環境においてOCamlのintは63 bit符号付き整数であり、-2⁶²から2⁶²-1までの値となる。 64 bitのうちの1ビットは内部でガベージコレクション用に利用される。

$ ./factor 4611686018427387904
Fatal error: exception Failure("int_of_string")

$ python
Python 2.7.12 (default, Nov 19 2016, 06:48:10)
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> bin(4611686018427387904)
'0b100000000000000000000000000000000000000000000000000000000000000'
>>> len(_)-3
62
>>> [Ctrl+D]

関数型プログラミングで書いてみる

パターンマッチや関数合成を使ったプログラムの例として、上と同じ内容の factor_fp.ml を書いてみる。

let rec factor_by d = function
  | n :: factors when n > d && n mod d == 0 -> factor_by d ((n/d) :: d :: factors)
  | ns -> ns

let factor n =
  let rec factor_gt d = function
    | n :: factors when n < d*d -> n :: factors
    | ns -> factor_by d ns |> factor_by (d+2) |> factor_gt (d+6) in
  if n < 2 then []
  else List.rev (factor_by 2 [n] |> factor_by 3 |> factor_gt 5)

let () =
  if Array.length Sys.argv < 2 then (
    Printf.printf "Usage: %s N\n" Sys.argv.(0);
    exit 1
  );
  let n = int_of_string Sys.argv.(1) in
  (* let n = int_of_string (read_line ()) in *)
  let factors = factor n in
  Printf.printf "%d: %s\n" n (String.concat " " (List.map string_of_int factors))

暗黙の引数を取るパターンマッチ関数は function と | P -> ... を使って定義する。ガード節は when ... で表し、後続の条件を満たす場合のみマッチさせることができる。また、f x |> g はいわゆるパイプライン演算子（Reverse-application operator）であり、g (f x) と等価である。

ocamloptコマンドで実行ファイルにコンパイルし、実行してみると次のようになる。

$ ocamlopt factor_fp.ml -o factor_fp

$ ./factor_fp 360
360: 2 2 2 3 3 5

$ time ./factor_fp 4611686018427387903
4611686018427387903: 3 715827883 2147483647

real    0m2.966s
user    0m2.960s
sys     0m0.004s

$ factor 4611686018427387903
4611686018427387903: 3 715827883 2147483647

上の結果から、多少効率は落ちているものの、同じ結果が得られていることが確認できる。

クラスを使ったプログラムを書いてみる

OCamlらしいプログラムの例として、クラスを使った oop_example.ml を書いてみる。

class virtual animal (name : string) = object(self)
  val mutable name = name
  method set_name new_name = name <- new_name
  method virtual cry : unit
end

class dog name = object(self)
  inherit animal name
  method cry = Printf.printf "%s: bowwow\n" name
end

class cat name = object(self)
  inherit animal name
  method cry = Printf.printf "%s: meow\n" name
end

let () =
  let dog = new dog "Snoopy" in
  let cat = new cat "Kitty" in
  dog#cry;
  cat#cry;
  dog#set_name "Pochi";
  cat#set_name "Tama";
  dog#cry;
  cat#cry

animal#cry のような仮想メソッドを持つクラスには、クラス本体にも virtual キーワードを付ける必要があることに注意する。

コンパイルして実行すると次のようになる。

$ ocamlopt oop_example.ml -o oop_example

$ ./oop_example
Snoopy: bowwow
Kitty: meow
Pochi: bowwow
Tama: meow

更新履歴

2021/12/13: 素因数分解のコード・関連リンクを修正、関数型プログラミングの項を追記

環境