Qual é o sentido de usar mônadas em um intérprete?

Question

Eu descobri recentemente este pequeno Exemplo de Scala chamado Intérprete simples usando mônadas:

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))
  }
}

Qual é o uso/vantagem dos cálculos monádicos aqui? De fato, o M não passa de uma mônada de identidade. Isso é apenas introduzido para dar um exemplo de sintaxe monádica ou tem um efeito importante?

Answer 1

Aqui está um pequeno resumo do artigo de Phil Wadler: quando você escreve um intérprete no estilo "direto" direto, muito código precisa mudar quando você adiciona um novo recurso. Por exemplo, se você adicionar exceções, precisar E se ou enquanto ou chamada de função e, portanto, não tem nada a ver com exceções.

Se você escrever o intérprete em estilo monádico, poderá adicionar um novo recurso apenas alterando a Mônada. Você geralmente também adiciona alguns novos bits de sintaxe para suportar o recurso, mas nenhum dos restos do código muda. Portanto, o estilo monádico é uma maneira de fazer um intérprete modular em relação às mudanças de idioma.

Exemplos:

• Para adicionar exceções, altere a mônada para a Monad Erro, adicione nova sintaxe e código para throw e catch, e nenhum dos seus outros mudanças de código.

• Mudar o idioma para que o valor de uma expressão seja um distribuição de probabilidade, não apenas um valor, altere a mônada e adicione uma construção probabilística como "virar uma moeda tendenciosa". Novamente, nenhuma das mudanças de código antigo. (Este é muito divertido; eu tenho fiz isso sozinho.)

Agora que eu lhe disse qual é a vantagem dos cálculos monádicos, é melhor lhe dizer a desvantagem suprema: Você só pode fazer um recurso interessante de cada vez. A razão é que, em geral, você não pode compor duas mônadas para fazer uma nova mônada. Isso é verdade não apenas em geral, mas em mônadas que você realmente gostaria de usar.

Se você está realmente interessado em fazer um intérprete modular, no qual você pode facilmente experimentar com diferentes Combinações dos recursos do idioma (em oposição a apenas recursos individuais), você precisa Monad Transformers. Há um ótimo artigo sobre Monad Transformers e Interpretadores Modulares Por Sheng Liang, Paul Hudak e Mark Jones. É uma ótima leitura; Eu recomendo muito.

Answer 2

Usar uma mônada torna o analisador/intérprete extensível. Este artigo de Philip Wadler leva algum tempo para ler, mas explora essa idéia em grande detalhe. Veja também Análise de Monadic em Haskell.