What's the point of using monads in an interpreter?

Question

I recently discovered this little scala example called Simple interpreter using monads:

object simpleInterpreter {

  case class M[A](value: A) {
    def bind[B](k: A => M[B]): M[B] =  k(value)
    def map[B](f: A => B): M[B] =  bind(x => unitM(f(x)))
    def flatMap[B](f: A => M[B]): M[B] = bind(f)
  }

  def unitM[A](a: A): M[A] = M(a)

  def showM(m: M[Value]): String = m.value.toString();

  type Name = String

  trait Term;
  case class Var(x: Name) extends Term
  case class Con(n: int) extends Term
  case class Add(l: Term, r: Term) extends Term
  case class Lam(x: Name, body: Term) extends Term
  case class App(fun: Term, arg: Term) extends Term

  trait Value
  case object Wrong extends Value {
   override def toString() = "wrong"
  } 
  case class Num(n: int) extends Value {
    override def toString() = n.toString()
  }
  case class Fun(f: Value => M[Value]) extends Value {
    override def toString() = "<function>"
  }

  type Environment = List[Pair[Name, Value]]

  def lookup(x: Name, e: Environment): M[Value] = e match {
    case List() => unitM(Wrong)
    case Pair(y, b) :: e1 => if (x == y) unitM(b) else lookup(x, e1)
  }

  def add(a: Value, b: Value): M[Value] = Pair(a, b) match {
    case Pair(Num(m), Num(n)) => unitM(Num(m + n))
    case _ => unitM(Wrong)
  }

  def apply(a: Value, b: Value): M[Value] = a match {
    case Fun(k) => k(b)
    case _ => unitM(Wrong)
  }

  def interp(t: Term, e: Environment): M[Value] = t match {
    case Var(x) => lookup(x, e)
    case Con(n) => unitM(Num(n))
    case Add(l, r) => for (val a <- interp(l, e);
               val b <- interp(r, e);
               val c <- add(a, b))
                      yield c
    case Lam(x, t) => unitM(Fun(a => interp(t, Pair(x, a) :: e)))
    case App(f, t) => for (val a <- interp(f, e);
               val b <- interp(t, e);
               val c <- apply(a, b))
              yield c
  }

  def test(t: Term): String = 
    showM(interp(t, List()))

  val term0 = App(Lam("x", Add(Var("x"), Var("x"))), Add(Con(10), Con(11)))
  val term1 = App(Con(1), Con(2))

  def main(args: Array[String]) {
    println(test(term0))
    println(test(term1))
  }
}

What's the use/advantage of monadic computations here? In fact, the M is nothing but an identity monad. Is this just introduced to give an example of monadic syntax or does it have an important effect?

Answer 1

Here's a little summary of Phil Wadler's paper: When you write an interpreter in straightforward, "direct" style, a lot of code has to change when you add a new feature. For example, if you add exceptions, you have to check if an exception is raised any place you might evaluate an expression, even if the construct is like if or while or function call, and so has nothing to do with exceptions.

If you write the interpreter in monadic style, you can add a new feature just by changing the monad. You usually also add a few new bits of syntax to support the feature, but none of the rest of the code changes. So monadic style is a way of making an interpreter that is modular with respect to language changes.

Examples:

• To add exceptions, change the monad to the error monad, add new syntax and code for throw and catch, and none of your other code changes.

• To change the language so that the value of an expression is a probability distribution, not just a value, change the monad, and add a probabilistic construct like "flip a biased coin". Again, none of the old code changes. (This one is really fun; I've done it myself.)

Now that I've told you what the advantage of monadic computations, I'd better tell you the supreme disadvantage: you can only do one interesting feature at a time. The reason is that in general, you cannot compose two monads to make a new monad. This is true not just in general, but of monads you might really like to use.

If you're really interested in making a modular interpreter, in which you can easily experiment with different combinations of language features (as opposed to just individual features), you need monad transformers. There's a great paper on Monad Transformers and Modular Interpreters by Sheng Liang, Paul Hudak, and Mark Jones. It's a great read; I recommend it highly.

Answer 2

Using a monad makes the parser/interpreter extensible. This paper by Philip Wadler takes some time to read, but explores this idea in great detail. See also Monadic Parsing in Haskell.