Лекция 07 (1160807), страница 2

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

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

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

record

{ постоянная часть – возможно пустая совокупность описания полей ]

[ возможно пустая вариантная часть ]

end;

При этом вариантная часть выглядит так

case имя_дискриминанта : тип of

значение 1: (структура 1);

значение 2: (структура 2);

…

Где каждая структура является описанием записи без скобок и слов record, end.

Есть специальное поле, которое мы называем дискриминант. Структура записи выглядит следующим образом

постоянная часть

дискриминант

структура 1 структура 2 структура 3 …

Структуры 1, 2 и 3 могут сильно отличаться.

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

procedure HandleEvent (VAR E: Event);

которой по ссылке передается параметр - событие, будет выглядеть как большой оператор выбора

case E.EvType of

KBEvent: begin … end;

MouseEvent: begin … end;

…

end;

Языковые абстракции оператор выбора и объединение очень тесно связаны между собой. И программа в большинстве случаев имеет такой вид. Это позволяет считать, что Event – это в некотором смысле какой-то обобщенный ТД, который служит объединением частных случаев.

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

VAR x: Event;

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

В языке Паскаль есть специальная процедура new(p), где р – указатель на тип данных Т. У этой процедуры есть еще один синтаксис: new(p, t1, …,tn). В случае, если р указывает на запись с вариантами, то t1, …, tn – значения дискриминантов во вложенных вариантных записях. Но в реальной жизни, как правило, синтаксис сводится к new(p, t), где t – это значение дискриминанта. В этом случае память будет отводиться по тому варианту, на который указывает значение t. Самое неприятное в этой процедуре то, что в Паскале в этот момент не происходит инициализация дискриминанта. Надо писать что-то вроде

p^.discr := t;

Возникает некоторая ненадежность. Если мы напишем

new(p, t1);

p^.discr := t2;

память будет отведена по одному варианту, дискриминант проинициализирован по другому варианту.

Записи с вариантами необходимы. Поэтому объединения есть во всех традиционных ЯП.

Приведенный синтаксис в языке Паскаль не полный потому, что имя дискриминанта может отсутствовать. А зачем нужен дискриминант, если поле отсутствует? А как без этого в языке Паскаль, реализованном на машине БЭСМ-6, получить доступ ко всем видам числа? Описать соответствующую структуру как неразмеченное объединение.

type word =

record

case Boolean of

true:(bits: packed array[1..48] of Boolean);

false:(w: integer);

end;

48 битов – длина ячейки памяти в соответствующей архитектуре. integer занимает 48 битов. Значит, обе эти части занимают одно и то же место, но они задают разную интерпретацию. Таким образом, на уровне языка без всяких побитовых операций мы можем получить доступ к отдельным битам. Т.е. описывая переменную

x: word;

мы можем писать

x.w := 127;

x.bits[1] – доступ по другому варианту. При этом нет никакого явного дискриминанта. Иногда нам нужны неразмеченные объединения. В языке С только неразмеченные объединения без постоянной части. По определению все поля, которые описаны в union, размещаются с одного и того же адреса.

Есть еще одна проблема – проблема трудной модификации программ. Если у нас есть некий комплекс процедур и функций, основанных на механизме событий, и появляется новое периферийное устройство, появляется еще один класс событий. Это события, которые поступают от нового периферийного устройства. Нужно расширить соответствующий ТД, пролистать всю программу, найти везде соответствующие case и расширить их. В случае если мы модифицируем объединение, мы должны модифицировать практически всю программу. Мы должны перекомпилировать всю систему. Если мы забудем что-нибудь исправить, это значит, что данный тип события в данном обработчике обрабатываться не будет. Компилятор не сможет найти такую ошибку.

Ненадежность и трудность модификации – основные проблемы, связанные с объединениями в традиционных ЯП.

Язык Ада создавался прежде всего с расчетом на надежность. Каким образом создатели языка Ада попытались решить эту проблему? Принцип языкового дизайна языка Ада: если есть какая-то критичная технологическая потребность, в базис языка вводится некоторая конструкция, которая отвечает этой критичной технологической потребности. Для решения проблемы объединения типов появляется новая концепция – параметризованные типы записи. Общий синтаксис параметризованной записи

type T(Discr: DT) is record

[постоянная часть]

case Discr of

when зн1|зн2|зн3 => вариант1 вариантная

when зн4 => вариант2 часть

…

end record;

Т.е. мы параметризуем запись дискриминантом. Ситуация аналогична ситуации с неограниченными массивами. Мы не можем написать

А:T;

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

А:T(t);

t должно принадлежать дискриминантному типу DT.

Тоже самое и в случае, если ОД размещается в динамической памяти.

type PT is access T;

X: PT := new T(t);

Просто написать new T в этом случае нельзя – компилятор выдает ошибку. Нельзя описать ОД без указания значения дискриминанта. При этом автоматически происходит инициализация значения дискриминанта. Изменяться значение дискриминанта не может. Т.е. мы не имеем права писать

A.Discr := -1;

Все объединения могут быть только дискриминированными, т.е. размеченными.

Таким образом часть ненадежности снимается. Однако проблемы с трудностями модификации остаются. ООЯП эту проблему снимают. В современных ООЯП, особенно в тех, которые проектировались без соображений совместимости с существующими языками, понятие запись с вариантами отсутствует. Это такие языки как Java, C# и Оберон. В языках С++ и Delphi понятие записи с вариантами осталось исключительно для совместимости со старым кодом. И если понятие struct расширено в языке С++, то понятие union никаким образом не расширяется потому, что в программах на С++ union употреблять не надо. В С++ есть механизм наследования, который обеспечивает механизм объединения типов, но без проблем, связанных с записями с вариантами. Именно поэтому в основном все современные языки объектно-ориентированные.

Множество.

Впервые множества появились в языке Паскаль.

type T = set of D;

где D – это некоторый дискретный тип данных. Основные операции, которые можно проводить над множествами это операция объединения двух множеств +, операция разности двух множеств -, операция пересечения двух множеств *. Кроме это есть конструктор множества [x1, …, xn]. Операция x in S дает логический результат – true, если х содержится в S, и false, если нет. Операция добавления элемента выглядит так

S:= S+[x]

Аналогично исключение элемента может быть описано с помощью операции -.

В языке Модула 2 была полностью перенята эта концепция, за исключением того, что для повышения эффективности компиляции были введены псевдофункции INCL(S, x) - включить элемент х в множество S, и EXCL(S, x) – исключить элемент х из множества S. В стандарте языка Паскаль ничего не сказано про мощность множества D. Но в большинстве реализаций она ограничена. Наиболее простая реализация множества – упакованный массив булевского типа.

packed array [D] of boolean;

Индекс D дискретного типа. Если S – переменная этого типа, то, если S[x]=true x содержится в этом множестве, если S[x]=false – не содержится. В Паскале, Модуле 2 и многих других языках множество реализуется в виде битовой шкалы, которая пакуется в одно или два машинных слова. Отсюда ограничение на размер множества в 32 или 64 элемента. Основное назначение множеств в такой реализации – именованный доступ к отдельным битам числа. В Паскаль и Модула 2 нет побитовых операций потому, что их можно заменить манипуляциями с объектами множества. Установка бита – включение соответствующего значения, сброс бита – исключение. Чаще всего такие манипуляции с именованными битами нужны для программ, которые управляют вводом/выводом. Регистры устройств – некоторые ячейки памяти. В ряде систем регистры устройств являются частью ОП (например, система PDP 11), а в ряде систем это особые отдельные ячейки, которые адресуются с помощью специальных команд ввода/вывода in и out (например, системы, построенные на базе процессоров Intel). Управление внешними устройствами осуществляется с помощью установки или сброса особых битов в регистрах внешних устройств. Получается, что для решения очень частной задачи в базис языка вводится некоторое понятие.

В языке Модула 2 дополнительно был введен специальный ТД

BITSET = SET OF [0..N-1]

Он был встроен в базис языка (т.е. это стандартный идентификатор языка). N – количество битов в слове для данной реализации.

В языке Оберон все дискретные ТД сводятся к ТД integer. Понятие множества исчезает полностью. Вместо него в Обероне появляется ТД, который называется SET. Он соответствует понятию BITSET в языке Модула 2.

В языке Ада понятия множество нет потому, что в Аде можно описывать упакованные массивы. Вместо того, чтобы встраивать в базис языка ТД множество, Ада предлагает нужный вариант множества реализовать в виде упакованного массива. В языке Ада можно перекрывать стандартные знаки операций. Учитывая это, можно описать ТД – упакованный массив логических чисел, перекрыть для него операции +, * и - , и работать с ним, как мы работали с множествами в языке Паскаль.

В современных ООЯП, таких как Java, C#, Delphi, C++, понятие множества отсутствует. Реализация множества на Паскале – битовая шкала. Множество можно реализовать и на других структурах данных. Множество всех целых чисел в виде упакованного массива скорее всего представить не удастся – большим будет диапазон индексов. А с помощью дерева поиска – можно. Тогда операция поиска – реализация операции in. При этом множество превращается в более обобщенное понятие – таблица. В множестве мы храним булевское значение, которое говорит есть элемент в множестве или нет. В таблице есть понятие ключа и связанное с ним понятие данных. Т.е. в таблице хранятся данные, а ищем мы их по ключу. В простейшем случае ключ может совпадать с данными, в этом случае мы приходим к обычному понятию множества. Таблица может реализовываться с помощью дерева поиска, хэш-таблицы. Какая реализация лучше – зависит от ситуации. (В случае если размер данных сопоставим с размером хэш-таблицы, она перестает работать. Есть специальные методы перехэширования.) Поэтому встраивать какой-то вариант в язык – не лучшая идея.

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

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