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

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

TYPE ARR = ARRAY N of T, где N – количество элементов.

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

Проблема длины - самая главная проблема.

Длина – количество элементов массива.

Длина – атрибут массива. В языке стандартный Pascal было принято самое жесткое решение : длина – это атрибут типа, и для всех объектов этого типа этот атрибут не меняется. Как следствие, если мы описываем тип массива, то все массивы этого типа обязаны быть одинаковой длины.

Кроме длины есть понятие диапазон индексов. Заметим, что для разных диапазонов индексов может быть одна и та же длина (например, 0…9 и 1…10).

В языке стандартный Pascal диапазон индексов является атрибутом типа. Как следствие, все значения регулярного ТД имеют один и тот же диапазон индексов. Это один из самых главных недостатков этого языка. Например, попробуем написать функцию скалярного произведения векторов на языке Pascal. Она должна возвращать real и иметь в качестве аргументов два массива А1 и А2. Уже в описании функции должно фигурировать имя типа этих массивов.

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

В результате этого для написания реальных задач стандартный Pascal мало применим. Даже писать на нем стандартные библиотеки, которые обрабатывают массивы, просто невозможно. И нужно использовать расширения, которые введены в языке Turbo Pascal.

В чем же преимущества такой жесткости?

• контроль, надежность

• удобство распределения памяти.

Но как следствие, недостаток гибкости.

На основе проблемы длины ( диапазона индексов) есть два конфликтующих требования.

• гибкость

• эффективность, надежность

В Pascal эффективность и надежность доведены до предела, но нет гибкости.

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

ARRAY диапазон OF T; // обычный массив в Modula2

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

Открытый массив может появляться только как тип аргумента процедуры или функции.

Т.е. можно написать процедуру

PROCEDURE SCAL (VAL A1,A2: ARRAY OF REAL):REAL.

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

Т.о., атрибут длина для открытого массива – это динамический атрибут экземпляров типа, тогда как для обычного массива атрибут длина и диапазон индексов являются статическими атрибутами типа. Считается, что для открытых массивов любой диапазон сводится в диапазон от 0 до HIGH(A)-1, где HIGH(A) - некоторая функция, применимая только к экземплярам открытого массива, которая дает длину этого массива.

HIGH(A) – это и есть динамический атрибут длина. Иначе говоря, система типов в языке Modula2 и Oberon расширена для улучшения гибкости.

Отметим, что наиболее мощное понятие массива в языке Ада.

Лекция 9

В современных ЯП (Java, C#, C++) индексация массивов ведётся от 0 до N-1,где N – длина массива. С точки зрения машинных операций, в этом случае доступ к элементам массива наиболее эффективный. В языках Ada, Modula2, Pascal индексы массива могут быть произвольными диапазонами дискретного типа.

Рассмотрим самую главную проблему – проблему длины массива.

Здесь возникает два основных вопроса : чьим атрибутом является длина, и вопрос о статичности /динамичности этого атрибута.

С точки зрения распределения памяти, надежности (контроля) наиболее подходящий вариант, когда длина – статический атрибут. Мы говорили, что в языке Паскаль длина – это статический атрибут всего типа в целом, т.е. у двух массивов одного типа не может быть различная длина. Но, как следствие, при таком подходе теряется гибкость. Языки Modula2 и Oberon решают эту проблему следующим образом: для каждой переменной типа массив (т.е. ОД) длина – статический атрибут типа; но для формальных параметров сделано исключение: появляется понятие открытый массив, в котором фиксируется только тип элементов, но не фиксируются диапазоны.

Считается, что для открытых массивов любой диапазон сводится в диапазон от 0 до HIGH(A)-1, где HIGH(A) - некоторая функция, применимая только к экземплярам открытого массива, которая дает длину этого массива.HIGH(A) – это и есть динамический атрибут длина. Иначе говоря, система типов в языке Modula2 и Oberon расширена для улучшения гибкости. Синтаксис открытого массива – имя : ARRAY OF T

Т.о., атрибут длина для открытого массива – это динамический атрибут экземпляров типа, тогда как для обычного массива атрибут длина и диапазон индексов являются статическими атрибутами типа.

При индексировании открытого массива вставляется квазистатическая проверка типов, т.к. компилятор ничего не может контролировать (он ничего не знает о длине массива).При этом в языке Oberon никакие квазистатические проверки отключать нельзя по определению.

В языке Ада была предпринята попытка компромисса. Система массивов языка Ада наиболее развитая из рассматриваемых языков. Основная проблема такова: если длина – это статический атрибут, это эффективно и надежно, но не гибко. В Ада эксплуатируется понятие неограниченного типа данных. Т.е. типы данных являются параметризированными, например, вещественный тип данных

type T is digits; (его параметр – количество цифр).

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

Что обязательно должно быть зафиксировано при определении ТД массив?

В языке Ада синтаксис определения массива следующий:

array(тип_индекса range границы) of тип ;

Границы диапазона можно параметризировать. Если указать границы L..R, то тип является ограниченным; если вместо границ указать < >, то тип данных – неограниченный. Тип индекса, по умолчанию,– INTEGER.

Для чего нужны неограниченные массивы?

Вспомним концепцию подтипа. Типы данных не совместимы по операциям, а подтипы одного и того же типа совместимы ( но компилятор проверяет некоторые ограничения).

Неограниченные массивы в основном употребляются как типы для формальных параметров, а конкретные объекты данных(переменные) обязаны быть объектами ограниченных типов данных. Т.е. в тот момент, когда отводится память под ОД, компилятор должен знать его размер.

Например, можно объявить неограниченный тип массива

type RealVector is array (range<>) of REAL;

Тогда X:RealVector; вызовет ошибку, т.к. компилятор не сможет произвести распределение памяти. Иначе говоря, если речь идет об ОД (т.е. переменной или константе регулярного типа), компилятор должен знать все характеристики ( в том числе длину). Т.о., длина является статическим атрибутом объекта данных, т.е. для каждого ОД массива компилятор должен знать его длину.

Корректным будет объявление X:RealVector (0..250);

Теперь компилятор знает диапазон индексов (0..250) и длину (251).

Язык Ада отличается тем, что в нем развита система атрибутных функций, т.е. есть специальные функции, которые возвращают значения атрибутов.

Например, A’LENGTH в зависимости от того, что такое А, может быть либо статическим, либо динамическим атрибутом (например, для переменной – этот атрибут статический, для формального параметра, который передается по ссылке, этот атрибут динамический).

Если А – массив, атрибут LENGTH выдает длину A’LENGTH.

Для объектов неограниченного типа длина LENGTH – динамический атрибут, а для ОД переменных и констант, LENGTH является статическим атрибутом.

Объекты неограниченного ТД могут появляться как формальные параметры процедур и функций.

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

function SCAL (x, y : RealVector) return REAL;

Фактическим параметром этой функции может быть произвольный объект подтипа RealVector.

Кроме атрибута LENGTH есть специальные атрибутные функции: X’LEFT, X’RIGHT, X’RANGE {возвращает диапазон L..R}.

Можно записать

For i in X’RANGE

Loop

X(i):=…

Здесь i гарантированно попадает в корректный диапазон индексов, и компилятору языка Ада никакие квазистатические проверки вставлять не требуется.

Все сказанное относится и к многомерным массивам {A’LENGTH(i), где i – номер от 1

до N}.

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

Длина является статическим атрибутом ОД, т.е. обеспечивается эффективность распределения памяти, и, кроме этого, надежность.

Рассмотрим, чем обеспечивается надежность.

Пусть есть неограниченный ТД RealVector, тогда различные ОД будут содержать подтипы: например, А: RealVector(0..10), Х: RealVector(0..250).

Но подтипы одного и того же типа совместимы между собой. Формально, с точки зрения компилятора, Х и А объекты одного и того же типа RealVector, но они принадлежат к разным подтипам. Присваивание элементов различных подтипов является квазистатически контролируемым. Например, присваивание X: =A; или А: =Х; выдаст ошибку, потому что правило языка Ада гласит, что переменные различных подтипов одного и того же регулярного типа данных совместимы тогда и только тогда, когда количество элементов в них совпадают.

Поэтому, если мы опишем

Х1: RealVector (1..251);

А1: RealVector(-5..5);

то, несмотря на то, что все переменные А, А1, Х, Х1 имеют различные поддиапазоны, длины А и А1 , Х и Х1 совпадают, и присваивания А=А1; и Х=Х1; допустимы.

Во всех ли случаях компилятор может проверить это соответствие?

Нет. Пусть процедура F:

F (A, B: RealVector);

Корректно ли присваивание А :=В?

Компилятор ничего в этой точке сказать не может, т.к. с точки зрения контроля типов все нормально (А и В принадлежат одному и тому же типу, поэтому они статически совместимы по операциям типа), но они могут принадлежать различным подтипам. Т.е. , если RealVector – неограниченный тип, то компилятор в этом месте вставляет квазистатическую проверку; и, если длины не совпадают, здесь выдается динамически ошибка. Если RealVector – ограниченный тип, то никакой квазистатической проверки не требуется.

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

Но в языке Ада существует понятие динамического массива.

Динамический массив – это массив, длина которого не известна в момент трансляции, т.е. некоторые переменные имеют динамическую длину. Это локальные переменные в блоках. Т.е., если объект данных – локальная переменная, то она описана внутри какого-то блока (например, тела процедуры). В этом случае границы могут быть неизвестны в момент трансляции.

Например,

аrray (INDEX range L..R) of T;

В динамическом массиве L и R не обязаны быть константными выражениями.

Например,

PROCEDURE A (N: INT,…)

Локальная переменная Х может быть описана как массив от 1 до N:

X: array(1..N) of T;

Здесь правая граница массива Х – некоторая переменная блока( квазистатическая).

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

Длина динамического массива – квазистатическая (она определяется в момент входа в блок), т.е. и память под эти переменные отводится тоже в процессе входа в блок.

Термин динамический массив в языке Ада несколько не корректен. Настоящий динамический массив – это массив в современных ЯП (C#,Java); здесь длина массива является атрибутом объекта данных. Как следствие, способ реализации таких массивов – только динамическая память, потому что только на основе динамической памяти можно реализовать полностью динамический атрибут длина. Это как раз сделано в современных объектно-ориентированных ЯП.

В языках Java, C# общий синтаксис такой:

int[] имя; // здесь имя выступает только как ссылка на объект динамической памяти.

Инициализация:

int [] a=new int[20];

Теперь а – ссылка на массив из 20 элементов.

Массив можно рассматривать как некоторый объект какого-то класса, у которого есть функции:

a.Сlone(); /* возвращает ссылку на новый массив, который является точной копией другого массива */,

a.Length;

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

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