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

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

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

505

мантисса : INTEGER range 0..размер_мантиссы )

совсем не отражает то, о чем думают, когда оперируют с вещественными чи-

слами.

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

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

роде оперирования с вещественными числами. Эта противоречивая двой-

ственность данного типа объясняет и наличие двух вариантов вещественного

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

ния с ними. В частности, согласно с математическому смыслу, вещественные

значения плотно упорядочены отношением “<”:

∀p∀q(p < q ⇒ ∃x(p < x&x < q)),

но конечность множества всех машинных вещественных чисел в принципе

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

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

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

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

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

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

вычислительных машинах.

Говорить об отрезках вещественных значений можно,но в несколько ином

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

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

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

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

Ada

type MyFloat is digits 10 range 0..1000;

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

–

число значащих цифр = 10

type MyFixed is delta 0.01 range 0..1000;

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

–

числа различимы с шагом 0.01

За счет подобных описаний можно добиться передачи программе сведе-

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

тирует от ошибок вычислений и их накапливания. Например, оператор

X_Fixed_1 := 1.1 + 2.1 + 3.1;

(

X_Fixed_1

— переменная, описанная как фиксированная с одной значащей

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

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

506

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

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

с плавающей точкой. Примечательно, что

Ada

разрешает такое, поскольку

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

зации поддержки представления с фиксированной точкой. Решить же про-

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

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

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

узнать, какой вид вычислений подходит для того или иного выражения. Если

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

ных выражений воспользоваться (точной!) целочисленной арифметикой пу-

тем превращения значений в целые числа (нужно просто умножить число

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

на несколько знаков) с последующим обратным превращением. Так реали-

зуется фиксированная арифметика в языке

FORT

. При использовании веще-

ственных с фиксированной точкой следует четко осознавать, что в результате

вычислений могут появляться переполнения.

Арифметика с плавающей точкой более устойчива к проблеме перепол-

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

гда (исключения составляют специализированные процессоры). Но точность

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

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

ной (тройной и т. д.) точности вещественных. Это удобно, когда конкрет-

ный вычислитель действительно обладает соответствующими форматами.

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

рует указание кратности длины (в

Алголе-68

прямо предписывается посту-

пать именно так). В результате у программиста сохраняется только иллюзия

повышенной точности вычислений.

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

щественных значений (для типа с фиксированной точкой это возможно, но

только если его арифметика реализована корректно). Тем не менее, рассма-

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

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

страктное” перечисление-призрак. В этом случае исходный набор операций,

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

succ

pred

как противоречащие аксиоме непрерывности.

Для вещественных типов построение новых типов с наследуемым от ро-

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

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

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

507

type MyNewT is new T;

в языке Ада играет наиболее важную роль, когда

— один из веществен-

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

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

содержательной задаче. Таким образом, имеет место удобное и недорогое

средство дополнительного контроля. Почему это средство редко встретишь

в практических языках? Во многом это объясняется традициями, но не толь-

ко они причина. К примеру, для

С/С++

с его концепцией приведений просто

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

полностью эквивалентными свои базовым типам. В этом плане некоторые

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

объектно-ориентированного программирования.

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

в качестве примера рассмотрим рис. 9.1, на котором в приведена конструк-

Переменная

...

Тип = int

Переменная

...

first = 1

Тип = отрезок int

range

last = 10

Рис. 9.1. Описание выводимого типа

ция <Переменной>, имеющей в качестве значения атрибута <Тип> один из

встроенных типов (a), и <Переменной> выводимого типа (b). Таким образом,

здесь развивается лишь ветвь, соответствующая атрибутам типа.

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

ся ветвь атрибутов компоненты, а при обработке обращения (к переменной,

508

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

процедуре и т. п.) она используется. В этих случаях достаточно заранее по-

строенных шаблонов добавляемых ветвей.

§ 9.3. СТРУКТУРНЫЕ ТИПЫ

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

деле типов не существует. Это означает, что их битовое представление во

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

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

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

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

ется

С/С++

. По существу в них нет неструктурных типов, а то, что какие-

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

большинстве контекстов они могут рассматриваться такими. Но когда нуж-

но, разработчик программы имеет право мгновенно изменить точку зрения

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

структоров, в частности, конструктора объединения (см. § 9.3.3) в худшем

из вариантов. Это следствие принципа однородности памяти. Все меняет-

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

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

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

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

пример,

Эль-76

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

Эльбрус

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

ют доступ к компонентам, из которых они состоят. В этом смысле такие ти-

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

конструктора) селекторами компонент.

Абстрактная точка зрения на структурные типы требует рекурсивного опре-

деления их конструкторов: компоненты — это объекты произвольных типов,

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

тора. Но здесь не появляется “дурная” бесконечность: цепочка вложенности

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

ми (неструктурными) типами (сравнить с бекусо-науровой формой). Иное

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

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

иметь тот же самый тип, что и определяемый. Обычное соглашение для дан-

9.3. СТРУКТУРНЫЕ ТИПЫ

509

ной ситуации — трактовка рекурсивности как указателя на объект определя-

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

зуются явные обозначения указателя.

Несколько слов о соотношении понятий типа и структуры данных. Струк-

тура — это определение того, из чего и как строятся данные некоторого типа.

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

торые задаются одним и тем же конструктором структуры данных. Следуя

принципам абстракции, нужно различать употребление значения как струк-

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

объекта оперирования, когда сведений о структуре значения не требуются.

В первом случае мы говорим о структурах данных, а во втором — о типах.

В точном соответствии с таким разграничением можно говорить о структу-

ре и типе переменной, способной принимать значения. Но по отношению к

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

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

страктному, а не структурному рассмотрению значения.

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

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

как аргументы и/или результаты (здесь понятие операции трактуется рас-

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

определяемые для данного типа). В этом смысле, имея в виду традицион-

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

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

результата.

Данная характеристика внешне очень похожа на математическое опреде-

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

существенное отличие. Для математической функции эти области точно ука-

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

в итоге таких вычислений. Программистские области аргументов и резуль-

тата — это чисто синтаксические понятия, никакого отношения к функци-

ональному отображению не имеющие. Для согласования спецификаций па-

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

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

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

оперирования (например, для выражения соотношений). Однако традицион-

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

ческого контроля типов: вынесение проверки типовой правильности употре-

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

510

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

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

слений типов.

9.3.1. Наборы компонент

Определение 9.3.1. Конструктор общего вида,назначение которого есть опре-

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

набором компонент. Если

T1, ..., Tn

— типы компонент, а

Ki : Ti

— обозна-

чение того, что компонента с именем

имеет тип

, то кортеж (упорядочен-

ных) компонент обозначается как:

(K1 : T1; ...; Kn : Tn)

а набор (неупорядоченых):

(K1 : T1, ..., Kn : Tn)

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

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

нем ничего не сказано ни о том, может ли меняться количество компонент и

как оно задается, ни о том, что такое селектор.

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

• статический набор, когда число компонент фиксируется при опреде-

лении;

• динамический набор, когда число компонент фиксируется как значение

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

структора для определения структуры данных;

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

ся, а объекты с конструируемой структурой данных могут в динамике

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

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

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

зависящих от этих атрибутов:

a) порядковый номер компонент в наборе, если набор упорядочен;

b) статическое имя компонент в наборе, если компонентам приписаны фик-

сированные имена;

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

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

тора набора;

9.3. СТРУКТУРНЫЕ ТИПЫ

511

d) тип компоненты, если по крайней мере некоторые из компонент разли-

чаются своими типами;

e) значения теговых компонент, которые могут давать идентификационные

сведения о других компонентах;

f) специальные атрибуты компонент, смысл и назначение которых для се-

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

Теперь можно дать абстрактное определение селектора.

Определение 9.3.2. Универсальный селектор — пара частичных функций

и S

с одной и той же областью определения. S

отображает некоторое

подмножество значений идентифицирующих атрибутов компонент в значе-

ния компонент набора, S

отображает то же подмножество в переменные,

содержащие значения S

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

При желании можно считать результат S

адресом, что соответствует трак-

товке структурных конструкторов в языке

С/С++

. Чаще всего обе эти функ-

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

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

мы — адрес или значение. Иными словами, можно говорить о вычислении

компоненты S

, об извлечении значения компоненты S

и о приведении ком-

поненты, определенной функцией S

, к значению S

. В тех случаях, когда

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

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

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

пом к данным. Примитивнейший вид программируемого доступа демонстри-

руют компоненты со спецификатором

property

в объектно-ориентированных

языках, где задаются функции S

и S

Программируемый доступ является одним из средств повышения уровня

абстрактности. В самом деле, когда пишутся программы для S

и S

, опре-

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

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

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

Разумное языковое решение программируемго доступа — специальная

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

горитма селектирования, работающие в этом контексте. Удобно параметри-

зировать эту конструкцию в соответствии с абстракцией программируемого

512

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

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

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

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

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

Bliss

Ярмо

Эль 76

К сожалению, в современных объектно-ориентированных языках сред-

ства программируемого доступа даются в самом примитивном виде. Причи-

на тому — банальная неосведомленность разработчиков сегодняшних объ-

ектно-ориентированных языков

Какое оперирование с компонентами можно предусмотреть на уровне уни-

версального конструктора наборов? Прежде всего, приходят на ум средства

циклической обработки: совместный цикл

for all

для всех компонентов набо-

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

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

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

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

Безусловно,полезна функция,вычисляющая размер и характеристики на-

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

зависимая от реализации функция размера

sizeof

, вычисляющая размер па-

мяти, необходимой для размещения набора.

Конструктор набора компонент является полностью абстрактным, и в ре-

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

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

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

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

виде. Некоторые трудности возникают только при представлении рекурсив-

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

полнительных понятий, связанных с семантикой выполнения (в частности,

памяти, адресации и др.).

Поэтому вместо конструктора набора используются конкретные конструк-

торы, которые могут рассматриваться как конкретизации абстрактного кон-

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

ных типов. При конкретизации уточняются функции S

и S

и вводятся необ-

ходимые ограничения. Кроме того, определяется конкретно-синтаксическая

форма конструктора и его селекторов.

Ignorance is power.

(G. Orwell, ‘1984’)

9.3. СТРУКТУРНЫЕ ТИПЫ

513

Абстрактно-синтаксическая форма любого такого конкретного конструк-

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

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

конкретных конструкторов наследуется (с ограничениями) от конструктора

набора компонент. Поэтому имеет смысл описать это поведение один раз в

общем виде. Это построение является типичным примером применения при-

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

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

тизаций абстрактного понятия.

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

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

струкциями, имеющими тип: для переменной, процедуры и др. Как было уже

замечено, у такой конструкции имеется атрибут

<Тип>

, который может быть

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

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

числителя с атрибутом

<Тип>

— извлечение его значения, т. е. типа кон-

струкции. Все остальное, что может потребоваться (к примеру, активизация

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

да вычислителя. Уже для выводимых типов атрибут

<Тип>

более сложен: он

имеет составляющие, которые доступны для действий вычислителя. Однако

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

тура атрибута

<Тип>

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

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

ми, в частности, задание значений составляющих и использование значений

составляющих, можно рассматривать как библиотечные функции, специфи-

цированные языком.

Ситуация с конструкторами,порождающими структурные типы,несколь-

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

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

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

именем типа, описанного ранее (в некоторых языках, возможно, что позже),

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

чаях должна быть обеспечена доступность селекторов компонент.

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

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

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

присоединения дерева набора компонентов у атрибута

<Тип>

(см.рис.9.2, где

это место определяется для <Переменной>), к которому подсоединен один

514

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

Переменная

...

Тип =

Статический набор

Динамический набор

Гибкий набор

Конструктор

Рис. 9.2. Структурная переменная

из вариантов структуры набора (см. рис. 9.3). Схемы для компонент набора

приведены на рис. 9.4.

Значением атрибута

<Тип>

может быть структурный или неструктурный

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

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

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

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

при необходимости для встраивания подпрограмм нужных приведений. В

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

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

<Тип>

исчезает.

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

бы в самой рудиментарной форме) атрибут

<Тип>

не может быть ликвидиро-

ван.Он (быть может, в трансформированной форме) используется в процессе

вычислений. Например, в объектно-ориентированных языках это ссылка на

таблицу виртуальных методов объекта.

Новым по отношению к рассмотренным ранее абстрактно-синтаксиче-

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

во строится как часть атрибутной информации вершины. Эта ситуация ана-

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

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

страктного вычислителя.

Все теоретически возможное разнообразие вариантов набора компонент

в нынешних языках не используется. Конкретные формы конструкторов дан-