Какой смысл того, чтобы использовать монады в интерпретаторе?

Я недавно обнаружил этот небольшой scala пример под названием Простой интерпретатор с помощью монад:

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() = ""
  }

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

Каково использование/преимущество одноместных вычислений здесь? На самом деле, M только монада идентификационных данных. Это просто представлено для предоставления примера одноместного синтаксиса, или он имеет важный эффект?

10
задан jcubic 20 February 2011 в 13:22
поделиться

2 ответа

Вот краткое изложение работы Фила Вадлера: Когда вы пишете интерпретатор в простом, "прямом" стиле, много кода должно измениться, когда вы добавляете новую возможность. Например, если вы добавляете исключения, вы должны проверить, не поднимается ли исключение в любом месте, где вы можете оценить выражение, даже если конструкция похожа на if или while или вызов функции, и поэтому не имеет никакого отношения к исключениям.

Если вы пишете интерпретатор в monadic стиле, вы можете добавить новую возможность, просто изменив monad. Обычно вы также добавляете несколько новых битов синтаксиса для поддержки функции, но остальной код не меняется. Таким образом, monadic style - это способ сделать интерпретатор модульным по отношению к языковым изменениям. Примеры:

  • Чтобы добавить исключения, измените monad в monad ошибки, добавьте новый синтаксис и код для throw и catch, и ни один из других ваших кодов не изменится.

  • Чтобы изменить язык так, чтобы значение выражения было распределение вероятностей, а не просто значение, измените monad, и добавьте вероятностную конструкцию типа "подбросьте монетку с предубеждением". Опять же, ни один из старых кодов не изменился. (Этот действительно забавный; я сделал это сам.)

Теперь, когда я рассказал вам, в чем преимущество монадских вычислений, я лучше расскажу вам о главном недостатке: вы можете делать только одну интересную функцию за раз . Причина в том, что в общем, нельзя составить две монады, чтобы сделать новую монаду. Это верно не только в целом, но и в отношении монад, которые Вы, возможно, действительно захотите использовать.

Если Вы действительно заинтересованы в создании модульного интерпретатора, в котором Вы можете легко экспериментировать с различными комбинациями языковых особенностей (в отличие от просто индивидуальных особенностей), Вам понадобятся трансформаторы монад. Есть отличная статья о Monad Transformers and Modular Interpreters от Шенг Лян, Пола Худака и Марка Джонса. Это отличное чтиво, я очень рекомендую.

19
ответ дан 3 December 2019 в 17:20
поделиться

Использование monad делает синтаксический анализатор/интерпретатор расширяемым. Эта статья Филиппа Вадлера занимает некоторое время, но рассматривает эту идею очень подробно. См. также Монадический парсинг в Хаскелле.

.
4
ответ дан 3 December 2019 в 17:20
поделиться
Другие вопросы по тегам:

Похожие вопросы: