Лекция 6 (1160839), страница 2

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

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

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

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

//0..HIGH(A)

//массив совместим с любым типом

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

В данном случае возможно лишь явное преобразование:

X:NAT;

I: Integer;

X:=I;//error!

I:=X;//error! Обьекты РАЗНЫХ типов(ключевое слово new – NAT - это НОВЫЙ тип)

Однако возможны явные преобразования:

X:=NAT(I);//тут компилятор вставит квазистатическую проверку

I:=INTEGER(X);

Случай подтипа:

subtype POS is INTEGЕR range 0..MAX_INT

X: POS; I: INTEGER;//тут мы завели 2 обьекта одного типа данных

I:=X;

X:=I;//тут компилятор (неявно – мы же все-таки с одним типом данных работает) вставит X:=POS(I);

Аналогично решается проблема с массивами.

Вводится понятие неограниченного типа, а после выделяются конкретные типы или подтипы с ограничениями.

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

То есть:

Type Arr is array Integer aj real;//Arr – обьект неограниченного типа

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

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

type TARR is array Integer range 0..N of real

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

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

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

A’LENGTH

A’FIRST

A’LAST

A’RANGE -> range A’FIRST..A’LAST

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

В чем разница в употреблении данных атрибутов у двух вышеприведенных типов?

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

Пояснение:

Использование неограниченного регулярного типа:

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

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

X2: AR;//некорректно: не можем распределить память

X2: Arr range 0..N; //порождаются анонимный подтип типа Ar. Корректно(компилятор может распределить память).

Использование неограниченного регулярного типа:

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

function SUM(A: Arr) return real is

s: real:=0.0;

begin

for i in A’RANGE loop //кстати, i здесь принадлежит типу integer

s:=s+A(i); //заметим, что скобки именно круглые – продолжение традиции Фортран. (Квадратные скобки 0 привилегия Алгол-60)

end loop

return s;

end SUM

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

Subtype Arr1 is Arr range 0..N-1;

Subtype Arr2 is Arr range 1..N;

Пример

Пусть у нас есть функция вычисления скалярного произведения SCAL

function SCAL(X, Y: Arr): return REAL:

begin

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

end

Пусть у нас есть переменные

A: Arr1;

B: Arr2;

В Sum вполне можно передавать и А, и В. А в SCAL?

Возможны 2 трактовки:

1. функции SCAL требуется 2 параметра одной длины

2. функции SCAL требуется 2 параметра одной длины, причем диапазон должен быть один и тот же

Насколько Arr1 и Arr2 совместимы между собой?

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

C: POS;

D: INTEGER:=-1;

C: = D; // ошибка! Выход за границы диапазона

В стандарте языка Ада принято решение: если длины массивов совпадают, то присваивание возможно, даже если диапазоны рознятся. Собственно при программировании функции SCAL надо проверять, совпадают ли длины массивов, поданных в качестве фактических параметров. Если не совпадают, то должно сделать исключение.

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

Замечание

В купе с механизмом статической параметризации можно написать наиболее общий тип. Например, родовую процедуру SCAN , работающую с двумя массивами

1) одинаковых длин

2) с совпадающими базовыми типами элементов

Динамический массив в Ада

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

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

procedure P(N: integer) is

A: array(1..N) of real;//память под локальную переменную отводится в стеке

еnd

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

Современные языки программирования упростили ситуацию «до предела»:

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

Синтаксис:

T[ ] имя = new имя[Len];

В разных ЯП существуют разные способы инициализации массивов.

Пример(C#)

int [ ] a = new int {1, 2, 3, 5, -4};

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

Общий вывод: идея работы с массивами перенесена с раних языков на поздние.

Полезно также использовать такие средства работы с массивами, как array(маскируется под стандартную библиотеку, на деле встроен в CLR(Common Language Runtime)).

Разберем некоторые частные случаи массивов.

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

Как ведут себя многомерные массивы в рзличных языках программирования?

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

int a[N1][N2];//прямоугольная матрица размера N1*N2

В C# реализованы как прямоугольные, так и ступенчатые массивы.

Прямоугольный массив

int [ , ] a;//прямоугольный массив

int [ , ] a= new a[N1, N2];

Обращение:

a[i, j].

Рис1. Прямоугольный массив в памяти.

Ступенчатый массив

int a[ ][ ]

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

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

a = new int [ ] [3];

a[0] = new int[1];

a[1] = new int[2];

a[2] = new int[3];

Адрес выдается дважды - двух-этапно, причем на каждом из этапов осуществляется квазистатический контроль

Рис2. Ступечатый массив в памяти.

Вырезка

Вырезка – это подмножество элементов массива. Понятие вырезки возникало на разных этапах развития языков программирования.

Пусть у нас есть двумерный массив А:

A(N1, N2)// двумерный массив размера N1*N2

A(1, *);//некоторая вырезка из массива.

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

A(2..5, *) – это вырезка содержит вторую, третью, четвертую и пятую «строчки» массива.

А(1..3, 2..4) – еще более хитрая вырезка(второй, третий и четвертый элементы от первой, второй и третьей строк?)

Из рассматриваемых нами языков программирования вырезки поддерживаются лишь Ада, да и то

1. только для одномерных массивов

2. только непрерыные вырезки

Данные ограничения введены в Ада из сображений эффективности.

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

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

Пункт 3.2 Записи

Существует 2 синтаксические школы.

struct имя {

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

}

Понятие записи появилось в 1969 году в языке Pascal:

record

последовательность полей(обьявления переменных)

end

Подобный синтаксис предусмотрен и в Си, и во многих дргих языках.

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

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

(id1, T1)

(id2, T2)

…

(idN, TN)

В массиве, как мы знаем, доступ к элементу осуществляется чрез перацию индексирования (по имени массива А и индексу I мы находим элемент массива D)

[ ]: A, I->D

В записи доступ к элементу записи осуществляется через операцию точка.

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

Пусть R – имя записи, id i-тое – идентификатор поля записи, Т-i-тое – его тип. Схематично доступ к полю выглядит так:

. R, id i-тое  T i-тое

Замечание. Тут возникает проблема: точка – одна из немногих операций в С++, которую нельзя перегрузить.

Существует ли связь между записями и массивами? На первый взгляд – нет. Однако в современных языках происходит интересная тенденция. С точки зрения современных обьектно-ориентированных языков программирования отличие записи от массива(разнотипность элементов) несущественно.

Любая запись – это в некотором роде массив из обьектов.

Помимо обычного синтаксиса(Ob[index]), возможна и такая динамическая операция:

Ob[“fld”]

(сравните с Оb.fld – классическим синтаксисом точки)

Ob.fld=”string”;//если мы обращаемся к полю, а его нет, то оно создается.

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

В остальном синтаксис поведения записи не меняется от языка к языку.

В Си и Pascal(более ранних языках) понятие записи было необходимым. В С++ структуры неожиданно стали классами. Отличие структуры в С++:

1) структура может быть анонимной : struct{…..}

2) структура образует свое собственное пространство имен тегов:

Пример(см time.h – заголовочный файл стандартной библиотеки языка Си)

В языке Си, как мы знаем, существует структура time, и существует также функция time, возвращающая структуру time(Unix). Страуструп при создании С++ столкнулся с проблемой: имя структуры в Си может дуюлироваться с другими именами, а имя класса – нет. Понятие класса обобщило понятие структуры и понятие записи.(Единственное существенное отличие структуры от класса – уровень доступа – в структуре, как мы поним, доступ по умолчанию открытый.)

В Java понятия записи нет. В Оберон – есть , но смысл его иной.

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

Структура в C#

В C# понятие структуры осталось. Однако в данном языке структура - это не совсем класс. На первый взгляд она выглядит как класс и порождается с помощью new.

struct c{……}

C a = new C( );

Отличие структуры от класса в том, что

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

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

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

Пример. (C#)

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

class Point{

int x, y;

}

Point[ ] pts=new Point[1000];//Создаем массив

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

Pts[i]=new Point();

Структуры подобного рода называются POD(Plain Old Data)- класс, совместимый со старой структурой языка Си.

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

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