Intrepreting nested calls with Free inside StateT

[Dan Sanduleac]

Hi,

I've been using a stateful IO program in one of my projects, using the type Program[A] = StateT[IO, S, A]

Then I got the idea of abstracting out the behaviour using a free monad, such that now I have Program[A] = StateT[ActionFC, S, A], where ActionFC is the free monad type over a dsl trait called Action.

I can interpret this using Free.runFC and an Action ~> IO transformation. So far so good.

Then I became interested in doing conditional branching inside this model.

And since I've abstracted out the IO operations, I'd like to also abstract whether we're running in live or not, but some pieces of code should only run in live, and these pieces of code are themselves Program (so they modify state). I'm nesting such programs inside ExecuteIfLive(p: Program[A]).

This is where it gets interesting, as supporting this seems to necessitate an Action ~> StateIO transformation, rather than just Action ~> IO.

Then I got stuck in how to interpret this ExecuteIfLive step, as well as how to run the final result, because I end up with stacked StateTs that must necessarily run on different layers of execution. 

But I want a single layer of execution - conceptually, if we're live, then flatMap in the program contained within ExecuteIfLive, otherwise, flatMap in a StateT that does nothing.

Is this possible? Am I missing something? 

Here's what I tried so far.

object FreeTest {
  import scalaz._, Scalaz._, scalaz.Free._
  import scalaz.effect.IO

  type S = Int
  type ProgramOf[F[_], A] = StateT[F, S, A]
  type ActionFC[A] = FreeC[Action, A]

  type Program[A] = ProgramOf[ActionFC, A]

  sealed trait Action[A]
  case object Increment extends Action[Unit] // should increment state
  case object Print extends Action[Unit]     // should print the state
  case class ExecuteIfLive(into: Program[Unit]) extends Action[Unit]

  /** Perform the action and increase the state by 1. */
  def command[A](action: Action[A]): Program[A] = {
    (Free liftFC action).liftM[ProgramOf].imap(_ + 1)
  }

  // scala can't derive this automatically, because reasons..
  implicit val actionFCMonad: Monad[ActionFC] = scalaz.Free.freeMonad[ Coyoneda[Action, ?] ]

  // The idea is that in our Program, we'll be using ExecuteIfLive, and we only know if we're live at the point
  // of interpreting the Program.

  val plus2 = command(Increment) replicateM_ 2 // should increase state by 4 -- twice by Increment, twice by each command

  val program = for {
    _ <- command(ExecuteIfLive(plus2))
    _ <- command(Print)
  } yield ()
  // This program, after being interpreted and executed, should end up with a state of 1 + 4 + 1 = 6 when live, or 1 + 1 = 2 when not live

  
  type StateIO[A] = ProgramOf[IO, A]

  import scalaz.effect.stateTEffect._
  val ioInterpreter(live: Boolean) = new (Action ~> StateIO) {

    override def apply[A](fa: Action[A]): StateIO[A] = fa match {
      case Increment => StateT(s => IO((s + 1, ())))
      case Print     => StateT.stateTMonadState[S, IO].get flatMap (s => IO.putLn(s).liftIO[StateIO])
      case ExecuteIfLive(p) => ??? // not even sure how to convert a ProgramOf[ActionFC, A] to ProgramOf[IO, A]
    }
  }
  
  val r = program.mapK[StateIO, Unit, S] { actionFC => // : ActionFC[(S, Unit)]
    Free.runFC(actionFC)(ioInterpreter(true)) // : StateIO[(S, Unit)
  }
  // Now I've got nested StateT essentially boiling down to two levels of state:
  // StateT[StateIO, S, Unit]
  // S => StateIO[(S, Unit)]
  // S1 => S2 => IO[(S2, (S1, Unit))] 
  
  // I want to interpret the ProgramOf[ActionFC, _] into a ProgramOf[IO, _], where ExecuteIfLive would be replaced
  // with the equivalent of a flatMap if we had started with ProgramOf[IO, _] in the first place.
}

[Tomas Mikula]

Hi Dan,

instead of

  case class ExecuteIfLive(into: Program[Unit]) extends Action[Unit]

you can have

  case object IsLive extends Action[Boolean]

and then define executeIfLive as

  def executeIfLive(p: Program[Unit]): Program[Unit] =

    command(IsLive) flatMap { if(_) p else Monad[Program].point(()) }

Regards,

Tomas

--
You received this message because you are subscribed to the Google Groups "scalaz" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scalaz+un...@googlegroups.com.
To post to this group, send email to sca...@googlegroups.com.
Visit this group at https://groups.google.com/group/scalaz.
For more options, visit https://groups.google.com/d/optout.

[Dan Sanduleac]

That's a good point, definitely simpler than what I was trying to do!

I'm still curious, though, if it is possible to interpret-and-splice-in a nested Program in such a situation. 

Perhaps if instead of the simple case of ExecuteIfLive(..), there was an Action such as EncryptUsingSecretKey(s: String), and then using different interpreters you could splice in a different Program (let's say, there is a different secret key for each interpreter) that does the encryption. For curiosity's sake let's say that the encryption program we splice in has to be a Program[byte[]] as defined above, because it also modifies the state of the Program it's being spliced into.

I'm sure we can simplify this as well (like, using a Kleisli and obtaining the encryption function: String => Program[byte[]] from that), but without using a Kleisli this way, can it be done?

Regards,

Dan

[Tomas Mikula]

I don't think there is a method in scalaz that would do what you want out of the box, but you could write one. Your interpreter would take an Action[A] and return Program[A]\/M[A] (where M is your target monad, e.g. StateT[IO, S, A]). Then your method to run the free program would call the interpreter and if it returned -\/(p), it would call itself recursively.

However, note that one big benefit of Free is the compositionality: being able to define instruction sets F[_] and G[_] *independently* and then get an interpreter for Coproduct[F, G, _] by composing the interpreters for F[_] and G[_]. These instruction sets don't need to know what final language (a big Coproduct) they will be injected in in the end. However, both your examples,

  case class ExecuteIfLive(into: Program[Unit]) extends Action[Unit]

and

  case class EncryptUsingSecretKey(s: String) extends Action[Program[byte[]]]

somehow dictate the final language to be Program[_]. This hinders the compositionality of your free programs.

To overcome this limitation, you could parameterize your instruction sets by an additional type parameter, call it K[_], that, in the end, would be instantiated to Program[_], but the instruction sets don't need to know about it upfront. As a consequence, you would need your own version of Free that accounts for this additional type parameter of the instruction set: Free[F[_[_], _], A]. Then, you will also need your own versions of Coproduct, Coyoneda, Inject, Functor. I have written such custom version of Free in [1].

Regards,

Tomas

[1] https://github.com/TomasMikula/nutcracker/blob/9ef6b3dd0d79e8842b86535de161443070090ebd/src/main/scala/nutcracker/util/free/FreeK.scala