sid-array-a


Scala 2.8 配列 (Scala 2.8 Arrays)


Martin_Odersky、EPFL
2009 年 10 月 1 日

問題 (The Problem)


Scala では、配列は最もトリッキーな概念の 1 つであることが分かりました。 望ましいことを破綻させる、非常に難しい制約を扱わなければなりません。 一方で我々は、Java と相互運用するために配列を使うことを望みます。このため、配列は Java と同じ表現でなければなりません。 この下位レベル表現は、配列で高パフォーマンスを得るにも役立ちます。 しかし他方、Java の配列には厳しい制限があります。

まず、Java にはただ一つの配列型表現ではなく、実際には 9 つの異なる表現があります。: 参照型の配列のための表現が 1 つと、プリミティブ型 byte、char、short、int、long、float、double と boolean 等に対する 8 つの表現があります。 これらの異なる表現に共通の型はなく、単なる java.lang.Object よりいっそう特化しおり、java.lang.reflect.Array 中には任意の型の配列を扱ういくつかのリフレクション関連のメソッドさえあります。第二に、ジェネリック型の配列を生成する方法がありません。; ただ単相的な配列生成だけが許されています。 第三に、配列がサポートする操作は、インデックス付け、更新、長さのみです。

Scala で我々がしたいことと比べてみてください。 配列を、シーケンス上で定義される数百かそれ以上のメソッドをサポートするコレクション階層中に位置づけるべきです。 それらは必ずジェネリックで、型変数 T に対して Array[T] を生成できるべきです。


過去 (The Past)


Java との相互運用性およびパフォーマンスのために課せられた表現上の制約と、これら望まれることとをどのように統合できるでしょうか? 簡単な答えはなく、そして私は、我々が Scala を最初に設計したときに間違いをおかしたと思っています。 Scala 言語は 2.7.x まで、ボクシング/アンボクシングと呼ばれる処理で必要とされるときに、「魔法のように」配列をラップ/アンラップしていました。 それは、プリミティブな数値型をオブジェクトとして扱うときにすることと似ています。 「魔法のように」とは、次を意味します。: コンパイラは、式の静的な型に基づいてコードを生成します。 さらなるマジックにより、ジェネリック配列を生成します。 new Array[T] のような式は(ここで T は型パラメータ)、new BoxedAnyArray[T] に変換しました。

BoxedAnyArray was a special wrapper class ,which changed its representation depending on the type of the concrete Java array to which it was cast.

BoxedAnyArray は特別なラッパークラスで、具象 Java 配列の型に依存する表現をそれでキャストしたものへ変えます。この方法はたいていのプログラムで十分機能しました。 しかし、型テストと型キャストのある組み合わせに関して、未初期化配列のチェックに関しても、実装には「漏れ」が起きました。 予期しないパフォーマンスの低下も起こり得ました。 問題のいくつかは David MacIver[Mac08b] とMatt Malone[Mal09] によって述べられています。

ボックスされた配列も、共変コレクションと組み合わせると不健全でした。 まとめると、古い配列実装技術では解決が難しかったのです。なぜなら、漏れが起きる場所を特定することに大変な労力を強いられ、漏れを起こしやすい複雑な抽象化だからです。


解決策の探求 (Exploring the Solution Space)


配列に必要なマジック量を減らす明らかな方法は、2 つの表現を使うことです。: 1 つは Java 配列に密接に対応するもので、もう一方は Scala のコレクション階層と一体となる部分を形づくります。暗黙の型変換を使って、2 つの表現を透過的に変換できます。 これは、David MacIver (と Stepan Koltsov の貢献)による配列リファクタリング提案の要点です [Mac08a]。 この提案の主な問題は、私の見るところ、これがプログラマーに使うべき配列種の選択を強いることです。 その選択は明快ではありません。: Java ライクな配列は速く、相互運用可能であるのに対して、Scala ネイティブの配列は、もっとよく洗練された配列操作群をサポートします。 このような選択があるとき、異なる決定に対しては異なるコンポーネントとライブラリを用いることが期待されますが、それは、非互換性と脆弱で複雑なコードをもたらします。 MacIver と Koltsov は、その軽減のためにいくつかのコンパイラマジックを導入します。 彼らは、引数として配列をとるメソッドを 2 つのオーバーロードされたバージョンに自動的に分けることを提案します。: 1 つは Java 配列をとり、もう 1 つはジェネリックな Scala 配列をとるものです。 私はこれが、よりひどい配管工事問題をいくつか解くとは思いますが、しかし単に問題を隠して少しましになるだけであり、解決はしないと思います。

似ているが少し異なる観点を持つアイデアとして、Scala のコレクション階層に統合する暗黙の変換を用いて、ネイティブの配列を「ドレスアップ」するものがあります。 これは 2.8 以前の Scala 中で String から RichString への変換で用いた方式と似ています。 MacIver/Koltsov 提案との違いは、人は、Scala 中の RichString を滅多に参照しないのと同様に、通常はユーザーコード中で Scala ネイティブの配列を参照しないであろうということです。 人は、Java 配列に必要なメソッドとトレイトを加える、暗黙の型変換を当てにするだけでしょう。 特に、Scala 2.8 以前のバージョンにおいては、次のような直観的でないプロパティが使われました。

   "abc".reverse.reverse == "abc"      , yet
   "abc" != "abc".reverse.reverse      !

ここでの問題は、reverse メソッドをクラス Seq から継承していたことであり、そこでは、それが別の Seq を返すと定義されていました。 文字列はシーケンスではありませんから、String 上で呼ばれたときに reverseが返すことのできるただ 1 つの適した型は RichString でした。 しかしそうすると Java から継承される String 上の equals メソッドは、String が RichString と等価であり得るとは認識しません。


2.8 コレクション (2.8 Collections)


Scala 2.8 の新しい方式は、配列と文字列両方の問題を解決します。 それは、新しい 2.8 コレクションフレームワークをクリティカルに使い、Seq のようなコレクション・トレイトに、コレクションの表現にわたる抽象化を行う実装トレイトを関連づけます。 たとえば、トレイト Seq に加えて、次のトレイトがあります。

   trait SeqLike[+Elem, +Repr] { ... }

このトレイトは表現型 Repr でパラメータ化されています。 この表現型については、何も必要とされる前提がありません。; 特に、これは Seq のサブ型である必要はありません。 トレイト SeqLike 中の reverse のようなメソッドは、Seq ではなく表現型 Repr の値を返します。 Seq トレイトは、Reprパラメータを Seq にインスタンス化することで、SeqLike からそのすべての基本的操作を継承します。

 trait Seq[+Elem] extends ... with SeqLike[Elem, Seq[Elem]] { ... }

基本トレイトと実装トレイトへの似たような分割手法を、Traversable、Iterable や Vecotr を含め、他のほとんどの種類のコレクションに適用します。


配列の統合 (Integrating Arrays)


我々は 2 つの暗黙の変換を使って、配列をこのコレクションフレームワークへ統合します。 最初の変換は、Array[T] を、型 VectorLike[T,Array[T]] のサブ型である、型 ArrayOps のオブジェクトへマップします。 この変換を使って、自然な型の配列については、すべてのシーケンス操作が利用できます。 特に、メソッドは、その処理結果として ArrayOps 値の代わりに配列を出力します。 なぜなら、これら暗黙の型変換の結果は非常に短命なので、今の VM はエスケープ解析を使ってそれらを完全に除去できるからです。 ですから、それら付加的なメソッドに関する呼び出しオーバーヘッドは実質的にゼロであることが期待できます。

ここまでは良いのです。 しかしもし配列を、それ上の 単なる Seq メソッドの呼び出しではないような、実際の Seq に変換する必要があるならどうでしょう? そのために、配列をパラメータにとり、WrappedArray に変換するもう 1 つの暗黙の型変換があります。 WrappedArrays は、与えられた Java 配列のすべてのベクトル操作を実装する、ミュータブルな Vectorsです。 WrappedArray と ArrayOps オブジェクトの違いは、reverse のようなメソッド類では明らかです。: WrappedArray 上の呼び出しでは reverse は再び WrappedArray を返しますが、しかし ArrayOps オブジェクト上の呼び出しでは Array を返します。 Array から WrappedArray への変換は不可逆です。 対をなす 2 つの暗黙の型変換により WrappedArray が Array へ変換されます。 WrappedArray と ArrayOps は共にトレイト ArrayLike 実装を継承します。 これは ArrayOps と WrappedArray 間のコード重複を避けるためです。 すべての操作は、共通の ArrayLike トレイトへまとめ入れられています。


あいまいさの回避 (Avoiding Ambiguities)


このように、 Array から ArrayLike 値への 2 つの暗黙の型変換がありますが、どのように選び、どのように曖昧さを避ければよいのでしょうか? そのこつは、Scala 2.8 のオーバーロードと暗黙解決の一般化を利用することです。 以前は、もっぱらメソッドの引数型に基づき、最も特化(specific)したオーバーロードされたメソッド、あるいは暗黙の型変換が選択されていました。

There was an additional clause ,which said that the most specific method could not be defined in a proper superclass of any of the other alternatives.

最も特化したメソッドは他のいかなる代替物の固有(proper)のスーパークラス中で定義できない、と述べる付加的な節がありました。

この方式は Scala 2.8 では次の、より進歩的なものに置き換わりました。: オーバーロードされたメソッドあるいは暗黙の変換の、2 つの異なる適用可能な代替物を比較するとき、各メソッドは、より特化した引数を持つ場合は 1 ポイント獲得し、固有のサブクラス内で定義されている場合も 1 ポイント得ます。 これら 2 つの比較により、得点が多い方の代替物がもう 1 つに対して「勝ち」ます。 このことは特に、もし代替物が同一の引数型を持っていれば、サブクラスで定義されているものが勝つことを意味します。

このことを配列に適用すると、Array から ArrayOps への変換を標準的な Predef オブジェクト中に置き、Array から WrappedArray への変換を Predef から継承されているクラス LowPriorityImplicits 中に置くことで、Array から ArrayOps への変換を Array から WrappedArray への変換よりも優先できます。 このように、シーケンスメソッドの呼び出しは、常に ArrayOps への変換を起動します。 WrappedArray への変換は、配列をシーケンスに変換する必要があるときのみ起動されます。


String の統合 (Integrating Strings)


本質的に同じ方法を文字列に適用します。 2 つの暗黙の型変換があります。: 1 つは、String から StringOps への変換であり、クラス String に役に立つメソッドを加えます。 2 つめは、String から WrappedString への変換であり、文字列をシーケンスに変換します。


ジェネリック配列の生成とマニフェスト

(Generic Array Creation and Manifests)

以上でほとんど全てです。 唯一の残っている問題は、ジェネリック配列生成の実装方法です。 Java と異なり、Scala ではインスタンス生成 new Array[T] が可能です。 ここで T は型パラメータです。 Java のような統一的な配列表現が存在しないという事実の下、これをどのように実装できるでしょうか? その唯一の方法は、型 T を記述する実行時情報の追加を要求することです。 Scala 2.8 には、このためのマニフェストと呼ばれる新しいメカニズムがあります。 型 Manifest[T] のオブジェクト は、T についての完全な情報を提供します。マニフェスト値は通常、暗黙のパラメータとして渡されます。 そしてコンパイラは、静的にわかる型 T のおかげで、それらをどのように構築したらよいかがわかります。 ClassManifest と名付けられた、より弱い形もあります。 それは、必ずしもすべての引数型を知らずに、たんに型のトップレベルのクラスを知ることで、構築されます。 それは配列生成で必要とされる実行時情報の類です。

次は 1 つの例です。 0 から与えられた長さまでの数範囲に、与えられた関数 f を適用し、その結果からなる配列を出力する、メソッド tabulate (一覧)を考えてみます。 Scala 2.7 までは、tabulateを次のように書けました。:

   def tabulate[T](len: Int, f: Int => T) = {
     val xs = new Array[T](len)
     for (i <- 0 until len) xs(i) = f(i)
     xs
 }

Scala 2.8 では、これはもうできません。 なぜなら、Array[T] の正しい表現を生成するには実行時情報が必要だからです。 人が、メソッドへ暗黙のパラメータとして ClassManifest[T] を渡して、この情報を提供する必要があります。:

 def tabulate[T](len: Int, f: Int => T)(implicit m: ClassManifest[T]) = {
     val xs = new Array[T](len)
     for (i <- 0 until len) xs(i) = f(i)
     xs
 }

この代わりに略記形式として、型パラメータ T 上のコンテキスト境界(*1)を使えます。与えてみます。:

   def tabulate[T: ClassManifest](len: Int, f: Int => T) = {
       val xs = new Array[T](len)
       for (i <- 0 until len) xs(i) = f(i)
       xs
   }

(*1) 一般に、コンテキスト境界をもつ型パラメータは [T:Bound]の形です。; これは、型 Bound[T] の暗黙のパラメータと一緒にプレーンな型パラメータ T へ展開されます。

Int あるいは String、List[T] のような型上で tabulate を呼ぶときは、Scala コンパイラは tabulate へ暗黙の引数として渡すマニフェストクラスを生成できます。 その他の型パラメータ上で tabulateを呼ぶときは、人が、他の暗黙のパラメータあるいはコンテキスト境界を使ってマニフェストクラスが必要とすることを伝える必要があります。 たとえば。:

   def tabTen[T: ClassManifest](f: Int => T) = tabulate(10, f)

ボクシング方式を離れてマニフェストクラスへ向かうことは、上記の tabulate の最初のバージョン中にあるような、ジェネリック配列を生成する既存のコードを変えることになります。 必要な変更は通常、ある型パラメータにコンテキスト境界を追加するだけです。


クラス GenericArray (Class GenericArray)


ジェネリックな配列生成の場合にマニフェストを加えることは、よくありません。 Scala 2.8 は GenericArray クラスで配列の代替バージョンを提供します。 このクラスは、パッケージ scala.collection.mutable 内で次のように定義されています。

   class GenericArray[T](length: Int) extends Vector[T] {
       val array: Array[AnyRef] = new Array[AnyRef](length)
       ...
       // all vector operations defined in terms of `array'
   }

標準的な配列と異なり、GenericArrays はマニフェストクラスなしで生成できます。 なぜなら、それら配列が同一の表現を持っているからです。: それらの全ての要素は、Java の Object[] 配列に対応する、Array[AnyRef] に記憶されます。 Scala コレクションライブラリへの GenericArray の追加は、プログラマに、標準的な配列か、あるいはジェネリック配列を選ぶことを要求します。 この選択は、しかし、容易に答えることができます。: 要素型に対するマニフェストを容易に作れるときはいつでも、通常の配列を選ぶのがベターです。なぜなら、より速い傾向があり、よりコンパクトで、Java とより良い相互運用性があるからです。 マニフェストクラスを作成できないときだけ、GenericArray へ立ち戻って考えるべきです。 Scala の現在のコレクションフレームワーク中で、GenericArray が使われる唯一の場所は、Seq クラスの sortWith メソッドの中です。 xs.sortWith(f) の呼び出しは、そのレシーバ xs を最初に GenericArray に変換し、得られる配列を java.util.Arrays 中で定義された Java ソートメソッドに渡し、ソートされた配列を xs と同じ Seq の型へ戻し変換します。 配列への変換は sortWith の単なる実装詳細なので、シーケンスの要素型に対してマニフェストクラスを要求するのは合理的でないと感じました。 ですから GenericArray を選択しました。


まとめ (Conclusion)


まとめると、新しい Scala コレクションフレームワークは配列や文字列の長期にわたる問題をいくつか解決します。 かなりの量のコンパイラマジックを除去し、前の実装で存在したいくつかの落とし穴を回避します。 それは、ライブラリとフレームワークの構築で一般に役に立つ、Scala 言語の 3 つの新しいフィーチャーに依存しています。: 第一は、オーバーロードと暗黙の解決の一般化により、いくつかの暗黙の変換に優先順位を付けることが可能です。 第二は、マニフェストが型消去によって失われた型情報を実行時に提供します。 第三は、コンテキスト境界は、暗黙の引数のある形態に対する便利な略記表現となります。 これら 3 つの言語フィーチャーは、別のノートでより詳細に記述します。


参考文献 (References)


[Mac08a] David MacIver. Refactoring scala.array. Pre-SIP (Scala Improvement Proposal), October 2008 . http//www.drmaciver.com/repos/scala-arrays/sip-arrays.xhtml .

[Mac08b] David MacIver. Scala arrays. Blog, June 2008. http//www.drmaciver.com/2008/06/scala-arrays .

[Mal09] Matt Malone. The mystery of the parameterized array. Blog, August 2009 . http//oldfashionedsoftware.com/2009/08/05/the-mystery-of-the-parameterized-array .

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2011年04月05日 08:29
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。