Modular Interpreters

The content of this chapter is available as a Scala file here.

A Monad Library

We define a Monad library in Scala. Monad libraries like in scalaz and cats (for Scala) or the Haskell standard library look similar.

trait Monad {
  type M[_] // this time we treat M as a type member and not as type parameter
            // because it leads to shorter type signatures
  def unit[A](a: A): M[A]
  def bind[A, B](m: M[A], f: A => M[B]): M[B]

  extension [A](m: M[A])
    def map[B](f: A => B): M[B] = bind(m, (x: A) => unit(f(x)))
    def flatMap[B](f: A => M[B]): M[B] = bind(m, f)
}

We formulate concrete monads in the form of abstract interfaces first. The idea of those interfaces is that it should be possible to use the monad only in terms of that interface, without knowing anything about M. The advantage of this approach is that it enables us to compose monads. M changes in every composition of monads. For instance, when composing the list monad and the option monad, then M[X] = Option[List[X]] or M[X] = List[Option[X]].

By keeping M abstract and using it only via the interfaces, "client code" does not need to depend on the particular composition of monads.

Reader Monad

The Reader (or Environment) monad captures computations that depend on an environment of type R.

The ask function yields the current environment, the local function is used to transform the environment in a subcomputation a by an environment transformer f.

trait ReaderMonad extends Monad {
  type R
  def ask: M[R]
  def local[A](f: R => R, a: M[A]): M[A]
}

The standard implementation of the Reader monad:

trait ReaderMonadImp extends ReaderMonad {
  type M[X] = R => X
  def unit[A](a: A): M[A] = r => a
  def bind[A, B](m: M[A], f: A => M[B]): M[B] = r => f(m(r))(r)
  def ask: M[R] = identity
  def local[A](f: R => R, a: M[A]): M[A] = r => a(f(r))
}

An example of using the Reader monad to propagate an environment of type Int through a computation.

object ReaderExample extends ReaderMonadImp {
  type R = Int
  def example: M[Int] = for { x <- ask } yield (x + 1)
  def example2: M[Int] = local(r => 99, example)
}

A more useful example where we use the Reader monad to propagate a mapping from identifiers to boolean values in an interpreter for boolean formulas. Note that the signature of eval is identical to def eval(e: Exp): Map[String, Boolean] => Boolean, that is, we curry eval to make it applicable to the Reader monad.

object ReaderExample2 extends ReaderMonadImp {
  enum Exp:
    case Id(x: String)
    case And(l: Exp, r: Exp)
    case Or(l: Exp, r: Exp)
  import Exp._
  type R = Map[String, Boolean]

  def eval(e: Exp): M[Boolean] = e match {
    case Id(x) => for {env <- ask } yield env(x)
    case And(l, r) => for {
      x <- eval(l)
      y <- eval(r)
    } yield (x && y)
    case Or(l, r) => for {
      x <- eval(l)
      y <- eval(r)
    } yield (x || y)
  }
}

The implementation of the And case is semantically equivalent to this code:

case And(l, r) => env => {
  val x = eval(l)(env)
  val y = eval(r)(env)
  x && y
}

However, the monadic code is more abstract (and hence more reusable) because it is not coupled to the concrete M.

State Monad

This is the interface and standard implementation for the State monad:

trait StateMonad extends Monad {
  type S
  def getState: M[S]
  def putState(s: S): M[Unit]
}

trait StateMonadImp extends StateMonad {
  type M[A] = S => (A, S)
  def unit[A](a: A): M[A] = (s: S) => (a, s)
  def bind[A, B](m: M[A], f: A => M[B]): M[B] = (s: S) => {
    val (a, s2) = m(s)
    f(a)(s2)
  }
  def getState: M[S] = s => (s, s)
  def putState(s: S): M[Unit] = _ => ((), s)
}

Continuation Monad

And here is the interface for the Continuation monad. The Continuation monad provides a method callcc, which reifies the current Continuation k: A => M[B].

trait ContinuationMonad extends Monad {
  def callcc[A, B](f: (A => M[B]) => M[A]): M[A]
}

Implementaions

Now we provide implementations of the monad interfaces.

The identity monad, which is the end of each transformer chain reads:

trait IdentityMonad extends Monad {
  type M[A] = A
  def unit[A](a: A): M[A] = a
  def bind[A, B](m: M[A], f: A => M[B]) = f(m)
}

object IdentityMonad extends IdentityMonad

We organize most other monads as monad transformers. A monad transformer is parameterized with another monad. The monads are organized in a chain. Operations of "inner" monads must be lifted to top-level operations.

trait MonadTransformer extends Monad {
  val m: Monad
}

Reader Monad Transformer

The Reader monad transformer. We provide some convenient functions lift, lift2 etc. to lift functions from the inner monad. Note that M[X] = R => m.M[X] instead of M[X] = R => X (as for the non-transformer version of the Reader monad). The correct implementation of the interface methods follows from this type equation.

trait ReaderT extends MonadTransformer with ReaderMonad {
  type R
  override type M[X] = R => m.M[X]
  override def unit[A](a: A): M[A] = r => m.unit(a)
  override def bind[A, B](x: M[A], f: A => M[B]): M[B] =
    r => m.bind(x(r), (n: A) => f(n)(r))
  override def ask: M[R] = r => m.unit(r)
  override def local[A](f: R => R, a: M[A]): M[A] = r => a(f(r))
  protected implicit def lift[A](x: m.M[A]): M[A] = r => x
  protected implicit def lift2[A, B](x: A => m.M[B]): A => M[B] = a => lift(x(a))
  protected implicit def lift3[A, B, C](x: (A => m.M[B]) => m.M[C]): (A => M[B]) => M[C] =
    f => r => x((a: A) => f(a)(r))
  protected implicit def lift4[A, B, C, D](x: ((A => m.M[B]) => m.M[C]) => m.M[D]): ((A => M[B]) => M[C]) => M[D] =
    f => r => x((a: A => m.M[B]) => f(lift2(a))(r))
}

// The original Reader monad can be reconstructed by composing ReaderT with the identity monad.

trait ReaderMonadImpl extends ReaderT {
  val m: IdentityMonad = IdentityMonad
}

We do not need this because we have just synthesized it:

trait ReaderMonadImpl extends ReaderMonad {
  type M[X] = R => X
  def unit[A](a: A): M[A] = r => a
  def bind[A, B](m: M[A], f: A => M[B]): M[B] = r => f(m(r))(r)
  def ask: M[R] = identity
  def local[A](f: R => R, a: M[A]): M[A] = (r) => a(f(r))
}

State Monad Transformer

The design of StateT is similar to that of ReaderT:

trait StateT extends MonadTransformer with StateMonad {
  type M[A] = S => m.M[(A, S)]
  override def unit[A](a: A): M[A] = (s: S) => m.unit(a, s)
  override def bind[A, B](x: M[A], f: A => M[B]): M[B] = (s: S) => {
     m.bind[(A, S), (B, S)](x(s), { case (a, s2) => f(a)(s2)})
  }
  override def getState: M[S] = s => m.unit((s, s))
  override def putState(s: S): M[Unit] = _ => m.unit(((), s))
}

// and again we can reconstruct the ordinary State monad.

trait StateMonadImpl extends StateT {
  val m: IdentityMonad = IdentityMonad
}

We do not need this because we have just synthesized it:

trait StateMonadImpl extends StateMonad {
  type M[A] = S => (A, S)
  def unit[A](a: A): M[A] = (s: S) => (a, s)
  def bind[A, B](m: M[A], f: A => M[B]): M[B] = (s: S) => {
     val (a, s2) = m(s)
     f(a)(s2)
  }
  def getState: M[S] = s => (s, s)
  def putState(s: S): M[Unit] = _ => ((), s)
}

Continuation Monad

We could also synthesize ContinuationMonadImpl from a ContT just as we did for ReaderMonadImpl and StateMonadImpl, but for simplicity we only present the ordinary Continuation monad here.

trait ContinuationMonadImpl extends ContinuationMonad {
  type T
  type M[A] = (A => T) => T
  override def unit[A](a: A): M[A] = k => k(a)
  override def bind[A, B](m: M[A], f: A => M[B]): M[B] = k => m(a => f(a)(k))
  override def callcc[A, B](f: (A => M[B]) => M[A]): M[A] = k => f(a => _ => k(a))(k)
}

Compositions

Let's compose some monads.

The composition of the Reader monad and some Continuation monad.

trait ReaderContinuationMonadForwarder extends ReaderT with ContinuationMonad {
  val m: ContinuationMonad
  // call to lift4 inserted automatically
  override def callcc[A, B](f: (A => M[B]) => M[A]): M[A] = (m.callcc[A, B] _)(f)
}

Fro the implementation, we use the Continuation-monad implementation.

trait ReaderContinuationMonadImpl extends ReaderContinuationMonadForwarder {
  type T
  val m: ContinuationMonadImpl { type T = ReaderContinuationMonadImpl.this.T } =
    new ContinuationMonadImpl { type T = ReaderContinuationMonadImpl.this.T }
}

Composition of the Reader monad with some State monad.

trait ReaderStateMonadForwarder extends ReaderT with StateMonad {
  val m: StateMonad { type S = ReaderStateMonadForwarder.this.S }
  override def getState: M[S] = m.getState
  override def putState(s: S): M[Unit] = m.putState(s)
}

And the implementation with StateMonadImpl.

trait ReaderStateMonadImpl extends ReaderStateMonadForwarder {
  val m: StateMonadImpl { type S = ReaderStateMonadImpl.this.S } =
    new StateMonadImpl { type S = ReaderStateMonadImpl.this.S }
}

A Modular Interpreter

Now we use the monad library to modularize the interpreters of the various language variants we have seen so far.

trait Expressions extends Monad {
  abstract class Value
  abstract class Exp {
    def eval: M[Value]
  }
}

trait Numbers extends Expressions {
  case class NumV(n: Int) extends Value
}

trait Arithmetic extends Numbers {
  case class Num(n: Int) extends Exp {
    def eval = unit(NumV(n))
  }
  implicit def num2exp(n: Int): Exp = Num(n)

  case class Add(lhs: Exp, rhs: Exp) extends Exp {
    def eval = for {
                 l <- lhs.eval
                 r <- rhs.eval
               } yield (l, r) match {
                 case (NumV(v1), NumV(v2)) => NumV(v1 + v2)
                 case _ => sys.error("can only add numbers")
               }
  }
}

trait If0 extends Numbers {
  case class If0(cond: Exp, thenExp: Exp, elseExp: Exp) extends Exp {
    def eval = for {
                 c <- cond.eval
                 res <- c match {
                   case NumV(0) => thenExp.eval
                   case _ => elseExp.eval
                 }
               } yield res
  }
}

trait Functions extends Expressions with ReaderMonad {
  type Env = Map[String, Value]
  override type R = Env

  case class ClosureV(f: Fun, env: Env) extends Value
  case class Fun(param: String, body: Exp) extends Exp {
    def eval = for { env <- ask } yield ClosureV(this, env)
  }
  case class Ap(f: Exp, a: Exp) extends Exp {
    def eval = for {
                 fv <- f.eval
                 av <- a.eval
                 res <- fv match {
                   case ClosureV(fun, cenv) =>
                     local(env => cenv + (fun.param -> av), fun.body.eval)
                 }
               } yield res
  }
  case class Id(x: String) extends Exp {
    def eval = for {
                 env <- ask
               } yield env(x)
  }
  implicit def id2exp(x: String): Exp = Id(x)
  def wth(x: String, xdef: Exp, body: Exp): Exp = Ap(Fun(x, body), xdef)
}


trait Boxes extends Expressions with StateMonad  {
  type Store = Map[Address, Value]
  override type S = Store

  type Address = Int
  var _nextAddress = 0

  def nextAddress: Address = {
    _nextAddress += 1
    _nextAddress
  }

  case class AddressV(a: Address) extends Value

  case class NewBox(e: Exp) extends Exp {
    def eval = {
      val a = nextAddress
      for {
        v <- e.eval
        s <- getState
        _ <- putState(s + (a -> v))
      } yield AddressV(a)
    }
  }
  case class SetBox(b: Exp, e: Exp) extends Exp {
    def eval =
      for {
         box <- b.eval
         ev  <- e.eval
         s   <- getState
         _   <- putState(box match { case AddressV(a) => s.updated(a, ev) })
      } yield ev
  }
  case class OpenBox(b: Exp) extends Exp {
    def eval = for {
                 bv <- b.eval
                 s  <- getState
               } yield (bv match { case AddressV(a) => s(a) })
  }
  case class Seq(e1: Exp, e2: Exp) extends Exp {
    def eval = bind(e1.eval, (_: Value) => e2.eval)
  }

}

trait Letcc extends Expressions with ContinuationMonad with ReaderMonad {
  override type R = Map[String, Value]

  // We introduce a new application form CAp instead of using Ap because we cannot extend Ap
  case class CAp(f: Exp, a: Exp) extends Exp {
    override def eval: M[Value] =
      for {
         fv <- f.eval
         av <- a.eval
         res <- fv match { case ContV(f) => f(av) }
       } yield res
  }
  case class Letcc(param: String, body: Exp) extends Exp {
    override def eval: M[Value] =
      callcc[Value, Value](k => local(env => env + (param -> ContV(k)), body.eval))
  }
  case class ContV(f: Value => M[Value]) extends Value
}

Let's compose together some languages!

object AE extends Arithmetic with IdentityMonad {
  val aetest = Add(1, Add(2, 3))
}
assert(AE.aetest.eval == AE.NumV(6))

object FAELang extends Functions with Arithmetic with ReaderMonadImpl {
  val faetest = Ap(Fun("x", Add("x", 1)), Add(2, 3))
  assert(faetest.eval(Map.empty) == NumV(6))
}
object BCFAE extends Boxes with Arithmetic with Functions with If0 with ReaderStateMonadImpl {
  val test = wth("switch", NewBox(0),
                wth("toggle", Fun("dummy", If0(OpenBox("switch"),
                                          Seq(SetBox("switch", 1), 1),
                                          Seq(SetBox("switch", 0), 0))),
                    Add(Ap("toggle", 42), Ap("toggle", 42))))
}

assert(BCFAE.test.eval(Map.empty)(Map.empty)._1 == BCFAE.NumV(1))

object FAEwLetcc extends Arithmetic with Functions with If0 with Letcc with ReaderContinuationMonadImpl {
  override type T = Value
  val testprog = Add(1, Letcc("k", Add(2, CAp("k", 3))))
}

assert(FAEwLetcc.testprog.eval(Map.empty)(identity) == FAEwLetcc.NumV(4))