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

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

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

485

• Структурирование действий (в особенности с использованием проце-

дур) и структурирование данных (в особенности объектное структу-

рирование) являются средствами повышения уровня абстрагирования

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

тричность: действия почти всегда определяются над данными, а не на-

оборот. Поэтому в современном программировании чаще всего сначала

задаются структуры данных, а уже затем конструируются действия.

9.1.2. Базовые структуры данных и конструкторы структур

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

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

ры из уже существующих. Естественно, что как базовые структуры, так и

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

Определение 9.1.1. Базовые структуры данных — изначально определен-

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

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

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

зываются базовыми типами данных.

Конструктор структуры данных — правило построения новых струк-

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

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

данных.

Конструктор типа данных — это конструктор структуры данных плюс

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

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

Основанием системы структурирования данных (т. е. подхода к данным

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

строится вся система, включая базовые структуры. В качестве базы теорети-

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

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

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

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

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

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

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

вых положений объектно-ориентированного программирования.

486

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

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

данных:

• средства оперирования с данными, в настоящее время предоставляе-

мые машинными языками, а тем более общеупотребительными языка-

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

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

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

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

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

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

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

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

рующие модели вычислителей на основе редукции до уровня битов (т. е. на

базе логического типа).

Иллюстрацией этого направления может служить

язык

APL

, который провозглашал принцип конструирования всего, что нуж-

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

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

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

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

ны более абстрактные структуры данных, а конструкторы данных на бито-

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

уровне требуются свои средства.

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

минимально необходимым. Он должен соответствовать командам модели

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

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

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

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

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

щее:

• обычные вычисления с этими объектами укладываются в системы ко-

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

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

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

DDL

), а о предъявлении формальных описаний вы-

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

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

487

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

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

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

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

ния:

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

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

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

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

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

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

выполняться определенные для каждого типа операции;

Эти принципы хорошо согласуются с устройством базовых средств опериро-

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

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

Следует отметить и различия. Базовые средства программирования “на-

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

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

сто, отвечают требованиям защиты и т. п.). Базовые же структуры данных

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

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

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

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

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

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

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

ционном аспекте). Точно так же для представления объектов, с которыми

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

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

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

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

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

компьютеры. Само понятие конструктора было осознано позднее.

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

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

488

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

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

ных:

3. Предлагая конструктор, разработчики языка обязаны обеспечить осу-

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

4. Конструктор должен быть эффективно реализуем, т. е. составляемые

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

доступа к ним с приемлемой скоростью.

Если для второго из этих принципов критерии проверки достаточно понятны

(хотя они меняются в связи с развитием возможностей компьютеров), то осо-

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

далеко не сразу.

9.1.3. Операции над вновь определяемыми типами данных

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

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

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

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

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

уровне процедур с параметрами, обозначающими эти структуры.

Идея, проведенная в концепции объектно-ориентированного программи-

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

ются операции — методы обработки определяемых объектов. Чтобы рассма-

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

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

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

зации методов.

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

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

ний о данных:

a) как и какие из существующих стандартных средств распространяются на

новые данные;

b) какие способы приведения между старыми и новыми типами предусма-

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

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

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

489

d) как новые операции согласуются с процедурными средствами данного

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

параметризации, представленные в языке);

Эти вопросы решаются вместе с вопросами размещения конструируемых

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

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

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

С/С++

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

Pascal

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

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

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

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

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

емым в том или ином случае. Концепция, когда ‘все приводится ко всему’,

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

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

модифицируемые модули. Но если говорить о надежном коллективном про-

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

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

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

базовых, так и структурных данных. Разнобой, который при этом демонстри-

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

риев выбора того или иного решения.

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

числений, — фиксированным значением, независимым от контекста. Значе-

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

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

фиксируются уже при реализации языка, которая задает их в соответствии с

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

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

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

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

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

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

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

490

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

b) По причине реальной неперечислимости всех возможных значений боль-

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

вил записи изображений значений, возникают общие синтаксические по-

нятия: число, строка и др.

c) Неестественность использования литералов для большинства конструи-

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

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

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

d) Необходим учет назначения данных (пример из

С/С++

— логические зна-

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

обходился без них).

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

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

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

чений,

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

на новые значения чаще всего.

Так сделано, к примеру, в

Pascal

. Распространение присваивания здесь

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

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

ния новых типов данных. В

С/С++

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

ный тип и все оперирование с конструируемыми значениями осуществляется

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

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

передавать информацию о них — весьма ограничена и плохо разработана. Как следствие,

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

ции, которая никакого отношения к логике программы не имеет. В результате, скажем, опе-

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

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

и/или систему программирования).

Главная причина преувеличения значимости присваиваний — выбор модели вычисле-

ний фон Неймана в качестве основы большинства языков программирования. Характерны-

ми качествами этой модели являются пассивность памяти и единственность активного ком-

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

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

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

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

числительных систем (см. § 1.2 про традиционные языки).

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

491

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

водит лишь к получению нескольких ссылок на общую память (см. рис. 7.6;

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

пример, разработать специальную процедуру).

Что касается других операций, то чаще всего они не распространяются на

конструируемые структуры данных. Упомянем несколько исключений. Из-

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

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

Альфа

, разработанный в Новосибирске. В

неоднократно упомянутом языке

APL

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

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

и переменные новых типов.

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

процедур.Возможно синтаксическое оформление вызовов этих процедур как

операций (

С/С++

Алгол-68

Присваивания указателей — основа согласования новых операций с про-

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

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

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

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

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

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

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

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

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

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

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

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

терный пример — язык

Java

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

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

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

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

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

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

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

По существу модель вычислений языка

Java

основана на том, что память

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

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

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

Java

вычисления

492

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

можно спроецировать таким образом. Но это уже область прагматических

ограничений реализаций языка.

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

два взгляда на понятие переменной:

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

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

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

Pascal

);

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

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

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

того же типа (пример такого подхода — язык

С/С++

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

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

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

разным системам типов данных.

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

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

LUCID

, в которой явно фигу-

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

ность элементарных значений во все моменты ее жизни. При такой трактовке

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

менных в разные моменты времени. Например, фрагмент

for all t C[t] = 5;

(9.1)

задает константу со значением 5, а соотношения

V[ﬁrst] = 0;

for all t > ﬁrst V[t] = V[t-1] + C;

(9.2)

определяют в условиях первого фрагмента, что переменная

изменяется во

времени как арифметическая прогрессия с разностью, равной C = 5.

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

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

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

LUCID

, которая точно соответствует этому

стилю программирования. В естественной нотации фрагмент (9.1) записы-

вается просто как

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

493

C = 5;

а соотношения (9.2) — как

V = 0 fby V + C;

(

fby

— follow by, “следуют через”). Никакого индексирования временем нет.

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

шение: каждая переменная является контейнером, содержащим поток значе-

ний, удовлетворяющий задаваемым соотношением.

Приведенный пример показывает, как принципы систем структурирова-

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

рационными.

9.1.4. Типизация и стили

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

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

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

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

наково.

Например,для функционального типа естественной, хотя и не единствен-

но возможной, концепцией типа данных может служить соглашение о том,

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

ся на базе операции применения функции к ее аргументам. Таким образом

строится система типов, соответствующая математическому понятию типов

функций (см. Приложение А).

Для объектно-ориентированного стиля требуется поддержка порождения

и уничтожения данных (объектов) в динамике выполнения программы. Как

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

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

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

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

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

ния всех следов объекта.

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

делировать реальность, рассматривать и фиксировать требования к новым

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

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

ми данных как с едиными абстрактными объектами. Требуется, чтобы спо-

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

494

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

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

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

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

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

и § 12.1), что в связи с объектной декомпозицией полезно в качестве типа

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

граммного интерфейса, и, таким образом, объект может обладать нескольки-

ми типами, или, что то же, реализовывать несколько интерфейсов. Эта по-

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

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

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

абстрактных типов данных.

9.1.5. Абстрактные типы данных

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

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

щихся структур.

Абстрактные типы данных (АТД)—теоретическая концепция, в которой

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

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

емым для нового типа данных.

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

поставлении с требованиями ООП.

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

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

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

Это требование удовлетворяется в ООП в другой форме:операции опре-

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

значений.

2. Соотношения между операциями должны полностью определять все

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

руемого типа — поведение объектов конструируемого типа.

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

ном ООП.

3. Определение поведения не должно опираться на информацию о пред-

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