ちゃっくのメモ帳

ちゃっくがメモしときたいことをメモしとくよ

IQ1とOCamlとFirst-classモジュール

はじめに

この記事はIQ1アドベントカレンダー2019の1日目の記事です。
adventar.org

IQ1アドベントカレンダーは今年で3年目です。
なんでこんな意味不明なアドベントカレンダーが3年も続けられてるんですかね!?
登録してくださった方々ありがとうございます。

「IQ1をせずにクリスマスを迎える人を生んじゃってもいいんですか！」
登録していない方々は2枚目を用意したので是非登録してください。

IQ1アドベントカレンダーはその名の通り(?)、何でもありのアドベントカレンダーです。僕は去年はご飯について書いたり、卒業するときにやったことについて書いたりしてました。一昨年はアルゴリズムについて書いたりしてるっぽいですね。真面目な記事、ネタ記事、どちらも大歓迎です。

さて、今年の1日目のネタを何にするか。
できるだけ後ろのハードルを上げないいい感じの記事を書きたいですね。最初は、今年のIQ1の活動について振り返ろうかと思ったのですが、25日目には今年のIQ1アドベントカレンダーの総評を書こうと思っているので1日目を活動記にすると僕の2つの記事の雰囲気が被っちゃうかなぁと思い、プログラミングに関する記事でも書くことにしました。

IQ1の修論を支える言語

本題です。この記事ではIQ1の人間が修論のためにどんな言語を選び、その言語を使う上でどこで躓いたかを記します。
よい解決方法を知っている人は助けてーー。

ある日、IQ1の人間が修論のためにプログラミングをしようと思いました。
色々あってOCamlを使うことにしました。(端折りすぎやろ)

OCaml、書いてみると結構良い言語に思えます。代数的データ型とパターンマッチもありますし、まぁまぁ速度も出ますし、まぁまぁ書きやすいです。
多分、手続き型プログラミングに慣れた人が関数型言語を使ってみたいと思ったときに、OCamlを使ってみるという選択は比較的ストレスも少ないのではないかと思います。

しかし、使いやすい言語といっても書いてる/勉強していると困るポイントというのは存在します。こういうポイントを無視して盲目的に特定の言語を推してる人は警戒したほうが良いと思っています。そういう人はIQ1の可能性があります。(僕はIQが1なので盲目的に意味不明的なことを言っていても許されます。)
使っていると、「これができてほしい」と思うことは多々あります。OCamlを使っていて感じた、そういう「これができてほしい」の1つを紹介します。

OCamlには(もっというとおそらくML系の言語では)、Functor(ファンクタ)という機能があります。
(ここでのMLはMachine Learningを指しません。Meta-Languageの方です。Machine Learningに関する記事が読みたかったらIQ1AdC2018にはいくつかそのような記事が存在しています
IQ1 Advent Calendar 2018 - Adventar )

このファンクタというのはモジュールをパラメータとして受け取り、モジュールを生成する関数です。
(モジュール関数とか言われたりするっぽい?)

おそらく馴染みの無い方は「は?何言ってんだこのIQ1は?」と思ったりすると思うので例としてSetモジュールを見てみましょう。これは集合を表すモジュールです。

まず整数集合を表すモジュールを生成し、使用していく簡単な例を見ていきましょう。

module IntSet = Set.Make(Int);;

let _ = 
  let set = IntSet.of_list [1;2;3;4] in
  let sum = IntSet.fold (fun x acc -> x + acc) set 0 in
  print_int sum (* 10 *)

これで整数集合を表すモジュールIntSetを作ることができます。
ここで、Set.Makeがファンクタです。
確かにSet.MakeはパラメータIntを引き受けてSet.Make(Int)というモジュールを生成しています。そして生成されたモジュールにはIntSetという名前が付けられています。

では、同様に文字列集合のStringSetも定義したとしましょう。

module IntSet = Set.Make(Int);;
module StringSet = Set.Make(String);;

そして、Set.Makeを用いて生成された任意のモジュール(IntSet,StringSet,...)の中身を出力する関数print_setを作りたいとします。

let print_set (set:Set.S) (printer : 'a -> unit) : unit = ...
  Set.S.iter set printer

ダメです。

これは、関数の引数のtype constraintsには型が必要で、シグネチャ(Set.S)やファンクタ、モジュールを指定することができません。
(話は逸れますが、type constraintsってtype restrictionと違うのでしょうか? OCamlでtype constraintsって言ってるだけ?)
では、関数を多相にすることを考えてみましょう。

let print_set (set : 'b) (printer : 'a -> unit) : unit = ...
  'b.iter set printer

これは上手く行くように見えますが、実際は上手く行きません.

では、locally abstract typeを使うことを考えてみましょう。

let print_set (type s) (set : s) (printer: 'a -> unit) : unit = 
  s.iter ...

これもダメです。
なぜならset : sとなっている部分のsにはsetがIntSetモジュールの値ならば型はIntSet.tになります。そのためs.iterはIntSet.t.iterとなってしまいます。
しかし、iterを持っているのはIntSetモジュールであり、IntSet.t型ではありません。

これでダメだと割と心が折れてきますね。
ここで出てくるのがFirst-class moduleという機能です。
これはモジュールを値として扱うことでモジュールを引数に取る関数を定義したり、モジュールを変数として扱うことができる機能です。

OCamlの普通のモジュールはFirst-classではありません。そのため、普通のモジュールからFirst classなモジュールに変換したり、First classなモジュールから普通のモジュールへ変換したりする必要があります。
では、このFirst classモジュールを使ってどのようにprint_setを実装していくかを見ていきます。

結論から言うとこれでいけます

let print_set (type s t) m (set :t) (p : s -> unit) : unit=
  let module M = (val m : Set.S with type elt = s and type t = t) in
  M.iter p set

これがしていることは、First-classモジュールmを引数と渡して、関数の中でmを一般のモジュールMに戻しています。

これを使うと、次のようなコードが書けるようになります。

let _ () =
  let set = IntSet.of_list [1;2;3;4;5] in
  print_set (module IntSet) set print_int;
  let set2 = StringSet.of_list ["abc"; "def"; "xyz"] in
  print_set (module StringSet) set2 print_string;

print_setの第一引数はFirst-classモジュールです。そこで、モジュールIntSetを(module IntSet)としてFirst-classモジュールに変換して引数に渡します。
そうするとprint_set関数は(val m)でFirst-classモジュールを一般モジュールにもどしMという名前に束縛します。
このようにすればモジュールMは引数として渡されたFirst-classモジュールmの一般的なモジュールとなるのでM.iter等を使うことが出来ます。
このようにFirst-classモジュール(第一級モジュール)を使用すればSetファンクタから生成された任意のモジュールを受け取り、モジュールに含まれる関数を定義するような関数を定義することができます。

因みに、上のprint_setはmの型が(module Set.S with type ...)なので省略して次のように書くことができます

let print_set (type s t) (module S : Set.S with type elt = s and type t = t) (set : t) (p : s -> unit) : unit =
  S.iter p set

こうしてみると、OCamlのファンクタというのは微妙に使いづらい気がしてしまいます。
モジュールをパラメータとして受け取らないとモジュールが定義できず、型をとれないの
そもそもSetを多相で実装してくれていれば.....(実際BatteriesライブラリにはPSetという多相Setがあるらしいです)

これ、C++だったら多分次のような感じで簡単に書けるはずです。
OCamlでもこの辺り、いい手段がほしいです。
(もちろん違う言語の違う機能を比べてもしょうがないのですが...)

template<typename T>
void print_set(const std::set<T>& s, std::function<void(int)> p){
    for(auto& e : s) p(e);
}

int main(){
    std::set<int> st{1,2,3,4};
    std::function<void(int)> f = [](int i){ std::cout << i; };
    print_set(st,f);
}

さいごに

OCamlのModule周り、実はかなり分かっていない。
雰囲気でOCamlを書いている。多分ちゃんと勉強したほうが良いんだけど....
僕はまだこの辺り上手く扱えないので、ちゃんと扱うのは荷が重い。


明日はrian_tkbがなんか書くらしいので期待するか