Лекции (1129116), страница 11
Текст из файла (страница 11)
Записи. Записи с вариантами.
Записи впервые появились в языке Паскаль, после основополагающей работы Хоора, в которой он сформулировал основные концепции структур данных. Эти структуры данных в практически не измененном виде и вошли в язык Паскаль. Записи неизменно кочевали из одного Виртовского языка в другой, что подтверждает удачность этой структуры данных. Наконец, настали светлые времена, когда понятие записи медленно трансформировалось в понятие класса. Поговорим о проблемах, связанных с записями.
На самом деле, проблема одна – это проблема, связанная с записями с вариантами. Есть специальное понятие записи с вариантами, которое абсолютно необходимо в традиционных языках программирования, в которых отсутствует понятие наследования, и принята концепция уникальности типа (все объекты данных разбиваются на непересекающиеся классы). Здесь возникает проблема, связанная с неоднотипностью объектов реального мира, которые могут относиться одновременно к нескольким классам. Самый яркий пример в программировании – это понятие события. С одной стороны, событие характеризуется неким общим набором признаков (например, время возникновения, причина, и т.д.). В то же время, такие события, как нажатие кнопки мыши, нажатие клавиши клавиатуры, приход сообщения от таймера, вообще говоря, все специфичны. Приходится на каждый тип события вводить по своему типу данных, но тогда как писать обработчики событий, что у них будет формальным параметром? Получается, что для каждого типа данных нужно писать свой обработчик. В реальной жизни никто так не делает.
Запись с вариантами, как раз и есть механизм объединения нескольких типов в один.
record имя_записи
…
case имя_дискриминанта : имя_типа of
имя_1 : имя_типа1;
имя_2 : имя_типа2;
…
end;
end;
Это синтаксис Паскаля, аналогичный синтаксис и в Модуле-2. В языке Си есть аналогичное понятие union teg {T1, … , TN}. Основная проблема записей с вариантами – это проблема ненадежности. Программисты пользуются т.н. дискриминантом записи, чтобы понимать, по какому варианту пойдет программа. В языке Си понятие дискриминанта записи вообще отсутствует. В этом случае программист вводит дискриминант сам:
union Event {
int EvType; // дискриминант
KBEvent kb_event;
TimerEvent t_event;
}
В таких языках программирования, как Паскаль, Ада, Модула-2, дискриминант может присутствовать явным образом. Обработчик в Паскале выглядит следующим образом:
case имя_записи . имя_дискриминанта of
имя1 : begin … end;
…
end;
Записи с вариантами частично решают проблему, позволяя совмещать несколько типов данных, но есть и проблемы. Первая проблема – это негибкость. Трагедия в том, что при добавлении нового события программа просто перестает работать. В этом случае, программист должен изменить структуру данных и во всей программе проверить все обработчики и поправить в них соответствующий case, что очень не удобно. Отследить все изменения очень тяжело. Полностью эту проблему может решить только механизм наследования.
Однако у записей с вариантами есть еще один недостаток по технологии программирования – это ненадежность. Может сложиться такая ситуация, когда мы записали что-то а потом где-то испортили дискриминант, тогда при чтении мы получим чушь. Языки программирования не дают никаких гарантий соответствия дискриминанта и типа записи, только сам программист может следить за этим. Программист может просто забыть о переключателе, и никто за руку его не схватит. Кроме того, во многих языках дискриминант можно опускать, и тогда ни о каком контроле речи вообще не может идти. Одним словом, записи с вариантами – это механизм вскрытия типового контроля, причем, интересно, что он иногда действительно необходим. Этот механизм похож на понятие void* в Си, pointer в Turbo Pascal, ADDRESS в Модула-2. Всегда создатели языка оставляют дыру в системе типов. Преобразуя эти указатели к указателям соответствующих типов, мы сразу обходим типовой контроль.
В языке Ада все сделано несколько хитрее, и это понятие более жестко. Записи с вариантами являются частью т.н. параметризованных данных. Любую запись в языке Ада можно параметризовать, и, в частности, она параметризуется значением дискриминанта.
Type Event (EventType:EvType) is
record
…
case EventType of
when TimerEvent => … ;
when KBEvent => … ;
end case;
end record;
Дискриминант обязательно должен быть описан, и он получает значение только один раз – при инициализации объекта, при этом, память отводится строго под значение дискриминанта.
X : Event(KBEvent);
P : PEvent;
P := new Event(TimerEvent);
Заметьте, что эта концепция похожа на неограниченный массив, потому что он тоже параметризован своей левой и правой границей. Параметризованные записи ведут себя точно также, как массивы – компилятор всегда должен знать, сколько памяти отводить. Типом Event можно пользоваться и без конкретизации в том случае, если это формальный параметр. В обработчике, соответственно, обрабатывается дискриминант, и выполнение программы далее идет по одному из вариантов. Язык нам гарантирует, что значение дискриминанта не может быть испорчено, но он не может гарантировать, что мы всегда будем работать с записью правильно. Мы можем забыть про case и трактовать значение поля как-то иначе.
Ненадежность уменьшена, но проблема расширяемости остается.
С точки зрения свойств развития – записи это самый мощный класс. Когда мы вводим новые типы данных, то мы пользуемся, прежде всего , записями. При определении новых типов данных мы можем сталкиваться с некоторыми проблемами. Одна из них – гибкость описания. В Аде, например, понятие параметрических записей позволяет решить некоторые проблемы. Путь решения проблем в этом языке – это введение новых средств в базис. Какого рода проблемы могут возникнуть при описании новых типов данных с помощью записи? Допустим, мы описываем стек:
type Stack is
record
body : array (1..50) of integer;
top : 1..51;
end record;
Что сразу бросается в глаза? Во-первых – неуниверсальность этого типа данных. Если нам понадобится стек из float, то мы должны описывать другую структуру, и переписывать все функции работы с ним. Можно ли тип данных параметризовать другим типом, и если можно, то какие возможности контроля у нас есть? Если параметризовать тип данных, то мы должны передавать всю информацию о типе данных, все атрибуты, в общем случае, динамически. Следовательно, проконтролировать статически (и даже квазистатически) соответствующую абстракцию невозможно. Создатели традиционных языков программирования либо полностью исключают параметризацию (Паскаль, Си, Модула-2), либо вводят понятие статической параметризации, а именно, в Аде – это родовые сегменты, в языке C++ - это шаблоны. По-настоящему, динамически параметризовать без потери эффективности и надежности нельзя.
Но есть еще и другой момент. Хватит ли нам стека из 50 элементов или нет? В некоторых случаях этого больше чем достаточно, а в некоторых случаях требуется несколько килобайт. Поэтому нужно создавать, либо динамические стеки (с помощью понятия связного списка), либо каким-то образом управлять параметризацией. В С++ понятие класса, и связанное с ним понятие конструктора и деструктора, а также понятие шаблона, полностью решают эту проблему. Создатели языка Ада предпочли некоторые частные решения, которые иногда помогают.
type Stack (size : integer) is
record
body : array (1..size) of integer;
top : 1..size+1;
end record;
S1,S : Stack(50);
P : Stack(10);
S:=S1; // Можно
S:=P; // Нельзя!
P:=S; // Нельзя!
Корректность таких присваиваний, в общем случае, можно проверить только динамически.
Еще одна проблема связана с проблемой инициализации. Этот стек сразу использовать нельзя. Дело в том, что нужно установить top=1. Приходиться писать процедуру Init(S), однако никто нас не проконтролирует, вызвали ли мы перед работой со стеком процедуру Init(). В Аде эта проблема частично решена: можно при описании типа данных сразу осуществлять инициализацию top : 1..size = 1. Такое решение неуниверсально. Если нужно инициализировать сложные структуры данных, то такое тривиальное присваивание не спасет. Кроме того, если стек реализован в виде линейного списка, то еще надо не забыть освободить явным образом память (если нет динамической сборки мусора). Т.е. отсутствует некоторый общий механизм, который нам может гарантировать корректность инициализации и уничтожения соответствующих структур данных. Полностью эта проблема решена в языке С++ (и конечно, в Java) с помощью понятия конструкторов и деструкторов.
Один из источников сложности – семантический разрыв между объектами реального мира и тем базисом, который нам предлагают языки программирования. С точки зрения простых типов данных, базис – это числа. С точки зрения структур данных – это либо последовательность фиксированного размера, либо набор полей. И это все абстракции, с помощью которых нам предлагается моделировать окружающий мир. С этой точки зрения уровень языков программирования очень низок.
Строки.
Строка, строго говоря, это массив символов. В чем специфика строк? Строки – это очень динамическое понятие. Кроме того, в отличие от обычных массивов, для строк хотелось бы иметь некоторые функции, например функции объединения строк, поиска подстроки, поиска вхождения символа в строку, и т.д. Интересно с этой точки зрения посмотреть на наши языки программирования.
В Модуле-2 понятие строки отсутствует - понятие литеральной строки трактуется точно также как в Си, т.е. это массив с нулем в конце. Аналогичный подход в таких языках, как Паскаль, Оберон, Си, и т.д. В языке Ада строк также нет, но есть некоторый стандартный параметризованный (по размеру) вид записи String.
Рассмотрим три более мощных языка: C++, Java, Delphi. Какой подход в этих языках? В С++ понятия строки нет. В Java есть тип данных String, который, на самом деле, является классом. И, наконец, в Delphi есть встроенный тип данных, который называется тоже String. Откуда такой разброс подходов?
В языке С++ нет понятия строки по той же причине, по которой нет понятия диапазона, нет массива с контролируемыми размерами границ, - потому что все эти объекты можно реализовать наиболее оптимально для данной реализации с помощью понятия класса. В любой стандартной библиотеке С++ есть класс строк, например в MFC есть класс CString, который ведет себя полностью динамически и предоставляет множество полезных операций со строками. Т.е. сила С++ не в базисе, а в средствах развития.
С этой точки зрения, казалось бы, Java не менее мощный язык. Класс String вроде бы тоже находится в стандартной библиотеке, однако аналогию с классом CString провести нельзя. Дело в том, что в Java отсутствует перекрытие стандартных операций, т.е. в Java нельзя, например, перекрыть операцию '+', что спокойно делается в С++. Кроме того, для каждого объекта определена операция ToString, т.е. любой тип данных имеет встроенный метод перевода в строковое представление. Почему же в языке Java можно писать S1=S2+"string"? В этом случае компилятор сам догадывается, когда видит тип String и операцию '+', что здесь имеется ввиду операция конкатенации. Здесь мы сталкиваемся с подходом создателей Java, отличным от подхода создателя языка С++. Страуструп спроектировал средства развития и базисные типы данных таким образом, что компилятор специфически обрабатывает только базисные типы данных. При этом, эти базисные типы крайне просты. Все остальное программист доопределяет сам. Если он хочет использовать операцию '+', то он должен сам ее перекрыть для соответствующих классов. Если он ее не перекрыл, то компилятор выдаст ошибку.
В Java мы сталкиваемся с тем, что есть специальный языковый пакет, в который, с одной стороны, является частью некоторой стандартной библиотеки, но с другой стороны, этот пакет одновременно является и частью языка. Класс String в Java интегрирован с базисом языка, сам компилятор языка Java обрабатывает некоторые классы специфическим образом. То же самое относится и к другим классам. Например, для типа long в соответствующем пакете описан и специальный класс-оболочка Long. Такие классы в языке Java нужны по двум причинам. С одной стороны, такой класс инкапсулирует в себе все атрибуты данных типа long, например, значение максимального и минимального числа, и некоторые другие характеристики. С другой стороны, в Java передача параметров осуществляется только по значению, но возникает вопрос: как в отсутствии указателей и ссылок передавать объекты, значения которых хотелось бы в функции изменить?
double d;
int f(double X) {…};
f(d); // передача параметра только по значению
int g(Double X) {…};
g(d); // здесь компилятор неявным образом преобразует переменную в объект
// класса, а поскольку классы передаются только по ссылке,
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
