ゼミでParametric polymorphismの実装方法についてサーベイをしたのでそれについて書く 早足に論文を読んだところもあるので内容の正しさ無保証です
メジャーな言語のパラメータ多相性の実装方法
インライン展開してしまう
Cのマクロ、C++などの実装方法
多相的な関数が使われているところで、コンパイル時にコードを展開してしまう
実装が簡単だし、データ構造もCと同等の効率のよいものに保てる
欠点は分割コンパイルを放棄することになることと、コンパイル時間が伸びること
分割コンパイルは、もちろん実装がわかってないと展開するコードもわからないわけで、実装がすでにないとコンパイルできなくなる
また、もし多相関数が100回つかわれていたら、同じコードを100回コンパイルしないといけなくなるわけだからコンパイル時間の大きくなる
もちろんコードを１つ変更すればその変更が伝搬してその周りのモジュールも再コンパイルする必要があって更にコンパイル時間が長くなる
全てのデータをUniformに表現する
Javaや多くのML系言語の実装方法
すべての値を1ワードで表すようにする
２ワード必要なdoubleなどのデータはヒープ上にmallocしてポインタを介して操作する
なぜこのようなことをするのかというと、
- 関数呼び出し規約のため
- 値の長さを揃えるため
例えば、
let f x = x
のようなコードがあった時に
f 1
f 3.14
のいずれも実行できないと困るが、Cの関数の感覚だと関数呼び出しの際、どのレジスタから値を取り出すのかハッキリしている
int func(int x)の関数ならば整数レジスタの１番目に引数が格納されて関数が呼ばれる、のようなことがわかる
しかしこの感覚だとPolymorphicな関数を呼び出すとときに困ってしまう
f 1の関数呼び出しの時も、f 3.14のときも同じレジスタから値を取り出したいが、整数は整数レジスタに格納されるし3.14は浮動小数点数レジスタに格納される
そのため、これらを全部１ワードに揃えてしまって、汎用レジスタに入れてしまう
そうすればどこのレジスタから取り出せばよいのかハッキリする
この方法で実装するとArrayなどは不効率な構造になってしまう
右が理想的なFlatなArray 左が現実
なぜこんなふうになるかというと、右のArrayをArray.lengthのような関数に与えた時を考えれば良い
Array.lengthでArrayの長さを測るとき、中に入っているデータによって何ワード読み込めばよいのかわからない
もちろん今回の場合doubleが入っているので２ワードだが、そんなことはわからない
そのためこれは左のようにFully Boxedな表現になってしまう
このへんはよく知られている問題らしい（？）
JITコンパイルする
.NETの解決策。.NETではGenericsとか言うんだっけか
あまり実装について資料がないのだけど、 嘘です論文がありました
http://research.microsoft.com/pubs/64031/designandimplementationofgenerics.pdf
これによると、JITコンパイルを利用してGenerics利用されるコードが必要なときに生成するらしい
効率的な実装ぽいですね、これなら100回使ってても1回しかコンパイルしなくてよい
それに上のようにBoxedなデータ構造を用いる必要もない
問題はJITコンパイルすることで実行時に計算が必要なことと、VMがないとできない解決策だということ
しかしまぁ、プログラムの実行時に生成するとかリンク時に解決するとか、実装を工夫すればVMなしでもできそうな気はします
論文レベルの話
LeroyのMixed representationを用いる
http://www.slideshare.net/nomaddo/unboxing
これの話
詳しくは読んでもらえばわかるけど、アイディアは単相的な関数にはFlatでSpecilizedな表現を用いて、多相的な関数に値を渡すときには全てbox化してuniformに表現する
これで数値計算とはぐっと良くなる
問題点もいっぱいあるのだけど
- Array, Listなどは相変わらずFully Boxedな表現
- Mutableなデータ構造は効率的にできない
理由はスライドに書いてある
ShaoのFlexible representation analysis
Flexible representation analysis
これの話
Fully Boxedな表現はひどいので、あまり実行時に付加をかけない範囲で、type-passingによりSimply Boxed representationやPartially Boxed representationを実現する話
うえのようなFully Boxedな表現を簡単にしたいというのは割りと自然なアイディアだと思う
面白いのはType-passingする情報は意外に減らせるということ(論文の4.3節の話)
論文と同じ例で、
みたいなコードがあったときに、g・fを呼び出すとき両方に型情報を渡さなくて良いと主張している
何故ならばf, gの型にArrayの要素が現れないから
もうちょっと一般的に言うと、Arrayの要素の型情報は渡さないといけない
fの中で、consオペレータにxを渡したり、arrayをアップデートしていたりする
例えば、fのなかでxを100個並べた配列を作ってupdateしようとすると、xの値のサイズの情報が必要だと思われるが、これは外に絶対にエキスポートされないので、これらのコードを削除しても差し支えない
そのため、型を見れば型情報を渡すべきか判明するとShaoは主張している、のだと思う
完全にこの論文理解しているのか怪しいのだけど、実験のための実装で、型情報は
- Wrap、Unwrapするための情報
- Arrayの要素に含まれる型の情報
- ユーザ定義のRecursive Typesに関連する情報
のみ渡すとしている。これによって
- int32, floatのArrayはFlatに
- それ以外のArrayはSimply boxedに
- ListはSimply Boxedに
になるように実装しているらしい
意外に情報は少なくて済むらしい
感想
あんまりShaoの論文がわからないのでゼミ前にずっとShaoのことを考えていた
多分間違ってないと思うのですが、識者の皆様特にShaoまわりの理解って間違ってないですよね…？
というかShaoの論文sml/njで実験したそうですが、もしかしてこれがsml/njがぐじゃぐじゃになった原因の論文？
