Quel est le point d'utiliser des monades dans un interprète?

Question

J'ai récemment découvert ce petit scala example appelé interprète simple à l'aide monades:

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

Quelle est l'utilisation/avantage des calculs monades ici? En fait, le M n'est rien d'autre qu'une monade d'identité. Est-ce que cela vient d'être présenté pour donner un exemple de syntaxe monadique ou a-t-il un effet important?

Answer 1

Voici un petit résumé de l'article de Phil Wadler: Lorsque vous écrivez un interpréteur dans un style simple, "direct", beaucoup de code doit changer lorsque vous ajoutez une nouvelle fonctionnalité. Par exemple, si vous ajoutez des exceptions, vous devez vérifier si une exception est déclenchée à un endroit où vous pourriez évaluer une expression, même si la construction est si ou ou ou appel de fonction, et n'a donc rien à voir avec des exceptions .

Si vous écrivez l'interpréteur dans un style monadique, vous pouvez ajouter une nouvelle fonction en changeant simplement la monade. Vous ajoutez également généralement quelques nouveaux bits de syntaxe pour prendre en charge la fonctionnalité, mais aucun des autres éléments du code ne change. Le style monadique est donc une façon de rendre un interprète modulaire par rapport aux changements de langage.

Exemples:

• Pour ajouter des exceptions, modifiez la monade à la monade d'erreur, ajouter une nouvelle syntaxe et code pour throw et catch, et aucun de vos autres modifications du code.

• Pour changer la langue de sorte que la valeur d'une expression est une distribution de probabilité , non seulement une valeur, modifiez la monade, et ajouter une construction probabiliste comme « lancer une pièce biaisée ». Encore une fois, aucun de l'ancien code ne change. (Celui-ci est vraiment amusant, j'ai done it myself.)

Maintenant que je vous ai dit ce que l'avantage des calculs monades, je ferais mieux de vous dire l'inconvénient suprême: vous ne pouvez faire un caractéristique intéressante à la fois. La raison en est qu'en général, vous ne pouvez pas composer deux monades pour faire une nouvelle monade. C'est vrai non seulement en général, mais aussi des monades que vous aimeriez vraiment utiliser.

Si vous êtes vraiment intéressé à faire un interprète modulaire, dans lequel vous pouvez facilement expérimenter avec différentes combinaisons des caractéristiques linguistiques (par opposition à quelques caractéristiques individuelles), vous avez besoin transformateurs monade. Sheng Liang, Paul Hudak et Mark Jones ont écrit un excellent article sur Monad Transformers and Modular Interpreters. C'est une bonne lecture; Je le recommande fortement.

Answer 2

L'utilisation d'une monade rend l'analyseur/interpréteur extensible. This paper by Philip Wadler prend du temps à lire, mais explore cette idée dans les moindres détails. Voir aussi Monadic Parsing in Haskell.