The ratio of the free monad and AST

Question

I am referring to the source code of Ken Scambler below, also see the source of GitHub .

package kenbot.free import scalaz._ import Scalaz._ import Free._ import scala.collection.mutable // This example is based off the one in Runar Bjarnason "Dead Simple Dependency Injection" talk. // http://www.youtube.com/watch?v=ZasXwtTRkio // 0. Fantasy API // def put(key: String, value: String): Unit // def get(key: String): String // def delete(key: String): Unit // 1. ADT sealed trait KVS[+Next] case class Put[Next](key: String, value: String, next: Next) extends KVS[Next] // <---- def put(key: String, value: String): Unit case class Get[Next](key: String, onResult: String => Next) extends KVS[Next] // <---- def get(key: String): String case class Delete[Next](key: String, next: Next) extends KVS[Next] // <---- def delete(key: String): Unit object KVS { type Script[A] = Free[KVS, A] // 2. Functor definition implicit val functor: Functor[KVS] = new Functor[KVS] { def map[A,B](kvs: KVS[A])(f: A => B): KVS[B] = kvs match { case Put(key, value, next) => Put(key, value, f(next)) case Get(key, onResult) => Get(key, onResult andThen f) case Delete(key, next) => Delete(key, f(next)) } } // 3. Lifting functions def put(key: String, value: String): Script[Unit] = liftF( Put(key, value, ()) ) def get(key: String): Script[String] = liftF(Get(key, identity)) def delete(key: String): Script[Unit] = liftF(Delete(key, ())) // 4. Composite functions def modify(key: String, f: String => String): Free[KVS, Unit] = for { v <- get(key) _ <- put(key, f(v)) } yield () // 5. Write scripts val script: Free[KVS, Unit] = for { id <- get("swiss-bank-account-id") _ <- modify(id, (_ + 1000000)) _ <- put("bermuda-airport", "getaway car") _ <- delete("tax-records") } yield () // 6. Interpreters // Building an immutable structure def interpretPure(kvs: Script[Unit], table: Map[String, String] = Map.empty): Map[String, String] = kvs.resume.fold({ case Get(key, onResult) => interpretPure(onResult(table(key)), table) case Put(key, value, next) => interpretPure(next, table + (key -> value)) case Delete(key, next) => interpretPure(next, table - key) }, _ => table) // Directly running effects def interpretImpure(kvs: Script[Unit], table: mutable.Map[String, String]): Unit = kvs.go { case Get(key, onResult) => onResult(table(key)) case Put(key, value, next) => table += (key -> value); next case Delete(key, next) => table -= key; next } } 

If a follow these slides , any script (see 5. in the source code) is converted to something like Suspend(Op(Suspend(Op(......(Result(Op))..)) within the free monad.

Unfortunately, a script under 5 is just a linear sequence of commands.

Even after searching the Internet for several hours, I could not find any examples that provided more information on the following issues:

• The sequence of linear operations (which is also a tree, of course) is represented by Suspend Suspend(Op(Suspend(Op(......(Result(Op))..)) and thus is an AST representation; Is this correct assumption?
• How is a real AST represented in a free monad? I assume this happens when control structures are enabled? (for example, the left and right branches of a tree, depending on the state). Can someone illustrate an example when real ACTs come into play? Maybe an illustration of how "if" can be implemented in this example.
• What is the general approach for including control structures in scripts (as stated in 5 in the source code?)

PS: Please try to stick with Scala / ScalaZ, since Haskell is not yet my area of ​​expertise.

Answer 1

In Scalaz, the Free monad is like two cases (simplified and ignoring GoSub optimization):

  sealed abstract class Free[S[_], A] case class Return[S[_], A](a: A) extends Free[S, A] case class Suspend[S[_], A](a: S[Free[S, A]]) extends Free[S, A] 

First, see what Free.liftF does, for example. for

 def get(key: String): Script[String] = liftF(Get(key, identity)) 

when executing get("key") we get

 get("key") // definition of get liftF(Get("key",identity) // definition of liftF Suspend(Get("key",identity).map(Return) // definition of map for Get above Suspend(Get("key", identity andThen Return)) // identity andThen f == f Suspend(Get("key", Return)) 

After that, let's start with your questions:

• The sequence of linear operations (which is also a tree, of course) is represented by Suspend (Op (Suspend (Op (...... (Result (Op)) ..)) and, thus, is an AST representation? Is this correct assumption?

In fact, a program written in DSL using the free monad that emerges from a functor is a chain of “steps”, where each step is either Suspend containing one of your functor cases, or Return representing the end of the chain.

As a concrete example, a script looks something like this:

 Suspend(Get("swiss-bank-account-id", id => Suspend(Get(id, v => Suspend(Put(id, v+1000000, _ => Suspend(Put("bermuda-airport","getaway car", _ => Suspend(Delete("tax-records", _ => Return(()) )))))))))) 

As you can see, we essentially just “fill” the holes of our functor by continuing with the calculation, ending with a Return . In the DSL sample, we will always have a linear chain due to the fact that each case of the KVS functor has only one “hole” for filling, therefore there is no branching.

2. How is a real AST represented in a free monad? I assume this happens when control structures are enabled? (for example, the left and right branches of a tree, depending on the state). Can someone illustrate an example when real ACTs come into play? Maybe an illustration of how "if" can be implemented in this example.

Let us expand our DSL with a branching construct:

 case class Cond[Next](cond: Boolean, ifTrue: Free[KVS,Next], ifFalse: Free[KVS,Next]) extends KVS[Next] def cond[A](c: Boolean)(ifTrue: => Script[A])(ifFalse: => Script[A]): Script[A] = liftF(Cond(c,ifTrue,ifFalse)) 

after changing the cases of the interpreter, it can be used as follows:

 val script2: Script[Unit] = for { id <- get("swiss-bank-account-id") _ <- cond(id == "123") { Free.point[KVS,Unit](()) } { for { _ <- modify(id, ("LOTS OF " + _)) _ <- put("bermuda-airport", "getaway car") _ <- delete("tax-records") } yield () } } yield () 

So, now you have a “real” AST, where I interpret your “real” as “has branch nodes” instead of a linear chain form, as it has been so far. Expected Output:

 println(interpretPure( script2, Map("swiss-bank-account-id" -> "42", "42" -> "money", "tax-records" -> "acme corp"))) // Map(swiss-bank-account-id -> 42, 42 -> LOTS OF money, bermuda-airport -> getaway car) println(interpretPure( script2, Map("swiss-bank-account-id" -> "123", "tax-records" -> "acme corp"))) // Map(swiss-bank-account-id -> 123, tax-records -> acme corp) 

3. What is the general approach for including control structures in scripts (as stated in 5 in the source code?)

First of all, remember that you can, for example, use the standard, if inside for understanding:

 val script3: Script[Unit] = for { id <- get("swiss-bank-account-id") _ <- if (id == "123") { Free.point[KVS,Unit](()) } else { for { _ <- modify(id, ("LOTS OF " + _)) _ <- put("bermuda-airport", "getaway car") _ <- delete("tax-records") } yield () } } yield () 

Secondly, remember that because Script[A] is just Free[KVS,A] , you have a monad at your disposal, so any "control structure" defined, for example, Scala for monads will also work for you:

 val script4: Script[Unit] = modify("key",_+"!").untilM_ { get("key").map(_.length > 42) } println(interpretPure(script4, Map("key" -> ""))) // Map(key -> !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!) 

Take a look at Monad.scala and MonadSyntax.scala , there are also whileM and iterateWhile .