Hatena::ブログ(Diary)

Milestones to EVERPEACE 〜alius via〜

2012-09-17

合成できるモナド、モナドが合成できる時

(今回のコードは 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の2つで定義されているのです!

コードで書くとこんな具合です。

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は2重になったモナドを1重にしてくれますよね。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 )

合わせて読みたい。

今回のコード

今回のコードはgithub:everpeace/composing-monadsに有ります。

2012-05-19

「プログラミング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

めでたしめでたし。

今日のソースコード

github.com/everpeace/ring-benchmark-in-akka

2012-05-15

.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

これで、gitssh接続する時に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.

注意

  • このスクリプトはGIT_SSHを上書きしてまうので注意してください。
  • 環境変数を書き換えるので、sourceつけないと駄目です。
  • でも、alias gitsshm='source path/to/gitsshm'しておくとコマンドっぽく使えます。
  • ラッパースクリプトを生成してそれを指定してるだけなので、別にgithubじゃなくても使えます。
  • ssh-agent使ってないと落ちちゃうので気をつけて下さい。

コード

Gistにのせてありますので良ければ活用してください

追記

githubレポジトリにもしてみました。よければフォークしてね。

https://github.com/everpeace/gitsshm

「プログラミングErlang」のRing Benchmarkをやってみた

最近「プログラミングErlang」を読んでいます。

プログラミングErlang

プログラミングErlang

今後、並行、分散プログラミングが主流になるにつれて、Erlangという言語のもつパワーやその背後に横たわっている並行、分散プログラミングについての考え方がとても重要だと思うからです。最近Scala界隈で良く耳にするAkkaフレームワークもこのErlangから影響を受けているようです。

で、この本の中にこんな問題があったのでやってみました。

リングのベンチマークを書いてみよう。N個のプロセスからなるリングを作り、1つのメッセージがリングをM回るようにして、合計でN*Mのメッセージが送信されるようにする。さまざまなNとMの値について所要時間を計ってみよう。

プロセスモジュール設計

プロセスモジュールはこんな感じにしました。

f:id:everpeace:20120515202721p:image

2つのモジュールで構成されていて、それぞれのモジュールはこんな感じの責務を持ちます。

下記のソースコード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が入っているときに、メインプロセスからのメッセージだと解釈することにしました。

メインからのトークンを受け取ったら、タプルの第1要素に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.

メインプロセス

上記のリングと対話をしながらベンチマークを行うのがメインプロセスです。下記を行います。

  1. リングの生成
  2. リングへのトークンの注入
  3. リングからトークンM周完了通知受信
  4. 上記の処理時間の計測

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:シンボルみたいなやつ

2012-05-03

Scala/SBT/Growlで快適TDD環境「sbtのテスト結果をGrowlで通知する」

会社のRuby好きな同僚に

ZenTestいいわぁ。しかもGrowlで通知とかいいわぁ。

なんて自慢されてくやしいので、Scalaにも当然あるよねと思って調べたらありました☆

softprops/sbt-growl-plugin

作者はpicture-showを作ってるsoftpropsさんでした。

このプラグインは、sbtのtestタスクの結果をgrowlnotifyというGrowlのコマンドラインインターフェース経由で通知してくれるプラグインです。

さて、ではやってみましょう。

growl とgrowlnotifyをインストールする

ここからダウンロードしてインストールします。

プロジェクトを作る

まずはScalaのサンプルプロジェクトを作りましょう*1

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で通知が表示されます。

f:id:everpeace:20120503185648p:image:w360

アイコンは自分でカスタマイズもできるみたいですね。

passed,error,failの3種類設定できるみたいです。デフォルトだと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が鳴くという具合です。

2011-12-21

Stanfordの機械学習コースは初学者にホントおススメです。

10月から3ヶ月間受講してきた、スタンフォード大学機械学習のオープンコースであるhttp://www.ml-class.org/ のコースを修了しました。

機械学習の初学者として受講してとても満足感&充実感があったのでシェアさせてもらいます。

来期(1月スタート)も同コースが開催されますので興味をもたれた方はぜひどうぞ。


学んだこと


敷居は高くないです

このクラスは通常のstanford open courseよりも難易度的には低く設定されてて、大学レベルの数学を知らない人もトライできるくらいに随所に必要な基礎知識の解説が出てくるので、気軽に参加できます。(ビデオの中でも、「数学的な細かいことは知らなくても大丈夫だから」とか言ってますw)

しかも、タダ。受講に際しての制約も一切なし。来るもの拒まず、去るもの追わず。

そういった意味でもとてもオープンなコースなので気軽に参加できます。

また、コースが2種類に分かれていて、自分の好きなほうで受講できるというのもポイントです。(ちなみに僕はAdvanced Trackで受講しました)

  • Basic Track:ビデオ講義、ミニテスト(Review Question)、プログラム演習すべて受講可能だが、提出しなくてもいいコース(見るだけ、やるだけ)
  • Advanced Track:ビデオ講義、ミニテスト(Review Question)、プログラム演習すべてを提出しなければいけないコース(見なきゃだめ、やらなきゃだめ)

それでいて結構実践的です

かといって概論や基礎だけにとどまらず、かなり実践を意識した講義&演習内容になっています。

といった、かなり実践的な題材を取り上げてくれています。講義でも「機械学習エンジニアとしての人生に役に立つと思います」的な言葉もありました。

また、機械学習アルゴリズムを実際に適用したときに悩むような問題

なんかへの対策なんかも含まれていて、このコースが終わると機械学習技術者として通用するんじゃないか、といった気分になれます。


ゆったりペースで学べます

個人的にはかなりゆるいペースで十分こなせたましたので、日夜仕事に追われあまり時間が取れないといわれる社会人の方々でも大丈夫だと思います。技術者として仕事の合間をぬってマイペースにスキルアップできるので、とってもオヌヌメです。

ペースとしてはこんな感じした:

  • 平日の通勤時間(片道1時間弱)に、満員電車内でガメつく席を確保してiPadでビデオ講義を聞く&Review Quizに答える
  • 土日のどっちかで数時間プログラミング演習(by octave)に割く。

 ⇒演習結果はgithubで公開中:https://github.com/everpeace/ml-class-assignments

プログラミング演習の多くは穴埋め形式になっていて、アルゴリズム全体を実装するのではなく、講義で学習したコアな部分のプログラムを埋めるといった形式です。

たとえばニューラルネットワークの演習では

となっていました。

なので、プログラミング演習の負荷はそこまで高くないにもかかわらず、実践的な機械学習アルゴリズムの全容を理解することができるようになっているという点もとてもポイントになると思います。


みんなで学びあえます

インターネットで受講ということで、受講生の数もかなり多い反面、スタッフは数人です。

ということで、スタッフに直接質問はできないのですが、コース内のページには受講生どうしがやり取りできる(もちろんスタッフとも)Q&Aフォーラムがあってかなり活発に質疑がされていました。

私が演習問題で詰まった時や、これは課題の方がおかしいんじゃないか?なんて疑問をフォーラムに書き込んだときは数分で誰かから返答が来てびっくりでした。全世界で受講生がいるので24時間いつだって、どこかでだれかは同じ勉強してるんですね。

この点でも、一人で進めていて挫折する、なんて危険性にも考慮してくれているのもポイントです。

参考ですが、今回のコースの受講生分布を表すヒートマップ(Global版)です。

日本がかなり薄いのがちょっと残念ですね。

f:id:everpeace:20111221143923p:image:w360


機械学習以外も色々あっておススメです

今期(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の知識があると望ましい」みたいな求人もあるようなので、現場で使われているのかもしれませんね。

僕が選択できる実用的な言語というとやっぱりJavaScala。ということで、そっち系でちょこちょこ見たりしています。

Hadoop上で動く機械学習ライブラリMahoutもウォッチはしてるけれど、ここ数ヶ月動きがない模様。

SparkっていうScalaベースの分散計算のライブラリを最近触ってみたけど、行列計算とかがまだまだ充実してなくて、すぐに分散機械学習アルゴリズムで楽しめるってわけじゃなさそうです。分散計算だけ手軽にかけてかなりいいと思うんだけど。(分散の行列計算から実装しなきゃだとちょっと面倒。。機械学習アルゴリズムを動作させたいですからね。)

分散には対応していないけれど、Scalaだと、Scalalaっていう線形代数ライブラリがあるので、これで演習のやり直しでもしてみようかな、なんて思ったりしています。見たところ行列演算は結構Octaveっぽく書いたりできるので、やりやすいかなって思ったり。最近良く聞くの並列コレクションとか対応してるのかな。。。

といったところで実践に向けた活動はまだまだ停滞気味なんだけれども、なんとか実践で使える機械学習の技術を磨いていきたいところです。

クラウドやら分散の時代がやってきて、SIerで雇われてるプログラマなんて多くが職にあぶれる時代がやってくるぞ、なーんて怖いニュースも聞いたりする世知辛い時代ですが、日々精進することで、そんな篩(ふるい)がやってきてもちゃんと引っかかるようになりたいものですね。

おしまい。