2016年3月31日木曜日

State的状態機械2016

昨年Scalaにおける状態機械の実装戦略について以下の記事で検討しました。

OOP編はcase classで作った汎用の状態機械オブジェクトをOOP的な枠組みで利用しました。

そして、FP編ではOOP編で作った汎用の状態機械オブジェクトをそのままFP的な枠組みで利用できることを確認しました。

もちろん、これはOOPでもFPでも使用できる汎用の状態機械オブジェクトの作り方を確認するのが目的で、幸いどちらの目的にも使用できるものを作成することができました。

この記事で検討した方針で一年間プログラミングをしてきましたが、改良のポイントが出てきたので、これを反映した2016年版の状態機械オブジェクトを考えてみます。

ParseState

「状態+状態遷移を表現するオブジェクト兼代数的データ型」であるParseStateですが、2016年版では以下の点を変更しています。

  • イベントの入力用メソッドであるeventメソッドとendEventメソッドを統合
  • イベントをParseEventオブジェクトで表現
  • イベントに対する反応を新状態のParseStateと処理結果ParseResultの組を返すようにした

2015年版と機能的には変わらないのですが、Stateモナドの形に合わせることでストリーム処理で使いやすい構造になっています。

sealed trait ParseState {
  def apply(event: ParseEvent): (ParseState, Option[ParseResult])
}

case object InitState extends ParseState {
  def apply(event: ParseEvent): (ParseState, Option[ParseResult]) = event match {
    case CharEvent(',') => (InputState(Vector(""), ""), None)
    case CharEvent('\n') => (InitState, Some(ParseResult.empty))
    case CharEvent(c) => (InputState(Vector.empty, c.toString), None)
    case EndEvent => (InitState, None)
  }
}

case class InputState(
  fields: Vector[String],
  candidate: String
) extends ParseState {
  def apply(event: ParseEvent): (ParseState, Option[ParseResult]) = event match {
    case CharEvent(',') => (InputState(fields :+ candidate, ""), None)
    case CharEvent('\n') => (InitState, Some(RecordParseResult(fields :+ candidate)))
    case CharEvent(c) => (InputState(fields, candidate :+ c), None)
    case EndEvent => (InitState, Some(RecordParseResult(fields :+ candidate)))
  }
}
ParseEvent

2016年版では入力パラメタとして入力イベントを表現するParseEventを使用するようにしました。

2015年版では入力の終了をendEventメソッドでハンドリングしていましたが、2016年版ではEndEventイベントで扱うようになっています。

製品開発で実際に使用した経験で、この構造の方がストリーミング処理に適していることが分かりました。

具体的には、EndEventなどのイベントで状態をクリアな状態に戻すことができるので、scalaz-streamといったReactive-Streams的なパイプラインの部品として使用することが容易になります。

trait ParseEvent
case class CharEvent(c: Char) extends ParseEvent
case object EndEvent extends ParseEvent
ParseResult

計算結果を表現するParseResultは以下になります。

2015年版では、ParseStateが結果を管理していましたが、2016年版では結果をParseResultで外部に出力するようにしました。

ParseEventと同様に製品開発で実際に使用した経験で、Stateモナドとの相性がよいことが分かりました。

sealed trait ParseResult {
  def getRecord: Option[Vector[String]]
}
case object NoneParseResult extends ParseResult {
  def getRecord = None
}
case class RecordParseResult(record: Vector[String]) extends ParseResult {
  def getRecord = Some(record)
}

object ParseResult {
  val empty = RecordParseResult(Vector.empty)
}

Stateモナド

それでは、新版のParseStateをStateモナドで使ってみましょう。

2015年版に比べると結果を取り出す処理が若干複雑になっていますが、それほど大きな違いはありません。

Stateモナドで問題なく使えることが確認できました。

import scalaz._, Scalaz._

object ParserStateMonad {
  def action(event: ParseEvent) = State((s: ParseState) => s.apply(event))

  def parse(events: Seq[Char]): Seq[String] = {
    val xs = events.toStream.map(CharEvent) :+ EndEvent
    val t = xs.traverseS(action)
    val r = t.eval(InitState)
    r.flatten.flatMap(_.getRecord).flatten
  }

  def parseAnnotated(events: Seq[Char]): Seq[String] = {
    val xs: Stream[ParseEvent] = events.toStream.map(CharEvent) :+ EndEvent
    val t: State[ParseState, Stream[Option[ParseResult]]] = xs.traverseS(action)
    val r: Stream[Option[ParseResult]] = t.eval(InitState)
    r.flatten.flatMap(_.getRecord).flatten
  }
}

scalaz-stream版状態機械

次はscalaz-streamのProcessモナドです。

Scala的状態機械/FP編の「scalaz-stream版状態機械」と基本的には同じで、ParseStateの入出力が変更された部分に対応しています。

大きな違いとしては2015年版はParseState自身がストリームを流れてくる構造になっており、ParseStateから計算結果を取り出す処理になっていました。

それに対して、今回はParseStateによる処理結果であるParseResultがストリームを流れてくるので、これを取り出す構造になっています。

いずれにしても、OO版としても使える汎用の状態機械オブジェクトをscalaz-streamのProcessモナドで使えることが確認できました。

import scalaz._, Scalaz._
import scalaz.stream._

object ParserProcessMonadStateMonad {
  def fsm(state: ParseState): Process1[ParseEvent, ParseResult] = {
    Process.receive1 { evt: ParseEvent =>
      ParserStateMonad.action(evt).run(state) match {
        case (s, Some(r)) => Process.emit(r) fby fsm(s)
        case (s, None) => fsm(s)
      }
    }
  }

  def parse(xs: Seq[Char]): Seq[String] = {
    val events = xs.map(CharEvent) :+ EndEvent
    val source: Process0[ParseEvent] = Process.emitAll(events)
    val pipeline: Process0[ParseResult] = source.pipe(fsm(InitState))
    pipeline.map(_.getRecord).pipe(process1.stripNone).toList.last
  }

  import scalaz.concurrent.Task

  def parseTask(xs: Seq[Char]): Task[Seq[String]] = {
    val events = xs.map(CharEvent) :+ EndEvent
    val source: Process0[ParseEvent] = Process.emitAll(events)
    val pipeline: Process[Task, ParseResult] = source.pipe(fsm(InitState)).toSource
    pipeline.map(_.getRecord).pipe(process1.stripNone).runLastOr(Nil)
  }
}

まとめ

状態機械の実装方法について、1年間の実践経験を踏まえて改良版をまとめました。

状態機械の実装方法は色々な選択肢がありますが、OOPかつFPを同時に満たすものとなると選択肢が限られてきます。

OOP化はそれほど難しくないので、焦点はFP化ですが、StateモナドやProcessモナドで使用することを前提にした上で、自然な形の実装方法に落とし込めたと思います。

諸元

  • Java 1.7.0_75
  • Scala 2.11.7