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

Паттерн "интерпретатор" в последнее время привлекает всё больше внимания в сообществе Scala. Множество усилий было затрачено на борьбу с наиболее ярким недостатком решений, основанных на ADT/GADT: расширяемость. Для начала можно взглянуть на typeclass Inject из cats как на реализацию идей Data Type a 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 a 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 конспекта для кодировки просто типизированного лямбда-исчисления.