Was ist der Sinn der Verwendung von Monaden in einem Interpreter?

Question

Vor kurzem entdeckte ich dieses kleine Scala-Beispiel genannt. Einfacher Interpreter mit Monaden :

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

Was ist der Nutzen/Vorteil von monadischen Berechnungen hier? In der Tat, die M ist nichts anderes als eine Identitätsmonade. Wurde dies nur eingeführt, um ein Beispiel für die monadische Syntax zu geben, oder hat es eine wichtige Wirkung?

Answer 1

Hier ist eine kleine Zusammenfassung des Papiers von Phil Wadler: Wenn man einen Interpreter in einem einfachen, "direkten" Stil schreibt, muss eine Menge Code geändert werden, wenn man eine neue Funktion hinzufügt. Wenn man zum Beispiel Ausnahmen hinzufügt, muss man an jeder Stelle, an der man einen Ausdruck auswertet, prüfen, ob eine Ausnahme ausgelöst wird, selbst wenn das Konstrukt wie folgt lautet wenn o während oder Funktionsaufruf, und hat daher nichts mit Ausnahmen zu tun.

Wenn Sie den Interpreter im monadischen Stil schreiben, können Sie eine neue Funktion hinzufügen, indem Sie einfach die Monade ändern. Normalerweise fügt man auch ein paar neue Syntaxelemente hinzu, um die Funktion zu unterstützen, aber der Rest des Codes ändert sich nicht. Der monadische Stil ist also eine Möglichkeit, einen Interpreter zu erstellen, der im Hinblick auf Sprachänderungen modular ist.

Beispiele:

• Um Ausnahmen hinzuzufügen, ändern Sie die Monade in die Fehlermonade, fügen eine neue Syntax und Code für throw y catch und keine der anderen Codeänderungen.

• Um die Sprache so zu ändern, dass der Wert eines Ausdrucks ein Wahrscheinlichkeitsverteilung , nicht nur einen Wert, ändern Sie die Monade, und fügen Sie ein probabilistisches Konstrukt wie "Werfen Sie eine voreingenommene Münze" hinzu. Auch hier ändert sich nichts am alten Code. (Das hier macht wirklich Spaß; ich habe Ich habe es selbst getan .)

Nachdem ich Ihnen nun die Vorteile monadischer Berechnungen genannt habe, sollte ich Ihnen auch den größten Nachteil nennen: Sie können immer nur ein interessantes Feature zur gleichen Zeit machen . Der Grund dafür ist, dass man im Allgemeinen nicht zwei Monaden zusammensetzen kann, um eine neue Monade zu bilden. Das gilt nicht nur allgemein, sondern auch für Monaden, die Sie vielleicht wirklich gerne verwenden würden.

Wenn Sie wirklich daran interessiert sind, einen modularen Interpreter zu entwickeln, mit dem Sie leicht mit verschiedenen Kombinationen von Sprachmerkmalen (im Gegensatz zu nur einzelnen Merkmalen), müssen Sie Monaden-Transformatoren . Es gibt ein großartiges Papier über Monadentransformatoren und modulare Interpreter von Sheng Liang, Paul Hudak und Mark Jones. Es ist eine großartige Lektüre, die ich sehr empfehle.

Answer 2

Die Verwendung einer Monade macht den Parser/Dolmetscher erweiterbar. Dieses Papier von Philip Wadler braucht einige Zeit, um gelesen zu werden, geht aber sehr ausführlich auf diese Idee ein. Siehe auch Monadisches Parsing in Haskell .