MLの多相関数の実装方法

PPLでの質問にも関連するのですが、意外と周知というわけでもないようなので、簡単にメモしてみました。MinCamlでも実装されていないことですし（某所のコンパイラ演習の課題にはなっていますし、私が学部４年生だったときの演習課題にもありましたが）、サーベイ論文やチュートリアルにするほどのことではないので…。もし私の勘違いがあったら是非ともご指摘を（実はそれが目的です）。

ML（やHaskellなど）には、たとえばOCamlの文法で

let f x y = y

と定義すると

val f : 'a -> 'b -> 'b = <fun>

と型推論され、

# f "abc" 123 ;;
- : int = 123
# f 4.5 67.89 ;;
- : float = 67.89

のように任意の型の値に対して適用できる「多相関数」(polymorphic function)があります。JavaやC#などのオブジェクト指向言語でいうgenericsに相当する機能です。

しかし、たとえばC言語でf(x,y)のような関数呼び出しを考えると、xやyの型によって関数呼び出し規約が異なることからもわかるように、一般に多相関数の実装方法は自明ではありません。では、MLの多相関数はどうやって実装されているのでしょうか。

ボックス化(boxing)による実装

LispやSchemeのような動的型つき関数型言語の伝統もあってか、もっとも古くから行われている実装は、すべての型の値を１ワードで表して渡す方法です。この方法だと普通は、１ワードの整数はそのまま、浮動小数や組などはメモリ（ヒープまたはスタック）にアロケートしてポインタを渡します（ボックス化）。

ただし、これだけだとfの中でごみ集め（garbage collection）が起きたときに、xやyがポインタか整数か区別できません。なので、正確なごみ集めのためには、すべての値に1ビットのタグをつけて

整数の最下位ビットは必ず1とし、残りの31ビットで値を表す
ポインタは最下位ビットが必ず0となるように、少なくとも2バイト境界に配置する

ことが（この方法では）通常です。

OCamlやSML/NJは（いくらかの最適化はしていますが）この方法を採用しています。タグのついた整数の計算や、ごみ集めの実装を工夫すれば、それほどのオーバーヘッドはない、ということになっているようです。

コード複製(code duplication)による実装

これはちょっと「力づく」なやり方ですが、xやyの型ごとに、f_int_int, f_float_int, f_int_float, ...のように、複数の関数を生成してしまう方法です。ただし、MLの型は無限にあるので、各型変数('aや'b）について、「整数またはポインタ」と「浮動小数」の2種類、あるいは「整数」と「ポインタ」と「浮動小数」の3種類だけ複製することが普通のようです。

そんなことをしたらコードサイズが爆発するのではないか、という（当然の）疑問がわきますが、

多相関数のコードサイズは小さいことが多い
インターフェース(signature)を経由してモジュール(structure)の外部にexportされるような多相関数は、型変数の数も少ないことが多い（exportされない関数は、すべての呼び出しが静的に把握できるので、必要な型についてのみ複製すれば良い）

ということになっているようです。

MLtonやMLjがこの方法を採用しているそうです（SML.NETも？）。ただし、MLtonやMLj自体は、プログラム全体を一気にコンパイルするように実装されており、対話環境や分割コンパイルをサポートしていません。（もちろん、上の二つの仮定が成り立つ場合には分割コンパイルも可能なはずですし、対話環境もlazyにコードを複製してコンパイルすれば実現できそうですが）

型渡し(type passing)による実装

xやyの型を表すような何らかの値（型表現）を実行時に渡すやり方です。fは型表現を受け取り、それを見て必要な処理を行います（たとえばyが整数だったら整数レジスタから読み出し、浮動小数だったら浮動小数レジスタから読み出す、など）。

これらの方法はまったく独立というわけではなく、たとえばtype passingを（関数の）インライン展開とうまく組み合わせれば、コード複製と同様の効果が得られるかもしれません。

あと、F#（というか.NETのGeneric IL）がどうなっているのか、恥ずかしながらよく知らないのですが、.NET関係の文書でboxing/unboxingがどうとか見かけた覚えもあるので「boxingだけど、整数もbox化する（のでタグはいらない）」みたいな感じでしょうか…？＞ご存じの方