kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

高階多相か高カインド多相、どちらが適切な用語かを考える

タイトルだけだと、わかってる人にしかわからないので、背景を説明します。サンプルコードはScalaですが、同じ機能はHaskellにもあります（あとは、C++のテンプレートテンプレート引数もこれに該当します。もうちょっとマイナーな言語だと他にいくつもありますが、プロダクション環境での事例がある程度ある言語だとこの三つくらいになると思います）。

今回考えたいのは、ある型システムに関して色々な用語が入り乱れているので、どれが適切なのかを検討したいということです。まず、次のようなScalaプログラムの断片を考えます。

trait Functor[F[_]] {
 def fmap[A, B](f: F[A])(g: A => B): F[B]
}

ここで、Functor[F[_]]で、パラメタとして渡せるものは、通常の型ではなく、型コンストラクタです。型コンストラクタというのは、何か引数を受け取って型を返すもので、具体的な例でいうと、List,Option,Vector,ArrayList,などなど、型パラメタを実際に与える前の何かを指します。型コンストラクタを与えたものとして、Functor[List],Functor[Option],Functor[Vector]などを、実際の型として考えることができます。

このようなものは、それ自体は型ではないので、単純なパラメタ多相（あるいはジェネリクス）では扱うことができません。そのため、パラメタ多相を拡張する必要がありますが、このようなパラメタ多相の拡張を何と呼ぶかについて、いくつかの用語があり、外野からみるとそれらが同じものなのか別のものなのか区別がつきにくいので、どの用語が最も適切かについて検討を加えてみようというのがこの記事の趣旨です。

まず、結論からいうと、使われている数の多さ、用語の歴史、概念をよく説明していることから、高階多相が適切だろうというのが自分の考えです。以下で、その根拠について説明していきます。

まず、このような多相性を表すことばとして、いくつかの用語があるので、それらをリストアップしてみます。

  • 高階多相（higher-order polymorphism）
  • 型コンストラクタ多相（type constructor polymorphism）
  • 高カインド多相（higher-kinded polymorphism）
  • 高カインドジェネリクス（higher kind(ed) generics）
  • 高階ジェネリクス（higher order generics）

ざっと調べただけでもこれだけ色々な用語が同じ概念を指す言葉として使われています。まず、自分は、型システム上の用語としてどれが適切かを考えたいので、特定の言語群に結びついたHogeHoge Genericsというのは避けたいところです。なので、HogeHoge Genericsは除外して考えます。

残る候補としては、

  • 高階多相（higher-order polymorphism）
  • 型コンストラクタ多相（type constructor polymorphism）
  • 高カインド多相（higher-kinded polymorphism）

になります。これらはどれも概念上はそれなりに妥当性がありそうですが、自分が知る限り、型コンストラクタ多相というのは、ScalaにおいてAdriaan Moors氏が導入した用語のようで、それ以前の用例は見つけることができませんでした（Google Scholarの検索結果においては）。それ以前からあったシステムに新たな用語を付ける必要もなかろうと思うので、型コンストラクタ多相も除外します。

あとは、高階多相か高カインド多相かということになりますが、まず、この二つの用語についてGoogle Scholarで検索した場合、前者（higher order polymorphism）は96件ヒットで、古い用例では1980年代からあるようです。また、型システムの教科書として定評のあるTypes And Programming Languages（日本語訳：型システム入門）では、高階多相（higher-order polymorphism）という用語が採用されており、これは伝統的な用語を踏まえたもののように思います。

後者については、higher-kind polymorphismが6件ヒットで、higher-kinded polymorphismが36件ヒット、また、両方とも2005年以前の用例がみつからない辺り、2005年以降のどこかの論文を参照した用語ではないかと思われます。

用語が使われてきた歴史や用例の多さ、著名な教科書に使われていることなどを考えて、高階多相という用語がもっともよさそうです。また、高階多相という用語は、型上の関数を考えたときに、型上の関数そのものを渡せるという意味で高階関数との類似性があり、名前としても妥当です。

無論、ある概念を他の用語で呼ぶべきでない、ということは一般に言えないですから、他の用語を使うことを積極的に止めるものではないですが、あえて統一するなら高階多相が一番妥当そうだという話です。

なお、私は型システムは専門ではないので、何かツッコミどころがある可能性はあるので、そういったことがあればコメントをいただければと思います。