Материал из eSyr's wiki.

Предыдущая лекция | Следующая лекция

Содержание 1 Часть 1. Основные понятия традиционных процедурных ЯП 1.1 Глава 2. Составные базисные типы 1.1.1 Пункт 2. Массив (продолжение) 1.1.1.1 Адские массивы 1.1.1.2 Вырезки 1.1.1.3 Прочие вариации 1.1.2 Пункт 3. Записи и структуры 1.1.2.1 Общность записей и массивов 1.1.2.2 Мифы и легенды структур и классов 1.1.2.3 С точки зрения современных ЯП

[править] Часть 1. Основные понятия традиционных процедурных ЯП

[править] Глава 2. Составные базисные типы

[править] Пункт 2. Массив (продолжение)

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

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

В С#, Java, Ada (хотя в ней есть возможность отключить) всегда делается статическая проверка. Для эффективности в совр языках L, R имеют тип int, L = 0.

• Java, Delphi, C# - динамические массивы (коллекции), меняющие длину с сохранением содержимого
• Modula-2, Oberon, Oberon-2 — открытые массивы.

[править] Адские массивы

В Ada понятие массива максимально гибкое. Идея: опирается на концепцию типа. Если мы вводим новый тип, то они несовместимы, а подтипы с типом совместимы, но производится контроль. Массивы – введено понятие неограниченного типа массива.

(Ada)
Type ARR is array (Index range L..R) of  T;

L, R – константное выражения, Т – произвольный тип данных, Индекс – дискретный тип. Неограниченный массив – массив, в котором задан базовый тип индекса, элементов, но не границы.

(Ada)
Type TARR is array (Index range <>)  of T;

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

(Ada)
function SCAL(X, Y : TARR) return T;
нельзя A : TARR;
A : TARR(1..20);
B : TARR(0..20);
C : TARR(0..19);

Относятся к одному типу, но разным подтипам. Поэтому можно вызывать SCAL(A, B), SCAL(B, C), SCAL(A, C). Все эти вызовы синтаксически корректны.

К каждому массиву применимы операции: атрибутные функции, которые выдают значения атрибутов (A'LENGTH, A'FIRST, A'LAST, A'RANGE – выдаёт диапазонный подтип). Как написать SCAL – если не совпадают – исключение, иначе считать:

(Ada)
RES : T;
RES := 0;
for i in X'RANGE do loop
   RES := RES+X(i)*Y(i);
end loop;
return RES;

Если из неё сделать родовой модуль, который параметризует базовый тип, ... . То эта функция хорошо обобщается как родовая функция для вычисления скалярного произведения произвольных массивов.</p>

При трансляции не пропустят A:=B; B:=C; но пропустят совместимые по длине:

(Ada)
A:=C; 

Для параметров такого типа атрибут LENGTH динамический. То же в Modula-2 и Оberon – если мы описываем объекты данных, то они статические, если речь о формальных параметрах – то это динамические аттрибуты, могут меняться от вызова к вызову, но во время выполнения статические. Ада более гибкая – можно использовать произвольный диапазон. Создатели языка ада пошли ещё дальше.

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

(Ada)
procedure P(N : integer) is A : array  (1..N) of T;
begin
end P;
N – переменная,  размещается в стеке, является квазистатической.

Между вызовами массив может менять длину, но во время вызова нет.

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

Пусть есть тип TARR

(Ada)
PT : access TARR;

Такие переменные указывают на массив переменной длины, сам массив находится в динамической памяти, и память определяется при вызове new, и там можно уточнить:

(Ada)
pt := new TARR(-N..N);

Это уже динамический массив, итак как N переменная.

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

[править] Вырезки

Экзотическое понятие – вырезка. То есть можно определить сегмент массива.

(Ada)
A : TARR(1..20);
x : TARR(0..3);
x:=A(2..5);

A(2..5) – эта вырезка, она может использоваться везде, где может использоваться массив, она определяет подмассив о 4 элементах. Вырезка особенно нужна математикам. Такая возможность вырезки появилась и в FORTRAN-90:

(FORTRAN-90)
A(2..5)
M(*, i)
M(i, *) 
M(2..4, 3..5)

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

FORTRAN – единственный язык, в котором строки хранятся по столбцам

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

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

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

[править] Прочие вариации

В большинстве языков программирования прямоугольные массивы хранятся по строкам (последний индекс меняется быстрее). Есть исключения: C#

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

(С#)
a = new int[3, 5]

а есть ступенчатый массив (jagged)

(С#)
int [][] a; /*первый уровень представляет  ссылки на массивы*/
a = new(int [10][]);
/*Инициализация*/
a[0]= new int[10];
a[1]= new int[3];
и  т. д.

То есть, можно иметь строки разной длины. Они выглядят как матрицы, но позволяют экономить память.

Синтаксис нам не важен. В процессе изучения языков главное - концепции.

Трудности, связанные с реализациями массивов, в частности в скриптовых языках. Например, в Perl и Lua есть ассоциативные массивы, в Lua есть хеши, которые позволяют использовать не только набор, но и ключи:

(Lua)
a[«key»]

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

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

В C# и Delphi нет возможности перегружения инлексирования, но есть понятие индексера. Возможность индексирования по ключу настолько важна, что если нет возможности перегрузки операции в языке, то вводятся индексаторы. В Perl и Lua это встроено в базис языка, но это только для проблемно-ориентированных языков, но для универсадьнцых языков базис упрощают, и всё выносят в библиотеки.

[править] Пункт 3. Записи и структуры

Впервые понятие записи появилось в 60х в языке Algol W. Потом перенеслось в Pascal без изменений</p>

(Pascal)
record
    список переменных;
end;

Традиционно, операция доступа имеет вид:

(Pascal)
X.имя_поля

Чем отличаются записи от массива в Pascal? Если массив фиксирован и по типу и длине, то запись фиксируется по длине. Массивы и записи суть принципиально разные вещи, хоть и те, и те есть последовательность переменных. Кроме опреации доступа больше никаких операций нет. Сами записи можно присваивать, передавать как параметр и т. д.

[править] Общность записей и массивов

Изначально они разошлись. Но вообще, можно трактовать все эти элементы одинаково. Для массива есть операция индексирования, которая ставит ссылку на элемент, операция доступа, которая имени объекта и поля ставит ссылку на поле. Отличие в том, что в массивах это вычисляется, а в записях поле статическое – смещение относительно начала записи, неслучайна в MS ASM есть возможность созждания записей, которая синтаксически похожа.

Массив = D  x D  x D  x D  ... x D
  a[i]-ссылка на элемент по номеру

Запись = D1 x D2 x D3 x D4 ... x Dn
  a.b -ссылка на элемент по имени 

И операция индексирования, и опреация доступа – двумесные операции доступа. Существуют языки – Lua, Java Script – интерпретируемые языки для писания сценариев. Изначально JavaScript предназначен для динамического изменения страницы на стороне клиента, но это не единственное применение. В JavaScript нет записей, как и в других современных языках. В JavaScript немножко хитрее.

Представим себе классическую запись window.title синтаксически это выглядит как обращение к полю title объекта window. На саомм деле в классическом языке программирования известны адрес и смещение, в современных языках – форма доступа к специальным опреациям – современные скриптовые объекты представляют некоторые интерфесы - набор операций, которые можно делать с объектом. Например, в ActiveX есть Idispatch, то есть соответствующие интерфейсы предоставляют действия трёх видов – получить идентификатор, SetValue – позволяет по идентификатору установить значение, GetValue – получить значение по ID. Если нельзя получить ID, то свойства нет. Если есть, то вызывается Set/GetValue.

Все скриптовые объекты должны поддерживать возможность доступа по имени, и это имя, обращение к нему происходет динамически, поэтому почему бы не разрешить вычисление его. И тогда почему же не распространить то же самое на языковые объекты. Тогда если o.name, то проверяем, есть ли такое свойство, и тогда мы им пользуемся. Но В JavaScript есть такая тонкость – если поля нет, то оно добавляется. Так же можно обращаться o[«name»] o[0], o[1], если известны ID. Таким образом разница между массивом и объектом стёрта.

Соответственно, можно динамически менять длину массива – если нет 100-го элемента, но добавляется, если нет поля, оно добавляется. Откуда это следут? С точки зрения специфики – сначала разрабатывался NetScape, чтобы можно было добавлять анимацию, и вообще динамически менять страницу на стороне клиента (Изначально назывался LiveScript, но потом Sun уговорила называть JavaScript). Тут полный динамизм, поэтому говорить об оптимизации операций не приходится, и эффективность тут дело десятое, она не нужна и добиться её трудно.

Но с точки зрения традиционных ЯП подобные конструкции невозможны с точки зрения эффективности, поэтому и вводят разлиные понятия массив и запись. Дальше, понятие записи явилось базисом для дальнейшего расширения – понятия класса. Пример – C++: там структуры становятся классами, причём единственное различие – умолчаниями – у класса по умолчанию private, у struct – public. Больше никакой разницы. Аналогично при наследовании. В остальном разницы нет, и это приводит к замешательствам.

[править] Мифы и легенды структур и классов

К примеру, распространён такой миф, что в класс можно добавлять методы, а структуру – нет. Это чушь собачья. Есть единственное маленькое но, которое связано с совместимостью – в C совершенно идиотское понятие имени структуры. Концепция классов говорит, что имя и есть имя класса. Но только struct name, образует совершенно другое проостранстов имён. В одной области видимости доступен только один объект. Простая система, которая была во всех ЯП. Но struct образует другое пространство имён.

(C++)
struct C {
    struct B {} b;
}
struct C с;
struct B b; хотя казалось  бы, что, это имя локализовано.

Поэтому в плюсатом компиляторе вложенные классы локализуются, а структуры – нет. Это единственное отличие. Можно, было, конечно, переделать программы, но это было уже проще. Необходимость совместимости диктовалась необходимость совместимости с библиотеками UNIX. Поэтому C++ должны были поддерживать этот идиотизм. Например, в плюсах есть throw, хотя во всех других языках raise. Это сделано потому, что raise уже был в библиотеках UNIX. Классы очень мягко вошли в ЯП.

[править] С точки зрения современных ЯП

В C++ обобщается понятие записи. В Delphi то, что record – добрая старая запись, класс – class. Это более простой путь. В Java записи полностью отсутствуют, и слава Богу. В C# понятие структуры осталось, но это недокласс. Почему появилось там понятие структуры? Во введении в C# начинают ругать Java. Там референциальная модель объектов, но есть простые классы, например Point, который не предназначен для того, чтобы мы его откуда-то наследовали. Это чисто прикладной класс.

Если речь идёт о Java, представим, что мы хотим описать массив

(Java)
class Point {
    public int x;
    public int y;
}
...
Point [] p = new Point[1000];

Так как там два инта, то размер массива 8 байт. Общий расход 8000 байт и 4000 байт на сслыки. Функции невиртуальные. Ну, и надо пройтись по всем элементам и инициализировать их. Структура в C# отличатеся от класса тем, что не имеет референциальной семантики.

(C#)
class Y {...}
struct B{...}
class X {
    Y y; - указатель
    B b; - экземпляр
}

В терминологии языка C# структура относится к типам-значениям (value types). И размещаются непосредственно в памяти (в динамической памяти, в стеке, в объекте). Все поля структуры публичны, наследуются только от Object, от них нельзя наследовать. Ещё одна существенная причина, почему структуры не являеются объектами классов в С# – необходимость совместимости. Требования к проектированию Java примерно такие же, как к Ada: Java – язык для программирования серверных и клиентских приложений в интернете.

Один Аналитик сказал: Java – безусловно техническое достижение, сомнительное маркетинговое, провальное с финансовой точки зрения.

Сам язык спроектирован с целью монопольного программирования в интернете, посему совместимость не важна. А C# – один из языков, не исключительный. Система .NET не является замкнутой. Более того, когда начинается программиорвание в .NET, её возможностей не хватает, например, если хочеться показывать baloontips, то надо вызывать WinAPI.

Нет наследования – нет виртуальных функций. Поэтому не нужны ссылки на таблицу виртуальных методов, поэтому структуры полностью совпадают по расположению со структурами в C, но если используются указатели, то совместимость нарушается. Ограничения на структуры в C# - ... . Ещё одно ограничение – нельзя перекрывать конструктор по умолчанию. Все переменные по умолчанию инициализируются неопределёнными значениями. Соответственно, все элементы структуры должны быть не определены, поэтому конструктор умолчания перегружать нельзя, его делает система.

Существует специальная процедура – boxing-unboxing (упаковка-распаковка). Каждая структура неявно наследуется от Object, а Object – класс, тогда если пишем Object o, то можно присваивать объекты любого типа, но есть типы-значения, и , соответственно, процесс упаковки – такие типы пакуются в специальные классы. Поэтому для кадждого типа-значенич есть специальный класс, который похож на структуру. Упаковка – процесс преобразования типа-значения в соответствующий класс. Есть int – класс Int32, uint- UInt32. Структура преобразуется в специальный объект класса, то когда o = x, где x – структура, то генерируется временный объект в дин памяти, таким образом можно передавать значения в процедуры-функции. Таким образом, в современных языках всё можно представить классом.

В традиционных ЯП понятие записи оставлено в том виде, в котором оно существовало в стандартном Pascal. И что можно сказать про старые языки (кроме Oberon), то там есть записи с вариантами – следующая лекция.