在翻译中使用monads有什么意义？ [英] What's the point of using monads in an interpreter?

问题描述

我最近发现了这个小 scala示例，名为使用monads的简单解释器：

  object simpleInterpreter {
 
 case class M [A]（value：A ）{b $ b 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 
案例类别Lam（x：Name，body：Term）延伸Term 
案例类别App（fun：Term，arg：Term）延伸Term 
 
特征值
案例对象错误扩展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> 
 
 
类型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）匹配{
 case Pair（Num（m），Num（n））=> unitM（Num（m + n））
 case _ =>单位M（错误）
} 
 
 def apply（a：Value，b：Value）：M [Value] =匹配{
 case Fun（k）=> k（b）
 case _ =>单位M（错误）
} 
 
 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））
产出c 
 case Lam（x，t）=>单位M（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））
 （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 （1），Con（2））
 
 def main（args：Array [String]）{
 println（test（term0））
 println（test（term1）） 
} 
} 
  

单程计算在这里有什么用处/优点？事实上， M 不过是一个身份monad。这只是介绍给一个monadic语法的例子，或者它有一个重要的影响？

解决方案

这是一个小小的摘要菲尔Wadler的论文：
当您直接编写解释器时，直接样式，添加新功能时必须更改大量代码。例如，如果添加异常，则必须检查是否有可能评估表达式的任何地方出现异常，即使该结构像 if 或 或函数调用，所以与异常无关。

如果您以一元风格编写解释器，则可以通过更改monad来添加新功能。您通常还会添加一些新的语法来支持该功能，但其余代码都不会更改。所以一元风格是一种使语言变化模块化的解释器。

示例：

• 要添加例外，请将monad更改为错误monad，为 throw 和 catch 添加新的语法和代码，并且您的其他代码都不会更改。要改变语言，以便表达式的值是一个概率分布，而不仅仅是一个值，改变monad，并添加像翻转有偏见的硬币这样的概率结构。再次，旧代码没有任何变化。 （这个很有趣，我自己自己做。 ）

现在我已经告诉过你单程计算的优点了，我最好告诉你至尊劣势：一次只能做一个有趣的功能。原因是，一般来说，你不能组成两个monad来创建一个新的monad。这不仅仅是一般情况，而且还有你可能真正喜欢使用的monad。

如果你真的对制作模块化解释器感兴趣，你可以很容易地试验语言特征的不同组合（而不仅仅是个别特征），你需要 monad变形金刚。 Monad变形金刚和模块化口译员

I recently discovered this little scala example called Simple interpreter using monads:

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

What's the use/advantage of monadic computations here? In fact, the M is nothing but an identity monad. Is this just introduced to give an example of monadic syntax or does it have an important effect?

解决方案

Here's a little summary of Phil Wadler's paper: When you write an interpreter in straightforward, "direct" style, a lot of code has to change when you add a new feature. For example, if you add exceptions, you have to check if an exception is raised any place you might evaluate an expression, even if the construct is like if or while or function call, and so has nothing to do with exceptions.

If you write the interpreter in monadic style, you can add a new feature just by changing the monad. You usually also add a few new bits of syntax to support the feature, but none of the rest of the code changes. So monadic style is a way of making an interpreter that is modular with respect to language changes.

Examples:

• To add exceptions, change the monad to the error monad, add new syntax and code for throw and catch, and none of your other code changes.

• To change the language so that the value of an expression is a probability distribution, not just a value, change the monad, and add a probabilistic construct like "flip a biased coin". Again, none of the old code changes. (This one is really fun; I've done it myself.)

Now that I've told you what the advantage of monadic computations, I'd better tell you the supreme disadvantage: you can only do one interesting feature at a time. The reason is that in general, you cannot compose two monads to make a new monad. This is true not just in general, but of monads you might really like to use.

If you're really interested in making a modular interpreter, in which you can easily experiment with different combinations of language features (as opposed to just individual features), you need monad transformers. There's a great paper on Monad Transformers and Modular Interpreters by Sheng Liang, Paul Hudak, and Mark Jones. It's a great read; I recommend it highly.

这篇关于在翻译中使用monads有什么意义？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！