Пишем мультиметоды из Lisp в С++

Что и главное зачем мы собираемся делать?

Начнём с примера, допустим у нас есть интерфейс Animal, который поддерживают классы Cat, Dog, и Frog.

И мы хотим определить операцию interact(взаимодействовать) между двумя Animal.

void interact(Cat, Dog) { std::cout << "fight" << std::endl; } void interact(Dog, Cat) { interact(Cat{}, Dog{}); } void interact(Cat, Frog) { std::cout << "Cat licks Frog" << std::endl; }

Но если мы попробуем это использовать, что возникнет громадная проблема:

void foo(Animal* a, Animal* b) { ??? }

В стандартной библиотеке С++ нет возможности сделать это никак кроме вереницы ‘if’ с dynamic_cast, что просто ужасно и выглядит и работает, к тому же совершенно не масштабируемо, после добавления одной функции достаточно забыть изменить код в других местах и в коде логическая ошибка.

Вы можете сказать — С++17 же есть std::variant! Кажется он решает эту проблему!
И нет, он не решает эту проблему полностью. Во первых использование std::variant предполагает, что вы типы храните в variant, что далеко не всегда так, у вас может быть иерархия на virtual функциях, своя собственная как llvm-type-id или использовано стирание типов. К тому же нужно знать определения всех типов в месте создания variant, что далеко не всегда возможно.

Ну и наконец главная проблема — если подать в visit больше одного варианта, то есть риск схлопнуть вселенную, т.к. сложность компиляции этой конструкции O(N*M*X*…) где N M X это количества типов в вариантах

Вот живой пример: https://godbolt.org/z/633eh11rc

Таким образом, мы хотим на основе динамических типов выбирать во время выполнения программы нужную функцию и вызывать её. Фактически делать runtime overload resolution.

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

В Lisp есть языковая поддержка этого механизма, выглядит это примерно так:

Теперь подумаем, как бы мы вообще могли такое сделать?

Это можно представить как таблицу, где ключ это набор типов аргументов, а значение — указатель на функцию.

Но что такое ключ из типов? Нужно как-то отобразить типы в значение, которое может быть ключом в map.

Тут есть несколько идей:

1. std::type_info — сразу нет. Почему? Потому что эта вещь не гарантирует буквально ничего, .name() полученный из неё согласно стандарту С++ может изменяться от вызова к вызову (!), к тому же нельзя использовать это в constexpr контексте, а мы бы хотели constexpr map<Types, Foo>.

Вариант №2:

template<typename T> constexpr void* type_desc == &type_desc<T>;

Подобное странное рекурсивное определение действительно работает и даёт уникальные указатели для каждого типа, известные на компиляции. Но и тут есть проблемы.

Во-первых операция < на указателях на разные объекты во время компиляции unspecified, поэтому использовать её нельзя.

Во-вторых если мы подключили типы через .dll, то у них этот идентификатор будет другим и мы будем неверно искать функцию в таблице. Поэтому лучшим вариантом является сравнивать типы по их именам, при этом внезапно лучшим способом оказывается использование C-string, потому что нам нужна операция <, которая выполняется для таких строк даже быстрее, чем для string_view. Но это детали, представим что этот тип мы реализовали:

struct descriptor_t {   constexpr descriptor_t(const char* name);   constexpr auto operator<=>(const descriptor_t&); };

Теперь нам остаётся всего ничего:

• достать информацию из функций(перегрузок нашего мультиметода);

• сложить эту информацию в constexpr map<array<descriptor_t, CountArgs>, Foo>;

• потом при вызове генерировать ключ из нескольких descriptor_t, полученных из входных аргументов;

• находить функцию в таблице и вызывать. Если такой функции нет, будем возвращать std::nullopt;

• дополнительное: можно проверять на компиляции и на рантайме const-correctness вызова, что задача нетривиальная, но необходимая.

template <typename Key, typename Value, std::size_t N, typename Compare = std::less<Key>> struct flat_map {  private:   std::array<Key, N> keys;   std::array<Value, N> values;   public:   constexpr flat_map(std::array<std::pair<Key, Value>, N> arr) {     // sort by keys     std::ranges::sort(arr, [](auto& l, auto& r) { return l.first < r.first; });     auto kb = keys.begin();     auto kv = values.begin();     // clang do not supports views like 'keys' now =(     for (auto& [k, v] : arr) {       *kb = k;       *kv = v;       ++kb, ++kv;     }     bool b = false;     assert(b = true);     if (std::is_constant_evaluated() || b) {       auto it = std::unique(keys.begin(), keys.end(),                             [](auto& l, auto& r) { return !Compare{}(l, r) && !Compare{}(r, l); });       if (it != keys.end())         throw "keys are not unique!";     }   }   // its minimal impl, do not support transparent compare   constexpr auto find(const Key& key) const noexcept(requires(Key v) {                                                        { Compare{}(v, v) } noexcept;                                                      }) {     auto it = std::ranges::lower_bound(keys, key, Compare{});     // lower_bound returns such 'it' for which 'key' <= *it, so check if it true, that key < *it     if (it == keys.end() || Compare{}(key, *it))       return values.end();     return std::next(values.begin(), std::distance(keys.begin(), it));   }   constexpr auto end() const noexcept {     return values.end();   } };

template <typename Result, poly_traits Traits, lambda_without_capture... Foos> struct visit_invoke_fn {  private:     template <typename F>   static constexpr std::pair<key_type, value_type> make_key_value_pair_for() noexcept {     return []<typename... Ts>(aa::type_list<Ts...>) {       return std::pair{key_type{descriptor_v<Ts>...}, &match_invoker<F, Ts...>};     }(typename traits<F>::all_args{});  // INVOKED HERE   }   public:   constexpr explicit visit_invoke_fn(Traits t = Traits{}) noexcept       : map({make_key_value_pair_for<Foos>()...}), poly_traits(std::move(t)) {     struct signatures_must_be_unique_after_decay : traits<Foos>::decay_args... {     } _; // применяем трюк чтобы компилятор проверил, что сигнатуры функций уникальны // если они не уникальны, то класс будет иметь больше 1 базы такого же типа, // что является ошибкой компиляции     (void)_;   }

Теперь напишем главный метод .resolve, выполняющий разрешение перегрузки на рантайме,
(в коде опущены все проверки для простоты).

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

Это позволяет поддерживать любые возможные пользовательские полиморфные иерархии:

  template <typename... Args>   std::optional<result_type> resolve(Args&&... args) const {     key_type key{poly_traits.get_type_descriptor(args)...};     auto it = map.find(key);     if (it == map.end()) [[unlikely]]       return std::nullopt; // заранее мы стёрли тип функции до состояния Ret(*)(array<void*, N>), // чтобы хранить их в одном конейнере     return (*it)({poly_traits.to_address(args)...});   }

А теперь время использовать это!

struct spaceship; struct asteriod; struct star;  std::string ship_asteroid(spaceship s, asteroid a); std::string ship_star(spaceship s, star); std::string star_star(star a, star b); std::string ship_ship(spaceship a, spaceship b);  // Create multidispatcher constexpr inline auto collision = aa::make_visit_invoke< // с С++20 можно использовать здесь и лямбды, но так выглядит проще   ship_asteroid,   ship_star,   star_star,   ship_ship >(); ... // Perform runtime overload resolution std::optional<std::string> foo(any_with<A> a, any_with<B> b) {   return collision.resolve(a, b); }

Итоги

Мы добились возможности писать мультиметоды, так что они эффективнее и удобнее и лучше мастштабируются, чем куча if или std::visit, наша реализация разрешает перегрузку за O(1) от количества возможных типов(то есть не зависит от их количества, в отличие от std::visit), также этот способ может быть использован не только с variant, но и с любыми другими полиморфными типами — один из них кстати any_with<…>, используемый в примере.

Разумеется в статью не влезли все возможности, и подробности, поэтому если вы заинтересованы, то всегда можете посмотреть исходный код здесь: https://github.com/kelbon/AnyAny