Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 19
Меня интересует использование мультиметодов в Obj-C проектах. Реально ли? Речь, скорее, не о Obj-C, а чистом Си.
Т.е допустим у меня есть 50 типов обьектов и их столкновение хотелось бы обрабатывать в сишных функциях методом «мультиметодов». Ну и конечно же наиболее быстрым и наиболее удобным с точки зрения кодинга способом (и, как мне показалось, мне нужно смотреть в сторону мультиметодов). Конечно же на самом деле речь не о столкновениях. :)
Т.е допустим у меня есть 50 типов обьектов и их столкновение хотелось бы обрабатывать в сишных функциях методом «мультиметодов». Ну и конечно же наиболее быстрым и наиболее удобным с точки зрения кодинга способом (и, как мне показалось, мне нужно смотреть в сторону мультиметодов). Конечно же на самом деле речь не о столкновениях. :)
На чистом C, к сожалению, будет гораздо сложнее. Да и на C++ оказалось все очень непросто. Но в C++ удалось сделать многое на шаблонах так, чтобы внешне для пользователя все выглядело привлекательно. Для C мне приходит в голову только 2-мерная матрица указателей на функции + к этому прикрутить полиморфизм, RTTI, регистрировать методы в этой матрице и диспетчить по ней вызовы в зависимости от типа аргументов. Все это геморно с точки зрения и реализации и использования, и выглядеть будет коряво. Лучше уж генератор кода писать
На Obj-C никогда не писал, но слышал, что там вызов метода реализован через диспетчер внутри объекта. Если можно переопределять диспетчер, то с этим можно поиграться.
На Obj-C никогда не писал, но слышал, что там вызов метода реализован через диспетчер внутри объекта. Если можно переопределять диспетчер, то с этим можно поиграться.
Фундаментально, прочитал с удовольствием!
Не часто встретишь такие труды.
Не часто встретишь такие труды.
Есть вопрос(ы):
Каким образом мультиметод узнает иерархию классов? Предположим, есть базовый класс Base, от него наследуется Foo, а от Foo наследуется Bar. Каким образом мультиметод определяет правильный порядок?
И еще второй вопрос, у мультиметода в данном примере нету ничего кроме game_object и зарегистрированных функций. Т.е. единственное откуда можно взять список возможных параметров это тот список функций, которые мы передаем в качестве параметров при создании мультиметода, так? Но как?
inline const char* collide(game_object* obj1, game_object* obj2)
{
if (space_ship* sh1 = dynamic_cast<space_ship*>(obj1))
if (space_ship* sh2 = dynamic_cast<space_ship*>(obj2))
return collide_sh_sh(sh1, sh2);
else if (asteroid* as2 = dynamic_cast<asteroid*>(obj2))
return collide_sh_as(sh1, as2);
else
return collide_go_go(sh1, obj2);
Каким образом мультиметод узнает иерархию классов? Предположим, есть базовый класс Base, от него наследуется Foo, а от Foo наследуется Bar. Каким образом мультиметод определяет правильный порядок?
И еще второй вопрос, у мультиметода в данном примере нету ничего кроме game_object и зарегистрированных функций. Т.е. единственное откуда можно взять список возможных параметров это тот список функций, которые мы передаем в качестве параметров при создании мультиметода, так? Но как?
Вы правы, именно из параметров целевых функций, которые передаются в мультиметод, выводятся типы аргументов. Правильный порядок определяется сортировкой типов по предикату is_base_and_derived (он как и остальные параметры задан по-умалчанию, неявно) для каждого аргумента в порядке от роизводного к базовому. Все эти манипуляции происходят во время компиляции. Почти весь код библиотеки является кодом времени компиляции. Производится статическая интроспекция кода с помощью метапрограммирования. Я пока намеренно не пишу о реализации, вводная статья и так получилась раздутой. Если касаться реализации, то писать придется очень много. В либе 57 файлов весом 180 КБ сплошного шаблонного метапрограммирования.
Кстати, а что происходит, если при диспетчеризации мультиметода возникает неоднозначность? ( <*,asteroid> vs <asteroid,*> при вызове с <asteroid,asteroid>).
В конечном итоге после выявления реальных типов происходит вызов целевой перегруженной функции по правилам обычной перегрузки языка C++, то есть Вы получите ошибку компиляции с сообщением о неоднозначности.
Спасибо, за вопрос, я об этом забыл упомянуть. Добавлю к статье.
Спасибо, за вопрос, я об этом забыл упомянуть. Добавлю к статье.
А если неоднозначность нельзя детектировать в компайлтайме? Например мы одновременно отнаследовались от asteroid и space_ship.
Я немного не понял Вас. Приведите пример, пожалуйста. Рассматривайте мультиметод так:
сначала каждый аргумент приводится к самому последнему производному типу в иерархии, затем вызывается статически перегруженная функция компилятором по полученным типам аргументов, согласно правилам перегрузки (это ничего, что имена функций в примере разные, они все равно внутри объединяются в один функтор с перегруженным operator() для каждой функции).
Понятно, что не может быть сначала динамический поиск типа, а затем статическая перегрузка. Во время компиляции закомпиливаются все возможные вариации типов аргументов, которые потенциально могут быть преобразованы из входящих базовых типов. То есть во время компиляции строятся двоичное дерево if (cast)-else (можно посмотреть любой псевдокод из приведенных примеров).
Пример про неоднозначность:
не даст ошибки неоднозначности, т.к. скомпилируется в:
Представив мультиметод в виде дерева if-else очень просто понять его механизм.
Более усложнив пример, можно добиться неоднозначности, но ее будет просто разрешить, вводя дополнительные целевые функции. Вообще, лучше рассматривать реальные примеры.
сначала каждый аргумент приводится к самому последнему производному типу в иерархии, затем вызывается статически перегруженная функция компилятором по полученным типам аргументов, согласно правилам перегрузки (это ничего, что имена функций в примере разные, они все равно внутри объединяются в один функтор с перегруженным operator() для каждой функции).
Понятно, что не может быть сначала динамический поиск типа, а затем статическая перегрузка. Во время компиляции закомпиливаются все возможные вариации типов аргументов, которые потенциально могут быть преобразованы из входящих базовых типов. То есть во время компиляции строятся двоичное дерево if (cast)-else (можно посмотреть любой псевдокод из приведенных примеров).
Пример про неоднозначность:
struct C : asteroid, space_ship {};
typedef void f1_type(game_object*);
typedef void f2_type(C*);
void f(game_object*);
void f(C*);
game_object* go;
auto mm = make_multimethod((f1_type*)f, (f2_type*)f);
mm(go);
не даст ошибки неоднозначности, т.к. скомпилируется в:
if (C* c = dynamic_cast<C*>(go)) // dynamic_cast способен производить downcast по ромбовидным иерархиям
f(c); // нет неоднозначности, разрешение перегрузки в void f(C*)
else
f(go); // нет неоднозначности, разрешение перегрузки в void f(game_object*);
Представив мультиметод в виде дерева if-else очень просто понять его механизм.
Более усложнив пример, можно добиться неоднозначности, но ее будет просто разрешить, вводя дополнительные целевые функции. Вообще, лучше рассматривать реальные примеры.
Допустим «специализации» мультиметода для C нет, есть только варианты для asteroid и space_ship. Если мультиметод где-то вызывается с C, то мы узнаем о неоднозначности в компайлтайме. Представим теперь, что мультиметод никогда явно с C не вызывается (допустим типы фактических аргументов — всегда ссылка на game_object).
Если я правильно понял ваши объяснения, для C в рантайме будет вызван либо вариант для asteroid либо для space_ship, причем выбор скорее всего случайный, так как asteroid и space_ship не связаны наследованием.
Если я правильно понял ваши объяснения, для C в рантайме будет вызван либо вариант для asteroid либо для space_ship, причем выбор скорее всего случайный, так как asteroid и space_ship не связаны наследованием.
Да, Вы все верно поняли. Так и есть: в первом варианте ошибка компиляции, во втором варианте выбор будет не то, чтобы случайным, а в зависимости от сортировки типов. Но, как вы правильно заметили, asteroid и space_ship не связаны наследованием, поэтому сортировка типов может их расположить как угодно, можно считать что случайным (implementation specific) образом.
Но это только в примитивном, базовом использовании мультиметода. Есть механизмы, о которых я позже расскажу, которые позволяют вместо неявного формирования списка типов, вручную указать список типов, к которым будут приводиться аргументы. Тогда можно будет ввести вручную тип C и получить ту же ошибку компиляции во втором случае.
Вернее наоборот, более общий класс dispatcher требует ручного ввода списка типов. А multimethod — это фасад к нему, который автоматически этот список формирует.
Но это только в примитивном, базовом использовании мультиметода. Есть механизмы, о которых я позже расскажу, которые позволяют вместо неявного формирования списка типов, вручную указать список типов, к которым будут приводиться аргументы. Тогда можно будет ввести вручную тип C и получить ту же ошибку компиляции во втором случае.
Вернее наоборот, более общий класс dispatcher требует ручного ввода списка типов. А multimethod — это фасад к нему, который автоматически этот список формирует.
Можно сказать, что серьезно не думал, но мечтал. Целиком до буста ей еще расти и расти, в особенности, нужно все жестко формализовать. Но вот внутри есть несколько самостоятельных суб-библиотек, которых в бусте нет, которые я позже опишу. Возможно они бы пригодились там. Это overloaded_function и compressed_tuple
Хотя, народ не дремлет, и, пока моя реализация пылилась несколько лет, в последней версии буста уже опубликовали overloaded_function, даже названия такие же, правда в несколько ином виде.
Там функция полиморфно скрывает свои составляющие компоненты, а у меня, наоборот, открыты для статического встраивания. Можно навесить полиморфную обертку и моя реализация будет идентична бустовой, только по размерам в разы меньше.
boost::overloader_function из-за тривиальной реализации весит n*sizeof(boost::function), n — количество перегрузок. На MSVC boost::overloaded_function перегруженная 5-ю функторами весит 5*16 = 80 байт и имеет солидный оверхед при вызове. Аналогичная mml::overloaded_function весит 1 байт и имеет нулевой оверхед (полностью встраивается). Наверное, нужно сделать сравнительный анализ.
Хотя, народ не дремлет, и, пока моя реализация пылилась несколько лет, в последней версии буста уже опубликовали overloaded_function, даже названия такие же, правда в несколько ином виде.
Там функция полиморфно скрывает свои составляющие компоненты, а у меня, наоборот, открыты для статического встраивания. Можно навесить полиморфную обертку и моя реализация будет идентична бустовой, только по размерам в разы меньше.
boost::overloader_function из-за тривиальной реализации весит n*sizeof(boost::function), n — количество перегрузок. На MSVC boost::overloaded_function перегруженная 5-ю функторами весит 5*16 = 80 байт и имеет солидный оверхед при вызове. Аналогичная mml::overloaded_function весит 1 байт и имеет нулевой оверхед (полностью встраивается). Наверное, нужно сделать сравнительный анализ.
Как видно, накладные расходы во время выполнения представлены в лучшем случае 2-мя dynamic_cast, в худшем — 4-мя.
Правильно ли я понимаю, что производительность такого решения будет значительно ниже, чем если бы реализация была встроена в язык, например, с помощью vtables? Более того, на сколько я понял, эта реализация имеет сложность в рантайме O(ln(n)), где n — число комбинаций из количества перегрузок по два? Vtable реализация теоретически могла бы иметь сложность O(1), — один переход по ключу ID<pair<type1,type2>>?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Мультиметоды в C++. Библиотечная реализация. Введение в MML