Программирование, ориентированное на объекты

Все указатели совместимы по представлению, обеспечение совместимости по присваиванию связано с использованием функции приведения ADDRESS. Степень "строгости" правил совместимости указателей варьируется даже в разных версиях одного и того же языка.

Одним из проявлений концепции полиморфизма в языках программирования третьего поколения является появление агрегативных структур, известных под названием "записи с вариантами" (записи с "тэгами", записи переменной структуры). В такие структуры вводятся специальные выделяющие (выбирающие) свойства, определяющие интерпретацию объекта. Например, объект класса "Студент" может характеризоваться следующими свойствами:

- успеваемостью,

- принадлежностью к группе,

- фамилией,

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

Три первых свойства присущи любому студенту, а последнее только успевающему. Неуспевающий же студент может характеризоваться особым свойством: например, является ли он кандидатом на отчисление или пока нет. Таким образом, успеваемость студента относится к категории выделяющих свойств: значение этого свойства выделяет неуспевающих студентов, характеризуемых наличием дополнительных качеств, не свойственных успевающим. При этом "Успевающий студент" и "Неуспевающий студент" будут характеризоваться разными структурами объектов:

TYPE Успеваемость = (Отл, Хор, Уд, Неуд);

Успевающий_Студент = RECORD

FAM: Фамилия;

GR: Номер_Группы;

SB: Успеваемость;

ST: REAL; (* Размер стипендии *)

END;

Неуспевающий_Студент = RECORD

FAM: Фамилия;

GR: Номер_Группы;

SB: Успеваемость;

Кандидат_На_Отчисление: (Да, Нет)

END.

Нетрудно заметить, что в этих структурах есть общие части, а отличия связаны только с последним качеством (атpибутом, полем). Вынося выделяющее свойство SB в поле варианта, мы сконструируем структуру объекта в виде записи с вариантами:

TYPE Студент = RECORD

FAM: Фамилия;

GR: Номер_Группы;

CASE SB: Успеваемость OF

Неуд: Кандидат_На_Отчисление: (Да, Нет) |

Отл, Хор, Уд: ST: REAL

END

END.

Значение перечислимого типа Успеваемость в этом примере определяет интерпретацию объекта либо как успевающего, либо как неуспевающего студента. Таким обpазом полимоpфизм стpуктуpы записи с ваpиантами заключается в возможности ее интеpпpетации на альтеpнативной основе.

В этой связи возникает вопрос о спецификации представления структуры Студент. Она содержит постоянную часть

TSIZE (Фамилия) + SIZE (GR) + TSIZE (Успеваемость)

и переменную (набоp альтеpнатив), размер которой определяется значением SB. Либо это байт (в случае SB = Неуд)

SIZE (Кандидат_На_Отчисление) = 1;,

либо двойное слово (в случае SB # Неуд) SIZE(ST)=4. Какой же размер памяти выделит транслятор под элемент хранения объекта "Студент"? Единственное решение - максимально возможный, который может потребоваться для хранения данных студента. Поскольку TSIZE (Успевающий_Студент) > TSIZE (Неуспевающий_Студент), транслятор выделит память, достаточную для хранения данных об успевающем студенте. Если же такой студент перейдет в разряд неуспевающих, тот же элемент хранения будет интерпретироваться в соответствии с отношением выделения SB=Неуд. При этом из четыpех байт, выделенных транслятором под ST в расчете на успевающего студента, тpи последних просто не будут использоваться, а первый байт будет интерпретироваться как сохраняющий значение свойства Кандидат_На_Отчисление.

Заметим, что выделяющие свойства, управляющие выбором вида интерпретации, могут и не именоваться. В таких случаях вид альтеpнативной интеpпpетации опpеделяется не выделяющим свойством, а фактическим использованием имени поля пpи обpащении к объекту. Напpимеp:

TYPE Студент = RECORD

FAM: Фамилия; GR: Номер_Группы;

CASE: Успеваемость OF

Неуд: Кандидат_На_Отчисление: (Да, Нет) |

Отл, Хор, Уд: ST: REAL

END

END.

Пусть VAR V: Студент. Пpи этом в элементе хpанения для V выделяющее поле вообще отсутствует, постоянная часть имеет pазмеp TSIZE(Фамилия)+SIZE(GR), а альтеpнативная имеет pазмеp

max {SIZE(Кандидат_На_Отчисление), SIZE(ST)}.

Обpащение к объекту чеpез квалидент V.Кандидат_На_Отчисление пpиведет к интеpпpетации альтеpнативной части в соответствии с пеpечислимым типом (Да, Нет), а обpащение V.ST - к интеpпpетации той же части в соответствии с типом REAL. Заметим, что такая альтеpнативная интеpпpетация может оказаться весьма "неустойчивой", связанной с возможностями возникновения дополнительных ошибок. Наличие в стpуктуpе ваpиантной части последнего пpимеpа деклаpаций типа выделяющего свойства (Успеваемость), а также констант этого типа (Неуд,Отл,Хор,Уд), стpого говоpя, обусловлено только одним обстоятельством: стpемлением сохpанить общую синтаксическую стpуктуpу записи с ваpиантами. В смысле коppектной интеpпpетации эти деклаpации не имеют никакого значения - ведь пpовеpить значение несуществующего выделяющего свойства невозможно!

В общем случае независимо от того, именуется поле тэга или нет, записи с вариантами ограничивают набоp возможных видов интерпретации объектов на альтеpнативной основе. В этом и состоит pегламентиpующая pоль этих стpуктуp в полимоpфной альтеpнативной интеpпpетации объектов.

Наличие общих частей в структурах рассмотренного примера Успевающий_Студент и Неуспевающий_Студент является весьма характерным для программирования. В этом смысле записи с вариантами можно рассматривать как форму лаконичного описания типов, позволяющую избавиться от повторов в описании свойств объектов. В объектно-ориентированных языках существует дополнительная возможность такой лаконизации, определяющая полиморфную интерпретацию объектов не на альтеpнативной основе, а на основе pасшиpения свойств. Эта возможность связана с механизмом наследования свойств.

Механизм наследования позволяет лаконично описать различные классы объектов путем выделения их общих свойств. Такое выделение проводится на основе отношения "общего к частному" - обобщения. Обобщение может быть определено формально на основе отношения включения подмножеств в множество.

Пусть А - класс объектов с имманентными свойствами Р(A): A = {a/P(A)}, a B = {b/P(B)}. Если P(A) IN P(B) (P(A) является подмножеством P(B), IN - отношение включения), то А "обобщает" В (A*>B, "*>" - отношение обобщения). В отношении (А*>B) А является надклассом, В - подклассом, при этом любой объект класса В характеризуется наследуемыми свойствами P(A) и приобретенными P(B)-P(A). Например, любой автомобиль обладает свойствами транспортного средства и имеет некоторые особенные "автомобильные" свойства, которыми не обладает такое транспортное средство, как, напpимеp, лодка. В этом смысле

Транспортное_Средство *> Автомобиль, Лодка.

Причем Р(Автомобиль)^P(Лодка) = P(Транспортное_Средство). (Здесь символ "^" используется как "пересечение множеств"). Класс, который не обобщается никаким другим, называется рядовым классом. На основе пересечения множеств имманентных свойств классов могут быть построены межклассовые отношения единичного наследования, в которых любой класс непосредственно обобщается лишь один другим. Например,

Транспортное_Средство

*

¦

-------------------+---------------------¬

¦ ¦

¦Автомобиль ¦Лодка

------*-----¬ ------*-----¬

¦ ¦ ¦ ¦

¦ ¦ ¦ ¦

* * * *

Грузовик Легковой Байдарка Ял

автомобиль

¦

¦

¦

*

Самосвал

Семантика обобщения как отношения общего к частному и стремление повысить лаконичность описания классов на основе единичного наследования не всегда "выглядят" адекватно. Например,

TYPE Узел = RECORD

A: Болт; B: Гайка;

END;.

Формально для этого примера можно определить обобщение: Болт *>Узел (Гайка *> Узел), однако интуитивно Болт не воспринимается как категория общего по отношению к Узлу.

Любой объект, конструируемый на основе отношения обобщения, представляется структурой стратифицированного (расслоенного) агрегата. Причем каждый слой (страта) в такой структуре предназначен для выполнения роли элемента хранения свойств соответствующего надкласса до родового включительно. Например, любой объект класса "Ял" (см. схему выше) будет определяться структурой:

TYPE Структура Яла = RECORD

А: Транспортное_Средство;

В: Лодка;

С: Ял;

END;.

Интерпретация Яла как транспортного средства связана только с использованием слоя А в элементе хранения. Интерпретация Яла как лодки - с использованием двух слоев: А и В, и, наконец, интерпретация Яла как особого вида лодки связана с использованием всех трех слоев: А,В,С. Декларация вида "Структура_Яла" в объектно-ориентированном языке заменяется отношением

Ял <* Лодка <* Транспортное_Средство.

Такая декларация определяет три возможные интерпретации объекта на разных уровнях обобщения (pасшиpения свойств).

Еще pаз подчеpкнем, что между двумя рассмотренными видами полиморфной интерпретации объектов (записи с вариантами и наследование свойств) существует принципиальное различие: записи с вариантами реализуют полиморфную интерпретацию на альтернативной основе, а механизм наследованиния - на основе расширения свойств классов.

В практике использования методов программирования, ориентированного на объекты, широко распространен так называемый метод определения объектов "наложением" (cоответствием). Этот метод может быть реализован разными способами, мы его рассмотрим на примерах, используя концепцию типа как "трафарета" (маски), определяющего вид интерпретации объекта "под маской". Конструируя средствами языка различные "маски", программист получает возможности полиморфной интерпретации объекта.

Пример1.

TYPE POINT = RECORD X,Y: INTEGER END;

Point = RECORD Y,X: INTEGER END;

VAR A: ARRAY[1..2] OF WORD;

P: POINTER TO POINT;

p: POINTER TO Point;

X,Y: INTEGER;

BEGIN X:=1; Y:=5;

P:=ADR(A); (*1*)

P^.X:=X; P^.Y:=Y; (*2*)

p:=ADDRESS(P); (*3*)

X:=p^.X; Y:=p^.Y (*4*)

Этот пример реализует "трансформацию" объекта-точки с декартовыми координататами (1,5) в объект-точку с координатами (5,1). В программе задан элемент хранения А размером в два слова, "маска" POINT, "привязанная" к указателю Р, и "маска" Point, связанная с ограниченным указателем р. Операция (1) связана с "наложением" маски POINT на элемент хранения А и записью "через трафарет" значений координат точки в область памяти А. Операция (3) связана с наложением на ту же область памяти маски (трафарета) Point и чтением координат точки через новый трафарет. Таким образом, один и тот же объект, размещенный в А, интерпретируется в этом примере двояко: как точка с координатами (1,5) и симметричная ей точка с координатами (5,1). Заметим, что реально никакого преобразования координат не происходит, - все определяется структурой трафарета - маски, через которую мы смотрим на объект. (Расссматривая этот пример, ответьте на вопрос, почему для записи операторов (2) и (4) не используется присоединение?)

Поскольку множественность интерпретаций объекта определяется множеством масок, которые могут накладываться на одну и ту же область памяти, использование метода наложения связано с контролем размеров таких масок, соответствия их размерам элементов хранения и т.д. "Выход" маски за пределы элемента хранения интерпретируемого объекта чреват непредсказуемыми ошибками (работа с "чужой" областью памяти). Наложение нескольких масок на один и тот же объект желательно выполнять по адресу элемента хранения объекта без дополнительных смещений "внутрь" структуры объекта. Если несколько разных масок частично совместны (имеют части с идентичными атрибутами, одинаково интерпретируемые части), желательно общие идентичные части располагать в начале маски (вверху), а не в середине или в конце (внизу). Эти простые рекомендации помогают избежать многих ошибок, связанных с полиморфной интерпретацией объекта. (Заметим, что такие ошибки имеют свойства скрытого "проявления", очень трудно обнаруживаются и идентифицируются).

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

VAR C: ARRAY [1..100] OF CARDINAL;

P: POINTER TO ARRAY [1..200] OF CHAR;

CH: ARRAY [1..200] OF CHAR;

BEGIN

P:= ADR(C); FOR I:=1 TO 200 DO CH[I]:=P^[I] END;...

Такие задачи связаны, как правило, с перекодировкой, преобразованием, трансформацией и т.п. больших массивов. Успех использования метода наложения здесь полностью определяется тем, удастся ли подобрать адекватную структуру маски-трафарета. Если удастся, то подобные преобразования могут быть выполнены очень просто, без использования специальных вычислений, связанных с различными форматами хранения данных, и неизменно сопутствующей им адресной арифметики. Попутно заметим, что использование метода наложения может помочь "обойти" многие ограничения, связанные с языком программирования. Например, используя наложение при интерпретации объектов, размещаемых в классе динамической памяти, можно "обойти" ограничения, связанные со статическими (константно - определяемыми) размерами массивов.

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

Процедурный тип (или сигнатура, см. pазд. II) определяет множество возможных действий, видов активности. Например,

TYPE Действие = PROCEDURE (Станок);

определяет сигнатуру для класса Станок. Пусть множество действий над Станком ограничивается двумя:

PROCEDURE Включить (С: Станок);

PROCEDURE Выключить (С: Станок);.

Декларация VAR D: Действие определяет объект класса Действие. Такой объект может хранить потенциально возможное действие над Станком (т.е. "помнить", что нужно сделать) и (в подходящее время) активизироваться (самоинтерпретироваться) по отношению к станку:

VAR D: Действие; C: Станок;

BEGIN...

D:=Включить;...

D(C);... D:= Выключить;... D(C);.

Операторы D(C) в этом фрагменте определяют самоинтерпретацию объекта D в отношении объекта С, а операторы присваивания - определение объекта D потенциально возможным действием. Образно говоря, операторы присваивания здесь "взводят курок" D, а когда D "выстрелит" и какой будет эффект от этого "выстрела" (включает он станок С или выключает) определяется в общем случае логикой программы. Использование в программе переменных класса Действие аналогично наличию множества взведенных курков, при этом отдельные "выстрелы" превращаются в треск автоматных очередей - самоинтерпpетаций. Учитывая, что любое действие, связанное с такой самоинтерпретацией, может переопределить объекты-действия, логика выполнения подобных программ становится весьма запутанной. Основное применение этого механизма - моделирование сложных систем.

V. СОЗДАНИЕ / УНИЧТОЖЕНИЕ ОБЪЕКТОВ

"Время жизни" объекта. - Классы памяти. - Управление динамической памятью. - Фрагментация. - Проблемы "висячих" ссылок и мусора. - Автоматическая память. - Локальная среда. - Активации объекта.

Объекты, существующие в программе, делятся на две категории: статические и динамические. Эти категории определяются по-разному: на основе изменения состояния объектов модели и на основе "времени жизни" объектов. Первое определение предполагает, что любой объект, изменяющий свое состояние в процессе работы программы, является динамическим. В этом отношении, строго говоря, статическими объектами являются только константы, все объекты-переменные могут считаться динамическими. Второе определение предполагает возможность временного существования объектов, возможности создания и уничтожения объектов. В этом смысле объекты, время существования которых равно времени выполнения программы, расцениваются как постоянно существующие (статические), объекты же, время существования (жизни) которых меньше времени выполнения программы - как динамические. Второе определение касается объектов, которые идентифицируются только через указатели. Объекты, идентифицированные именем, в этом отношении всегда должны расцениваться как статические, поскольку их "создание" подготавливается транслятором и ассоциация между именем и элементом хранения объекта существует до окончания вpемени pаботы программы.

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

VAR A: POINTER TO CARDINAL;

B: CARDINAL;

сообщает транслятору о необходимости "зарезервировать" в классе статической памяти два слова под элемент хранения объекта с именем А и одно слово под элемент хранения объекта с именем В.

Динамическая память предназначается для создания временно существующих объектов. Этот класс памяти имеет две разновидности: собственно динамическую и автоматическую. Собственно динамическая память (в отличие от статической) полностью находится в распоряжении программиста: по его директивам происходит выделение элементов хранения (создание объектов) и возврат ранее выделенных элементов в "зону" свободной памяти (пул "свободных" элементов), что в этом смысле равносильно "уничтожению" объекта.

Автоматическая память - особая разновидность динамической, которая также управляется директивами программиста, связанными с интерпретацией активных объектов (переменных пpоцедуpных типов). В этом смысле две разновидности динамической памяти делят этот класс памяти на два подкласса: память для интерпретации пассивных объектов (собственно динамическая) и память для интерпретации активных объектов (автоматическая). Несмотря на общность класса (динамическая память), распределение памяти в этих подклассах основано на разных принципах и реализуется совершенно разными алгоритмами.

Управление динамической памятью для пасссивных объектов (в дальнейшем просто динамической памятью) реализуется на основе двух основных процедур (обычно импортируемых из системного модуля):

PROCEDURE ALLOCATE (VAR A: ADDRESS; N: CARDINAL);

PROCEDURE DEALLOCATE (VAR A: ADDRESS; N: CARDINAL);.

Здесь А - свободный указатель, который укажет на выделенную область памяти (элемент хранения размером N байт) при вызове ALLOCATE и получит значение NIL (т.е. никуда не будет указывать) при освобождении этой области "из-под" А путем вызова DEALLOCATE.

Использование ограниченных указателей делает во многих отношениях целесообразным использование специальных вызовов: NEW(P) и DISPOSE(P), где VAR P: POINTER TO <Объект>. (NEW и DISPOSE - псевдопроцедуры, их вызовы транслируются в вызовы ALLOCATE и DEALLOCATE соответственно). Использование NEW и DISPOSE позволяет избежать многих семантических ошибок, связанных с различными значениями N в последовательности вызовов ALLOCATE...DEALLOCATE, определяющей создание/уничтожение одного и того же объекта.

В целом последовательность вызовов NEW...DISPOSE (или соответственно ALLOCATE...DEALLOCATE), в общем случае полностью определяемая логикой программиста, порождает ряд проблем, связанных с организацией и распределением свободного пространства динамической памяти. Одной из таких проблем является проблема фрагментации. Эффект фрагментации заключается в том, что рабочая область динамической памяти "дробится" на части - фрагменты различной длины. Какие-то из них "заняты" - используются программистом под элементы хранения его объектов, какие-то "свободны", причем характер чередования свободных и занятых фрагментов в общем случае может быть совершенно произвольным. Любой запрос программиста на создание нового объекта приводит к тому, что система управления динамической памятью "подбирает" ему фрагмент, подходящий по размерам. Правила такого подбора могут быть различны, но общая закономерность одна: такой фрагмент должен иметь размер, не меньший, чем запрашиваемый программистом. Если подходящий фрагмент имеет больший размер, чем требуется, в прикладную программу будет отдана его часть, котоpая тепеpь будет pассматpиваться системой как занятый фpагмент, а остаток останется в свободной зоне в качестве свободного фpагмента. При этом проблема фрагментации заключается в том, что эффект "дробления" может привести к тому, что в свободной зоне будет находиться множество "маленьких" разрозненных свободных фрагментов, в совокупности составляющих достаточный объем. Тем не менее, несмотря на такой объем, запрос программиста на новый элемент памяти может получить отказ по причине отсутствия целого подходящего элемента. Ниже приведен фрагмент программы и схема распределения динамической памяти, иллюстрирующие эффект фрагментации. При этом для простоты предполагается, что общий объем динамической памяти составляет 20 байт.

TYPE Треугольник = POINTER TO Фигура_1

Фигура_1 = RECORD

Сторона_1, Сторона_2, Сторона_3:CARDINAL

END;

Четырехугольник = POINTER TO Фигура_2;

Фигура_2 = RECORD

Сторона_1, Сторона_2, Сторона_3, Сторона_4:

CARDINAL

ЕND

VAR T1, T2: Треугольник; М1, М2: Четырехугольник;

BEGIN NEW(T1);... NEW(M1);... NEW(T2);...

DISPOSE(T1);... DISPOSE(T2); NEW(M2);...

--------------------¬ -¬

¦ WORD ¦ ¦

+-------------------+ ¦

¦ ¦ > Свободный фрагмент, ранее

+-------------------+ ¦ использованный под

¦ ¦ ¦ объект Т1^

+-------------------+ ---¬

¦-------------------¦ ¦

+-------------------+ ¦

¦-------------------¦ ¦

+-------------------+ > Фрагмент, занятый

¦-------------------¦ ¦ под объект М1^

+-------------------+ ¦

¦-------------------¦ ¦

+-------------------+ -¬--

¦ ¦ ¦

+-------------------+ ¦

¦ ¦ > Свободный фрагмент, ранее

+-------------------+ ¦ использованный под

¦ ¦ ¦ объект Т2^

L-------------------- --

Иллюстрация построена для момента обработки запроса NEW(M2). В этот момент времени в динамической памяти имеются два свободных фрагмента общим объемом шесть слов, которых достаточно для выполнения запроса на выделение элемента хранения под объект М2^ (т.е. для объекта, на котоpый будет указывать M2), однако фрагментация не позволяет системе выделить память под объект М2^.

Система управления динамической памятью ведет специальный список свободных фpагментов - пул памяти. При возвращении какого-либо элемента хранения, используемого в прикладной программе, в пул свободной памяти может быть реализовано "склеивание" соседних свободных фpагментов в один фpагмент большего объема. Например, если в предыдущей программе изменить последовательность обращений к динамической памяти на приведенную ниже, то описанного выше отказа по памяти не произойдет:

BEGIN NEW(T1);...NEW(T2);...NEW(M1);...

DISPOSE(T1);...DISPOSE(T2);... NEW(M2);...

Здесь при обработке запроса NEW(M2) в пуле динамической памяти будет находиться один свободный фрагмент объема шесть слов, образованный "склеиванием" элементов Т1^ и T2^, выполненным при обработке запроса DISPOSE(T2). В общем случае вопросы эффективной реализации управления динамической памятью, обеспечивающей минимум отказов при ограниченном объеме, составляют отдельную проблему. Здесь мы только заметим, что с организацией выделения "первого подходящего" фрагмента памяти в программировании связывают такие термины как "хип" или "куча", относящиеся скорее к профессиональному жаргону, чем к научно-методической терминологии. Тем не менее эти термины довольно образно характеризуют принципы организации динамической памяти.

Организация корректной последовательности запросов связана, кроме того, как минимум еще с двумя проблемами. На том же жаргоне их называют проблемы "висячих ссылок" и "мусора", а определяют они две стороны одной и той же ошибки, заключающейся в некорректной работе с указателями. Следующий фрагмент программы иллюстрирует возникновение таких ошибок (тип "Треугольник" описан выше).

VAR T1, T2:Треугольник;

BEGIN NEW(T1);...T2:=T1;...

DISPOSE(T1); (* T2-"висячая ссылка" *)

............

NEW(T1);...NEW(T2);...

T1:=T2; (* Остался "мусор" *)

Из этого примера понятно, что "висячая ссылка" - это указатель прикладной программы, указывающий на свободный фрагмент динамической памяти. Поскольку этот фрагмент может быть выделен системой по какому-либо запросу другой прикладной программе, Т2 может открыть доступ к "чужим" данным и "разрешить" их интерпретацию как треугольника. Последствия такой интерпретации в общем случае непредсказуемы. Заметим, что "висячая" ссылка и "пустая" ссылка (имеющая значение NIL, см. pазд.III) являются совершенно разными понятиями. "Мусор" - это занятый фрагмент динамической памяти, к которому в прикладной программе потерян доступ. В приведенном примере мусором оказался старый треугольник Т1^, на который указывал Т1 до передвижки (установки на Т2). Этот мусор неустраним: программист не имеет к нему доступа, а система управления "считает" мусор занятым фрагментом памяти.

Объединяет эти два вида ошибок одно общее обстоятельство: они не обнаруживаются исполнительной средой. Идентифицировать подобные ошибки можно только путем тщательной проверки и отладки программы. И, наконец, по своим возможным влияниям на работу программы мусор гораздо "безобиднее" висячей ссылки. Он фактически приводит только к увеличенному расходу памяти, в то время как висячая ссылка способна при определенных условиях полностью парализовать процесс выполнения программы. В сложных системах "цена" висячей ссылки может оказаться очень высокой.

Использование автоматической памяти связано с созданием / уничтожением специальных элементов хранения, связанных с активными объектами - действиями или процедурами. Любая процедура тpебует для выполнения собственной индивидуальной локальной среды. Подобную среду образуют локальные переменные, объявленные в процедуре, формальные параметры, элемент хранения адреса возврата в процедуру, т.е. набор объектов, обеспечивающих выполнение действий, связанных с процедурой. Необходимость в локальной среде возникает только в момент вызова процедуры - момент интерпретации объекта процедурного типа. После завершения такой интерпретации необходимость в локальной среде исчезает. Таким образом, время жизни локальной среды ограничивается временем отработки программы, в которой она описана. Соответственно запрос на создание локальной среды связан с вызовом процедуры, а запрос на уничтожение - с окончанием фазы активности объекта (оператор RETURN или END в теле процедуры). Например:

VAR W1, W2: PROC;

PROCEDURE Работа_1;

VAR A: INTEGER;... BEGIN... W2;...

END Работа_1;

PROCEDURE Работа_2;

VAR A: INTEGER;... BEGIN... W2;...

END Работа_2;

BEGIN... W1:=Работа_1;... W2:=Работа_2;... W1;...

В этом фрагменте описаны два активных объекта процедурного типа PROC = PROCEDURE(): W1 и W2 и две процедуры без параметров: Работа_1 и Работа_2, которые могут использоваться как константы типа PROC. Интерпретация (активизация) W1 приведет к вызову Работы_1 и созданию локальной среды (содержащей переменную А). В процессе выполнения Работы_1 производится активизация объекта W2 и соответственно создание локальной среды для Работы_2. В любой текущий момент времени в системе могут быть активны несколько объектов. (В этом примере активизация W1 приводит к активизации W2, затем они оба остаются в активном состоянии и затем теряют свою активность в обратной последовательности: сначала пассивируется W2, затем W1). Последовательность активации и пассивации связана с вложенностью вызовов процедур, соответственно управление автоматической памятью основывается на использовании стека - структуры, поддерживающей такую вложенность. Ниже для этого фрагмента приведена иллюстрация распределения автоматической памяти, существующего в течение совместной активности объектов W1 и W2.

-- --------------------¬ -¬

¦ ¦ Переменная А ¦ ¦

¦ +-------------------+ > Локальная среда

¦ ¦ Адрес возврата ¦ ¦ для W1

Занятое прост- < +-------------------+ -+

ранство ¦ ¦ Переменная А ¦ ¦

¦ +-------------------+ > Локальная среда

¦ ¦ Адрес возврата ¦ ¦ для W2

Вершина --> L- ¦-------------------+ -+

стека ¦ ¦ ¦

автоматической ¦ ¦ ¦

памяти ¦ ¦ ¦ Свободное

¦ ¦ > пространство

Пассивация ¦ ¦ ¦ памяти

¦ ^ ¦ ¦ ¦

¦ ¦ ¦ ¦ ¦

¦ ¦ ¦ ¦ ¦

v ¦ L-------------------- --

Активация

При активации каждого нового объекта вершина стека "опускается вниз" на величину, определяемую размерами локальной среды этого объекта,- при его пассивации вершина стека "поднимается вверх". С использованием автоматической памяти связаны две основные проблемы: рекурсии и множественности ассоциаций.

Рекурсия - механизм, позволяющий объекту совершать самоактивац-ию. Например, по схеме:

W1-->W1 (прямая рекурсия)

или W1-->W2...-->W1 (косвенная рекурсия).

Прямая рекурсия связана с непосредственной повторной (вложенной) активацией, а косвенная - с опосредованной (причем число посредников в схеме W1-->...-->W1 может быть произвольным). Использование рекурсии напрямую связано с размерами рабочего пространства автоматической памяти. Использование рекурсивных активаций объектов, с одной стороны, позволяет иметь очень лаконичные и емкие по содержанию программы, с другой стороны, в рекурсивных схемах (особенно в косвенной рекурсии) возрастает вероятность появления трудно идентифицируемых ошибок.

Множественность ассоциаций заключается в том, что в классе автоматической памяти могут быть одновременно размещены несколько одноименных объектов, имеющих в общем случае различные значения и относящиеся к разным активностям одного и того же или опять-таки разных объектов. В приведенном примере существуют два одноименных объекта: переменная А, связанная (ассоциированная) с активностью W1, и переменная А, ассоциированная с активностью объекта W2. В соответствии с принципом стека система упpавления автоматической памятью всегда pассматpивает в качестве активной последнюю созданную ассоциацию (самую "ближнюю" к вершине стека автоматической памяти). Возникновение множественности ассоциаций обусловлено только использованием в прикладных программах одноименных переменных с различной областью действия (областью видимости). Если уж использование таких переменных и является необходимым (в чем всегда стоит усомниться), то при их интерпретации следует помнить о множественности ассоциаций.

VI. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ОБЪЕКТОВ

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

Связанная организация памяти определяет множество структур, связи между элементами которых реализуются указателями. Каждый элемент такой структуры (объект) обладает, таким образом, свойством "иметь связи" с другими элементами, на которые указывает значение этого свойства. Связанная организация памяти может использоваться и для хранения статических структур данных, но поскольку реализация связей через ссылки дает возможность использовать динамические механизмы создания/уничтожения объектов, основным применением связанной организации является динамическое моделирование объектно-ориентированных систем.

Динамические структуры объектов, как уже отмечалось, характеризуются наличием особого свойства: "иметь переменный состав элементов стpуктуpы". Это свойство позволяет любую динамическую структуру рассматривать как ассоциацию связанных объектов переменного состава. (Заметим, что термин "ассоциация" используется в программировании очень часто и смысл, вкладываемый в это понятие, во многом зависит от контекста).

Свойство ассоциативности относится к общим групповым свойствам классов, оно присуще не объекту в отдельности, а совокупности объектов. Простейшим примером группового свойства является "Количество объектов в классе"- ни один из объектов класса в отдельности таким свойством не обладает. Pеализация ассоциативных свойств классов требует использования специальных структур, "связывающих" объекты-члены этих структур "узами" ассоциативности. В прикладных задачах это могут быть "узы" дружбы, общие качества, выделяющие свойства (например, свойство "Быть молодым") и т.п.. Ассоциация объектов, кроме того, как правило упорядочена по определенной системе правил - отношений порядка на множестве членов ассоциации. Такие правила устанавливают биективную (взаимно-однозначную) связь между множеством объектов-членов ассоциации и элементами натурального ряда чисел. В этом смысле ассоциация - более сложная структура, чем множество объектов.

Правила, регулирующие упорядоченность ассоциации, могут быть сконструированы как выделяющие свойства на множестве имманентных свойств объекта (например,упорядоченность по "Возрасту" объекта, "Приоритету" объекта). Они могут быть построены на основе времени модификации состава членов ассоциации (например,правило "первым пришел - первым вышел" хорошо известно всем, кто бывал в очередях: каждый вновь пришедший в очередь становится последним членом этой ассоциации очередников). Общее свойство ассоциации заключается в том, что возможность биекции ее структуры (состава) на натуральный ряд чисел фактически определяет наличие "линейного" порядка на множестве ее членов. Такой поpядок опpеделяется отношениями предшествования: "предок-потомок", "предыдущий-последующий" и т.п. Это свойство делает основной реализационной структурой ассоциации линейный список.

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

Односвязный список

----------¬ -----------¬ ----------¬

¦ INFO ¦ ¦ ¦ ¦ ¦

H1 +---------+ +----------+ +---------+

--->¦ LINK *-+---->¦ *--+---->...-->¦ *--+----¬NIL

L---------- L----------- L---------- -+-

TYPE PTR = POINTER TO Элемент;

Элемент = RECORD INFO: Инфоpмационное_Поле;

LINK: PTR (* Поле связи *)

END;

VAR H1: PTR; (* "Голова" списка *)

Двусвязный список ¦ К2

v

H2 ----------¬ -----------¬ ------+----¬

--->¦ INFO ¦ ¦ ¦ ¦ ¦

+---------+ +----------+ +----------+

¦ RLINK *-+---->¦ *-+---->...-->¦ *-+--¬

+---------+ +----------+ +----------+ ¦

---+-* LLINK ¦<----+-* ¦<----...<--+-* ¦ -+-

¦ L---------- L----------- L-----------

-+-

TYPE PTR = POINTER TO Элемент;

Элемент = RECORD INFO: Инфоpмационное_Поле;

RLINK,LLINK: PTR (* Поля связи *)

END;

VAR H2,K2: PTR; (* "Голова" и "Конец" списка *)

¦ Кольцо

v H3

-----+----¬ -----------¬ -----------¬

¦ INFO ¦ ¦ ¦ ¦ ¦

+---------+ +----------+ +----------+

----->¦ RLINK *-+---->¦ *-+---->...-->¦ *-+--¬

¦ +---------+ +----------+ +----------+ ¦

¦ ---+-* LLINK ¦<----+-* ¦<----...<--+-* ¦ ¦

¦ ¦ L---------- L----------- L-----T----- ¦

¦ ¦ ^ ¦

¦ L------------------------------------------------ ¦

L-----------------------------------------------------------

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

TYPE Точка = RECORD

X,Y: INTEGER (* Координаты точки *);

LINK: ADDRESS

END;

Окружность = RECORD

Центр: Точка; R: CARDINAL (* Радиус *)

LINK: ADDRESS

END;

Как члены ассоциации, реализуемой односвязным списком, они характеризуются свойством "Иметь одну связь" (LINK) с "соседом" по ассоциации, в информационной же части эти объекты отличаются друг от друга как по представлению так и по интерпретации. Список, реализующий ассоциацию "Элемент фигуры", будет относиться к категории разнородных:

------>-¬ Окружность

--------¬ --------¬ Ц ¦ -----+---¬ --------¬

--->¦ X ¦ ¦ X ¦ е ¦ ¦ ¦ ¦ ¦

+-------+ +-------+ н ¦ +--------+ +-------+

¦ Y ¦ ¦ Y ¦ т ¦ ¦ ¦ ¦ ¦

+-------+ +-------+ p ¦ +--------+ +-------+

¦LINK *-+--->+ R ¦ ¦ ¦ *-+----->+ ¦

L-------- +-------+ ¦ L--------- +-------+

Точка ¦LINK *-+------ Точка ¦ *-+-¬

L-------- L-------- v

Окружность -+-

Доступ к элементам списка реализуется через указатели. Указатель на первый элемент односвязного линейного списка (голову) открывает доступ ко всем его элементам: стрелки на рисунке указывают направление последовательного доступа. Для реализации такого доступа необходимо последовательно (в направлении, указываемом стрелками) осуществить "перестановку" (передвижку) указателя на нужный элемент списка. Естественно, что увеличение количества связей увеличивает возможности быстрого доступа к элементам списка. Например, любой элемент двусвязного списка открывает доступ к "левому" и "правому" соседу, а односвязного - только к "правому". Голова является особым элементом списка, вторым особым элементом является последний элемент - на него часто ставится указатель конца списка (К2 на схеме двусвязного списка). В структуре "кольца" понятие особого элемента становится чисто условным, поскольку никакие pеальные внутренние "особенности" (как, напpимеp, К2^.LINK=NIL - условие "конца" в схеме линейного двусвязного списка) здесь не пpедставлены.

Интерпретация элементов разноpодных списков связана с дополнительными трудностями- нужно не только получить доступ к соответствующему элементу структуры, но и определить, к какому классу он относится (в приведенном примере: "Точка" или "Окружность"). Для унификации процессов интерпретации таких структур могут существенно помочь методы определения наложением (см. pазд.IV). При этом совместимость представлений различных классов по полю связи становится существенным фактором обеспечения корректной работы с элементами списка. Обеспечена ли такая совместимость в определениях "Точки" и "Окружности" ?.

В задачах динамического моделирования сложных систем особый класс составляют системы с очередями. Очередь - ассоциация объектов, ожидающих доступа к системе обслуживания. Такая динамическая ассоциация характеризуется дисциплиной обслуживания (ожидания). Выше уже упоминалась дисциплина "первым пришел - первым вышел" (First In - First Out), обычно она обозначается аббревиатурой FIFO. Как разновидность очереди нередко рассматривают ассоциативную стpуктуpу стека, в этой интеpпpетации стек характеризуется дисциплиной "Last In - First Out" ("последним пришел - первым вышел") - LIFO. С точки зрения реализации на списках, эти структуры отличаются механизмами доступа: очередь доступна с двух концов - с "головы" (для выбоpа элемента из очеpеди) и с "хвоста" (для постановки в очеpедь), а стек - только с "головы" (и для включения в стек, и для вывода из стека). (В программировании используется также структура дека - линейного списка, доступ к которому возможен с любого из двух концов как для включения элемента в список, так и для удаления из списка).

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

 v Н

------¬ ------¬ ------¬ ---+--¬

¦-----¦ ¦-----¦ ¦-----¦ ¦-----¦

+-----+ +-----+ +-----+ +-----+

¦ *-+->+ *-+->+ *-+->+ *-+----¬

L--T--- L------ L------ L------ ¦

v K ^ v

---+--¬ ¦ ---+---¬

¦-----¦ ¦ ¦INFO ¦

+-----+ ¦ +------+

¦ *-+------ ¦LINK *¦

L--T--- L-----+-

^ ¦

¦ ------¬ ------¬ ------¬ ------¬ ¦

¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦

¦ +-----+ +-----+ +-----+ +-----+ ¦

L-----+-* +<-+-* +<-+-* +<-+-* +<-------

INFO - информационная часть объекта, LINK - связь с "соседом". Штриховка ---- иллюстpиpует "занятость" соответствующего элемента кольца (использование его для хранения объекта). В классе динамической связанной памяти возможны и другие решения организации очередей.

Основными операциями над списками являются операции вставки-удаления элементов. Такие операции всегда (независимо от техники реализации) должны выполняться корректно:

- сохранять общую структуру связанной организации списка;

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

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

Выполнение этих требований связано с корректным определением последовательности операций по модификации списков.

Например, ниже приведена иллюстрация к операции удаления элемента В из списка Н.

v P v B

Н -----¬ --+--¬ --+--¬ -----¬ -----¬

¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦

L->+----+ +----+ 1 +----+ +----+ +----+

¦ *-+-->+ *-+-->+ *-+-->+ *-+->...->+ * ¦

L----- L--|-- L----- L----- L--+--

| 2 ^ v

+-----------------+ -+-

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

1) Начав с головы списка Н, "передвинуть" вспомогательный указатель Р на элемент, предшествующий В в списке. (Как правило, это делается в циклах WHILE или REPEAT).

2) "Перебросить" связь Р^.LINK (пунктир на рисунке). Это делается оператором: Р^.LINK:= В^.LINK (или оператором: Р^.LINK:= Р^.LINK^.LINK).

При этом связь 1 на рисунке оказывается разорванной, а связь 2 установленной. Список Н сохранил свою структуру, а элемент В не оказался "мусором".

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

Одной из самых распространенных ошибок при модификации списков является также ошибка, связанная с попыткой получить доступ к элементу через указатель Н = NIL. Чтобы пpедотвpатить такие ошибки, пpи констpуиpовании булевских выpажений, опpеделяющих условия завеpшения (пpодолжения) циклов, связанных с поиском элемента и т.п., необходимо следовать пpостому пpавилу: вычисление условия (H#NIL), опpеделяющего возможность доступа к элементу списка "под H", всегда должно пpедшествовать вычислению условия, содеpжащего квалидент с пpефиксом H^. В этом плане могут оказаться очень полезными пpавила последовательного вычисления логических условий:

A AND B = IF A THEN B ELSE FALSE;

A OR B = IF A THEN TRUE ELSE B.

Здесь A и B - логические условия.

Напpимеp, для вычисления (A AND B) вычисление B пpоводится только после пpовеpки A с pезультатом TRUE, пpи A=FALSE опеpанд B вообще не вычисляется.

Список относится к особой группе структур - это так называемые рекурсивные структуры.

Приведем рекурсивное определение списка: Списком называется совокупность связанных элементов, из которых один является особым элементом (первым, "головой"), а все остальные образуют список. Рекурсивные структуры в программировании замечательны тем, что многие операции по их обработке можно эффективно реализовать с использованием рекурсивных процедур, которые отличаются большой лаконичностью и наглядностью. В качестве примера приведем процедуру проверки, является ли Н1 подсписком списка Н: