лекции (1998) (Буров), страница 10

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

Вирт ввел в Pascal параметр-процедуры и параметры-функции, которых уже не было в Turbo Pascal, так как в последнем уже существовал процедурный тип, аналогичный модуловскому синтаксису. Создатели Ada83 поступили примерно также. Но они не стали вводить новый класс параметров. Как они это сделали - мы будем рассматривать позже, так как это достаточно сложно. Следует заметить, что в Ada95 процедурный тип появился, так как при объектно-ориентированном программировании замены этого типа на другие механизмы оказались неэффективными.

Почему же в Ada83 отказались от процедурного типа? Для надежности. Очевидно, что передача управления по неинициализированному (например) указателю - крайне опасная ситуация.

Вот все, что сейчас можно сказать об этом типе данных.

Строго говоря, к простым типам данных можно отнести еще много чего, но они уже не носят универсального характера. Например, в Ada есть «задачный тип данных», значениями которого являются «задачи» - tasks. Это средство параллельного программирования. Мы не будем разбирать его в этом курсе.

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

Интересно, что наибольшую номенклатуру таких типов содержит Pascal. Там фигуриют следующие типы данных:

• массивы

• записи

• записи с вариантами

• файлы

• множества

• строки

Понятно, что это очень похоже на алгебраические вещи. Массив - это декартово произведение. Запись - тоже декартово произведение, но различных доменов. Заметим, что для массивов характерны - фиксированная длина и однотипность элементов. Записи с вариантами - попытка устранить проблему, когда тип мог трактоваться двояко. Например, если записью попытаться описать человека, то, вполне вероятно, в ней будет некая общая части и различные части для мужчин и женщин. Это типичный пример янус-проблемы. Множества - чисто математическое понятие. Файл - то же, что и массив, но нет фиксированной длины. Строка - особенный тип массива, который должен, очевидно, иметь расширенный набор операций, обусловленных предназначением данных.

В большинстве современных ЯП типов меньше. Что мы встречаем? Прежде всего, массивы, потом записи и записи с вариантами. Они присутствуют в C, C++, Ada. Почему в этих языках нет множеств?

Дело в том, что паскалевское множество соответствует битовой шкале и ничему больше. Реализация множества во всех реализациях Паскаля одинакова. К тому же во-первых, тип, включаемый в множество должен быть дискретным (чтобы можно было различать), а во-вторых - не очень мощным (мы не можем написать set of integer). С точки зрения реализации понятно, что наиболее эффективны битовые шкалы на определенном диапазоне - будь то 16, 64, 256 - элементов. Более массивных реализаций не было. Ни о какой математической концепции говорить нельзя.

На самом деле множество соответсвует хэш-таблице. Имеет ли смысл на уровне языка вводить такой тип, как хэш-таблица? Разумеется, нет. Таким образом понятие множества быстро редуцировалось.

Интересна с этой точки зрения эволюция других языков Вирта. В Модула-2 понятие множества присутствовало, но только Вирт ввел стандартный тип данных BITSET - это битовая шкала, которая «влезает» в естественное для данной реализации машинное слово. В Oberon Вирт понял, что концепция универсальной битовой шкалы неэффективна, и люди используют множества для доступа к отдельным битам слова (это очень удобно при написании драйверов). Поэтому в Oberon появляется встроенный тип данных SET, который также как и в Модула-2 ориентирован на естественное слово машины.

Примерно аналогично было вытеснено понятие файла. В Pascal оно в некотором смысле «смешное» - было похоже на магнитную ленту, даже не прямого доступа. В современных ЯП понятие файла сводится к коллекции. А с точки зрения ввода-вывода, например, в C все средства ввода вывода были убраны из языка и реализуются через стандартную библиотеку, такой же принцип был принят и в Модула-2 и в Ada. Таким образом, понятие файла также исчезло.

Поговорим о массивах. Это очень простой тип данных. Какие проблемы возникают при работе с ним? Например, в Pascal размерность массива фиксирована и, более того, она зашита в понятие типа. С точки зрения обсуждения массивов, как типов данных, главная проблема - что делать с длинами? С одной стороны понятно, что длина очень хорошо характеризует массив (массивы разных длин должны, вобщем-то, относиться к разным типам), но с другой стороны, мы не можем писать гибкие процедурные абстракции, так как если длина - часть типа, то мы не можем написать процедуру, которая была бы применима к разным типам данных. Частично, из этого положения можно выйти с помощью перекрытия операций (overloading) - мы для каждой длины пишем свою процедуру, но это мало применимо, т.к. типов может быть очень много.

Как была решена эта проблема в других языках? В Модула-2 Вирт оставил принципы работы с массивами такие же, как и в Паскале, но ко всему прочему было введено понятие открытого массива:

PROCEDURE P(VAR A: ARRAY OF CHAR);

в стандартном Паскале такая конструкция невозможна, плюс мы обязаны поставить имя типа, а не его описание. В Модула-2 все то же самое, но допускаются открытые массивы. Их индексация ведется с 0 до N-1, где N вычисляется с помощью атрибутной функции HIGH:

HIGH(A)=N-1;

В данном случае мы сталкиваемся с атрибутами. Атрибутом также является, например, количество бит в машинном слове. Но большинство атрибутов, с которыми мы имели дело, являются статическими, например, все атрибуты массивов в Pascal являются статическими. Здесь же мы впервые сталкиваемся с динамическим атрибутом, который вычисляется в момент выполнения. Совершенно очевидно, что компилятор Модула-2 должен генерировать такой код, который вместе с массивом передает еще и его верхнюю границу, как неявный параметр.

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

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

type TARR is array (POSITIVE range 1..20) of integer;

procedure P(X: TARR);

и неограниченный:

type T1ARR is array (NATURAL range <>) of integer;

Фиксируется тип элементов и тип диапазона (заметим, что во многих ЯП позволительно в качестве индекса массива использовать не только целочисленные типы, но и другие - дискретные типы) и не фиксируется левая и правая границы. То есть неограниченной получается только размерность. Что можно делать с таким типом данных? В отличие от ограниченных массивов, мы не имеем права описывать объекты типа T1ARR (неограниченного массива), соответственно, делать присваивания. Объявление

A: T1ARR; - неверно!

Но Ada позволяет делать уточнения:

имя: тип [уточнение];

В частности, уточнять можно тип «неограниченный массив». Мы можем написать:

A: T1ARR range 0..10;

B: T1ARR range 1..11;

C: T1ARR range 0..20;

Заметим, что A,B,C с одной стороны принадлежат T1ARR, а с другой - некоторому подтипу. То есть мы получили три объекта типа T1ARR, но трех разных подтипов. С точки зрения концепции типов Ada, эти массивы должны быть совместимы по присваиванию. Но стоит ли разрешать присваивания

A:=B;

B:=A;

эти два присваивания надежны, т.к. длины массивов одинаковы. А вот

A:=C;

C:=B;

будут запрещены, так как они некорректны. И запрещены будут уже при компиляции!

И после таких уточнений мы уже можем написать процедуру P(X: T1ARR), в теле которой:

...

A:=X;

...

Такую конструкцию компилятор уже не может проверить статически, т.к. связывание конкретных объектов произойдет динамически. Мы можем передать в процедуру, как массив B, так и C. Поэтому компилятор Ada вставляет здесь динамическую проверку.

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

Лекция 9

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

Основная проблема, связанная с массивами, это проблема динамики атрибутов. Атрибуты простых типов данных были статичны. В языке Паскаль все атрибуты простых массивов абсолютно статичны, и это приводит к проблемам. Отсюда возникает понятие открытого массива. Квазистатическим атрибутом открытого массива является его размерность. В Модуле-2 есть операция HIGH(A), которая выдает верхнюю границу индекса. Здесь есть два подхода.

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

Другой подход воплощает язык Ада-83. Там было уделено очень большое внимание программированию с массивами, и вместо того, чтобы отдать это на откуп средствам развития, в базис были введены очень мощные средства. Прежде всего – это концепция неограниченного массива. Статическими атрибутами любого массива являются: базовый тип индекса и базовый тип элементов. Размерность можно не фиксировать – это динамический атрибут. Соответственно, есть т.н. атрибутные функции.

type T is array (POSITIVE range < >) of Tel;

A : T;

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

A'FIRST – индекс первого элемента

A'LAST – индекс последнего элемента

A'RANGE – значение диапазонного типа. Т.е. можно писать if (i in A'RANGE)…

Естественно, неограниченные массивы чаще всего используются как формальные параметры процедур и функций. И в результате можно передавать любые объекты типа данных Tel. При этом, конечно же, память под эти объекты не отводится (она может быть выделена, только если компилятор знает размеры массива). И поэтому, можно при выведении новых типов или подтипов уточнять размерность:

subtype T1 is T(0..10);

X : T(0..20);

A : T1;

B : T(1..11);

T1 является типом данных, совместимым с типом данных T, объекты типа Т1 одновременно принадлежат и типу Т. Каким образом согласуются объекты этих типов? Проверка корректности присваивания А:=Х и Х:=А в общем случае осуществляется динамически (квазистатически). Присваивания А:=В и В:=А с точки зрения компилятора, корректны и в этом случае никаких квазистатических проверок не осуществляется, потому что количество элементов совпадает, хотя и не совпадают диапазоны. Проблемы, связанные с универсализацией массивов в Аде решены.

Но Ада пошла еще дальше. В некоторых алгоритмах, которые работают с массивами, есть проблема заведения какой-то временной памяти.

procedure P(A : in TARR) is

B : TARR; Пусть по каким-то причинам необходимо хранить локальную begin временную копию массива А.

B:=A;

…

Возникают проблемы. Если тип TARR – неограниченный тип данных, то мы не можем описать переменную В, потому что память под нее должна отводиться в стеке, а мы не знаем ее размеров. Каким образом выбраться из этой ситуации? Как только в языке возникает понятие неограниченного массива, сразу появляется множество проблем, из-за которых так тяжело расширят базис. В данном случае на помощь приходит понятие динамического массива. Не думайте, что динамические массивы – это массивы, которые размещаются в динамической памяти, в Аде это совсем не так. Динамические массивы размещаются в стеке. Название сложилось чисто исторически (в Алголе-60), когда еще и речи не шло ни о какой куче.

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

B : TARR(A'FIRST..A'LAST);

A'FIRST и A'LAST – динамические атрибуты, и в момент компиляции компилятор может ничего об их значении не знать. В данном случае, атрибуты массива также задаются динамически.

В других языках программирования нет "динамических" массивов (в нашей терминологии их логичнее назвать квазистатическими, потому что, например, в языке Java динамические массивы – совсем другое). Видимо без нужды не хотят расширять базис. В С++ описать такой "динамический" массив очень тяжело.

Вначале все языки программирования использовали только статическую память. Затем появился Алгол-60, в котором уже была квазистатическая память и рекурсия. Первые компиляторы с этого языка отдельно компилировали рекурсивные и нерекурсивные программы, потому что нерекурсивные программы можно было создать без программного стека. После того, как машинные архитектуры развились настолько, что стали поддерживать явную концепцию программного стека, то разница в компиляции исчезла. Та же история сейчас происходит и с динамической памятью. В некоторых случаях, "динамические" массивы в языке Ада немного более эффективны, чем настоящие динамические массивы. Однако сейчас вопросы эффективности не настолько важны, что языки программирования пренебрегают такой экзотической возможностью.

Наиболее радикальный подход к массивам в языке Java. Все атрибуты связанные с массивом только динамические, более того, статических атрибутов и быть не может. При объявлении массива T[] a (можно использовать и классическое описание T a[]) память не выделяется, а выделяется она только при инициализации a=new T[10]; . Теперь можно работать с этим массивом. Такие массивы можно свободно присваивать друг другу, при этом старый массив удаляется (с помощью динамической сборки мусора). Т.е. семантика массивов чисто ссылочная. Хотя остается квазистатический контроль над значением индекса массива a[i], причем этот контроль в Java отключить никак нельзя, потому что этот контроль предусмотрен на уровне виртуальной Java машины.

Записи. Записи с вариантами.

Записи впервые появились в языке Паскаль, после основополагающей работы Хоора, в которой он сформулировал основные концепции структур данных. Эти структуры данных в практически не измененном виде и вошли в язык Паскаль. Записи неизменно кочевали из одного Виртовского языка в другой, что подтверждает удачность этой структуры данных. Наконец, настали светлые времена, когда понятие записи медленно трансформировалось в понятие класса. Поговорим о проблемах, связанных с записями.

На самом деле, проблема одна – это проблема, связанная с записями с вариантами. Есть специальное понятие записи с вариантами, которое абсолютно необходимо в традиционных языках программирования, в которых отсутствует понятие наследования, и принята концепция уникальности типа (все объекты данных разбиваются на непересекающиеся классы). Здесь возникает проблема, связанная с неоднотипностью объектов реального мира, которые могут относиться одновременно к нескольким классам. Самый яркий пример в программировании – это понятие события. С одной стороны, событие характеризуется неким общим набором признаков (например, время возникновения, причина, и т.д.). В то же время, такие события, как нажатие кнопки мыши, нажатие клавиши клавиатуры, приход сообщения от таймера, вообще говоря, все специфичны. Приходится на каждый тип события вводить по своему типу данных, но тогда как писать обработчики событий, что у них будет формальным параметром? Получается, что для каждого типа данных нужно писать свой обработчик. В реальной жизни никто так не делает.