об bounded polymorphism
Jun. 4th, 2015 06:44 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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 делать то или это, а также включать или не включать те или иные операции в определяемый генерик тип. Пример такого подхода:
Тут deallocate - метод некоторого определяемого генерик типа, зависящего от типов-параметров P и F - типов primary и fallback аллокаторов. Если P умеет отличать выделенную им память от чужой (hasMember!(P, "owns")), и хотя бы кто-то из P и F имеет метод deallocate, то тогда только данный метод становится частью описываемого типа. Внутри он определяет, которому из аллокаторов принадлежит освобождаемая память, и вызывает соответствующий метод deallocate, если тот определен. Тут большая пользя от static if еще не очень заметна, то же самое на тайпклассах или концептах могло быть даже проще записано, как две разных функции, но в более сложных примерах, где больше общей логики static if начинает рулить, там разделение разных вариантов по разным реализациям функции привело бы к большому количеству повторяющегося кода.
Само выступление: видео, слайды. В нормальном качестве видео будет позже, пока лишь запись с онлайн стрима.
От себя могу отметить, что с конкретно такой ситуацией, как у него, я особо не сталкивался, но зато было, когда мой контейнер мог иметь разное представление данных и разные дополнительные поля в зависимости от свойств типов-параметров. И там пользу от static if и компайл-тайм интроспекции ощутил хорошо, так что с формулой в целом согласен. На одних бесплатных теоремах, где можно работать с чем угодно, но нельзя с этим чем угодно делать ничего конкретного, далеко не уедешь.
Доклад с названием 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 и компайл-тайм интроспекции ощутил хорошо, так что с формулой в целом согласен. На одних бесплатных теоремах, где можно работать с чем угодно, но нельзя с этим чем угодно делать ничего конкретного, далеко не уедешь.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2015-06-04 05:57 pm (UTC)Т.е. проблема-то есть, просто ее надо как-то пограмотнее сформулировать, что ли. А не надеяться на бесплатные теоремы (они примерно как аксиома выбора, по-моему).