atnos-effのEff.addLastをEffでエミュレーション

はじめに

atnos-effはScalaでEff（More Extensible Effects）を扱うためのライブラリーである。EffはOlegさんと石井さんの論文で提案されたものであるが、atnos-effではこの論文には述べられていないEff.addLastという機能を提供している。addLastはEffにインタープリターを適用して最後に何か副作用のようなものを実行するために存在する。この文書ではaddLastの動きについてまずは説明して、その次に問題点を述べる。そのあとに論文で述べられているEffの機能を用いてaddLastをエミュレーションすることを目指し、それによって既存のaddLastの問題の解決を目指す。

またこの記事に登場するコードの一部はGitHubで公開されている。

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

addLastと既存の問題

addLastとは？

前述のとおりatnos-effはEff.addLastというものがあり、これは次のようなインターフェースとなっている。

def addLast(l: =>Eff[R, Unit]): Eff[R, A] =
  addLast(Last.eff(l))

private[eff] def addLast(l: Last[R]): Eff[R, A]

EffはADTとして3つのデータ型であるPureとImpureと、そしてImpureApを持つ^[1]。それらにそれぞれ次のようなlastというフィールドが追加されているため、このようにaddLastを利用することができる。ただしImpureApはApplicativeで合成されたときには専用の処理（並列化など）が書けるようにするための拡張である。

case class Pure[R, A](value: A, last: Last[R] = Last.none[R]) extends Eff[R, A] {
  def addLast(l: Last[R]): Eff[R, A] =
    Pure(value, last <* l)
}

case class Impure[R, X, A](union: Effect[R, X], continuation: Continuation[R, X, A], last: Last[R] = Last.none[R]) extends Eff[R, A] {
  def addLast(l: Last[R]): Eff[R, A] =
    Impure[R, X, A](union, continuation, last <* l)
}

case class ImpureAp[R, X, A](unions: Unions[R, X], continuation: Continuation[R, Vector[Any], A], last: Last[R] = Last.none[R]) extends Eff[R, A] {
  def addLast(l: Last[R]): Eff[R, A] =
    ImpureAp[R, X, A](unions, continuation, last <* l)
}

このように全てのデータlastというフィールドが存在しており、addLastは既存のlastと入力のlを<*（= productL）で結合するような形で実装されている。この<*は次のように実装されている。

def <*(last: Last[R]): Last[R] =
  (value, last.value) match {
    case (None, None)       => this
    case (Some(r), None)    => this
    case (None, Some(l))    => last
    case (Some(r), Some(l)) => Last(Option(r.map2(l)((a, b) => b <* a)))
  }

そして、このようにして結合されたlastは最後にEff[NoFx, A] => Aとするための関数Eff.runで実行される。

問題点

ここでmap2を利用していることが大きな問題であると著者は考えている。ImpureApの説明でも少し言及したが、atnos-effにはApplicativeの場合とMonadの場合で、効率化など目的にあわせて別の振る舞いができるようになっている。これはたとえばFutureの挙動を考えると分かりやすい。

• Monadの場合
  • ma.flatMap(a => f(a))となり、maに依存した関数fを実行するため、maを実行してから逐次fを実行する
• Applicativeの場合
  • ma.map2(mb)((a, b) => f(a, b))となり、maとmbは結果に依存関係がないため2つを同時に実行してからfを実行すればよい

このような違いにより、flatMap（モナド）からmap2などのApplicativeのインスタンスは自動生成できるが、あえて別の実装を作ることで効率を得ている。例としたFutureのようにScalaではこのようなApplicativeにおいては挙動を変更する（Monadインスタンスとの一貫性が実はない）ことが普通に行なわれているため、おそらくそれをサポートするためにatnos-effもApplicativeはより効率のよい別の処理が書けるようになっていると思われる。
この議論を踏まえてaddLastの合成に注目する。いま合成のコードはLast(Option(r.map2(l)((a, b) => b <* a)))となっているが、これに型をつけると次のようになる。

Last(Option(
  (r: Eval[Eff[R, Unit]]).map2(l: Eval[Eff[R, Unit]])
    ((a: Eff[R, Unit], b: Eff[R, Unit]) => b <* a)
))

つまり2つのEffな値であるaとbは<*(= b.map2(a){(b, _) => b}）で合成されている。したがってaddLastは最後にApplicativeな値として実行されることになる。これはインタープリターによってはaddLastの追加順序と実際の実行順序がまったく一致しない可能性を孕んでいるといえる。したがって、たとえばメインのコードはTaskなどで非同期にしつつも、終了処理は順序通りにやってもらうというようなことはできない。

atnos-eff-last-action

そこで今回はこのような挙動をEffの改造を使うことなく対応した。ソースコードは下記のリポジトリーに存在している。

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

まずはケースクラスなどを定義する。

sealed trait LastAction[A]
 
case class SideEffectLastAction(
  value: Eval[Unit]
) extends LastAction[Unit]
 
type _last[R] = LastAction |= R

そしてインタープリターは次のようになっている。

def runLast[U](implicit
  m: Member.Aux[LastAction, R, U]
): Eff[U, A] =
  Interpret
    .runInterpreter(eff)(new Interpreter[LastAction, U, A, Eval[A]] {
      override def onPure(a: A): Eff[U, Eval[A]] = {
        Eff.pure(Eval.now(a))
      }
 
      override def onEffect[X](
        x: LastAction[X],
        continuation: Continuation[U, X, Eval[A]]
      ): Eff[U, Eval[A]] = {
        x match {
          case SideEffectLastAction(value) =>
            continuation(())
              .map { eval =>
                value >> eval
              }
        }
      }
 
      override def onLastEffect[X](
        x: LastAction[X],
        continuation: Continuation[U, X, Unit]
      ): Eff[U, Unit] =
        x match {
          case SideEffectLastAction(value) =>
            continuation(()).map(_ => value.value)
        }
 
      override def onApplicativeEffect[X, T[_] : Traverse](
        xs: T[LastAction[X]],
        continuation: Continuation[U, T[X], Eval[A]]
      ): Eff[U, Eval[A]] = {
 
        continuation
          .apply(xs.map { case SideEffectLastAction(_) => () })
          .map { eval =>
            xs.foldLeft(Eval.Unit) {
              case (acc, SideEffectLastAction(value)) =>
                value >> acc
            } >> eval
          }
      }
    })
    .map(_.value)

軽く解説すると次のようになる。

• SideEffectLastActionにパターンマッチすることでGADTsであるLastAction[X]の型XをUnitに固定している
  • よって継続（continuation）を(): Unitで起動することができる
• 結合には*>ではなくて>>（= ma.flatMap(a => f(a).map(a))）を使っている

このように専用のエフェクトとすることで、Eff.addLastのようにMonadなのかApplicativeなのかの差を気にしなくてよくなるうえ、さらにGo言語のdeferのように逆順に実行されるといった挙動も簡単に作ることができる。

まとめ

いちおうすでにatnos-effにはPRを送信してある。

• https://github.com/atnos-org/eff/pull/292

ただこれがマージされるかどうか？についてはよく分からない。元々の論文にはない挙動であり、著者にもどちらがいいか？という判断がつかなかったからである。
いずれにしてもaddLastを狙ったとおり動かすなら、場合によってはインタープリターを自作などしても解決しないためforkする必要があるなど面倒になる。一方でこのようにインタープリターを使った手法なら自作すればいくらでも挙動を変更することができるため、よりよいと考えている。

脚注

1. ImpureApは元となった論文には登場しない。