Лекция 06 (1160806), страница 3

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

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

Глава 2. Составные типы данных.

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

массивы

записи

множества

файлы

Интересно, что минимальным вариантом с этой точки зрения является такой язык как Фортран, который в 60-ые г.г. был одним из самых популярных ЯП. В Фортране из всех составных типов данных есть массив. Это другой полюс. В принципе понятно, что без составных типов данных нельзя, но ясно, что минимальный набор – это массив. На базе массива можно смоделировать все остальные виды, например запись. С точки зрения современных языков программирования, рассмотрим такую неявную наследницу Паскаля, как язык Ада. В базисе Ады остались только массивы и записи. Для более современных ЯП: C++, Delphi, Java, C# характерна следующая тенденция - остались, разумеется, массивы, как базисная структура программирования, а все остальное перешло в понятие класса. Понятие класса оказалось очень мощным как средство развития, т.е. класс не относится к базисной структуре языка, класс - это средство развития. Так вот оказывается на базе класса можно смоделировать и множество, и файл, и многие другие коллекции, поскольку понятия массив, запись, множество возможных коллекций в ЯП не исчерпывает. Т.е. общая тенденция среди этих языков такая: оставлено понятие массива, введено понятие класса, и на базисе понятия класса все остальные понятия уже моделируются как часть стандартной библиотеки языка, и единственным исключением является понятие строка. Это еще один базисный тип данных, который есть во многих ЯП, прежде всего в современных. Важность строк обусловлена тем, что они несут текстовую информацию, а большинство языков именно текстовую информацию обрабатывают. Интересно при этом, что в некотором смысле даже понятие массива в таком языке, как С++ с точки зрения практического программирования практически не нужно. Можно смоделировать надежный массив на базе класса, причем не просто массив, а произвольный вид массива, что ассоциативный массив, что динамический массив, что массив с фиксированными границами и т.д. – все это можно смоделировать на базе класса. Интересно, что в С++ нет даже понятия строки. Вместо этого в большинстве реализаций языка С и в том числе в стандартной библиотеке шаблонов есть специальный шаблонный класс из стандартной библиотеки, который полностью моделирует соответсвующую функциональность строки, но тем не менее, в такие языки как C#, Java, Delphi понятие строки добавлено как базисный тип. Почему они не использовали подход, скажем Строуструпа, который не стал раздувать базис языка, а вместо этого сделал мощным понятие класса, это мы обсудим позже.

Теперь давайте для каждого из этих типов данных охарактеризуем более подробно то как они реализованы для тех или иных языков.

Самой важной структурой данных безусловно является массив. Какие проблемы связаны с определением массива? Вспомним: каждый объект данных имеет атрибуты. На первых лекциях мы водили базовые атрибуты объектов данных, а конкретно мы вводили их 6. Тогда же было сказано, что, естественно, для частных типов данных у нас набор атрибутов существенно расширяется. В частности, самый главный атрибут для массива – это его размер. Основная проблема массива такая: каким именно атрибутом является длинна и чей это атрибут.

У нас есть атрибут длина, и он может быть:

статическим,

квазистатическим,

динамическим.

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

Ну и есть еще один аспект: у нас есть объекты данных (ОД) и у нас есть тип данных (ТД). Атрибут длина – то ли это атрибут ОД, то ли это атрибут ТД.

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

2. Посмотрим производные языка Паскаль, та же самая Модула 2. Там с одной стороны сохранены свойства языка Паскаль, что атрибут длина является статическим и свойством ТД. Но с другой стороны существуют ОД, а именно формальный параметр, у которого этот атрибут является квазистатическим, а именно: от вызова к вызову длина формального параметра может меняться, но на протяжении вызова она остается постоянной. Это пример квазистатического атрибута, т.е. некоторая форма динамизма, для особого вида ОД, а именно для формальных параметров. В частности в Модуле 2 и в языке Оберон введено понятие параметра-массива - открытого массива.

PROCEDURE P(X:ARRAY OF T);

По правилам Паскаля мы обязаны были здесь указать имя соответствующего типа. Но в случае формального параметра – массива можно написать ARRAY OF T . Соответствующим фактическим параметром может быть любой массив, элементы которого имеют тип данных Т, т.е. массив любой длинны, главное, чтобы у него базисный элемент был типа данных Т. У этого массива есть специальный атрибут длинна, есть специальная псевдофункция HIGH(X), которая дает максимальный размер индекса по его измерению. Очевидно, что теперь мы можем обрабатывать элементы этого массива, используя цикл с фиксированным числом повторений и конструкцию HIGH(X). Это значительно снижает проблему гибкости. Но такой подход всетаки черезмерно статический. Т.е. решается одна частная проблема - то, что можно писать универсальные процедуры обработки массивов, которые не привязываются к длинне соответствующего массива. При этом очевидно, что с соответствующим формальным параметром компилятор должен одновременно передавать его длинну, доступ к которой имеется с помощью функции HIGH.

Но существует другая проблема: если у нас есть 2 массива одинаковой длинны, но у них различные диапазоны (например, один массив у нас описан от 0 до 9, второй от 1 до 10), можно ли считать, что это массивы одного типа или это массивы разных типов? Язык Модула 2 отвечает однозначно – это массивы разных типов. Их присваивать друг другу нельзя, но с другой стороны их можно передавать в качестве формальных параметров. Здесь есть некоторая концептуальная нестыковка. Т.е. если эти объекты разных типов, тогда их вообще никак смешивать нельзя, в часности нельзя вызывать процедуру р с параметром одного типа а потом процедуру р с параметром другого типа. Это противоречие. Это некоторая концептуальная проблема, в языке Оберон, кстати, эта проблема снята очень просто, а именно - в языке Оберон, как и во многих других языках, и это вообще характерно для всех современных ЯП, отказались от того, что у нас произвольный диапазон индексов. Если в таких языках как Паскаль, Модула 2, Ада можно было брать массив у которого произвольный дискретный диапазон индексов. В качестве индексного типа может выступать любой дискретный тип, например перечислимый. В современных языках такую свободу сочли абсолютно излишней. В современных ЯП в качестве индексного типа данных выступает целый тип данных integer, а в качестве нижней границы всегда выступает 0. В результате единственной характеристикой массива является число элементов в этом массиве N и, соответственно, максимальный индекс - это N-1. И, судя по тому, что эта точка зрения принята во всех современных ЯП, которые мы обсуждаем, это не является существенным недостатком с точки зрения программирования. А достоинство – очень высокая эффективность обращения. Но в тоже время в языках, которые допускают большую гибкость, а именно: допускают произвольный дискретный тип в качестве индексного, произвольную левую и правую границы, проблема о совместимости массивов одной длинны, но с разными диапазонами остается.

3) Наиболее радикально эта проблема решена в языке Ада. В языке Ада, вообще говоря, наиболее развитое понятие массива. Массивы языка Ада безусловно самые мощные массивы из тех, которые мы рассматриваем. С одной стороны атрибут длина статический атрибут, а с другой стороны в языке Ада он является свойством ОД. Он связан с ОД, и для ОД он статический, а для ТД он может быть как статическим, так и квазистатическим. В Аде с одной стороны введено понятие неограниченного типа данных, а с другой стороны понятие типов и подтипов, которые мы уже обсуждали, когда обсуждали простые типы данных. Что в Аде можно параметризовать в массиве? Прежде всего длину.

В Аде разрешено общее объявление массива, которое похоже на объявление массива в Паскале(ограничимся пока одномерными массивами):

type ARR is array(IndexType range L..R) of T;

Сразу видна особенность языка Ада. Есть только 2 языка, в которых особая форма индексирования – через ( ), это FORTRAN и Ада. Во всех остальных языках индексирование через [ ]. Обратим внимание, что это очень похоже на конструкцию языка Паскаль, только в Аде диапазоны более общего вида. Здесь мы указываем какой-то дискретный тип данных и сразу же должны указать его диапазон. Если у нас индексный тип данных INTEGER, то он может быть опущен вместе с ключевым словом range. Поэтому, в принципе, можно написать:

type ARR is array(L..R) of T;

где L, R должны быть константными выражениями соответствующего типа. Т.е. это решение в стиле языка Паскаль, и можно программировать в стиле языка Паскаль, когда у вас атрибут длина является атрибутом типа, и любой ОД наследует этот атрибут, но теряется гибкость. Поэтому введено понятие неограниченного массива.

type TArr is array(Index range <>) of T;

Спрашивается, что с таким типом данных можно делать? Во-первых, объявление

X:TArr;

не подходит, компилятор на этом месте выдаст ошибку, потому что компилятор не может отвести память под переменную такого типа. Потому такое объявление переменной является ошибочным. Спрашивается: а зачем нужен соответствующий ТД? Очень просто, объекты этого ТД не могут быть переменными, но могут быть формальными параметрами процедур. В результате это похоже на концепцию открытого массива, вот только она расширена за счет того, что в ТД входит базовый индексный тип и, если для открытого массива в таких языках как Оберон и Модула 2 считается, что индексы его элементов от 0 до HIGH(X), то здесь можно устраивать произвольный диапазон индексов. А именно: у нас у любого ОД типа массив есть специальные атрибуты. К атрибуту длинна в языке Ада можно обращаться явно

X'Length

В качестве Х может выступать объект типа массив и может выступать ТД типа массив. Если у нас есть процедура, у которой формальный параметр описан как неограниченный массив

procedure P(X:TArr)

то мы знаем длину Х, кроме этого есть атрибуты X'FIRST –нижняя граница, X'LAST – верхняя граница и X'Range, который выдает соответствующий диапазон. Мы например можем писать так:

…

begin

for i in X'Range loop

здесь мы можем ссылаться на X(i).

X 'Range = range X'FIRST . . X'LAST

Разумеется мы явным образом с помощью X'FIRST можем ссылаться на нижнюю границу. И в результате мы вполне можем работать с элементами этого массива. Соответствующим фактическим параметром может быть любой массив типа TArr. Мы можем объявлять объекты этого типа в случае, если мы их уточним. Объявление вида

X: TArr(0..10);

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

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