лекция 8 (1161103), страница 2

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

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

Глава 2: Составные ТД

Составные ТД

- Массивы (регулярный тип, последовательность элементов одного и того же типа)

- Записи (в современных яп присутствуют как класс)

- Множества

- Таблицы

- Файлы

- Строки (можно трактовать как массивы символов, но это не совсем удобно).

В современных ЯП:

- Массивы

В документации на языки Java и Cи# массивам там уделено всего несколько страниц. Но в Си# есть тип коллекций ArrayList - чистые объекты, предлагающие функциональность массивов. Теоретически можно вообще обойтись без массивов, однако из соображений эффективности реализации понятие массива сохранено. Хотя мы видим, что современное понятие класса, в общем-то, включает в себя понятие массива.

В Си++ старое понятие массивов сохранено, но средства языка позволяют реализовать объекты-массивы.

- Запись замещена понятием класс.

- Множества, Таблицы, Файлы – объекты из стандартной библиотеки.

В языке Паскаль присутствуют все перечисленные составные тд, кроме таблиц. В Обероне (потомке Паскаля) есть записи(являются объектами), массивы, множества приведены к одному тип set, а таблиц, строк и файлов просто нет.

Современные яп существенно упрощают базисную систему типов при помощи классов.

Массивы

Какие атрибуты есть у массивов. Для простоты будем рассматривать одномерные массивы - вектора. Это последовательность элементов одного и того же типа длины N, основная операция для вектора - индексирование: V[i], V(i) – в Ада, Фортран.

Атрибуты:

1) AB:T; - базовый тип, или тип компоненты вектора

2) L..R - начальный и конечный индексы

3) N – Длина (L – R +1, если L и R имеют некоторую целочисленную интерпретацию)

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

Паскаль

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

type A = array [L..R] of T;

type B = array [L..R] of T;

L, R - константные выражения. Таким образом изменить границы массива, или ео длину во время выполнения никак нельзя. Как следствие, никакой мало-мальски серьёзной программы на Паскале не напишешь. Потому что в любой мало-мальски серьёзной программы на Паскале должны встречаться массивы, каждый объект типа массив должен иметь свой тд, различные тд с различными именами в общем случае в Паскале считаются различными. Объекты типа А и В различны и не совместимы даже по присваиванию. Например, нельзя написать универсальную процедуру скалярного произведения массивов (после введения нового типа (type C = ...) придётся писать новую функцию). Возникает проблема – если процедура обрабатывает массивы, то для каждого типа массивов надо писать свою процедуру обработку.

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

Отметим, что есть еще индексный тип – базовый тип диапазона. Это может быть целочисленный тип, перечислимый тип. Дискретные типы, которые можно использовать так или иначе в Паскаль сводятся к целому либо к перечислимому типу. Кроме того в Паскаль как индексный тип может использоваться символьный тип, который не является ни перечислимым (как в Аде).

Модула2

В языке Модула-2 (ответ на недостатки Паскаля в системном программировании) есть ряд существенных изменений.

Чтобы решить проблему универсальности обработки массивов (см. выше) придумали следующее. Для всех объектов данных массивов, которые не являются формальными параметрами процедур и функций, все атрибуты являются статическими. Для объектов, являющихся формальными параметрами – L и R являются динамическими атрибутами. Введено понятие открытого массива - ARRAY OF T. Мы задаём только тип массива, а его длина остаётся неизвестной, и такой тип данных может появиться только как формальный параметр процедур и функций.

PROCEDURE SUM(VAR X:ARRAY OF REAL): REAL;

Для открытых массивов L,R, N неизвестны во время выполнения, для простоты считается L = 0; R = N-1; существует специальная HIGH(X) - динамически вычисляемая функция, которая дает R. С каждым открыт массивом неявно передается дескриптор массива, в котором хранится его длина. В то же время базовый тип элементов известен. С одной стороны эффективность языка Паскаль сохранена, потому что требования к переменным типа массива он такие же как и в Паскаль – все атрибуты зафиксированы в момент трансляции. А гибкость решена за счет введения для процедур и функций понятия открытого массива.

Ада

Язык Ада является в некотором смысле развитием этого подхода. Там есть понятие типа и подтипа, эти понятии применимы не только к простым тд, но и к массивам.

Объявление массива имеет вид:

type A is array (INDEX range L..R) of T; явным образом указываем тип базового элемента, указываем диапазон range L..R, и указываем базовый тип диапазона.

Если речь идет об объектах типа А, необходимо чтобы все соответствующие значения были статические (тип Т и тип INDEX задаются статически, L и R обязаны быть константными выражениями). Тогда под объекты типа А можно отводить память, присваивать эти объекты.

В Аде существует понятие неограниченного типа, что относится и к массиву. Неограниченный массив:

type B is array (INDEX range <>) of T; можно не ограничивать как раз значение L и R.

• Кроме того есть механизм выведения нового типа:

type NewType is new OLDTYPE; - никак не совместим с типом-родителем OLDTYPE, несмотря на то, что новый тип наследует и множество допустимых значении и набор операций.

• Механизм выведении подтипа:

subtype NewST is OLDT; - полностью совместим по операциям с типом-родителем OLDT, кроме того множество значений и набор операций наследуются.

• И еще в Аде после определения типа может стоять уточнение:

1) уточнение для простого тд

type POSITIVE is new INTEGER range 1..MAX_INT

При этом тип данных POSITIVE абсолютно не совместим с типом INTEGER. И если далее мы укажем диапазон 1..50, то придется дописать к какому типу POSITIVE или INTEGER он относится.

2) уточнение для массива

type C is new B range 1..100;

subtype D is B range 0..10;

subtype E is B range 1..11;

subtype F is B range 1..10;

Мы породили новы тип С и три подтипа, принадлежащих одному типу B. Переменные типа С никак несовместимы с переменными типов D, E, F.

Если у нас есть тип Т и из него механизмом подтипов выведены типы Т1, Т2, Т3, то объекты типа Т совместимы с объектами типов Тi (i=1..3).

Х:Т;

Х1:Т1; // лежит в диапазонеL1..R1

Х2:Т2;

Х3:Т3;// лежит в диапазонеL3..R3

Х=Х1; // допустимо

Х1=Х3; //формально допустимо, однако компилятор автоматически проверяет, попадает ли соответствующие переменные в соответствующий диапазон

Но совместимы ли между собой D, E и F? По документации языка Ада они совместимы по присваиванию, только если они имеют одинаковую длину. Таким образом, совместимы только D и E.

X1:D;

X2:E;

X3:F;

X1 := X2;

X2 := X3; // ошибка!

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

Y:B; // ошибка, потому что компилятор не может произвести распределение памяти, здесь нет диапазона индексов

Y:B range -1..9; // можно

Будет ли переменная У совместим с Х1 или Х2? Заметим, что У, Х1 и Х2 принадлежат одному и тому же типу В. Y принадлежит анонимному подтипу типа B, следовательно, он будет совместим с типами D и E, так как длина объекта 11 элементов. Неограниченные типы можно использовать для введения новых подтипов, но это неосновное их назначение.

Неограниченные типы могут использоваться для формальных параметров процедур.

function SUM(X:B) return T; Мы можем обращаться к данной функции и с Х1, и сХ2, и сХ3, и с У, так как все они объекты типа В.

Для каждого массива определены специальные атрибутные функции. Если Х объект регулярного типа (массив), то для него определены атрибуты:

X' LENGTH длина

X' LOW индекс первого элемента

X' HIGH индекс последнего элемента

X' RANGE диапазон от X' LOW до X' HIGH

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

function SUM(X:B) return T;

for i in X'RANGE loop

S:=S+X(i);

end loop

return S;

Таким образом, все объекты данных у нас имеют статические атрибуты и проблема эффективности решена, а проблема гибкости решена за счет того, что у неограниченных объектов все атрибуты динамические.

Если речь идет о многомерных массивах, то у каждого атрибута добавляется параметр i, который обозначает номер измерения массива (от 1 до к, где к – число измерений, не путать с длиной). В одномерном случае – единичка, которую можно опускать.

Оберон.

В языке Оберон (минимальном ЯП) продолжен подход языка Модула 2, а именно: если объект данных, то все характеристики статические, а если массив, то границы от 0 до N-1. Отсутствует понятие перечислимого тд, и понятие диапазона. Все массивы начинаются с 0 и заканчиваются N-1, есть понятие открытого массива.

ARRAY N OF T; // N – длина массива

ARRAY OF T; // открытый массив

В Обероне2 появились многомерные открытые массивы, есть функция High(x[i]) – дает индекс крайнего элемента по каждому из измерений, i меняется от 1 до к, где к – количество измерений.

Современные языки.

В языках Java, C# и Delphi массивы - частные случаи объектов. Элементы простых типов данных также являются частными случаями объектов, есть специальные классы, которые представляют эти типы данных как объекты. Объекты соответствующих классов - только объекты из динамической памяти, как следствие массивы являются объектами из динамической памяти. Диапазон индексов – диапазон целочисленный от 0 до N-1, поэтому для задания длины и границ диапазона необходимо задать только количество элементов. Поскольку место под массивы отводится в динамической памяти, то и атрибут N является чисто динамическим. Есть понятие только чистого динамического массива.

Объявление массива:

int [ ] a;// [ ] – указывают на то, что это массив

а – с одной стороны имя массива, а с другой только ссылка на объект.

a = new int [10]; //Только после этого массив начинает существовать.

У всех массивов есть методы a.length – показывает длину массива, a.setlength – позволяет установить новую длину массива.

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

Список файлов лекций