LoginSignup
28
9

More than 5 years have passed since last update.

Fringe81Advent Calendar 2018Day 10fringe81
@gion(Yuya ONUMA)inUnipos株式会社

Scala 2.13 のコレクションライブラリの設計について

Last updated at Posted at 2018-12-10

はじめに

Scala (v2.12) のコレクションのクラス構造が謎だなとはわりと思っていて（Xxx と XxxLike と GenXxx ってなに〜）、The Architecture of Scala Collections あたりを読んでまとめようと思っていました。
しかし、v2.13 でコレクションに入る（正確に言うと、 2.13.0-M4 で入った）変更をドキュメントやソース読みつつ調べていたら、ほんとうに大きな変更だなあ、なんだかここでまとめてももったいないなあ、という気持ちになってきたので 2.13 のコレクションについてざっくり調べてみることにしたのでした。

この記事では、scala-lang.org にある、コレクションライブラリの設計概念について書かれているドキュメントをざっくり訳しつつ 2.13 でのコレクションの設計などについて理解を深めようと思います。

TL; DR

2.13 でのコレクションライブラリの設計や実際の変更について知りたいならこれらを読めばだいたいわかるんじゃないかと思います。

免責

  • ドキュメントの意図を正しく表現できていることは保証しません
    • 誤り指摘は歓迎です

LICENSE

The following document is Japanese translation of Stefan Zeiger's "Scala 2.13 Collections Rework" (https://www.scala-lang.org/blog/2017/02/28/collections-rework.html).

This document is licensed by @gion under a Creative Commons Attribution-Share Alike 3.0 Unported license ("CC-BY-SA").

Scala 2.13 Collections Rework

2015年の10月に Odersky は Scala 2.13 向けの新しいコレクションライブラリの試案を求めた。
Scala のコレクションの再設計ははじめてのことではなく、現在の形のものは Scala 2.8 においてはじめて実装され、Scala コンパイラの型推論に必要な改良が加えられた。
現在のコレクションライブラリはおおむね共通のインターフェースとコードベースを持つ、可変・不変、直列・並列なコレクションを提供しており、基本的には成功しているといえる一方で、セカンドシステム症候群の兆候を示しているような部分もある。

Goals

問題点や新しい設計での解決策の案を探す前に、新しい設計が目指すところから定義する:

  • APIの単純化（利用者向き）: これには一般的な操作を CanBuildFrom なしで行うこと、継承ツリーを整理すること、可変コレクションと不変コレクションに対する操作のよりよい分離が含まれる
  • APIの単純化（ライブラリ開発者向き）: いまのところ、新しいコレクション型の実装は自明からはほど遠く、望む型の CanBuildFrom のインスタンスが得られるように implicit なオブジェクトを用意するのは面倒。また、たくさんのデフォルト実装を継承できるのは利点に見える一方で、それが十分な性能を発揮するかは自分でチェックし、必要ならオーバーライドしないといけない
  • よりよい性能のためのデザイン: 最高のアルゴリズムも、プリミティブ型に対する特殊化や JVM のメソッドディスパッチなどの低レイヤにおけるパフォーマンスへの懸念を無視してしまっては有用にならない。Slick のクエリコンパイラでは、Scala ライブラリのものではなく自前のコレクションを利用することで 25% の性能向上を果たした。一般化されたライブラリで同等の性能向上は達成できなくても、改善の余地があることは示されている
  • 2.12 との高い互換性: コレクションの使い方の大部分は 2.12 と 2.13 の間で互換性を保ち、非互換な部分もおおむね ScalaFix で自動的に修正できるだろう

Traversable and Iterable

現在のコレクションライブラリは、基本的に Traversable を継承ツリーのルートとしているが、これの実際のサブクラスは Iterable のみである。
両者の違いは、 Traversable が foreach として内部的イテレーションを提供するにとどまるのに対し、 Iterable が Iterator 型を通してより強力な外部的イテレーションを提供している。
Traversable での抽象化は現在のライブラリにおいては重要ではなく、また新設計においても表出することはないため、 Iterable があれば事足りる。

また、コレクションのトレイトを削除する他の機会も窺っている。それぞれのトレイトは妥当な理由があって存在してはいるが、その数とそれらの相互作用でライブラリの複雑度が高くなっている。たとえば、現在の List クラスの宣言について:

sealed abstract class List[+A] extends AbstractSeq[A]
                               with LinearSeq[A]
                               with Product
                               with GenericTraversableTemplate[A, List]
                               with LinearSeqOptimized[A, List[A]]
                               with scala.Serializable {
  ...
}

親タイプは全部で40個近くになる。

CanBuildFrom

現在のコレクションライブラリの中で最も強力であり、一方で議論の余地にあるものの1つは CanBuildFrom だ:

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That

これは TraversableLikeで宣言されている map メソッドのシグニチャだ。初心者にはこれは分かりにくいため、意図をより明確に伝える『ユースケースの』シグネチャがAPIドキュメントに追加された:

 def map[B](f: A => B): $Coll[B]

これによって Scaladoc 上ではわかりやすくなったものの、IDEでの補完やコンパイラのエラーでは依然として実際の定義と付き合う必要がある。

新設計では、 map メソッドは次のように宣言される:

def map[B](f: A => B): C[B]

このメソッドは期待されたシグネチャを持ち、正しい CanBuildFromを探索するコンパイル時や実行時のオーバーヘッドもなく、また型コンストラクタ C はほとんどのユースケースで具象コレクション型となるように改善されているために、Scaladoc のみでなくコード補完やエラーメッセージ中でも期待されたシグネチャの形で見ることができる。

CanBuildFrom は Scala 2.8 で導入され、これによって制約のないコレクションと、要素の型に対する implicit evidence1 を必要とする制約付きコレクションの両方に対して map などの標準的なメソッドの定義を1度で済ますことができる。
たとえば、 BitSet は class BitSet extends Set[Int] と自然に定義できるだろうが、次のように map を呼ぶことは何を意味するだろうか:

val s: BitSet = ...
val c1 = s.map(i => i+1)
val c2 = s.map(i => i.toString)

現在の設計では c1 として BitSet を、 c2 として HashSet を実行時に構築するだけでなく、型推論をコンパイル時に行うこともできる。
一方で、次のようなコードになると、話は複雑になってくる:

val s: BitSet = ...
val c1 = (s: Set[Int]).map(i => i+1)

ここで c1 が BitSet になるとは考えないだろうが、このときにも依然実態としては BitSet なのか、それとも既定の Set 実装が用いられるのだろうか。実際この場合は後者であるが、現在のライブラリにおいてはコンパイル時と実行時で Builder 型の探索の整合性がとれていないので、型か実装が予期しないものになる可能性がある2。

先に見たように、新設計では map が implicit evidence をパラメータとしてとらないので、BitSetを BitSet として扱っていても Set[Int] として扱っていても、常に同じ実装を利用することが保証され、この場合は Set の実装が利用される。
コレクションの実装は、制約がない限り、（継承ツリーにおいて、スーパークラスと自身の間にいる）任意のコレクション型を返すことができる。
BitSet.map を呼び出して、別の制約付き BitSet を得るようにするには、 map メソッドをオーバーロードする必要がある:

class BitSet extends Set[Int] {
  //def map[B](f: Int => B): Set[B]  // 継承で得たもの

  def map(f: Int => Int): BitSet
}

Scala 2.12 における型推論の強化によって、オーバーロードしたメソッドをラムダ関数を引数にして呼ぶときに型アノテーションが不要になっている:

val s: BitSet = ...

// Scala 2.11 以下ではこう書かないといけない:
val c1 = s.map((i: Int) => i+1)

// 2.12 以降ではこれでよい:
val c2 = s.map(i => i+1)

BitSetは若干特殊なコレクション型であるが、要素型 T についての暗黙的な制約の原則は他のコレクション型にも適用される:
- BitSet: T <:< Int （『Int でなくてはならない』）
- 全ての Map 型: T <:< (_, _) （『Tuple2 でなくてはならない』）
- 全ての Sorted なコレクション（TreeSet など）: Ordering[T] （『順序がなければならない』）
- String（それ自体はコレクションではないが、コレクションのメソッドを持つ）: T <:< Char （『Char でなくてはならない』）
- Array（String と同様にコレクションではないが）: ClassTag[T] （『型タグを持っていなくてはならない』）

ここで説明した設計では、 CanBuildFrom のほとんどの用途をはるかに簡単な方法で実現する。
新設計で直接サポートできない重要なユースケースに、 collection.breakOut （別のコレクション型を追加の変換ステップなしに直接作成する）と to （CanBuildFromを使用できる別のコレクション型に変換する）があるが、同じ効果を達成するための代替方法を提供する。

FromIterable

to メソッドは新設計でも依然存在するが、制約のない全てのコレクション型のコンパニオンオブジェクトによって実装されるメソッドの抽象である FromIterable のデコレータでしかない:

trait IterableOps[+A] extends Any {
  def to[C[X] <: Iterable[X]](fi: FromIterable[C]): C[A @uncheckedVariance] =
    fi.fromIterable(coll)
  ...
}

trait FromIterable[+C[X] <: Iterable[X]] {
  def fromIterable[B](it: Iterable[B]): C[B]
}

fi は（現在のライブラリの CanBuildFrom と違い）implicit でないため、型と一緒に呼び出して CanBulidFrom を探索するのではなく、値で呼び出して型を推論する:

val s: Set[Int] = ...
val v = s.to(Vector) // いままでは to[Vector]

この設計には Map やその他の制約つきコレクション型 to をオーバーロードできるという利点もある（現在のライブラリでは to は引数が1つの型コンストラクタにしか適用できない）。

Views

現在のコレクションライブラリにおいて、ビューはライブラリ実装の複雑さを高めている割にあまり使われていない機能のひとつである。新設計では不変ビューと可変ビューを分離し（後者はまだ実装されていないが）。不変ビューはインデックスがあるかどうかで2つに分けることで、構造が大幅に簡潔化される。

概念的にはビューは Java 8 の Stream のように、新しい View を作成する中間操作（filter や flatMap など）と、 現在のViewで表わされている操作を Iterator に対して実行する終端操作（foreach や foldLeft など）を持つようになる。
これにより、中間操作によるビューの作成は基本となるコレクションの変化とは常に独立し、終端操作を呼び出すときだけコレクションの現在の状態が使用されるようになるため、可変コレクションに使用しても、明確なセマンティクスが得られる。

ビューは collection.breakOut の代替としても推奨される。たとえば、次の式:

val s: Seq[Int] = ...
val set: Set[String] = s.map(_.toString)(collection.breakOut)

は、同様のパフォーマンス特性を保ったまま、次のように書ける:

val s: Seq[Int] = ...
val set = s.view.map(_.toString).to(Set)

複数の操作を組み合わせた場合、実際の操作は遅延される:

val s: Seq[Int] = ...

// フィルタした Seq を作り、次にマップした Seq をつくり、Set にする
val set1 = s.filter(_ > 0).map(_.toString).to(Set)

// filter と map を同時に評価して Set を直接作る
val set2 = s.view.filter(_ > 0).map(_.toString).to(Set)

Laziness

ビューとは別に、現在のコレクションライブラリは遅延コレクションもサポートしているものの、一級市民の扱いを受けない。
Stream は tail のみ遅延評価で head は正格評価され、また実装はほとんどの部分で自前の実装を必要とする。
なぜならば、新しいコレクションのインスタンスを構築するための基本抽象（正格コレクション型が安全に継承できるデフォルト実装）が、正格評価で push ベースでコレクションを構築する CanBuildFrom や Builder を用いているからだ。
FromIterable と新設計における View を組み合わせることで、コレクションの正格・遅延を問わず使える pull ベースの構築メソッドを提供することができる。実際、次に示すものが map の共通実装であり、遅延コレクションとするために LazyList でオーバーライドする必要はない3:

def map[B](f: A => B): C[B] = fromIterable(View.Map(coll, f))

View に対する操作から現在のコレクション型を再構築できることに基いて、このような共通実装にまとめるができる。
Iterator を取得し、必要に応じて要素を1つずつ取り出すだけで、 LazyList を Iterable から『構築』することができるため、この共通実装から遅延評価する map の実装が自動的に得られる。

Language Integration

Predef または scala パッケージオブジェクトのスコープにあるデフォルトの型の非対称性について疑問に思ったことがあるかもしれない:

scala> classOf[Set[_]]
res1: Class[Set[_]] = interface scala.collection.immutable.Set

scala> classOf[Map[_, _]]
res2: Class[Map[_, _]] = interface scala.collection.immutable.Map

scala> classOf[Seq[_]]
res3: Class[Seq[_]] = interface scala.collection.Seq

このように、Seq のみは不変コレクションではなく、可変シーケンスと不変シーケンスの両方を含むものになっている。
この理由は、Scala の言語仕様において、可変長引数を scala.Seq 型としているからだ（また、最上位である scala パッケージに含まれない型に依存したくないため）。
Java（および JVM）の可変長引数は実際に変更可能な配列なので、デフォルトの Seq は可変コレクションを許容する必要がある。
しかし実際には、このようなの配列は準不変として扱うことができるので、新設計に ImmutableArray ラッパーを追加して可変長引数に使用できるようにすることで、不変ではなくなっているデフォルトの Seq 型への依存を取り除くことを考えている。

Outlook

（訳註: ドキュメントが書かれた当時、新コレクションライブラリが github.com/scala/collection-strawman で開発中であることや、今後の展望などが書いてある。情報が古いところもあるので省略）

（訳出ここまで）

このドキュメントやほかのものを見ながらの所感とか

  • 2.12 との互換性をとろうと頑張っているけれど、一部非互換になるところが出てくる
    • コレクション自作とかしている人はつらそう
  • 2.13.0-M4 で scala/scala にマージされた
    • 既存のコレクション関連のトレイトも結構 deprecated になったりしている
  • 並列コレクションが別モジュールとして切り出されるらしいが M4 に追いついてなさそうな雰囲気
  • 結論として、利用者としては大変更を強いられることはあまりなさそうだしそこまで気に病まなくてもよさそう
    • ライブラリ開発者は……
  • 2.13 と 2.12 のコレクション構造に多少明るくなれてよかった

今後の展望

  • Scala のソースもう少し読みたい
  • v2.13 実際に触る
  • このコードがこう書き変えられる、というようなユーザー側からの違いも書いてみる

  1. この場合の evidence って訳したほうがいいのか、その場合ふつうどんな訳が当たるのか ↩

  2. この段落を正しく訳せてる自信がない。とくに "still backed by" のくだり ↩

  3. いまの 2.13.0-M4 では共通実装になっていない（ただし必要なものは実装されているようなので、たとえば List と LazyList で def mapV[B](f: A => B): C[B] = fromIterable(new View.Map(coll, f)) などとしてあげれば期待の動作をしてくれそうな感じはある）。同一のコードベースでやるにはパフォーマンス等々で問題があったのかな？（未調査） ↩

28
9
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
28
9