2008年11月6日木曜日

Scalaでの可変オブジェクトの扱い

今までは、関数は副作用を持たないものとして扱ってきた。なので、時間の概念を気にする必要もなかった。一連の処理は、どのような順番で評価しても最終的に同じ結果が得られる。これを合流性(confluence property)とかチャーチ・ロッサー性と呼び、関数型プログラミングの理論的基盤となるラムダ計算の重要な帰結らしい。知らなかった。

ざっとWebを流し読みしたところ、ラムダ計算の体系では、ラムダ式をベータ簡約することが計算そのものとなるようだ。ベータ簡約は関数適用による正規化のこと。で、チャーチ・ロッサー性とか合流性とかは、ベータ簡約の順序がどうであっても最終的に同じ正規化されたラムダ式が得られる、ということを言っているようだ。これはつまり、どのラムダ式から評価・計算しても同じ計算結果が得られるということになる。…簡約、つまり計算が停止さえすれば。
つーか、これを調べてる間にラムダ計算の迷宮に迷い込んでしまった…大学で情報の基礎教育を受けていない身にはつらい…けど、勉強になる。
さて、これは不変の世界・参照透過性が保証された世界の話で、ここでの本題はScalaでの可変の世界の扱い方。ここでは、オブジェクトがhistoryによってその振る舞いを変える場合、オブジェクトは状態を持つという。このあたりは、純粋関数型とかそういうのはもう捨ててしまって、完全にオブジェクト指向の世界に入っている。いわば、Javaな人にとってはおなじみの世界。Javaとの違いといえば、変数は定義と同時に初期化しなければならない点くらいだろうか。なので途中の例は思い切って省略!つまんないし。

同値性と変更
「代入」の導入により、二つの式が同じかどうか判別するには、より正確な「同値性」の定義が必要になってくる。具体的には、可変の世界では以下のようにして同一性をテストするらしい。
  1. 式xと式yを含む任意の一連の処理Sを実行し、結果を観測する。
  2. Sの処理のうち、yをxにすべて置き換えた処理S’を実行し、結果を観測する。
  3. もしS’の実行結果がSの実行結果と異なっている場合、xとyは同じでない。
  4. SとS’の実行結果がすべて同じであれば、xとyは同じ。
これは、インスタンス自体が同じかどうかみたいな話をしているようだ。Javaのequalsに慣れた身としてはなんとももどかしい定義だ。理屈としてはこれで良いとして、実際上はどうするんだろう?

代入と置き換えモデルの崩壊
今までは、値の名前を常にその値を定義する式に置き換えることができた。例えば、
val x = new BankAccount; val y = x
のval y = xは、val y = new BankAccountと置き換えることができた。しかし、可変の世界ではこのモデルはもはや機能しない。このように書き換えてしまうと、違う意味になってしまう。

手続き的制御フロー
おなじみのwhile/do-whileがあります。なーんだ、あるじゃん!と手続きに馴染み深い自分は一安心してしまった。変数に値を代入できるから使える制御フローではあるよね、確かに。while (j <>
だけど結局、whileループも以下のような再帰の関数で置き換えることができる。
def whileLoop(condition: => Boolean)(command: => Unit) {
if (condition) {
command; whileLoop(condition)(command)
} else ()
}
こうすれば、可変オブジェクトは不要になる。なるほど。ちなみに、whileLoopは末尾再帰なので、実際はループとしてコンパイルされる。ということで、一定のスタック領域しか消費しない。
後は、回路をシミュレートするサンプルが延々続いてるけどこれは省略。おなじみだし。

まとめ
状態(代入)を導入すると、プログラムは複雑になる。とりわけ、参照透過性が失われる。が、状態はこれはこれでエレガントなプログラムを作るのに役立ったりもする。どちらを選ぶかは状況によりけり。

2008年11月4日火曜日

ScalaのForループ

MapやFilterを使った高階操作はわかりづらい場合もあるので、Scalaでは従来の手続き型スタイルのForループに近い記法も用意されている。その記法では、
persons filter (p => p.age > 20) map (p => p.name)
for (p <-persons if age > 20) yield p.name
という風に書くことができる。形式的には、
for ( s ) yield e
このようなになり、sはGenerators, Definitions, Filtersの並びで構成されるらしい。
Generatorsとは、 val x <- e で、eがList値の式であるようなもの。Definitionsは通常の定義と同じで、以後の式で使うことができる。FiltersはBoolean型の式。普通は関数になるハズ。
sはGeneratorsではじまる必要があり、Generatorが複数記述された場合はネストされたような動きになる。つまり、先行するGeneratorが1度評価されるたびに、後続のGeneratorはすべて評価される。
for ( s )の記法ではGeneratorsとDefinitions,Filtersの間はセミコロンで区切らないといけないが、()の代わりに{}を使う記法、つまり for { s }の記法を使った場合、セミコロンは省略することができる。

The N-Queen Problem
レイトン教授でもよく出題されていた、N-Queen問題を例として、For-Comprehensionの使い方を見ていく。N-Queen問題は、N行・N列のチェス盤にQueenを置くゲームで、Queenは互いにチェック状態にならないようにする、というもの。Queenは同じ行・列・斜めの直線状のコマをチェックできるので、お互いが同じ行・列・斜め線に並ばないように配置しなければならない。
これを解く方法としては、新たに置いたQueenが今まで置いたQueenにチェックされないかを確認しながら、1列ずつQueenを置いていく、というものが考えられる。このコードは、以下のように書ける。
def queens(n: Int): List[List[Int]] = {
  def placeQueens(k: Int): List[List[Int]] =
    if (k == 0) List(List())
    else for { queens <- placeQueens(k - 1)
      column <- List.range(1, n + 1)
       if isSafe(column, queens, 1) } yield column :: queens
    placeQueens(n)
}
def queens(n: Int) : List[List[Int]]は、N-Queen問題の「n」、つまりQueenを置く盤のサイズを受け取り、すべての解をListで返すというもの。
内部のList[Int]はそれ自体が1つの解を表すようになっており、1~nのそれぞれの行(列)でのQueenの位置(列または行)を表す。
実際にこの問題を解いているのはdef placeQueens(k: Int): List[List[Int]]の部分で、再帰になっている。queensはこの内部メソッドを呼んでいるだけだ。

では、placeQueensを見ていく。
「k == 0」の場合は、空ListのListを返している。List(List())の部分。「k >= 1」の場合にFor-Complehensionが出てきている。

「k >= 1」の場合、まずk-1の解のセットをすべて取得(これはplaceQueens(k - 1)で取得)し、ここから解を1つ取り出す。この1つの解ごとにList.range(1, n + 1)でIntのList(1~n、これは盤の列の数、すなわちk番目のQueenの置き場所の候補)を生成する。
で、k-1の解と、k列でのQueenの配置をisSafeに渡して、Safeだったらこの2つを結合してk列までの解として返す。これを解とk列の置き場所の組み合わせの数だけ実行すれば、すべての解が得られることになる。

k-1の解とkの解の総当りを試すところは、二重ループになっている。ScalaのForの表記的は多重ループがわかりづらいので、最初見た時には混乱してしまった。

Querying with For-Comprehensions
For記法は、データベースクエリ言語の基本的な部分と本質的には同じらしい。例えば、書籍データベースを以下のようにBookクラスのListとして表現したとする。
case class Book(title: String, authors: List[String])

val books: List[Book] = List(
Book("Structure and Interpretation of Computer Programs",
List("Abelson, Harold", "Sussman, Gerald J.")),
Book("Principles of Compiler Design",
List("Aho, Alfred", "Ullman, Jeffrey")),
Book("Programming in Modula2",
List("Wirth, Niklaus")),
Book("Introduction to Functional Programming"),
List("Bird, Richard")),
Book("The Java Language Specification",
List("Gosling, James", "Joy, Bill", "Steele, Guy", "Bracha, Gilad")))
このデータベースに対して、authorが"Ullman"から始まるBookのtitleを取り出すには、こう書ける。
for (b <- books; a <- b.authors if a startsWith "Ullman") yield b.title
titleに"Program"が含まれるものについては、こう。
for (b <- books if (b.title indexOf "Program") >= 0) yield b.title
少なくとも2冊の本を書いている著者の名前を取り出す場合には、こう書ける。
for (b1 <- books; b2 <- books if b1 != b2; a1 <- b1.authors; a2 <- b2.authors if a1 == a2) yield a1
これは完全ではなく、著者が二重にカウントされてしまう。重複した著者を取り除く関数は、以下のように書ける。
def removeDuplicates[A](xs: List[A]): List[A] =
if (xs.isEmpty) xs
else xs.head :: removeDuplicates(xs.tail filter (x => x != xs.head))
これをFor-Comprehensionで書くと、こうなる。
xs.head :: removeDuplicates(for (x <- xs.tail if x != xs.head) yield x)

For-Comprehensionの変換
For-Comprehensionは、結局はmap/flatMap/filterの組み合わせに変換できる。
for (x <- e) yield e’
このようなFor-Comprehensionは、
e.map(x => e’)
こう変換できる。
for (x <- e if f; s) yield e’
これは、
for (x <- e.filter(x => f); s) yield e’
こう。fはフィルタ(Boolean式)で、sはGeneratorとFilterらしい。が、ForでDefinition使った例見たことないし、if f の後のGeneratorってどうなるのかもよくわからないぞ。
for (x <- e; y <- e’; s) yield e’’
これは、
e.flatMap(x => for (y <- e’; s) yield e’’)
こうなる。

もう少し具体的な例をあげると、
for { i <- range(1, n) j <- range(1, i) if isPrime(i+j)} yield {i, j}
これが…
range(1, n)
.flatMap(i =>
range(1, i)
.filter(j => isPrime(i+j))
.map(j => (i, j)))
こうなる。まぁ、そうだよね。

For-Loop
For-ComrehensionではListを構築して返す形になるが、繰り返し処理では必ずしもListを構築したいとは限らない。こういう場合にはFor-Loopが使える。
for (xs <- xss) for (x <- xs) print(x + "\t") println() } 
Bloggerでなぜかインデントできなかったけど、インデントすればおなじみのForループ。

Generalizing For
Forは、Listに対して以外にも使うことができる。実際のところ、以下のようなメソッドが実装されているクラスCであれば、For-ComprehensionやFor-Loopを使うことができるらしい。
  • def map[B](f: A => B): C[B]
  • def flatMap[B](f: A => C[B]): C[B]
  • def filter(p: A => Boolean): C[A]
というわけで、しょぼいながら試してみた。
class ListLike[+A](x : Seq[A]) {
val internal = x.toList

def map[B](f: A => B): ListLike[B] = {
new ListLike(internal.map[B](f).toSeq)
}
def flatMap[B](f: A => ListLike[B]): ListLike[B] = {
new ListLike(null)
}
def filter(p: A => Boolean): ListLike[A] = {
new ListLike(null)
}
}
で、呼び出し。
val list = new ListLike(List(1, 2, 3, 4))
val ret = for (i <- list) yield 1; println(ret)
結果。
List(1, 1, 1, 1)
というわけで、一応動いている模様。mapしか使われていないけど、他はちゃんと実装するのが面倒くさかったので飛ばしてしまう。
さらに、For-Loopを試してみたが、実際にやってみると、以下のようなコンパイルエラーが出る。
value foreach is not a member of sample.for_example.ListLike[Nothing]
どうやら、For-Loopではforeachというメンバが必要らしい。foreachを定義してみたところ、コンパイルエラーは消えた。
def foreach(f: A => Unit) {
internal.map(f)
}
実行してみる。
for (i <- list) { println("aaa") } 
結果。
aaa
aaa
aaa
aaa
というわけで、あまりにもしょぼいけど一応動くことは確認。foreachは内部のブロックを引数として取る形になってるらしい。デバッグしてみたらFuction1だった。ということで、Forも終わり。なんだか長かったなぁ。