Возвращаясь к Неразмеченным Конечным Интерпретаторам с Dotty / Хабр

Неразмеченные Конечные Интепретаторы (Tagless Final interpreters — прим. пер.) — это альтернативный подход традиционным Алгебраическим Типам Данных (и обобщённым ADT), основанный на реализации паттерна "интерпретатор". Этот текст представляет "неразмеченный конечный" подход в Scala, и демонстрирует каким образом Dotty с его недавно добавленными типами неявных функций делает этот подход ещё более привлекательным. Все примеры кода — это прямое переложение их Haskell версий, представленных в Typed Tagless Final Interpreters: Lecture Notes (раздел 2).

Паттерн "интерпретатор" в последнее время привлекает всё больше внимания в сообществе Scala. Множество усилий было затрачено на борьбу с наиболее ярким недостатком решений, основанных на ADT/GADT: расширяемость. Для начала можно взглянуть на typeclass Inject из cats как на реализацию идей Data Type à la Carte. Библиотека Freek предоставляет средства для комбинирования более двух алгебр, используя украшения с задействованием аппарата операций на уровне типов. Решение, предложенное в работе Freer Monads, More Extensible Effects также ставит акцент на расширяемости, и вдохновлено набором небольших Scala-библиотек, таких как eff, emm и paperdoll. Неразмеченные конечные интерпретаторы подходят в некотором смысле с противоположной стороны, используя типы классов в своём непосредственном основании вместо более традиционных ADT/GADT. Они также поставляются с большим превосходством в расширяемости "из коробки" без каких-то явных опасностей.

Конспект углубляется в детали представления и сравнения подходов с использованием ADT/GADT и типов классов, обозначая первый как начальный и второй как конечный. С целью краткости этот текст посвящён преимущественно конечным интерпретаторам.

Введение

Мы будем работать с простыми математическими выражениями, похожими на те, что используются в калькуляторах. Наша задача состоит не только в вычислении подобных выражений, но также в их сериализации, десериализации и упрощении. С точки зрения ленивого инженера совершенно разумно представить предметную область с использованием (встроенного) предметно-ориентированного языка (domain specific language — прим. пер.): помимо всего прочего, это спасает нас от необходимости отслеживать возможно некорректные представления нашей предметной области — базовый язык программирования позаботится об этом за нас. Наша предметная область будет состоять только из целочисленных литералов, сложения и взятия с обратным знаком. Кодировка, которая возникла в Вашем сознании, возможно, выглядит так:

sealed trait IExp
final case class Lit(i: Int) extends IExp
final case class Neg(e: IExp) extends IExp
final case class Add(r: IExp, l: IExp) extends IExp

Математическое выражение 8 - (1 + 2), к примеру, может быть закодировано как значение типа IExp:

val fe: IExp = Add(Lit(8), Neg(Add(Lit(1), Lit(2))))

Пока что всё выглядит просто, так? Интерпретация fe как целого числа будет использовать рекурсивную функцию с типом IExp => Int, сериализация происходит с функцией IExp => Json, десериализация идёт в обратном направлении с Json => Option[IExp], и трансформации происходят через функции IExp => IExp.

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

trait Exp[T] {
  def lit(i: Int): T
  def neg(t: T): T
  def add(l: T, r: T): T
}

Как нам представить 8 - (1 + 2) с помощью Exp? Каким-то образом вроде:

def tf0[T](implicit e: Exp[T]): T =
  e.add(e.lit(8), e.neg(e.add(e.lit(1), e.lit(2))))

В Haskell (с соответсвующим расширением языка) tf0 может быть полиморфным значением. В Scala мы используем функцию с параметром типа T и ограничением (constraint — прим. пер.) implicit Exp[T]. Синтаксис можно упростить (к примеру) избавившись от e. используя вспомогательные функции:

object ExpSyntax {
  def lit[T](i: Int)    (implicit e: Exp[T]): T = e.lit(i)
  def neg[T](t: T)      (implicit e: Exp[T]): T = e.neg(t)
  def add[T](l: T, r: T)(implicit e: Exp[T]): T = e.add(l, r)
}
import ExpSyntax._ // Безопасно всегда иметь её в области видимости

def tf1[T: Exp]: T =
  add(lit(8), neg(add(lit(1), lit(2))))

В этот момент Вы, вероятно, задаётесь вопросом, "как нам написать интерпретатор для этой tf1?". Ответ прост: определяя реализацииExp!

implicit val evalExp: Exp[Int] = new Exp[Int] {
  def lit(i: Int): Int = i
  def neg(t: Int): Int = -t
  def add(l: Int, r: Int): Int = l + r
}

implicit val printExp: Exp[String] = new Exp[String] {
  def lit(i: Int): String = i.toString
  def neg(t: String): String = s"(-$t)"
  def add(l: String, r: String): String = s"($l + $r)"
}

Интерпретация производится через определение типов. Давайте посмотрим на tf1 как на Int:

scala> tf1[Int]
res0: Int = 5

А что насчёт tf1 как String?

scala> tf1[String]
res1: String = (8 + (-(1 + 2)))

Расширяемость

Что если мы решим дополнить наши математические выражения операцией произведения? В начальной (основанной на ADT) кодировке IExp, мы бы столкнулись с двумя обременительными альтернативами: обновить определения типа данных IExp в купе со всеми интерпретаторами, что мы до сих пор написали, или положиться на возведение значений IExp в абстрактные суммы типов (coproducts — прим. пер.) в стиле Data Type à la Carte. И имено в этом отношении, где конечный неразмеченный подход по настоящему проявляет себя, т.к. он может быть расширен ествественным образом без изменений (или ��аже повторной компиляции) написанного кода. Мы введём новый, совершенно независимый класс типов для операции произведения:

trait Mult[T] {
  def mul(l: T, r: T): T
}

object MultSyntax {
  def mul[T](l: T, r: T)(implicit e: Mult[T]): T = e.mul(l, r)
}
import MultSyntax._

Выражения, использующие умножение чисел требуют дополнительного ограничения Mult (дополнительного неявного (implicit — прим. пер.) аргумента Mult[T], вот и всё). Вот так мы определим tfm1 = 7 - 1 * 2 и tfm2 = 7 * (8 - (1 + 2)):

def tfm1[T: Exp : Mult] = add(lit(7), neg(mul(lit(1), lit(2))))
def tfm2[T: Exp : Mult] = mul(lit(7), tf1)

Если Вас не устраивает добавлять всюду : Exp : Mult, забегая вперёд, я скажу, что мы увидим в конце статьи: в Dotty это может быть вынесено в тип неявной функции ( (implicit-function-type — прим. пер.).

Чтобы интерпретировать эти новые выражения, мы должны предоставить реализации Mult для Int и String:

implicit val evalMult: Mult[Int] = new Mult[Int] {
  def mul(l: Int, r: Int): Int = l * r
}

implicit val printMult: Mult[String] = new Mult[String] {
  def mul(l: String, r: String): String = s"$l * $r"
}

Без какого либо дополнительного связывания реализации Exp и Mult автоматически комбинируются во время интепретации:

scala> tfm1[String]
res2: String = (7 + (-1 * 2))
scala> tfm1[Int]
res3: Int = 5
scala> tfm2[String]
res4: String = 7 * (8 + (-(1 + 2)))
scala> tfm2[Int]
res4: Int = 35

Десериализация

Продвинемся теперь к более сложной задаче десериализации. Целевой формат — это Json-подобная древовидная структура, определённая следующим образом:

sealed trait Tree
final case class Leaf(s: String) extends Tree
final case class Node(s: String, ts: List[Tree]) extends Tree

Преобразование выражений в этот Json-подобный формат не сложнее сериализации в String. В зависимости от того, где определены реализации Exp и Mult, их можно сгруппировать вместе:

implicit val toTree: Exp[Tree] with Mult[Tree] = new Exp[Tree] with Mult[Tree] {
  def lit(i: Int): Tree = Node("Lit", List(Leaf(i.toString)))
  def neg(t: Tree): Tree = Node("Neg", List(t))
  def add(l: Tree, r: Tree): Tree = Node("Add", List(l , r))
  def mul(l: Tree, r: Tree): Tree = Node("Mult", List(l , r))
}

scala> val tf1Tree = tf1[Tree]
tf1Tree: Tree = Node(Add,List(Node(Lit,List(Leaf(8))), Node(Neg,List(Node(Add,List(Node(Lit,List(Leaf(1))), Node(Lit,List(Leaf(2)))))))))

Для десериализации нам необходимо описать функцию fromTree для преобразования Json-подобных Tree в его конечную кодировку. Учитывая это, наши конечно закодированные значения — это функции типа [T] => Exp[T] => T (в Dotty это синтаксис для лямбда-функции типов ({type L[T] = Exp[T] => T})#L), нашей первой догадкой может быть определение fromTree как def fromTree[T](t: Tree)(implicit e: Exp[T]): Either[ErrMsg, T]:

type ErrMsg = String

def readInt(s: String): Either[ErrMsg, Int] = {
  import scala.util.{Try, Success, Failure}
  Try(s.toInt) match {
    case Success(i) => Right(i)
    case Failure(f) => Left(f.toString)
  }
}

def fromTree[T](t: Tree)(implicit e: Exp[T]): Either[ErrMsg, T] =
  t match {
    case Node("Lit", List(Leaf(n))) =>
      readInt(n).right.map(e.lit)

    case Node("Neg", List(t)) =>
      fromTree(t).right.map(e.neg)

    case Node("Add", List(l , r)) =>
      for(lt <- fromTree(l).right; rt <- fromTree(r).right)
      yield e.add(lt, rt)

    case _ => Left(s"Дерево некорректно $t")
  }

Это сработает, но так как T и Exp[T] должны быть полностью определены при вызове fromTree, полиморфизм утерян и результат fromTree может иметь единственную интерпретацию. Мы обойдём эту проблему, обернув результат, используя следующий подход:

trait Wrapped {
  def value[T](implicit e: Exp[T]): T
}

Конспект далее предлагает переписать fromTree с использованием новой сигнатуры: def fromTree(t: Tree): Either[ErrMsg, Wrapped], но, как я полагаю, они упустили из виду, что мы можем получить тот же результат определив реализацию Exp[Wrapped] и используя наш изначальный код для fromTree:

implicit val wrappingExp: Exp[Wrapped] = new Exp[Wrapped] {
  def lit(i: Int) = new Wrapped {
    def value[T](implicit e: Exp[T]): T = e.lit(i)
  }
  def neg(t: Wrapped) = new Wrapped {
    def value[T](implicit e: Exp[T]): T = e.neg(t.value)
  }
  def add(l: Wrapped, r: Wrapped) = new Wrapped {
    def value[T](implicit e: Exp[T]): T = e.add(l.value, r.value)
  }
}

Этого достаточно, чтобы получить полиморфизм первого класса

scala> fromTree[Wrapped](tf1Tree) match {
     |  case Left(err) =>
     |    println(err)
     |
     |  case Right(t) =>
     |    println(t.value[Int])
     |    println(t.value[String])
     |    println
     |}
5
(8 + (-(1 + 2)))

Но мы справились только с половиной задачи: нашему десериализатору всё ещё не хватает расширяемости. Для того, чтобы разрешить добавлять умножение пост-фактум, fromTree должна быть переписана в открыто-рекурсивном стиле. Это ещё одно из страшных имён для очень простой идеи: мы можем переписать все наши рекурсивные вызовы fromTree через дополнительный параметр recur:

// Заметьте, что `recur` и `fromTree _` одного типа!
def fromTreeExt[T]
  (recur: => (Tree => Either[ErrMsg, T]))
  (implicit e: Exp[T])
  : Tree => Either[ErrMsg, T] = {
    val e = implicitly[Exp[T]]
    tree => tree match {
      case Node("Lit", List(Leaf(n))) =>
        readInt(n).right.map(e.lit)

      case Node("Neg", List(t)) =>
        recur(t).right.map(e.neg)

      case Node("Add", List(l , r)) =>
        for(lt <- recur(l).right; rt <- recur(r).right)
        yield e.add(lt, rt)

      case t => Left(s"Дерево некорректно $t")
    }
  }

Рекурсия затем стягивается, используя оператор неподвижной точки (fix point operator — "прим. пер."):

def fix[A](f: (=> A) => A): A = f(fix(f))

def fromTree2[T: Exp](t: Tree): Either[ErrMsg, T] = fix(fromTreeExt[T] _)(t)

Таким образом, становится возможным определить десериализатор оператора произведения независимо, и "затянуть узел" ещё раз::

def fromTreeExt2[T]
  (recur: => (Tree => Either[ErrMsg, T]))
  (implicit e: Exp[T], m: Mult[T])
  : Tree => Either[ErrMsg, T] = {
    case Node("Mult", List(l , r)) =>
      for(lt <- recur(l).right; rt <- recur(r).right)
      yield m.mul(lt, rt)

    case t => fromTreeExt(recur).apply(t)
  }

def fromTree3[T: Exp : Mult](t: Tree): Either[ErrMsg, T] = fix(fromTreeExt2[T] _)(t)

Теперь мы можем протестировать нашу сериализацию и десериализацию для любого e, к примеру, используя:

assert(fromTreeN[String](e[Tree]) == Right(e[String]))

Заметьте, что в Scala эта реализация стэко-небезопасна. Нам понадобится добавить trampolining, чтобы использовать этот трюк с рекурсией для больших структур данных.

Преобразование

Мы увидели как преобразовывать наши математические выражения в различные другие представления, т.е. интерпретацию; как строить наши математические выражения из другого представления: десериализацию; но что насчёт преобразования математического выражения в другое математическое выражение?

Рассмотрим преобразование, которое опустит унарный минус в самый низ, к литералам, так чтобы 8 - (1 + 2) стало 8 + ((-1) + (-2)). Задача звучит просто для на��альной (основанной на ADT) кодировки, сработала бы простая функция IExp => IExp

def pushNeg(e: IExp): IExp = e match {
  case Lit(_) => e
  case Neg(Lit(_)) => e
  case Neg(Neg(n)) => n
  case Neg(Add(l, r)) => Add(pushNeg(Neg(l)), pushNeg(Neg(r)))
  case Add(l, r) => Add(pushNeg(l), pushNeg(r))
}

Это выглядит невозможным в конечной кодировке. Сопоставление с образцом (pattern matching — прим. пер.) очень удобно для преобразований в определённыом контексте, как нам добиться аналогичного удобства внутри реализации Exp? Уловка в том, что вместо обработки Exp[T] как мы поступали прежде, работать с Exp[Ctx => T] в подходящем контексте. В данном случае контекст довольно прост: всё, что нам нужно знать — это нужно или нет изменить знак у текущего узла:

sealed trait NCtx
final case object PosCtx extends NCtx
final case object NegCtx extends NCtx

Преобразование выражается как Exp[NCtx => T]:

implicit def negDownExp[T](implicit e: Exp[T]): Exp[NCtx => T] = new Exp[NCtx => T] {
  def lit(i: Int): NCtx => T = {
    case PosCtx => e.lit(i)
    case NegCtx => e.neg(e.lit(i))
  }

  def neg(x: NCtx => T): NCtx => T = {
    case PosCtx => x(NegCtx)
    case NegCtx => x(PosCtx)
  }

  def add(l: NCtx => T, r: NCtx => T): NCtx => T =
    c => e.add(l(c), r(c))
}

Чтобы применить трансформацию, нужно сначала преобразовать выражение в фунцкию NCtx => T, а затем вызвать её с начальным контекстом:

scala> tf1[NCtx => String].apply(PosCtx)
(8 + ((-1) + (-2)))

Начальный контект также можно вынести в фунцкию:

scala> def pushNeg[T](e: NCtx => T): T = e(PosCtx)
pushNeg: [T](e: NCtx => T)T

scala> pushNeg(tf1[NCtx => String])
(8 + ((-1) + (-2)))

К несчастью, механизм вывода типов в scalac в этом случае требует явно определя��ь внутренний параметр типа, что может выглядеть довольно некрасиво при композиции нескольких трансформаций: pushNeg(pushNeg(pushNeg(tf1[NCtx => NCtx => NCtx => String]))). Улучшения в механизме вывода типов в Dotty делают возможным писать просто pushNeg(pushNeg(pushNeg(tf1))): String, аналогично тому, как бы Вы написали в Haskell. Смотрите Dotty and types: the story so far для введения в механизм вывода типов в Dotty.

Это преобразование может быть естественным образом расширено для операции произведения с помощью определения дополнительной реализации Mult[NCtx => T]:

implicit def negDownMult[T](implicit e: Mult[T]): Mult[NCtx => T] = new Mult[NCtx => T] {
  def mul(l: NCtx => T, r: NCtx => T): NCtx => T = {
    case PosCtx => e.mul(l(PosCtx), r(PosCtx))
    case NegCtx => e.mul(l(PosCtx), r(NegCtx))
  }
}

scala> pushNeg(tfm1[NCtx => String])
(7 + 1 * (-2))

scala> pushNeg(tfm2[NCtx => String])
7 * (8 + ((-1) + (-2)))

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

// Из кодировки классом типов в кодировку ADT
implicit def initialize: Exp[IExp] = new Exp[IExp] {
  def lit(i: Int): IExp = Lit(i)
  def neg(t: IExp): IExp = Neg(t)
  def add(l: IExp, r: IExp): IExp = Add(l, r)
}

// Из кодировки ADT в кодировку классом типов
def finalize[T](i: IExp)(implicit e: Exp[T]): T = i match {
  case Lit(l) => e.lit(l)
  case Neg(n) => e.neg(finalize[T](n))
  case Add(l, r) => e.add(finalize[T](l), finalize[T](r))
}

Объединение ограничений на классы типов с помощью типов неявных функций

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

trait Function1[A, B] {
  def apply(a: A): B
}

В компиляторе реализован синтаксический сахар, преобразующий типы A => B в Function1[A, B] и позволяет пользователям лаконично определять значения-функции. Неявные функции аналогичны: implicit A => B становится корректным типом, раскрывающимся в ImplicitFunction1[A, B]:

trait ImplicitFunction1[A, B] {
  def apply(implicit a: A): B
}

Определение функции, возвращающей тип неявной функции получает дополнительное преимущетство в дополнительном раскрытии, автоматически помещающим неявные параметры в область видимости:

def f: implicit Ctx => Unit = ???

Раскрывается в:

def f: implicit Ctx => Unit = { implicit $e1: Ctx => ???: Unit }

Синтаксический сахар, возможно, и не выглядит очень полезным в этом простом примере, но с таким синонимом типа уже становится более интересным:

type Contextualized[T] = implicit Ctx => T

def f: Contextualized[Unit] = ???

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

type Constrained[T] = implicit (TC1[T], TC2[T], TC3[T]) => T

def f: Constrained[Int] = ???

Раскрывается в:

def f: Constrained[Int] = { ($e1: TC1[Int], $e2: TC2[Int], $e3: TC3[Int]) =>
  implicit $e4: TC1[Int] = $e1
  implicit $e5: TC1[Int] = $e2
  implicit $e6: TC1[Int] = $e3
  ???: Int
}

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

type Ring[T] = implicit (Exp[T], Mult[T]) => T

def tfm1[T]: Ring[T] = add(lit(7), neg(mul(lit(1), lit(2))))
def tfm2[T]: Ring[T] = mul(lit(7), tf1)

Так завершается наше возвращение к Неразмеченным Конечным интерпретаторам (смотри здесь все (Scala 2.11) фрагменты кода из этой статьи)!

Если вам хочется узнать больше о Неразмеченных Конечных интерпретаторах, я настоятельно рекомендую продолжить изучение разделов 3 и 4 конспекта для кодировки просто типизированного лямбда-исчисления.

Возвращаясь к Неразмеченным Конечным Интерпретаторам с Dotty

Введение

Расширяемость

Десериализация

Преобразование

Объединение ограничений на классы типов с помощью типов неявных функций

Публикации

Ближайшие события