合成できるモナド、モナドが合成できる時
(今回のコードは github:everpeace/composing-monads にあります。)
一般に、モナドって合成できないって言われますよね。
でも、モナドって合成できる場合も有るんです。
今回はまず、合成が難しい(できない)理由を説明して、
じゃぁ「モナドが合成できる時」はいつなのか？
というのと「合成できるモナドたち」をちょっとだけ紹介してみます。
それにはまず、ここから始めましょう。
モナドをflatMapじゃなくてflattenで定義してみる。
flatMapで定義されるモナドのおさらい
Mというモナドは次の用に定義されます。
trait Functor[F[_]]{ def map[A,B](fa:F[A])(f:(A) => B):F[B] } trait Monad[M[_]] extends Functor[M]{ def unit[A](a:A):M[A] def flatMap[A,B](ma: M[A])(f:A => M[B]):M[B] }
有名なリストモナド（たくさんの値を返す計算の抽象です)はこんな風に定義されます。
implicit val ListMonad = new Monad[List]{ def map[A,B](as:List[A])(f:(A)=>B) = as.map(f) def unit[A](a:A):List[A] = List(a) def flatMap[A,B](as:List[A])(f:A => List[B]) = (List[B]()/:as)(_++f(_)) }
リストモナドのflatMapが何をやってるかおさらいしましょう。
def repeat2(a:Int):List[Int] = List(a,a) ListMonad.flatMap(List(1,2,3))(repeat2) //=== List(1,1,2,2,3,3)
分解して説明すると、List(1,2,3)の各要素にrepeat2を施すとこんな感じ。
1 => List(1,1) 2 => List(2,2) 3 => List(3,3)
これを、List[List[Int]]じゃなくて、それをflatにしたList[Int]にして返すのがflatMapです。名前の通りなのですが、ただmapするだけだと、List[List[_]]になるので、それをflatする。
モナドのパワーがここにあるのは様々なブログに書かれている通りです。
flatMapじゃなくてflattenでMonadを定義してみる。
mapは与えられるのだから、モナドのパワーの根源はflatする部分にあると感じませんか？圏論の小難しい事は抜きにしますが、圏論におけるモナドは元々, unit, flattenの２つで定義されているのです！
コードで書くとこんな具合です。
trait Monad[M[_]] extends Functor[M]{ def unit[A](a:A):M[A] def flatten[A](mm:M[M[A]]):M[A] }
上と同じ様にListモナドをflattenで定義してみましょう。
implicit val ListMonad = new Monad[List]{ def map[A, B](as: List[A])(f: (A) => B) = as.map(f) def unit[A](a: A) = List(a) def flatten[A](ass: List[List[A]]) = (List[A]()/:ass)(_++_) }
こうですね。
さて、ちょっと抽象の世界に戻って考えてみましょう。flattenは２重になったモナドを１重にしてくれますよね。flatMapに渡されるfをmapに渡すとM[M[A]]になるので、実は、flatMapはこのflattenを使って抽象レベルで定義できるんです。
trait Monad[M] extends Functor[M]{ def unit[A](a:A):M[A] def flatten[A](mma:M[M[A]]):M[A] def flatMap[A,B](f:A=>M[B])(ma:M[A]) = flatten(fmap(f,ma)) }
さっきのList Monadの例に戻ってみましょう。
implicit val ListMonad = new Monad[List]{ def map[A, B](as: List[A])(f: (A) => B) = as.map(f) def unit[A](a:A):List[A] = List(a) def flatten[A](ass:List[List[A]]):List[A] = (List[A]() /: ass)(_++_) def flatMap[A,B](f:A=>List[B])(ma:List[A]):List[A] = flatten(fmap(f,ma)) }
このflatmapを分解して実行してみると、
ListMonad.flatMap(List(1,2,3)(repeat2)) = flatten(map(List(1,2,3))(repeat2)) = flatten(List(List(1,1),List(2,2),List(3,3)) = List(1,1,2,2,3,3)
flattenを使って、flatMapが元のと同じように動作しているのが分かりますね。(fの実行タイミングが違うのは置いておいて)
モナドの合成の難しさ
さて、flattenを通してモナドを理解してみると、モナド合成の難しさが見えやすくなります。
二つのモナドM,Nを考えましょう。モナドを合成するということは、M,Nという二つのモナドからMN[A]というモナドを作り出す事です。つまり、Monad[M], Monad[N]のインスタンスが与えられたとき、Monad[({type MN[α] = M[N[α]]})#MN]を与えよという事になります。
new Monad[({type MN[α] = M[N[α]]})#MN]{ def map[A,B](ma:M[N[A]])(f: (A) => B) = /* これを実装する */ def unit[A](a: A) = /* これを実装する */ def flatten[A](mnmn:M[N[M[N[A]]]])= /* これを実装する */ }
簡単のために、M,Nで定義されている関数をこんな風に最後にM,Nをつけて区別することにします。
mapM, unitM, flattenM mapN, unitN, flattenN
ここから、作り出したいのは
mapMN[A,B](mna: M[N[A])(f: A=>B): M[N[B]] unitMN[A](a:A): M[N[A]] flattenMN[A](mna: M[N[M[N[A]]]]):M[N[A]]
です。
unitMNは簡単そうですよね。
unitMN[A](a:A):M[N[A]] = unitM(unitN(_))
でオッケーそうです。
mapMNもなんとか行けそうですね。
// Mの中をmapN(f)するイメージ
mapMN[A,B](mna:M[N[A])(f: A=>B) = mapM(ma)(mapN(_)(f))
では、最後にflattenMNを考えてみましょう。
flatten[A](mnmn: M[N[M[N[_]]]]):M[N[A]]
を与えるにはどうすればいいでしょう？
今与えられている、mapM, unitM, flattenM, mapN, unitN, flattenN, mapMN, unitMNを組み合わせるだけでは、型からしてそのような型の関数を与える事はできないのです。
ここが、一般に二つのモナドが合成が無理と言われる所なのです。(flatMapを合成するよりflattenから見た方が簡単ですよね？？)
モナドが合成できる時 (スワップできるモナドたち)
目指すは、flattenMNです。この関数の型に注目してみましょう。
M[N[M[N[A]]]] => M[N[A]]
です。flattenM,flattenNだけではにっちもさっちもいかなかったんですが、この引数の型の真ん中のNMをMNにひっくり返すようなことができたらどでしょう？
M[N[M[N[A]]]] ==(真ん中のNMを反転)==> M[M[N[N[A]]]] ==(flattenN)==> M[M[N[A]]] ==(flattenM)==> M[N[A]]
とできるではないですか！
そんなにうまく行くはずがない。と思うでしょう。それができるんです。
swapというNMをMNにひっくり返すような関数が与えられているとしましょう。
swap[A](nma:N[M[A]):M[N[A]]
ですね。
このswapをmapMに渡すと何が起こるでしょうか？
//mapM(mnmn)(swap(_))の型は？ swap: N[M[_]] => M[N[_]] mapM: (M[X])(X=>Y) => M[Y] //X=N[M[N[A]]], Y = M[N[N[A]]なのでM[Y] = M[M[N[N[A]]]] mapM(mnmn)(swap(_)): M[M[N[N[A]]]]
です！なんと、MNMNの真ん中だけが見事にひっくり返ってMMNNになっています！
こうなれば、最初の戦略にあったように、flattenN, flattenMを順番にかければ、flattenMNの完成です！！！(実際は、ただ順番にかけるのではなく、mapに渡してやる必要はありますが)
flattenMN(mnmn:M[N[M[N[A]]]]):M[N[A]] = mapM(flattenM(mapM(mnmn)(swap(_))))(flattenN(_))
です。
つまり、もし、モナドM,Nについて、
swap: N[M[_]] => M[N[_]]
というモナドをひっくり返すswapper(圏論ではこれはdistributive lawと呼ばれます)が与えられているときには合成できる。(モナドがMonad Lawを満たさなくてはならないように、本当はswapが満たすべきLawがいくつも有ります。)
ということなんです。
合成できるモナド
swapが満たすべき条件については今回は触れませんが、合成できるモナドについて書いてみます。
任意のMonad MとOption
任意のモナド MとOptionについて M[Option[_] ]というのは合成できます。こんな風にswapを与える事ができます。
def swap[A](oma: Option[M[A]]) = oma match{ case Some(ma) => monadM.map(ma)(Option(_)) case None => monadM.unit(None) }
任意のMonad MとList
任意のモナド MとListについて M[List[_] ]というのは合成できます。こんな風にswapを与える事ができます。
def swap[A](nm: List[M[A]]):M[List[A]] = nm match { case List() => monadM.unit(List()) case x::xs => for { y <- x; ys <- swap(xs)} yield y::ys }
任意のMonad MとValidation
こんなValidationモナド
trait Validation[A] case class Ok[A](a: A) extends Validation[A] case class Error[A](msg: String) extends Validation[A] object Validation { def ok[A](a:A):Validation[A] = Ok(a) def error[A](msg:String):Validation[A]=Error[A](msg) implicit val ValidationMonad = new Monad[Validation] { def unit[A](a: A) = Ok(a) def map[A, B](ma: Validation[A])(f: (A) => B) = ma match { case Ok(a) => Ok(f(a)) case Error(msg) => Error(msg) } def flatten[A](mm: Validation[Validation[A]]) = mm match { case Ok(a) => a case Error(msg) => Error(msg) } } }
と任意のモナド Mについて M[Validation[_] ]というもは合成できます。こんな風にswapを与える事ができます。
def swap[A](nm: Validation[M[A]]) = nm match{ case Ok(a) => monadM.map(a)(Ok(_)) case Error(msg) => monadM.unit(Error(msg)) }
こんな風にできます。
こんな風(github)に定義してやると、scala のfor comprehensionを活用してこんな風にできます。
// 普通にList[Option[_]]をfor文で束縛するとOptionが束縛される。 // i はSome(1) for { i<- List(Option(1)) } yield {println(i);i} // でも、composeするとfor文で束縛されるのiは1。 for { i<- compose(List(Option(1)))} yield {println(i);i} // List[Option[_]] monad の計算が一度にできます。 // this outputs: List(Some(4), Some(5), Some(8), Some(9)) println(for { i<- compose(List(Option(1), None, Option(5))) j<- compose(List(Option(3), Option(4))) } yield i+j) // Option[List[_]]の計算も出来ます。 // this outputs: Some(List(4, 5, 8, 9)) println(for { i<- compose(Option(List(1, 5))) j<- compose(Option(List(3, 4))) } yield i+j) // List[Validation[_]]の計算もいっぺんに出来ます。 // this outputs: List(Ok(3), Error(error2), Error(error3), // Error(error1), Ok(4), Error(error2), Error(error3)) println(for { i <- compose(List(ok(1),error[Int]("error1"),Ok(2))); j <- compose(List(ok(2),error[Int]("error2"),error[Int]("error3")))} yield i+j )
合わせて読みたい。
- 檜山正幸さんのベックの法則と複合モナド(実はここに書かれているベックの法則がswapが満たさなくては行けない条件です。)
- Tony Morrisさん の Monads do not compose
- Jordan Westさん の Monad Transformers(モナドの合成というと良く出てくるモナド変換子のスライドです。途中モナド合成の難しさにも触れています)
今回のコード
今回のコードはgithub:everpeace/composing-monadsに有ります。
「プログラミングErlang」のRing Benchmark をAkkaでやってみた
「プログラミングErlang」のRing Benchmarkをやってみた
の続編です。今度は、Akkaでやってみました。
github.com/everpeace/ring-benchmark-in-akka
ErlangでプロセスといっていたのがAkkaではアクターになります。
ちょっとだけ違うのは、Erlangのプロセスは
Pid = spawn(somefunction)
ってやると、somefunctionが実行されると終わっちゃうけれど、Akkaのアクターは
class Hoge extends Actor{ def receive ={ case 'msg => println('msg) } }
とやっても終わらずにメッセージを待ち続けるところ。あるメッセージを受け取ったときに終了したいなら、こんな風に自分にPoisonPillを飲ませてやればOK.
class Hoge extends Actor{ def receive ={ case 'msg => self ! PoisonPill } }
では、普通のリングプロセスから見てみましょう
普通のリングプロセス
こんな感じです。
abstract class ProcessInRing extends Actor { import context._ def receive = wait_for_link def wait_for_link: Receive = { case ('link, next: ActorRef) => become(listen_tokens(next)) } def listen_tokens(next: ActorRef): Receive override def preStart() = println("[%s] starting..." format self) override def postStop() = println("[%s] exitting..." format self) } class Ordinal extends ProcessInRing { def listen_tokens(next: ActorRef): Receive = { case (i: Int, token) => println("[%s] token \"%s\" received, forward to %s" format(self, (i, token), next)) next forward(i, token) } }
ルートプロセスとも共通な振る舞いだけ抜き出してProcessInRingにしました。
- アクターが生成されたら、リング上のお隣さんのlinkをまつ
- リンクされたらトークンを待つ(これがルートと普通ので違う)
- ログ（生成と消滅のときにメッセージだす)
なので、Ordinalクラスのlisten_tokensは単純です。
あと、Erlangと変えたところは、ActorContextを活用して、リングの終了処理をAkkaに任せたところです。なので、listen_tokensの所に自分を終了させる部分は書かれていません。Ringプロセスとメインプロセスの節参照。
ルートプロセス
class Root(val M: Int) extends ProcessInRing { def listen_tokens(next: ActorRef): Receive = { case ('start, token) => println("[%s] token \"%s\" is injected." format(self, token)) println("[%s] token \"%s\" is forwarded to %s" format(self, (0, token),next)) next forward(0, token) case (i: Int, token) if i == (M - 1) => println("[%s] token \"%s\" received, the token reaches root %d time" format(self, (i, token), i + 1)) println("[%s] report the end of benchmark to main" format (self)) sender ! 'ended case (i: Int, token) => println("[%s] token \"%s\" received, the token reaches root %d time" format(self, (i, token), i + 1)) println("[%s] token \"%s\" is forwarded to %s" format(self, (i+1, token),next)) next forward(i + 1, token) } }
これも特に前と変わりませんね。メインから受け取ったときはリングへ流し込んで、リングの内側から受け取ったときは、もう一周流すか、メインに終了を報告するかです。
Ring プロセス
Erlangとはちょっと変えて、Ringプロセスというのを作ってみました。
AkkaではActorはcontextという名前でActorContextというのを持っています。そのコンテキスト中で生成したプロセスは自分が終了したときに、一緒に終了されます。それを今回は活用してみました。
主にRingの生成と消滅が責務です。消滅のほうはAkkaの機能(PoisonPillが来たら終了)なのでコードには反映されません。なので、Ringに送信されたメッセージはrootへ転送されるだけです。
Ringの生成手順自体はErlang版と大差ありません。
// Main --> Root --> Ordinal --> Ordinal --> ... --> Ordinal // +<----------------------------------------+ class Ring(val N: Int, val M: Int) extends Actor { require(N > 0 && M > 0) val root = init def receive = { case token => root forward token } private[this] def init: ActorRef = { val root = context.actorOf(Props(new Root(M)), name = "0") val first = create_ordinals(1, N - 1, root) root ! ('link, first) root } private[this] def create_ordinals(i: Int, num: Int, root: ActorRef): ActorRef = i match { case x if x == num => val ordinal = context.actorOf(Props[Ordinal], name = i.toString) ordinal !('link, root) ordinal case _ => val ordinal = context.actorOf(Props[Ordinal], name = i.toString) val next = create_ordinals(i + 1, num, root) ordinal !('link, next) ordinal } }
メインプロセス
クラス宣言とかmainとかは省略。
val system = ActorSystem("RingBenchmarkInAkka") val start = System.currentTimeMillis() // リングを作ります。 val ring = system.actorOf(Props(new Ring(n, m))) // askのときのタイムアウト implicit val timeout = Timeout(1000 seconds) // ベンチマークを開始して、終了を待つ (ring ? ('start, 'token)) onSuccess { case 'ended => println("[main] received the end of benchmark. killing the ring...") // graceful stop: // ringへPoisonPillを送って、ringの終了を待つ。 // ringのActorContextの中で作られたアクターたちも終了される。 val stopped: Future[Boolean] = gracefulStop(ring, timeout.duration)(system) Await.result(stopped, timeout.duration) // now system can be stopped safely. system.shutdown() val end = System.currentTimeMillis() println("[main] ring benchmark for %d processes and %d rounds = %d milliseconds" format(n, m, end - start)) }
とこんな感じです。
動かしてみる。
$ sbt
> run 4 3
[info] Compiling 2 Scala sources to /Users/everpeace/Documents/github/ring-benchmark-in-akka/target/scala-2.9.2/classes...
[info] Running org.everpeace.ringbench.RingBenchmarkInAkka 4 3
[Actor[akka://RingBenchmarkInAkka/user/$a/0]] starting...
[Actor[akka://RingBenchmarkInAkka/user/$a/1]] starting...
[Actor[akka://RingBenchmarkInAkka/user/$a/2]] starting...
[Actor[akka://RingBenchmarkInAkka/user/$a/3]] starting...
[Actor[akka://RingBenchmarkInAkka/user/$a/0]] token "'token" is injected.
[Actor[akka://RingBenchmarkInAkka/user/$a/0]] token "(0, 'token)" is forwarded to Actor[akka://RingBenchmarkInAkka/user/$a/1]
[Actor[akka://RingBenchmarkInAkka/user/$a/1]] token "(0, 'token)" received, forward to Actor[akka://RingBenchmarkInAkka/user/$a/2]
[Actor[akka://RingBenchmarkInAkka/user/$a/2]] token "(0, 'token)" received, forward to Actor[akka://RingBenchmarkInAkka/user/$a/3]
[Actor[akka://RingBenchmarkInAkka/user/$a/3]] token "(0, 'token)" received, forward to Actor[akka://RingBenchmarkInAkka/user/$a/0]
[Actor[akka://RingBenchmarkInAkka/user/$a/0]] token "(0, 'token)" received, the token reaches root 1 time
[Actor[akka://RingBenchmarkInAkka/user/$a/0]] token "(1, 'token)" is forwarded to Actor[akka://RingBenchmarkInAkka/user/$a/1]
[Actor[akka://RingBenchmarkInAkka/user/$a/1]] token "(1, 'token)" received, forward to Actor[akka://RingBenchmarkInAkka/user/$a/2]
[Actor[akka://RingBenchmarkInAkka/user/$a/2]] token "(1, 'token)" received, forward to Actor[akka://RingBenchmarkInAkka/user/$a/3]
[Actor[akka://RingBenchmarkInAkka/user/$a/3]] token "(1, 'token)" received, forward to Actor[akka://RingBenchmarkInAkka/user/$a/0]
[Actor[akka://RingBenchmarkInAkka/user/$a/0]] token "(1, 'token)" received, the token reaches root 2 time
[Actor[akka://RingBenchmarkInAkka/user/$a/0]] token "(2, 'token)" is forwarded to Actor[akka://RingBenchmarkInAkka/user/$a/1]
[Actor[akka://RingBenchmarkInAkka/user/$a/1]] token "(2, 'token)" received, forward to Actor[akka://RingBenchmarkInAkka/user/$a/2]
[Actor[akka://RingBenchmarkInAkka/user/$a/2]] token "(2, 'token)" received, forward to Actor[akka://RingBenchmarkInAkka/user/$a/3]
[Actor[akka://RingBenchmarkInAkka/user/$a/3]] token "(2, 'token)" received, forward to Actor[akka://RingBenchmarkInAkka/user/$a/0]
[Actor[akka://RingBenchmarkInAkka/user/$a/0]] token "(2, 'token)" received, the token reaches root 3 time
[Actor[akka://RingBenchmarkInAkka/user/$a/0]] report the end of benchmark to main
[main] received the end of benchmark. killing the ring...
[Actor[akka://RingBenchmarkInAkka/user/$a/0]] exitting...
[Actor[akka://RingBenchmarkInAkka/user/$a/1]] exitting...
[Actor[akka://RingBenchmarkInAkka/user/$a/2]] exitting...
[Actor[akka://RingBenchmarkInAkka/user/$a/3]] exitting...
[main] ring benchmark for 4 processes and 3 rounds = 46 milliseconds
[success] Total time: 0 s, completed 2012/05/19 12:23:56めでたしめでたし。
.ssh/configで変なHostを設定せずにGithubの複数のアカウントを使い分ける
Githubのアカウントが複数になってくると、結構厄介ですよね。
githubで複数ユーザを使い分ける
http://d.hatena.ne.jp/monjudoh/20110411/1302521587
ここにあるように.ssh/configにHostエントリを書けば出来るんですが、githubのページに表示されているclone用のレポジトリの文字列を書き換えなきゃ成らないのが億劫です。
要するに鍵の指定を出来れば良い訳なので、そこで、
git over ssh with options
http://hisashim.org/2010/02/23/git-ssh-options.html
を参考にして、GIT_SSHをいい感じに設定してくれるスクリプトを作ってみました。
gitsshm: GIT_SSH Manager for github
使い方
1.鍵を配置する。
まず使いたい鍵は ~/github-keys/にこんな感じで入れておきます。
~/github-keys/
+- user_A/
+- id_rsa
+- id_rsa.pub
+- user B/
+- id_rsa
+- id_rsa.pub
2.セットアップする。
~/github-keys直下の各usernameに対して、~/github-keys/.gitsshm/username-ssh.shという名前のスクリプトを生成してくれます。中身はこんな感じ。
exec /usr/bin/ssh -i /Users/everpeace/github-keys/username/id_rsa "$@"
sshの公開鍵認証はssh-agentを使う事でいちいち秘密鍵のパスフレーズを入力することが省略できます。各鍵をagentに登録する機能も付けてみました。
こんな感じで使います。
$ source githsshm setup GIT_SSH is not set now. WARNING: GIT_SSH may not be maintained by gitsshm. GIT_SSH will be overwritten. mkdir /Users/everpeace/github-keys/.gitsshm all keys in /Users/everpeace/github-keys will be added to ssh_agent Enter passphrase for /Users/everpeace/github-keys/user_A/id_rsa: <-パスフレース入力 Identity added: /Users/everpeace/github-keys/user_A/id_rsa (/Users/everpeace/github-keys/user_A/id_rsa) create /Users/everpeace/github-keys/.gitsshm/user_A-ssh.sh Enter passphrase for /Users/everpeace/github-keys/user_B/id_rsa: <-パスフレース入力 Identity added: /Users/everpeace/github-keys/user_B/id_rsa (/Users/everpeace/github-keys/user_B/id_rsa) create /Users/everpeace/github-keys/.gitsshm/user_B-ssh.sh Now you can switch GIT_SSH by -s action for available usernames: user_A user_B current GIT_SSH is not set.
ssh-agentに登録されている鍵はこんな感じで確認できます。
$ source gitsshm listkeys 2048 84:.....:80 /Users/everpeace/github-keys/user_A/id_rsa (RSA) 2048 84:.....:91 /Users/everpeace/github-keys/user_B/id_rsa (RSA)
3.ユーザをスイッチする。
これで、準備ができました。
$ source gitsshm switch everpeace GIT_SSH is not set now. WARNING: GIT_SSH may not be maintained by gitsshm. GIT_SSH will be overwritten. current GIT_SSH is /Users/everpeace/github-keys/.gitsshm/user_A-ssh.sh
これで、gitでssh接続する時にuser_Aで認証できてると思います。
スイッチ可能なユーザはこんな感じで確認できます。
$ source gitsshm list available usernames: user_A user_B current GIT_SSH is /Users/everpeace/github-keys/.gitsshm/user_A-ssh.sh
今の設定はこんな感じで確認できます。
$ source gitsshm current current GIT_SSH is /Users/everpeace/github-keys/.gitsshm/user_A-ssh.sh
4.リセットする。
ssh-agentから鍵を削除して、ラッパースクリプトも解除してGIT_SSHを削除します。
$ source gitsshm reset detected GIT_SSH is maintained by chgitssh. Identity removed: /Users/everpeace/github-keys/user_A/id_rsa (/Users/everpeace/github-keys/user_A/id_rsa.pub) Identity removed: /Users/everpeace/github-keys/user_B/id_rsa (/Users/everpeace/github-keys/user_B/id_rsa.pub) remove dir /Users/everpeace/github-keys/.gitsshm GIT_SSH is not set now.
注意
コード
Gistにのせてありますので良ければ活用してください
追記
githubのレポジトリにもしてみました。よければフォークしてね。
https://github.com/everpeace/gitsshm
「プログラミングErlang」のRing Benchmarkをやってみた
最近「プログラミングErlang」を読んでいます。
- 作者: Joe Armstrong,榊原一矢
- 出版社/メーカー: オーム社
- 発売日: 2008/02/23
- メディア: 単行本（ソフトカバー）
- 購入: 8人 クリック: 284回
- この商品を含むブログ (97件) を見る
今後、並行、分散プログラミングが主流になるにつれて、Erlangという言語のもつパワーやその背後に横たわっている並行、分散プログラミングについての考え方がとても重要だと思うからです。最近Scala界隈で良く耳にするAkkaフレームワークもこのErlangから影響を受けているようです。
で、この本の中にこんな問題があったのでやってみました。
リングのベンチマークを書いてみよう。N個のプロセスからなるリングを作り、1つのメッセージがリングをM回るようにして、合計でN*Mのメッセージが送信されるようにする。さまざまなNとMの値について所要時間を計ってみよう。
プロセスとモジュールの設計
各プロセスとモジュールはこんな感じにしました。
２つのモジュールで構成されていて、それぞれのモジュールはこんな感じの責務を持ちます。
- ringbenchモジュール: メインプロセスを包含したモジュールです。このベンチマークの動作を制御します
- ringモジュール: リングです。リングの生成/停止、リングの各プロセスの処理など。リング自体はルートプロセスと通常のリングプロセスから構成されます。
下記のソースコードはgithub.com/everpeace/ring-benchmarkにあります。
まずは通常のリングプロセスから見ていきましょう。
通常のリングプロセス
リング中に存在するルートプロセス以外のプロセスはこのプロセスです。このプロセスは受け取ったトークンを隣のプロセスに中継するのが主な責務です。killというアトム*1はベンチマークが終わった後に自分を終了させるために使っています。
% Name は名前、 Nextはお隣のプロセスID listen_tokens(Name, Next) -> receive % killを受け取ったら終了。 kill -> forward_kill(Name, Next); % それ以外を受け取ったら次に転送してまた待ち状態に。 Token -> forward_token(Name, Token, Next), listen_tokens(Name, Next) end. forward_token(Name, Token, Next) -> io:format("[~p(~p)] token \"~p\" received. forwading to ~p~n", [Name, self(), Token, Next]), Next ! Token. forward_kill(Name, Next)-> io:format("[~p(~p)] exitting...~n", [Name, self()]), Next ! kill.
プロセスの生成は次のような感じにします。プロセス生成時にお隣さんを引数にとってしまうと、再帰的な生成がやりづらいので、プロセスをスタートさせると、リング中のお隣さんを指定してもらうのを待つ状態(wait_for_link関数)に入るようにします。その状態で{link, Next}というメッセージを受け取ると、Next(プロセスID)をお隣さんとして、トークンを待つ状態に入る(listen_tokens関数(上参照))という具合です。
% 通常のリングプロセスの生成 node_start(Name) -> spawn(fun() -> io:format("[~p(~p)] starting...~n", [Name, self()]), wait_for_link(Name) end). % 次要素の指定を待つ wait_for_link(Name) -> receive {link, Next} -> listen_tokens(Name, Next) %上参照 end.
ルートプロセス
メインプロセスとリングのインターフェースとなるプロセスです。リング中のプロセスとしても振る舞うので、通常のリングプロセスより少々複雑になります。
メインプロセスからのメッセージはタプルで受け取ることにして、最初の要素にメインプロセスのプロセスIDが入っているときに、メインプロセスからのメッセージだと解釈することにしました。
メインからのトークンを受け取ったら、タプルの第１要素に0周目であることを付け加えて、リング中に放流します。通常のプロセスは中継するだけにして、自分がそのメッセージを受け取ることで、リングを一周したことを検出しています。
最後にM周したことを検出したらメインプロセスにendedというメッセージを送っています。
ルートプロセスの生成は通常のリングプロセスと大体同じ感じなので省略。
listen_tokens(Name, Main, Next, M) -> receive % メインからのメッセージ % メインからkillを受け取った時(リング停止) {Main, kill} -> Next ! kill, listen_tokens(Name, Main, Next, M); % メインからトークンを受け取った時(トークンM周開始) {Main, Token} -> io:format("[~p(~p)] token \"~p\" is injected from main. the token starts rounding in the ring.~n", [Name, self(), Token]), Next ! {0, Token}, % 0周目 listen_tokens(Name, Main, Next, M); % リング中を流れるメッセージ % M周完了 {I, Token} when I =:= M-1 -> io:format("[~p(~p)] token \"~p\" reaches root ~p times.~n", [Name, self(), Token, M]), io:format("[~p(~p)] report the finish of benchmark to main(~p)~n", [Name, self(), Main]), Main ! ended, % メインにendedを送信 listen_tokens(Name, Main, Next, M); % I 周完了 {I, Token} -> io:format("[~p(~p)] token \"~p\" reaches root ~p times.~n", [Name, self(), Token, I+1]), Next ! {I+1, Token}, % I+1周目 listen_tokens(Name, Main, Next, M); % 終了 kill -> io:format("[~p(~p)] exitting... \n", [Name, self()]) end.
リングの生成
ルートプロセスと通常のリングプロセスを生成して、サイズNのリングを生成します。最初にルートプロセスを一個生成し、その後にN-1個のリングプロセスを生成しています。
init(Main, N, M) -> io:format("[main(~p)] constructing ~p nodes ring...~n", [self(), N]), Root = root_start(0, Main, M), % ルートを生成 First = create_nodes(1, N-1, Root), % ルート以外のリングプロセスを再帰的に生成(最初のリングプロセスIDが返る) Root ! {link, First}, % ルートの次要素は最初のプロセス Root. % ルートのプロセスIDを返す %リングサイズが1の時 create_nodes(_, 0, Root)-> Root; % 最後のノードはルートが次要素 create_nodes(Num, Num, Root)-> Node = node_start(Num), Node ! {link, Root}, Node; % 途中のノードは次のプロセスを次要素として指定 create_nodes(I, Num, Root)-> Node = node_start(I), Next = create_nodes(I+1, Num, Root), Node ! {link, Next}, Node.
メインプロセス
上記のリングと対話をしながらベンチマークを行うのがメインプロセスです。下記を行います。
mainプロセスのコードはこんな感じです。
start(N, M) -> statistics(runtime), statistics(wall_clock), Main = self(), Root = ring:init(Main, N, M), % リング生成、ルートプロセスのプロセスIdが返ってくる。 io:format("[main(~p)] injecting the token \"~p\".~n", [self(), M]), Root ! {Main, token}, % リングのルートプロセスにトークンを送る(ベンチマーク開始) receive % リングからの終了通知待ち ended -> void end, Root ! {Main, kill}, % リングを停止 {_, Time1} = statistics(runtime), {_, Time2} = statistics(wall_clock), U1 = Time1, U2 = Time2, io:format("[main(~p)] ring benchmark for ~p processes and ~p tokens = ~p (~p) milliseconds\n", [self(), N, M, U1, U2]).
動作させてみる。
erlangシェルで動作させてみましょう。N=3,M=2です。
-(~/Documents/github/ring-benchmark)-
(git:master) $ erl
Erlang R15B01 (erts-5.9.1) [source] [64-bit] [smp:4:4] [async-threads:0] [hipe] [kernel-poll:false]
Eshell V5.9.1 (abort with ^G)
1> ringbench:start(3,2).
[main(<0.31.0>)] constructing 3 nodes ring...
[main(<0.31.0>)] injecting the token "2".
[0(<0.33.0>)] starting...
[1(<0.34.0>)] starting...
[2(<0.35.0>)] starting...
[0(<0.33.0>)] token "token" is injected from main. the token starts rounding in the ring.
[1(<0.34.0>)] token "{0,token}" received. forwading to <0.35.0>
[2(<0.35.0>)] token "{0,token}" received. forwading to <0.33.0>
[0(<0.33.0>)] token "token" reaches root 1 times.
[1(<0.34.0>)] token "{1,token}" received. forwading to <0.35.0>
[2(<0.35.0>)] token "{1,token}" received. forwading to <0.33.0>
[0(<0.33.0>)] token "token" reaches root 2 times.
[0(<0.33.0>)] report the finish of benchmark to main(<0.31.0>)
[main(<0.31.0>)] ring benchmark for 3 processes and 2 tokens = 10 (3) milliseconds
[1(<0.34.0>)] exitting...
[2(<0.35.0>)] exitting...
[0(<0.33.0>)] exitting...
okうまく行ってますね。この記事で使ったコードはgithub.com/everpeace/ring-benchmarkにあります。Makefileが作ってあるので、make runだけでもしよかったら試してみてください。
*1:シンボルみたいなやつ
Scala/SBT/Growlで快適TDD環境「sbtのテスト結果をGrowlで通知する」
会社のRuby好きな同僚に
ZenTestいいわぁ。しかもGrowlで通知とかいいわぁ。
なんて自慢されてくやしいので、Scalaにも当然あるよねと思って調べたらありました☆
作者はpicture-showを作ってるsoftpropsさんでした。
このプラグインは、sbtのtestタスクの結果をgrowlnotifyというGrowlのコマンドラインインターフェース経由で通知してくれるプラグインです。
さて、ではやってみましょう。
プロジェクトを作る
Scalaのプロジェクトはgiter8があるから簡単です。Javaでいうとmaven archetypeみたいな感じでしょうか。ビルドツールに依存してない点でgiter8のほうが良いですよね。
こんな感じで作れます↓
-(~/Documents/scala-sandbox)- $ g8 chrislewis/basic-project version [0.1.0-SNAPSHOT]: organization [com.example]: org.everpeace name [Basic Project]: sbt_growl_plugin_test Applied chrislewis/basic-project.g8 in sbt_growl_plugin_test -(~/Documents/scala-sandbox)- $ cd sbt_growl_plugin_test/ -(~/Documents/scala-sandbox/sbt_growl_plugin_test)- $ sbt test ...途中省略... [info] Compiling 1 Scala source to /Users/everpeace/Documents/scala-sandbox/sbt_growl_plugin_test/target/scala-2.9.1/classes... [info] Compiling 1 Scala source to /Users/everpeace/Documents/scala-sandbox/sbt_growl_plugin_test/target/scala-2.9.1/test-classes... [info] AppSpec [info] [info] The 'Hello world' string should [info] + contain 11 characters [info] + start with 'Hello' [info] + end with 'world' [info] [info] [info] Total for specification AppSpec [info] Finished in 200 ms [info] 3 examples, 0 failure, 0 error [info] [info] Passed: : Total 3, Failed 0, Errors 0, Passed 3, Skipped 0 [success] Total time: 6 s, completed 2012/05/03 18:14:06
ちゃんとサンプルテストも通ってますね。では、プロジェクトにプラグインを追加してみましょう。
sbt-growl-pluginを追加する
プラグインをプロジェクトに追加しましょう。softprops/sbt-growl-pluginのREADMEにあるようにすれば良いです。僕はプロジェクト単位に追加したかったので、project/plugin.sbtに
resolvers += "less is" at "http://repo.lessis.me"
addSbtPlugin("me.lessis" % "sbt-growl-plugin" % "0.1.3")と書きました。これだけです。
Growlでテスト結果を通知させてみる
では、テストしてみましょう。結果がGrowlで通知されるはずです。
-(~/Documents/scala-sandbox/sbt_growl_plugin_test)- $ sbt test Detected sbt version 0.11.2 Using /Users/everpeace/.sbt/0.11.2 as sbt dir, -sbt-dir to override. [info] Loading project definition from /Users/everpeace/Documents/scala-sandbox/sbt_growl_plugin_test/project [info] Set current project to sbt_growl_plugin_test (in build file:/Users/everpeace/Documents/scala-sandbox/sbt_growl_plugin_test/) [info] AppSpec [info] [info] The 'Hello world' string should [info] + contain 11 characters [info] + start with 'Hello' [info] + end with 'world' [info] [info] [info] Total for specification AppSpec [info] Finished in 154 ms [info] 3 examples, 0 failure, 0 error [info] [info] Passed: : Total 3, Failed 0, Errors 0, Passed 3, Skipped 0 [success] Total time: 1 s, completed 2012/05/03 18:54:05
とテスト結果が表示されると同時にこんな風にGrowlで通知が表示されます。
アイコンは自分でカスタマイズもできるみたいですね。
passed,error,failの３種類設定できるみたいです。デフォルトだとScalaのロゴがすべての場合に利用されるようです。
sbtのTriggered Executionでテストをまわす
あとは、sbtのTriggered Executionでソースの変更を監視して、随時テストさせれば、快適なTDD環境の出来上がりです！
sbtコンソールを立ち上げて「~test」を実行します。
-(everpeace@everpeaces-MacBook-Air)-(~/Documents/scala-sandbox/sbt_growl_plugin_test)- $ sbt Detected sbt version 0.11.2 Starting sbt: invoke with -help for other options Using /Users/everpeace/.sbt/0.11.2 as sbt dir, -sbt-dir to override. [info] Loading project definition from /Users/everpeace/Documents/scala-sandbox/sbt_growl_plugin_test/project [info] Set current project to sbt_growl_plugin_test (in build file:/Users/everpeace/Documents/scala-sandbox/sbt_growl_plugin_test/) > ~test [info] AppSpec [info] [info] The 'Hello world' string should [info] + contain 11 characters [info] + start with 'Hello' [info] + end with 'world' [info] [info] [info] Total for specification AppSpec [info] Finished in 148 ms [info] 3 examples, 0 failure, 0 error [info] [info] Passed: : Total 3, Failed 0, Errors 0, Passed 3, Skipped 0 [success] Total time: 1 s, completed 2012/05/03 19:01:01 1. Waiting for source changes... (press enter to interrupt)
この状態になれば、あとはソースが変更されしだいテストが勝手に回ってGrowlが鳴くという具合です。
Stanfordの機械学習コースは初学者にホントおススメです。
10月から3ヶ月間受講してきた、スタンフォード大学の機械学習のオープンコースであるhttp://www.ml-class.org/ のコースを修了しました。
機械学習の初学者として受講してとても満足感＆充実感があったのでシェアさせてもらいます。
来期(1月スタート)も同コースが開催されますので興味をもたれた方はぜひどうぞ。
学んだこと
- 教師あり学習
- 線形回帰、ロジスティック回帰、ニューラルネットワーク、SVM
- 教師有り学習アルゴリズムのチューニング手法
- Bias/Variance分析、エラー解析、学習曲線による分析、適合率(precision)/再現率(recall)/F値による分析
- 教師なし学習
- K-means、アノーマリ検出、主成分分析
- 応用
- ニューラルネットワークによる文字認識システムの実装
- 協調フィルタリングによるリコメンダシステムの実装
敷居は高くないです
このクラスは通常のstanford open courseよりも難易度的には低く設定されてて、大学レベルの数学を知らない人もトライできるくらいに随所に必要な基礎知識の解説が出てくるので、気軽に参加できます。（ビデオの中でも、「数学的な細かいことは知らなくても大丈夫だから」とか言ってますｗ）
しかも、タダ。受講に際しての制約も一切なし。来るもの拒まず、去るもの追わず。
そういった意味でもとてもオープンなコースなので気軽に参加できます。
また、コースが2種類に分かれていて、自分の好きなほうで受講できるというのもポイントです。（ちなみに僕はAdvanced Trackで受講しました)
- Basic Track:ビデオ講義、ミニテスト(Review Question)、プログラム演習すべて受講可能だが、提出しなくてもいいコース（見るだけ、やるだけ）
- Advanced Track:ビデオ講義、ミニテスト(Review Question)、プログラム演習すべてを提出しなければいけないコース（見なきゃだめ、やらなきゃだめ）
それでいて結構実践的です
かといって概論や基礎だけにとどまらず、かなり実践を意識した講義＆演習内容になっています。
- ニューラルネットワークによる文字認識
- 協調フィルタリングにより映画のリコメンダシステム
といった、かなり実践的な題材を取り上げてくれています。講義でも「機械学習のエンジニアとしての人生に役に立つと思います」的な言葉もありました。
また、機械学習アルゴリズムを実際に適用したときに悩むような問題
なんかへの対策なんかも含まれていて、このコースが終わると機械学習の技術者として通用するんじゃないか、といった気分になれます。
ゆったりペースで学べます
個人的にはかなりゆるいペースで十分こなせたましたので、日夜仕事に追われあまり時間が取れないといわれる社会人の方々でも大丈夫だと思います。技術者として仕事の合間をぬってマイペースにスキルアップできるので、とってもオヌヌメです。
ペースとしてはこんな感じした：
⇒演習結果はgithubで公開中：https://github.com/everpeace/ml-class-assignments
プログラミング演習の多くは穴埋め形式になっていて、アルゴリズム全体を実装するのではなく、講義で学習したコアな部分のプログラムを埋めるといった形式です。
たとえばニューラルネットワークの演習では
- ニューラルネットワークの出力部分の計算
- バックプロパゲーションによるパラメータ更新処理
となっていました。
なので、プログラミング演習の負荷はそこまで高くないにもかかわらず、実践的な機械学習アルゴリズムの全容を理解することができるようになっているという点もとてもポイントになると思います。
みんなで学びあえます
インターネットで受講ということで、受講生の数もかなり多い反面、スタッフは数人です。
ということで、スタッフに直接質問はできないのですが、コース内のページには受講生どうしがやり取りできる（もちろんスタッフとも）Q&Aフォーラムがあってかなり活発に質疑がされていました。
私が演習問題で詰まった時や、これは課題の方がおかしいんじゃないか？なんて疑問をフォーラムに書き込んだときは数分で誰かから返答が来てびっくりでした。全世界で受講生がいるので24時間いつだって、どこかでだれかは同じ勉強してるんですね。
この点でも、一人で進めていて挫折する、なんて危険性にも考慮してくれているのもポイントです。
参考ですが、今回のコースの受講生分布を表すヒートマップ(Global版)です。
日本がかなり薄いのがちょっと残念ですね。
- Global: http://i.imgur.com/rZ2yD.png
- APJ: http://i.imgur.com/lR8MK.png
- America: http://i.imgur.com/TJlyH.png
- Europe: http://i.imgur.com/ZmD4s.png
機械学習以外も色々あっておススメです
今期(2011/10〜2011/12)は人工知能、機械学習、データベースくらいのコースだったんですが、来期（1月スタート）はさまざまな分野のコースが開催されるようです。もちろん機械学習のコースも再度開催されます。
今期の機械学習ページ http://www.ml-class.org/ に来期開催されるコース群へのリンクがありますので興味があればぜひ。
僕の琴線に触れるのは
・Software as a Service
・Design and Analysis of Algorithms I
・Game Theory
・Cryptography
といったところ。僕は来期はcryptographyかgame theoryか悩み中（両方はちょっと高負荷になっちゃうかもなので）。。。
学んだらちゃんとモノにしたい
時代は、ビッグデータ全盛期。クラウドも分散計算も大フィーバー。winnyの作者の方も無罪確定でP2Pの技術開発はほう助罪に当たらない判例ができて本当によかっねといった感じで、
はとってもこれからはキーになると思われます。
そんな時に機械学習のコースを受講できたのはとってもありがたかったです。しかも仕事にもプライベートにもまったく支障をきたさず勉強できたのはとてもうれしいです。
ただ、今回のプログラム演習で使用したoctaveは実稼動の機械学習システムではあまり適用されていない模様。となるとやっぱり実稼動でも通用する言語で機械学習を実装できる技術がほしいところです。
コース内のフォーラムではやっぱC/C++でしょ、pythonでしょ、データの前処理ならperlだろ、と色々いう人がいました。
octaveとペアで良く聞かれるRですが、Rは実稼動システムで実績はあるのでしょうか。RIHPEもあるからこれからは使われていくようになるのかな？最近だとWeb系の会社では「Rの知識があると望ましい」みたいな求人もあるようなので、現場で使われているのかもしれませんね。
僕が選択できる実用的な言語というとやっぱりJavaかScala。ということで、そっち系でちょこちょこ見たりしています。
Hadoop上で動く機械学習ライブラリMahoutもウォッチはしてるけれど、ここ数ヶ月動きがない模様。
SparkっていうScalaベースの分散計算のライブラリを最近触ってみたけど、行列計算とかがまだまだ充実してなくて、すぐに分散機械学習アルゴリズムで楽しめるってわけじゃなさそうです。分散計算だけ手軽にかけてかなりいいと思うんだけど。（分散の行列計算から実装しなきゃだとちょっと面倒。。機械学習のアルゴリズムを動作させたいですからね。）
分散には対応していないけれど、Scalaだと、Scalalaっていう線形代数ライブラリがあるので、これで演習のやり直しでもしてみようかな、なんて思ったりしています。見たところ行列演算は結構Octaveっぽく書いたりできるので、やりやすいかなって思ったり。最近良く聞くの並列コレクションとか対応してるのかな。。。
といったところで実践に向けた活動はまだまだ停滞気味なんだけれども、なんとか実践で使える機械学習の技術を磨いていきたいところです。
クラウドやら分散の時代がやってきて、SIerで雇われてるプログラマなんて多くが職にあぶれる時代がやってくるぞ、なーんて怖いニュースも聞いたりする世知辛い時代ですが、日々精進することで、そんな篩（ふるい）がやってきてもちゃんと引っかかるようになりたいものですね。
おしまい。
[形式手法][モデル検証] AlloyでDining Philosophors 日本語版
FormalMethod勉強会をやられていて、最近は僕も圏論勉強会でご一緒させていただいている id:kencoba さんが前から提案されていた
Unicode identifier in Alloy Analyzer
http://alloy.mit.edu/community/node/1039
がめでたく本家のAlloy Analyzerに取り込まれることになったそうです☆
モデル検証において、識別子が日本語もOKということはソースもそうだけれど、図示したときの理解しやすさが格段にわかりやすくなる。
ってことでDining Philosophersのalloyのモデルを日本語化してみました。
まずは、デッドロック状態を図示したやつ。
ソースはコチラ。
