об bounded polymorphism

[thedeemon]

Андрей Александреску, который когда-то непоправимо и бесповоротно изнасиловал мозги С++ программистов книгой об изощрениях на С++ шаблонах, выступил на днях как тролль 78-го уровня:

Доклад с названием Generic Programming Must Go содержит фразы вроде "Generic Programming is fail" и "Concepts are fail". Но не обольщайтесь, он не содержит призывов переходить на Го, где нет генериков. Речь о другом.

Он берет несколько странное определение Generic Programming (из википедии), где говорится, что в обобщенном коде требования к алгоритмам и структурам данных абстрагируется через концепты, и код пишется в терминах этих концептов. Концепты это что-то вроде тайпклассов. Обсуждения о включении концептов в С++ в виде языковой фичи ведутся еще со времен первых крестовых походов, когда слово тайпкласс было известно лишь в отдельных монастырях Шотландии. Каждый концепт, каждый тайпкласс - это в первую очередь имя. Если у нас есть семейство типов с большим набором необязательных операций, т.е. каждый конкретный тип из этого семейства может реализовывать свое подмножество этого набора операций, то канон такого вот Generic Programming'a предполагает создание отдельного имени для каждой комбинации, т.е. для 10 операций тут может быть 1024 слегка разных концепта. В мире ООП эта ситуация частенько разруливается через один интерфейс на 10 функций и просто бросание NotImplementedException для неподдержанных операций в реализациях оного интерфейса, но хочется ведь это безобразие контролировать в статике, на уровне типов. В языках с тайпклассами это обычно превращается в 10 маленьких тайпклассиков, и если нашей функции нужны 7 операций из того набора, то на генерик тип будет навешено условие с перечислением всех 7 тайпклассов, ну или нужно описывать новый тайпкласс, являющийся пересечением тех 7, т.е. идем по дороге в сторону 1024 имен.

Еще интереснее ситуации, где у нас генерик тип С зависит от типов-параметров А и В, и некоторая операция определенa для С только если она определена хотя бы для одного из А или В. Как это будет выглядеть обычно? На тайпклассах скорее всего придется описывать две реализации (в одной предусловие-тайпкласс навешен на А, в другой на В), и как-то разруливать вариант, когда А и В оба поддерживают требуемую операцию.

В качестве примера Александреску рассматривает свою библиотеку аллокаторов, которую он пытался сначала задизайнить в стиле Generic Programming, но провалился. У аллокаторов бывает пара десятков разных операций, и разные аллокаторы поддерживают разные подмножества операций из этого набора. Кто-то умеет освобождать память, кто-то нет. Кто-то умеет изменять размер выделенного куска на месте, кто-то только переносом на новое место в памяти, а кто-то совсем не умеет realloc. И т.д. Всякие интересности начинаются, когда мы объединяем два аллокатора в один - первый используется в качестве primary, второй в качестве fallback, он используется когда первый не может выделить. Операция deallocate для такого объединенного аллокатора имеет смысл, когда хотя бы один из них умеет освобождать память.

И в качестве ответа он предлагает подход Design by Introspection, который местами уже активно используется в D, просто не имел названия. Его формула: Static introspection + CTFE + Boolean constraints + static if = WIN. Все опирается на Dивные возможности компайл-тайм интроспекции, когда у переданного типа-параметра можно запросить, какие у него есть члены или умения, может ли он делать то или это (тут пригождается Compile Time Function Execution), и в зависимости от этого через static if делать то или это, а также включать или не включать те или иные операции в определяемый генерик тип. Пример такого подхода:

static if (hasMember!(P, "owns") && (hasMember!(P, "deallocate") || hasMember!(F, "deallocate")))
void deallocate(void[] b) {
  if (primary.owns(b)) {
    static if (hasMember!(P, "deallocate"))
      primary.deallocate(b);
  } else {
    static if (hasMember!(F, "deallocate"))
      fallback.deallocate(b);
  }
}

Тут deallocate - метод некоторого определяемого генерик типа, зависящего от типов-параметров P и F - типов primary и fallback аллокаторов. Если P умеет отличать выделенную им память от чужой (hasMember!(P, "owns")), и хотя бы кто-то из P и F имеет метод deallocate, то тогда только данный метод становится частью описываемого типа. Внутри он определяет, которому из аллокаторов принадлежит освобождаемая память, и вызывает соответствующий метод deallocate, если тот определен. Тут большая пользя от static if еще не очень заметна, то же самое на тайпклассах или концептах могло быть даже проще записано, как две разных функции, но в более сложных примерах, где больше общей логики static if начинает рулить, там разделение разных вариантов по разным реализациям функции привело бы к большому количеству повторяющегося кода.

Само выступление: видео, слайды. В нормальном качестве видео будет позже, пока лишь запись с онлайн стрима.

От себя могу отметить, что с конкретно такой ситуацией, как у него, я особо не сталкивался, но зато было, когда мой контейнер мог иметь разное представление данных и разные дополнительные поля в зависимости от свойств типов-параметров. И там пользу от static if и компайл-тайм интроспекции ощутил хорошо, так что с формулой в целом согласен. На одних бесплатных теоремах, где можно работать с чем угодно, но нельзя с этим чем угодно делать ничего конкретного, далеко не уедешь.

Comments

[soonts.livejournal.com]

В нормальных С++ компайлерах вот уже более 10 лет есть __if_exists statement :-)

[thedeemon.livejournal.com]

А кто-нибудь рискует этим пользоваться? Чего нет в стандарте то не существует же, для большинства плюсовиков.
Но в целом да, в сочетании с constexpr уже близко.

[soonts.livejournal.com]

>кто-нибудь рискует этим пользоваться?
Пользовался несколько раз. Нужно нечасто, зато когда нужно, полезно очень.

>не существует же, для большинства плюсовиков.
Ты сильно преувеличиваешь число людей, которым есть хоть какое-то дело до линупсов и прочих макосей.

>уже близко
Причём обрати внимание, что 13 лет назад оно уже было так же близко.
А всякие там GCC и комитеты по стандартизации традиционно в позиции догоняющих.

P.S. Вспомнил один пример, когда использовал.
Давно правда, но последнее время я 80% времени программирую на C#, а не на плюсах.
Исходники тут (прямая сцылко на ZIP архив), файл Direct3D_demo\Direct3D9\VertexBuffer9.hpp
В зависимости от того, поддерживает ли класс-параметр GetVertexDeclaration() или GetFVF(), используется один из двух способов описания D3D9 буфера вершин, если ничего, будет assert false.
Понятно, что виртуальные функции бы тоже сработали, или просто 2 разных класса с буфером.
Но оба этих решения усложнили бы использование, потому что это на пустом месте +сущности, про которых должен знать пользователь этого кода.

[thedeemon.livejournal.com]

Ну, я по себе сужу. У меня разные компании библиотеки покупают (сжатие или обработка видео), подавляющему большинству таки нужны и линуксы с макосями тоже. А некоторым только линукс, например.

[soonts.livejournal.com]

Если бы ты делал что-то ещё более низкоуровневое и заточенное на разработчиков, очень оптимизирующий компилятор C к примеру, ты бы щас не только линупсы с макосями поддерживал, а вообще все существующие платформы и ОС.

Есть однако очень большой рынок прикладного ПО.
Которое продаётся отдельно от железок, на которых работает, и прям конечным пользователям делает шо-нибудь полезное.
Разработчикам, которые разрабатывают такое, точно не нужны линупсы, и скорее всего не нужны макоси.

[thedeemon.livejournal.com]

Я сам в том числе как раз пример такого разработчика прикладного ПО чисто под винду. Но есть и другие.
Те мои корпоративные клиенты тоже такие разработчики прикладного ПО, и многие хотят много платформ. Даже китайцы, к которым я недавно летал, которые шаровару для массового пользователя клепают, хотят винду и мак.

[sassa-nf.livejournal.com]

я не совсем понял, каков смысл операции deallocate, когда только один из комбинации аллокаторов её реализует. Partial function же получается.

[thedeemon.livejournal.com]

Допустим, первичный аллокатор это быстрая bump-the-pointer арена без освобождения памяти, вторичный - обычный malloc. Память выделяет один из них, вызывающий код не знает кто именно. Т.к. один из них требует, чтобы память освобождали, для комбинации тоже опредена функция освобождения. Она внутри уже умеет определять, кто из двух выделил данный кусок. Если ей передали память, выделенную первым аллокатором, ареной, то освобождения не делается, это noop. Если память принадлежит второму, вызывается его deallocate, который делает free.

[sassa-nf.livejournal.com]

ну это примерно понятно, моё возражение, что либо должна быть partial (неопределена для P - не no op, а ⊥), либо не говорить тогда, что для P функция deallocate не определена (и, пожалуй, таки не выпендриваться и добавить в P).

[thedeemon.livejournal.com]

А какой практический смысл делать ⊥? Это вредительство.

С deallocate еще можно согласиться, что можно было не мучаться и объявить ее определенной для всех, оставив noop'ом где надо. Но многие другие функции аллокаторов все же имеет смысл различать на уровне типов, поддерживаются или нет.
Хотя даже с deallocate - если информация о том, стоит ли вообще заботиться об освобождении, вынесена в типах на самый верх, то клиентский код может тоже себя довольно по-разному вести, так же сделав static if. Скажем, если у меня контейнер-дерево с некоторым переданным типом-аллокатором, то статическое знание о ненужности деаллокации может сэкономить лишние пусторорожние обходы, которые ни один оптимизатор не выкинет, скорее всего.

[sassa-nf.livejournal.com]

Может быть, но хотелось бы и пример соответствующий.

Смысла делать ⊥ нарочно нет, есть смысл уточнять, что это не ⊥ на самом деле.

Насчёт пустопорожних обходов - зависит от оптимизаторов. dead code elimination таким заниматься должен, и no-op очевидно выбрасывается вместе с пурыми ветками условий / проверок. Конечно, если полиморфизма нет; а если полиморфизм есть, то и тип будет общий. С другой стороны, разве нельзя на уровне типов сказать, что такой-то метод - это юнит (т.е. выразить не отсутствие метода, а существование no-op). Короче, пример нужен.

[juan-gandhi.livejournal.com]

Я тут вижу глобальную проблему, состоящую в том, что в головах теоретиков программирования функтором называется эндофунктор. Надо же разобраться, хм, вот есть другие функторы, вот есть тайпклассы (подкатегории); и чо?

Т.е. проблема-то есть, просто ее надо как-то пограмотнее сформулировать, что ли. А не надеяться на бесплатные теоремы (они примерно как аксиома выбора, по-моему).

[sab123.livejournal.com]

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

[thedeemon.livejournal.com]

Если в крайность кодогенерации вдаваться, придется на себя брать слишком много работы компилятора. Например, о типах в сгенеренном коде придется заботиться самостоятельно, как и о его компилируемости в целом. В D используется симбиоз двух фаз (сгенеренного и генерирующего кода): можно выполнять код во время компиляции и можно при желании генерить код прямо текстом, и тут же его выполнять или делать частью основной программы, но можно и на уровне шаблонов иметь подробную информацию о типах и всякими static if'ами направлять компилятор в нужную сторону, адаптировать код в зависимости от свойств переданных компайл-тайм параметров. В этом случае выводом и проверкой типов в генерируемом коде занимается компилятор, нам эту работу делать не надо, но эта информация доступна уже на этапе кодогенерации.

[swizard.livejournal.com]

В лиспе ещё удобней получается: там макры пишутся том же самом языке, что и основной код. Можно совершенно спокойно использовать обычный "if" вместо всяких "static if" или специализаций шаблонов, или даже обычный ооп с множественной диспетчерезацией.

Грубо говоря, можно аллокаторы представить обычной ооп-иерархией, с полиморфным методом "gen-deallocate": для bump-the-pointer он не сгенерирует ничего, для системного аллокатора там будет сгенерирован "free", а для комбинированного (который описывается обычным классом с двумя полями) будет вызов "gen-deallocate" для основного, и "gen-deallocate" для fallback аллокаторов.

Ну и тд, в этой схеме тривиально добавляется третий fallback в виде свопа, например, да хоть бы дерево аллокаторов — а тайпклассами такое поведение замучаешься программировать. Ну и в D, подозреваю, тоже :)

[thedeemon.livejournal.com]

Дерево аллокаторов как раз у него в библиотеке и строится, там можно большую иерархию накрутить (Heap Building Blocks он это обозвал), и фишка в том, что на уровне типов это статически все выстраивается. Обычной ооп-иерархией любой дурак может, речь-то о том, чтобы иметь статические гарантии, шоб ты не пытался делать realloc там, где аллокатор этого не умеет, например. А со статическими гарантиями в лиспе традиционно никак.

[swizard.livejournal.com]

Да, но статические гарантии такого рода необязательно на типах должны быть. Макрос, код которого раскрывается в assert или error вместо ast тоже сломает компиляцию, но при этом сообщение об ошибке будет в сто раз более внятным :)

Систему типов в языке можно рассматривать как некий DSL, который интерпретируется во время компиляции, проверяя код на непротиворечивость.

А в лиспе вместо этого DSL можно использовать лисп, что круче, потому что это язык общего назначения. Можно хоть в бд во время компиляции сходить и, например, схему проверить на консистентность с кодом — никакая система типов так не позволит.

[thedeemon.livejournal.com]

Прям уж никакая, type providers я как минимум в двух статически типизированных языках видел.

Сообщения об ошибках в D не обязательно оставлять на откуп конпелятору, можно свои выводить (static if ... else pragma(msg, "are you ok?")). Всякая сложная компайл-тайм логика в нем тоже ведь пишется на языке общего назначения, недаром в формуле CTFE присутствует.

[awson.livejournal.com]

Нащет тайпклассов (доклад Александреску не смотрел):

В GHC со времен аж, по-моему, 7.4 есть сonstraint kinds, что делает констрейнты до некоторой степени первоклассными. Так что проблемы со 100500 концептов более-менее нет.

[thedeemon.livejournal.com]

А как именно они тут помогают?

Вот есть функция, использующая 7 функций из 10 от "интерфейса" того же аллокатора. Как можно применить constraint kind, чтобы не перечислять в ней 7 маленьких тайпклассов и не делать нового имени для этого набора?

[awson.livejournal.com]

Перечислить их *так или иначе* придется (какие механизмы не используй, хоть static if'ы, хоть черта лысого -- если вы используете static if'ы, то они так или иначе проверяют наличие каких-то интерфейсов, т.е., вот здесь-то вы их и перечисляете), но это можно сделать composable способом.

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

[yurikravchik.livejournal.com]

C++ напоминает мне это.

Особенно когда в него пытаются добавить новые фичи.

[sleepy-drago.livejournal.com]

А мне кажется забавным баланс отклика от обоих набросов =)