суботу, 25 січня 2014 р.

Function on types and advanced pattern matching

Вы наверное помните мой недавний вопрос. Частично он решен: есть реализация через методы класса (см. там же). Но мне также хотелось иметь решение через паттерн матчинг. Но компилятор (напомню, что его зовут scalac) никак не принимал мое решение.

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

Ниже вы можете увидеть тип Expr, параметризованный НЕ типом возвращаемого значения, а тегом, который символизирует тип возвращаемого значения. Типы Case, First и Second будут представлены позже.

object Tag {
  type Bool = First
  type Num = Second
}

trait Expr[_ <: Case]
object Bool extends Expr[Tag.Bool]
object Num extends Expr[Tag.Num]
case class Or(a: Expr[Tag.Bool], b: Expr[Tag.Bool]) 
  extends Expr[Tag.Bool]
case class If[T <: Case](b: Expr[Tag.Bool], x: Expr[T], y: Expr[T]) 
  extends Expr[T]
case class Plus(x: Expr[Tag.Num], y: Expr[Tag.Num]) 
  extends Expr[Tag.Num]

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

trait Api[B, N] {
  def num(): N
  def bool(): B
  def or(a: B, b: B): B
  def plus(x: N, y: N): N
  def if_[T](b: B, x: T, y: T): T
}

Давайте теперь попробуем написать функцию для вычисления значения конкретного выражения для конкретного API:

def eval[T <: Case, B, N](e: Expr[T], api: Api[B, N])

Какой тип возвращает эта функция? Если T =:= Bool, то результат B, иначе N. Тут нам нужны функции на типах. Над решением этого мне пришлось долго биться головой об стену, но на самом деле нужно было просто ввести shapeless в Google. А конкретней нужно было посмотреть на реализацию Boolean induction. Так родился (копипастом) тип Case и его друзья:

sealed trait Case
final class First extends Case
final class Second extends Case

sealed trait Select[S <: Case, A, B] {
  type T
}
object Select {
  implicit def whenFirst[A, B] = new Select[First, A, B] {
    type T = A
  }
  implicit def whenSecond[A, B] = new Select[Second, A, B] {
    type T = B
  }
}

Теперь можно полностью написать сигнатуру функции eval:

def eval[T <: Case, B, N](expr: Expr[T], api: Api[B, N])(
  implicit s: Select[T, B, N]): s.T

Осталось написать тело этой функции (API передается неявно просто для удобства). Пробуем решение в лоб:

def eval[T <: Case, B, N](expr: Expr[T])(
  implicit api: Api[B, N], s: Select[T, B, N]): s.T =
  expr match {
    case Bool => api.bool()
    case Num => api.num()
    case Or(a, b) => api.or(eval(a), eval(b))
    case Plus(x, y) => api.plus(eval(x), eval(y))
    case If(b, x, y) => api.if_(eval(b), eval(x), eval(y))
  }

Конечно же компилятор не примет такого решение. Повсюду можно видеть ошибки вида type mismatch; found: B required: s.T. Все потому, что компилятор не знает, что если, например, выражение имеет тип Expr[Tag.Bool], то результат будет иметь тип B, то есть B =:= s.T.

Для этого компилятору нужно чуть-чуть помочь. Рассмотрим следующий случай:

object Bool extends Expr[Tag.Bool]
...
    case Bool => api.bool()

В данной ветке (case'е) компилятор знает, что T =:= Tag.Bool. Воспользуемся этой информацией и добавим несколько вспомогательных методов к trait'у Select.

sealed trait Select[S <: Case, A, B] {
  type T
  implicit def toFirst(t: T)(implicit ev: S =:= First): A
  implicit def toSecond(t: T)(implicit ev: S =:= Second): B
  implicit def fromFirst(a: A)(implicit ev: S =:= First): T
  implicit def fromSecond(b: B)(implicit ev: S =:= Second): T
}

object Select {
  private def absurd(bottom: AnyRef) = throw new Exception(
    if (bottom == null) "Cheater detected. Null is passed as an evidence"
    else s"Impossible happened. Absurd is proved: $bottom")

  implicit def whenFirst[A, B] = new Select[First, A, B] {
    type T = A
    def toFirst(t: T)(implicit ev: First =:= First): A = t
    def toSecond(t: T)(implicit ev: First =:= Second): B = absurd(ev)
    def fromFirst(a: A)(implicit ev: First =:= First): T = a
    def fromSecond(b: B)(implicit ev: First =:= Second): T = absurd(ev)
  }

  implicit def whenSecond[A, B] = new Select[Second, A, B] {
    type T = B
    def toFirst(t: T)(implicit ev: Second =:= First): A = absurd(ev)
    def toSecond(t: T)(implicit ev: Second =:= Second): B = t
    def fromFirst(a: A)(implicit ev: Second =:= First): T = absurd(ev)
    def fromSecond(b: B)(implicit ev: Second =:= Second): T = b
  }
}

Вот и все! В ветке, которую мы рассматриваем (case Bool) есть доказательство T =:= Tag.Bool, поэтому может сработать соответствующее неявное преобразование (implicit conversion) нужно только внести в область видимости данные преобразования. Конечная функция будет выглядеть следующим образом:

def eval[T <: Case, B, N](expr: Expr[T])(
  implicit api: Api[B, N], s: Select[T, B, N]): s.T = {
  import s._
  expr match {
    case Bool => api.bool()
    case Num => api.num()
    case Or(a, b) => api.or(eval(a), eval(b))
    case Plus(x, y) => api.plus(eval(x), eval(y))
    case If(b, x, y) => api.if_(eval(b), eval(x), eval(y))
  }
}

Вывод

Учите матчасть, читайте исходники shapeless.

Немає коментарів:

Дописати коментар