kmizuの日記

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

Scala doesn't Need Generics! (or You can Encode Generics Using Abstract Type Members)

タイトルは煽りではありません。もちろん、Scalaを実用的に使う上では「直接」Genericsを扱えないのは困ります。しかし、記述の冗長ささえ我慢すればGenericsのほぼ全ての機能をAbstract Type Membersによって表現できます。このことを指して、GenericsはAbstract Type Membersでエンコードできると言ったりします。とりあえずコード出せやといわれそうなので、実際のコードを貼りつけてみます。

gist.github.com

このコードでは、不変Listと、その上の高階関数mapforeachGenericsなしで構築しています。

ポイント:

  • Genericな型 => Abstract Type Memberを持った型
  • Genericなメソッド => Abstract Type Memberとメソッドを持った型
  • 関数 => Abstract Type Member InOutを持った型Function
  • Consセルの生成はCons型の無名サブクラスのインスタンス生成を経由して行う

でしょうか。見ればわかる通り、記述としてはGenericsを使った場合よりかなり冗長になっていますが、機能としては同じ要件を満たしていることがわかります。

さて、このような回りくどいことをする事にどのような意味があるのでしょうか。実用的にScalaを使う上ではこのような事実を知ることには意味がありません。

重要なのは、Scalaの最小のサブセットを理論的に議論したい場合においてです。このようなものには、Featherweight Scala(FS)やその後継と言ってもよいDependent Object Types(DOT) Calculusものがあります。FSもDOTもScalaにとって本質的な機能だけを抜き出した、理論的に議論しやすいためのサブセットですが、どちらもAbstract Type MembersはあるがGenericsはないという特徴があります。これは、Abstract Type Membersを使って、Genericsを使ったコードの(ほとんど)全部をエンコードできるためです。

Genericsを含んだ体系を構築した理論的に議論することは可能ですが、Scalaはその開発の初期段階のモデルであるνObj Calculusの頃から、Type Memberはあっても、Genericsを持たない体系でした。これは、Scalaのモデルをできるだけ議論しやすいシンプルなモデルにしたいからだと思われます。

現実のScala処理系では、JVMとの互換性の問題もあって、GenericsとAbstract Type Membersを共に搭載する必要がありますが、実用性を犠牲にしてよいのならば、Genericsを使ったコードをAbstract Type Membersを使ったコードにコンパイルすることも(おそらく)可能です。

オチはありませんが、そのような事が可能であるということを知っておくのは、Scalaの理論的な基盤が何故DOT CalculusのようなGenericsなしの形になっているかを知る上で有益ではないかと思います。