EffでミュータブルなしStateとプロパティーベーステスト

はじめに

状態を扱う方法としてStateモナドがよく知られている。Extensible Effectsのライブラリーであるatnos-effが標準でStateが提供されているが、これは次のように微妙な点がある。

1. CatsのStateをそのままEffのエフェクトスタック^[1]へ乗せている^[2]が、そうする必要はない
2. Stateのインタープリター内でミュータブルなvar変数を利用している^[3]

この2点は実際使う上で実害があるわけではない^[4]が、せっかくなので完全に純粋なStateをatons-effで作ったほうがいいのではないかということで、この記事ではミュータブルを利用しないStateの実装を考えていく。さらにそのState実装に対してScalaCheck + cats-lawsでモナド則などのテストを与える。

なお、この記事にある完全なソースコードは下記のGitHubリポジトリーから入手できる。

• https://github.com/y-yu/atnos-eff-state

この記事への質問やコメントがあれば気軽に教えてほしい。

Extensible EffectsによるState実装

DSLの設計

まずCatsのStateとは別のデータ構造を次のように定義する。

StateTypes.scala

sealed trait State[S, A]

object State {
  case class Get[S]() extends State[S, S]

  case class Set[S](value: S) extends State[S, Unit]
}

Stateは2つの型パラメーターSとAを持ち、それぞれ状態の型と結果の型となる。モナドmoand: M[A]において結果の型はAとなるが、このAがfor (a <- monad)というようなfor式を書いたとき左辺の変数aの型となる。
代数的データ型として定義されたGet/Setはそれぞれ次のようになる

• Getは現在の状態を取得するDSLであり、そのためState[S, S]のように結果の型 = 状態の型となる
• Setは新しい状態をセットするDSLであり、状態の更新はモナドとしての結果がないため結果の型はUnitとなる

型レベルのユーティリティー定義

atnos-effをはじめとするExtensible Effectsでは型レベルリストのような構造に上記のGetといった型を乗せることになる。このような型レベルのコンテナー（= 入れ物）をエフェクトスタックと呼ぶことがあるが、エフェクトスタックに狙った型があるのか？というようなことをチェックしたくなるため、そういうユーティリティーを作っておく。

エフェクトスタックの制約

StateTypes.scala

trait StateTypes {
  type _state[S, R] = State[S, *] /= R
}

この_stateはkind-projectorの利用を前提として次のように使うことができる。

def something[R: _state[Int, *]](): Eff[R, Unit]

こうすることで上記の例でいえばsomethingの返り値の型であるEff[R, Unit]に状態に対する処理が必要であることを制約できる。

エフェクトスタックへの追加

for式などで使えるようにするため、次のget/setというユーティリティーを作っておく。

StateCreation.scala

trait StateCreation extends StateTypes {
  def get[S, R: _state[S, *]]: Eff[R, S] =
    Eff.send[State[S, *], R, S](State.Get())

  def set[S, R: _state[S, *]](value: S): Eff[R, Unit] =
    Eff.send[State[S, *], R, Unit](State.Set(value))
}

これを利用して次のようにfor式を組み立てることができる。

val eff: Eff[R, Int] = for {
  s1 <- get[Int, R]
  _ <- set[Int, R](1)
  s2 <- get[Int, R]
} yield s1 + num

インタープリターの実装

atons-effはaddLastというExtensible Effectsの元論文にはない機構を独自に搭載したことによって、このような低レイヤーのインタープリターを独自実装する際にとても冗長になってしまう。addLast関連はいったん無視して、StateInterpreterから意味がある部分だけを抜き出したのが下記のコードとなる。

StateInterpreter.scala

def runState[R, A, U, S](state: S)(eff: Eff[R, A])(implicit
  m1: Member.Aux[State[S, *], R, U]
): Eff[U, (A, S)] = {
  def interpretContinuation[X](
    s: S,
    c: Continuation[R, X, A]
  ): Continuation[U, X, (A, S)] =
    Continuation.lift { (x: X) =>
      runState(s)(c(x))
    }


  eff match {
    case Pure(a, last) =>
      Eff.pure((a, state))

    case Impure(NoEffect(a), c, last) =>
      Impure(
        NoEffect(a),
        interpretContinuation(state, c),
      )

    case Impure(u: Union[_, _], c, last) =>
      m1.project(u) match {
        case Right(tu) =>
          tu match {
            case State.Get() =>
              Eff.impure(state, interpretContinuation(state, c))

            case State.Set(value) =>
              Eff.impure((), interpretContinuation(value, c))
          }

        case Left(other) =>
          Impure(other, interpretContinuation(state, c))
      }
  }
}

atnos-effのInterpret.runInterpreterと再帰の仕方が似ているが、runInterpreterは一般化したためrunStateのように「次の状態」を引数で引き回すことができない。したがってatons-effにおけるStateInterpretationの実装はミュータブルなvarを利用せざるを得なかったものと思われる^[5]。

ScalaCheckとcats-lawsによるプロパティベーステスト

ここで作ったインタープリターが動作しているのかをプロパティベーステストしていく。ここではエフェクトスタックを次のRに固定して行う。

StateLawsTest.scala

type R = Fx.fx1[State[Int, *]]

このように状態の型はIntに固定で行う。

また、Arbitrary.arbitrary[A].sampleの返り値がAではなくてOption[A]となる^[6]ので、このようなデフォルト値を定義しておく。

StateLawsTest.scala

val default: Int = Arbitrary.arbitrary[Int].sample.getOrElse(1)

Arbitrary[Eff[R, A]]のインスタンス定義

プロパティベーステストはランダムにデータを作り、そのデータに対して操作を適用したあとで結果が予定された性質（モナド則など）を満しているかをチェックする。このためまずは今回作成したEff[R: _state[S, *], A]というような型を持つデータを自動生成するためのArbitrary[Eff[R, A]]のインスンタンス定義する必要がある。

StateLawsTest.scala

implicit def genState[A: Arbitrary](implicit
  aInt: Arbitrary[Int]
): Arbitrary[Eff[R, A]] =
  Arbitrary(
    Gen.frequency(
      1 -> Arbitrary.arbitrary[A].map(Eff.pure[R, A]),
      1 -> Arbitrary.arbitrary[A].map { x =>
        for {
          s <- StateEffect.get[Int, R]
          newState = s + 1
          _ <- StateEffect.set(newState)
        } yield x
      }
    )
  )

自動生成をどういうふうにしてもいいが次のような2種類の値が$1 : 1$の割合で生成されるようにした。

• 任意の型Aの値をEff.pureで持ち上げた値
• getで状態sを取得した後、それに1を足し算した値$s + 1$で状態を更新しつつ型Aの値を結果とする値

比較用のインスタンスEq[Eff[R, A]]

ランダム生成ができるようになったところで、次は比較のためのインスタンスEq[Eff[R, A]]を作る必要がある。

implicit def equalState[A](implicit
  eq: Eq[(A, Int)]
): Eq[Eff[R, A]] =
  Eq.by { (eff: Eff[R, A]) =>
    Eff
      .run(
        eff.runState(default)
      )
  }

これは単純にインタープリターを起動して得られた状態と結果の両方（タプル値）が等しければ等しいとみなすインスタンスとなる。

モナド則の検査

あとはcats-lawsに入っているMonadTestsを利用すればよい。cats用のMonadインスタンスはatons-effが提供しているものを使えばよい。

import Eff.EffMonad

def checkAll(props: Seq[(String, Prop)]): Unit = {
  for ((name2, prop) <- props) yield {
    property(name + ":" + name2) = prop
  }
}

checkAll(MonadTests[Eff[R, *]].monad[Int, Int, Int].props)
checkAll(ApplicativeTests[Eff[R, *]].applicative[Int, Int, Int].props)

ついでにApplicativeTestsでアプリカティブ則もテストさせてみる。これをsbt testすると次のようになる。

sbt:atnos-eff-state> test
[info] Formatting 1 Scala sources...
[info] compiling 1 Scala source to /Users/yyu/Desktop/atnos-eff-state/target/scala-2.13/test-classes ...
[info] + StateLaws.StateLaws:tailRecM stack safety: OK, proved property.
[info] + StateLaws.StateLaws:applicative unit: OK, passed 100 tests.
[info] + StateLaws.StateLaws:map flatMap coherence: OK, passed 100 tests.
[info] + StateLaws.StateLaws:monad left identity: OK, passed 100 tests.
[info] + StateLaws.StateLaws:monoidal left identity: OK, passed 100 tests.
[info] + StateLaws.StateLaws:monad right identity: OK, passed 100 tests.
[info] + StateLaws.StateLaws:monoidal right identity: OK, passed 100 tests.
[info] + StateLaws.StateLaws:applicative identity: OK, passed 100 tests.
[info] + StateLaws.StateLaws:applicative homomorphism: OK, passed 100 tests.
[info] + StateLaws.StateLaws:applicative map: OK, passed 100 tests.
[info] + StateLaws.StateLaws:applicative interchange: OK, passed 100 tests.
[info] + StateLaws.StateLaws:ap consistent with product + map: OK, passed 100 tests.
[info] Passed: Total 12, Failed 0, Errors 0, Passed 12
[success] Total time: 14 s, completed 2021/11/20 23:56:30

このように、とりあえずモナド則 + アプリカティブ則に関してはうまく実装できたらしいことが分かる。

まとめ

業務で必要となったあるインタープリターで状態が欲しくなり、atnos-effの実装を見て内部で状態を使っているのが変だと思い自力で作ってみることにした。しかしImpureApの特別な内部構造であったり、addLastの拡張によってatnos-effにおけるインタープリターは本質的でないところで肥大化してしまうという印象を持った。たしかに並行・並列のことなどを考えるとImpureApが必要であることも理解できるし、リソース管理などでaddLastがあったほうがいいこともあるものの、ここまで複雑となるとインタープリターを書くのは大変でかつランタイムエラーの危険がつきまとう一か八かの作業と言わざるを得なくなる。したがって普通はvar変数を利用してでもInterpret.runInterpreterを利用する方がより安全になると思う。このようなatons-effの方向性はこれはこれでいいとして、一方でもっと原理主義的なExtensible Effectsの実装があればインタープリターをもっとシンプルに実装できると思う。
また今回はじめてScalaCheck + cats-lawsによるモナド則などのプロパティーベーステストを実施してみた。scalapropsでの経験が多少あったため、比較的簡単に書くことができたがもう少しドキュメントがあってもいいかもしれない。

参考文献

• 確率モナドの Cats 実装とモナド則の Discipline テスト
  • cats-lowsのことが書いてある日本語記事で、自分で一通りやったあとに発見したが、はじめに読んでおけばもっと簡単になったと思う……

脚注

1. エフェクトスタックについては軽く後述するが、この記事では最低限のことすらカバーできていないかもしれない……。

2. https://github.com/atnos-org/eff/blob/68280574a80713a451c0e3b00945f6dfd37101df/shared/src/main/scala/org/atnos/eff/StateEffect.scala#L21-L39

3. https://github.com/atnos-org/eff/blob/68280574a80713a451c0e3b00945f6dfd37101df/shared/src/main/scala/org/atnos/eff/StateEffect.scala#L93

4. CatsのStateを直接利用しているのでget/putの挙動をインタープリターで変更したくなったときに面倒なことにはなるが、できないわけではないと思われる。またインタープリターがここで利用しているミュータブル変数が複数スレッドなどからアクセスされる可能性もないと考えられる。

5. ソースコードは省略したがatnos-effではImpureApという Freer Applicative とも言えるような機能をサポートしている。しかし効率化のためなのか、それともScalaの型システムの都合なのかAnyなどで型エラーを回避した箇所が大量にあり、少し失敗したインタープリターを書くとすぐにランタイム型エラーが生じる。Interpret.runInterpreterを使えばImpureApなどデータ構造Effの具体的なデータ構造に対して直接アクセスしなくて済むため、このような型的にアンセーフな部分を隠蔽しておきたいという思惑があったのかもしれない。

6. xuwei_kさんのコメントによると、ScalaCheckのGenはfilterを搭載しており、filterによって値が取れたり取れなかったりするためであるからだという。