лекции (1998) (Буров) (1161123), страница 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); // здесь компилятор неявным образом преобразует переменную в объект

// класса, а поскольку классы передаются только по ссылке,

// то и переменная передастся как бы по ссылке

С++, с этой точки зрения, не менее мощный язык, но более опасный. В таких случаях, он предлагает использовать явным образом ссылки. Заменителем операции ToString в С++ служит оператор преобразования к типу данных char* или CString. Но для преобразования в CString, программист должен сам задать оператор преобразования типа в CString, и тогда компилятор сможет автоматически подставлять это преобразование. К сожалению, за все надо платить, и иногда, неявные преобразования выходят боком.

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

Лекция 10

Мы начинаем рассматривать cредства развития в современных ЯП, традиционных (то есть процедурных). Кроме определения новых типов мы будем рассматривать:

• управление доступом и абстрактные типы данных;

• раздельная трансляция;

• статическая параметризация (механизм шаблонов в C++ и разрывных модулей в Ada)

• исключения (тема, которая стоит особняком, но интересная и важная с практической и теоретической точек зрения)

Это наша программа на часть, касающуюся традиционных ЯП.

Определение новых типов данных

Основными атрибутам типа данных являются:

• множество значений

• набор операций

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

Type T= record

Re, Im: real;

End;

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

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