Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

9.1. СТРУКТУРИРОВАНИЕ ДАННЫХ

495

Требование частично удовлетворяется в ООП, но даже в принципе не

может быть выполнено полностью.

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

доступными на уровне использования, чтобы исключить возможность

вложить в использующую программу информацию о том, как устроен

конструируемый тип — экранирование реализации.

В принципе декларируется в ООП, но в реальности нарушается на ка-

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

семантически связывающих объекты разных типов (классов) опреде-

ленными отношениями, регламентированное нарушение этого требо-

вания даже предписывается. Пример с делегированием (см. § 12.1)

лишь одна из иллюстраций такого рода, когда явно указывается, что

один объект должен содержать в своем представлении ссылку на дру-

гой объект.

5. Должна быть определена функция абстракции [53]

, отображающая

объекты представления (rep) в абстрактные объекты A:

: rep → A

Это отображение должно быть согласовано с использованием опера-

ций, применимых к

, т. е. для любой операции f, действующей в обла-

сти абстрактных объектов,ее реализация f

rep

,действующая на предста-

влении

, должна удовлетворять диаграмме

A −−−→



rep

−−−→

rep

(9.3)

и rep

— области значений функций f и f

rep

, соответственно. По

существу это требование означает возможность независимого от пред-

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

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

Объектно-ориентированный подход с самого начала отказывается от

данного требования.Упоминавшееся выше делегирование (см.§12.1)—

496

ГЛАВА 9. СТРУКТУРЫ ДАННЫХ

пример, показывающий, как нарушается независимость объектного ти-

па от представления (то, что это нарушение регламентировано соответ-

ствующим шаблоном проектирования, ничего не меняет): объект «зна-

ет», что другой объект сможет выполнить требуемое действие, и это

знание используется с помощью включения ссылки на другой объект

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

ний и абстракций разрушается: в противном случае была бы допустима

другая реализация, которая не поддерживала делегирование.

Конечно, можно ограничить использование ООП так, чтобы не выхо-

дить за рамки существования функции абстракции. Но тогда исчезают

и преимущества ООП, обусловленные совместным определением дан-

ных и действий: программист, определяя действия, может обращаться

к представлению типа.

Приведенные требования выражают суть концепции АТД, которая, начиная с

середины семидесятых годов,интенсивно развивается в теоретическом аспек-

те. Несмотря на очевидные преимущества концепции абстрактных типов,

есть ряд трудностей при реальном ее воплощении.

Главная трудность обусловлена теоретическими ограничениями: абсолют-

но формальное описание абстрактного типа, зависящего от ранее постро-

енных конкретных типов, недостижимо. Любой подход к описанию типа,

претендующий на формальную строгость и полноту, должен использовать те

понятия, которые использовались при построении представлений исходных

типов, или понятия, которые описывают эти представления. Иными слова-

ми, если новый тип пополняет сложившуюся систему типов программы, то

невозможно описать его поведение без привязки к какому-либо описанию

представления существуующих типов.

Этот исключительно сложный теоретический вывод базируется на тех же

идеях,что теорема Геделя о неполноте,и так же жестко указывает на границы

применимости подхода. Таким образом, нужно либо отказаться от целей,

на которые концепция абстрактных типов данных претендовала, либо не

базироваться на привычных типах, даже на типе целых чисел.

Внимание!

Средства конструирования абстрактных понятий сверху, путем конкре-

тизации и композиций общих концепций, плохо совместимы со средствами

построения новых понятий снизу, из базовых конкретных операций и кон-

кретных данных.

См. § 3.3.

Это предупреждение выражает еще одно концептуальное противоречие.

9.1. СТРУКТУРИРОВАНИЕ ДАННЫХ

497

В идеале абстрактные высокоуровневые концепции надо было бы реали-

зовывать в языках, вообще не содержащих конкретных типов данных и кон-

кретных понятий, а уже затем получившиеся шаблоны применять к конкрет-

ным конструкциям. Блестящий эксперимент Б. Лисков с языком АТД

CLU

[53] имел своей ахиллесовой пятой именно недостаточное осознание необ-

ходимости жестких и даже жестоких решений при последовательном прове-

дении нового метода, в нем пытались совместить восходящий и нисходящий

подходы.

Приведенное выше предупреждение связано со следующим практическим

наблюдением. Есть два пути построения структуры данных программы:

1. наращивание сложившейся структуры путем добавления новых значе-

ний и переменных, относящихся к конструируемым типам; и

2. определение абстрактных структур, моделирующих реальные объек-

ты, и построение для этих структур подходящих представлений, обес-

печивающих осуществимость такого моделирования.

Первый подход называется восходящим, а второй — нисходящим проекти-

рованием. На практике обычно применяется ‘смешанная’ стратегия, когда

сначала проектирование ведется нисходящими методами, затем осуществи-

мость моделирования проверяется на основе восходящих построений, и да-

лее проводится ‘синтез’ двух подходов (т. е. начинаются нерегламентирован-

ные итерации переходов от одних методов к другим). Именно на этапе ‘син-

теза’ начинаются неприятности в разработке большинства программных си-

стем. Поэтому чем жестче средства программирования будут разделять вос-

ходящее и нисходящее движение, тем лучше. Их средства, по крайней мере,

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

Можно заметить, что АТД в идеале полностью принадлежит нисходяще-

му проектированию, а ООП пытается совместить нисходящее и восходящее.

Перечислим другие трудности, связанные с проблемой перехода от тео-

ретической осуществимости к практической реализации:

• не получается разработать удобный для практики язык спецификаций

типов данных,

• конструкторы абстрактных типов довольно громоздки,

• не удается описать поведение объектов типа в зависимости от динами-

ки вычислительного процесса.

498

ГЛАВА 9. СТРУКТУРЫ ДАННЫХ

В методологическом плане требования концепции абстрактных типов дан-

ных положительно повлияли на систему типов данных в языках программи-

рования и в программах.К примеру, современные системы типов языков про-

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

ствам конкретных вычислителей, а на основе математически (или системно

и логически) обоснованной системы понятий, которая уже затем трансфор-

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

трансформация проходит безболезненно, но все-таки она дает возможность

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

элементы всей системы человеческой деятельности.

Абстрактную точку зрения на понятие типа данных следует рассматри-

вать как средство декомпозиции задач. Но это средство высокого уровня. Да-

же описать поведение объекта полностью независимо от представления не-

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

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

творяющая спецификации, гарантировала бы корректность использования.

Кроме того, если говорить о спецификации, которая описывает не только

математические свойства, но и требования к эффективности, то нынешняя

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

связь ресурсных требований с абстрактным представлением остается декла-

ративной, описанной так же нестрого, как семантика в традиционных описа-

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

должно удовлетворять ресурсным требованиям, вступает в противоречие с

высокоуровневыми операциями, никак не связанными при нынешнем их по-

нимании ни с памятью, отводимой под объекты, ни с временем исполнения.

Эта сторона спецификаций остается тем, что очень трудно проверить.

В связи со всем этим стоит заметить, что и объектный подход совсем не

преуспел в решении задачи отдельного от реализации описания типа и в со-

гласовании абстрактных и ресурсных требований.

Если исходить из потребностей абстрагирования, то заманчиво поставить

вопрос о существовании универсального типа типов, из которого все нужные

типы строились бы путем вычисления операций этого типа с типовыми зна-

чениями. Однако построения такого рода — прямой путь к логическим пара-

доксам теории множеств или комбинаторной логики (к примеру, к парадоксу

лжеца и парадоксу Рассела, см. [63]).

В последующих разделах обсуждаются средства построения систем ти-

пов данных, предлагаемые различными языками, с учетом общих положе-

ний, изложенных выше.

9.2. БАЗОВЫЕ И ВЫВОДИМЫЕ ТИПЫ

499

§ 9.2. БАЗОВЫЕ И ВЫВОДИМЫЕ ТИПЫ

9.2.1. Перечисления

Простейшие из абстрактно представленных базовых структур данных за-

даются просто перечислением значений.

Определение 9.2.1. Перечисление является конечным линейно упорядочен-

ным множеством изображений значений (литералов).

Для перечислений определены следующие константы и операции.

• Элементы

ﬁrst

last

— константы, представляющие первый и послед-

ний элементы перечисления.

• Отношения < и = — двуместные операции, задающие соотвественно

порядок и равенство на перечислении.

•

succ

pred

— частичные одноместные операции, вычисляющие сле-

дующее и предыдущее значения своего аргумента;

succ

не определено

для

last

, а

pred

— для

ﬁrst

, соответственно.

Конец определения 9.2.1.

Через операции порядка и равенства определяются также >, 6, > и 6=.

Изображения значений перечислений могут быть заданы априори или

определяться программистом. Априорное задание фиксируется определени-

ем языка, либо посредством явно выписанного в определении перечня изо-

бражений, либо с помощью правил построения изображений из символов.

Например, для булевого типа литералы

true

false

явно заданы языком. Для

целого типа есть соответствующие правила составления изображений чисел

из цифр, знаков плюс и минус.

Конкретно-синтаксические правила задания программистом перечисля-

емого типа различны, но все они сводятся к тому или иному способу зада-

ния набора литералов. Обычно литералы, определяемые программистом, —

идентификаторы (

Pascal

С/С++

и др.).Имена литералов дополняют контекст,

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

Можно сказать, что литералы выбираются из множества правомерных в дан-

ном контексте имен.

Рассмотрим некоторые преобразования перечислений как типов данных.

Из одного перечисления можно построить другое путем образования от-

резка:нужно просто указать два значения из данного набора, одно из которых

500

ГЛАВА 9. СТРУКТУРЫ ДАННЫХ

объявляется

ﬁrst

, а другое —

last

для нового перечисления (новые

ﬁrst

last

смысле исходного перечисления), при этом перечисленные выше операции

наследуются. Таким образом, мы построили первый конструктор типа: кон-

структор отрезка. При всей простоте конструктор отрезка строит структу-

ру данных, удовлетворяющую требованиям абстрактных типов данных (см.

§ 9.1.5).

Конструктор отрезка показывает важный класс конструкторов типов, ко-

торые в некотором смысле ограничивают тип, не усложняя его структуры.

Типы, получаемые при помощи ограничений других типов, часто называют-

ся выводимыми из них.

Если есть два перечисления, то можно построить инъективное отобра-

жение меньшего по числу элементов в большее, естественно согласованное

с упорядоченностью типов. Это очень важное для типов перечислений ото-

бражение называется вложением. Образ элемента

типа

при вложении в

тип

можно считать представлением

в типе

Вложение любого перечисления в множество значений целого типа явля-

ется стандартным реализационным представлением данного типа. Но вот ка-

кое из вложений выбрать — не всегда очевидно. Некоторые языки оставляют

это на усмотрение разработчиков систем программирования (

Pascal

). В этом

случае стандарт языка не фиксирует преобразования между различными пе-

речислениями, но и не запрещает их. В других (

С/С++/C#

) допускается явное

задание отображений между перечислениями (в

С/С++/C#

— отображение в

тип беззнаковых целых; по умолчанию для него устанавливается, что

ﬁrst

отображается в нуль).

Имея вложение одного перечисления в другое,можно говорить и об обрат-

ном (частичном) отображении: оно определено, если для значения существу-

ет прообраз вложения, и не определено в противном случае. Требования од-

нородности диктуют запрет явного использовании в программе нескольких

различных вложений и их обращений для одной и той же пары перечислений.

Для отрезков перечислений можно говорить о естественном вложении, кото-

рое сохраняет литеральные изображения. Корректно определенный язык не

допускает иных вложений и их обращений между перечислением и его от-

резком, что не исключает задания разных вложений для них в другие пере-

числения.

Вложения перечислений — основа для приведений объектов данных ти-

пов. В

С/С++/C#

такие приведения явно задавать не требуется, там перечи-

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

тическим контролем типов (например,в

Pascal

Ada

)такие приведения нуж-

9.2. БАЗОВЫЕ И ВЫВОДИМЫЕ ТИПЫ

501

но указывать явно.

Указанных выше операций достаточно для использования перечислений

в программах. Для повышения выразительности полезно согласование этих

операций с циклами

for

(в двух вариантах: по возрастанию и по убыванию)

for all

(порядок перебора не фиксируется). Естественно, что по значениям

типа перечисления можно организовывать выбирающие операторные кон-

струкции. С точностью до оператора

for all

так сделано в

Pascal

9.2.2. Булевский тип

Этот тип есть перечисление специального вида. Множество его значений

состоит из двух элементов, для которых языком фиксированы изображения:

True

False

. Уместно заметить, что это не означает эквивалентности булев-

ского типа какому-либо перечислению из двух элементов, хотя бы потому,

что операции

succ

pred

для булевских значений не употребляются. Логи-

ческий тип в хорошо сконструированных языках не приводится ни к каким

другим (в

C++

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

ния может приведен к целому).

Обычный набор операций булевского типа дополняет стандартные опера-

ции логическими связками. Смысл такого расширения в том, что они легко

(однозначно и эффективно) реализуются непосредственно командами любо-

го конкретного вычислителя и соответствуют задаче разветвления вычисле-

ний, а потому есть прямой резон предоставить их программисту в качестве

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

По этой причине логический тип был подробно разобран в главе 5, по-

священной операторам выбора.

9.2.3. Тип литерных

Этот тип есть перечисление специального вида, наиболее близкое к об-

щему определению: все операции заданы именно так, как предписывается

для любых типов перечислений. Мощность множества значений стандарт-

ного литерного типа 256, что соответствует байтовому кодированию литер.

В качестве вложения в тип целых чисел для литерных значений задается ото-

бражение на отрезок 0..255, что прямо указывает на кодировки литер как на

представление данного типа.

Для литерных значений вводятся правила изображения. Обычно это за-

ключенный в кавычки символ. Но есть значения, не представимые символа-

ми. Для них, а также для кавычек в качестве символа, используются правила

502

ГЛАВА 9. СТРУКТУРЫ ДАННЫХ

задания изображений специального вида. Часто такие правила распростра-

няются на все литерные значения, из-за чего в языке появляется синонимия

и излишняя привязка к реализации, в частности, к конкретным кодировкам

литер.

В связи с распространением в последние годы международной кодиров-

ки

Unicode

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

ных значений приобрел напарника для представления символов

Unicode

.Для

этой кодировки все перечисленные проблемы обостряются, так как почти на-

верняка многие из символов

Unicode

приходится представлять числовыми

кодами.

9.2.4. Тип целых

Целые — это перечисления, для которых языком вводятся специальные

обозначения литералов: значений целых типов. В соответствии с машинной

арифметикой и разрядной сеткой часто определяют несколько вариантов це-

лых, каждый из которых соотносится со своим регистровым представлени-

ем: байтовые, двухбайтовые, беззнаковые и др. Считать ли все варианты це-

лых соответствующими отрезками “самых больших” целых, представимых в

данном языке или системе программирования, дело вкуса. Необходимо отме-

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

приведения операндов к “самым большим”целым с последующим обратным

приведением к требуемому формату, да и человек скорее склонен восприни-

мать различные целые типы как отрезки типа-призрака всех целых чисел,

который непредставим в машине из-за своей бесконечности.

Наличие вариантов целых мотивируется в первую очередь тем, что си-

стемы команд предлагают различные способы работы, выбираемые исходя

из конкретных особенностей значений. Объединение различных целых ти-

пов дает возможность повысить строгость описания языка, одновременно

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

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

выходят за границы представления, определенные для сохраняемых резуль-

татов. Для стандартных представлений целых чисел надежности гарантиро-

вать не удается: к примеру, сложение и вычитание машинных целых не под-

чиняется законам математики (произведение ненулевых чисел, в частности,

может дать 0).

Русские программисты прекрасно знают неприятности, которые доставляют многчислен-

ные, не согласованные друг с другом, кодировки русских букв.

9.2. БАЗОВЫЕ И ВЫВОДИМЫЕ ТИПЫ

503

Для расширения стандартного набора операций целого типа языковыми

образами арифметических машинных команд (например, командами сдвига)

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

вычислителя.

Современные языки иногда предлагают средства управления представле-

нием различных числовых типов, ориентированные на повышение точности

и корректности вычислений. Это нужно, например, для обеспечения перено-

симости программ и для гарантированных вычислений

. Применительно к

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

Вот как это делается в языке

Ada

type MyInt1 is INTEGER range 0..1000;

–

область фиксирована

type MyInt2 is INTEGER range 0..V;

–

область динамически вычисляется!!!

type MyInt3 is INTEGER range 0..INTEGER’LAST;

–

любое неотрицательное целое,

–

допустимое реализацией

Транслятор использует информацию об областях значений следующим

образом. Описание языка предписывает системам программирования обес-

печить математическую корректность вычислений в заданной области, но

при условии,что значения не превышают допустимых величин

INTEGER’FIRST

INTEGER’LAST

. Для малых значений это указание означает, что можно ис-

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

ровать арифметику, если вычислитель не позволяет соответствующие дей-

ствия выполнить стандартными командами.

Интересен случай динамических вычислений области. Он осмыслен для

динамически возникающих переменных и констант, область которых опре-

деляется в момент появления описания их типа (после этого, к примеру, из-

менение переменной

не повлияет на диапазон данных, тип которых опи-

сывается как

MyInt3

В Аде есть еще одно полезное свойство определения типов, применимое

и к типу целых. Можно описать новый тип, который имеет поведение уже

существующего типа, но им не является:

type MyNewInt is new INTEGER;

Гарантированные (доказательные)вычисления — вычислительные эксперименты,стро-

го обосновывающие оценки некоторой величины, например, α > 2 или 0.49999 < disp <

0.50001.

504

ГЛАВА 9. СТРУКТУРЫ ДАННЫХ

Это описание позволяет определять переменные и константы,которые,к при-

меру, нельзя складывать с целыми, но можно между собой. Транслятор дол-

жен контролировать указанное различие. Применение данного средства на-

кладывает, например, запрет на «сложение ‘яблок’ и ‘людей’».

Это отличает новые типы от тех, которые описываются без специфика-

тора

new

и называются в

Ada

подтипами одного и того же типа. Примеры

подтипов:

MyInt1

MyInt2

MyInt3

. Применительно к целым подтипы — это

просто отрезки “самого большого целого типа”, и неявные приведения в оба

направления для них возможны, тогда как для новых типов приведение мо-

жет задаваться только явной квалификацией (указанием имени типа).

Оперирование с новыми типами и с областями предусматривается не толь-

ко для целых типов. Эти средства, безусловно, являются конструкторами ти-

пов. Они до некоторой степени отвечают потребности программистов при-

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

повышения абстрактности программирования на данном языке.

9.2.5. Вещественные типы

Системы команд большинства компьютеров обеспечивают возможности

оперирования с числами с плавающей точкой. Во многих случаях предусма-

тривается и оперирование с числами с фиксированной точкой. Естественно,

эти возможности предоставляются в языках с помощью специальных базо-

вых типов, именуемых как вещественные (real) в двух видах: плавающие

(ﬂoat)и фиксированные (ﬁxed).Первые характеризуются относительной точ-

ностью, задаваемой как число значащих цифр, вторые — абсолютной точно-

стью, задаваемой с помощью минимальной величины, на которую они могут

различаться. Другая характеристика — это область допустимых значений,

т. е. их диапазон: минимальное и максимальное представимые числа.

Уже из этих характеристик следует, что о вещественных типах нельзя го-

ворить как о математических вещественных числах. В то же время, на соот-

ветствующем уровне абстракции полезно не замечать различий, поскольку

представление вещественных чисел в виде

( знак_числа, знак_порядка : (’+’, ’-’);

порядок : INTEGER range 0..размер_порядка;

Беда в том,что заодно запрещается также умножение и (что самое обидное) деление яблок

на людей. Так что воспринимать этот полезный вид выводимых типов как приписывание

размерностей — рекламный трюк, используемый в руководствах по

Ada