?

Log in

No account? Create an account

Зачем нужны имплисит макросы? - Excelsior — LiveJournal

May. 7th, 2013

11:06 pm - Зачем нужны имплисит макросы?

Previous Entry Share Next Entry

И в недавней папере и во вчерашнем посте про новые макро фичи в 2.10.2, я упоминал имплисит макросы. Это все хорошо, но очень эзотерично, поэтому наверняка у вас возник вопрос о смысле существования таких макросов. Сегодня я постараюсь наглядно объяснить.

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

С имплисит макросами произошло несколько по-другому. Довольно долгое время мы не догоняли их сакраментального значения, поэтому они, в основном, служили материалом для шуток. Ну, знаете, многие боятся имплиситов и точно так же многие боятся макросов, поэтому имплисит макросы это получается вообще что-то убер. Я, кстати, предлагаю в этом посте не обсуждать кажущуюся бессмысленность имплиситов или макросов, т.к. уже есть отличные беседы на эту тему: про имплиситы и про макросы. Давайте лучше сосредоточимся собственно на теме поста.

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

Тайп классы и их инстансы

Тайп классы были впервые описаны Филипом Вадлером в работе How to make ad-hoc polymorphism less ad hoc для реализации оверлоадинга функций (ad-hoc polymorphism) в Хаскелле. С того времени прошло уже больше двадцати лет и тайп классам нашлась масса применений - от поддержки ретроактивной расширяемости до вычислений на типах.

Со времен паперы Type Classes as Objects and Implicits известно, что при помощи имплиситов тайп классы можно реализовать и в Скале. Детальное описание техники, ее применения, а также сравнение с аналогами в других языках можно прочитать в папере, а здесь же мы просто обсудим несложный пример для того, чтобы разобраться, что представляют собой тайп классы.

Предположим, что нам нужно реализовать сериализатор. Одним из самых простых вариантов реализации будет объявление пачки оверлоадов: наиболее общего метода для произвольных классов, основанного на рефлексии, и нескольких специализированных методов для часто используемых типов вроде примитивов и коллекций.
  def serialize(x: Any): Pickle
  def serialize(x: Int): Pickle
  def serialize(x: String): Pickle
  ...
  def serialize[T](x: Traversable[T]): Pickle
Одним из недостатков данной реализации является слабая расширяемость. К примеру, для сериализации массивов вместо медленного поэлементного обхода и копирования массива в результирующий Pickle можно использовать интринсики JVM, которые быстро скопируют всю пачку байтов, представляющую массив, в пачку байт, представляющую результат сериализации. Единственным вариантом использования этой техники будет добавление нового оверлоада def serialize[T](x: Array[T]): Pickle, что вполне несложно, если мы контролируем код сериализатора, но становится невозможным в случае, если мы используем чью-то библиотеку сериализации, скачанную из мейвена.

Для устранения этого досадного недостатка можно вынести стратегию сериализации в отдельный модуль, Serializable[T], который мы назовем тайп классом, и заменить все оверлоады на один-единственный метод, параметризованный стратегией. Теперь, вызывая serialize, в дополнение к собственно сериализуемому значению программист будет также передавать модуль, реализующий подходящий Serializable, который мы назовем инстансом тайп класса.

Замечание. В комментариях завязалось интересное обсуждение этого определения тайп классов. Уважаемый juan_gandhi предлагает альтернативную и, возможно даже, более точную формулировку: http://xeno-by.livejournal.com/83590.html?thread=793734#t793734.
  trait Serializable[T] { // тайп класс
    def serialize(x: T): Pickle
  }
  def serialize[T](x: T)(s: Serializable[T]): Pickle = s.serialize(x)

  object IntSerializable extends Serializable[Int] { // инстанс тайп класса
    def serialize(x: Int) = Pickle.fromInt(x)
  }
  serialize(42)(IntSerializable)
Само собой, не особенно весело руками передавать инстансы тайп класса в каждый вызов serialize, но это и не нужно, т.к. в Скале есть имплиситы, которые полностью автоматизируют этот процесс. Если отметить параметр s ключевым словом implicit, то при вызове serialize компилятор переберет все доступные в текущий момент имплиситы (т.е. значения, объекты и методы, аннотированные ключевым словом implicit), автоматически выберет подходящий имплисит и передаст его в serialize.
  trait Serializable[T] { ... }
  def serialize[T](x: T)(implicit s: Serializable[T]): Pickle = ...

  implicit object IntSerializable extends Serializable[Int] { ... }
  serialize(42) // превратится в serialize(42)(IntSerializable)
Очень важная особенность имплиситов заключается в том, что они композируются. Например, можно написать сериализатор, работающий для любых списков, элементы которых сериализуются. Обратите внимание, что в вызове serialize(x) в реализации listSerializable компилятор сам поймет, что нужно использовать сериализатор s, совместимый с элементами списка - таким образом из простых инстансов тайп классов можно собирать более сложные.
  implicit def listSerializable[T](implicit s: Serializable[T]) = new Serializable[List[T]] {
    def serialize[T](xs: List[T]) = {
      val p = new Pickle
      for (x <- xs) p += serialize(x)
      p
    }
  }

  implicit object IntSerializable extends Serializable[Int] { ... }
  serialize(List(42)) // превратится в serialize(List(42))(listSerializable(IntSerializable))
Наконец, еще одна приятная фича имплиситов заключается в том, что они могут влиять на тайп инференс - именно так и реализованы крайне удобные методы стандартных коллекций. Например, map, вызванный на списке, вернет список, в то время как тот же самый map, вызванный на массиве, вернет массив.
  def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = ...

  implicit def cbfList[T] = new CanBuildFrom[List[_], T, List[T]]
  List(1, 2).map(x => x) // возвращаемый тип: List[Int]

  implicit def cbfArray[T] = new CanBuildFrom[Array[_], T, Array[T]]
  Array(1, 2).map(x => x) // возвращаемый тип: Array[Int]

Материализация инстансов тайп классов

Возвращаясь к сериализации, давайте рассмотрим вопрос реализации сериализаторов для кастомных классов (например, для кейс классов, используемых для моделирования домена какого-нибудь приложения). Можно довольно легко написать обобщенную реализацию, основанную на рефлекшене, которая будет работать для произвольных объектов таких классов, но, к сожалению, производительность решений, использующих рефлекшен, обычно оставляет желать лучшего.

Поэтому в Play, например, JSON-сериализаторы обычно пишутся руками. Добавил в программу новый кейс-класс - написал новый инстанс тайп класс сериализации, добавил еще один класс - написал еще один инстанс. Даже для простых классов выглядит это не очень.
  case class Person(name: String)
  implicit val personReads = (
    (__ \ 'name).reads[String]
  )(Person)
При помощи обычных (не имплисит) макросов уже в 2.10.0 можно значительно уменьшить количество кода, который нужно писать руками. Всю целиком реализацию имплисита можно сгенерировать при помощи макроса, который будет делать все то же самое, что сделала бы рефлективная реализаци, но без потери производительности.
  case class Person(name: String)
  implicit val personReads = Json.reads[Person] // reads это макрос!
При помощи имплисит макросов можно убрать последнюю каплю бойлерплейта и вообще не объявлять инстансы сериализующего тайп класса, а вместо этого написать один-единственный имплисит макрос, генерирующий эти инстансы.
  trait Serializable[T] { def serialize(x: T): Pickle }
  object Serializable {
    implicit def materializeSerializable[T]: Serializable[T] = macro ...
  }
Внутри такого имплисит макроса программист имеет доступ к внутреннему представлению типа T (например, можно получить список всех полей соответствующего класса). Соответственно, каждый раз, когда компилятор производит поиск инстансов тайп класса Serializable, макрос может сгенерировать подходящий инстанс на лету. Например, для класса Person, мы сгенерируем new Serializable[Person] { def serialize(x: Person) = ... }.

Красота имплисит макросов заключается еще в том, что они идеально интегрируются в стандартную инфраструктуру имплиситов. Например, наряду с обобщенным материализатором вполне возможно объявить и использовать написанный вручную имплисит для специального случая (например, для массивов). Также можно определить и специализированный материализатор, например, макрос, генерирующий сериализаторы только для синглтонов. Кроме того, можно обычным для обычных имплиситов способом управлять скоупингом имплисит макросов. Ну и, наконец, с помощью имплисит макросов можно управлять тайп инференсом, но, правда, это еще весьма свежая тема: https://github.com/scala/scala/pull/2499.

А в это время в Хаскелле

В Хаскелле тайп классы гораздо более распространены, чем в Скале, поэтому весьма логично то, что в паперах про Хаскелл материала по автоматической генерации инстансов тайп классов гораздо больше. Я сам не специалист по Хаскеллу, поэтому буду говорить в меру своего понимания, а более опытных коллег попрошу меня дополнять и поправлять.

Из прочтения паперы A Generic Deriving Mechanism for Haskell у меня создалось впечатление, что дела с материализацией обстоят следующим образом:
1) Тем или иным способом программисту предоставляется возможность в рантайме рефлексировать относительно типов. Например, для абстрактного типа данных data Exp = Const Int | Plus Exp Exp будет возможность узнать имя Exp, то, что у этого Expr есть два конструктора по имени Const и Plus, а также то, какие типы параметров эти конструкторы принимают.
2) На основе метаданных, имеющихся для типов, становится возможным представить любые значения в программе (от простых до самых навороченных) в унифицированном виде. Например, значению Const 2 будет соответствовать представление вида "абстрактный тип данных по имени Exp => первый конструктор => первый аргумент равен двум".
3) Теперь, когда у нас есть универсальные представления типов и значений, при помощи паттерн матчинга по этим представлениям для типов (в сигнатурах инстансов тайп классов) и значениям (в телах функций этих инстансов), можно для любого тайп класса написать обобщенную реализацию, которая будет работать для всех типов. В примере ниже, взятом из сабжевой паперы и несколько упрощенном, приведена реализация обобщенного сериализатора, работающего для целой кучи типов:
  data Bit = 0 | 1

  class Encode α where
    encode :: α → [Bit]

  instance Encode Int where encode = ...
  instance Encode Char where encode = ...

  instance (Encode φ, Encode ψ) ⇒ Encode (φ + ψ) where
    encode (L a) = 0 : encode a
    encode (R a) = 1 : encode a

  instance (Encode φ, Encode ψ) ⇒ Encode (φ × ψ) where
    encode (a × b) = encode a ++ encode b
Как я могу судить по первому знакомству с литературой, эта техника кажется проще в использовании, чем генерация кода при помощи макросов, но у нее есть недостаток - перфоманс, так как перед обработкой данные всегда должны быть преобразованы в универсальный формат. Как указывает папера Optimizing Generics Is Easy!, замедление относительно рукописных инстансов составляет 1-2 порядка. Можно сказать, что этот результат примерно коррелирует с примером из предыдущей части поста, в которой речь шла про Скалу, когда мы были вынуждены использовать рукописные сериализаторы вместо универсального сериализатора, основанного на рефлексии.

Первое решение проблемы с перфомансом заключается в использовании встроенного в GHC оптимизатора. Как красочно описывается в Optimizing Generics Is Easy!, выставление нужных флагов для GHC иногда позволяет полностью устранить оверхед, так как GHC настолько крут, что иногда способен заинлайнить и дефорестировать преобразование данных в универсальный формат, превратив паттерн матч по универсальному представлению данных в специализированный паттерн матч по конструкторам АДТ. Впрочем, как и у всех техник автоматической оптимизации, у этой техники есть определенные проблемы. Во-первых, даже если оптимизации и работают, требуется тщательный подбор флагов оптимизатора для достижения хороших результатов. Во-вторых, для некоторых популярных реализаций рефлексии встроенный оптимизатор вообще неэффективен.

Второе решение заключается в использовании макросов, то есть Template Haskell. Библиотека Template Your Boilerplate предоставляет набор комбинаторов при помощи которых можно удобно разрабатывать компайл-тайм генераторы инстансов тайп классов. По сути, TYB использует трехшаговую технику, описанную выше, но для каждого конкретного типа данных она дополнительно выполняет компайл-тайм специализацию на полуручной тяге. Перфоманс получается отличный, но реализация замусоривается деталями стейджинга.

Возникает закономерный вопрос: можно ли совместить удобство разработки обобщенных рантайм реализаций и скорость сгенерированных в компайл-тайме специализаций? Или же, по-другому, можно ли для shallowly embedded доменно-специфического языка прозрачно применить deep embedding со всеми его плюшками на тему оптимизаций? На последний вопрос в нашей недавней папере Yin-Yang: Transparent Deep Embedding of DSLs дан весьма убедительный положительный ответ, поэтому я уверен, что и в частном случае генерации инстансов тайп классов все будет в порядке.

Резюме

1) Тайп классы представляют собой паттерн организации расширяемого кода.
2) Тайп класс = полиморфный модуль, содержащий набор абстрактных (и не только) функций, например, trait Serializer[T] { def serialize(x: T): Pickle }.
3) Инстанс тайп класса = модуль, реализующий функции тайп класса для конкретного типа, например, object IntSerializer extends Serializer[Int] { def serialize(x: Int) = ... }.
4) При помощи имплиситов и средств модуляризации, предоставляемых ООП, паттерн "тайп класс" может полноценно и удобно использоваться в Скале.
5) Написание инстансов тайп классов зачастую сопровождается кучей ручного труда, который вроде бы и можно, но весьма трудно абстрагировать обычными средствами языка.
6) При помощи имплисит макросов можно полностью автоматически генерировать инстансы тайп классов.
7) Имплисит макросы прозрачно встраиваются в инфраструктуру обычных имплиситов, что делает их композируемыми, управляемым и в хорошем смысле незаметными для пользователя.
8) Генерация инстансов тайп классов при помощи макросов эффективна с точки зрения производительности, но не очень удобна в реализации.
9) Вполне возможно, что при помощи какого-нибудь мета имплисит макроса можно будет совместить производительность и удобство разработки, но это покажет будущее.

Tags: ,

Comments:

From:zhengxi
Date:May 7th, 2013 09:26 pm (UTC)
(Link)
  case class Person(name: String)
  implicit val personReads = Json.reads[Person] // reads это макрос!

При помощи имплисит макросов можно убрать последнюю каплю бойлерплейта и вообще не объявлять инстансы сериализующего тайп класса, а вместо этого написать один-единственный имплисит макрос

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

для кастомных классов вот так, а case class - в общем виде, макрос про всё них узнаёт через рефлексию во время компиляции и генерит соответсвующий код.

Edited at 2013-05-07 09:29 pm (UTC)
(Reply) (Thread)
[User Picture]
From:xeno_by
Date:May 7th, 2013 09:29 pm (UTC)
(Link)
А как юзерам расширять Json.pack/Json.unpack? Можно ли, например, написать кастомную реализацию сериализаторов для какой-нибудь супер-мега-коллекции MyCollection[T], которая берет сериализатор для T и как-то его использует для создания сериализованного представления коллекции?
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:unstablebear
Date:May 8th, 2013 04:08 am (UTC)
(Link)
> implicit def listSerializable[T](xs: List[T])(implicit s: Serializable[T]) = {
> val p = new Pickle
> for (x <- xs) p += serialize(x)
> p
> }
>
> implicit object IntSerializable extends Serializable[Int] { ... }
> serialize(List(42))

Насколько я могу понять последний вызов serialize эквивалентен serialize(listSerializable[Int](List(42))(IntSerializable)) .
listSerializable вернет Pickle. Подразумевается, что существует инстанс тайп-класса вроде PickleSerializable extends Serializable[Pickle] { ... } ?
В теме не силен, но интересуюсь :)
(Reply) (Thread)
[User Picture]
From:xeno_by
Date:May 8th, 2013 07:01 am (UTC)
(Link)
Прошу прощения, пример я зафейлил. Теперь все исправлено и добавлен результат дешугаринга. Спасибо!
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:thedeemon
Date:May 8th, 2013 05:04 am (UTC)
(Link)
Спасибо, очень внятно изложено.

В недавнем проекте на D у меня сериализация в бинарный поток произвольных объектов/структур/массивов из простых типов и других объектов/структур/массивов вылилась в несколько строк, вот они целиком:
void saveArray(T)(T[] arr, OutBuffer buf)
{
    int n = arr.length;
    buf.write(n);
    static if (isBasicType!T) 
        buf.write(cast(const(ubyte)[])arr);
    else 
        foreach(x; arr) save(x, buf);	
}

void save(T)(T x, OutBuffer buf)
{
    static if (isBasicType!T) buf.write(x);
    else
    static if (isArray!T) saveArray(x, buf);
    else			
    foreach(m; __traits(allMembers, T))
        static if ((m!="Monitor") && !isSomeFunction!(typeof(__traits(getMember, x, m))))
            save(__traits(getMember, x, m), buf);
}


Весь рефлекшон, проверки и циклы по мемберам раскрываются в компайл-тайме, в рантайме оказываются уже специализированные функции. Чтение обратно выглядит аналогично. Такой простоты больше нигде не видел.
(Reply) (Thread)
[User Picture]
From:xeno_by
Date:May 8th, 2013 07:08 am (UTC)
(Link)
Мартин очень положительно отзывается о простоте метапрограммирования в D. Кое-что оттуда, возможно, войдет в обновленный дизайн макросов в 2.11 или 2.12, но пока что о деталях говорить рано. Лично мне очень нравится идея адхок генерации кода при помощи mixin. Строки это, конечно, не фонтан, но сама возможность вколбасить куда хочешь что хочешь впечатляет.

Касательно твоего примера, как здесь с расширяемостью? Например, как добавить еще одно условие в кондишен if ((m!="Monitor") && ...)?
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:akuklev
Date:May 8th, 2013 11:54 am (UTC)
(Link)
А есть ли уже тайпмакрос Tuple(n: Nat), генерящий туплы разных размеров или так и остались типы Tuple2, Tuple3, Tuple4 и т.д.? Есть ли тайпмакрос для создания именованного произведения?

Usecase:
есть points: Collection[Point], moments: Collection[Time]
val events = points tableProduct time
for (event <- events) {
println(event.points.x)
println(event.moments.t)
}

Тип events -- TableProduct[Point, Time]("points", "moments") = {val points: Point; val moments: Time}

Другой, менее тривиальный пример -- оператор джоина таблиц:
users: Collection[User]
phoneBook: Collection[PhoneBookEntry]
usersWithPhoneNumbers = users join{_.name} phoneBook
(Reply) (Thread)
From:ex_juan_gan
Date:May 10th, 2013 03:15 am (UTC)
(Link)
Было бы неплохо, конечно.
Народу надо.

(Reply) (Parent) (Thread)
[User Picture]
From:akuklev
Date:May 8th, 2013 11:57 am (UTC)
(Link)
Ох крррасота! Тайпмакросы + имплисит макросы это макрорай в самом деле, сделать можно всё.
А вот скажи, как у вас дела со Slick'ом и автогенерацией соотв. типов из спецификации базы данных во время компиляции?
(Reply) (Thread)
[User Picture]
From:xeno_by
Date:May 8th, 2013 11:59 am (UTC)
(Link)
С тайп макросами, в отличие от имплисит макросов, непонятно, войдут ли они в состав основной Скалы. Есть разные подходы к вычислениям на типах. Например, Адриаану нравятся type families из Хаскелла. Поэтому пока что мы еще думаем (а точнее, только начали думать) о том, в какую сторону двигаться.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:xeno_by
Date:May 8th, 2013 11:59 am (UTC)
(Link)
Для Слика вроде бы есть прототип тайп провайдеров, но так как с тайп макросами ничего не ясно, то там проект пока что немного затормозился.
(Reply) (Parent) (Thread)
[User Picture]
From:akuklev
Date:May 8th, 2013 12:00 pm (UTC)
(Link)
И всё-таки, как у макросов дела с выдачей разумных сообщений об ошибках?
(Reply) (Thread)
[User Picture]
From:xeno_by
Date:May 8th, 2013 12:01 pm (UTC)
(Link)
Пока никак, разве что автор сам руками вызовет c.error/c.abort в красивым сообщением об ошибке.
(Reply) (Parent) (Thread) (Expand)
From:ex_juan_gan
Date:May 10th, 2013 03:55 am (UTC)
(Link)
Это прекрасно, конечно; я, правда, за псевдоквоты, или как их там по-русски. Описывать деревья в виде выражений как-то не тянет. Тянет на выразительность.

Имплицитные макросы - это да, это сильно; это мы как бы выскакиваем на новый уровень.

Спасибо.

(А с мнением, шо это такое, тайпклассы, я не соглашусь; по мне так тайп класс - это класс типов.)
(Reply) (Thread)
[User Picture]
From:xeno_by
Date:May 10th, 2013 04:22 am (UTC)
(Link)
Можете, пожалуйста, пояснить про класс типов? Т.е., например, в случае Serializable тайп классом предлагается называть множество {Int, String, List[Int], List[String]...}?
(Reply) (Parent) (Thread) (Expand)