Background: how we got the generics we have (Or, how I learned to stop worrying and love erasure)

原文はこちら。
This article was written by Brian Goetz (Java Architect, Oracle).
http://cr.openjdk.java.net/~briangoetz/valhalla/erasure.html

ジェネリクスの方向性を語る前に、まず、ジェネリクスの現在の状況とそこまでの経緯を語る必要があります。この文書では、現在のジェネリクスが、いま作ろうとしている「より良い」ジェネリクスへどのように影響を与えるかの礎として、主として現在のジェネリクスがどのようにしてできあがったのか、そしてその理由についてフォーカスします。

特に、2004年にJavaにジェネリクスを追加する際には、実際にはerasure(消去、ここではtype erasure、つまり型消去を意図している)が賢明で実用的な選択であったこと、そして、erasureによる変換(translation)を選択するようことになった多くの力が、今日でも機能していることを強調しておきます。

Erasure

Java のジェネリクスについて開発者に尋ねると、erasureに対して怒りの声を上げることがあるでしょう(erasureについてあまり知られていないこともありますが)。erasureは、おそらくJavaで最も広く、深く誤解されている概念です。

erasureはJavaに特有のものでもジェネリクスに特有のものでもありません。erasureは、(Java ソースからバイトコードへのコンパイルや、C ソースからネイティブ コードへのコンパイルなど)あるレベルのコードをより低いレベルのコードに変換するための、どこにでもあり、しばしば必要なツールです。これは、高レベルの言語から中間表現(IR)、ネイティブコード、ハードウェアへとスタックを下降させていくと、低レベルで提供される型の抽象化は、ほとんどの場合、高レベルで提供されるものよりも単純で弱いものになるからです(仮想ディスパッチのセマンティクスをx86の命令セットに組み込んだり、Java のプリミティブ型のセットをレジスタで真似したりすることはしたくありませんので)。erasureとは、(理想的には、上位レベルで健全な型チェックを行った後に)あるレベルのリッチな型を低いレベルのリッチでない型にマッピングする技術で、これはコンパイラが日々実施していることです。

例えば、Javaのバイトコードセットには、スタックとローカル変数セットの間で整数の値を移動する命令(iload, istore)や、整数の演算を行う命令(iadd, imulなど)が含まれています。float (fload, fstore, fmul など)、long (lload, lstore, lmul)、double (dload, dstore, dmul)、オブジェクト参照 (aload, astore) にも同様の命令がありますが、byte、short、char、booleanにはそのような命令はありません。それは、コンパイラがこれらの型をintに型消去(erase)するためで、これらの型ではintの移動や演算の命令を使います。これは、バイトコード命令セットの設計における実用的な設計上のトレードオフであって、これにより、命令セットの複雑さが軽減され、ランタイムの効率が向上します。チェック例外(checked exceptions)、メソッドのオーバーロード(method overloading)、列挙型(enums)、確定割り付け解析(definite assignment analysis)、入れ子のクラス(nested classes)、ラムダやローカルクラスによるローカル変数の捕捉といった、Java言語の他の多くの機能はlanguage fictions(言語の虚構)であり、Javaコンパイラではチェックされますが、クラスファイルへの変換時には消去されます。

同様に、C言語をネイティブコードにコンパイルすると、符号付き整数と符号なし整数の両方が型消去されて汎用レジスタに入れられ(符号付きと符号なしのレジスタは別個に存在しません)、const変数はミュータブルなレジスタとメモリロケーションに格納されます。このような消去がおかしいとは全く思いません。

Homogeneous vs heterogeneous translations

パラメータのポリモーフィズム(多相性、parameteric polymorphism)を持つ言語においてジェネリック型を変換するには、同種変換(homogeneous translation)と異種変換(heterogeneous translation)の2つの一般的なアプローチがあります。同種変換では、ジェネリッククラス Foo<T> が Foo.class のような単一のアーティファクトに変換されます(ジェネリックメソッドも同様です)。異種変換では、ジェネリック型やジェネリックメソッド(Foo<String>、Foo<Integer>)の各インスタンス化は別個のエンティティとして扱われ、別個のアーティファクトが生成されます。例えば、C++ では異種変換を使用します。テンプレートの異なるインスタンスは全く異なる型であり、異なるセマンティクスを持ち、異なるコードが生成されます。vector<int>とvector<float>は別の型です。これは型の安全性(拡張後に各インスタンスを個別に型チェックできる)と、生成されるコードの品質(各インスタンスを個別に最適化できる)の面で優れています。一方で、(vector<int>とvector<float>は別々のコードを持っているため)これはコードフットプリントが大きくなることを意味し、各インスタンスが完全に無関係な型なので、(Javaがワイルドカードを使ってやるように)”何かのベクトル”について話すことはできません。(可能性のあるフットプリントコストの極端なデモンストレーションとして、Scalaで @specialized アノテーションを使って実験を行いました。このアノテーションを型変数に適用すると、コンパイラはすべてのプリミティブ型に特化したバージョンを出すようになります。一見よさげですが、nをクラス内の特殊化された型変数の個数とすると、結果として生成されるクラスが9n個も爆発的に増えてしまいます。そのため、数行のコードから簡単に100 MBのJARファイルが生成されてしまう可能性があります)。

同種変換と異種変換の選択には、言語設計者が常に行っているようなトレードオフを行う必要があります。異種変換では、型の特定性が高まりますが、静的および動的なフットプリントが大きくなり、実行時の共有が少なくなります。これらは全てパフォーマンスに影響を与えます。同種変換は、JavaのワイルドカードやC#のdeclaration-site varianceなど、型のパラメトリックなファミリーを抽象化するのに適しています(どちらもC++にはありません。C++の場合、vector<int>とvector<float>の間には共通点がありません)。変換戦略の詳細については、この影響力の大きい論文を参照してください。

Two Ways to Bake Your Pizza — Translating Parameterised Types into Java
http://pizzacompiler.sourceforge.net/doc/pizza-translation.pdf

Erased generics in Java

Javaでは、同種変換を用いてジェネリクスを変換します。ジェネリクスはコンパイル時に型チェックされますが、その際バイトコード生成時にList<String>のようなジェネリック型はListに型消去され、<T extends Object>のような型変数はその境界(この場合はObject)のerasureに型消去されます。

次のようなコードを考えます。

class Box<T> {
    private T t;

    public T(T t) { this.t = t; }

    public Box<T> copy() { return new Box<>(t); }

    public T t() { return t; }
}

javacコンパイラは1個のクラスファイルBox.classを生成します。これはワイルドカード(Box<?>)とraw型(Box)を含む、Boxの全てのインスタンスのための実装として機能します。以下のように、フィールドやメソッド、スーパータイプのディスクリプタが消去され、型変数はその境界に型消去され、ジェネリック型はそのhead、つまりList<String>はListに型消去されます。

class Box {
    private Object t;

    public Box(Object t) { this.t = t; }

    public Box copy() { return new Box(t); }

    public Object t() { return t; }
}

コンパイラがクラスファイルを読む際にジェネリックシグネチャを見ることができるよう、ジェネリックシグネチャは(Signature属性で)保持されていますが、JVMはリンケージにおいて消去されたディスクリプタのみを使用します。この変換スキームは、クラスファイルレベルでは、Box<T>のレイアウトとAPIの両方が消去されることを意味します。use siteでは同じことが起こります。つまり、Box<String>への参照はBoxに消去され、Stringへの合成キャストがuse siteで挿入されます。

Why? What were the alternatives?

この時点で、不機嫌になり、これらは明らかに愚かな選択であるとか、怠惰な選択であるとか、erasureはダーティなハックであると宣言したくなります。結局のところ、なぜコンパイラは完全に良い型情報を捨ててしまうのでしょうか?

この質問をよりよく理解するためには、次のような質問もしなければなりません。

  • 型情報を具体化するとして、それを使ってどうしたいのか
  • それに伴うコストはどれくらいになるのか、

具体化された型パラメータ情報を使用する方法はいくつか考えられます。

  • Reflection(リフレクション)
    ある人にとっては、reified generics (具体化されたジェネリクス)とは、単に、型変数の instanceof やパターンマッチングのような言語ツールを使用して、またはreflectiveなライブラリを使って型型パラメータを問い合わせて、何のlistであるかをListに問い合わせることができることを意味しているにます。
  • Layout or API specialization(レイアウトまたはAPIの特殊化)
    プリミティブ型やインラインクラスを持つ言語では、ボックス化オブジェクトへの2つの参照ではなく、2個のintを保持するために、Pair<int, int>のレイアウトをフラットにするのが良い場合があります。
  • Runtime type checking.(実行時の型チェック)
    クライアントが(例えば、 Listのraw参照を使って)Integerを List<String> に入れようとするとヒープ汚染を引き起こしますが、後に合成キャストに達した際に検出するのではなく、そのような操作を捕捉し、ヒープ汚染が生じる時点で失敗するのがよいでしょう。

相互に排他的ではありませんが、これら3つの可能性(リフレクション、特殊化、型チェック)は、それぞれ異なる目標(プログラマの利便性、性能、安全性)を支援するためのものであり、異なる意味合いとコストを持っています。「具体化(reification)を望む」と言うのは簡単ですが、もっと深く掘り下げてみると、これらのうちどれが最も重要なのか、また、それらの相対的なコストと便益はどうなのかという点で、大きな分かれ道が見えてくるでしょう。

ここでどのようにerasureが賢明で実用的な選択であったかを理解するためには、当時の目標、優先順位、制約、代替案がどのようなものであったかを理解する必要があります。

Goal: Gradual migration compatibility

Javaのジェネリクスは野心的な要件を採用しました。

It must be possible to evolve an existing non-generic class to be generic in a binary-compatible and source-compatible manner.(既存の非ジェネリッククラスを、バイナリ互換性とソース互換性のある方法でジェネリッククラスに進化させることができる必要があります)

これは、既存のクライアントや例えばArrayListのサブクラスは、ジェネリクスにされたArrayList<T>に対して変更することなく再コンパイルを続けることができ、既存のクラスファイルは、ジェネリクスにされたArrayList<T>のメソッドにリンクし続けることができることを意味します。これをサポートすることは、ジェネリクスにされたクラスのクライアントやサブクラスが、即座に、もしくは後にジェネリクスにするか、もしくは全くジェネリクスにしないかを、他のクライアントやサブクラスのメンテナが選択したこととは無関係に選択可能であることを意味しています。

この要件がない場合、クラスのジェネリクス化には全てのクライアントやサブクラスを変更していなくても、少なくとも一度にすべて再コンパイルしなければならないflag day(国旗制定記念日)が必要です。ArrayListのようなコアクラスの場合、これは基本的に全てのJavaコードを一度に再コンパイルする必要があります(またはJava 1.4にとどまるように永続的に追放する必要があります)。Javaエコシステム全体にわたるこのようなflag dayは論外ゆえに、コアプラットフォームクラス(だけでなく、人気のある3rdパーティーライブラリも)クライアントがジェネリクス化について知る必要なくジェネリクスにできる、ジェネリック型システムが必要だったのです。(さらに悪いことに、それは1回ではなく多数回ののflag dayだったことでしょう。というのも、世界中のすべてのコードが単一のアトミックトランザクションでジェネリクスにされるとは限らないためです。)

ジェネリックス化されていた可能性のあるコードをすべて孤立させたり、開発者にジェネリクスと既存のコードに実施してきた投資の維持を選択をさせたりすることは受け入れられないと考えられています。ジェネリクス化を互換操作にすることで、そのコードへの投資を無効にせず、維持できる可能性があります。

“flag days”への嫌悪は基本的なJavaの設計の本質的な側面に由来しています。Javaは個別にコンパイルされ、動的にリンクされます。個別のコンパイルとはつまり、全てのソースファイルを1個以上のクラスファイルにコンパイルするのであって、ソースファイルの一群を1個のアーティファクトにコンパイルするのではありません。動的なリンクとは、シンボル情報を基にしてクラス間の参照を実行時にリンクすることです。具体的には、クラスCがDのメソッド void m(int x) を呼び出す場合、Cのクラスファイルで呼び出しているメソッドの名前とディスクリプタ((I)V)を記録し、リンク時に、この名前とディスクリプタを使ってD内のメソッドを探します。一致するものがあれば、call siteをリンクします。

これは大変な作業のように聞こえるかもしれませんが、別個のコンパイルと動的リンクはJavaの最大の利点の一つで、(D にバイナリ互換性のない変更を加えない限り)、D のあるバージョンに対してCをコンパイルし、クラスパス上の異なるバージョンのDとともに実行できます。

動的リンクへの広範なコミットメントにより、クラスパスに新しいJARをドロップするだけで、依存関係の新しいバージョンに更新できます。再コンパイルの必要はありません。これを気がつかないくらい頻繁にやっていますが、これが動かなくなったら、確かに気がつくはずです。

ジェネリクスがJavaに導入された当時、世界にはすでに多くのJavaコードがあり、それらのクラスファイルは java.util.ArrayList などのAPIへの参照が多数ありました。これらのAPIを互換性のある形でジェネリクスにできない場合、 新しい APIを作成してそれらを置き換える必要があり、さらに悪いことに、(アプリケーションコードだけでなく、アプリケーションが依存するすべてのサードパーティライブラリも含めて)古いAPIのすべてのクライアントコードが、1.4で永久に塩漬けにするか、それらを書き直して、新しいAPIを同時に使用するか、という選択を迫られることになります。

C#では、VMをアップデートし、既存のライブラリやそれに依存する全てのユーザーコードを無効にする、という逆の選択をしました。その当時に可能これが可能だったのは、比較的C#のコードが少なかったからです。Javaの場合はその選択はできませんでした。

しかし、この選択の結果、ジェネリッククラスは、ジェネリッククライアント、非ジェネリッククライアントの両方もしくはサブクラスを同時に持つことが予想されます。これは、ソフトウェア開発プロセスにとっては有益なことですが、このような混在した使用法の下では型の安全性に影響を及ぼす可能性があります。

Heap pollution

この方法で消去し、ジェネリッククライアントと非ジェネリッククライアント間の相互運用性をサポートすると、 ヒープ汚染の可能性が生じます。つまり、ボックス化されたものが、コンパイル時に予期された型と互換性のないランタイム型を持つ、という可能性です。クライアントがBox<String>を利用する場合、TをStringに割り当てる都度キャストが挿入されるため、型変数(Boxの実装)の世界からを具象型の世界にデータ移行する時点でヒープ汚染を検知します。ヒープ汚染が存在する場合、これらのキャストが失敗する可能性があります。

非ジェネリックコードがジェネリッククラスを使う場合、もしくは未チェックのキャストや未加工の型を使って誤ったジェネリック型の変数への参照を偽造した場合に、ヒープ汚染が発生する可能性があります(未チェックのキャストや未加工の型を使った場合、コンパイラはヒープ汚染が発生する可能性があることを警告します)。例えば以下のような例を考えます。

Box<String> bs = new Box<>("hi!");   // safe
Box<?> bq = bs;                      // safe, via subtyping
Box<Integer> bi = (Box<Integer>) bq; // unchecked cast -- warning issued
Integer i = bi.get();                // ClassCastException in synthetic cast to Integer

このコードの罪は、Box<?>からBox<Integer>への未チェックのキャストです。指定されたboxが本当にBox<Integer>であるという開発者の言葉を鵜呑みにしなければならない、というものです。しかし、ヒープ汚染はすぐには検出されません。box内のStringをIntegerとして使おうとしたときに初めて、何かが間違っていることが検出されます。現在の変換では、boxをBox<Integer>にキャストし、Box<Integer>として使用する前にBox<String>に戻しても、(良くも悪くも)何も悪いことは起こりません。異種変換の場合、Box<String>とBox<Integer>は異なるランタイム型を持つため、このキャストは失敗します。

規則に従う限り、この言語は実際にジェネリクスに対して非常に強力な安全性保証を提供します。

If a program compiles with no unchecked or raw warnings, the synthetic casts inserted by the compiler will never fail.(プログラムが未チェックまたは未加工の警告なしでコンパイルする場合、コンパイラが挿入した合成キャストは失敗しません)

換言すると、ヒープ汚染は、非ジェネリックコードと対話している場合、もしくはコンパイラに嘘を言っている場合にのみ発生する可能性があります。ヒープ汚染を検知した時点で、予期される型と実際に検出された型を示す明確な例外が発生します。

Context: Ecosystem of JVM implementations and languages

JVM実装のエコシステムとJVM上で動作する言語の構造もまた、ジェネリクスを取り巻く設計の選択に影響を与えています。ほとんどの開発者にとってJavaはモノリシックな実体ですが、実際にはJava言語とJava仮想マシン(JVM)は別個の実体であり、それぞれに独自の仕様があります。JavaコンパイラはJVM用のクラスファイルを生成します(そのフォーマットとセマンティクスはJVM仕様書に記載されています)が、JVMは、元々のソース言語に関係なく、有効なクラスファイルを喜んで実行します。数えてみると、コンパイルターゲットとしてJVMを使用する言語は200以上あり、その中にはJava言語と共通点の多いもの(例えばScalaやKotlin)、や、全く異なる言語(例えばJRuby、Jython、Jaskell)があります。

JVMがコンパイルターゲットとして成功している理由の1つは、Javaとは全く異なる言語であっても、Java言語からの影響を限定した、かなり抽象的なコンピューティングモデルを提供していることです。言語と仮想マシンの間の抽象化層は、JVM上で動作する他の言語のエコシステムを刺激するのに役立っただけでなく、JVMの独立した実装のエコシステムも刺激しました。今日のマーケットは大幅に統合されていますが、Javaにジェネリクスが追加された時点では、JVMの商用実装は12を超えていました。ジェネリクスを具体化するということは、ジェネリクスをサポートするために言語だけでなくJVMも強化する必要があることを意味します。

当時のJVMにジェネリクスのサポートを追加することは技術的には可能だったかもしれませんが、多くの実装者間の実質的な調整と合意を必要とする多額のエンジニアリング投資であっただけでなく、JVM上の言語のエコシステムも、具体化されたジェネリクスについて意見を持っていたかもしれません。例えば、具体化の解釈に実行時の型チェックが含まれていたとしたら、(declaration-siteジェネリクスを持つ)Scalaは、JVMにJavaの(不変の)ジェネリックサブタイプルールを適用させるでしょうか?

Erasure was the pragmatic compromise

まとめると、これらの制約(技術的な制約、エコシステムの制約の両方)は強力に称型の情報をコンパイル時に消去するという同種変換戦略へと推し進めました。要約すると、この決定に至るまでの後押しした力には以下のものがあります。

  • Runtime costs.(ランタイムコスト)
    異種変換は、あらゆる種類のランタイムコストを伴います。例えば静的および動的フットプリントの増加、クラスロードコストの増加、JITコストの増加、コードキャッシュの圧力などです。これにより、開発者は型の安全性とパフォーマンスのどちらかを選択しなければならない状況に追い込まれた可能性があります。
  • Migration compatibility(移行の互換性)
    当時、具体化されたジェネリクスへの移行をソースおよびバイナリ互換にすることを可能にする既知の変換スキームがありませんでした。(やろうとすると)flag dayを作成し、開発者の既存のコードへのかなりの投資を無効にするしかありませんでした。
  • Runtime costs, bonus edition.(ランタイムコストの追加) 
    具現化が(Javaの共変配列への保存が動的にチェックされるのと同じように)実行時の型チェックと解釈される場合、言語のジェネリック型システムを使うと、JVMは全てのフィールドまたは全ての配列要素ストアで実行時にジェネリックサブタイプチェックを実行する必要があるため、ランタイムに大きな影響があります(型が List<String>のような単純なものであれば、簡単でコストもかからないように思えるかもしれませんが、Map<? extends List<? super Foo>>、? super Set<? extends Bar>>の ようなものである場合、すぐに高価になる可能性があります。実際、後年の研究でジェネリックサブタイピングの決定可能性に疑問を投げかけています)。

    On Decidability of Nominal Subtyping with Variance
    https://www.cis.upenn.edu/~bcpierce/papers/variance.pdf
  • JVM ecosystem.(JVMエコシステム)
    実行時に型情報を具体化するかどうか、またどのように具体化するかについて、JVMベンダー全体の同意を得るのは、非常に疑わしい提案でした。
  • Delivery pragmatics(配信語用論)
    JVMベンダー全体が実際に機能するスキームに対して同意することが可能であったとしても、複雑さ、タイムライン、そしてすでに実体があり、リスクのある作業のリスクが大幅に増加したことでしょう。
  • Language ecosystem.(言語エコシステム)
    Scalaのような言語は、Javaの不変のジェネリクスをJVMのセマンティクスに焼き付けるのは満足していなかったかもしれませんが、JVMにおけるジェネリクスの一連の受け入れ可能な言語間セマンティクスに同意していれば、繰り返しになりますが、複雑さ、タイムライン、およびすでに実体のある、リスクのある作業のリスクが増加したことでしょう。
  • Users would have to deal with erasure (and therefore heap pollution) anyway(ユーザーはとにかくerasure(それゆえにヒープ汚染)に対処する必要がある)
    実行時に型情報を保持できたとしても、クラスをジェネリクスにする前にコンパイルされたクラスファイルが常に存在するため、ヒープ内の特定の ArrayList に型情報が添付されていない可能性が残存します。つまり、ヒープ汚染という付随するリスクがあります。
  • Certain useful idioms would have been inexpressible(特定の有用なイディオムは表現できなかった)
    既存のジェネリックコードは、コンパイラが認識しない実行時の型について何かを知っている場合、未チェックのキャストに頼ることがあります。ジェネリック型システムでこれを表現する簡単な方法はありません。これらのテクニックの多くは、具体化されたジェネリックでは不可能でした。つまり、別の方法で表現される必要があり、多くの場合、はるかに高価な方法で表現されていました。

コストとリスクが高かったことは明らかですが、メリットは何だったのでしょうか?以前、具体化の考えられる3つの利点、リフレクション、レイアウトの特殊化、および実行時の型チェックを挙げました。上記の議論の結果、実行時の型チェック(ランタイムコスト、決定不能リスク、エコシステムリスク、および消去されたインスタンスの存在)が発生する可能性はなくなりました。

確かに、 Listに その要素タイプが何であるかを尋ねられるとよいでしょう(そして、おそらく答えることができたかもしれませんが、答えなかったかもしれません)。これは明らかにゼロではない利点ですが、コストと利益が数桁違いだったというだけです(選択した変換戦略のもう1つのコストは、プリミティブを型パラメーターとしてサポートできないことです 。List<int> の代わりに、 List<Integer> を使用する必要があります)。

erasureが「ダーティなハック」であるというよくある誤解は、一般に、すでに記述されている大量の Java コードや JVM 実装と JVM 上で実行される言語の両方の多様なエコシステムを考慮して、エンジニアリングの労力、市場投入までの時間、配信リスク、パフォーマンス、エコシステムへの影響、およびプログラマの利便性の両方において代替案の真のコストがどのようなものであったかを認識していないことに起因していると考えられます。

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中