Книга: Основы объектно-ориентированного программирования

Ограниченная универсальность

Расширяя базовое понятие класса, мы представляли наследование и универсальность (genericity) как своего рода "партнеров". Объединить их нам позволило знакомство с полиморфными структурами данных: в контейнер - объект, описанный сущностью типа SOME_CONTAINER_TYPE [T] с родовым параметром T - можно помещать объекты не только самого типа T, но и любого потомка T. Однако есть и другая интересная комбинация партнерства, в которой наследование используется для задания ограничения на возможный тип фактического родового параметра класса.

Вектора, допускающие сложение

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

Предположим, что мы хотим объявить класс VECTOR, над элементами которого определена операция сложения. Потребность в подобном базовом классе неоспорима. Вот первый вариант:

indexing
description: "Векторы со сложением"
class
VECTOR [G]
feature -- Доступ
count: INTEGER
-- Количество элементов
item, infix "@" (i: INTEGER): G is
-- Элемент вектора с индексом i (нумерация с 1)
require ... do
...
end
feature -- Основные операции
infix "+" (other: VECTOR [G]): VECTOR is
-- Поэлементное сложение текущего вектора с other
require ... do
...
end
... Прочие компоненты ...
invariant
non_negative_count: count >= 0
end

Применение инфиксной записи продиктовано соображениями удобства. Для удобства введены и синонимы в обозначении i-го компонента вектора: v.item (i) или просто v @ i.

Обратимся к функции "+". Сначала сложение двух векторов кажется очевидным и состоящим в суммировании элементов на соответствующих местах. Общая его схема такова:

infix "+" (other: VECTOR [G]): VECTOR is
-- Поэлементное сложение текущего вектора с other
require
count = other.count
local
i: INTEGER
do
"Создать Result как массив из count элементов"
from i := 1 until i > count loop
Result.put(item (i) + other.item (i), i)
i := i + 1
end
end

Выражение в прямоугольнике - результат сложения i-го элемента текущего вектора с i-м элементом other. Процедура put сохраняет это значение в i-м элементе Result, и хотя она не показана в классе VECTOR, данная процедура в нем, безусловно, присутствует.

Рис. 16.5.  Поэлементное сложение векторов

Но подобная схема не работает! Операция +, которую мы определили для сложения векторов (VECTOR), здесь применяется к объектам совсем другого типа (G), являющегося родовым параметром. По определению, родовой параметр представлен неизвестным типом - фактическим параметром, появляющимся только тогда, когда нам понадобится для каких либо целей родовой класс. Процесс порождения класса при задании фактического родового параметра называется родовым порождением (generic derivation). Если фактическим параметром служит INTEGER либо иной тип (класс), содержащий функцию infix "+" правильной сигнатуры, корректная работа обеспечена. Но что если параметром станет ELLIPSE, STACK, EMPLOYEE или другой тип без операции сложения?

С прежними родовыми классами: контейнерами STACK, LIST и ARRAY - этой проблемы не возникало, поскольку их действия над элементами (типа G как формального параметра) были универсальны - операции (присваивание, сравнение) могли выполняться над элементами любого класса. Но для абстракций, подобных векторам, допускающих сложение, нужно ограничить круг допустимых фактических родовых параметров, чтобы быть уверенными в допустимости проектируемых операций.

Этот случай отнюдь не является исключением. Вот еще два примера того же рода.

[x]. Предположим, вы проектируете класс, описывающий структуру данных с операцией sort, упорядочивающей элементы структуры в соответствии с некоторым критерием сортировки. Тогда элементы этой структуры должны принадлежать типу, для которого определена операция сравнения infix "<=", задающая порядок для любой пары соответствующих объектов.

[x]. При разработке таких базисных структур данных как словари зачастую используется для хранения данных хеш-таблица, в которой место элемента определяется ключом, вычисляемым по значению элемента. Элементы, размещаемые в словаре должны принадлежать классу, допускающему применение хеш-функции, вычисляющей ключ каждого элемента.

Не ОО-подход

Переходя к решению этой проблемы, посмотрим, как с такой задачей справлялись другие, не ОО-языки.

В языке Ada нет классов, но зато есть пакеты для группировки взаимосвязанных типов и операций. Пакет может быть родовым, с родовыми параметрами, представляющими типы. При этом возникает та же проблема: пакет VECTOR_PROCESSING может включать объявление типа VECTOR и эквивалент нашей функции infix "+".

Решение в языке Ada рассматривает необходимые операции, например инфиксное сложение, как родовые параметры. Параметрами пакета могут быть не только типы, как при объектном подходе, но и подпрограммы. Например:

generic
type G is private;
with function "+" (a, b: G) return G is <>;
with function "*" (a, b: G) return G is <>;
zero: G; unity: G;
package VECTOR_HANDLING is
... Интерфейс пакета ...
end VECTOR_HANDLING

Заметим, что наряду с типом G и подпрограммами родовым параметром служит значение zero - нулевой элемент сложения. Типичное использования пакета:

package BOOLEAN_VECTOR_HANDLING is
new VECTOR_HANDLING (BOOLEAN, "or", "and", false, true);

В этом примере логическая операция or используется как сложение, and - умножение, а также задаются соответствующие значения для zero и unity. Подробнее мы обсудим этот пример в одной из следующих лекций курса.

Являясь решением для Ada, данный прием не применим в объектной среде. Основа ОО-подхода - приоритет типов данных над операциями при декомпозиции ПО, чьим следствием является отсутствие независимых операций. Всякая операция принадлежит некоторому типу данных, основанному на классе. Следовательно, возникшая "на пустом месте" функция, скажем, infix "+", не может быть фактическим родовым параметром, стоящим в одном ряду с типами INTEGER и BOOLEAN. То же касается и значений, таких как zero и unity, обязанных знать свое место - быть компонентами класса - вполне респектабельными членами ОО-сообщества.

Ограничение родового параметра

Эти наблюдения дают решение. Мы должны оперировать исключительно терминами классов и типов.

Потребуем, чтобы любой фактический параметр, используемый классом VECTOR (в других примерах по аналогии), был типом, поставляемым с множеством операций: infix "+", zero для инициализации суммы и т.д. Владея наследованием, мы знаем, как снабдить тип нужными операциями, - нужно просто сделать его потомком класса, отложенного или эффективного, обладающего этими операциями.

Синтаксически это выглядит так:

class C [G -> CONSTRAINING_TYPE] ... Все остальное как обычно ...

где CONSTRAINING_TYPE - произвольный тип, именуемый родовым ограничением (generic constraint). Символ -> обозначает стрелку на диаграммах наследования. Результат этого объявления в том, что:

[x]. в роли фактических родовых параметров могут выступать лишь типы, совместимые с CONSTRAINING_TYPE;

[x]. в классе C над сущностью типа G допускаются только те операции, которые допускаются над сущностью CONSTRAINING_TYPE, другими словами, представляющими собой компоненты базового класса этого типа.

Какое родовое ограничение использовать для класса VECTOR? Обсуждая множественное наследование, мы ввели в рассмотрение NUMERIC - класс объектов, допускающих базисные арифметические операции: сложение и умножение с нулем и единицей (лежащая в его основе математическая структура называется кольцом). Эта модель кажется вполне уместной, хотя нам необходимо пока только сложение. Соответственно, класс будет описан так:

indexing
description: "Векторы, допускающие сложение"
class
VECTOR [G -> NUMERIC]
... Остальное - как и раньше (но теперь правильно!) ...

После чего ранее некорректная конструкция в теле цикла

Result.put(item (i) + other.item (i), i)

становится допустимой, поскольку item (i) и other.item (i) имеют тип G, а значит, к ним применимы все операции NUMERIC, включая, инфиксный "+".

Следующие родовые порождения корректны, если полагать, что все классы, представленные как фактические родовые параметры, являются потомками NUMERIC:

VECTOR [NUMERIC]
VECTOR [REAL]
VECTOR [COMPLEX]

Класс EMPLOYEE не порожден от NUMERIC, так что попытка использовать VECTOR [EMPLOYEE] приведет к ошибке времени компиляции.

Абстрактный характер NUMERIC не вызывает никаких проблем. Фактический параметр при порождении может быть как эффективным (примеры выше), так и отложенным (VECTOR [NUMERIC_COMPARABLE]), если он порожден от NUMERIC.

Аналогично описываются класс словаря и класс, поддерживающий сортировку:

class DICTIONARY [G, H -> HASHABLE] ...
class SORTABLE [G -> COMPARABLE] ...

Игра в рекурсию

Вот некий трюк с нашим примером: спросим себя, возможен ли вектор векторов? Допустим ли тип VECTOR [VECTOR [INTEGER]]?

Ответ следует из предыдущих правил: только если фактический родовой параметр совместим с NUMERIC. Сделать это просто - породить класс VECTOR от класса NUMERIC (см. упражнение 16.2):

indexing
description: "Векторы, допускающие сложение"
class
VECTOR [G -> NUMERIC]
inherit
NUMERIC
... Остальное - как и раньше...

Векторы, подобные этому, можно и впрямь считать "числовыми". Операции сложение и умножение дают структуру кольца, в котором роль нуля (zero) играет вектор из G-нулей, и роль единицы (unity) - вектор из G-единиц. Операция сложения в этом кольце - это, строго говоря, векторный вариант infix "+", речь о котором шла выше.

Можно пойти дальше и использовать VECTOR [VECTOR [VECTOR [INTEGER]]] и так далее - приятное рекурсивное приложение ограниченной универсальности.

И снова неограниченная универсальность

Конечно же, не все случаи универсальности ограничены. Форма - STACK [G] или ARRAY [G] - по-прежнему существует и называется неограниченной универсальностью. Пример DICTIONARY [G, H -> HASHABLE] показывает, что класс одновременно может иметь как ограниченные, так и неограниченные родовые параметры.

Изучение ограниченной универсальности дает шанс лучше понять неограниченный случай. Вы, конечно же, вывели правило, по которому class C [G] следует понимать как class C [G -> ANY]. Поэтому если G - неограниченный типовой параметр (например, класса STACK), а x - сущность, имеющая тип G, то мы точно знаем, что можем делать с сущностью x: читать и присваивать значения, сравнивать (=, /=), передавать как параметр и применять в универсальных операциях clone, equal и прочее.

Оглавление книги