読者です 読者をやめる 読者になる 読者になる

type t (* void *)

関数型言語や英語学習の事とか。

OCaml: 内部のデータ構造とか多相的な配列へのアクセスとか

この記事は ML Advent Calendar 2014 - Qiita の13日目のために書かれた。
MLというかOCamlべったりな内容なのですが……。

雑多な小ネタ集。全て4.02.1で確認した。
OCamlの挙動でよくわからないことを中途半端な時間があったので調べた。

# type t = A of int * int;;
type t = A of int * int
# fun x -> A x;;
Characters 9-12:
fun x -> A x;;
^^^
Error: The constructor A expects 2 argument(s),
but is applied here to 1 argument(s)

 なんでや、と思ったのでとりあえずデータ構造を見てみたくなってlambdaをみる。
Lambda.lambdaは中間コードの一つで、OCamlでは内部でParsetree.structure -> Typedtree.structure -> Lambda.lambda -> Clambda.ulambda -> Cmm.pharse listを経てアセンブリが出力される(ネイティブコードコンパイラの場合)。
driver/optcompile.mlのimplementationとその中の関数を追いかければ流れが分かる。こういうことをやる時には、merlinやocamlspotのような関数の型を表示してくれるツールがあると便利だ。動作が違うので私は両方使ってる。

[~] ocaml -dlambda
OCaml version 4.02.1

# type t = A of int * int;;
0a
type t = A of int * int
# type tt = B of (int * int);;
0a
type tt = B of (int * int)
# A (1, 2);;
[0: 1 2]
- : t = A (1, 2)
# B (3, 4);;
[0: [0: 3 4]]
- : tt = B (3, 4)

 

# (fun (x, y) -> A (x, y));;
(function param/1022
  (makeblock 0 (field 0 param/1022) (field 1 param/1022)))
- : int * int -> t = <fun>
# (fun e -> B e);;
(function e/1023 (makeblock 0 e/1023))
- : int * int -> tt = <fun>

type t = A of int * int と定義した時、
A (1, 2)はラベル0と2つのデータの3つの値がフラットに並んでいるようだ。
type tt = B of (int * int)と定義した時、
B (3, 4)はラベル0と更にラベル0がついた構造体のポインタが並ぶ、つまり2つのデータが並ぶ構造のようだ。

よりあとの関数の例のほうが分かりやすい……?どっちでもいいですね。

そりゃ最初の定義では直接値をひとつ受け取って、ラベルを付けて返すなんて操作が出来ないわけだよ。

ちなみに全ての要素がfloatのレコードは特別扱いされて例えば{x:float; y:float}は{x: t; y:t}と抽象化できない。こういう抽象化をしようとすると表現が違うよ~~~とコンパイラに怒られる。

データ構造が全然違うしレコードの場合はarrayと違って実行時に情報を渡したりしないかららしい。

# module type S = sig type t type r = {x: t; y: t} end;;
module type S = sig type t type r = { x : t; y : t; } end
# module M : S = struct type t = float type r = {x: float; y:float} end;;
Characters 15-69:
module M : S = struct type t = float type r = {x: float; y:float} end;;
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Error: Signature mismatch:
Modules do not match:
sig type t = float type r = { x : float; y : float; } end
is not included in
S
Type declarations do not match:
type r = { x : float; y : float; }
is not included in
type r = { x : t; y : t; }
Their internal representations differ:
the first declaration uses unboxed float representation.

[~] ocaml -dlambda

OCaml version 4.02.1

# type t = {x: float; y: float};;
0a
type t = { x : float; y : float; }
# {x=1.; y=2.};;
[|1. 2.|]
- : t = {x = 1.; y = 2.}
# type tt = {a: float; b: int};;
0a
type tt = { a : float; b : int; }
# {a=1.; b=2};;
[0: 1. 2]
- : tt = {a = 1.; b = 2}

 すべての要素がfloatのレコードはlambdaのレベルだとarrayになってますねー。
そうでない時はラベル付きのデータ構造になっている模様です。

 

ちなみにarrayにアクセスするときどうなってるのか調べてみた。
コードで言うと、

let access arr i = arr.(i) 

みたいな関数がどういう風になっているか。上の1行のプログラムを-c -Sのオプション付きでocamloptでコンパイルしてみる。 

output of ocamlopt -c -S ./arr.ml. arr.ml includes ...

見てみるとどうやら何かしらの情報で分岐しているらしくfloatの時とそうでない時で動作がわかれる模様。
アセンブリで見なくてもbyterun/array.cのcaml_array_getを読めば分かる……。

比較についてもまぁ何かしらの型情報渡してるだろうなーと思うのだけどbyterun/compare.cのcompare_val(比較のToplevelはこれではなく多分caml_compare)が結構複雑っぽくて移動中に読み終わらなそうなので解説は諦める。

雰囲気メッチャTagのチェックしてる。まぁ読めば分かるんじゃないでしょうか。

14日目は@keita44_f4さんのSMLの記事です!