Ада 83. Закрыта большая дыра в потенциальной ошибочности программ. Не было никакой адресной операции, реализация с автоматической сборкой мусора была не менее надёжна, чем Оберон.

Ада 95. В определенном виде появилась адресная операция – a ‘ access. Изменения внеслись по нескольким причинам – в определении языка всё-таки были какие-то ошибки, недоделки и пропущенные моменты, никакой концепции ООП не было до 95 года, изменились технологические потребности. Ада ранее не допускал использование на других языках – создавался язык как единый, но в 95 году предпосылки изменились – создатели уже не могли рассчитывать на монопольную роль языка. Интерфейс системных вызовов был привязан к языку С, где мы передаём адрес, а по правилам 83 года адресных операций не было. Но надо отдать должное создателям Ада 95 – они сумели расширить язык так, чтобы он оставался не менее надёжным, чем версия 83 года. Да, операцию, выдающую адрес, разрешили, но в случае a: X; брать адрес a нельзя. i:alias integer; - к таким переменным и применима операция access. С точки зрения указателей – TYPE PT is access T; может использоваться только для ссылки на анонимный объект динамической памяти. А вот Pi is access all integer; - может использоваться как на объекты из динамической памяти, так и на объекты из обычной. Мы страхуемся по 2-м каналам – старая семантика остаётся, но появляются дополнительные переменные, к которым применима адресная операция и дополнительный указательный тип. Таким образом, надёжность старых программ обеспечена, а новые программы становятся существенно более надёжными чем если бы использовалась просто адресная операция.

Возвращаясь к понятию ссылки, если язык является строгим, то мы все объекты отправляем в динамическую память, а если ещё и существует автоматическая сборка мусора, то понятие указателя нам не нужно. Языки становятся достаточно надёжными. Тем не менее, в Java появился JNI – Java Native Interface – возможность в языке Java вызывать родные системные вызовы той машины, на которой работает программа. Заметим, что это противоречит принципу WORA, потому что если например используются вызовы Windows, то на другой системе программа работать не будет. С точки зрения разработчиков языка это была ошибка, но она повышает производительность. У C# могут возникнуть другие проблемы – была специально оставлена дырочка, для того, чтобы программисты могли использовать свои методы – unsafe{ …}. Можно использовать например malloc и free. Более того, существует специальный спецификатор fixed(), который может перевести массив байтов в указатель на байт. Мы позволяем явно обращаться к этому байту, код естественно ненадёжен, так что же фиксируется? Надо понять как работает алгоритм сборки мусора. Здесь это Mark and Scan – система пробегается по указателям при нехватке памяти, смотрит, на какие памяти они ссылаются, и помечает их. Все неиспользуемые области памяти сводятся в один блок, как следствие – значения ссылок меняются, но при этом значение ссылки в любой момент времени может измениться. Конструкция fixed говорит, что мы зафиксировали адрес и не можем менять соответствующую ссылку. Такие проблемы возникают в любых системах управления динамической памятью. Всегда когда речь идёт о переменных объектах в C#, Java, Delphi речь идёт о ссылках. В Delphi не C++-принятая версия задания конструкторов через имя класса, а есть ключевое слово construct, тем не менее при разном синтаксисе, семантика одна и та же. Существует ещё один язык с явным понятием ссылки, но там оно отличается от ссылки в семантике этих языков. В языке С++ ссылка это имя некоторого объекта, просто синоним какого-то другого объекта. Ссылки реализуются тоже как указатель, но применима единственная операция – инициализация.

В каких контекстах может стоять такая ссылка – T& a;?

1. Просто переменная такого типа – локальная или глобальная (тогда T& a=b;)

2. В контексте формальных параметров

3. В качестве возвращаемого параметра

4. Как член класса – в конструкторе
   
   
   

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

Лекция 11.

Глава 2. Составные типы данных

C одной стороны - они встроены в базис языка, с другой - не имеют внутреннюю структуру.

Пункт 1. Классификация СТД.

• массивы

• записи/структуры (объединения – частный случай записи)

• множества (есть в паскале)

• файлы (есть в паскале)

• строки («недотип» в паскале)

Например, ‘array’(строка) – это packed array of char. К ним применимы операции сравнения.

Как правило, больше никаких составных данных в языках нет, хотя, можно к ним еще добавить ассоциативные массивы/таблицы (Perl). В большинстве языков мы встретим массивы, записи, строки.

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

Для множеств не существует универсального, одновременно и эффективного мощного средства представления данных. Вместо этого выбирается некоторая реализация и собственно реализация этого понятия входит в библиотеку. Например, возьмем упорядоченный массив и применим к нему quick sort(быструю сортировку) и heap sort – это случай, который говорит о том, что не существует удобного и оптимального для всех способа обработки данных. Так как есть случаи, когда быстрая сортировка превращается в медленную, поэтому существует другой метод сортировки – heap sort – который устойчив и не зависит от распределения величин (например, при работе с БД). Поэтому все зависит от того, какого рода задачи будем решать. Базис составных типов данных скукоживался, а базис простых типов данных расширялся на протяжении развития языков.

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

DxDx…xD -> массив – одномерный массив.

Массив имеет непрерывное расположение в памяти, и для него определена операция индексирования – A,I => ref D.

Чем отличаются массивы в разных языках?

Общее – есть операция индексирования. Например, в C# и Java обязательна инициализация массива T[] имя = new T[expr];

Атрибуты данных у массива (дополнительные к атрибутам типов данных):

• базовый тип => D

• тип индекса (это должны быть непрерывная некая последовательность значений). Больше всего подходят дискретные типы, у которых должны быть определены операции succ(i), pred(i) (например, все целые типы).

• границы значений индекса – L..R и связанное с ним понятие длины length = integer(R)-integer(L)+1.

Когда мы знаем базовый тип массива, он непрерывно расположен в памяти, и компилятор эффективно может определить операцию индексирования. Операция индексирования зависит от L: адрес A[L] + размер Dx[integer(i)-integer(L)].

В языке Паскаль связывание статическое, в нем array[Index] of T – это и есть описатель массива. А в С, C# и так далее, фиксируется не только тип, тип индекса – это всегда integer. Время связывание – не статическое, это определено еще в самом компиляторе.

Массив – компромисс между тремя вещами:

• надежность

• эффективность

• гибкость

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

Язык Си – ориентирован на эффективность, но не ориентирован на гибкость и надежность. Для простоты тип индекса – целый тип, а границы – 0..N-1 . То есть тип D и N – статические атрибуты типа. Тоже самое что и в Паскале, только уменьшили гибкость (ограничили границы). Но чего добились – у нас есть адрес на начало массива и теперь операция индексирования выглядит следующим образом – a[i] = адрес a + i*sizeof(D). Это очень эффективно. Теперь получатся, что имя массива эквивалентно D*. Массив int a[] легко переводится в int*. Мы можем писать a+1 = a[1], a-1 = a[-1]. Эти операции допустимы. (язык ассемблер – на эффективность).

Модула-2:

Открытый массив – шаблон в Модула-2. ( формальные параметры процедуры/функции)

Procedure P (var A:T); - на месте T может быть открытый массив.

ARRAY OF T.

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

VAR R:T; I:INTEGER;

BEGIN

T:=0;

FOR I:=1 TO HIGH(A) DO R:=R+A[I] END;

RETURN R;

END SUM;

High(a) – ведет себя как квазистатический объект, с точки зрения эффективности доступа все тоже самое.

Оберон:

Должны зафиксировать только базовый тип массив, диапазон находится от 0 до Н-1.

TYPE T = ARRAY N OF D;

N - константа.

Неограниченный массив в языке Ада:

Type arr is array (index range <>) of D;

Ограниченный массив:
type Limarr is array (index range<1..N>) of D;

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

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

X:Limarr;

Y:arr; - ошибка.

Z : arr range 0..10; Z – относится к подтипу типа arr – некоторое подмножества значения некоторого базисного типа. Можем ввести W : arr range 1..11;

U : arr range 0..11;

Можно писать z:=w; w:=z; - язык неявно приведет (занимают одинаковое количество памяти), но Z:=U; не пропустит.

Лекция 12.

Глава 3. СТД.

П.2. Массивы.

3 критерия при дизайне понятия массива:

• Надежность

• Эффективность

• Гибкость

Язык Ада ближе всех подошел к компромиссу ближе всех за счёт понятий «тип<->подтип» и «неограниченный массив».

type Index is new INTEGER;
type ARRS is array(1..10) of integer;
type ARRUNL is array(Index range<>) of real;

function SUM(A: опред.типа) – если указываем имя ограниченного типа, то теряем свойство универсальности, но мы можем определить переменную неограниченного типа.

return real is
R:real:=0.0;
begin
for I in A’RANGE loop
// есть ещё атрибуты A’LENGTH, A’FIRST, A’LAST. A’RANGE=A’FIRST..A’LAST
R:=R+A(i);

end loop;
return R;
end SUM;

VAR:T опред;
X:ARRUNL range 0..9;
Y:ARRUNL range -10..10;

i=SUM(X);
j=SUM(Y);

В C#,Java,Delphi есть динамические массивы. С современной точки зрения, индекс принадлежит типу данных int. (диапазон – 0..N-1) Длина является свойством не типа, а экземпляра, массивы – объекты из кучи, а имена - ссылки. Поддержка классов Array и интерфейсов IArray, массивы поддерживают абстракцию непрерывного распределения памяти. Описываются и в C#, и в Java одинаково – T[] x = new T[N]; N – необязательно константа, отводится в динамической памяти массив длины N. Массивы в этих языках ведут себя как классы – у них не свойства, а методы. В С# x.GetLength(0); - взять длину, 0 – номер измерения, однако длину массива мы в C# и Java изменить уже не можем. Можем только перераспределить память под другой массив и скопировать существующий. Есть метод x.Copy(i,j); 0..i-j+1. Длина массива является квазистатическим атрибутом. Появились классы – StringBuilder – для того чтобы строить строки. Обычно строку разбирают и из элементов строят новую, в процессе построения строк чаще всего встречается операция увеличения новой строки – небезопасный способ, неизбежна фрагментация памяти. Этот класс более оптимальным образом умеет разбивать память на подстроки. В Аде тоже есть понятие динамического массива, но фактически оно непохоже на аналогичные при похожем поведении.

procedure P(N:INTEGER) is
A: array(1..N) of real; -здесь N это некий формальный параметр, память отводится в стеке
begin
..
end P;

Несколько слов про многомерные массивы и вырезку.
“вырезка” (slice) – операция которая даёт некоторый диапазон его элементов. Было в языках PL/I, Fortran 90, Ada.
A:array(1..10) of T;
А(2..5)
Операция Copy(I,j) – по сути дела тоже некий аналог вырезки.

В большинстве языков, n-мерный массив это последовательность меньших массивов, расположенных друг за другом.
Pascal
TYPE T2=array[1..N] of T1;
T1=array[1..N] of T;

X[i][j] ~ X[i,j];

C/C++
int n[3][3]; - объявление такого массива эквивалентно **.
(располагаются они последовательно, по строкам, исключением является язык Fortran, там расположение по столбцам)

Java
Многомерный массив – массив.
int [][]x=new int[][3];
for(int i=0;i<3;i++)
x[i]=new int[i+1];