勉強帳 (3)

資料: http://www.scala-lang.org/docu/files/ScalaByExample.pdf

5. First-Class Functions

関数がファーストクラスな話。

5.1 Anonymous Functions

すでに出てきたと思うけど

(x: Int) => x * x

が匿名関数。Int 型の引数を 1 つ受け取って、二乗を返す。ただし、Int => Int であることが文脈からわかる場合は

x => x * x

だけ書いてもいい。インタプリタでそこだけ試すときとかは型が必要なので、多少 lightweight でない気分になった。まあとても些細な話だけど。

以下の 2 つが同値。

(x1: T1, ..., xn: Tn) => E
{ def f(x1: T1, ..., xn: Tn) = E; f _ }  // ただし f は fresh

なので Scala では匿名関数は syntax sugar らしい。おおかっこいい。しかしここまでに _ の説明がなかったぞ。

5.2. Currying

カリー化の話。想定読者が Java プログラマのせいだろうけど、説明が冗長。
文法の話の要約だけ。以下の 2 つが同値。

def f (x1: T1) ... (xn: Tn) = E
def f = (x1: T1) => ... => (xn: Tn) => E

5.3. Example: Finding Fixed Ponts of Functions, 5.4. Summary

スルー

5.5. Language Elements Seen Sor Far

ここまでの文法の BNF 的なもの。

• リテラルは Java と同じ。
• 識別子は以下のような感じに書いてある。

letter   ::= 'a' ... 'z'
operator ::= '#', '+', ':', etc.
ident    ::= letter (letter | digit)*
           | operator+
           | ident '_' ident

しかしこの通りだと、x_ や _x や f_1 が識別子にならない。でも試してみると識別子になってる。文法の間違いか、未定義挙動か。
普通の言語と違って、以下のようなのも識別子。

+
--
foldl_:
+_vector

いやー、DSL 作り甲斐のありそうな言語ですね。
あとは細かいこと。x+-y は x 、+- 、y になるので、x+(-y) という意味で書きたかったらスペースあけろ。$ はコンパイラ用に予約されているので使うな。

識別子以外の知見は以下のとおり。ただ、説明用の不正確な BNF みたいなので、あまり当てにならない。

• => Unit という型はない。def foo(f: => Unit) の => は型ではなく call-by-name の指示にすぎないみたい。
• 単項演算子は + と - と ! と ~ だけっぽい。再定義が出来るかどうかなどはわからない。

6. Classes and Objects

あんまし面白くないのでスルー気味に。

細かいこと

• class の中で private def x = e や private val x = e とすれば private メンバになるよ。
• 継承元を省略した場合は scala.AnyRef を継承したことになるよ。Java 実装の場合、これは java.lang.Object の alias 。
• オーバーライドする際は override def と明示的に書いてね。
• 0 引数メソッドと無引数メソッドの違い、def と val の違いはすでに説明があったとおり。
• abstract class はご存知のとおり。
• traits はすでに出てきたとおり。

object 定義

Hello, world にでてきた、singleton オブジェクトみたいな、特異メソッドのあるオブジェクトみたいなやつ。
class 定義とほぼ同じ文法で object 定義もできる。ただしコンストラクタの仮引数はない。object 定義はどこにでもおけるらしい。必要になるまでオブジェクト生成は延期される。
companion object の説明はなかった。

標準クラス

Int や Boolean の標準クラスは 32 bit 整数なり Java の boolean なりに最適化されるけど、言語仕様上からはただのオブジェクトにしか見えないよ。当たり前だよね。
あと遅延評価があるから Boolean や ifThenElse も自分で定義できるんだよ。すごいよね。
あとせっかくだから Church encoding による Int の実装も書いてみたよ。
という内容だった。

7. Case Classes and Pattern Matching

計算機を題材に。
演算式を表す木を考える。整数がリーフ、+ がノード。これをオブジェクト指向で普通に表現するには、整数とノードをそれぞれ Number と Sum みたいなクラスとして定義する。この演算式を評価するには、Number と Sum に eval メソッドをそれぞれ持たせる。めでたし。
これで終わればいいけれどそうはいかない。この演算式に、eval に加えて新たな操作 (print) を実装する場合を考えると、Number と Sum の両方のクラスに print メソッドを持たせることになる。既存のクラスを再利用できてない。だめじゃん。
というのはぼくも前から言っていた不満。
そこでオープンクラス、ではなく、アスペクト指向プログラミング、でもなく、ケースクラスとパターンマッチング。

7.1. Case Classes and Case Objects

チュートリアルとかぶるけど。

abstract class Expr
case class Number(n: Int) extends Expr
case class Sum(e1: Expr, e2: Expr) extends Expr

普通のクラスとの違い。

• コンストラクタ関数が勝手に定義される。ので、new Number(1) を Number(1) と書ける。
• toString 、equals 、hashCode メソッドが勝手に適当に定義される。
• 無引数のアクセサも定義される。Number(1).n とか。
• パターンマッチにかけられる。

7.2. Pattern Matching

いきなり「match は Scala のルートクラス Any に定義されたメソッドだ」って書いてある。本当？

1 match { case 1 => 1 }   // 動く
1.match({ case 1 => 1 })  // error: identifier expected but 'match' found.

なんだけどなあ。ルートクラスは Any じゃなくて AnyRef な気がするし、昔の話とかかな。
パターンとして書けるのは以下の通り。

• ケースクラスのコンストラクタ
• パターン変数 (小文字で始まる)
• ワイルドカードパターン _
• リテラル
• 定数識別子 (大文字で始まる)

Scala はローカル変数を大文字小文字どちらから始めてもいいけど、パターン変数は小文字でないとダメ。

{ case P1 => E1 ... case Pn => En }

は引数を 1 個受け取ってパターンマッチする匿名関数。つまり以下と同じ。

(x => x match { case P1 => E1 ... case Pn => En })

8. Generic Types and Methods

スタックのようなデータ構造を、要素の型ごとに定義するのはいやだよね、そこでジェネリクス、というよくある導入。

abstract class Stack[A] {
  def push(x: A): Stack[A] = new NonEmptyStack[A](x, this)
  def isEmpty: Boolean
  def top: A
  def pop: Stack[A]
}
class EmptyStack[A] extends Stack[A] {
  def isEmpty = true
  def top = error("EmptyStack.top")
  def pop = error("EmptyStack.pop")
}
class NonEmptyStack[A](elem: A, rest: Stack[A]) extends Stack[A] {
  def isEmpty = false
  def top = elem
  def pop = rest
}

Stack の中で NonEmptyStack を参照していて、NonEmptyStack は Stack を継承してるから、対話的環境に流しこめない。ファイルにしてコンパイルするしかない？
型をパラメータとして受け取る、型多相なメソッド。

def isPrefix[A](p: Stack[A], s: Stack[A]): Boolean = {
  p.isEmpty ||
  p.top == s.top && isPrefix[A](p.pop, s.pop)
}

面白いところなのに、コンパイル時間が遅すぎるせいでみるみるやる気を失っていく！
多相の英単語の polymorphic は、ギリシャ語由来で having many forms という意味らしい。知らんかった。
型多相のメソッドを呼ぶ場合は型も引数として渡す。

val s1 = new EmptyStack[String].push("abc")
val s2 = new EmptyStack[String].push("abx").push(s1.top)
println(isPrefix[String](s1, s2))

ただし、型推論できる場合は型の引数を省略できる。

println(isPrefix(s1, s2))

試しに new EmptyStack とだけしてみたら、EmptyStack[Nothing] 型になった。
object EmptyStack[A] extends Stack[A] は syntax error 。型パラメータとはいえ引数を取るからかな。

8.1. Type Parameter Bounds

集合を現すクラスを考える。要素の型は限定したくないのでパラメータ化する。

abstract class Set[A] {
  def incl(x: A): Set[A]
  def contains(x: A): Boolean
}

で、これの実装を二分探索木で与えようと思ったら、A のインスタンスと A のインスタンスの大小が比較できなくて困る。
そういうときは、型パラメータに upper bound を設定する。

trait Ordered[A] {
  // 正なら this が大きい、負なら that が大きい、0 なら等しい
  def cmp(that: A): Int
}
class Set[A <: Ordered[A]] {
  def incl(x: A): Set[A]
  def contains(x: A): Boolean
}
class EmptySet[A <: Ordered[A]] extends Set[A] {
  def incl(x: A) = null  // 実装省略
  def contains(x: A) = false
}

A <: Ordered[A] とすることで、A は Ordered[A] のサブクラスに制限される。
で、要素のクラスは Ordered[自分] を継承しておく。

case class Num(value: Double) extends Ordered[Num] {
  def cmp(that: Num): Int =
    if (this.value < that.value) -1
    else if (this.value > that.value) 1
    else 0
}

すると EmptySet の要素にできる。

val s = new EmptySet[Num].incl(Num(1.0)).incl(Num(2.0))

// 以下は java.io.File は Ordered[java.io.File] のサブクラスじゃないからダメ
val s = new EmptySet[java.io.File]

とはいえ、要素とする型が必ず Ordered[自分] を継承してないといけないのは不便ですね。そういうときは、A <: Ordered[A] の代わりに A <% Ordered[A] を使うといいらしい。この場合、「A が Ordered[A] のサブクラス」という制限から、「A から Ordered[A] への暗黙的な変換 (implicit conversion) が定義されている」という制限に緩和されるそうな。implicit conversion は後で出てくるとのこと。

8.2. Variance Annotations

co-variant と contra-variant の話。
Stack[String] は Stack[AnyRef] のサブタイプとみなしてよいか。Stack がこの章 (8 章) の最初で書いたような実装 (mutable cell など持たない pure functional な実装) になってるなら問題ない。つまり Stack は co-variant 。
でも Scala はデフォルトで non-variant を採用する。つまり、Stack[String] と Stack[AnyRef] はサブクラスでもスーパークラスでもない。以下のような代入があるとコンパイル時に例外になる。実際には問題ないにもかかわらず。

val string_stack = new EmptySet[String]
val anyref_stack : Stack[AnyRef] = string_stack  // 型エラー

これを通るようにするには、Stack の型パラメータに + をつける。これで Stack が co-variant となる。

class Stack[+A] {
  def push(x: A): Stack[A] =
  ...
}

って、co-variant にしたらまずい場合は自己責任ですか？と一瞬頭をよぎったけど、ちゃんと型チェックしてくれた。というか、contra-variant の位置に A が出てしまっている (push(x: A) のところ) ので、これだけだと型エラーになってしまう。これを何とかするには次節の lower bound を使うとのこと。

ちなみに、contra-variant にしたい場合は - をつける。あと、Array が co-variant になっているという、Java 仕様策定の有名な痛恨ミスが紹介されていた (某先生が「型理論も勉強していない者が言語設計をするからこういうミスが起きる」と言ってた) 。

8.3. Lower Bounds

すっかり型理論を忘れているので、かなりあやふやですが。
とりあえず、さっきの問題は以下のようにすれば通るらしい。

class Stack[+A] {
  def push[B >: A](x: B): Stack[B] =
  ...
}

B >: A は、「B は A のスーパータイプ」という制限。
なぜこれで型推論が通るか。contra-variant の位置である push の引数の型が B になった。変わりに lower bound の指示のところ (B >: A) にでてきたけど、ここは co-variant の位置らしい。よって、contra-variant の位置に A が現れないので OK 。
どう理解すべきか。Stack[String] に AnyRef のインスタンスを push すると考えると、A = String 、B = AnyRef になって、変える値は Stack[String] でなく Stack[AnyRef] 、つまり Stack[B] 。実際にあってるでしょ。
狐につままれた気分ですが、まあ。どこが co-variant の位置でどこが contra-variant の位置かは、ちゃんと考えればわかるんだろう。たぶん。

ちなみに、T >: S <: U で「T は S のスーパータイプ、かつ U のサブタイプ」ということも書けるらしい。

8.4. Least Types

多相型のスタックで object EmptyStack を作る話。えーと、Haskell でいうと ［］ : [a] 、ocaml でいうと ［］ :: 'a list ですよね。
co-variant なスタックなら以下のイディオムで定義できる。

object EmptyStack extends Stack[Nothing] { ... }

お、Nothing だ。
Nothing はボトム型で、Nothing 型になる値は存在しない。つまり Stack[Nothing] は要素になりえる値が存在しないので、必然的に EmptyStack となる。
Nothing 型は任意の型のサブタイプ。なので、Stack が co-variant として定義されていることから、任意の T に対して Stack[Nothing] は Stack[T] のサブタイプ。
co-variant のスタックは小さい型から大きい型へ広げていけた (Stack[String] から String[AnyRef]) ので、同様に、任意の型 T に対して Stack[Nothing] から Stack[T] へ広げられる。
以上より、

val s = EmptyStack.push("abc").push(new AnyRef())

と書ける。EmptyStack だけなら Stack[Nothing] 型、String を push すると Stack[String] 型、AnyRef を push すると Stack[AnyRef] 型。
んー。TAPL にこんな話あった気がするね。
今までのコードをまとめるとこうなる。

abstract class Stack[+A] {
  def push[B >: A](x: B): Stack[B] = new NonEmptyStack(x, this)
  def isEmpty: Boolean
  def top: A
  def pop: Stack[A]
}
object EmptyStack extends Stack[Nothing] {
  def isEmpty = true
  def top = error("EmptyStack.top")
  def pop = error("EmptyStack.pop")
}
class NonEmptyStack[+A](elem: A, rest: Stack[A]) extends Stack[A] {
  def isEmpty = false
  def top = elem
  def pop = rest
}

んー、おもしろいけど使いこなせるかわからん。とはいえ、データ構造なんて滅多に自分で定義しないので、そもそも使うことがあまりないかも。
さて、Scala ライブラリの多くのクラスはジェネリックに書かれている。以下、その代表の tuple クラスと関数クラスを取り上げる。

8.5. Tuples

定義。

case class Tuple2[A, B](_1: A, _2: B)

作り方。

val p = new Tuple2[Int, Int](1, 2)
val p = Tuple2(1, 2)
val p = (1, 2)  // syntax sugar

参照の仕方。

println(p._1)
p match { case Tuple2(a, b) => println(a) }
p match { case (a, b) => println(a) }  // syntax sugar

Tuple がない言語では生きていけません。

8.6. Functions

String => Int な関数は、Function1[String, Int] のインスタンス。Function1 は以下のように定義されている。

trait Function1[-A, +B] {
  def apply(x: A): B
}

原理主義的ですね。一応確かめてみた。

((x:Int) => x * x).apply(10)  // 100

f(x) は f.apply(x) の略記。
ちなみに (T1, ..., Tn) => S は Functionn[T1, ..., Tn, S] の略記。複数の引数は tuple 扱いなわけじゃないんですね。
あとは関数の引数が contra-variant になることの説明があった。

まとめ

匿名関数、クラス、パターンマッチ、ジェネリクスについて。ジェネリクスが重かった。
syntax sugar の裏に隠れた原理主義的な思想が見えてきて、かなり面白いですね。それでいて実行速度もそれなりに速いらしいんだから、がんばってますよね。
まあ、Java ベースでなければもっといい言語になった気がする。

大体これで Scala By Example の半分くらい。あとはリスト、Mutable State 、無限リスト、lazy value 、implicit parameter and convension 、 Hindley/Milner 型推論、並列。どんどん重くなっていく。
しかし可変長引数とかキーワード引数とかは無いのかな。我ながら世俗的な興味だけど。