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

Недавно я обнаружил этот маленький scala example, называемый Simple interpreter, использующий 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))
  }
}

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

Ответ 1

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

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

Примеры:

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

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

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

Ответ 1

Ответ 2