Relation of free monad and AST

Question

I'm referring to the Ken Scambler's source code listed below, also see GitHub source .

package kenbot.free

import scalaz._
import Scalaz._
import Free._
import scala.collection.mutable

// This example is based off the one in Runar Bjarnason's "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 source code) is "transformed" into something like Suspend(Op(Suspend(Op(......(Result(Op))..)) within the free monad.

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

Even after searching the web for several hours, I wasn't able to find any examples, that gave more insight on the following questions:

1. The sequence of linear operations (which is also a tree of course) is represented by Suspend(Op(Suspend(Op(......(Result(Op))..)) and is thus a representation of the AST? Is this assumption right?
2. How is a real AST represented within the free monad? I assume, this happens, when control structures are included? (e.g. left and right tree branch, depending on condition) . Could someone please illustrate an example where real ASTs come into play? Maybe, an illustration of how an "if" could be implemented in the given example.
3. What is the general approach to include control structures into scripts (as given under 5 in source code?)

P.S.: Please try to stick to Scala / ScalaZ, as Haskell is not (yet) my field of expertise.

Answer 1

In Scalaz, the Free monad as the two cases (simplified and ignoring the 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]

Let's first see what Free.liftF does, e.g. for

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

when doing get("key") we will 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))

Having that, let's start with your questions:

1. The sequence of linear operations (which is also a tree of course) is represented by Suspend(Op(Suspend(Op(......(Result(Op))..)) and is thus a representation of the AST? Is this assumption right?

Essentially yes, a program written in the DSL using the free monad arising from a functor represents a chain of "steps" where each step is either a Suspend containing one of your functor cases or a Return representing the end of the chain.

As an concrete example, script looks about 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 with the continuation of the computation, terminating with a Return. In the sample DSL we will always have a linear chain, due to the fact that every case of the KVS functor only has one "hole" to fill, so no branching.

2. How is a real AST represented within the free monad? I assume, this happens, when control structures are included? (e.g. left and right tree branch, depending on condition) . Could someone please illustrate an example where real ASTs come into play? Maybe, an illustration of how an "if" could be implemented in the given example.

Let's extend 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 interpreter cases, it can be used like this:

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 branching nodes" instead of the linear chain form as was the case up until now. Output is as expected:

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 to include control structures into scripts (as given under 5 in source code?)

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

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 due to the fact that Script[A] is just Free[KVS,A] you have a monad at disposal, so any "control structure" defined in e.g. Scalaz for monads will work for you too:

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

println(interpretPure(script4, Map("key" -> "")))
// Map(key -> !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!)

Have a look at Monad.scala and MonadSyntax.scala, there's also whileM and iterateWhile.