Многосортные алгебры, полиморфизм, шаблоны и обобщения перегрузки (original) (raw)

Этот пост касается поддержки многосортных алгебр на уровне языка в C++, а также переднего края современных методологий проектирования ПО.

Александр Степанов (автор STL) в своём предисловии к книге C++ Boost Graph Library [1] (библиотека для обработки графов в колекции библиотек Boost для C++) указывает на один интересный момент относительно вывода аргументов шаблонов в C++. Вместо его примера я возьму алгоритм std::accumulate из стандартной библиотеки шаблонов C++.

template< typename T, typename InputIterator > T std::accumulate( InputIterator begin, InputIterator end, T value ) { while( begin != end ) value += *begin++; return value; }

Речь идёт вот о чём. Компилятор не может при проверке типов формальных параметров для std::accumulate() убедиться, что в результате разыменования объекта класса InputIterator (т.е. применения к нему оператора *) должен получиться тип T. Конечно если вызвать std::accumulate() с тремя параметрами типа int, получим сообщение об ошибке, но оно будет далеко не очевидным для пользователя. Это известная проблема обобщённого программирования, и, в частности, библиотеки Loki.
(Герб Саттер в своей книге Exceptional C++ Style [2] в параграфе 36 указывает на то, что, например, Intel C++ Compiler 7.1 из-за неполного соответствия стандарту не собирает реализацию Андрея Александреску обобщения концепции объединений (union), выдавая 430 Кб диагностических сообщений на 5 строк кода).

Так вот, вернёмся к [1]. Степанов пишет: "Требования к итераторам сформулированы только на словах. Мы пытаемся программировать с концепциями (многосортными алгебрами) на языке, в котором для них нет поддержки."
Для решения проблемы Степанов предлагает расширить синтаксис языка, чтобы эти предусловия формулировались как часть сигнатуры функции, вот так:

template< typename T, typename InputIterator > T std::accumulate( InputIterator begin, InputIterator end, T value ) ( value_type(InputIterator) == T ) { while( begin != end ) value += *begin++; return value; }

Теперь мои мысли. Зачем ограничиваться статическими проверками, которые действуют только при проверке типов параметров и разрешении перегрузки (overload resolution)?
В эти списки (назовём их предусловиями) можно добавлять и динамические проверяемые условия, например:

void F( BaseClass* obj, int ) ( typeof(obj) == typeof(DerivedClass*) ) { }

или

void F( BaseClass* obj, int ) ( obj->TypeField == TF_BASE_CLASS ) { }

Таким образом, полиморфизм (в классическом объектно-ориентированном программировании) становится частным случаем этой концепции. Другим частным случаем становится мультиполиморфизм (с реализацией которого через шаблоны долго извращался Андрей Александреску, и его решение не назовёшь кратким и красивым).

Пусть есть класс Figure, и производные от него Circle, Triangle и Rectangle. Необходимо написать функцию, которая считает площадь пересечения пары фигур. Ясно, что формулы будут различаться для каждой пары типов фигур. Новый синтаксис позволяет решить эту проблему, вводя полиморфизм по двум аргументам функции:

// -- figure.h double GetIntersectionArea( Figure*, Figure* ); // -- circle.h double GetIntersectionArea( Figure* fig1, Figure* fig2 ) ( dynamic_cast< Circle* >(fig1) != 0 && dynamic_cast< Circle* >(fig1) != 0 ) { return formula1( fig1, fig2 ); } double GetIntersectionArea( Figure* fig1, Figure* fig2 ) ( dynamic_cast< Circle* >(fig1) != 0 && dynamic_cast< Triangle* >(fig1) != 0 ) { return formula2( fig1, fig2 ); } double GetIntersectionArea( Figure* fig1, Figure* fig2 ) ( dynamic_cast< Circle* >(fig1) != 0 && dynamic_cast< Rectangle* >(fig1) != 0 ) ) { return formula3( fig1, fig2 ); } // -- rectangle.h ...

В этом и заключается многосортность алгебры операций над Circle, Triangle, Rectangle: алгебра содержит n-арную операцию над общим типом Figure, которые полиморфны (-сортны) по нескольким аргументам одновременно.

Сила концепции очевидна - полиморфизм и перегрузка функций, а также специализация шаблонов - это её частные случаи.

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

Компилятор для построения такого дерева должен уметь вычислять два отношения между предусловиями:

Частный случай. Например ( a == 1 && b == 1 ) - частный случай ( a == 1 ), что, в свою очередь, частный случай ( a >= 1 ).
Взаимное исключение (непересечение). Например - ( a == 1 ) и ( a == 2 ), ещё пример - ( a == 0 && b > 0 ) и ( a > 0 && b == 0 ).

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

Мне кажется, этого более чем достаточно. Кто что думает по этому поводу?