Che senso ha usare le Monade in un interprete?

Question

Recentemente ho scoperto questo piccolo scala example chiamato interprete semplice utilizzando monadi:

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

cosa è l'uso/vantaggio di calcoli monadici qui? In effetti, lo M non è altro che una monade di identità. È appena introdotto per dare un esempio di sintassi monadica o ha un effetto importante?

Answer 1

Ecco un breve riassunto del documento di Phil Wadler: Quando si scrive un interprete in stile diretto, "diretto", un sacco di codice deve cambiare quando si aggiunge una nuova funzione. Ad esempio, se si aggiungono eccezioni, è necessario controllare se viene sollevata un'eccezione in qualsiasi posizione è possibile valutare un'espressione, anche se il costrutto è come se o mentre o chiamata di funzione e quindi non ha nulla a che fare con le eccezioni .

Se si scrive l'interprete in stile monadico, è possibile aggiungere una nuova funzione semplicemente cambiando la monade. Di solito aggiungi anche alcuni nuovi bit di sintassi per supportare la funzione, ma nessuno del resto del codice cambia. Quindi lo stile monadico è un modo di fare un interprete che è modulare rispetto ai cambiamenti linguistici.

Esempi:

• Per aggiungere eccezioni, cambiare la monade per la monade errore, aggiungere nuova sintassi e il codice per throw e catch, e nessuno dei tuoi altri modifiche al codice.

• Per cambiare la lingua in modo che il valore di un'espressione è una distribuzione di probabilità , non solo un valore, modificare la monade, e aggiungere un costrutto probabilistico come "lanciare una moneta sbilanciata". Di nuovo, nessuno del vecchio codice cambia. (Questo è davvero divertente, ho done it myself.)

Ora che vi ho detto quello che il vantaggio di calcoli monadici, è meglio vi dico lo svantaggio suprema: si può fare solo una caratteristica interessante alla volta. Il motivo è che, in generale, non puoi comporre due monadi per creare una nuova monade. Questo è vero non solo in generale, ma delle monadi che potresti davvero voler usare.

Se siete veramente interessati a fare un interprete di modulare, in cui si può facilmente sperimentare diverse combinazioni delle caratteristiche del linguaggio (al contrario di solo le caratteristiche individuali), è necessario trasformatori monade. C'è un grande articolo su Monad Transformers and Modular Interpreters di Sheng Liang, Paul Hudak e Mark Jones. È una buona lettura; Lo consiglio vivamente.

Answer 2

L'utilizzo di una monade rende il parser/interprete estendibile. This paper by Philip Wadler richiede un po 'di tempo per leggere, ma esplora questa idea in grande dettaglio. Vedi anche Monadic Parsing in Haskell.