Блог Scala Функ. программирование Классы типов Алгоритмы Библиотеки Упражнения Ресурсы

Type Class Derivation

Type class derivation - это способ автоматического создания экземпляров given классов типов, которые удовлетворяют некоторым простым условиям. Класс типов в этом смысле — это любой trait или класс с параметром типа, определяющим тип, над которым выполняется операция. Общие примеры: Eq, Ordering или Show. Пример, для следующего алгебраического типа данных (ADT) Tree:

enum Tree[T] derives Eq, Ordering, Show:
  case Branch(left: Tree[T], right: Tree[T])
  case Leaf(elem: T)

Предложение derives создает следующие экземпляры given для классов типов Eq, Ordering и Show в сопутствующем объекте Tree:

given [T: Eq]       : Eq[Tree[T]]    = Eq.derived
given [T: Ordering] : Ordering[Tree] = Ordering.derived
given [T: Show]     : Show[Tree]     = Show.derived

Говорится, что Tree - это производный тип (deriving type), а экземпляры Eq, Ordering и Show являются производными экземплярами (derived instances).

Типы вспомогательных derives предложений

Все типы данных могут содержать предложение derives. В этом документе основное внимание уделяется типам данных, для которых также доступен given экземпляр класса типа Mirror. Экземпляры класса типа Mirror автоматически генерируются компилятором для,

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

sealed trait Mirror:

  /** the type being mirrored */
  type MirroredType

  /** the type of the elements of the mirrored type */
  type MirroredElemTypes

  /** The mirrored *-type */
  type MirroredMonoType

  /** The name of the type */
  type MirroredLabel <: String

  /** The names of the elements of the type */
  type MirroredElemLabels <: Tuple

object Mirror:

  /** The Mirror for a product type */
  trait Product extends Mirror:

    /** Create a new instance of type `T` with elements
     *  taken from product `p`.
     */
    def fromProduct(p: scala.Product): MirroredMonoType

  trait Sum extends Mirror:

    /** The ordinal number of the case class of `x`.
     *  For enums, `ordinal(x) == x.ordinal`
     */
    def ordinal(x: MirroredMonoType): Int

end Mirror

Типы продуктов (т.е. case классы и case объекты, а также enum case) имеют зеркала, которые являются подтипами Mirror.Product. Типы суммы (т.е. закрытый (sealed) класс или trait-ы с дочерними продуктами и перечисления) имеют зеркала, которые являются подтипами Mirror.Sum.

Для Tree ADT, описанного выше, следующие экземпляры Mirror будут автоматически предоставлены компилятором:

// Mirror for Tree
new Mirror.Sum:
  type MirroredType = Tree
  type MirroredElemTypes[T] = (Branch[T], Leaf[T])
  type MirroredMonoType = Tree[_]
  type MirroredLabel = "Tree"
  type MirroredElemLabels = ("Branch", "Leaf")

  def ordinal(x: MirroredMonoType): Int = x match
    case _: Branch[_] => 0
    case _: Leaf[_] => 1

// Mirror for Branch
new Mirror.Product:
  type MirroredType = Branch
  type MirroredElemTypes[T] = (Tree[T], Tree[T])
  type MirroredMonoType = Branch[_]
  type MirroredLabel = "Branch"
  type MirroredElemLabels = ("left", "right")

  def fromProduct(p: Product): MirroredMonoType =
    new Branch(...)

// Mirror for Leaf
new Mirror.Product:
  type MirroredType = Leaf
  type MirroredElemTypes[T] = Tuple1[T]
  type MirroredMonoType = Leaf[_]
  type MirroredLabel = "Leaf"
  type MirroredElemLabels = Tuple1["elem"]

  def fromProduct(p: Product): MirroredMonoType =
    new Leaf(...)

Обратите внимание на следующие свойства типов Mirror:

Классы типов, поддерживающие автоматическую деривиацию

Trait или класс могут появиться в предложении derives, если их сопутствующий объект определяет метод с именем derived. Сигнатура и реализация derived метода для класса типов TC[_] произвольны, но обычно имеют следующую форму:

import scala.deriving.Mirror

def derived[T](using Mirror.Of[T]): TC[T] = ...

То есть метод derived принимает контекстный параметр типа Mirror (некоторого подтипа), который определяет форму производного типа T, и вычисляет реализацию класса типа в соответствии с этой формой. Это все, что поставщик ADT с предложением derives должен знать о порождении экземпляра класса типов.

Обратите внимание, что методы derived могут косвенно иметь параметры контекста Mirror (например, иметь аргумент контекста, который, в свою очередь, имеет параметр контекста Mirror, или вообще не иметь (например, они могут использовать какой-то совершенно другой механизм, предоставленный пользователем, например, с помощью макросов Scala 3 или runtime reflection)). Ожидается, что наиболее распространенными будут (прямые или непрямые) реализации Mirror.

Авторы классов типов, скорее всего, будут использовать производные библиотеки более высокого уровня или универсальные библиотеки программирования для реализации методов derived. Пример того, как метод derived может быть реализован с использованием только средств низкого уровня, описанных выше, и общих возможностей метапрограммирования Scala 3, приведен ниже. Не предполагается, что авторы классов типов обычно будут реализовывать метод derived таким образом, однако это пошаговое руководство можно рассматривать как руководство для авторов библиотек деривации более высокого уровня (для полностью проработанного примера о такой библиотеке см. Shapeless 3).

Как написать метод derived класса типов, используя низкоуровневые механизмы

Низкоуровневый метод, который будет использоваться для реализации метода derived класса типа в этом примере, использует три новые конструкции уровня типа в Scala 3: встроенные методы (inline methods), встроенные совпадения (inline matches) и неявный поиск через summonInline или summonFrom. Учитывая это определение класса типа Eq:

trait Eq[T]:
  def eqv(x: T, y: T): Boolean

нужно реализовать метод Eq.derived для сопутствующего объекта Eq, который создает экземпляр given для Eq[T] заданного Mirror[T]. Вот возможная реализация:

import scala.deriving.Mirror

inline given derived[T](using m: Mirror.Of[T]): Eq[T] =
  val elemInstances = summonAll[m.MirroredElemTypes]           // (1)
  inline m match                                               // (2)
    case s: Mirror.SumOf[T]     => eqSum(s, elemInstances)
    case p: Mirror.ProductOf[T] => eqProduct(p, elemInstances)

Обратите внимание, что derived определяется как inline given. Это означает, что метод будет расширен в местах вызова (например, компилятор сгенерировал определения экземпляров в сопутствующих объектах ADT, которые содержат derived Eq предложение), а также, что его можно будет использовать рекурсивно, если необходимо, для вычисления экземпляров для дочерних элементов.

Тело этого метода (1) сначала материализует экземпляры Eq для всех дочерних типов типа, для которого создается экземпляр. Это либо все ветви типа суммы, либо все поля типа продукта. Реализация summonAll - inline и использует конструкцию Scala 3 summonInline для сбора экземпляров в виде List:

inline def summonAll[T <: Tuple]: List[Eq[_]] =
  inline erasedValue[T] match
    case _: EmptyTuple => Nil
    case _: (t *: ts) => summonInline[Eq[t]] :: summonAll[ts]

с экземплярами для дочерних элементов метод derived использует inline match для отправки методов, которые могут создавать экземпляры либо для сумм, либо для произведений (2). Обратите внимание, что поскольку derived - inline совпадение будет разрешено во время компиляции, и только левая часть совпадающего случая будет встроена в сгенерированный код с уточненными типами, выявленными в результате совпадения.

В случае суммы, eqSum, используются ordinal runtime значения аргументов eqv, чтобы сначала проверить, относятся ли два значения к одному и тому же подтипу ADT (3), а затем, если подтипы совпадают, для дальнейшей проверки на равенство на основе экземпляра Eq для соответствующего подтипа ADT с помощью вспомогательного метода check (4).

import scala.deriving.Mirror

def eqSum[T](s: Mirror.SumOf[T], elems: List[Eq[_]]): Eq[T] =
  new Eq[T]:
    def eqv(x: T, y: T): Boolean =
      val ordx = s.ordinal(x)                            // (3)
      (s.ordinal(y) == ordx) && check(elems(ordx))(x, y) // (4)

В случае продукта eqProduct мы проверяем runtime значения аргументов eqv на равенство как продукты на основе экземпляров Eq для полей типа данных (5):

import scala.deriving.Mirror

def eqProduct[T](p: Mirror.ProductOf[T], elems: List[Eq[_]]): Eq[T] =
  new Eq[T]:
    def eqv(x: T, y: T): Boolean =
      iterator(x).zip(iterator(y)).zip(elems.iterator).forall {  // (5)
        case ((x, y), elem) => check(elem)(x, y)
      }

Собрав все это вместе, получается следующая полная реализация:

import scala.deriving.*
import scala.compiletime.{erasedValue, summonInline}

inline def summonAll[T <: Tuple]: List[Eq[_]] =
  inline erasedValue[T] match
    case _: EmptyTuple => Nil
    case _: (t *: ts) => summonInline[Eq[t]] :: summonAll[ts]

trait Eq[T]:
  def eqv(x: T, y: T): Boolean

object Eq:
  given Eq[Int] with
    def eqv(x: Int, y: Int) = x == y

  def check(elem: Eq[_])(x: Any, y: Any): Boolean =
    elem.asInstanceOf[Eq[Any]].eqv(x, y)

  def iterator[T](p: T) = p.asInstanceOf[Product].productIterator

  def eqSum[T](s: Mirror.SumOf[T], elems: => List[Eq[_]]): Eq[T] =
    new Eq[T]:
      def eqv(x: T, y: T): Boolean =
        val ordx = s.ordinal(x)
        (s.ordinal(y) == ordx) && check(elems(ordx))(x, y)

  def eqProduct[T](p: Mirror.ProductOf[T], elems: => List[Eq[_]]): Eq[T] =
    new Eq[T]:
      def eqv(x: T, y: T): Boolean =
        iterator(x).zip(iterator(y)).zip(elems.iterator).forall {
          case ((x, y), elem) => check(elem)(x, y)
        }

  inline given derived[T](using m: Mirror.Of[T]): Eq[T] =
    lazy val elemInstances = summonAll[m.MirroredElemTypes]
    inline m match
      case s: Mirror.SumOf[T]     => eqSum(s, elemInstances)
      case p: Mirror.ProductOf[T] => eqProduct(p, elemInstances)
end Eq

Получившийся результат можно проверить относительно простого ADT, например:

enum Opt[+T] derives Eq:
  case Sm(t: T)
  case Nn

@main def test(): Unit =
  import Opt.*
  val eqoi = summon[Eq[Opt[Int]]]
  assert(eqoi.eqv(Sm(23), Sm(23)))
  assert(!eqoi.eqv(Sm(23), Sm(13)))
  assert(!eqoi.eqv(Sm(23), Nn))

В этом случае код, сгенерированный встроенным расширением для derived экземпляра Eq для Opt, после небольшой доработки выглядит следующим образом:

given derived$Eq[T](using eqT: Eq[T]): Eq[Opt[T]] =
  eqSum(
    summon[Mirror[Opt[T]]],
    List(
      eqProduct(summon[Mirror[Sm[T]]], List(summon[Eq[T]])),
      eqProduct(summon[Mirror[Nn.type]], Nil)
    )
  )

Можно использовать альтернативные подходы к определению derived методов. Например, более агрессивно встроенные варианты с использованием макросов Scala 3, хотя и более используемы авторами классов типов, чем в приведенном выше примере, могут создавать код для классов типов наподобие Eq, который устраняет все артефакты абстракции (например, дочерние экземпляры List-а в приведенном выше примере) и генерировать код, который неотличим от того, что программист мог бы написать вручную. В качестве третьего примера, используя библиотеку более высокого уровня, такую как Shapeless, автор класса типов может определить эквивалентный derived метод как:

given eqSum[A](using inst: => K0.CoproductInstances[Eq, A]): Eq[A] with
  def eqv(x: A, y: A): Boolean = inst.fold2(x, y)(false)(
    [t] => (eqt: Eq[t], t0: t, t1: t) => eqt.eqv(t0, t1)
  )

given eqProduct[A](using inst: K0.ProductInstances[Eq, A]): Eq[A] with
  def eqv(x: A, y: A): Boolean = inst.foldLeft2(x, y)(true: Boolean)(
    [t] => (acc: Boolean, eqt: Eq[t], t0: t, t1: t) =>
      Complete(!eqt.eqv(t0, t1))(false)(true)
  )

inline def derived[A](using gen: K0.Generic[A]): Eq[A] =
  gen.derive(eqProduct, eqSum)

Описанная здесь структура позволяет использовать все три этих подхода, не навязывая ни один из них.

Получение экземпляров в другом месте

Иногда требуется создать экземпляр класса типов для ADT после того, как ADT определен, без возможности изменения кода самого ADT. Для этого просто определите экземпляр, используя метод derived класса типа в правой части. Например, для реализации Ordering для определения Option:

given [T: Ordering]: Ordering[Option[T]] = Ordering.derived

Предполагая, что у метода Ordering.derived есть контекстный параметр типа Mirror[T], сгенерированным компилятором экземпляр Mirror для Option будет достаточен, а вывод экземпляра будет расширен в правой части этого определения так же, как экземпляр, определенный в сопутствующих объектах ADT.

Как написать метод derived класса типов, используя макросы

Ниже демонстрируется, как реализовать derived метод класса типа, используя только макросы. Мы следуем тому же примеру deriving экземпляров Eq и для простоты поддерживаем тип Product, например класс case Person. Низкоуровневый метод, который будет использовать для реализации метода derived, использует кавычки, соединения как выражений, так и типов, а также scala.quoted.Expr.summon метод, эквивалентный методу summonFrom. Первый подходит для использования в контексте кавычек, используемых в макросах.

Как и в исходном коде, определение класса типа такое же:

trait Eq[T]:
  def eqv(x: T, y: T): Boolean

нам нужно реализовать метод Eq.derived для сопутствующего объекта Eq, который создает quoted экземпляр для Eq[T]. Вот возможная подпись:

given derived[T: Type](using Quotes): Expr[Eq[T]]

и для сравнения дадим ту же подпись, что и у нас с inline:

inline given derived[T]: (m: Mirror.Of[T]) => Eq[T] = ???

Обратите внимание, что поскольку тип используется на последующем этапе, его необходимо поднять до Type с помощью соответствующей привязки контекста. Кроме того, мы не можем вызвать quoted Mirror внутри тела derived, мы можем опустить его из подписи. Тело метода derived показано ниже:

given derived[T: Type](using Quotes): Expr[Eq[T]] =
  import quotes.reflect.*

  val ev: Expr[Mirror.Of[T]] = Expr.summon[Mirror.Of[T]].get

  ev match
    case '{ $m: Mirror.ProductOf[T] { type MirroredElemTypes = elementTypes }} =>
      val elemInstances = summonAll[elementTypes]
      val eqProductBody: (Expr[T], Expr[T]) => Expr[Boolean] = (x, y) =>
        elemInstances.zipWithIndex.foldLeft(Expr(true: Boolean)) {
          case (acc, (elem, index)) =>
            val e1 = '{$x.asInstanceOf[Product].productElement(${Expr(index)})}
            val e2 = '{$y.asInstanceOf[Product].productElement(${Expr(index)})}
            '{ $acc && $elem.asInstanceOf[Eq[Any]].eqv($e1, $e2) }
        }

      '{ eqProduct((x: T, y: T) => ${eqProductBody('x, 'y)}) }

  // case for Mirror.ProductOf[T]
  // ...

Обратите внимание, что в этом inline случае можно просто написать summonAll[m.MirroredElemTypes] внутри встроенного метода, но здесь, поскольку это необходимо Expr.summon, можно извлечь типы элементов в виде макроса. Находясь внутри макроса, нашей первой реакцией было бы написать приведенный ниже код. Поскольку путь внутри аргумента типа нестабилен, его нельзя использовать:

'{
  summonAll[$m.MirroredElemTypes]
}

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

case '{ $m: Mirror.ProductOf[T] { type MirroredElemTypes = elementTypes }} => ...

Ниже показана реализация summonAll в виде макроса. Предполагается, что given экземпляры для примитивных типов существуют.

def summonAll[T: Type](using Quotes): List[Expr[Eq[_]]] =
   Type.of[T] match
      case '[String *: tpes] => '{ summon[Eq[String]] } :: summonAll[tpes]
      case '[Int *: tpes]    => '{ summon[Eq[Int]] }    :: summonAll[tpes]
      case '[tpe *: tpes]    => derived[tpe] :: summonAll[tpes]
      case '[EmptyTuple]     => Nil

Еще одно отличие тела derived здесь от тела с inline заключается в том, что с макросами нужно синтезировать тело кода во время макрорасширения. Это обоснование функции eqProductBody. Предполагая, что мы вычисляем равенство двух Persons, определенных с case классом, который содержит имя типа String и возраст типа Int, проверка на равенство, которую хотим сгенерировать, выглядит следующим образом:

true
   && Eq[String].eqv(x.productElement(0),y.productElement(0))
   && Eq[Int].eqv(x.productElement(1), y.productElement(1))

Вызов производного метода внутри макроса

Следуя правилам макросов, мы создаем два метода. Первый, в котором размещается соединение верхнего уровня eqv, и второй - реализация. В качестве альтернативы показанного ниже, можно вызвать метод eqv напрямую. eqGen может вызвать деривацию.

extension [T](inline x: T)
   inline def === (inline y: T)(using eq: Eq[T]): Boolean = eq.eqv(x, y)

inline given eqGen[T]: Eq[T] = ${ Eq.derived[T] }

Обратите внимание, что используется синтаксис inline метода, и можно сравнивать экземпляры, Sm(Person("Test", 23)) === Sm(Person("Test", 24)), например, для следующих двух типов:

case class Person(name: String, age: Int)

enum Opt[+T]:
   case Sm(t: T)
   case Nn

Полный код показан ниже:

import scala.deriving.*
import scala.quoted.*


trait Eq[T]:
   def eqv(x: T, y: T): Boolean

object Eq:
   given Eq[String] with
      def eqv(x: String, y: String) = x == y

   given Eq[Int] with
      def eqv(x: Int, y: Int) = x == y

   def eqProduct[T](body: (T, T) => Boolean): Eq[T] =
      new Eq[T]:
         def eqv(x: T, y: T): Boolean = body(x, y)

   def eqSum[T](body: (T, T) => Boolean): Eq[T] =
      new Eq[T]:
         def eqv(x: T, y: T): Boolean = body(x, y)

   def summonAll[T: Type](using Quotes): List[Expr[Eq[_]]] =
      Type.of[T] match
         case '[String *: tpes] => '{ summon[Eq[String]] } :: summonAll[tpes]
         case '[Int *: tpes]    => '{ summon[Eq[Int]] }    :: summonAll[tpes]
         case '[tpe *: tpes]    => derived[tpe] :: summonAll[tpes]
         case '[EmptyTuple]     => Nil

   given derived[T: Type](using q: Quotes): Expr[Eq[T]] =
      import quotes.reflect.*

      val ev: Expr[Mirror.Of[T]] = Expr.summon[Mirror.Of[T]].get

      ev match
         case '{ $m: Mirror.ProductOf[T] { type MirroredElemTypes = elementTypes }} =>
            val elemInstances = summonAll[elementTypes]
            val eqProductBody: (Expr[T], Expr[T]) => Expr[Boolean] = (x, y) =>
               elemInstances.zipWithIndex.foldLeft(Expr(true: Boolean)) {
                  case (acc, (elem, index)) =>
                     val e1 = '{$x.asInstanceOf[Product].productElement(${Expr(index)})}
                     val e2 = '{$y.asInstanceOf[Product].productElement(${Expr(index)})}

                     '{ $acc && $elem.asInstanceOf[Eq[Any]].eqv($e1, $e2) }
               }
            '{ eqProduct((x: T, y: T) => ${eqProductBody('x, 'y)}) }

         case '{ $m: Mirror.SumOf[T] { type MirroredElemTypes = elementTypes }} =>
            val elemInstances = summonAll[elementTypes]
            val eqSumBody: (Expr[T], Expr[T]) => Expr[Boolean] = (x, y) =>
               val ordx = '{ $m.ordinal($x) }
               val ordy = '{ $m.ordinal($y) }

               val elements = Expr.ofList(elemInstances)
               '{ $ordx == $ordy && $elements($ordx).asInstanceOf[Eq[Any]].eqv($x, $y) }

         '{ eqSum((x: T, y: T) => ${eqSumBody('x, 'y)}) }
   end derived
end Eq

object Macro3:
   extension [T](inline x: T)
      inline def === (inline y: T)(using eq: Eq[T]): Boolean = eq.eqv(x, y)

   inline given eqGen[T]: Eq[T] = ${ Eq.derived[T] }

Ссылки: