10.3. Родовые (настраиваемые) сегменты

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

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

Сложная обработка индексов делается одинаково для всех типов элементов массива:

type lnt_Array is array(lnteger range <>) of Integer;

procedure Sort(A: lnt_Array) is

Begin

for I in A'First ..A'Last-1 loop

Min:=l;

for J in I+1 .. A'Last loop

if A(J) < A(Min) then Min := J; end if;

-- Сравнить элементы, используя "<"

end loop;

Temp := A(l); A(l) := A(Min); A(Min) := Temp;

-- Переставить элементы, используя ":="

end loop;

end Sort;

На самом деле даже тип индекса не существенен при программировании этой процедуры, лишь бы он был дискретным типом (например, символьным или целым).

Чтобы получить процедуру Sort для некоторого другого типа элемента, на­пример Character, можно было бы физически скопировать код и сделать не­обходимые изменения, но это могло бы привести к дополнительным ошиб­кам. Более того, если бы мы хотели изменить алгоритм, то пришлось бы сде­лать эти изменения отдельно в каждой копии. В Ada определено средство, называемое родовыми сегментами (generics), которое позволяет программисту задать шаблон подпрограммы, а затем создавать конкретные экземпляры подпрограммы для нескольких разных типов. Хотя в С нет подобного средст­ва, его отсутствие не так серьезно, потому что указатели void, оператор sizeof и указатели на функции позволяют легко запрограммировать «обобщенные», пусть и не такие надежные, подпрограммы. Обратите внимание, что примене­ние родовых сегментов не гарантирует, что конкретные экземпляры одной родовой подпрограммы будут иметь общий объектный код; фактически, при реализации может быть выбран независимый объектный код для каждого конкретного случая.

Ниже приведено объявление родовой подпрограммы с двумя родовыми фор­мальными параметрами:

generic

type ltem_Array is array(lnteger range <>) of Item;

procedure Sort(A: ltem_Array);

Это обобщенное объявление на самом деле объявляет не процедуру, а только шаблон процедуры. Необходимо обеспечить тело процедуры: оно будет напи­сано в терминах родовых параметров:

Temp, Min: Item;

begin

… -- Полностью совпадает с вышеприведенным

end Sort;

Чтобы получить (подлежащую вызову) процедуру, необходимо конкретизиро­вать родовое объявление, т. е. создать экземпляр, задав родовые фактические параметры:

type Char_Array is array(lnteger range <>) of Character;

procedure lnt_Sort(A: lnt_Array) is new Sort(lnteger, lnt_Array);

procedure Char_Sort(A: Char_Array) is new Sort(Character, Char_Array);

Это реальные объявления процедур; вместо тела процедуры после объявления следует ключевое слово is, и тем самым запрашивается новая копия обобщен­ного шаблона.

Родовые параметры — это параметры этапа компиляции, и используются они компилятором, чтобы сгенерировать правильный код для конкретного экземпляра. Параметры образуют контракт между кодом родовой процедуры и ее конкретизацией. Первый параметр Item объявлен с записью (<>). Это оз­начает, что конкретизация программы обещает применить дискретный тип, такой как Integer или Character, а код обещает использовать только операции, допустимые на таких типах. Так как на дискретных типах определены опера­ции отношения, процедура Sort уверена, что «<» допустима. Второй обобщен­ный параметр ltem_Array — это предложение контракта, которое говорит: ка­кой бы тип ни был задан для первого параметра, второй параметр должен быть массивом элементов этого типа с целочисленным индексом.

Модель контракта работает в обе стороны. Попытка выполнить арифмети­ческую операцию «+» на значениях типа Item в родовом теле процедуры явля­ется ошибкой компиляции, так как существуют такие дискретные типы, как Boolean, для которых арифметические операции не определены. И обратно,родовая процедура не может быть конкретизирована с элементом массива ти­па запись, потому что операция «<» для записей не определена.

Цель создания модели контракта заключается в том, чтобы позволить про­граммистам многократно применять родовые модули и избавить их от необ­ходимости знать, как реализовано родовое тело процедуры. Уж если родовое тело процедуры скомпилировано, конкретизация может завершиться неус­пешно, только если фактические параметры не удовлетворяют контракту. Конкретизация не может быть причиной ошибки компиляции в теле проце­дуры.

Шаблоны в C++

В языке C++ обобщения реализованы с помощью специального средства — шаблона (template):

template <class ltem_Array> void Sort(ltem_Array parm)

{

…

}

Здесь нет необходимости в явной конкретизации: подпрограмма создается неявно, когда она используется:

typedef int l_Array[100];

typedef char C_Array[100];

l_Array a;

C_Array c;

Sort(a); // Конкретизировать для целочисленных массивов

Sort(c); // Конкретизировать для символьных массивов

Явная конкретизация — это оптимизация, задаваемая программистом по желанию; в противном случае, компилятор сам решает, какие конкретизации необходимо сделать. Шаблоны могут быть конкретизированы только по ти­пам и значениям, или, в более общем случае, по классам (см. гл. 14).

Язык C++ не использует модель контракта, поэтому конкретизация может закончиться неуспешно, вызвав ошибку компиляции в определении шабло­на. Это затрудняет производство и поставку шаблонов как самостоятельных компонентов программного обеспечения.

Родовые параметры-подпрограммы в языке Ada

В Ada допускается, чтобы родовые параметры были подпрограммами. Пример программы сортировки может быть написан так:

generic

type Item is private;

type ltem_Array is array(lnteger range <>) of Item;

with function "<"(X, Y: in Item) return Boolean;

procedure Sort(A: ltem_Array);

Контракт теперь расширен тем, что для реализации операции «<» должна быть предоставлена булева функция. А поскольку операция сравнения обеспечена, Item больше не нужно ограничивать дискретными типами, для которых эта опе­рация является встроенной. Ключевое слово private означает, что любой тип, на котором определено присваивание и сравнение на равенство, может при­меняться при реализации:

type Rec is record . .. end record;

type Rec_Array is array(lnteger range <>) of Rec;

function "<"(R1, R2: in Rec) return Boolean;

procedure Rec_Sort(A: Rec_Array) is new Sort(Rec, Rec_Array, "<");

Внутри подпрограммы Sort присваивание является обычным поразрядным присваиванием для записей, а когда нужно сравнить две записи, вызывается функция «<». Эта обеспеченная программистом функция решит, является ли одна запись меньше другой.

Модель контракта в языке Ada очень мощная: типы, константы, перемен­ные, указатели, массивы, подпрограммы и пакеты (в Ada 95) могут использо­ваться как родовые параметры.