лекции (2003) (Глазкова) (1160821), страница 13

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

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

В рамках традиционного подхода наиболее безопасной является концепция записи с вариантами в языке Ада.

В языке Ада записи с вариантами называются дискриминированными записями (параметрические записи).

Идея такова.

Откуда берется ненадежность работы с вариантными записями?

Может быть испорчено значение дискриминанта; в языке стандартный Pascal мы можем неправильно инициализировать варианты и т.д.

В языке Ада сделано следующее. Объединения в языке Ада только размеченные (т.е. в любой вариантной записи обязан присутствовать дискриминант).

Первое ограничение языка Ада: дискриминант является параметром.

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

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

В языках, где допускается неинициализированная загрузка ( стандартный Pascal, Modula2, С), память отводится по максимальному варианту.

Третье ограничение: менять инициализированный дискриминант нельзя (он инициализируется всего один раз).

Каким образом это отражено: вариантные записи всегда являются параметризованными.

Например, опишем ТД Figure.

Пусть вид фигуры явно зависит от дискриминанта перечислимого типа.

Что является общим для каждой фигуры: понятие точки привязки (для точки точка привязки - она сама, для окружности точка привязки - центр, для отрезка - координаты одного из его концов).

type Figure (FigType: EFigureType)

is record

x,y : INTEGER; // точка привязки

case FigType of

when Point -> null //ничего в записи добавлять не надо

when Line -> x1,y1:INTEGER;//появл. еще два поля – коорд. 2-го конца отрезка

when Circle -> x, R: INTEGER;

end record

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

Обратное невозможно: любая запись с вариантами обязана быть параметризованным типом (дискриминант обязан быть параметром).

Запись может иметь несколько параметров.

Параметризованная запись Figure считается неограниченным типом данных. (ограничением будет только указание конкретного параметра).

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

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

procedure Draw (F: Figure) is

case F. FigType of

when Point -> рисование точки;

when Line -> рисование линии;

when Circle -> рисование окружности;

………

end case

end Draw

А как же объявляются ОД типа Figure?

Так же как и объекты неограниченного массива.

y: Figure(Circle);

z:Figure; // ошибочное объявление (такое объявление может появиться только как формальный параметр процедуры или функции)

y. FigType = Point;// ошибка

Если есть два объекта типа Figure( y и z), то присваивание y:=z; допустимо только тогда, когда y и z принадлежат одному и тому же подтипу (т.е. у них одно и то же значение дискриминанта).

Если это не так, выдается сообщение об ошибке (либо компилятором, либо во время выполнения).

Если, в общем случае, компилятор не знает значение дискриминанта, он ставит проверку - квазистатический контроль. В результате отлавливается целый класс ошибок.

Но остается проблема неудобства сопровождения при добавлении новой фигуры. Мы должны поменять ТД Figure, добавить новую структуру записи, после этого найти все процедуры, которые работают с ТД Figure, и в каждую из этих процедур внести изменения. И при этом никто нас не проконтролирует, довели ли мы эту работу до конца. Это один из самых больших недостатков не ОО программирования.

Окончательно решает проблемы только ОО стиль программирования (понятие наследования). С точки зрения ОО стиля программирования, должен быть описан базовый класс Figure, в котором есть поля x,y.

Кроме этого должны быть производные классы Point, Line, Circle и т.д.

После этого надо определить виртуальный метод рисования, и проблема будет решена целиком и полностью.

Т.о., в современных ЯП понятие записи трансформировалось в понятие класса.

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

Пункт 4.Другие составные ТД (множество, файл, строка).

Множество.

С математической точки зрения, множество - это некоторый составной объект.

Базовый синтаксис множества был введен в языке Pascal:

TYPE SET T=SET of T;

К множеству применимы следующие операции:

- х in S возвращает значение типа boolean (находится элемент х в множестве S или нет);

• объединение (+);

• пересечение (*);

• разность (-).

Интересна эволюция понятия множества.

Понятие множества появилось впервые в стандартном Pascal.

Какие ограничения накладывались на базовый тип множества в стандартном Pascal?

Дискретность.

Ошибочно объявление SET of Real, но также ошибочно и объявление SET of INTEGER, потому что тип Т должен быть некоторым диапазоном дискретного типа (в нем накладывалось ограничение на мощность элементов этого типа), причем в разных реализациях стандартного Pascal количество элементов в множестве N было 16, 32,64 (это степени числа 2 - размерность машинного слова).

Множество в стандартном Pascal - это фактически альтернативный способ битовых шкал.

Мы обсуждали, как можно битовую шкалу представить в виде пакованного массива булевских значений.

N - предельная мощность соответствующего дискретного ТД.

Множества представляли упакованную шкалу N битов.

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

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

Интересно, как понятие множества трансформировалось в языках - наследниках Pascal.

В языке Modula 2 понятие множества осталось, но появился специальный тип BIТSET. В Modula 2, так же как и в Pascal, мощность базового типа множество ограничена некоторым числом N, которое зависит от реализации.

В первой реализации Modula 2 на 16 битных машинах N=16. Вообще говоря, число N было равно числу битов в машинном слове.

BIТSET = SET OF [0..N-1];

где N - число битов в машинном слове для данной реализации.

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

Рассмотрим теперь язык Oberon - минимальный ЯП.

Т.к. множества нужны, в основном, для работы с битовыми шкалами, и кроме того в языке Oberon диапазонов и перечислимых ТД нет, то единственное множество, которое нужно - это BIТSET. И в языке Oberon из всех множеств осталось только SET=BIТSET

Операции с множествами:

INCL (S,X) - включение элемента Х в множество S,

EXCL(S,X) - исключение элемента Х из множества S.

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

В конце 70-х был создан язык SETL (SET Language).

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

Почему же в современных ЯП понятие множества отсутствует? Во-первых, множество в стиле Pascal - это аналог битовой шкалы; его можно моделировать наличием побитовых операций, которые есть практически во всех современных ЯП. Во-вторых, более общая реализация множества сильно зависит от конкретной задачи.

Например, множество таблиц может быть реализовано либо как Hash-таблица, либо как двоичное дерево (например, красно-черное), либо как сбалансированное АВЛ-дерево и т.д. При этом у каждой из реализаций есть свои достоинства и недостатки. Как только мы выбираем конкретный вариант реализации, он подходит для одних задач и не подходит для других. И, следовательно. язык с заранее определенной схемой реализации будет не совсем эффективен.

Поэтому тенденция современных ЯП такова: слишком сложные ТД делать частью стандартной библиотеки.

Например, в стандартной библиотеке языка С++ ( STL ) есть шаблоны для ТД Map (древовидный аналог множества), есть Hash. Мы сами выбираем наиболее подходящий вариант реализации.

Т.о., множества являются избыточными с точки зрения базиса языка (их вносят в стандартные библиотеки). То же самое относится и к понятию файла.

Файл.

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

Фактически, файл в языке стандартный Pascal - это математическая абстракция последовательного файла, который хранился на ленте.

Современные ЯП идут по пути языка С. Ввод-вывод в языке С был полностью отделен от языка и это был первый такой язык ( до этого ввод-вывод всегда являлся частью языка).

В языке С и во всех современных языках весь ввод-вывод - это часть стандартной библиотеки.

Строка.

ТД строка есть во многих ЯП.

С одной стороны, строка - это просто массив из символов. Но в отличие от массива символов, какие основные операции над строкой?

Основная операция с массивами - это индексирование [ ] -> T&.

В большинстве реализаций строк также есть операция индексирования, но она дает константную ссылку const T& (т.е. с помощью операции индексирования мы не можем изменять содержимое строки). Это сделано из соображений эффективности реализации. Основные операции над строками (в отличие от массива символов):

• операция сложения строк (конкатенация)

• операция поиска подстроки.

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

Строка в современных ЯП - это динамическая структура данных (это некоторый дескриптор строки, который в частности содержит указатель на массив).

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

Рассмотрим язык С++.

Понятие строки в языке С++ нет. (оно реализовано в стандартной библиотеке языка С++).

В STL есть тип данных basic_string<> Стандартная библиотека ЯП - это надстройка над языком.

В языках же Delphi, C#, Java, строки являются частью языка.

Чего же не хватает в этих языках, чтобы строки можно было сделать частью библиотеки?

В чем отличие строк в языке С++ от строк в этих языках?

Почему в этих языках строки обязаны быть частью языка?

Рассмотрим пример: S1+ S2.

Это означает связывание. Операция + полиморфна, т.е. смысл операции + зависит от фактических параметров, т.е. от типов S1 и S2. В языке С++, в отличие от Delphi и Java, можно переопределять почти все стандартные знаки операций. Поэтому можно написать свой ТД и для него определить операцию +, которая не складывает две строки, а их конкатенирует.

Если в языке нет перекрытия стандартных операций, мы не сможем для них переопределить операцию +.

Но, с другой стороны, известно, что конкатенация - основная операция работы со строками, и ее удобно делать именно в виде S1 +"str"+ S2, а это должно быть частью самого языка (если нет возможности переопределить +).

Более того, известно, что в языке Java можно писать 5+S, где S - строка. При этом 5 переводится в строковую форму, а затем происходит конкатенация.

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

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