Scala School意訳(Type & polymorphism basics) - seratch's weblog in Japanese

http://twitter.github.com/scala_school/type-basics.html

以下は私の方でtypoや表示崩れを直したものです。

https://github.com/seratch/scala_school/blob/master/web/_posts/2011-05-05-lesson.textile

誤訳などありましたら、お手数ですが、ご指摘いただければ幸いです。

What are static types? Why are they useful?

Benjamin C. Pierceは「型システムは、プログラムの句を計算結果の種類によって分類することで間違ったプログラムのふるまいがないことを自動的にチェックするための構文上の手法です」と言いました。

型はあなたに関数のドメインや値域を示します。数学から見慣れた例を挙げます。

f: R -> N

これは関数fが実数の集合から値を自然数の集合にマッピングすることを示しています。

考えてみれば、これはまさに具体的な型が何なのかという話です。
型システムはこういうものを表現するためのより強力なやり方を提供します。

これらの注釈（＝型の指定）があることで、コンパイラは静的に（コンパイル時に）プログラムが正当かを検証することができます。
すなわち、（実行時に）渡される値がプログラムによる制約に従っていない場合、コンパイルが失敗するということです。

一般的に言えば、型チェッカーは問題のあるプログラムをコンパイルできないということを保証するだけです。
型チェッカーは問題のないプログラムであればコンパイルできるということは保証できません。

型システムにおける表現力が増すことで、プログラムを実行する前にその不変条件を証明することができるようになるので、より信頼性の高いコードを書くことができます（もちろん型自体に法としてのバグはありえます！）。
学術的な世界では、値依存な型のようにその表現力に非常に厳しく制限を設けています！

注釈：型情報はコンパイル時に除去されます（訳者追記：バイトコード内に残らない）。もはや必要としないからです。これは型消去と呼ばれます。

（訳者追記）

上記に出てきたPierceによる型システムの説明の元ネタはこちらのようです。

Benjamin Pierce's Types and Programming Languages (MIT Press, 2002)

補足として、型消去についてオライリー本における記述を引用します。

プログラミングScala

作者: Dean Wampler,Alex Payne,株式会社オージス総研オブジェクトの広場編集部
出版社/メーカー: オライリージャパン
発売日: 2011/01/20
メディア: 大型本
購入: 2人クリック: 300回
この商品を含むブログ (38件) を見る

まず、型消去の定義は

JVMにおけるジェネリクス型モデルの性質。ジェネリクスから型が生成されたとき、その型パラメータに代入された型の情報はバイトコードには格納されておらず、実行時には利用できない。Scalaも同様のモデルに従う必要がある。そのため、たとえばList[String]とList[Int]のインスタンスは区別がつかない。「レイファイされた型」とは対照的。

レイファイされた型については、以下のような説明です。

実行時に利用できるよう、ジェネリクス型のインスタンス生成時に指定した型の情報が、バイトコードに保持されたもの。これは.NETのバイトコードが持つ性質であり、型消去を使うJavaバイトコードにはない。非互換性を最小化するために、ScalaではJavaと.NETの両方のバージョンで型消去を使う。

もっと簡単に説明しているところだと

ジェネリクスの型パラメータが、バイトコードレベルで「消去」されている（「型消去」と呼ばれる）。たとえば、List[Int]が生成された場合、Int型はバイトコード中には存在しない。

型消去といえばManifestの話題が欠かせませんが、それは次の回（Advanced Types）に登場します。

Types in Scala

Scalaには豊かな表現を可能にするとても強力な型システムがあります。その主な特長は以下の通りです。

- パラメータ多相（ポリモーフィズム）: parametric polymorphism
- （ローカルな）型推論： (local) type inference
- 存在量化： existential quantification
- ビュー： views

Parametric polymorphism

ポリモーフィズムは、静的型付けの豊かさを損なうことなく（異なる型の値に対して）汎用なコードを書くために使用されます。

たとえば、パラメータポリモーフィズムがなければ、汎用リストのデータ構造はいつもこんな感じになってしまうでしょう（ジェネリクス以前のJavaはまさにこんな感じだったのです）。

scala> 2 :: 1 :: "bar" :: "foo" :: Nil
res5: List[Any] = List(2, 1, bar, foo)

こうなってしまってはもはや各メンバーの型情報を復元することはできません。

scala> res5.head
res6: Any = 2

そして、私達のコードはキャストの類を使ったものに退化し、型安全さは失われてしまいます（なぜなら全て動的になっているからです）。

ポリモーフィズムは型変数を指定することで実現されます。

scala> def drop1[A](l: List[A]) = l.tail
drop1: [A](l: List[A])List[A]

scala> drop1(List(1,2,3))
res1: List[Int] = List(2, 3)

Scala has rank-1 polymorphism

このように関数があると仮定して

def toList[A](a: A) = List(a)

それを汎用に使いたい（fooの引数fとして渡したい）と思うわけですが

def foo[A, B](f: A => List[A], b: B, c: Int) = (f(b), f(c))

このコードをコンパイルすることはできません。
なぜならメソッド起動時に全ての型変数は確定している必要があるからです。

（訳者追記）

これは別の言い方をすると、型変数Aと型変数B、Int型とが整合するか確定しないのでコンパイルできないということになるかと思います。

scala> def toList[A](a: A) = List(a)
toList: [A](a: A)List[A]

scala> def foo[A, B](f: A => List[A], b: B, c: Int) = (f(b), f(c))
<console>:7: error: type mismatch;
 found   : b.type (with underlying type B)
 required: A
       def foo[A, B](f: A => List[A], b: B, c: Int) = (f(b), f(c))
                                                         ^
<console>:7: error: type mismatch;
 found   : c.type (with underlying type Int)
 required: A
       def foo[A, B](f: A => List[A], b: B, c: Int) = (f(b), f(c))
                                                               ^

たとえば以下のようなものであれば、コンパイルできます。

def foo[A, B](f: A => List[A], b: A, c: A) = (f(b), f(c))
def foo[A, B <: A](f: A => List[A], b: B, c: A) = (f(b), f(c))

ここで問題になっているのは、b、cの型がfの引数の型Aとしてみなせるのかどうか、という点です。

Type inference

静的型付けに対するお決まりの異論は構文上のオーバーヘッドが大きいというものです。
Scalaは型推論を提供することにより、これを軽減しています。

関数プログラミングにおける型推論の古典的な手法はヒンドリー-ミルナー型推論で、これはMLで初めて採用されました。
Scalaの型推論は少し違っていますが、気質としては似通っています（制約の推論、型を統一する試み）。

Scalaでは、たとえばこのようなことはできません。

scala> { x => x }
<console>:7: error: missing parameter type
       { x => x }

一方でOCamlでは可能です。

# fun x -> x;;
- : 'a -> 'a = <fun>

Scalaの型推論は全てローカルです。たとえば

scala> def id[T](x: T) = x
id: [T](x: T)T

scala> val x = id(322)
x: Int = 322

scala> val x = id("hey")
x: java.lang.String = hey

scala> val x = id(Array(1,2,3,4))
x: Array[Int] = Array(1, 2, 3, 4)

型は保存されています。Scalaコンパイラが私達のために型パラメータを推論してくれます。また私達が戻り値の型を明確に指定する必要がないことにも注目してください。

（訳者追記）

常に戻り値の型を省略できるとは限りません。例えば、再帰呼び出しされるメソッドでは戻り値の型を省略できません。

scala> def p(str: List[Int]) = str match {
     |   case Nil => 
     |   case h :: t => { println(h); p(t) }
     | }
<console>:10: error: recursive method p needs result type
         case h :: t => { println(h); p(t) }
                                      ^

scala> def p(str: List[Int]): Unit = str match {
     |   case Nil => 
     |   case h :: t => { println(h); p(t) }
     | }
p: (str: List[Int])Unit

scala> p(List(1,2,3,4,5))
1
2
3
4
5

Variance

Scalaの型システムはクラス階層についてポリモーフィズムと併せて説明しなければなりません。
クラス階層はサブ型の関係性の表現を可能にします。

オブジェクト指向とポリモーフィズムをミックスすると出てくる重要な問題は、もしT'がTのサブクラスだとしてContainer[T']はContainer[T]のサブクラスと考えるのかという疑問です。
変位指定がクラス階層とポリモーフィックな型について以下のような関係性について表現を可能にします。

共変（covariant）：C[T']はC[T]のサブクラスです
反変（contravaliant）：C[T]はC[T']のサブクラスです
非変（invariant/nonvariant）：C[T]とC[T']は関係がありません

サブ型の関係性とは実際こういうことです。「T型にとってT'がそのサブ型だとしてT'はTを置き換えることができるか？」

// 訳者追記：以下は共変のサンプル

scala> class Covariant[+A]
defined class Covariant

scala> val cv: Covariant[AnyRef] = new Covariant[String]
cv: Covariant[AnyRef] = Covariant@4035acf6

scala> val cv: Covariant[String] = new Covariant[AnyRef]
<console>:6: error: type mismatch;
 found   : Covariant[AnyRef]
 required: Covariant[String]
       val cv: Covariant[String] = new Covariant[AnyRef]
                                   ^

// 訳者追記：以下は反変のサンプル

scala> class Contravariant[-A]
defined class Contravariant

scala> val cv: Contravariant[String] = new Contravariant[AnyRef]
cv: Contravariant[AnyRef] = Contravariant@49fa7ba

scala> val fail: Contravariant[AnyRef] = new Contravariant[String]
<console>:6: error: type mismatch;
 found   : Contravariant[String]
 required: Contravariant[AnyRef]
       val fail: Contravariant[AnyRef] = new Contravariant[String]

反変は奇妙な感じだと思います。一体いつ使うというのでしょう？ちょっと驚きですね！

trait Function1 [-T1, +R] extends AnyRef

もしこれについて置換の視点から考えるとすれば、かなり納得のいく話です。

シンプルなクラス階層を定義してみましょう。

scala> class A
defined class A

scala> class B extends A
defined class B

scala> class C extends B
defined class C

scala> class D extends C
defined class D


scala> val f: (B => C) = ((b: B) => new C)
f: (B) => C = <function1>

scala> val f: (B => C) = ((a: A) => new C)
f: (B) => C = <function1>

scala> val f: (B => C) = ((a: A) => new D)
f: (B) => C = <function1>

scala> val f: (B => C) = ((a: A) => new C)
f: (B) => C = <function1>

scala> val f: (B => C) = ((c: C) => new C)
<console>:8: error: type mismatch;
 found   : (C) => C
 required: (B) => C
       val f: (B => C) = ((c: C) => new C)
                                 ^
                                    ^

（訳者追記）

以下、誤りです。ご指摘ありがとうございました。


共変（covariant）： [+T] はJavaでいうとと同じです
反変（contravaliant）： [-T] はJavaでいうとと同じです
非変（invariant/nonvariant）：[T]はJavaでいうとと同じです

Bounds

Scalaでは境界を使ってポリモーフィックな制約をつくることができます。
この境界はサブ型の関係性を表現します。

scala> class F { def foo = "F" }
defined class F

scala> class E extends F { override def foo = "E" }
defined class E

// 訳者追記：以下は境界を指定してない例で当然のごとくコンパイルエラー

scala> def callFoo[T](foos: Seq[T]) = foos map (_.foo) foreach println
<console>:8: error: value foo is not a member of type parameter T
       def callFoo[T](foos: Seq[T]) = foos map (_.foo) foreach println

// 訳者追記：上限境界（Fかそのサブクラスのみ指定可能）を指定した例

scala> def callFoo[T <: F](foos: Seq[T]) = foos map (_.foo) foreach println
callFoo: [T <: F](foos: scala.collection.mutable.Seq[T])Unit

scala> callFoo(Seq(new E, new F))
E
F

下限境界もまたサポートされています。これは反変と同調して動作します。

Nodeというクラスがあると仮定してみましょう。

scala> class Node[T](x: T) { def sub(v: T): Node[T] = new Node(v) }

Tを共変にしたいと思います。

scala> class Node[+T](x: T) { def sub(v: T): Node[T] = new Node(v) }
<console>:6: error: covariant type T occurs in contravariant position in type T of value v
       class Node[+T](x: T) { def sub(v: T): Node[T] = new Node(v) }
                                      ^

subメソッドの引数は反変だったことを思い出してください。
置換トリックを実行するためには前と同じようなクラスを使う必要があります。

class Node[B](x: B) { def sub(v: B): Node[B] = new Node(v) }

このクラスは以下のクラスのサブ型ではありません。

class Node[A](x: A) { def sub(v: A): Node[A] = new Node(v) }

なぜなら、Aはsubメソッドの引数としてのBを置き換えることができないからです。

一方で下限境界を正確さを強制するために使うことができます。

scala> class Node[+T](x: T) { def sub[U >: T](v: U): Node[U] = new Node(v) }
defined class Node

// 訳者追記：Nodeの型パラメータがBになっている
scala> (new Node(new B)).sub(new B)
res5: Node[B] = Node@4efade06

// 訳者追記：Nodeの型パラメータがAになっている
scala> ((new Node(new B)).sub(new B)).sub(new A)
res6: Node[A] = Node@1b2b2f7f

// 訳者追記：Nodeの型パラメータがasInstanceOfで指定されたCになっている
scala> ((new Node(new B)).sub(new B)).asInstanceOf[Node[C]]
res7: Node[C] = Node@6924181b

// 訳者追記：Nodeの型パラメータがAになっている
scala> (((new Node(new B)).sub(new B)).sub(new A)).sub(new C)
res8: Node[A] = Node@3088890d

subメソッドの後続の呼び出しでの型変換（=asInstanceOf）にも注目してください。

（訳者追記）
下限境界を指定している場合、subから返るNode[U]のUは、このインスタンスの型に指定されている型パラメータと引数の型を比較して、より親である型が指定されています。

class A
class B extends A
class C extends B
class D extends C
class Node[+T](x: T) { 
  def sub[U >: T](v: U): Node[U] = new Node(v) 
}
new Node(new B).sub(new A).sub(new C) // Node[A]

下限境界を指定しなかった場合、引数の型がそのまま型として指定されることになります。

class Node2[+T](x: T) { 
  def sub[U](v: U): Node2[U] = new Node2(v)  
}
new Node2(new B) // Node2[B]
new Node2(new B).sub(new A) // Node2[A]
new Node2(new B).sub(new A).sub(new C) // Node2[C]

Quantification

時々、型変数に名前をつけたくない場合があります。

たとえば以下の例ではAという名前をつけています。

scala> def count[A](l: List[A]) = l.size
count: [A](List[A])Int

そういう場合は代わりにワイルドカードを指定することができます。

scala> def count(l: List[_]) = l.size
count: (List[_])Int

これは以下のやり方の省略形です。

scala> def count(l: List[T forSome { type T }]) = l.size
count: (List[T forSome { type T }])Int

存在量化はこのようにちょっとトリッキーなことになったりするので注意してください。

scala> def drop1(l: List[_]) = l.tail
drop1: (List[_])List[Any]

突然、型情報が失われてしまいましたね！
何が起こっているか見るために、不器用な構文に戻してみましょう。

scala> def drop1(l: List[T forSome { type T }]) = l.tail
drop1: (List[T forSome { type T }])List[T forSome { type T }]

こうなるとT型はもう何と表現したらよいかわかりませんね。

あるいは、ワイルドカードの型指定で境界を適用することもあるかもしれません。

scala> def hashcodes(l: Seq[_ <: AnyRef]) = l map (_.hashCode)
hashcodes: (Seq[_ <: AnyRef])Seq[Int]

scala> hashcodes(Seq(1,2,3))
<console>:7: error: type mismatch;
 found   : Int(1)
 required: AnyRef
Note: primitive types are not implicitly converted to AnyRef.
You can safely force boxing by casting x.asInstanceOf[AnyRef].
       hashcodes(Seq(1,2,3))
                     ^

scala> hashcodes(Seq("one", "two", "three"))
res1: Seq[Int] = List(110182, 115276, 110339486)

（訳者追記）
ここでの話題はオライリー本では「12.11 存在型」として扱っています。存在型は「Existential types」です。

Scalaの型パラメータは型消去によりバイトコードレベルでは失われてしまうので、例えば、このようなパターンマッチは警告が出ますし、結果も「Int...」と出力されてしまいます。

scala> val something = List("a","b","c")
something: List[java.lang.String] = List(a, b, c)

scala> something match {
     |   case intList: List[Int] => println("Int...")
     |   case strList: List[String] => println("String!")
     |   case _ => 
     | }
warning: there were 2 unchecked warnings; re-run with -unchecked for details
Int...

型パラメータによるパターンマッチはできません。型パラメータを持つ型に対してパターンマッチを行う場合は、ワイルドカードである「_（アンダースコア）」を使ってListであるというところに焦点をあてることになります。

something match {
  case list: List[_] => println("It's a List!")
  case _ => println("It's not a List...")
}

このワイルドカード指定の「List[_]」は実は存在型「List[T] forSome { type T }」の省略形です。Scala Schoolでの「List[T forSome { type T }]」と若干違いますが、どちらも有効のようです。

scala> def count(l: List[T forSome { type T }]) = l.size
count: (l: List[T forSome { type T }])Int

scala> def count(l: List[T] forSome { type T }) = l.size
count: (l: List[_])Int

オライリー本では存在型についてこう説明しています。

Scalaのコード中で、forSomeという存在型の構文が使われることはあまりないでしょう。なぜなら、存在型は主にScalaの型システムにおける正しさを維持しながら、Javaのジェネリクスをサポートするためのものだからです。ほとんどの文脈では、型推論がこの詳細を隠します。