Подтипы массивов в языке Ada - М. Бен-Ари Языки программирования. Практический сравнительный анализ


^ Подтипы массивов в языке Ada



Подтипы, которые мы обсуждали в разделе 4.5, определялись добавлением ог­раничения диапазона к дискретному типу (перечисляемому или целочисленно­му). Точно так же подтип массива может быть объявлен добавлением к типу неограниченного массива ограничения индекс'.
type A_Type is array(lnteger range о) of Float;
subtype Line is A_Type(1 ..80);
L, L1, L2: Line;
Значение этого именованного подтипа можно использовать как фактиче­ский параметр, соответствующий формальному параметру исходного неогра­ниченного типа:
Sort(L);
В любом случае неограниченный формальный параметр процедуры Sort ди­намически ограничивается фактическим параметром при каждом вызове процедуры.
Приведенные в разделе 4.5 рассуждения относительно подтипов примени­мы и здесь. Массивы разных подтипов одного и того же типа могут быть при­своены друг другу (при условии, что они имеют одинаковое число элементов), но массивы разных типов не могут быть присвоены друг другу без явного пре­образования типов. Определение именованного подтипа — всего лишь вопрос удобства.
В Ada есть мощные конструкции, называемые сечениями (slices) и сдвигами
(sliding), которые позволяют выполнять присваивания над частями массивов. Оператор
L1(10..15):=L2(20..25);
присваивает сечение одного массива другому, сдвигая индексы, пока они не придут в соответствие. Сигнатуры типов проверяются во время компиляции, тогда как ограничения проверяются во время выполнения и могут быть дина­мическими:
L1(I..J):=L2(l*K..M+2);
Проблемы, связанные с определениями типа для массивов в языке Pascal, за­ставили разработчиков языка Ada обобщить решение для массивов изящной концепцией подтипов: отделить статическую спецификацию типа от ограни­чения, которое может быть динамическим.

^ 5.5. Строковый тип


В основном строки — это просто массивы символов, но для удобства програм­мирования необходима дополнительная языковая поддержка. Первое требо­вание: для строк нужен специальный синтаксис, в противном случае работать с массивами символов было бы слишком утомительно. Допустимы оба следу­ющих объявления, но, конечно, первая форма намного удобнее:
char s[]= "Hello world";
chars[] = {‘H’,’e’,’l’,’o’,’ ‘,’w’,’o’,’r’,’l’,’d’,’/0’};
Затем нужно найти некоторый способ работы с длиной строки. Вышеупо­мянутый пример уже показывает, что компилятор может определить размер I строки без явного его задания программистом. Язык С использует соглаше-I ние о представлении строк, согласно которому первый обнаруженный нуле­вой байт завершает строку. Обработка строк в С обычно содержит цикл while вида:
C
while (s[i++]!='\0')... •
Основной недостаток этого метода состоит в том, что если завершающий ноль почему-либо отсутствует, то память может быть затерта, так же как и при лю­бом выходе за границы массива:
C
char s[11]= "Hello world"; /* He предусмотрено место
для нулевого байта*/
chart[11];
strcpy(t, s); /* Копировать set. Какой длины s? */
Другие недостатки этого метода:
• Строковые операции требуют динамического выделения и освобожде­ния памяти, которые относительно неэффективны.
• Обращения к библиотечным строковым функциям приводят к повтор­ным вычислениям длин строк.
• Нулевой байт не может быть частью строки.
Альтернативное решение, используемое некоторыми диалектами языка Pascal, состоит в том, чтобы включить явный байт длины как неявный нуле­вой символ строки, чья максимальная длина определяется при объявлении:
S:String[10];
Pascal
S := 'Hello world'; (* Требуется 11 байтов *)
writeln(S);
S:='Hello';
writeln(S);
Сначала программа выведет «Hello worl», так как строка будет усечена до объявленной длины. Затем выведет «Hello», поскольку writeln принимает во внимание неявную длину. К сожалению, это решение также небезупречно, потому что возможно непосредственное обращение к скрытому байту длины и затирание памяти:
Pascal

s[0]:=15;
В Ada есть встроенный тип неограниченного массива, называемый String, со следующим определением:
Ada

type String is array(Positive range ) of Character;
Каждая строка должна быть фиксированной длины и объявлена с индексным ограничением:

Ada

S:String(1..80);
В отличие от языка С, где вся обработка строк выполняется с использованием библиотечных процедур, подобных strcpy, в языке Ada над строками допускаются такие операции, как конкатенация «&», равенство и операции отноше­ния, подобные «<». Поскольку строго предписан контроль соответствия типов, нужно немного потренироваться с атрибутами, чтобы заставить все заработать:
Ada
S1: constant String := "Hello";
S2: constant String := "world";
T: String(1 .. S1 'Length + 1 + S2'Length) := S1 & ' ' & S2;
Put(T); -- Напечатает Hello world
Точная длина Т должна быть вычислена до того, как выполнится присваива­ние! К счастью, Ada поддерживает атрибуты массива и конструкцию для со­здания подмассивов (называемых сечениями — slices), которые позволяют выполнять такие вычисления переносимым способом.
Ada 83 предоставляет базисные средства для определения строк нефикси­рованной длины, но не предлагает необходимых библиотечных подпрограмм для обработки строк. Чтобы улучшить переносимость, в Ada 95 определены стандартные библиотеки для всех трех категорий строк: фиксированных, из­меняемых (как в языке Pascal) и динамических (как в С).

^ 5.6. Многомерные массивы


Многомерные матрицы широко используются в математических моделях фи­зического мира, и многомерные массивы появились в языках программиро­вания начиная с языка Fortran. Фактически есть два способа определения многомерных массивов: прямой и в качестве сложной структуры. Мы ограни­чимся обсуждением двумерных массивов; обобщение для большей размерно­сти делается аналогично.
Прямое определение двумерного массива в языке Ada можно дать, указав два индексных типа, разделяемых запятой:
type Two is
Ada
array(Character range

,

Integer range ) of Integer;
T:Two('A'..'Z', 1 ..10); I: Integer;
C: Character;
T('XM*3):=T(C,6);
Как показывает пример, две размерности не обязательно должны быть одно­го и того же типа. Элемент массива выбирают, задавая оба индекса.
Второй метод определения двумерного массива состоит в том, чтобы опре­делить тип, который является массивом массивов:
Ada
type l_Array is array( 1.. 10) of Integer;
type Array_of_Array is array (Character range ) of l_Array;
T:Array_of_Array('A1..>ZI);
I: Integer;
С: Character;
T('X')(I*3):=T(C)(6);
Преимущество этого метода в том, что можно получить доступ к элементам второй размерности (которые сами являются массивами), используя одну операцию индексации:
Ada

Т('Х') :=T('Y'); -- Присвоить массив из 10 элементов
Недостаток же в том, что для элементов второй размерности должны быть за­даны
ограничения до того, как эти элементы будут использоваться для опре­деления первой размерности.
В языке С доступен только второй метод и, конечно, только для целочис­ленных индексов:
C
inta[10][20];
а[1] = а[2]; /* Присвоить массив из 20 элементов */
Язык Pascal не делает различий между двумерным массивом и массивом мас­сивов; так как границы считаются частью типа массива, это не вызывает ни­каких проблем.

^ 5.7. Реализация массивов


При реализации элементы массива размещаются в памяти последовательно. Если задан массив А, то адрес его элемента A(l) есть (см. рис. 5.2.):
addr (А) + size (element) * (/ - A.'First)
Например: адрес А(4) равен 20 + 4 * (4 - 1) = 32.
Сгенерированный машинный код будет выглядеть так:
L
oad R1,l Получить индекс
sub R1,A'First Вычесть нижнюю границу
multi R1 ,size Умножить на размер — > смещение
add R1 ,&А Добавить адрес массива — > адрес элемента
load R2,(R1) Загрузить содержимое
Вы, возможно, удивитесь, узнав, что для каждого доступа к массиву нужно столько команд! Существует много вариантов оптимизации, которые могут улучшить этот код. Сначала отметим, что если A'First — ноль, то нам не нужно вычитать индекс первого элемента; это объясняет, почему разработ­чики языка С сделали так, что индексы всегда начинаются с нуля. Даже если A'First — не ноль, но известен на этапе компиляции, можно преобразовать вычисление адреса следующим образом:
(addr (А) - size (element) * A'First) + (size (element) * i)
Первое выражение в круглых скобках можно вычислить при компиляции, экономя на вычитании во время выполнения. Это выражение будет известно во время компиляции при обычных обращениях к массиву:
Ada
А:А_Туре(1..10);
A(I):=A(J);
но не в том случае, когда массив является параметром:
procedure Sort(A: A_Type) is
Ada
begin

A(A'First+1):=A(J);

end Sort;
Основное препятствие для эффективных операций с массивом — умножение на размер элемента массива. К счастью, большинство массивов имеют про­стые типы данных, такие как символы или целые числа, и размеры их элемен­тов представляют собой степень двойки. В этом случае дорогостоящая опера­ция умножения может быть заменена эффективным сдвигом, так как сдвиг влево на n эквивалентен умножению на 2". В случае массива записей можно повысить эффективность (за счет дополнительной памяти), дополняя записи так, чтобы их размер был кратен степени двойки. Обратите внимание, что на переносимость программы это не влияет, но само улучшение эффективности не является переносимым: другой компилятор может скомпоновать запись по-другому.
Программисты, работающие на С, могут иногда повышать эффектив­ность обработки массивов, явно программируя доступ к элементам массива с помощью указателей вместо индексов. Следующие определения:
typedef struct {
C

int field;
} Rec;
Rec a[100];
могут оказаться более эффективными (в зависимости от качества оптимиза­ций в компиляторе) при обращении к элементам массива по указателю:
Rec* ptr;

C

for (ptr = &а; ptr < &a+100*sizeof(Rec); ptr += sizeof(Rec))
...ptr-> field...;
чем при помощи индексирования:
for(i=0; i<100;i++)
…a[i].field…
Однако такой стиль программирования чреват множеством ошибок; кроме того, такие программы тяжело читать, поэтому его следует применять только в исключительных случаях.
В языке С возможен и такой способ копирования строк:
C

while (*s1++ = *s2++)
в котором перед точкой с запятой стоит пустой оператор. Если компьютер поддерживает команды блочного копирования, которые перемещают со­держимое блока ячеек памяти по другому адресу, то эффективнее будет язык типа Ada, который допускает присваивание массива. Вообще, тем, кто программирует на С, следует использовать библиотечные функции, кото­рые, скорее всего, реализованы более эффективно, чем примитивный спо­соб, показанный выше.
Многомерные массивы могут быть очень неэффективными, потому что каждая лишняя размерность требует дополнительного умножения при вычис­лении индекса. При работе с многомерными массивами нужно также пони­мать, как размещены данные. За исключением языка Fortran, все языки хра­нят двумерные массивы как последовательности строк. Размещение
Ada

type T is array( 1 ..3, 1 ..5) of Integer;
показано на рис. 5.3. Такое размещение вполне естественно, поскольку сохраняет идентичность двумерного массива и массива массивов. Если в вычислении перебираются все элементы двумерного массива, проследите, чтобы последний индекс продвигался во внутреннем цикле:

intmatrix[100][200];
C

for(i = 0;i<100;i++)
for (j = 0; j < 200; j++)
m[i][j]=…;
Причина в том, что операционные системы, использующие разбиение на страницы, работают намного эффективнее, когда адреса, по которым проис­ходят обращения, находятся близко друг к другу.
Если вы хотите выжать из С-программы максимальную производитель­ность, можно игнорировать двумерную структуру массива и имитировать од­номерный массив:
C
for (i=0; i< 1 00*200; i++)
m[]0[i]=…;
Само собой разумеется, что применять такие приемы не рекомендуется, а в случае использования их следует тщательно задокументировать.
Контроль соответствия типов для массива требует, чтобы попадание ин­декса в границы проверялось перед каждым доступом к массиву. Издержки этой проверки велики: два сравнения и переходы. Компиляторам для языков типа Ada приходится проделывать значительную работу, чтобы оптимизиро­вать команды обработки массива. Основной технический прием — использо­вание доступной информации. В следующем примере:

Ada
for I in A' Range loop
if A(I) = Key then ...
индекс I примет только допустимые для массива значения, так что никакая проверка не нужна. Вообще, оптимизатор лучше всего будет работать, если все переменные объявлены с максимально жесткими ограничениями.
Когда массивы передаются как параметры на языке с контролем соответ­ствия типов:
Ada
type A_Type is array(lnteger range о) of Integer;
procedure Sort(A: A_Type) is ...
границы также неявно должны передаваться в структуре данных, называемой дескриптором массива (dope vector) (рис. 5.4). Дескриптор массива содержит

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

^ 5.8. Спецификация представления


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

^ Вычисления над битами


В языке С есть булевы операции, которые выполняются побитно над значениями целочисленных типов: «&» (and), «|» (or), «л» (xor), «~» (not).
Булевы операции в Ada — and, or, xor, not — также могут применяться к бу­левым массивам:
type Bool_Array is array(0..31) of Boolean;
Ada
B1: Bool_Array:=(0..15=>True, 16..31 => False);
B2: Bool_Array := (0..15 => False, 16..31 => True);
B1 :=B1 orB2;
Однако само объявление булевых массивов не гарантирует, что они представ­ляются как битовые строки; фактически, булево значение обычно представ­ляется как целое число. Добавление управляющей команды
Ada

pragma Pack(Bool_Array);
требует, чтобы компилятор упаковывал значения массива как можно плот­нее. Поскольку для булева значения необходим только один бит, 32 элемента массива могут храниться в 32-разрядном слове. Хотя таким способом и обес­печиваются требуемые функциональные возможности, однако гибкости, свойственной языку С, достичь не удастся, в частности, из-за невозможно­сти использовать в булевых вычислениях такие восьмеричные или шестнад-цатеричные константы, как OxfOOf OffO. Язык Ada обеспечивает запись для таких констант, но они являются целочисленными значениями, а не булевы­ми массивами, и поэтому не могут использоваться в поразрядных вычисле­ниях.
Эти проблемы решены в языке Ada 95: в нем для поразрядных вычислений могут использоваться модульные типы (см. раздел 4.1):
Ada
type Unsigned_Byte is mod 256;
UI,U2: Unsigned_Byte;
U1 :=U1 andU2;

^ Поля внутри слов


Аппаратные регистры обычно состоят из нескольких полей. Традиционно до­ступ к таким полям осуществляется с помощью сдвига и маскирования; опе­ратор
field = (i » 4) & 0x7;
извлекает трехбитовое поле, находящееся в четырех битах от правого края слова i. Такой стиль программирования опасен, потому что очень просто сде­лать ошибку в числе сдвигов и в маске. Кроме того, при малейшем измене­нии размещения полей может потребоваться значительное изменение про­граммы.
- Изящное решение этой проблемы впервые было сделано в языке Pascal: использовать обычные записи, но упаковывать несколько полей в одно сло­во. Обычный доступ к полю Rec.Field автоматически переводится компиля­тором в правильные сдвиг и маску.
В языке Pascal размещение полей в слове явно не задается; в других языках такое размещение можно описать явно. Язык С допускает спецификаторы разрядов в поле структуры (при условии, что поля имеют целочисленный тип):
C
typedef struct {
int : 3; /* Заполнитель */
int f1 :1;
int f2 :2;

C
int : 3; /* Заполнитель */
int f3 :2;
int : 4; /* Заполнитель */
int f4 :1;
}reg;
и это позволяет программисту использовать обычную форму предложений присваивания (хотя поля и являются частью слова), а компилятору реализо­вать эти присваивания с помощью сдвигов и масок:
reg r;
C
[с] int i;
i = r.f2;
r.f3 = i;
Язык Ada неуклонно следует принципу: объявления типа должны быть абстрактными. В связи с этим спецификации представления (representation speci­fications) используют свою нотацию и пишутся отдельно от объявления типа. К следующим ниже объявлениям типа:
type Heat is (Off, Low, Medium, High);
type Reg is
Ada
record
F1: Boolean;
F2: Heat;
F3: Heat;
F4: Boolean;
end record;
может быть добавлена такая спецификация:
Ada
for Reg use
record
F1 at 0 range 3..3;
F2 at Orange 4..5;
F3at 1 range 1..2;
F4at 1 range 7..7;
end record;
Конструкция at определяет байт внутри записи, a range определяет отво­димый полю диапазон разрядов, причем мы знаем, что достаточно одного бита для значения Boolean и двух битов для значения Heat. Обратите внима­ние, что заполнители не нужны, потому что определены точные позиции полей.
Если разрядные спецификаторы в языке С и спецификаторы представле­ния в Ada правильно запрограммированы, то обеспечена безошибочность всех последующих обращений.

^ Порядок байтов в числах


Как правило, адреса памяти растут начиная с нуля. К сожалению, архитекту­ры компьютеров отличаются способом хранения в памяти многобайтовых значений. Предположим, что можно независимо адресовать каждый байт и что каждое слово состоит из четырех байтов. В каком виде будет храниться це­лое число 0x04030201: начиная со старшего конца (big endian), т. е. так, что старший байт имеет меньший адрес, или начиная с младшего конца (little endi­an), т. е. так, что младший байт имеет меньший адрес? На рис. 5.6 показано размещение байтов для двух вариантов.

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

^ Производные типы и спецификации представления в языке Ada


Производный тип в языке Ada (раздел 4.6) определен как новый тип, чьи зна­чения и
операции такие же, как у родительского типа. Производный тип мо­жет иметь представление, отличающееся от родительского типа. Например, если определен обычный тип Unpacked_Register:
Ada
type Unpacked_Register is
record

end record;
можно получить новый тип и задать спецификацию представления, связан­ную с производным типом:
Ada
type Packed_Register is new Unpacked_Register;
for Packed_Register use
record

end record;
Преобразование типов (которое допустимо между любыми типами, получен­ными друг из друга) вызывает изменение представления, а именно упаковку и распаковку полей слов в обычные переменные:
U: Unpacked_Register;
Р: Packed_Register;

Ada

U := Unpacked_Register(P);
Р := Packed_Register(U);
Это средство может сделать программы более надежными, потому что, коль скоро написаны правильные спецификации представления, остальная часть программы становится полностью абстрактной.

5.9. Упражнения


1. Упаковывает ваш компилятор поля записи или выравнивает их на грани­цы слова?
2. Поддерживает ли ваш компьютер команду блочного копирования, и ис­пользует ли ее ваш компилятор для операций присваивания над массивами и записями?
3. Pascal содержит конструкцию with, которая открывает область види­мости имен так, что имена полей записи можно использовать непосред­ственно:

type Rec =


record


Paskal
Field 1: Integer;
Field2: Integer;
end;
R: Rec;
with R do Field 1 := Field2; (* Правильно, непосредственная видимость *)
Каковы преимущества и недостатки этой конструкции? Изучите в Ada конструкцию renames и покажите, как можно получить некоторые аналогичные функциональные возможности. Сравните две конструк­ции.
4. Объясните сообщение об ошибке, которое вы получаете в языке С при попытке присвоить один массив другому:
C

inta1[10],a2[10]:
а1 =а2;
5. Напишите процедуры sort на языках Ada и С и сравните их. Убедитесь, что вы используете атрибуты в процедуре Ada так, что процедура будет обрабатывать массивы с произвольными индексами.
6. Как оптимизирует ваш компилятор операции индексации массива?
7. В языке Icon имеются ассоциативные массивы, называемые таблицами, в которых строка может использоваться как индекс массива:
count["begin"] = 8;
Реализуйте ассоциативные массивы на языках Ada или С.
8. Являются следующие два типа одним и тем же?
Ada

type Array_Type_1 is array(1 ..100) of Float;
type Array_Type_2 is array(1 ..100) of Float;
Языки Ada и C++ используют эквивалентность имен: каждое объявление типа объявляет новый тип, так что будут объявлены два типа. При струк­турной эквивалентности (используемой в языке Algol 68) объявления типа, которые выглядят одинаково, определяют один и тот же тип. Каковы преимущества и недостатки этих двух подходов?

9. В Ada может быть определен массив анонимного типа. Допустимо ли присваивание в следующем примере? Почему?
Ada
А1, А2: аггау( 1.. 10) of Integer;
А1 :=А2;

chop-po-raspisaniyu-peresechenie-vengerskoj-granici-v-niredgaze-vozmozhno-poseshenie-torgovogo-centra-tesco-tranzit-po-territorii-vengrii-slovenii-vecherom-poselenie-v-otel-v-slovenii-nochleg-3-den.html
chop-posadka-v-avtobus-prohozhdenie-ukrainsko-vengerskoj-granici-pereezd-v-tokaj.html
chop-v-06-58-peresechenie-granici-na-ukrainskom-avtobuse-v-g-niredhaze-peresadka-na-turisticheskij-avtobus-s-video-kondicionerom-wc-pereezd-v-mishkolc-tapolca.html
chop-v-58-po-raspisaniyu-tranzit-po-territorii-vengrii-slovenii-nochleg-3-den.html
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат