Я недавно обнаружил этот небольшой 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
только монада идентификационных данных. Это просто представлено для предоставления примера одноместного синтаксиса, или он имеет важный эффект?
Вот краткое изложение работы Фила Вадлера: Когда вы пишете интерпретатор в простом, "прямом" стиле, много кода должно измениться, когда вы добавляете новую возможность. Например, если вы добавляете исключения, вы должны проверить, не поднимается ли исключение в любом месте, где вы можете оценить выражение, даже если конструкция похожа на if или while или вызов функции, и поэтому не имеет никакого отношения к исключениям.
Если вы пишете интерпретатор в monadic стиле, вы можете добавить новую возможность, просто изменив monad. Обычно вы также добавляете несколько новых битов синтаксиса для поддержки функции, но остальной код не меняется. Таким образом, monadic style - это способ сделать интерпретатор модульным по отношению к языковым изменениям. Примеры:
Чтобы добавить исключения, измените monad в monad ошибки, добавьте новый синтаксис и код для throw
и catch
, и ни один из других ваших кодов не изменится.
Чтобы изменить язык так, чтобы значение выражения было распределение вероятностей, а не просто значение, измените monad, и добавьте вероятностную конструкцию типа "подбросьте монетку с предубеждением". Опять же, ни один из старых кодов не изменился. (Этот действительно забавный; я сделал это сам.)
Теперь, когда я рассказал вам, в чем преимущество монадских вычислений, я лучше расскажу вам о главном недостатке: вы можете делать только одну интересную функцию за раз . Причина в том, что в общем, нельзя составить две монады, чтобы сделать новую монаду. Это верно не только в целом, но и в отношении монад, которые Вы, возможно, действительно захотите использовать.
Если Вы действительно заинтересованы в создании модульного интерпретатора, в котором Вы можете легко экспериментировать с различными комбинациями языковых особенностей (в отличие от просто индивидуальных особенностей), Вам понадобятся трансформаторы монад. Есть отличная статья о Monad Transformers and Modular Interpreters от Шенг Лян, Пола Худака и Марка Джонса. Это отличное чтиво, я очень рекомендую.
Использование monad делает синтаксический анализатор/интерпретатор расширяемым. Эта статья Филиппа Вадлера занимает некоторое время, но рассматривает эту идею очень подробно. См. также Монадический парсинг в Хаскелле.
.