発表できなかったところの補足

オマケではありますが、聞きたかったという人がありがたい事にいて下さったので補足説明をしておきます。
結構長いので注意。
あ、あくまでスライドの補足です。

決定的有限状態オートマトン

まあwikipedia:有限オートマトンが非常に詳しいんですが。
このページ(あるいはスライド中)の数学モデルは<Σ, S, s0, δ, F>*1(スライドでは(Q, Σ, δ, q0, F))で書かれています。
これは5-Tupleで、その要素はそれぞれ、状態の集合S(Q)、入力記号の集合Σ、初期状態s0(q0)、遷移関数δ：Q×Σ→Q、受理状態の集合F(⊆Q)です。
このように数学的に定義する場合、先の要素で定義された物は後で使えるようにするというルールが何となくありそうです。ただの直感ですが。

さて、決定性(決定的)というのは、どの状態にどの様な入力があったとしても、その遷移先が一意に決定できる事をいいます。
たとえば、資料P.60の1が3n+1の倍数のテープを受理する有限状態オートマトンでは、どの状態に居たとしても、全ての入力(0か1か)に対して次にどの様な状態に遷移するのかが示されています。
なお、この数学モデルにおける遷移関数δ：Q×Σ→Qは、「状態集合と入力記号集合の直積の要素」を「状態集合の要素」に変換する関数です。これを意味を踏まえた上で言い換えると、「現在の状態とテープからの入力１つのペア」を「次の状態」に移していることになります。

scalaによる決定的有限状態オートマトンの表現

全文。

package dfa;

object Main {
	def main(args: Array[String]) = {
	  val dfa = DFA.sample()
	  dfa.accept(Tape(0, 0, 0, 1, 0, 1, 0))
	  dfa.accept(Tape(1, 1, 1, 0, 1, 0, 0))
	}
}

case class Tape[I](values: I*)

case class DFA[S, I](
	states: Set[S],
	inputs: Set[I],
	funcs: Map[(S, I), S], 
	q0: S, 
	accepts: Set[S]
) {
	def accept(input: Tape[I]): Boolean = {
		lastState(input.values) match {
			case Some(state) => accepts.contains(state)
			case _ => false
		}
	}

	def lastState(input: Seq[I]): Option[S] = {
		input.foldLeft(Option(q0)) {
		  (currentStateOption, in) => for { 
			  state <- currentStateOption
			  nextState <- funcs.get(Tuple2(state, in))
		  } yield { nextState }
		}
	}
}

object DFA {
	def sample() = {
		val Sigma = Set(0, 1)
		val Q = Set("a", "b", "c")
		val F = Set("b")
		val delta= Map(
			("a", 0) -> "a", ("a", 1) -> "b",
			("b", 0) -> "b", ("b", 1) -> "c",
			("c", 0) -> "c", ("c", 1) -> "a"
		)
		val q0 = "a"
		DFA(Q, Sigma, delta, q0, F)
	}
}

こうやって見てみると、次の点が便利な点として上げられます。

Set, Mapがある

まあ、Javaなどでもありますので特筆すべき点は無いです。

n-Tupleがそのまま使える

case class DFAのfuncsの定義を見ると、Map[(S, I), S]と成っています。[]内はGenericsによる型指定を表してます*2。
ここで(S, I)の様に、タプルを自然に扱う事ができ*3、またそれを使用するための便利な構文も準備されています。

パターンマッチ

簡単にいってしまえば強力なif-else／switch構文です。
acceptメソッドにあるmatch前後がScalaのパターンマッチになります。
この例では、「lastStateの結果がSome型である時、その要素をstateに代入し=>の右側で使用します。具体的にはそのstateはaccepts.contains(state)という形で使用し、その評価を戻り値とします。それ以外(_)の時はfalseを戻します」といった事を行っています。
なお、scalaのメソッド・関数・式の戻り値は明示的にreturnを書く事も出来ますが、関数内で最終的に評価された値を返します。

Option

別の言語ではMaybeとも。
要は「でーたがある・無いのどちらかを示す」事を表した型です。
Some(x)はxという要素がある事を示します。
Noneは何も要素が無い事を示します。
「何も無ければnullを返し、そのnullをチェックする」ことを防いでくれますし、
明示的に型にすることによって、「この関数は結果を得られる場合と得られない場合がある」事を明示できます。
例えば、def: toInt(s: String): Option[Int]のような関数は分かりやすいですね*4。
sがparseできればSome(sの整数表現)が、parseできなければNoneがそれぞれ戻ってきます。

foldLeft

あるデータAsと何かのデータB0を与えたとき、B0とAs[0]を使って処理を行い、B0と同じ型である結果B1を返します。As[1]はこのB1を使って同様の処理を行いB2を返します……といった処理を行うのがfoldです。
Leftはデータ列(As)の最初から、Rightではデータ列の最後から処理を行います。
lastStateメソッドの中で、input.foldLeftという形で使用しています。
この例では初期にOption(q0)という要素を渡し、input、すなわち入力テープの最初(Left)から順に読み込んで、個別の処理を行っています。
早い話がループとほぼ同様の処理を行っています。

カリー化

f: A1×A2×...×An→B という関数を f: A1→(g: A2→...(n: An→B)...)の様に１引数関数のみで扱えるように変換する事です。
例えば要素が２個の場合、関数f: A×B→C (使う時はf(a, b) )を等価な関数f': A→(g': B→C))の様に変換できます。
この時、f'(a)の結果は関数g'です。このg'の対応をとる事も出来るので、(f'(a))(b)の様に呼び出す事ができます。
(f'(a)) = g'を考えると単純に置き換えできる事が分かると思います。
このような時、f(a, b)として呼び出していた物を、f'(a)(b)として呼び出すことができる様になります。
何故このような事をするのかは関数の部分適用が容易という点が１点挙げられますが、今回は紹介なのでこれ以上は立ち入らない事にします。
foldLeft(B)(f: B×A→B)はカリー化されたメソッドです。
要は２つの引数を渡しているだけです。

無名関数

foldLeftの第二引数には２つの要素を受け取ってどの様な処理を行うかという関数を渡します。
……しかし、何故か{}で囲まれており、構文を構成しているように見えます。
{}内はカリー化された要素の第２引数です。
(厳密では無いと思いますが)Scalaのメソッド・関数では、要素が１つである最後のカリー化部分は()だけではなく{}で書く事も許容されています。そのため、あたかも自分が構文を作るようにプログラムをする事が可能です。C#のusing(IDisposable){}構文も再現できます。
scalaでは 「引数 => 内容」という記述で無名関数を定義できます。
無名関数はC#で言えばdelegate*5、Javascriptで言えばfunction() {}を直に書く、ただそれだけの物です。
ここでは、タプル(foldLeftの第一引数の型要素, foldLeftメソッドを持つコレクション(=input)の要素の型)を引数に貰い、このタプルの第一要素を返す無名関数を記入しています。
具体的には、f: (Option[S], I) => Option[S] という関数を書いています。

Maybeモナド

さて、Scalaではfor*6は文ではありません。式です。
言語仕様書によれば、forは中に書かれた要素を決まった形に変換します。
forの中でどの様な処理をしているかは、次の通りです。

• まず、currentStateOptionがSomeかNoneかを見る。Someの場合stateにSomeの中味の要素を代入する。そうで無い場合はこれ以下の処理を行わずに、結果としてNoneを返す。
• 前の処理で「この処理が呼ばれる事はstateにデータがある」事が保証されているので、それを使って状態遷移関数を呼び出す。Map.getは「対応するkeyがmap中にあるならば、Some(value)を、対応するkeyが無いならばNoneを返すメソッド」である。ここでも同様にSome(value)が得られば、valueの値をnextStateに設定する。そうで無い場合はこれ以下の処理を行わずに、結果としてNoneを返す。
• yieldを付けると、その後のブロックの処理結果を戻り値として得る事ができる*7。ここでは、nextStateを返すが、for式の魔術*8により、結果はSome(nextState)を返す。

結果として、このfor式はSome(nextState)かNoneを返します。そして、その結果を基にinputに対して順次処理を行っています。
これはすなわち、状態遷移を行っています。
最初は初期状態q0にテープの第一入力i0が与えられるので、この(q0, i0)を状態遷移関数に適用してq1を得ます。そして次は第二入力i1とq1を元にしてさらに状態を遷移させて行きます。
最終的に得られたのが入力テープに対する終端状態です。
なお、Noneが得られる場合は状態遷移関数に不備がある場合、入力に不備がある場合などが考えられます。

従来の手続き型処理では、１つずつif (state == null) { return; }のようなコードを書いて、あるかどうかが分からないデータの処理をしてやる必要がありました。
これは即座にリターンする方式ですが、パターンマッチを使う場合などは処理がネストし、深く読みづらいソースコードになることも多くあります。
しかしながら、Maybeモナドという仕組みがあると、「この全てが成功する（途中の式にはそれ以前の式で得られた結果を使っても良い）場合、結果としてSome(value)を返す。いずれか１つだけでも失敗する場合はNoneを返す。」といった事が簡潔に記述できる様になるのです。
より興味がある人は以下も合わせてどうぞ。
# というか、今回の説明は大雑把な所しか言ってないので、こっちを読んだ方が正しく理解できるのではないかと。

• 第14回 関数脳のつくり方　Second Season　〜モナドで悟りをひらく〜
• 第14回 関数脳のつくり方　Second Season　〜モナドで悟りをひらく〜 - 刺激を求める技術者に捧げるScala講座：ITpro　へのツッコミ

まとめ

軽く流そうと思ってた部分だったけど、やっぱり書くと大変だなー……。
あ、間違いとか分かりづらい所とかのご指摘は歓迎です。

*1:組の事を<>で表す場合もある。

*2:ここでS=State, I=Input

*3:Tuple2(x, y)の様に明示的に書く事もできます。

*4:このメソッドが標準であるわけではありません。

*5:あまり詳しくないのでここ間違えていたらごめんなさい

*6:ここでは要素が2個以上あるのに{}で囲んでいるが、forは関数ではないので、先に挙げたルールは適用されない。

*7:yieldを付けない場合はfor式の結果はUnitとなる

*8:これを説明しようとすると、それだけで一本記事が必要になりそうなので省略