Универсальность и (versus) наследование

Последующий материал и его появление в приложении требует некоторых пояснений. Начальным толчком, приведшим в итоге к появлению этой книги, было исследование, проведенное в 1984 году при подготовке курса для студентов " Концепции в языках программирования ", в котором я сравнивал "горизонтальный" механизм универсальности с "вертикальным" механизмом наследования, введенным в Simula. Первый механизм модульного расширения рассматривался на примере родовых языков, таких как Ada, Z, LPG. Анализировалось, чем отличаются эти техники, в чем они соревнуются, в чем дополняют друг друга. Это привело к статье с одноименным данному приложению названием [M1986], представленной на конференции OOPSLA, и к главе в первом издании этой книги.

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

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

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

Универсальность

Начнем с оценки достоинств универсальности, присутствующей в различных языках. Для удобства будет использована нотация самого известного не объектно-ориентированного языка с поддержкой универсальности - Ada, точнее Ada 83. Так что в оставшейся части этого раздела на минуточку забудьте о ОО-языках и соответствующей технике.

Будем рассматривать только наиболее важную форму универсальности Ada - параметризацию типа, возможность параметризации программных элементов (в языке Ada это пакет или подпрограмма) одним или более типами. Родовые параметры имеют и другое, менее важное использование в Ada, допуская параметризацию размерности массивов. Будем также отличать неограниченную универсальность ( unconstrained genericity) и ограниченную ( constrained genericity), накладывающую ограничения на родовые параметры.

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

Неограниченная универсальность частично ослабляет жесткий статический контроль типов. Тривиальный пример - подпрограмма обмена значений двух переменных (на языке, подобном Ada, но без явных объявлений типов):

procedure swap (x, y) is
local t;
begin
    t := x; x := y; y := t;
end swap;

В этой форме не специфицируются типы обмениваемых элементов и локальной переменной t. Здесь слишком много свободы, так вызов swap (a, b), где a имеет тип integer, а b - character string, не будет отвергнут, хотя и приведет к ошибке.

Для устранения этой проблемы статически типизируемые языки, такие как Pascal и Ada, требуют от разработчиков явного задания типов всех переменных и формальных аргументов и вводят статически проверяемое ограничение на совместимость типов формальных и фактических аргументов в вызовах подпрограмм и между целью и источником при присваиваниях. Процедура, обменивающая значения двух переменных типа G, в этом случае принимает вид:

procedure G_swap (x, y: in out G) is
    t: G;
begin
    t := x; x := y; y := t;
end swap;

Требование определенности типа G предотвращает ошибки несовместимости, но в постоянном споре между безопасностью и гибкостью пострадала гибкость в угоду безопасности. Теперь для элементов каждого типа необходима новая процедура, например INTEGER_swap, STRING_swap и так далее. Такие множественные объявления удлиняют и затеняют программы. Выбранный пример особенно показателен, так как все объявления подобных процедур будут отличаться лишь двумя вхождениями G.

Статическая типизация в данном случае накладывает избыточные ограничения. Единственное реальное требование - идентичность типов фактических параметров и локальной переменной t. Конкретный тип не имеет значения.

Универсальность обеспечивает компромисс между избыточной свободой бестиповых языков и излишней строгостью, свойственной Pascal. В родовых языках можно объявить G как родовой параметр процедуры swap или охватывающего модуля. Язык Ada предлагает как родовые подпрограммы, так и родовые пакеты, описанные в лекции 15 курса "Основы объектно-ориентированного проектирования". На квази-Ada можно написать так:

generic
    type G is private;
procedure swap (x, y: in out G) is
    t: G;
begin
    t := x; x := y; y := t;
end swap;

Единственное отличие от реальной записи на Ada выражается в необходимости отделения интерфейса от реализации. Поскольку скрытие информации несущественно для обсуждения в этой лекции, интерфейсы и реализации объединены для простоты представления.

Предложение generic... вводит тип в качестве параметра. Определяя G как "private", автор процедуры позволяет применять к сущностям типа G (x, y, t) операции, применимые ко всем типам, такие как присваивание или сравнение, и только их.

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

procedure int_swap is new swap (INTEGER);
procedure str_swap is new swap (STRING);

и т. д. Если теперь i и j переменные типа INTEGER, а s и t - STRING, то из следующих вызовов:

int_swap (i, j); str_swap (s, t);
int_swap (i, s); str_swap (s, j); str_swap (i, j);

допустимы только два первых, а остальные будут отклонены компилятором.

Параметризованные пакеты интереснее подпрограмм. Немного модифицировав пример стека, рассмотрим пакет, задающий очередь, в котором определены основные операции: добавление и удаление элемента, получение его значения и т. д. Интерфейс пакета:

generic
    type G is private;
package QUEUES is
    type QUEUE (capacity: POSITIVE) is private;
    function empty (s: in QUEUE) return BOOLEAN;
    procedure add (t: in G; s: in out QUEUE);
    procedure remove (s: in out QUEUE);
    function oldest (s: in QUEUE) return G;
private
    type QUEUE (capacity: POSITIVE) is
            -- Пакет использует массив для представления очереди
        record
            implementation: array (0 .. capacity) of G;
            count: NATURAL;
        end record;
end QUEUES;

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

package INT_QUEUES is new QUEUES (INTEGER);
package STR_QUEUES is new QUEUES (STRING);

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

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

Зачастую универсальное определение имеет смысл, только если фактические параметры удовлетворяют некоторым условиям. Эту форму можно назвать ограниченной универсальностью.

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

Примеры ограниченной универсальности будут включать подпрограмму и пакет, как и в предыдущем случае.

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

generic
    type G is private;
function minimum (x, y: G) return G is begin
        if x <= y then return x; else return y; end if;
end minimum;

Такое объявление функции имеет смысл только для таких типов G, для которых определена операция сравнения "<=". При статическом контроле типов соответствие этому требованию необходимо проверить на этапе компиляции, не дожидаясь выполнения. Нужен способ проверки того, поддерживается ли данная операция для типа G.

В Ada сама операция <= трактуется как родовой параметр. Синтаксически, операция - это функция, которую можно вызывать, используя обычную инфиксную форму, если в объявлении ее имя размещено в двойных кавычках - " <= ". Следующее объявление становится допустимым в Ada, объединив интерфейс и реализацию.

generic
    type G is private;
    with function "<=" (a, b: G) return BOOLEAN is <>;
function minimum (x, y: G) return G is begin
        if x <= y then return x; else return y end if;
end minimum;

Ключевое слово with вводит родовые параметры, представляющие подпрограммы, аналогичные " <= ".

Родовое порождение minimum можно выполнить для любого типа T1, если для него определена функция T1_le с сигнатурой: function (a, b: T1) return BOOLEAN.

function T1_minimum is new minimum (T1, T1_le);

Если функция T1_le действительно называется " <= ", точнее, если ее название и сигнатура соответствуют шаблону, то ее включение в список фактических параметров не требуется. Так, поскольку тип INTEGER имеет предопределенную функцию " <= " с правильной сигнатурой, то можно просто объявить:

function int_minimum is new minimum (INTEGER);

Такое использование заданных по умолчанию подпрограмм с соответствующими именами и типами возможно благодаря предложению is <> в объявлении формальной подпрограммы. Разрешенная и фактически поощряемая в Ada перегрузка операций играет существенную роль, и функция " <= " определена для различных типов.

От обсуждения ограниченной универсальности для подпрограмм легко перейти к пакетам. Предположим, что требуется универсальный пакет для работы с матрицами объектов любого типа G, где над матрицами определены операции суммирования и умножения. Такое определение имеет смысл, только если эти операции определены для типа G и каждая из этих операций имеет нулевой элемент. Эти свойства необходимы для реализации операций над матрицами. Интерфейсная часть пакета может быть написана следующим образом:

generic
    type G is private;
    zero: G;
    unity: G;
    with function "+"(a, b: G) return G is <>;
    with function "*"(a, b: G) return G is <>;
package MATRICES is
    type MATRIX (lines, columns: POSITIVE) is private;
    function "+"(m1, m2: MATRIX) return MATRIX;
    function "*"(m1, m2: MATRIX) return MATRIX;
private
    type MATRIX (lines, columns: POSITIVE) is
        array (1 .. lines, 1 .. columns) of G;
end MATRICES;

Вот типичные родовые порождения:

package INTEGER_MATRICES is new MATRICES (INTEGER, 0, 1);
package BOOLEAN_MATRICES is
    new MATRICES (BOOLEAN, false, true, "or", "and");

Для типа INTEGER опущены фактические параметры + и *, поскольку определены соответствующие операции. Однако их пришлось явно указать в случае BOOLEAN. (Параметры, опускаемые по умолчанию, лучше всего помещать в конец списка формальных параметров.)

Интересно рассмотреть реализацию такого пакета:

package body MATRICES is
    ... Остальные объявления ...
    function "*"(m1, m2: G) is
        result: MATRIX (m1'lines, m2'columns);
    begin
        if m1'columns /= m2'lines then
            raise incompatible_sizes;
        end if;
        for i in m1'RANGE(1) loop
            for j in m2'RANGE(2) loop
                result (i, j):= zero;
                for k in m1'RANGE(2) loop
                    result (i, j):= result (i, j) + m1 (i, k) * m2 (k, j)
                end loop;
            end loop;
        end loop;
        return result
    end "*";
end MATRICES;

В этом фрагменте использованы некоторые специфические особенности Ada:

Приведенные примеры демонстрируют реализацию ограниченной универсальности в Ada. Они также показывают серьезные ограничения этой техники: выразимы только синтаксические ограничения. Программист может потребовать только существования некоторых подпрограмм ( <=, +, * ) с заданной сигнатурой, но, если эти подпрограммы не удовлетворяют семантическим ограничениям, эти объявления становятся бессмысленными. Функция minimum имеет смысл, только если <= является отношением полного порядка на G. Для родового порождения MATRICES с заданным типом G, следует быть уверенным, что операции + и * имеют не только сигнатуру G x G -> G, но обладают и подходящими свойствами - ассоциативности, дистрибутивности, имеют нулевой элемент. Мы можем использовать математический термин "кольцо" для структур, обладающих этими свойствами.

Наследование

Теперь от универсальности в чистом виде можно перейти к наследованию. Для сравнения его с универсальностью рассмотрим пример из стандартной библиотеки для работы с файлами. Начнем с эскиза реализации "специальных файлов" в смысле Unix, то есть файлов, связанных с устройствами:

class DEVICE feature
    open (file_descriptor: INTEGER) is do ... end
    close is do ... end
    opened: BOOLEAN
end

Пример использования этого класса:

d1: DEVICE; f1: INTEGER; ...
create d1.make; d1.open (f1);
if d1.opened then ...

Теперь рассмотрим понятие ленточного накопителя. Это устройство обладает всеми свойствами, представленными в классе DEVICE, плюс способность перематывать ленту. Вместо формирования нового класса на пустом месте можно использовать наследование и объявить класс TAPE, расширяя и модифицируя DEVICE. Новый класс расширяет DEVICE, добавляя новую процедуру rewind в соответствии с особенностями именно ленточных устройств. Кроме того необходима новая версия open, модифицированная с учетом специфики накопителей на магнитной ленте.

Объекты типа TAPE автоматически обладают всеми свойствами объектов DEVICE плюс их собственные (перемотка). Придется модифицировать ряд компонентов DEVICE в классе TAPE (open) и добавить новые ( rewind ). Класс DEVICE может иметь и других потомков, например класс DISK с его собственными специфическими особенностями прямого доступа.

Наследованию сопутствует полиморфизм, разрешая присваивания x:= y, если тип x - предок типа y. Следующая особенность - динамическое связывание: если x устройство, то вызов x.open (f1) будет выполнен различным образом в зависимости от значения присвоенного x перед вызовом. После присваивания x := y, где y - лента, будет выполнена версия открытия для ленты.

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

Далее следуют отложенные компоненты и классы. Нужно отметить, что устройства Unix являются файлами специального типа, поэтому приведен граф наследования, в данном случае дерево наследования.

Открыть и закрыть можно любой файл, но способ выполнения этих операций зависит от того, является ли файл устройством, подкаталогом и т. д. Следовательно, FILE - абстрактный класс с отложенными подпрограммами open и close, реализация которых возлагается на потомков:

deferred class FILE feature
    open (file_descriptor: INTEGER) is deferred end
    close is deferred end;
end

Эффективные потомки FILE обеспечат реализацию open и close.

Эмуляция наследования с помощью универсальности

Являются ли наследование и универсальность взаимозаменяемыми? Давайте рассмотрим возможность эмуляции каждой из этих техник средствами другой техники.

Рассмотрим сначала язык, подобный Ada (Ada 83), с поддержкой универсальности, но не наследования. Что можно сделать в этом случае для достижения эффекта наследования?

Простой путь - перегрузка имен. Как известно, Ada допускает многократное использование одних и тех же имен подпрограмм для операндов различных типов. Значит можно определить типы TAPE, DISK и другие, каждый с его собственной версией подпрограмм:

procedure open (p: in out TAPE; descriptor: in INTEGER);
procedure close (p: in out DISK);

Никакая двусмысленность не возникнет, если подпрограммы отличаются, по крайней мере, типом одного операнда. Но это решение не поддерживает полиморфизм и динамическое связывание. Как добиться различного результата вызова d.close после присваиваний d := di и d := ta, где di - DISK, а ta - TAPE?

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

type DEVICE (unit: DEVICE_TYPE) is
    record
        ... Поля одинаковые для устройств всех типов ...
        case unit is
            when tape => ... поля для ленточных накопителей ...;
            when disk => ... поля для дисковых накопителей ...;
            ... Другие варианты ...;
        end case
    end record

где DEVICE_TYPE - перечислимый тип с элементами tape, disk и т. д. Тогда для каждого усройства можно определить индивидуальную версию каждой процедуры ( open, close и т. д.)

case d'unit is
    when tape => ... действия для ленточных накопителей ...;
    when disk => ... действия для дисковых накопителей ...;
    ... другие варианты ...;
end case

Здесь каждый случай явно выделен и список выбора закрыт, поэтому для добавления новых вариантов выбора придется внести изменения во все аналогичные подпрограммы. Такая программная архитектура явно противоречит принципу Единственного выбора.

Следовательно, ответ на вопрос, поставленный в данном разделе, отрицательный:

Эмуляция универсальности с помощью наследования

Обратимся теперь к решению обратной задачи: можно ли добиться эффекта универсальности в стиле Ada средствами наследования ОО-языка.

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

Возможно, это покажется удивительным, но проще эмулировать более сложную форму ограниченной универсальности, и именно этот вариант рассмотрен первым.

Эмуляция ограниченной универсальности: обзор

Довольно естественной является идея связывания ограниченного формального родового параметра с некоторым классом, в котором определены ограничивающие операции. Этот класс можно рассматривать как АТД. Расмотрим наши два примера Ada с ограниченными родовыми параметрами - minimum and matrices:

generic
    type G is private;
    with function "<=" (a, b: G) return BOOLEAN is <>
generic
    type G is private;
    zero: G; unity: G;
    with function "+"(a, b: G) return G is <>;
    with function "*"(a, b: G) return G is <>;

Можно рассматривать эти предложения как определения двух абстрактных типов данных - COMPARABLE и RING_ELEMENT. Первый характеризуется наличием операции сравнения " <= ", а второй компонентами zero, unity, + and *.

На ОО языке такие типы могут быть непосредственно представлены как классы. Определить эти классы полностью невозможно, так как нет универсального решения для операций " <= ", " + " и т.д. Следовательно, необходимо использовать абстрактные классы, возложив детали реализации на их потомков:

deferred class COMPARABLE feature
    infix "<=" (other: COMPARABLE): BOOLEAN is deferred end
end
deferred class RING_ELEMENT feature
    infix "+" (other: like Current): like Current is
        deferred
        ensure
            equal(other, zero) implies equal(Result, Current)
        end;
    infix "*" (other: like Current): like Current is deferred end
    zero: like Current is deferred end
    unity: like Current is deferred end
end

В отличие от Ada, ОО-нотация позволяет описывать абстрактные семантические свойства, хотя в данный пример включено только одно (постусловие x + 0 = x при любом x для операции infix "+" ).

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

Мы можем написать подпрограмму, такую как minimum, указав тип COMPARABLE для ее аргументов. Основываясь на образце Ada, функция была бы объявлена следующим образом:

minimum (one: COMPARABLE; other: like one): like one is
        -- Минимальное из one и other
    do ... end

При ОО-разработке каждая подпрограмма появляется в классе и связывается с текущим экземпляром класса. Включив minimum в класс COMPARABLE, аргумент one станет неявным текущим экземпляром. Класс будет выглядеть так:

deferred class COMPARABLE feature
    infix "<=" (other: like Current): BOOLEAN is
            -- Текущий объект меньше или равен other?
        deferred
        end
    minimum (other: like Current): like Current is
            -- Минимальное из двух значений: текущего 
            -- и other
    do
        if Current <= other then Result := Current else Result := other end
    end
end

Для вычисления минимума двух элементов необходимо объявить их тип как эффективного потомка COMPARABLE, с заданной реализацией операции сравнения <=, например:

class INTEGER_COMPARABLE inherit
    COMPARABLE
creation
    put
feature -- Initialization
    put (v: INTEGER) is
            -- Инициализация значением v.
        do item := new end
feature -- Access
    item: INTEGER;
        -- Значение, связанное с текущим объектом
feature -- Basic operations
    infix "<=" (other: like Current): BOOLEAN is
            -- Текущий объект меньше или равен other?
        do Result := (item <= other.item) end;
end

Для нахождения минимума двух целых теперь можно применять функцию minimum к сущностям ic1 и ic2, чьи типы не INTEGER, а INTEGER_COMPARABLE:

ic3 := ic1.minimum (ic2)

Для использования родовых функций infix <= и minimum придется исключить прямые ссылки на целые, заменив их сущностями INTEGER_COMPARABLE, поскольку этого требует атрибут item и подпрограмма put. Более того, придется вводить подобных потомков COMPARABLE, таких как STRING_COMPARABLE и REAL_COMPARABLE, для каждого типа, требующего своей версии minimum.

Заметьте, механизм закрепленных объявлений является основой обеспечения корректности. Если бы аргумент minimum в COMPARABLE был бы объявлен как COMPARABLE, а не like Current, то следующий вызов был бы синтаксически допустим:

ic1.minimum (c)

если c принадлежал бы типу COMPARABLE, но не был бы типом INTEGER_COMPARABLE. Понятно, что такой вызов мог быть некорректным. Все это применимо и к RING_ELEMENT.

Объявление компонентов item и put для всех потомков COMPARABLE, жертвуя при этом прямым использованием простых типов, конечно же, неприятно. При этом приходится идти на потерю производительности: вместо манипулирования целыми или строками приходится использовать объекты обертывающих типов, таких как INTEGER_COMPARABLE. Но, заплатив эту цену - простоту использования и эффективность, мы приобретаем полную эмуляцию ограниченной универсальности средствами наследования. (В заключительной нотации, конечно, ничего платить не требуется.)

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

Предыдущая дискуссия переносится и на пакеты. Для эмуляции абстракции матриц, которую Ada реализует пакетом MATRICES, можно использовать класс:

class MATRIX feature
    anchor: RING_ELEMENT is do end
    implementation: ARRAY2 [like anchor]
    item (i, j: INTEGER): like anchor is
            -- Значение элемента с индексами (i, j)
        do Result := implementation.item (i, j) end
    put (i, j: INTEGER; v: like anchor) is
            -- Присвоить значение v элементу с индексами (i, j)
        do implementation.put (i, j, v) end
    infix "+" (other: like Current): like Current is
            -- Матричная сумма текущей матрицы matrix и other
        local
            i, j: INTEGER
        do
            create Result.make (...)
            from i := ... until ... loop
                from j := ... until ... loop
                    Result.put ((item (i, j) + other.item (i, j)), i, j)
                    j := j + 1
                end
                i := i + 1
            end
        end
    infix "*"(other: like Current): like Current is
            -- Матричное произведение текущей матрицы и other
        local ... do ... end
end

С типом аргумента put и результата item связана интересная проблема: он должен быть RING_ELEMENT, но соответствующим образом переопределен в классах-потомках. Закрепленное объявление дает решение проблемы, но здесь, на первый взгляд, нет атрибута, который мог бы послужить якорем. Это не должно нас останавливать: следует объявить искусственный якорь, называемый anchor. Его единственное предназначение - быть переопределенным в подходящий тип потомка RING_ELEMENT будущими потомками MATRIX (например, BOOLEAN_RING в BOOLEAN_MATRIX и т. д.). Во избежание потерь памяти в экземплярах anchor объявляется как функция, а не как атрибут. Техника искусственного якоря полезна для сохранения согласованности типов, когда, как в данном случае, нет естественного якоря среди атрибутов класса.

Некоторые детали цикла, также как и тело инфиксной операции *, остались вне рассмотрения, но дополнить их просто. Компоненты put и item, применяемые в реализации, пришли из библиотечного класса ARRAY2, описывающего двумерные массивы.

Для определения эквивалента родового пакета Ada, показанного ранее:

package BOOLEAN_MATRICES is
    new MATRICES (BOOLEAN, false, true, "or", "and");

следует прежде всего объявить соответствующее булево кольцо:

class BOOLEAN_RING_ELEMENT inherit
    RING_ELEMENT
        redefine zero, unity end
creation
    put
feature -- Initialization
    put (v: BOOLEAN) is
            -- Инициализация значением v
        do item := v end
feature -- Access
    item: BOOLEAN
feature -- Basic operations
    infix "+" (other: like Current): like Current is
            -- Булево сложение: or
        do create Result.put (item or other.item) end
    infix "*"(other: like Current): like Current is
            -- Булево умножение: and
        do create Result.put (item and other.item) end
    zero: like Current is
            -- Нулевой элемент булева кольца для сложения
        once create Result.put (False) end
    unity: like Current is
            -- Нулевой элемент для булева умножения
        once create Result.put (True) end
end

Заметьте, ноль и единица реализуются однократными функциями.

Тогда для получения родового порождения пакета Ada следует просто определить наследника BOOLEAN_MATRIX от MATRIX, где нужно только переопределить anchor - искусственный якорь; все остальные типы будут следовать автоматически:

class BOOLEAN_MATRIX inherit
    MATRIX
        redefine anchor end
feature
    anchor: BOOLEAN_RING_ELEMENT
end

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

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

Механизм эмуляции неограниченной универсальности остается тем же самым. Этот случай можно рассматривать как специальную форму ограниченной универсальности с пустым множеством ограничений. Как и выше, типы формальных параметров будут рассматриваться как АТД, но без относящихся к ним операций. Эта техника работает, но вряд ли ее стоит применять, поскольку такой пустой тип не соответствует никакой реальности данных.

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

class QUEUABLE end

Мы можем теперь объявить класс QUEUE, чьи операции применимы к объектам QUEUABLE. (Помните, что этот класс не предлагается как образец совершенства хорошего ОО-проектирования, мы по-прежнему добровольно играем с не лучшей версией ОО-нотации, не имеющей универсальности.) Постусловия программы опущены для краткости. И хотя в принципе функция item могла бы служить якорем, ее тело не будет изменяться потомками, так что лучше использовать искусственный якорь во избежание ее переопределения.

indexing
    description: "Очередь, реализованная массивом"
class QUEUE creation
    make
feature -- Initialization
    make (m: INTEGER) is
            -- Создание очереди, вмещающей m элементов
        require
            m >= 0
        do
            create implementation.make (1, m); capacity := m
            first := 1; next := 1
        end
feature -- Access
    capacity, first, next, count: INTEGER
    item: like item_anchor is
            -- Старейший (первый пришедший) элемент очереди
        require
            not empty
        do
            Result := implementation.item (?rst)
        end
feature -- Status report
    empty: BOOLEAN is
            -- Пуста ли очередь?
        do Result := (count = 0) end
    full: BOOLEAN is
            -- Заполнен ли массив?
        do Result := (count = capacity) end
feature -- Element change
    put (x: like item_anchor) is
            -- Добавление x в конец очереди
         require
            not full
        do
            implementation.put (x, next); count := count + 1
            next := successor (next)
        end
    remove is
            -- Удаление старейшего элемента
        require
            not empty
        do
            first := successor (first); count := count - 1
        end
feature {NONE} -- Implementation
    item_anchor: QUEUABLE is do end
    implementation: ARRAY [like item_anchor]
    successor (n: INTEGER): INTEGER is
            -- Значение, следующее за n, циклически в интервале 1 .. capacity
        require
            n >= 1; n <= capacity
        do
            Result := (n \\ capacity) + 1
        end
invariant
    0 <= count; count <= capacity; first >= 1; next >= 1
    (not full) implies ((first <= capacity) and (next <= capacity))
    (capacity = 0) implies full
    -- Элементы, если они есть, появляются в позициях массива first, ... next - 1
end

Для получения эквивалента родового порождения (для получения очереди с элементами нужного типа) необходимо, как и в примере с COMPARABLE, определить потомков QUEUABLE:

class INTEGER_QUEUABLE inherit
    QUEUABLE
creation
    put
feature -- Initialization
    put (n: INTEGER) is
            -- Инициализация значением n
        do item := n end
feature -- Access
    item: INTEGER
feature {NONE} -- Implementation
    item_anchor: INTEGER is do end
end

Подобным образом следует поступить при порождении STRING_QUEUABLE и т. д. Затем следует объявить соответствующих потомков QUEUE, переопределив item_anchor в каждом из них.

Сочетание универсальности и наследования

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

Закрепленные объявления решают вторую проблему. (Читатель, знакомый с лекцией 17 курса "Основы объектно-ориентированного программирования", где детально обсуждались проблемы типизации, мог заметить важность проблемы проверки правильности системы, но эти вопросы исчезнут в окончательном варианте, представленном ниже.)

Давайте посмотрим, как можно решить первую проблему введением (по сути, повторным введением) подходящей формы универсальности.

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

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

class C [G, H, ...] ...

Здесь параметры представляют произвольные типы без всяких ограничений. Для получения непосредственно используемого типа строится родовое порождение с заданными фактическими родовыми параметрами:

x: C [DEVICE, RING_ELEMENT, ...]

Такой подход непосредственно применим к классу очереди, который может быть просто определен как:

indexing
    description: "Очередь, реализованная массивом"
class QUEUE [G] creation
    ... Все остальное как ранее, но удалив объявление item_anchor
    и заменив все вхождения типа like item_anchor на G ...
end

Мы избавились от класса QUEUABLE так же, как и от INTEGER_QUEUABLE и всех других потомков. Для получения очереди целых будем просто использовать тип QUEUE [INTEGER], непосредственно манипулируя целыми, а не обертывающими их объектами.

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

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

Рассматривая ограниченную универсальность можно теперь исходить из той же общей схемы. В примере с матрицами:

class MATRIX [G] feature
    anchor: RING_ELEMENT [G]
    ...Другие компоненты как ранее ...
end

класс, задающий элементы кольца, теперь объявляется так:

deferred class RING_ELEMENT [G] feature
    item: G
    put (new: G) is do item := new end
    ... Другие компоненты как ранее...
end

Использование одного и того же родового параметра для двух связанных классов, RING_ELEMENT и MATRIX, гарантирует согласованность типов: все элементы данной матрицы будут принадлежать типу RING_ELEMENT [G] с одним и тем же G.

Аналогично можно создать универсальный класс COMPARABLE:

deferred class COMPARABLE [G] feature
    item: G
    put (new: G) is do item := new end
    ...Другие компоненты (infix "<=", minimum) как ранее ...
end

Компоненты класса ( infix "<=", minimum ) представляют ограничения (программы в форме Ada). Ранее заданные потомки становятся совершенно простыми:

class INTEGER_COMPARABLE inherit
    COMPARABLE [INTEGER]
creation
    put
end

(Заметьте, это полностью заданный класс, а не его схема, в которую следует добавлять компоненты!) Этот же прием непосредственно применим ко всем другим вариантам, таким как STRING_COMPARABLE.

Эта простая в применении техника приводит к следующему принципу эмуляции:

Но снова ничто не дается даром: нам понадобилось введение обертывающих классов, таких как INTEGER_COMPARABLE. Это менее шокирует, в сравнении с предыдущим решением, поскольку некоторую цену следует платить за ограничение универсальности. Кажется, что здесь есть оправдание появлению обертывающих классов и объектов, поскольку ограниченная универсальность - сама по себе довольно изощренная идея.

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

Эта нотация, как показано в предыдущих лекциях, позволяет задавать ограниченную универсальность в виде:

class MATRIX [G -> RING_ELEMENT] ...
class SORTABLE_LIST [G -> COMPARABLE] ...

Здесь классы RING_ELEMENT и COMPARABLE заданы в обычном стиле - отложенные и не универсальные. Как отмечалось при первом представлении этой нотации, мы получаем замечательную комбинацию универсальности и наследования, позволяющую избежать тяжкого груза предыдущих решений:

Напоминаю семантику: теперь родовой параметр G не представляет произвольный тип - он должен удовлетворять ограничениям, будучи потомком определенного класса. Родовое порождение, такое как MATRIX [T], будет корректным, если и только если T - такой тип. Это верно для INTEGER, но не выполняется для типа STRING. Аналогично, STRING является наследником COMPARABLE и приемлем в качестве фактического параметра для класса SORTABLE_LIST, но это не верно для класса COMPLEX (комплексных чисел), для которых не задано отношение полного порядка. Символ -> был выбран для напоминания о стрелках в диаграммах наследования.

И, как последнюю деталь, напомним, что в этой схеме ограниченная универсальность становится основным свойством, а неограниченная представляется ее частным случаем. Например, QUEUE [G], теперь понимается как сокращение записи QUEUE [G-> ANY], где ANY означает класс, служащий предком для всех классов, включая классы, создаваемые разработчиком. Как следствие, теперь точно определяются операции, применимые к G: они наследуются от ANY, применимы ко всем классам, включая общецелевые компоненты, такие как clone, print и equal.

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

Ключевые концепции

Библиографические замечания

Материал для этой лекции основан на докладе на первой конференции OOPSLA [М. 1986]. Комбинация множественного наследования с ограниченной и неограниченной универсальностью предложена также в языке Trellis [Schaffert 1986].

Упражнения

УB.1 Искусственные якоря

Искусственный якорь anchor объявлен как атрибут класса MATRIX и потому требует в период выполнения выделения для экземпляров класса дополнительной (небольшой) памяти. Возможно ли избежать этих потерь, объявив якорь однократной функцией, чье тело может быть пустым, так как фактически она никогда не будет вычисляться? ( Подсказка: рассмотрите правила типов.)

УB.2 Бинарные деревья и бинарные деревья поиска

Напишите универсальное "бинарное дерево"-класс BINARY_TREE. Бинарное дерево задается информацией в корне дерева и двумя возможными поддеревьями, левым и правым. Затем рассмотрите "бинарное дерево поиска", для всех узлов которого выполняется следующее условие: информация в узле больше или равна информации в корне левого поддерева, но меньше информации в корне правого поддерева. Это означает задание полного порядка на "информациях". Напишите класс BINARY_SEARCH_TREE, реализующий это понятие как потомка BINARY_TREE. Сделайте класс универсальным, насколько это возможно. Клиенты должны использовать класс для произвольных типов, задающих информацию и специфическое отношение порядка.

УB.3 Более просто используемые матрицы

Добавьте в последнюю версию класса MATRIX две функции - для доступа и модификации элементов, которые в противоположность item и put будут позволять клиентам манипулировать матрицами типа MATRIX [G] в терминах элементов типа G, а не типа RING_ELEMENT [G].

УВ.4 Полная реализация очередей

Расширьте пример с очередью, определив отложенный класс QUEUE, дополнив класс этого приложения (называемый теперь ARRAYED_QUEUE, наследуемый от QUEUE и ARRAY, с подходящими постусловиями). Добавьте класс LINKED_QUEUE для реализации связного списка (основанный на наследовании от LINKED_LIST и QUEUE ).