лекции (2011), страница 2

Массивы и их особенности в современных ЯП.

Последовательность однотипных элементов.

D x … x Dn

A[i] – операция индексирования. i – индексное выражение.

Атрибуты массива:

1)Базовый тип (тип элементов) – D

2)Тип индекса (i)

3)Диапазон индекса (длина)

В разных ЯП:

Связывание базового типа статически (везде).

Тип индекса – С/С++/С#/Java/Оберон – всегда тип int (статическое связывание).

Фиксируется нижняя граница значения индекса.

Длина – статическая и динамическая.

Динамическая – чисто-динамическая (можно изменить в любое время) и квазистатическая (значение получено динамически, но изменять нельзя).

Можно длину сделать статической (жестко), оттого сделали квазистатической.

T[] a = new T[N]; //0..N-1

Модула-2:

Понятие открытого массива: зафиксирован базовый тип.

TYPE Arr = ARRAY Index of D;

TYPE Index = [1..N];

ARRAY of D;

Для типа CARDINALL:

Index = CARDINALL[0..N]; //В данном случае индекс задается статически.

//процедура суммирования элементов массива

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

//для любого открытого массива применима функция HIGH –она возвращает //максимальное значение индекса или -1.

VAR S: REAL; I: INTEGER;

BEGIN

S:=0.0;

FOR I:=0 TO HIGH(A) DO

S:=S+A[I];

END;

RETURN S;

END SUM;

Общий синтаксис объявления массива в Обероне

TYPE Arr = ARRAY N OF D;

При таком объявлении N, очевидно, является константой, длина массива – статический атрибут, что позволяет максимально эффективно распределять память. Таким образом

1. распределение памяти отчасти чисто статическое

2. квазистатические атрибуты длины возможны в качестве формальных аргументов

А собственно память распределяется чисто статически.

Механизм типа-подтипа в Ада

Подтип может ограничивать значения базового типа.

Пример

Тип диапазон:

TYPE NAT IS NEW INTEGER RANGE 1..MAX_INT (NEW – означает новый тип)

X: NAT;

Подтип:

SUBTYPE POS IS INTEGER RANGE 0..MAX_INT;

X: POS; I: INTEGER;

I:=X; X:=I ~ X:=POS(I);

Неограниченный тип массива.

D,I – зафиксированы.

L..R – не фиксируемые левые и правая границы.

Итак, в Ада существует 2 типа массивов:

1. регулярный ограниченный – тут фиксируется ВСЕ

TYPE TARR IS ARRAY INTEGER RANGE 0..N of REAL;

1. неограниченный регулярный тип

Разница между первым и вторым типами заключается во времени связывания атрибута длины.

Атрибуты регулярного типа:

A’LENGTH – длина массива

A’FIRST = L

A’LAST = R

A’RANGE = RANGE A.FIRST..A.LAST

У неограниченных типов данных – атрибуты динамические, у ограниченных – статические.

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

Зачем нужны неограниченные типы данных: они нужны для выведения из них других типов данных.

X1: TARR; //ограниченный тип данных

Таким образом, объявление переменной корректно, если компилятор может распределить память

X2: Arr; //Нельзя. Компилятор не может распределять память.

Надо: X2: Arr range 0..N;

Мы вполне можем написать функцию, к примеру, суммирующую все элементы неограниченного регулярного массива:

Function SUM(A: Arr)return real is

S: real := 0.0;

Begin

for i in A’RANGE loop S:=S+A(i); end loop;

return S;

end SUM.

Смысл такой же: описав объект неограниченного типа, мы можем передавать в качестве фактического параметра конкретный объект, принадлежащий, естественно, ограниченному типу.

a:=SUM(X2);

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

В стандарте языка Ада принято решение: если длины массивов совпадают, то присваивание возможно, даже если диапазоны рознятся.

Динамический массив (квазистатический).

Такой массив может быть только локальной переменной.

Динамический массив – это локальный массив, левая и правая граница которого определяются при входе в соответствующий блок.

procedure P(N: integer) is

A: array(1..N) of real;

В языке Oberon есть разница между чисто статическими объектами данных и открытыми массивами. В C# и Java длина массива квазистатическая.

C#, Java:

T[] имя;

new имя[len];

int[] a = new int{1,2,3,4,5}; (С#)

В C# и Java a[i](выход за границы массива) контролируется квазистатически.

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

С, С++: int a[N1][N2];

C#: int [,] a = new a[N1,N2];

int a[ ][ ]; //ступенчатый массив, он же разрывный.

Элементы ступенчатого массива представляют собой ссылки на соответствующие объекты (массивы).

Пример инициализации подобного массива:

a = new int [ ] [3];

a[0] = new int[1];

a[1] = new int[2];

a[2] = new int[3];

Вырезка: подмножество элементов массива.

Фортран:

А(N1,N2)

А(1,*) – 1-я строчка.

А(*,1) – 1-й столбец.

A(2..5,*), A(1..3,2..4) – прямоугольная вырезка.

Ада поддерживает только одномерные непрерывные вырезки.

В остальных нет.

Замечание: в языках Оберон и Модула-2 длина формальных

параметров — открытых массивов является динамическим атрибутом. В

других случаях длина массива — статический атрибут. В Аде формальные параметры неограниченных типов-массивов также имеют динамический

атрибут-длину (равно как и динамические массивы-локальные переменные).

Записи. Недостатки системы типов в традиционных ЯП. Объединения

как средство преодоления этих недостатков. Проблемы, связанные с

объединениями.

struct name {поля}

record последовательность полей end;

Запись – это набор переменных, с которыми можно обращаться как с единым целым.

Задавая набор полей, мы задаем запись( id – идентификатор поля, T – тип поля):

(id1, T1)

(id2, T2)

…

(idN, TN)

Разные типы: тип  класс обертка (упаковка, распаковка)

Java: отсутствует запись – она не нужна. В Обероне есть, но с другим смыслом.

С++: класс – обобщение структуры. (у структур в С собственное пространство имен)

Отличия:

1) Имена (структура может быть анонимной)

2) struct – public, class – private.

Delphi:

Новое – класс.

Старое – record.

C#: Типы – значения.

struct c {}

class F{}

С а = new C();

Отличия от класса:

1)память распределена под типы-значения (если локально – то память под структуры выделяется в стеке)

2) все структуры неявно наследуются из класса Object, но сами наследоваться не могут.

Следует отметить одно из странных свойств структуры в языке С#: у нее нельзя переопределять конструктор по умолчанию. Сделано это было с целью увеличения эффективности языка C#, чтобы впоследствии сделать его моноязыком под .Net.

В случае, когда мы заводим массив из объектов классов, в силу того, что классы – это объекты референциального типа, мы получаем не массив из объектов, а массив из ссылок на объекты.

class Point { int x,y; }

Point[] pointArray = new Point[1000];

Для создания самих объектов необходимо для каждого i написать:

Pts[i]=new Point(); //Неоправданные затраты памяти и времени. Здесь лучше использовать

структуру.

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

Размеченное объединение типов содержит одно выделенное поле (дискретного типа данных) — общее для всех вариантов. Такое поле называется дискриминантом. Значение дискриминанта определяет, по какому варианту выделена память в переменной-экземпляре

размеченного объединения

Запись с вариантами: эквивалентна по мощности, и более синтаксически наглядна. Есть размеченные и неразмеченные объединения. Есть объект типа Т1, Т2. Union просто позволяет их адресовать с одного места памяти:

(C)

union {

T1 t1;

T2 t2;

...

Tn tn;

};

При этом программисты на C/C++ постоянно вынуждены делать однообразные структуры, и потом switch по соответствующему типу, который идентифицируется идентификатором в начале каждого типа.

В Pascal — вариантная часть:

(Pascal)

case ... T of

v1: часть 1;

v2: часть 2;

...

vN: часть N;

end;

(Pascal)

case Boolean of

false: (i: integer);

true: (b: packed array [1..n] of boolean)

end;

Дискриминант отсутствует.

(Pascal)

case family : integer of

SOCKADDR_UN: (...);

SOCKADDR_IN: (...);

end;

family — специальное поле. Если дискриминант описан, то он принадлежит постоянной части, но идейно – вариантной.

Выделение памяти, расширенный синтаксис:

(Pascal)

new(p,t1,..,tn);

Их много, если дискриминантов несколько. Это позволяет выделять ровно необходимое количесвтво памяти, иначе по максимуму. Идиотизм: память отводится, дискриминант не присваивается. Поэтому, его явно надо присваивать. Тут первый недостаток: если забыть или описаться, то никто это никак не проконтроллирует, и не будет работать.

Запись с вариантами решает очень важную проблему объединения типов. Ни одна графическая система не обходится без записей с вариантами.

Неограниченная запись — запись с дискриминантом, параметризованная запись.

В Ada не бывает неразмеченных объединений вообще.

(Ada)

type SOCKADDR(Family : SAType) is record

case Family: SAType of

when SOCKADDR_IN => ...

when SOCKADDR_UN => ...

when others => ...

end case

end record;

В момент размещения в памяти всё должно быть известно (аналогично динамические массивы: P : TArr нельзя, P : Tarr[0..N] можно; Y : SOCKADDR нельзя, Y : SOCKADDR(SOCKADDR_IN) можно).

(Ada)

type Paddr is access SOCKADDR;

PA : Paddr;

PA := new Paddr(SOCKADDR_UN);

Резюме какого-то другого лектора таково: решение проблемы не лучшее.

(Ada)

procedure P(X: RecVal) is

begin

case X.Dic... of

when val1 => ...

when val2 | val => ...

end case

end P;

При изменении системы надо расширить тип и все участки, где используется тип данных. Беда. Надо перекомпилировать весь проект.

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

Страуструп не хотел до последнего включать RTTI, но так как каждые начали включать свои механизмы, пришлось их включить в целях унификации. Но это позволяет программированть свичами — источник ошибок.

Файлы

Вся языки, начиная с Фортран, Алгол и Cobol, имели встроенные средства ввода-вывода. Первый язык без встроенных средств ввода-вывода – Cи.

Стандарт Pascal:

file of T;

Множества также впервые появились в Паскале.

Cтандартный базис операций на множествами:

• set of T : T – множество

• a in T: принадлежит ли a множеству T?

• * S1+S2: объединение множеств

• S1*S2 : пересечение множеств

• S1-S2 : разность двух множеств

• [x] + S: добавить элемент х в множество

• S - [x]: вычесть элемент из множества

Modula-2

SET OF T;

X: BITSET;

INCL(S, X)

EXCL(S, X)

Из Оберона SET OF T исчез. Там «обязан был быть» диапазон [1..K].

В С++ множество «ушло» в стандартную библиотеку языка(STL: map, set, multiset).

Java

Также есть set, map и multiset, реализованные в виде битовых шкал. Пользователь также может реализовывать свои алгоритмы.

Строки

В С++ понятие строки входит в стандартную библиотеку. В Delphi, C#, Java оно встроены в язык.

3. Операторный базис языков программирования. Управление

последовательностью вычислений

Понятие о структурном программировании. Разновидности

управляющих конструкций в современных языках программирования.