OCaml 標準ライブラリ探訪 #1: Pervasives: 最も使われてるのに最も名前が知られていない奴

OCaml Tutorial

関連リンク:
OCaml 標準ライブラリ探訪 #0


標準ライブラリ探訪第一回は Pervasives です。

OCaml ソースファイルを持っている場合には ${srcdir}/stdlib/pervasives{.ml,.mli}、ライブラリディレクトリを見ている場合には ${libdir}/pervasives{.ml,.mli} *1 を見てください。

ところで、Pervasives って単語、知ってましたか？私はいまだに OCaml 以外でこの単語を見たことがありません。"pervert" じゃないですよ、"pervasives" です:

Pervasives : [adj] 行き渡る、普及する、広がる傾向にある、(全面的に)広がる、拡散的な、広範囲な、まん延する

英辞郎

なんだかよくわかりませんね。でも、 Pervasives モジュールは OCaml で最もよく使われるモジュールで、触れておくべき点が多々あります。第一回目ですが、避けて通れません。

常に open されている Pervasives

Pervasives モジュールには OCaml を使うにあたっての超基本的な関数である四則演算、入出力、例外、そしてそれらに関係するデータ型が定義、宣言されています。これらの関数群は非常に頻繁に使われますから、簡便のために Pervasives モジュールは常に open された特殊な状態になっています。例えば、print_string 関数は Pervasives で宣言されていますが、ocaml インタプリタを立ち上げた直後から Pervasives モジュール名無しで使用することが可能です。わざわざ open Pervasives とか、 Pervasives.print_string とか書かなくて構いません。

$ ocaml
        Objective Caml version 3.11.1

# print_string "hello world\n";;
hello world
- : unit = ()

このような特別な扱いを受けているため、Pervasives で定義されている型や関数はよく使うのに、そのモジュール名はさほど知られていません。Pervasives で定義、宣言されている関数は当然重要な物ばかりです。

external 宣言 : プリミティブ関数

OCaml 標準ライブラリ、特に Pervasives で目につくのが

external 関数名 : 型 = "ほにゃら"

という external 宣言です。external 宣言された関数には OCaml での実装が与えられていません。例えば pervasives.mli の先頭に出てくる

external raise : exn -> 'a = "%raise"

これと対応する宣言を実装 pervasives.ml で探してみると、やはり、

external raise : exn -> 'a = "%raise"

となっていて、型と謎の文字列 "%raise" が宣言されているだけです。

external は OCaml の外で定義されているプリミティブや C言語で定義された関数を OCaml で使うための橋渡しをするための宣言で、等号右の謎の文字列は、

  • % で始まっていればプリミティブ (% なのは多分 'P'ercent と 'P'rimitive の頭文字が同じだからでしょう)
  • それ以外は Cの関数名

になっています。例えば "%raise" は OCaml プリミティブの Lambda.Praise という命令に相当します。

プリミティブ名とプリミティブの対応については ${srcdir}/bytecomp/translcore.ml を参照してください。

普通のユーザーにとって、external 宣言は C言語で書かれた外部ライブラリとのインターフェースを作る時に主に使う位で、それ以外は使う必要がありません。唯一の例外は "%identity" プリミティブでしょうか。内部表現が同じ二つの型の間で値を変換(C言語でのキャストに相当)するときに "%identity" をよく使います。例えば、Perversives にも、

external int_of_char : char -> int = "%identity"
(** Return the ASCII code of the argument. *)

という型変換が宣言されています。

この "%identity" プリミティブは ADT( Abstract Data Type, 抽象データ型)の実装にも便利です。次の例では、モジュール M の実装内で int list 型を t として定義し、その実装を M のシグナチャでは隠蔽しています。抽象型 t と int list との関係は M のシグナチャでは隠蔽されていますが実は同じ物ですから、両者間の変換に "%identity" を使用できます:

module M : sig 
  type t (* abstracted *)
  external of_int_list : int list -> t = "%identity"
  ...
end = struct
  type t = int list
  external of_int_list : int list -> t = "%identity"
  ...
end

もちろんこれは "%identity" を使わなくても普通の identity(恒等)関数 fun x -> x でも実装できます:

module M : sig 
  type t (* abstracted *)
  val of_int_list : int list -> t
  ...
end = struct
  type t = int list
  let of_int_list t =  t
  ...
end

しかしこのバージョンでは external ..."%identity" を使った物と比べ変換時に関数の呼び出しを行うため少し遅くなってしまいます。"%identity" のバージョンではコンパイラは関数 M.of_int_list が identity である事を知っているので関数呼び出しを行わず、コスト無しで変換が可能です。

ocaml や ocamlc に -dlambda オプションを付けると、コンパイル結果を見ることが出来ます。-dlambda 付きで、

let identity x = x 
let _ = identity 42

と

external ext_identity : 'a -> 'a = "%identity" 
let _ = ext_identity 42

を比べると後者のコンパイルが明らかに早そうだということが判ります。

実装(.ml)内で external 宣言された関数でも、インターフェース(.mli)では普通の値として val を使って宣言することが可能ですが、お薦めしません。M の外部からは普通の関数として見なされることで、 external 宣言によって得られる最適化効果が失われてしまうからです。次の例では折角の external of_int_list 宣言が無駄になっています。

module M : sig 
  type t (* abstracted *)
  val of_int_list : int list -> t
  ...
end = struct
  type t = int list
  external of_int_list : int list -> t = "%identity"
  ...
end

便利な external 宣言ですが、external 宣言された値の型安全性は保証されていないので、細心の注意を払って使用しなければいけません。例えば "%identity" の場合は、もし型間の内部表現が異なればプログラムの誤動作の原因になります:

# external id : int -> float  = "%identity";;
external id : int -> float = "%identity"
# id 1;;
Segmentation fault

Predefined types, exceptions

Pervasives は他のモジュールの値や型を使っていないもっとも基本的なモジュールです。でも、その中では int, float 等の基本型、* や　-> などの型コンストラクタ、list, option などのデータ型、そして基本的な例外 (Failure, Invalid_argument など)を断りもなく使っています。定義が見つかりません。これらの型や例外は predefined type や exception として OCaml コンパイラが起動した時点でその型環境にすでに定義された状態になっています。

Predefined な物は型と例外、そのコンストラクタだけです。predefined な値の束縛はありません。

Predefined types, exceptions の情報や内部表現は ${srcdir}/typing/predef{.ml,.mli} にあります。

機能別 Pervasives 関数紹介

前置きが長くなりました。Pervasives の関数を機能別に見ていきましょう。.mli のコメントの翻訳をするつもりはありません。あくまで役に立つ追加情報を扱います。

例外 Exceptions

基本的な例外、Invalid_argument, Failure, Exit を扱っています。これらは普通次の目的で使われます:

  • Invalid_argument: 関数が想定外の引数を受け取ったとき、その関数名を引数にした Invalid_argument をよく使う。例えば、正整数しか受けとるはずのない関数が負整数を受け取ったときのエラー処理に。
  • Failure: 何かとにかく失敗したとき、エラーメッセージを引数に。
  • Exit: エラーではないがループなどから例外を使って大域脱出したいとき

もちろんこれは習慣であって、これ以外の使い方をしてはいけない訳ではありませんが、OCaml プログラマの基本慣習なのでできるだけ守った方がよいでしょう。

invalid_arg や failwith はそれぞれ Invalid_argument と Failure の例外を発生させるための関数ですが、実装を見れば、何のことはない、raise を使ってそれぞれの例外を発生させるだけです。ただ、実の所上級者はあまり使いません、なぜなら、failwith (Printf.sprintf "Error: %s" mes) の様に、ほとんどいつも Printf.sprintf と組に使うからです。この繰り返しを避けるために、よく次の failwithf (と invalid_argf) を自分で定義するなり、外部ライブラリをリンクして、printf スタイルのインターフェースで使うことが多いです。

val failwithf : ('a, unit, string, unit -> 'b) format4 -> 'a = <fun>

let failwithf fmt = Printf.kprintf (fun s () -> failwith s) fmt;;

この連載ではしばしば関数の定義と型を示すために上のような書き方をします。上はシグナチャ(.mli)、下は定義(.ml)。この二行をそのまま .ml に書いてもエラーになることに注意してください。

Printf.kprintf を使った　printf スタイルの関数の定義テクニックについては Printf モジュールで詳しく説明する予定です。(まぁ上に挙げたように kprintf を使えば printf スタイルの関数が定義できる、ということだけなのですが)

多相比較 Polymorphic comparison

OCaml 七大不思議の一つ、多相比較です。OCaml では普通の構造比較演算子 (=), (<>), (<), (<=), ポインタ比較演算子 (==), (!=) などすべて、

(比較) : 'a -> 'a -> bool

という型を持っています。この 'a -> 'a -> bool という polymorphic (多相的)な型は、建前上は、どんな型でも、比較演算子の左右の型が同じなら、比較することができる、という意味です。ポインタ比較はまだしも、普通の比較でそんなことが出きるのは実は結構不思議なことなのです。例えば option 型の None と Some _ の間に誰が定義した訳でもないのに大小関係があります:

# None < Some 1
- : bool = true
# Some 1 < Some 2;;
- : bool = true

種明かしをすると OCaml では、型とは独立した、値の内部表現だけを利用した決め打ちの大小関係が定義されおり、これを使ってこれらの多相比較演算子は定義されています。ただ、closure(クロージャ,関数値)だけは対象外です。Closure を比較すると Invalid_argument 例外が発生します。

決め打ちの大小関係がどう定義されているかは、OCaml の値の内部表現と密接に関係しており、詳しくは述べません。ここではごく簡単な説明に止めます。

  • 引数の無い variant constructor(バリアント構成子)同士は定義順。 
# type t1 = A | B;;
type t1 = A | B
# A < B;;   (* A の方が先に定義されている=小さい *)
- : bool = true
  • 引数のある variant constructor 同士も定義順。
# type t2 = A of int | B of float;;
type t2 = A of int | B of float
# A 10000 < B 0.0;;
- : bool = true
  • 同じ引数のある variant constructor 同士は引数の大小で決まる。
# A 10000 < A 10001;;
- : bool = true
  • 引数の無い variant constructor < 引数のある variant constructor。
# type t3 = A of int | B;;
type t3 = A of int | B
# A 100000 < B;;    (* A が先に定義されているが、引数がある *)
- : bool = false
  • レコード、タプルは型定義に出てくる初めの要素の大小関係が優先される。
# type t4 = { x : int; y : int };;  (* ここでの順序が重要 *)
type t4 = { x : int; y : int; }
# { y = 1000; x = 0 } < { x = 10; y = 0 };;  (* 使用する際の順序は関係ない *)
- : bool = true

この多相比較は奇妙ですが、なかなかよく出来ており、新しいデータ型を定義しても、普通はその型の大小比較関数を書く必要はあまりありません。これは多重定義がなく、同じ大小比較演算子に型によって別々のアルゴリズムを割り振る事が出来ない OCaml には必須の機能と言えるでしょう。

compare 比較関数

compare もやはり polymorphic comparison ですが、大小比較の結果を bool ではなく、 -1 (左辺が小さい), 0(同じ), 1(右辺が小さい)の int で返す関数です。この関数は Set.Make などの値のソートアルゴリズムを与える必要がある functor 適用でよく使います。(詳しくはそれぞれのモジュール解説で行います。)

多相比較関数の型よるコンパイルの変化

多相比較関数にもちょっとした最適化に関わるテクニックがあり、知っておいて損はありません。int, float, int32 など、数値に関わる大小比較で、compare や他の多相比較関数を使う場合、引数の型を明示的に指定するとプログラムが早くなる場合があります:

val cntr : int ref
val compare_and_count : 'a -> 'a -> unit

let cntr = ref 0 
let compare_and_count x y = 
  match compare x y with
  | -1 -> decr cntr
  | 0 -> ()
  | 1 -> incr cntr
  | _ -> invalid_arg "compare_and_count"

val cntr : int ref
val compare_and_count' : int -> int -> unit

let cntr = ref 0 
let compare_and_count' x y = 
  match compare (x : int) y with
  | -1 -> decr cntr
  | 0 -> ()
  | 1 -> incr cntr
  | _ -> invalid_arg "compare_and_count'"

上の二つの関数をループにでも入れて回してみればわかりますが、型が違うだけなのに、下の方が効率がよいのです。これは compare 関数のコンパイルが使用されている型によって異なるからです。上の compare では全体として多相関数となっているために、compare はどんな型の値がくるかわかりません。どんな型の値でも比較できるよう、万能型の比較プリミティブにコンパイルされます。他方、下の例では compare は int の比較しか行わないことが型から明かです。コンパイラはその情報を利用して compare を int を比較する事に特化したより早い比較プリミティブにコンパイルすることができるのです。

この compare に明示的な型制限を加えてより早いプリミティブへのコンパイルを促すテクニックはこれまた Set.Make や Hashtbl.Make など、大小関係や等号関係を内部で多用するアルゴリズムやモジュールでは非常に重要になってきます。是非数値の集合や hash table を作る際には compare に型を明示しましょう。

(* ダメな例 *)
module M = struct
  type t = int
  let compare = compare   (* 多相なまま、、、これでは遅い! *)	
end

module IntSetSlow = Set.Make(M)

(* 良い例 *)
module M' = struct
  type t = int
  let compare (x : int) y = compare x y   (* int 専用比較が使われる *)
end

module IntSetFast = Set.Make(M')

このコンパイルの違いは、ocaml, ocamlc に -dlambda オプションを付けることで出力されるコンパイル後の内部表現を見るとより詳しくわかります。

数値演算子

数値演算子は、これまた OCaml 七大不思議の一つ。(後の五つは考えてません。まー何かあるでしょう。) 多重定義されていないので int と float、そして他の数値型、それぞれに別名の演算子を使わなければいけません。めんどうですね。

external ( + ) : int -> int -> int = "%addint"
(** Integer addition. *)

external ( +. ) : float -> float -> float = "%addfloat"
(** Floating-point addition *)

多相比較のように (+) に 'a -> 'a -> 'a な型を与え、型が静的に判る場合、例えば 1 + 1 とか、1.2 + 3.4 はそれぞれのプリミティブ "%addint", "%addfloat" にコンパイル。それ以外の場合、例えば let double x = x + x では、(+) の型がその場では判らないので、内部表現によって場合分けをする "%add多相" にコンパイル、という事もできないわけではありません。しかし、多相比較と異なり、数値型以外の自然な「数値」演算は自明に与えることはできません。多相構造比較が closure を受け取った場合に Invalid_argument 例外を発生させるように、

# Some 1 + None;;
Exception: Invalid_argument "+".

としても良いですが、多層構造比較の場合と違って数値型以外しか受け取れない関数に 'a という多相型を与えるのは無理があります。

他にも、OCaml ランタイムが整数とゼロ引数 variant constructor の内部表現を区別できないという問題もあり、この多相(+)のアプローチは無理があります。

type t = A | B | C | D
let answer = (Obj.magic (+) : t -> t -> t) B C;;

を試してみてください。OCaml ランタイムでは最適化のため、 A, B, C, D と 0, 1, 2, 3 を区別していません。そのため、多相(+)は B + C を 1 + 2 と区別できず、これを実行時にエラーにして Invalid_argument 例外を投げることができません。

このような問題があるため、 OCaml では非常に簡単に、int 用と float 用、そしてその他の数値型用の別個の演算子をそれぞれ用意してやるという方法を採用しています。確かに float の演算子に .(dot) を付け忘れていてコンパイラに文句を言われるのはムッとくる物がありますが、、、

この数値演算子の問題は 、他の関数型言語では次のようなアプローチを取っています:

  • SML では数値演算子を特別扱いにして、上の "%addint", "%addfloat" などに変換できる場合にのみ受け付ける。double の様に型が決まらない場合は多相型にせず、int の演算と見なし、"%addint" を使ってみたりする。
  • Haskell では、多相型 'a -> 'a -> 'a に制限 (type class) を入れて、数値型のみを受け付ける多相型 Num 'a => 'a -> 'a -> 'a にして、非数値型の数値演算子への適用を禁止する。

それぞれ一長一短があります。SML の場合は簡単で良いのですが、double の取扱いがすっきりしない。だからといって Haskell のようにすると double のコンパイルに dictionary dispatching が必要になりパフォーマンスの問題が出てきます。もちろん最適化を頑張ったりする余地もあるのですが、、、

これは私の推測ですが、OCaml が非常に単純な解法を取ったのは、まず第一に数値演算子という非常に基本的な言語要素に理解の難しい型機構を入れるのは教育上どうだろうと理由だったのではないでしょうか。現在でも caml-light はフランスの情報学科で広く使われている言語です。そこで、(+) の型が何だか変だ、double が定義できません、とか、なんですかこの Num 'a => というのは？という質問を毎年受けたくはないのでは無いでしょう？私は嫌です(笑)。

第二の理由、これも推測ですけれども、OCaml はコード上に見えない所で妙な overhead がかかるのを嫌う言語です。言語仕様を単純化しておいて、ランタイムが早いものを用意すれば、特に超絶的最適化コンパイルを行わなくても結構早い言語が作れるよ、というのが OCaml の売り。また、Haskell の dictionary dispatch は、implicit な abstraction を導入するため、副作用のタイミングとの相性もよくありません。

ignore

ignore の型は、'a -> unit。受け取った値を忘れて、unit を返します。関数適用の返り値が必要ない時に便利ですね:

let calculate () =
  prerr_endline "Hit Enter to start calculation:";
  ignore (read_line ());
  let rec fib = function
    | 1 | 2 -> 1
    | n -> fib (n-1) + fib (n-2)
  in
  fib 35

上の例ではエンターキーを待つために read_line : unit -> string を使っています。ただリターンが押されるまでプログラム実効を止めたいだけなので、read_line () 返り値には興味がありません。そこで ignore を使っています。

実は、この ignore は書かなくても構いません:

let calculate () =
  prerr_endline "Hit Enter to start calculation:";
  read_line ();
  let rec fib = function
    | 1 | 2 -> 1
    | n -> fib (n-1) + fib (n-2)
  in
  fib 35

ただし、read_line () の所でコンパイラが警告を発します:

Characters 73-85:
    read_line ();
    ^^^^^^^^^^^^
Warning S: this expression should have type unit.

なぜ警告が出るのでしょうか。read_line () はせっかく何か文字列を返しているのに、それを利用せずにいるからです。普通、関数を呼び出して何か unit 以外の結果が返ってきた場合はそれを利用して計算を続けるのが普通ですが、それを無視してしまっている、これはどうも不自然だ、というわけです。

一番始めの例の様に、ignore を使って ignore (read_line ()) と書けば、この警告は消えます。ignore (f x) はコンパイラに、f x の結果は私は本当に興味が無いんですよ、だから文句は言わないでください、と伝える手段だと思えば良いでしょう。

fst, snd

fst, snd は 'a * 'b という二つ組からそれぞれ一つ目、二つ目の要素を返す関数です。名前が短いのは、、、まあタイピングが面倒だからでしょうか。

残念ながら三つ組以上の tuple(組)から要素を取り出してくる関数は OCaml にはありません。また任意の数の要素を持つ tuple から n 番目の要素を返す SML の #n のような機能もありません。数値演算子が多相型を持たない理由と同じく、 #n には fst や snd のような単純な型を与えることが出来ないからです。三つ組以上の tuple から要素を取り出すにはパターンマッチを使ってください:

val get_color_at_pixel : int -> int -> int * int * int  (* 画像のある点から色を取り出す関数だと思ってください *)

let r,g,b = get_color_at_pixel 0 0    (* パターンマッチで tuple を分解 *)

じゃあ例えば 8 要素のタプルから何か取り出すときは let (x,y,z,s,t,u,v,w) = octet などと書かなければいけないのかと、憤る方はお持ちの Practical OCaml *2 は捨てて、record (レコード)を使うことを考えた方がよいでしょう。Record は tuple と全く同じ効率で各メンバにアクセスできます。

prerr_endline

文字をプリントする関数は、

  • 標準出力へ出力する print_* (print_endline, print_string, print_int ...)系
  • エラー出力へ出力する prerr_* (prerr_endline, prerr_string, prerr_int ...)系
  • output channel へ出力する output_* 系

と三つ用意されています。多分一番使うのが prerr_endline。デバッグ用です。(標準出力の print_endline でも良いですが、エラー出力を使った方がよいでしょう。)
prerr_endline "hogehoge" と prerr_string "hogehoge\n" は似ていますが、違うことに注意してください。前者は "hogehoge" を出力した後、改行した上で、エラー出力を flush するので、呼出すと確実にプリントアウトされますが、後者は flush しませんので OCaml ランタイムのバッファに溜まったままになる可能性があります。prerr_string では、プリントアウトタイミングが遅れる可能性があるばかりか、プログラムが異常終了した際にも flush されず、呼出したにも関わらず、エラー出力には出てこない場合があります。

OCaml には二段階のバッファリングがあることに注意してください。まず文字列は OCaml ランタイムが持つバッファに送られます。( ${srcdir}/byterun/io.h ) ここにある程度溜まると、Unix のファイルハンドルのバッファにまとめて送られます。
OCaml ランタイムにはバッファリングされていても、Unix のファイルハンドルへのバッファに移されていないデータは、プログラムが異常終了すると、失われてしまいます。デバッグメッセージは必ず明示的に flush して両方のバッファからデータを flush する癖をつけましょう。

format, format4, format6

この奇妙な三つの型については Printf モジュールで説明します。

at_exit

at_exit で登録されたコールバック関数は、プログラムが終了する際に呼び出されます。プログラム終了処理に便利です。

モジュール名 "Pervasives" を敢えて使う

Pervasives はデフォルトで open されたモジュールなので、その中で定義された値や型はわざわざ Pervasives.prerr_endline などとモジュール名つきで使用する必要はありません。
ただ、敢えて Pervasives を使う場合もあります。例えば、Pervasives で定義されている値と同名の値を定義した環境で、Pervasives の値を使いたい場合です:

let (+) = Int32.add
let (-) = Int32.sub
...
let v = Pervasives.(+) e1 e2

あるモジュールが int32 などの int 以外の数値型を主に使う場合、関連モジュール (ここでは　Int32) が提供する四則演算(Int32.add, Int32.sub)などの長い名前をいちいち書くのは面倒ですから、(+) や (-) などの数値演算子として定義し直すことがよくあります。もしそのような環境で元の int の数値演算を使いたい場合、Pervasives.(+) と明示することで再定義された 非intの加算ではなく、int 用の加算を使うことが出来ます。
残念ながら、predefined type や predefined exception の名前やコンストラクタが再定義された場合、元の物を使うことは不可能です。できるだけそのような名前は使用しないようにしましょう:

type t = Some
(* 以降、もう Some を 'a option のコンストラクタとして使うことは出来ません *)
let some_one = Pervasives.Some 1 (* エラー。無駄です。Some は Pervasives で定義されている訳ではありません. *)

次回は List です。

モジュール探訪第一回は基本中の基本、 Pervasives でした。基本の割には避けて通れない重要なポイントがいくつもあり、初回から異様に長くなってしまいましたが、次からはもっと短くなるはずです。よろしくお願いします。

次回は List モジュールを紹介する予定です。

*1:${srcdir} は OCaml ソースのトップディレクトリ、${libdir} は ocamlc -where で調べることのできる OCaml のライブラリがインストールされているディレクトリを指すことにします

*2:素晴らしくお勧めしない本です。