Обобщенное программирование

Обобщённое программирование рассматривается как методология программирования, основанная на разделении структур данных и алгоритмов через использование абстрактных описаний требований. Абстрактные описания требований являются расширением понятия абстрактного типа данных. Вместо описания отдельного типа в обобщённом программировании применяется описание семейства типов, имеющих общий интерфейс и семантическое поведение. Набор требований, описывающий интерфейс и семантическое поведение, называется концепцией (англ. concept). Таким образом, написанный в обобщённом стиле алгоритм может применяться для любых типов, удовлетворяющих его своими концепциями. Такая возможность называется полиморфизмом.

Говорят, что тип моделирует концепцию (является моделью концепции), если он удовлетворяет её требованиям. Концепция является уточнением другой концепции, если она дополняет последнюю. Требования к концепциям содержат следующую информацию:

Допустимые выражения (англ. valid expressions) — выражения языка программирования, которые должны успешно компилироваться для типов, моделирующих концепцию.

Ассоциированные типы (англ. associated types) — вспомогательные типы, имеющие некоторое отношение к моделирующему концепцию типу.

Инварианты (англ. invariants) — характеристики типов времени исполнения, которые должны быть постоянно верны. Обычно выражаются в виде предусловий и постусловий. Невыполнение предусловия влечёт непредсказуемость соответствующей операции и может привести к ошибкам.

Гарантии сложности (англ. complexity guarantees) — максимальное время выполнения допустимого выражения или максимальные требования к различным ресурсам в ходе выполнения этого выражения.

В C++ ООП реализуется посредством виртуальных функций и наследования, а ОП — с помощью шаблонов классов и функций. Тем не менее, суть обеих методологий связана с конкретными технологиями реализации лишь косвенно. Говоря более формально, ООП основано на полиморфизме подтипов, а ОП — на параметрическом полиморфизме. В других языках то и другое может быть реализовано иначе. Например, мультиметоды в CLOS имеют сходную с параметрическим полиморфизмом семантику.

Массер и Степанов выделяют следующие этапы в решении задачи по методологии ОП:

Найти полезный и эффективный алгоритм.

Определить обобщённое представление (параметризовать алгоритм, минимизировав требования к обрабатываемым данным).

Описать набор (минимальных) требований, удовлетворяя которые всё ещё можно получить эффективные алгоритмы.

Создать каркас на основе классифицированных требований.

Минимизация и создание каркаса ставят целью создание такой структуры, при которой алгоритмы не зависят от конкретных типов данных. Этот подход отражён в структуре библиотеки STL.

Альтернативный подход к определению обобщённого программирования, который можно назвать обобщённым программированием типов данных (англ. datatype generic programming), был предложен Ричардом Бёрдом и Ламбертом Меертенсом. В нём структуры типов данных являются параметрами обобщённых программ. Для этого в язык программирования вводится новый уровень абстракции, а именно параметризация по отношению к классам алгебр с переменной сигнатурой. Хотя теории обоих подходов не зависят от языка программирования, подход Массера — Степанова, делающий упор на анализ концепций, сделал C++ своей основной платформой, тогда как обобщённое программирование типов данных используют почти исключительно Haskell и его варианты.

Средства обобщённого программирования реализуются в языках программирования в виде тех или иных синтаксических средств, дающих возможность описывать данные (типы данных) и алгоритмы (процедуры, функции, методы), параметризуемые типами данных. У функции или типа данных явно описываются формальные параметры-типы. Это описание является обобщённым и в исходном виде непосредственно использовано быть не может.

В тех местах программы, где обобщённый тип или функция используется, программист должен явно указать фактический параметр-тип, конкретизирующий описание. Например, обобщённая процедура перестановки местами двух значений может иметь параметр-тип, определяющий тип значений, которые она меняет местами. Когда программисту нужно поменять местами два целых значения, он вызывает процедуру с параметром-типом «целое число» и двумя параметрами — целыми числами, когда две строки — с параметром-типом «строка» и двумя параметрами — строками. В случае, с данными программист может, например, описать обобщённый тип «список» с параметром-типом, определяющим тип хранимых в списке значений. Тогда при описании реальных списков программист должен указать обобщённый тип и параметр-тип, получая, таким образом, любой желаемый список с помощью одного и того же описания.

Не нашли, что искали? Воспользуйтесь поиском: