М. Бен-Ари - Языки программирования. Практический сравнительный анализ (2000) (1160781), страница 31

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

Текст из файла (страница 31)

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) могут использо­ваться как родовые параметры.

10.4. Вариантные записи

Вариантные записи используются, когда во время выполнения необходимо интерпретировать значение несколькими разными способами. Ниже пере­числены распространенные примеры.

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

• Разнородные структуры данных, такие как дерево, которое может содер­жать узлы разных типов.

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

typedef int Arr[10];

typedef struct {

float f1;

int i1;

}Rec;

Давайте сначала определим тип, который кодирует вариант:

typedef enum {Record_Code, Array_Code} Codes; 23

Теперь с помощью типа union (объединение) в С можно создать вариантную запись, которая сама может быть вложена в структуру, включающую общее поле тега, характеризующего вариант:

typedef struct {

Codes code; /* Общее поле тега */

union { /* Объединение с альтернативными полями */

Агг а; /* Вариант массива */

Rес г; /* Вариант записи */

} data;

} S_Type;

S_Type s;

С точки зрения синтаксиса это всего лишь обычная вложенность записей и массивов внутри других записей. Различие состоит в реализации: полю data выделяется объем памяти, достаточный для самого большого поля массива а или поля записи r (см. рис. 10.1). Поскольку выделяемая память рассчитана на самое большое возможное поле, вариантные записи могут быть чрезвычайно

неэкономны по памяти, если один вариант очень большой, а другие малень­кие:

union {

int a[1000];

float f;

char c;

}

Избежать этого можно ценой усложнения программирования — использовать указатель на длинные поля.

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

if (s.code == Array_Code)

i = s.data.a[4]; /* Выбор первого варианта */

else

i = s.data.r.h ; /* Выбор второго варианта */

Основная проблема с вариантными записями состоит в том, что они потен­циально могут вызывать серьезные ошибки. Так как конструкция union по­зволяет программе обращаться к той же самой строке битов различными спо­собами, то возможна обработка значения одного типа, как если бы это было значение какого-либо другого типа (скажем, обращение к числу с плавающей точкой, как к целому). Действительно, программисты, пишущие на языке Pascal, используют вариантные записи, чтобы делать преобразование типов, которое в языке непосредственно не поддерживается.

В вышеупомянутом примере ситуация еще хуже, потому что возможно об­ращение к ячейкам памяти, которые вообще не содержат никакого значения: поле s.data.r могло бы иметь длину 8 байт для размещения двух чисел, а поле s.data.a — 20 байт для размещения десяти целых чисел. Если в поле s.data.r в данный момент находится запись, то s.data.a[4] не имеет смысла.

В Ada не разрешено использовать вариантные записи, чтобы не разрушать контроль соответствия типов. Поле code, которое мы использовали в приме­ре, теперь является обязательным полем, и называется дискриминантом, а при обращении к вариантным полям проверяется корректность значения дискри­минанта. Дискриминант выполняет роль «параметра» типа:

type Codes is (Record_Code, Array_Code);

type S_Type(Code: Codes) is

record

case Code is

when Record_Code => R: Rec;

when Array_Code => A: Arr;

end case;

end record;

а запись должна быть объявлена с конкретным дискриминантом, чтобы ком­пилятор точно знал, сколько памяти нужно выделить:

S1: S_Type(Record_Code);

S2: S_Type(Array_Code);

Другая возможность — объявить указатель на вариантную запись и проверять дискриминант во время выполнения:

I Ada type Ptr is access S_Type;

P: Ptr := new S_Type(Record_Code);

I:=P.R.I1; --Правильно

I:=P.A(5); -- Ошибка

Первый оператор присваивания правильный, поскольку дискриминант запи­си P.all — это Record_Code, который гарантирует, что поле R существует; в то же время второй оператор приводит к исключительной ситуации при работе программы, так как дискриминант не соответствует запрошенному полю.

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

Неограниченные записи в Ada

В дополнение к ограниченным записям, вариант которых при создании пе­ременной фиксирован, Ada допускает объявление неограниченных записей (unconstrained records), для которых допустимо во время выполнения безо­пасное с точки зрения контроля типов присваивание, хотя записи отно­сятся к разным вариантам:

S1, S2: S_Type; -- Неограниченные записи

S1 := (Record_Code, 4.5);

S2 := (Array_Code, 1..10 => 17);

S1 := S2; -- Присваивание S1 другого варианта

-- S2 больше, чем S1 !

Два правила гарантируют, что контроль соответствия типов продолжает работать:

• Для дискриминанта должно быть задано значение по умолчанию, чтобы гарантировать, что первоначально в записи есть осмысленный дискри­минант:

type S_Type (Code: codes: = Record_Code) is ...

• Само по себе поле дискриминанта не может быть изменено. Допустимо только присваивание допустимого значения всей записи, как показано в примере.

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

10.5. Динамическая диспетчеризация

Предположим, что каждый вариант записи S_Type должен быть обработан cобственной подпрограммой. Нужно использовать case-оператор, чтобы пе-pейти (dispatch) в соответствующую подпрограмму. Рассмотрим «диспетчер­скую» процедуру:

Характеристики

Список файлов книги