¿De qué sirve usar mónadas en un intérprete?

Question

Recientemente he descubierto este pequeño scala example llamada intérprete simple 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)) 
    } 
} 

Cuál es el uso/ventaja de cálculos monádicos aquí? De hecho, el M no es más que una mónada de identidad. ¿Se acaba de presentar para dar un ejemplo de sintaxis monádica o tiene un efecto importante?

Answer 1

Aquí hay un pequeño resumen del artículo de Phil Wadler: Cuando escribe un intérprete en estilo "directo" directo, una gran cantidad de código tiene que cambiar cuando agrega una nueva función. Por ejemplo, si agrega excepciones, debe verificar si se produce una excepción en cualquier lugar donde pueda evaluar una expresión, incluso si la construcción es como si o mientras o función de llamada, y por lo tanto no tiene nada que ver con excepciones .

Si escribe el intérprete en estilo monádico, puede agregar una nueva función simplemente cambiando la mónada. Por lo general, también agrega algunos nuevos bits de sintaxis para admitir la función, pero no cambia el resto del código. Entonces, el estilo monádico es una forma de hacer un intérprete que sea modular con respecto a los cambios de lenguaje.

Ejemplos:

• Para agregar excepciones, cambie la mónada a la mónada error, añada una nueva sintaxis y el código de throw y catch, y ninguno de sus otros cambios en el código.

• Para cambiar el idioma de manera que el valor de una expresión es una distribución de probabilidad , no sólo un valor, cambie la mónada, y añadir un constructo probabilístico como "lanzar una moneda sesgada". De nuevo, ninguno de los códigos antiguos cambia. (Esto es muy divertido, he done it myself.)

Ahora que te he dicho lo que la ventaja de los cálculos monádicos, será mejor que le diga la desventaja suprema: sólo se puede hacer una característica interesante en un momento. La razón es que, en general, no puedes componer dos mónadas para hacer una nueva mónada. Esto es cierto no solo en general, sino también de las mónadas que realmente te gustaría usar.

Si usted está realmente interesado en la fabricación de un intérprete modular, en el que se puede experimentar fácilmente con diferentes combinaciones de las características del lenguaje (en lugar de sólo las características individuales), debe transformadores monad. Hay un excelente artículo en Monad Transformers and Modular Interpreters de Sheng Liang, Paul Hudak y Mark Jones. Es una gran lectura; Lo recomiendo mucho

Answer 2

El uso de una mónada hace que el analizador/intérprete sea extensible. This paper by Philip Wadler toma algo de tiempo para leer, pero explora esta idea con gran detalle. Consulte también Monadic Parsing in Haskell.