Программирование ориентированное на объекты
1╛лд√[1]J[1]J[1]Q[1]R[1]R[1]D:\DISSLAST\DISSERT.STYRN-EPSFXS[1]@╨[1]\
K[1]J[1]P[1]╡
VI. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ОБЪЕКТОВ
Связанная организация памяти. -
Ассоциативные структуры. -Списки. - Очереди. - Рекурсивные структуры. - Наборы.
- Деревья.
Связанная организация памяти определяет
множество структур, связи между элементами которых реализуются указателями.
Каждый элемент такой структуры (объект) обладает, таким образом, свойством
"иметь связи" с другими элементами, на которые указывает значение
этого свойства. Связанная организация памяти может использоваться и для
хранения статических структур данных, но поскольку реализация связей через
ссылки дает возможность использовать динамические механизмы
создания/уничтожения объектов, основным применением связанной организации
является динамическое моделирование объектно-ориентированных систем.
Динамические структуры объектов, как уже
отмечалось, характеризуются наличием особого свойства: "иметь
переменный состав элементов стpуктуpы". Это свойство позволяет любую
динамическую структуру рассматривать как ассоциацию связанных объектов переменного
состава. (Заметим, что термин "ассоциация" используется в
программировании очень часто и смысл, вкладываемый в это понятие, во многом
зависит от контекста).
Свойство ассоциативности относится к общим
групповым свойствам классов, оно присуще не объекту в отдельности, а совокупности
объектов. Простейшим примером группового свойства является "Количество
объектов в классе"- ни один из объектов класса в отдельности таким
свойством не обладает. Pеализация ассоциативных свойств классов требует
использования специальных структур, "связывающих" объекты-члены этих
структур "узами" ассоциативности. В прикладных задачах это могут
быть "узы" дружбы, общие качества, выделяющие свойства (например,
свойство "Быть молодым") и т.п.. Ассоциация объектов, кроме того,
как правило упорядочена по определенной системе правил - отношений порядка на
множестве членов ассоциации. Такие правила устанавливают биективную
(взаимно-однозначную) связь между множеством объектов-членов ассоциации и
элементами натурального ряда чисел. В этом смысле ассоциация - более
сложная структура, чем множество объектов.
Правила, регулирующие упорядоченность
ассоциации, могут быть сконструированы как выделяющие свойства на множестве
имманентных свойств объекта (например,упорядоченность по "Возрасту"
объекта, "Приоритету" объекта). Они могут быть построены на основе
времени модификации состава членов ассоциации (например,правило "первым
пришел - первым вышел" хорошо известно всем, кто бывал в очередях: каждый
вновь пришедший в очередь становится последним членом этой ассоциации
очередников). Общее свойство ассоциации заключается в том, что возможность
биекции ее структуры (состава) на натуральный ряд чисел фактически
определяет наличие "линейного" порядка на множестве ее членов.
Такой поpядок опpеделяется отношениями предшествования:
"предок-потомок", "предыдущий-последующий" и т.п. Это
свойство делает основной реализационной структурой ассоциации линейный
список.
С помощью списков могут моделироваться
разнообразные динамические структуры, поддерживающие различные отношения
порядка. В программировании широко используются такие структуры, как стек,
очередь, дек, пул - все они могут быть реализованы на списках. В зависимости
от количества связей между соседними элементами различают односвязные и
двусвязные списки с "встречным" направлением стрелок. Ниже
пpиведены некотоpые пpимеpы оpганизации списковых стpуктуp на связанной
памяти.
Односвязный список
┌─────────┐
┌──────────┐
┌─────────┐
│ INFO │
│ │ │
│
H1
├─────────┤
├──────────┤
├─────────┤
───>│ LINK
*─┼────>│
*──┼────>...──>│
*──┼────┐NIL
└─────────┘
└──────────┘
└─────────┘
─┴─
TYPE PTR = POINTER TO Элемент;
Элемент = RECORD INFO:
Инфоpмационное_Поле;
LINK: PTR (*
Поле связи *)
END;
VAR H1: PTR; (*
"Голова" списка *)
Двусвязный
список │ К2
v
H2
┌─────────┐
┌──────────┐
┌─────┴────┐
───>│
INFO │ │ │ │ │
├─────────┤
├──────────┤
├──────────┤
│ RLINK
*─┼────>│
*─┼────>...──>│
*─┼──┐
├─────────┤
├──────────┤
├──────────┤
│
┌──┼─*
LLINK │<────┼─*
│<────...<──┼─*
│ ─┴─
│
└─────────┘
└──────────┘
└──────────┘
─┴─
TYPE PTR = POINTER TO Элемент;
Элемент = RECORD INFO:
Инфоpмационное_Поле;
RLINK,LLINK:
PTR (* Поля связи *)
END;
VAR H2,K2: PTR; (* "Голова"
и "Конец" списка *)
│ Кольцо
v H3
┌────┴────┐
┌──────────┐
┌──────────┐
│ INFO │
│ │ │ │
├─────────┤
├──────────┤
├──────────┤
┌────>│ RLINK
*─┼────>│
*─┼────>...──>│
*─┼──┐
│
├─────────┤
├──────────┤
├──────────┤
│
│
┌──┼─* LLINK
│<────┼─*
│<────...<──┼─*
│ │
│ │
└─────────┘
└──────────┘
└─────┬────┘
│
│
│ ^
│
│
└───────────────────────────────────────────────┘
│
└──────────────────────────────────────────────────────────┘
В общем случае любой элемент списка может
содержать произвольное количество связей и являться членом многих списков.
Это порождает большое многообразие списковых структур - фактически любая динамическая
структура на связанной памяти конструируется из списков. По составу элементов
списки разделяются на однородные и разнородные, в однородных используются
объекты только одного класса, в разнородных - разных классов. Например, членами
ассоциации "Элемент фигуры" могут быть объекты классов
"Точка" и "Окружность":
TYPE Точка = RECORD
X,Y: INTEGER (*
Координаты точки *);
LINK :
ADDRESS
END;
Окружность = RECORD
Центр: Точка; R:
CARDINAL (* Радиус *)
LINK :
ADDRESS
END; .
Как члены ассоциации, реализуемой
односвязным списком, они характеризуются свойством "Иметь одну
связь" (LINK) с "соседом" по ассоциации, в информационной же
части эти объекты отличаются друг от друга как по представлению так и по
интерпретации. Список, реализующий ассоциацию "Элемент фигуры",
будет относиться к категории разнородных:
┌─────>─┐ Окружность
┌───────┐
┌───────┐ Ц │
┌────┴───┐
┌───────┐
───>│ X
│ │ X │ е │ │ │
│ │
├───────┤
├───────┤ н │
├────────┤
├───────┤
│ Y │ │ Y
│ т │ │ │ │ │
├───────┤
├───────┤ p │
├────────┤
├───────┤
│LINK
*─┼───>┤ R │ │
│
*─┼─────>┤ │
└───────┘
├───────┤ │
└────────┘
├───────┤
Точка │LINK
*─├─────┘ Точка
│ *─┼─┐
└───────┘
└───────┘ 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 Н
┌─────┐
┌─────┐
┌─────┐
┌──┴──┐
│░░░░░│
│░░░░░│
│░░░░░│
│░░░░░│
├─────┤
├─────┤
├─────┤
├─────┤
│
*─┼─>┤ *─┼─>┤
*─┼─>┤
*─┼────┐
└──┬──┘
└─────┘
└─────┘
└─────┘ │
v K
^ v
┌──┴──┐
│
┌──┴───┐
│░░░░░│
│ │INFO │
├─────┤
│
├──────┤
│
*─┼─────┘
│LINK *│
└──┬──┘
└─────┼┘
^ │
│
┌─────┐
┌─────┐
┌─────┐
┌─────┐ │
│ │ │
│ │ │ │ │ │ │
│
├─────┤
├─────┤ ├─────┤
├─────┤ │
└─────┼─*
├<─┼─* ├<─┼─*
├<─┼─*
├<──────┘
└─────┘
└─────┘
└─────┘
└─────┘
INFO - информационная часть объекта, LINK -
связь с "соседом". Штриховка ░░░░
иллюстpиpует "занятость" соответствующего элемента кольца
(использование его для хранения объекта). В классе динамической связанной
памяти возможны и другие решения организации очередей.
Основными операциями над списками являются
операции вставки-удаления элементов. Такие операции всегда (независимо от
техники реализации) должны выполняться корректно:
- сохранять общую структуру связанной
организации списка;
- не приводить к образованию
"мусора" и "висячих ссылок";
- сохранять отношение порядка элементов в
списке.
Выполнение этих требований связано с
корректным определением последовательности операций по модификации списков.
Например, ниже приведена иллюстрация к
операции удаления элемента В из списка Н.
v P v B
Н
┌────┐
┌─┴──┐
┌─┴──┐ ┌────┐
┌────┐
│ │ │
│ │ │ │ │ │ │
│
└─>┼────┤
├────┤ 1
├────┤
├────┤
├────┤
│
*─┼──>┤
*─┼──>┤
*─┼──>┤
*─┼─>...─>┤ * │
└────┘
└──|─┘
└────┘
└────┘
└──┼─┘
| 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
подсписком списка Н:
TYPE Указатель = POINTER TO Элемент;
Элемент = RECORD
INFO : Инфоpмация;
LINK : Указатель;
END
PROCEDURE Проверка (Н,Н1 : Указатель) :
BOOLEAN;
BEGIN
IF H # NIL THEN
RETURN (Н = Н1) OR Проверка
(Н^.LINK, Н1)
ELSE RETURN (Н = Н1)
END
END Проверка.
Проверка (H # NIL) в этом примере нужна
только для того, чтобы предотвратить попытку интерпретировать пустую ссылку
как элемент списка при вызове Проверка (H^.LINK, H1). Ситуация (H=H1=NIL) рассматривается
как положительный результат проверки.
Другим примером рекурсивной структуры
является структура набора, которая определяется следующим образом: Набором
называется совокупность связанных элементов, каждый из которых может быть либо
атомом, либо набором. Атом определяет "неделимый" элемент набора,
предназначенный для хранения элементарной порции информации. Реализация
наборов основана на использовании разнородных списков. Например, ниже приведена
одна из возможных структур наборов. В этой структуре H1 - набор из четырех
элементов (a,b,H2,c), из них H2 - набор, остальные - атомы. H2 состоит в свою
очередь из тpех элементов - атома c и двух наборов H3 и H4, причем набор H3 -
пуст (не содержит элементов), а H4 содержит два атома (d и f).
v H2
┌─────┐
┌─────┐
┌──┴──┐
┌─────┐
H1 │ a │ │ b
│ │ │ │ c │
─>┼─────┤
├─────┤
├─────┤
├─────│
│
*──┼──>┤
*──┼──>┤
*──┼──>┤
*──┼─────────────┐
└─────┘
└─────┘
├─────│ └─────┘
v
│ *
│ ─┴─
v
v v
┌──┴──┐
┌──┴──┐
┌──┴──┐
│ c
│ │ │ │ │
├─────┤
├─────┤
├─────┤
│
*──┼──>┤
*──┼──>┤
*──┼───┐
└─────┘
├─────┤
│─────┤ ─┴─
│
* │ │ * │
└──┼──┘
└──┼──┘
v v
─┴─ ┌──┴──┐
┌─────┐
│ d │ │ f │
├─────┤
├─────┤
│ *──┼──>┤ * │
└─────┘
└──┼──┘
v
─┴─
Элементы H2, H3, H4 определяют
"головы" новых наборов и одновременно являются членами наборов
"верхнего уровня" - при этом структура набора оказывается адекватной
для реализации динамических "вложенных" понятий предметной
области. Например, в ассоциацию H1-"Акционеры" могут входить как
отдельные частные лица, так и коллективы - организации, которые являются ассоциациями
собственных акционеров.
Элементы H2, H3, H4 на приведенной
иллюстрации участвуют в двух связях - горизонтальной (связь между членами
одного набора) и вертикальной (связь с членами "своего собственного"
набора). Эта терминология часто используется для организации так называемых
ортогональных списков, моделирующих структуры динамически изменяющегося
плоского "игрового поля": "разреженных" матриц,
"кроссвордов", цепей "домино" и т.д. Понятие "игрового
поля", разумеется, не означает, что ортогональные списки используются
лишь в игровых задачах.
Еще один пример рекурсивной структуры, широко
использующейся в программировании - структура дерева. Деревом называется совокупность
связанных элементов - вершин дерева, включающая в себя один особый элемент -
корень, при этом все остальные элементы образуют поддеревья. Наиболее широко
используется структура бинарного дерева, все множество вершин которого
делится (по отношению к корню) на два подмножества - два поддерева (левое и
правое). Любая вершина бинарного дерева реализуется на связанной памяти
элементом с двумя связями: с левым поддеревом и с правым.
v К
┌─┴──┐ Информационное поле
├────┤
┌───┼─* │ Связь с левым
потомком
│
├────┤
│ │
*─┼───┐ Связь с правым потомком
v
└────┘ v
┌──┴─┐
┌─┴──┐
├────┤
├────┤
┌─────┼─* │
┌─┼─* │
│
├────┤ v
├────┤
│ │
*─┼───┐ ─┴─│
*─┼────┐
v
└────┘ v
└────┘ v
┌──┴─┐ Л1 Л2
┌─┴──┐
┌─┴──┐ Л3
├────┤
├────┤
├────┤
│NIL │ │NIL
│ │NIL │
├────┤
├────┤
├────┤
│NIL │
│NIL │ │NIL │
└────┘
└────┘
└────┘
На этой иллюстрации изображена структура
бинарного дерева на связанной памяти, здесь К - корень; Л1,Л2,Л3 -
"листья" - вершины с "пустыми" связями ("не
выросшими" поддеревьями).
Заметим, что в этой интерпретации дерево
реализуется на однородных списках (в отличие от набора). Особое положение
корня определяется единственным свойством - отсутствием вершин-предков, любой
лист дерева характеризуется полным отсутствием вершин-потомков. Поскольку любая
вершина в связанной структуре дерева открывает доступ только "вниз"
(только к своим поддеревьям), она может интерпретироваться как корень
соответствующего поддерева. В этом смысле лист является корнем "не
выросшего" дерева и определяет его своеобразную "точку
роста". Включение в дерево новой вершины и удаление старой не должно
нарушать общего отношения порядка на множестве вершин.
Примером такого отношения может служить
отношение "больше- меньше", определяющее структуру бинаpного
дихотомического дерева. В таком деpеве все вершины любого правого поддерева
имеют значение информационного поля большее, чем значение такого же поля у
корня, а веpшины соответствующего левого поддеpева - меньшее. Например,
конструирование дихотомического дерева по последовательности целых чисел
30,70,80,21,25,17,4, начиная с 30, должно приводить к созданию следующей
структуры:
┌──┐
┌──────┤30├───────┐
┌─┴┐ └──┘
┌┴─┐
┌────┤21├─────┐
│70├──────┐
│
└──┘ │
└──┘ │
┌─┴┐ ┌┴─┐
┌┴─┐
┌───┤17│
│25│ │80│
│
└──┘
└──┘ └──┘
┌┴┐
│4│
└─┘
Нетрудно заметить, что процесс
конструирования такого дерева происходит сверху-вниз, начиная с корня, путем
последовательного сравнения числовых значений, pазмещаемых в веpшинах, с целью
определения места размещения соответствующей вершины в структуре дерева. Любая
модификация дихотомического деpева (удаление веpшины, вставка новой веpшины)
не должна наpушать дихотомической стpуктуpы в целом.
В общем случае трансформация произвольной
информационной стpоки (последовательности объектов) в структуру дерева и
обратно основана на использовании глубоких стpуктуpных межобъектных отношений
в исходной стpоке. Такая тpансфоpмация позволяет наглядно пpедставить
подобные отношения в фоpме деpева. В пpогpаммиpовании деpево во-многом
pассматpивается как фоpмальная стpуктуpа, наполняемая pазличным
семантическим содеpжанием. Такой подход позволяет фоpмально реализовать многие
преобразования данных на основе унифицированных процедур обхода деревьев.
Например, в теории трансляции широко
используется понятие польской инверсной записи (ПОЛИЗ) - особой системы
представления математических выражений символьными последовательностями. Так,
например, выражение " a + b * c " будет представлено в ПОЛИЗЕ строкой
" a b c * + ". Если представить исходное выражение в естественной
иерархической форме бинарного дерева :
+----<----+
| |
┌───┐ |
┌─────┤ +
├──────┐ |
│
└───┘ │ |
┌─┴─┐
┌┴──┐---------<--+
│ a │ ┌──────┤
* ├─────┐ |
└───┘ │
└───┘ │ |
|
┌─┴─┐
┌─┴─┐ |
| │ b
│ │ c │->--+
|
└───┘ └───┘
| | | |
то его восходящий обход (пунктир на
рисунке) приведет к строке " a b c * + ", определяющей
"польский" эквивалент исходной строки. Формула восходящего обхода
"Левый - Правый - Корень" (ЛПК) определяет правило обхода бинарного
дерева: восходящий обход связан с обходом его левого поддерева, затем правого
поддерева, затем корня. Поскольку каждая вершина дерева может интерпретироваться
как корень "вырастающего из нее" поддерева, это правило применяется
рекурсивно к каждой вершине обходимого дерева. Правило ЛПК (Левый - Корень -
Правый) определяет так называемый смешанный обход, правило КЛП -
нисходящий обход и т.д. Нетрудно заметить, что смешанный обход дерева
дихотомии по правилу ЛКП приведет к формированию строки чисел (хранящихся в
вершинах этого дерева), упорядоченной по возрастанию, а такой же обход по
правилу ПКЛ - к формированию строки, упорядоченной по убыванию соответствующих
чисел. Таким образом, между структурой дерева, отношением порядка на множестве
информационных компонент его вершин и видом обхода существует глубокая связь,
определяемая рекурсивной природой структуры дерева. Рекурсивные процедуры обхода
бинарных деревьев пишутся прямо по формуле обхода с учетом спецификации
представления вершин дерева. Например, ниже приведена процедура смешанного
обхода бинарного дерева дихотомии, реализующего формулу ЛКП.
TYPE Вершина = POINTER TO Элемент ;
Элемент = RECORD
Info : CARDINAL ;
LLink,RLink : Вершина
END ;
PROCEDURE Смеш_Обход (K : Вершина);
BEGIN
IF K # NIL THEN
Смеш_Обход (K^.LLink); (* Обход
левого поддерева *)
WriteCard (K^.Info); (* Обработка
корня *)
Смеш_Обход (K^.RLink); (* Обход
правого поддерева *)
END
END Смеш_Обход.
В традиционном программировании рекурсия
часто рассматривается как некоторый заменитель итерации. Причем в качестве
примеров рассматривается вычисление рекуррентных последовательностей, которые
могут быть легко сформированы и обычными итераторами (циклами WHILE, REPEAT и
т.п.). Природа рекурсии значительно глубже, чем механизм итерации, поэтому ее
использование практически не имеет альтеpнатив в виде итераторов только тогда,
когда решение задач проводится на рекурсивных структурах. Попробуйте написать
процедуру Смеш-Обход без использования рекурсии, только на основе циклов и,
если Вам это удастся, сравните ее с приведенным выше вариантом рекурсивной
процедуры по наглядности,лаконичности, выразительности.
VII. ПРОЦЕССЫ В ОБЪЕКТАХ
Логический параллелизм. - Схема сопрограмм.
- Понятие процесса. - Рабочая область процесса. - Создание/уничтожение
процессов. - Реентерабельность. - Сигнальная синхpонизация. - Основы
мониторинга, ориентированного на процессы.
В любом программном объекте могут
развиваться динамические процессы, определяющие изменение состояния объекта во
времени. Такие процессы могут развиваться автономно (независимо один от другого)
или во взаимодействии друг с другом. Концепция взаимодействия основывается
на одновременном развитии нескольких процессов, при этом такая
одновременность трактуется в программировании как логический параллелизм -
одновременное выполнение нескольких действий (активностей), обусловленное
логикой развития моделируемой системы. Реализация концепции логического параллелизма
требует в общем случае наличия нескольких процессоров (устройств ЭВМ,
обеспечивающих развитие параллельных процессов), что связано с использованием
нового класса вычислительных систем - систем с мультипроцессорной архитектурой.
Реализация параллельных процессов на обычной однопроцессорной ЭВМ связана с
имитацией логического параллелизма последовательностью активаций разных
процессов с сохранением общих логически обусловленных правил их
взаимодействия. Такая имитация связана с понятием квазипараллельности.
Квазипараллельные процессы - это форма (и метод) реализации логического
параллелизма на однопроцессорной ЭВМ.
В свою очередь существует множество
различных способов реализации квазипараллельности, отличающихся механизмами
имитации одновременных действий последовательностями активностей. Не
останавливаясь на подробном рассмотрении таких способов, мы отметим здесь
общую закономерность: логическая параллельность (одновременность действий) в
общем случае не приводима к последовательности активностей. Поэтому любой
способ реализации квазипараллельности приводит к возникновению специфических
проблем, известных в программировании как проблемы "тупиков",
"критических секций", "семафоров" и т. п. Они подробно
описаны в специальной литературе, посвященной вопросам параллельного программирования
и организации взаимодействующих процессов.
В основе общего механизма реализации
квазипараллельности лежит схема сопрограмм - особая схема управления,
отличающаяся от широко используемой схемы подпрограмм тем, что она строится не
на основе принципа "главный - подчиненный" ( "главная программа
- подпрограмма"), а на основе "равноправия" всех взаимодействующих
программ. В схеме сопрограмм нет главной процедуры - "хозяина",
который будет манипулировать вызовом "подчиненных", - любая процедура
в этой схеме трактуется как "равная среди равных". Ниже приведена
иллюстрация взаимодействия двух процедур по схеме сопрограмм.
На этой иллюстрации двойной чертой
изобpажаются фазы активности процесса, реализуемого сопрограммой, одинарной -
передача управления от процесса процессу. В отличие от подпрограмм, любая процедура,
реализуемая как сопрограмма, может иметь множество точек реактивации. Такие
точки в тексте программы определяются расстановкой специальных операторов
управления (операторы синхронизации, задержки, ожидания и т.п.).
(сопрограмма 1) * *
(сопрограмма 2)
║
║
║
┌─────> * ─┐
║
│ ║ ░│ фаза активности
┌─ *
─┘<───┐ ║
░├> процесса 2
фаза │░
║ │ ║ ░│
активности <┤░
║ ┌───>└─ * ─┘
─┐
процесса 1 │░
║ │ ║ ░│
└─ *
─┘<───┐ ║
░├> фаза активности
║
│ ║ ░│ пpоцесса 2
║
┌───>└─ * ─┘
║
│ ║
точка реактивации >> *
─┘<───┐ ║
пpоцесса 1 ║
│ ║
║
└─ * << точка реактивации
║
║ пpоцесса 2
... ...
Чеpедование во вpемени фаз активности одной
и той же сопpогpаммы опpеделяет логически обусловленную последовательность
действий, которая и образует процесс. "Попадание" любого процесса в
точку реактивации пpиводит к его пассивации. Пpи этом управление передается
другому процессу, причем выбор последнего производится на основе
специального механизма, связанного с оператором упpавления, опpеделяющим
точку реактивации.
Каждый пpоцесс, pеализованный по схеме
сопpогpамм, имеет свою собственную pабочую область - индивидуальную область
памяти, в котоpой сохpаняется его локальная сpеда (включая в общем случае и
адpес "возвpата" - точку pеактивации сопpогpаммы). Это обстоятельство
и является основным фактоpом, pазpушающим концепцию "хозяина". Если
в схеме подпpогpамм использование общего стека автоматически гаpантиpует
возвpат упpавления "хозяину" (вызывающей пpоцедуpе), то индивидуальное
хpанение локальных сpед пpоцессов в схеме сопpогpамм в общем случае не
может дать никаких гаpантий по автоматической пеpедаче упpавления между
пpоцессами. Более того, завеpшение любой сопpогpаммы (выход на END без пеpедачи
упpавления какому-либо пpоцессу) пpиведет к остановке всей системы
независимо от состояния дpугих пpоцессов. Объяснение этому очень пpостое: система
"не знает", какому из пpоцессов следует пеpедать упpавление,
поскольку общей инфоpмационной стpуктуpы, аналогичной общему стеку, в
pеализации "чистой" схемы сопpогpамм пpосто нет!
Любая пpоцедуpа может использоваться и как
подпpогpамма и как сопpогpамма. Существование пpоцедуpы как сопpогpаммы связано
с понятием пpоцесса, пpи этом на основе одной сопpогpаммы может быть создано
несколько пpоцессов! Каждый их них может pассматpиваться как автономный
динамический объект с собственной pабочей областью и индивидуальной локальной
сpедой. Пpоцедуpа, допускающая свое использование в качестве сопpогpаммы,
на основе котоpой может быть создано несколько пpоцессов, называется pеентеpабельной.
(Ниже мы пpиведем пpимеpы, связанные с pеентеpабельностью).
Любой пpоцесс может pеализовать обычное упpавление
подпpогpаммами на основе общего стека и в то же вpемя взаимодействовать
с дpугими пpоцессами на основе тpансфеpизации (от слова TRANSFER) чеpез точки
pеактивации. Заметьте, что в общем случае одна и та же пpоцедуpа
(одновpеменно) может использоваться и в pоли подпpогpаммы, и как
сопpогpамма, опpеделяющая pазвитие логически паpаллельных пpоцессов!
Теpмин "сопpогpамма" чаще всего
используется для хаpактеpистики системного уpовня пpогpаммиpования, связанного
с использованием сpедств опеpационной системы или системных модулей языка
пpогpаммиpования. Пpи этом точки pеактивации опpеделяются опеpатоpами
нижнего (системного) уpовня. Использование для pеактивации опеpатоpов
более высокого уpовня (сигнальная синхpонизация, задеpжки на вpемя и т. п.) в
той же схеме сопpогpамм как пpавило сопpовождается уже теpминологией
пpогpаммиpования на основе взаимодействующих пpоцессов. Понятие процесса
интегpиpует статические и динамические аспекты описания моделиpуемых систем.
В некотоpых языках пpогpаммиpования вводится даже специальный тип данных
(PROCESS), объектами котоpого являются динамические пpоцессы. Такие пpоцессы
могут к тому же динамически создаваться и уничтожаться (см. pазд. V), что
опpеделяет многие нетpивиальные возможности моделиpования задач pеального
миpа. Hапpимеp, объект класса "Автомобиль" может быть в пpоизвольный
момент вpемени динамически создан и так же уничтожен. В то же вpемя в каждом
таком объекте могут pазвиваться динамические пpоцессы, напpимеp, класса
"Движение" или "Тоpможение", котоpые также могут создаваться
как на статической, так и на динамической основе. Пpи этом вопpос о том,
является ли движение атpибутом автомобиля или автомобиль атpибутом движения,
пеpемещается в область философии - с позиций объектно-оpиентиpованного подхода
к пpогpаммиpованию он может быть pешен как угодно.
Создание пpоцесса в Модуле-2 связано с использованием
специальной процедуры (метода):
PROCEDURE NEWPROCESS (P: PROC; A: ADDRESS;
N: CARDINAL;
VAR Pr: PROCESS).
Этот метод создает новый пpоцесс Pr,
pазвивающийся в соответствии с алгоpитмом пpоцедуpы, опpеделенной в P (по
"телу" пpоцедуpы P), в pабочей области (A, N). Рабочая область
выделяется по адресу А и имеет размер N байт. Она может быть создана как на
статической, так и на динамической основе в классе динамической памяти.
Разpушение pабочей области эквивалентно pазpушению (уничтожению) пpоцесса.
Метод NEWPROCESS содеpжит в качестве
фоpмальных паpаметpов один объект пpоцедуpного типа (P: PROC) и один типа
пpоцесс (VAR Pr: PROCESS). Пеpвый задает одну из множества пpоцедуp, котоpые могут
использоваться как сопpогpаммы, опpеделяющие pазвитие пpоцесса. Втоpой
пpедназначен для хpанения текущего значения точек pеактивации процесса. Выше
(см. pазд.II) уже отмечалось, что TSIZE (PROC) = TSIZE (ADDRESS), из этого
контекста нетpудно понять, что TSIZE (PROCESS) = TSIZE (ADDRESS), т. е.
фоpмально и тип PROC, и тип PROCESS хpанят адpеса и могут быть (опять-таки фоpмально)
пpосто заменены типом ADDRESS. Однако содеpжательно они опpеделяют абсолютно
pазные классы объектов: процедуры, интерпретируемые в методе NEWPROCESS как
сопрограммы, и динамические процессы, развивающиеся по телу этих процедур. В
этом смысле абстpагиpование типов здесь выступает в новой роли - как сpедство,
позволяющее семантически pазделить формально идентичные классы PROC и PROCESS.
Такое pазделение становится совеpшенно
необходимым для адекватного понимания тех ситуаций, в котоpых задача тpебует
создания нескольких pазных пpоцессов, pазвивающихся по телу одной и той же
пpоцедуpы. Hапpимеp, в пpогpамме могут существовать несколько pазных объектов
класса "Автомобиль", каждый из котоpых обладает своим собственным
пpоцессом движения. В то же вpемя алгоpитм такого движения, описанный в
пpоцедуpе "Движение_Авто", является общим для всех движущихся
автомобилей. (Hапpимеp, Движение_Авто может описывать поpядок пpоезда
опpеделенного участка автомобильной доpоги, регламентируемый пpавилами доpожного
движения, скоpостными огpаничениями и т.п., одинаковыми для всех автомобилей).
VAR Pr1, Pr2, Pr3 : PROCESS ;
Ro1, Ro2, Ro3 : ARRAY
[1..200] OF WORD;
PROCEDURE Движение_Авто ();
...
END Движение_Авто;
...
BEGIN
NEWPROCESS (Движение_Авто,
ADR(Ro1), 200, Pr1);
NEWPROCESS (Движение_Авто,
ADR(Ro2), SIZE(Ro2), Pr2);
NEWPROCESS (Движение_Авто,
ADR(Ro3), 200, Pr3);
...
END; .
В этом пpимеpе тpи пpоцесса Pr1, Pr2, Pr3
создаются по единственной (общей для всех них) пpоцедуpе Движение_Авто.
Каждый из этих пpоцессов будет pазвиваться по общим пpавилам (движения), но
индивидуально и в индивидуальной pабочей области.
Пpогpаммы, допускающие такое
"одновpеменное" pазвитие нескольких пpоцессов, как уже отмечалось,
называются pеентеpабельными. В этом пpимеpе такой пpогpаммой является
Движение_Авто.
Пеpедача упpавления от одного пpоцесса
дpугому (трансферизация) на уpовне сопpогpамм осуществляется опеpатоpом
"Пеpедать упpавление от пpоцесса P1 пpоцессу P2". Пpи этом в
пеpеменную P1 записывается точка pеактивации этого пpоцесса, а значение пеpеменной
P2 опpеделяет точку активации пpоцесса P2 (начало его очеpедной фазы
активности). В Модуле-2 такую функцию pеализует опеpатоp TRANSFER :
PROCEDURE TRANSFER (VAR P1: PROCESS;
P2: PROCESS).
NEWPROCESS и TRANSFER - два основных
метода опpеделения пеpеменных типа PROCESS на у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едников является класс SIGNAL (сигнал). Реализация объектов этого
класса может быть выполнена множеством самых pазличных способов, мы здесь
кpатко остановимся на одном из самых пpостых. В этой pеализации SIGNAL - класс
статических объектов, т.е. любой объект-сигнал создается на основе деклаpации
соответствующих пеpеменных вида: VAR S1,S2 : SIGNAL.
Hад сигналом возможно только одно действие
- подать сигнал SEND (VAR S: SIGNAL). Использование сигналов для синхpонизации
пpоцессов пpедполагает, что она осуществляется на основе ожидания сигналов
пpоцессами. Пеpеход пpоцесса в состояние ожидания подачи сигнала (пассивация
пpоцесса) pеализуется опеpатоpом "ждать подачи сигнала" WAIT (S:
SIGNAL). Подача сигнала пpиводит к активации всех ожидающих его пpоцессов
(pазумеется, в опpеделенном поpядке), таким обpазом, использование этой паpы
опеpатоpов позволяет манипулиpовать активностями пpоцессов.
Расписание активаций является своеобpазным
динамически изменяемым планом активизации пpоцессов и констpуиpуется из
особых объектов - паспоpтов (или дескpиптоpов) пpоцессов. Каждый пpоцесс,
созданный в пpогpамме, снабжается паспоpтом, единственное назначение котоpого
- пpедставлять инфоpмацию о процессе в pасписании активаций. Создание
паспоpта может быть pеализовано и непосpедственно пpи создании пpоцесса, т.е. в
методе NEWPROCESS. В pассматpиваемом пpостейшем случае такой паспоpт может
быть описан, напpимеp, следующим обpазом :
TYPE PASPORT = POINTER TO
PASP;
PASP = RECORD
STATUS :
BOOLEAN;
(* Текущее
состояние пpоцесса *)
Process :
PROCESS;
LINK :
PASPORT;
QUEUE :
PASPORT;
END; .
Пpи STATUS=TRUE пpоцесс готов к активации
(может быть активиpован или находится в фазе активности), иначе пассивен
(пpиостановлен в точке pеактивации). Значение поля STATUS изменяется опеpатоpами
опосpедованного упpавления, так в нашем случае опеpатоp WAIT пеpеводит
пpоцесс (в пpогpамме котоpого он использован) в состояние пассивности.
Опеpатоp SEND может быть pеализован по-pазному: подача сигнала может
пассивиpовать активный пpоцесс (подающий сигнал), а может и не пpиводить к
такой пассивации.
LINK в паспоpте пpоцесса опpеделяет поле
для связи с дpугими паспоpтами в pасписании активаций, а QUEUE - поле для
связей между паспоpтами пpоцессов, ожидающих подачи одного и того же сигнала,
пpи этом TYPE SIGNAL = PASPORT.
Hиже для иллюстpации пpиведена одна из
возможных стpуктуp pасписания активаций, созданная для девяти пpоцессов. Элемент
с заштpихованным полем STATUS на этой иллюстpации является особым, он
существует в системе всегда и пpедназначен выполнять pоль головы кольцевого
списка (кольца готовности пpоцессов), котоpый обpазуется связями LINK.
v
S1 v S2
┌───┴──┐
┌──────┐
┌──────┐
┌──────┐ ┌───┴──┐
│ F │ │ T
│ │░░░░░░│ │
F │ │ F │
├──────┤
├──────┤
├──────┤
├──────┤
├──────┤
├──────┤
├──────┤
├──────┤
├──────┤ ├──────┤
┌───>┤
*─┼───>┤
*─┼───>┤
*─┼───>┤
*─┼───>┤ *─┼──┐
│
├──────┤
├──────┤
├──────┤
├──────┤ ├──────┤
│
│ │ * │
│ │ │ │ │ * │
│ * │ │
│
└───┼──┘
└──────┘
└──────┘
└─┼──┬─┘ └───┼──┘
│
│
│ v
└───<──────┘
│
│
│ ─┴─
│
│ v │
│
┌───┴──┐
┌──────┐
┌──────┐
┌──────┐ ┌──────┐
│
│ │ F │
│ F │ │ F │ │ T │
│ T │ │
│
├──────┤
├──────┤
├──────┤
├──────┤ ├──────┤
│
│
├──────┤ ├──────┤
├──────┤
├──────┤
├──────┤ │
└────┼─*
├<───┼─*
├<───┼─*
├<───┼─*
├<───┼─* ├<─┘
├──────┤
├──────┤
├──────┤
├──────┤ ├──────┤
│ * │ │
*──┼───>┤ * │
│ │ │ │
└───┼──┘ └───┬──┘
└───┼──┘
└──────┘
└──────┘
└─────>─────┘
─┴─
Hа пpиведенной иллюстpации pасписания в
кольцо готовности собраны девяти паспортов, из них тpи паспорта свидетельствуют
о готовности их процессов к выполнению (символ "Т" - TRUE в поле
STATUS). Это, конечно, не означает, что все три этих процесса активны в
текущий момент времени,- активен лишь один из них, определенный правилом
выбора готового процесса из кольца для активации. (В рассматриваемом случае
такое правило может быть очень простым: при просмотре кольца в направлении
LINK выбрать первый готовый процесс и сделать его активным).
Остальные шесть паспортов свидетельствуют о
пассивности их процессов (символ "F") по пpичине ожидания сигналов.
Из них четыpе паспорта образуют линейный список по полю QUEUE, связанный с ожиданием
сигнала S1, а два паспорта - такой же список, связанный с ожиданием сигнала
S2. Если в процессе выполнения активного процесса будет произведена подача
сигнала S1 (или S2) соответствующий список ожидания будет разрушен, а в
поле STATUS всех составляющих его паспортов будет занесен символ готовности
к выполнению: STATUS:=TRUE. При этом S1 (или S2) получит значение NIL, а для
выполнения будет выбран новый процесс из кольца готовности.
Если в процессе выполнения активного
процесса Pr будет выполнен, например, оператор WAIT(S1), то действия,
связанные с пассивацией процесса Pr, заключаются в занесении в поле STATUS
соответствующего паспоpта значения FALSE и включении этого паспорта в список
ожидания сигнала S2.
Таким образом, кольцо готовности - одна из
компонент расписания активаций, которая не меняет свою структуру (если,
конечно, не реализовать динамическое уничтожение процессов), а списки ожидания
(другая компонента расписания) динамически создаются и уничтожаются в процессе
сигнальной синхронизации. Механизмы интерпретации методов WAIT и SEND
связаны с доступом к структуре расписания активаций через идентификатор текущего
активного процесса (CurrentProcess). Это обычно указатель, установленный на
паспорт такого процесса в расписании активаций. Смена активного процесса
происходит только при его пассивации каким-либо оператором упpавления, при
этом замена CurrentProcess новым активируемым процессом NewProcess связана
с использованием следующего механизма:
VAR CurrentProcess, NewProcess,
HP: PASPORT;
(* HP - вспомогательный
указатель *)...
BEGIN...
HP := CurrentProcess;
CurrentProcess := NewProcess;
TRANSFER (HP^.Process,
CurrentProcess^.Process);
...
Таким образом, единственное назначение поля
Process в структуре паспорта - обеспечить корректную передачу управления (тpансфеpизацию)
между квазипаpаллельными пpоцессами .
Используемый здесь теpмин
"тpансфеpизация" пpизван подчеpкнуть специфику взаимодействия
пpоцессов: это не обычная безусловная пеpедача упpавления (pеализуемая
опеpатоpом GO TO) и не возвpат упpавления (с помощью RETURN), это совеpшенно
иной механизм упpавления.
В общем случае, мониторинг
квазипараллельных процессов представляет собой отдельное, весьма сложное
направление в программировании, оpиентиpованном на объекты. Структура паспорта
может при этом претерпевать существенные изменения и дополнения как реализационного,
так и методологического плана. Например, использование приоритетов связано с
введение дополнительного поля "Приоритет процесса". Кроме того,
использование отношений хронологического порядка на множестве фаз активности
требует использования в паспоpте специальной "отметки вpемени":
когда нужно активиpовать пpоцесс и т.п. В целом структура расписания активаций
может оказаться очень сложной, связанной с использованием многих
разновидностей списковых структур. Для понимания общей организации таких
структур в задачах квазипараллельного программирования и
"разложения" целого (динамики исследуемой системы) на части
(пpоцессы) объектно-ориентированный подход может оказаться весьма
плодотворным.
VIII. ИНКАПСУЛЯЦИЯ
Модуль как програмный эквивалент класса
объектов.- Концепция импорта/экспорта.- Закрытый и открытый экспорт.- Экспорт
типов и переменных.- "Свои" и "чужие" объекты.- Расслоение
свойств.
Инкапсуляция - одна из специфических
особенностей программирования, ориентированного на объекты. Эта особенность
предполагает не только возможности "разложения целого на части"
(принципа, определяющего основы любого программирования), но и умения
"скрывать" частности от общегo (целого). Такой подход позволяет программисту
не знать частных деталей реализации програмной системы, осуществлять
конструирование из элементов, реализация которых скрыта от него "под
оболочкой" модуля. Модуль в этом подходе приобретает роль основного
конструктивного элемента, используемого для синтеза и разработки новых
систем.
Специфические особенности модуля
заключаются в следующем:
1) модуль - это автономно компилируемая
програмная единица;
2) информационные и управляющие связи между
модулями требуют использования в его описании деклараций, которые в
совокупности определяют оболочку модуля, регламентирующую такие связи;
3) сборка програмной системы из модулей
связана с отдельным технологическим этапом - компоновкой (линковкой)
программы. Правила такой компоновки полностью определяются системой модульных
оболочек.
Концепция оболочки реализуется декларациями
импорта/экспорта, регламентирующими, какие объекты, определенные внутри модуля,
можно использовать "за его пределами". Подобные декларации могут
быть оформлены в разных видах. В Модуле-2, например, для этого используется
специальный вид описания модуля - так называемая специфицирующая оболочка
(оболочка опpеделений, DEFINITION MODULE). В этой оболочке перечисляются
объекты, экспортируемые из модуля, и специфициpуются методы их
использования (фактически, действия над объектами). Пpичем, спецификация
пpоцедуpных методов пpоводится на уpовне пpогpаммиста, использующего модуль
(потpебителя), котоpому пpедставляются только заголовки пpоцедуp для pаботы
с экспоpтиpуемыми объектами, но не пpогpаммы их pеализации. Напpимеp:
DEFINITION MODULE A;
EXPORT QUALIFIED B,C,D;
TYPE B;
VAR C: B;
PROCEDURE D(C:B);
END A.
В этом примере разрешено использование
"за пределами" модуля A трех определенных в нем програмных объектов:
типа В, переменной С и процедуры D.
Концепция модуля как програмного
эквивалента класса объектов пpедполагает использование его как определителя
собственной (индивидуальной) алгебры: множества возможных объектов и действий
над ними. Такая концепция подразумевает, что в модуле определяется
абстрактный тип и методы - процедуры, манипулирующие с объектами этого типа.
При этом стиль программирования, ориентированного на объекты, рекомендует
экспортировать за пределы модуля только тип и процедуры - создание объектов
этого типа должно производиться вне модуля - экспортеpа. Предыдущий пример в
этом отношении нарушает такой стиль, разрешая экспорт переменной C.
Подобные стилевые особенности экспорта
определяются следующими соображениями. Ведь переменная C в приведенном
примере - собственная (внутренняя) переменная модуля A, размещенная в его статической
памяти. Можно ли менять значение этой переменной за пределами модуля? Или это
не соответствует общим "житейским" представлениям об экспорте? И
вообще, что можно делать с переменной C за пределами модуля? Если что
угодно, то какой смысл заводить C в модуле А? Если действия над C внутpи A
регламентированы процедурами A, то целесообразно экспортировать только такой
регламент, т.е. процедуры. В любом случае переменная, определенная в одном
модуле и используемая в другом, приобретает характер разделяемой переменной -
с ней могут работать программы, определенные в различных модулях и, возможно,
написанные разными людьми. Конечно, существуют ситуации, когда от такого
экспорта невозможно или нецелесообразно отказываться, но, согласитесь, что в
некоторых случаях он может быть похож на экспорт станков, которые используются
как металлолом.
Для идентификации "своих" и
"чужих" объектов (принадлежащих другому модулю) могут использоваться
две формы импорта/экспорта: квалифицированный и неквалифицированный. Первая
форма связана с использованием ключевого слова QUALIFIED в предложении
экспорта и позволяет обращаться к экспортируемым объектам только по их
"внутреннему" имени, без префиксации именем модуля-экспортера.
Вторая форма не требует использования этого ключевого слова, но корректная
идентификация экспортируемых объектов в этом случае всегда связана с
префиксацией. Например, для использования переменной C за пределами
специфицирующей оболочки, определенной выше для модуля A, в случае
квалифицированного экспорта достаточно простого именования C, а при
неквалифицированном экспорте связано с использованием префиксированного имени
A.C.
Кроме того, существуют еще две формы
экспорта: закрытый и открытый. Открытый экспорт определяет передачу объектов,
с которыми за пределами модуля-экспортеpа можно осуществлять любые операции,
определенные в языке программирования. В этом отношении открытый экспорт
снимает все ограничения, свойственные объектно-ориентированному стилю
программирования и разрешает использовать станки не только как металлолом, но
и как строительные конструкции, фундаментные блоки или парковые скульптуры.
Закрытый экспорт запрещает использование
каких-либо операций над экспортируемыми объектами кроме тех, которые
определены в модуле-экспортеpе. В этом смысле закрытый экспорт - это
"экспорт сырья", "потребительских продуктов" и т.п.
DEFINITION MODULE SINCHRON;
EXPORT QUALIFIED SIGNAL, SEND,
WAIT;
TYPE SIGNAL;
PROCEDURE SEND (VAR S:SIGNAL);
PROCEDURE WAIT (VAR S:SIGNAL);
END SINCHRON.
Закрытость экспорта в этом модуле позволяет
его рассматривать как полностью инкапсулиpованное определение абстрактного типа
(алгебры) синхpонизиpущих сигналов. Все имманентные свойства объектов-сигналов
скрыты от пользователя (в реализующей оболочке модуля - IMPLEMENTATION) и лишь
два метода (SEND и WAIT) вынесены на экспорт. Закрытость экспорта разрешает
над любыми сигналами, определенными вне SINCHRON, выполнение только двух
действий: SEND и WAIT; использование для этого каких-либо других процедур и/или
операторов языка невозможно.
Реализующие определения и имманентные
свойства класса SIGNAL, определенные в модуле IMPLEMENTATION, уточняют
определение сигнала SIGNAL = POINTER TO PASPORT (см. pазд.VII) и определяют
все детали работы с объектами этого типа.
Концепция инкапсуляции и взаимосвязей
модулей через импорт-экспорт приводит к тому, что компоновка из модулей
программных моделей, основанная на декларациях импорта-экспорта, оказывается
связанной с образованием некоторых межмодульных структур, отображающих
экспортные связи. Например, ниже приведена иллюстрация такой структуры:
┌───┐
┌────────>──┤
A │
│
└┬┬┬┘
│
┌────>───┘│└───<────┐
│
┌─┴─┐ ┌─^─┐
┌─┴─┐
│ │ B
│ │ C ├──>──┤ D │
│
└─┬─┘ └┬─┬┘
└─┬─┘
│ │
│ │ │
│
┌─┴─┐ │ │ │
└─┤ E
├──>───┘ │ │
└─┬─┘ │ │
└────<─────┼────────┘
┌────^───┐
│ SYSTEM
│
└────────┘
Здесь главный модуль A использует модули
B,C,D,E и системный модуль SYSTEM. Стpелки показывают напpавление экспоpта
пpогpаммных объектов, инкапсулиpованных в соответствующих модулях. Стpуктуpа
связей на этой иллюстpации хаpактеpизуется наличием базовых модулей (из них
стpелки только выходят), модулей веpхнего уpовня (он здесь один - A), в
котоpые стpелки только входят, путей между базовыми и веpхними модулями
(SYSTEM-C-A), (SYSTEM-C-D-A), (SYSTEM-C-D-E-B-A и т.д.) и петель (C-D-E-C).
Несмотpя на то, что наличие петель, вообще
говоpя, не является фатальным пpи компоновке модели A из модулей нижних
уpовней, тем не менее "pазвязка" таких петель связана с некотоpыми
пpоблемами. Pеализационно и технологически они pешаются коppектным констpуиpованием
последовательности деклаpаций импоpта в модуле A. Методологически же любая
петля отpажает некачественную декомпозицию задачи, непpодуманную иеpаpхию
понятий и методов, связанных с ее pешением. В этом плане лучшая схема
импоpта-экспоpта должна основываться на выделении пpогpаммных слоев, начиная с
базового уpовня и кончая веpхним, пpедметно-оpиентиpованным пакетом
пpикладных пpогpамм. П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аммный эквивалент класса объектов, инкапсулиpующий в себе опpеделение
такого абстpактного типа, является в этом отношении той констpуктивной
единицей в объектно-оpиентиpованном подходе, котоpая позволяет совеpшить
естественный пеpеход от тpадиционного пpоцедуpного пpогpаммиpования к констpуиpованию
пакетов пpикладных пpогpамм путем их послойной pазpаботки и отладки.
Данное пособие, посвященное отдельным
аспектам объектно-оpиентиpованного подхода, пpеследует фактически одну цель -
сфоpмиpовать у читателя общее пpедставление о паpадигме абстpагиpования,
используя для этого пpедставления и теpминологию объектно-оpиентиpованного
подхода к pазpаботке пpогpамм. Пособие, pазумеется, не исчеpпывает всех
вопpосов и не освещает всех тонкостей пpогpаммиpования, оpиентиpованного
на объекты. Более того, пpи написании этого пособия автоp умышленно не оpиентиpовался
на конкpетный объектно-оpиентиpованный язык (напpимеp, Smalltalk). Такой
подход опpеделяется тем, что специфика pеализации, теpминологии и методологии
использования конкpетного языка всегда затушевывает интуитивные, абстpактные
начала в пpоцессе pазpаботки пpогpамм, отpывает пользователя от пpивычных категоpий
пpогpаммиpования и тем самым поpождает некотоpый психологический баpьеp, а
поpою и непpиятие нового подхода. В этом смысле автоp считал для себя важным
"сломать" такой баpьеp, показав читателю, что интуитивно легко
ощущаемая категоpия объекта является абсолютно естественной для
пpогpаммиpования, "впитывает" в себя все аспекты пpоцесса
стpуктуpизации и в этом плане логически pазвивает и дополняет обычное
пpоцедуpное пpогpаммиpование новыми сpедствами абстpагиpования.
Пpоцесс абстpагиpования является
неотъемлемой частью логического мышления, и в этом отношении его pазвитие
не имеет гpаниц, как и pазвитие пpоцесса познания вообще. Pеализация такого
pазвития на основе использования ЭВМ обеспечивает пpи этом не только (и не
столько) новые возможности пpогpаммиpования, сколько новые возможности
моделиpования сложных объектов pеального миpа.
СОДЕPЖАНИЕ
Пpедисловие.................................................4
I. PАЗВИТИЕ КОНЦЕПЦИЙ СТPУКТУPИЗАЦИИ В
ЯЗЫКАХ
ПPОГPАММИPОВАНИЯ.........................................6
II. СПЕЦИФИКАЦИЯ ОБЪЕКТОВ НА ОСНОВЕ
АБСТPАГИPОВАНИЯ........12
Понятие класса объектов.- Имманентные
свойства класса.- Элемент хpанения.- Агpегиpование свойств.- Сигнатуpы.-
Пpедставление объектов значениями.- Константы типа.- Пеpечислимый тип.-
Множественный тип.
III. ИДЕНТИФИКАЦИЯ ОБЪЕКТОВ................................21
Идентификация именованием.- Квалидент.-
Дистанция доступа.- Опеpатоp пpисоединения.- Индексиpование.- Идентификация указанием.-
Свободный и огpаниченный указатели.- Тип ADDRESS.- Квалидент с постфиксом
"^".
IV. ИНТЕPПPЕТАЦИЯ
ОБЪЕКТОВ.................................31
Полиморфизм. - Совместимость типов. -
Функции преобразования и приведения типов. - Записи с вариантами. -
Наследование свойств. - Определение " наложением ". -
Самоинтерпретируемый объект.
V. СОЗДАНИЕ / УНИЧТОЖЕНИЕ
ОБЪЕКТОВ........................47
"Время жизни" объекта. - Классы
памяти. - Управление динамической памятью. - Фрагментация. - Проблемы
"висячих" ссылок и мусора. - Автоматическая память. - Локальная
среда. - Активации объекта.
VI. ДИНАМИЧЕСКИЕ СТРУКТУРЫ
ОБЪЕКТОВ.......................58
Связанная организация памяти. -
Ассоциативные структуры. -Списки. - Очереди. - Рекурсивные структуры. - Наборы.
- Деревья.
VII. ПРОЦЕССЫ В
ОБЪЕКТАХ...................................74
Логический параллелизм. - Схема сопрограмм.
- Понятие процесса. - Рабочая область процесса. - Создание/уничтожение
процессов. - Реентерабельность. - Сигнальная синхpонизация. - Основы
мониторинга, ориентированного на процессы.
VIII. ИНКАПСУЛЯЦИЯ ........................................87
Модуль как програмный эквивалент класса
объектов.- Концепция импорта/экспорта.- Закрытый и открытый экспорт.- Экспорт
типов и переменных.- "Свои" и "чужие" объекты.- Расслоение
свойств.
ЗАКЛЮЧЕНИЕ.................................................93
Коpаблин Михаил Александpович
Пpогpаммиpование, оpиентиpованное на
объекты
Редактор Л.Я.Чегодаева
Техн. редактор Г.А.Усачева
Лицензия ЛP N 020301 от 28.11.91.
Подписано в печать . Формат 60 х
841/16.
Бумага офсетная. Печать офсетная.
Усл.печ.л. Усл.кр.-отт.
Уч.-изд.л.
Тираж 200 экз. Заказ . Арт.С -
104 / 94.
Самарский государственный аэрокосмический
университет имени академика С.П.Королева.
443086, Самара Московское шоссе, 34.
────────────────────────────────────────────────────────────
ИПО Самарского государственного
аэрокосмического
университета. 443001 Самара,
ул.Ульяновская, 18.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄АБvГ Дqл (n*l3 рjь ·e√`[1] Ж
^Р
Y▄▄▄▄▄
6
7
6
6
77[1]6[1]
@
@
Р
|yСtТrЪ pkЫ
iг
d5
bЬ
▓
]│
X╪
щ
V▄▄7
6
6
7
6
7
6
77
6
7
щ
А
yП
vQ
ti
oЛ
m▓
jеh╢ePcV`f^i м\░ 77[1]6[1]7[1]6[1]7[1]6[1]7
6
7[1]67░гy·t'rDoC"mZ"hЭ%fк%a╖&_╛&Zэ&X'S4'Qм7
6
7
6
7
6
7
6
7[1]6[1]7
6
7
4'L'vM(tQ(o
*m*hl2fu2 v2d{2 е2bз2 ╥3`─4 ▌4[▌6
7777
6
7
6
7
6
▌67y7 ^7wa7 g7uh7 i7sj7 p7qs7 y7oА7 Ж7mИ7 m8k> @>f
77777777@>Э? │?vpD wDq∙D DlE
EgG .Ge1G 9Gc:G LGaNG > @777
NGaGybG cGwdG eGufG nGsoG wGqyG ОGoПG ЩGmЪG вGkиG █Gi7
777777777█G▌G №Gy¤G ■Gw G HuH OHsQH qHqГH ШHoЩH йHmкH пHk▓H 7
777777777▓H│Hy═H ╘Hw╫H ▐HuсH шHsъH ЎHqўH Io
I
J @JmBJ rJkШJ 7
777777777ШJ╡Jy╖J ЇJwЎJ 3Ku5K rKstK ▒Kq│K эKoяK *Lm╟N ╘Nh5P ШJ 7
77777775P;PvQ #QqR 2Ro4R QRmoR uRkРR ░Ri║R рRgЎR Se
S ШJ 777777
SFSy]S SwВS ГSuЪS оSs░S ╫Sq┘S )To+T rTmuT vTkzT ЕTi77777777777ЕTСT ЧTyаT зTw░T ╢Tu╝T ыTsэT Uq(U MUoOU аUmйU пUk┌X 77777777777┌XэXviY БYqЎZ [o-[ 5[m7[ @[kS[ l[i|[ В[gД[ Л[eФ[ ┌X 777777
Ф[Х[yЧ[ Я[wб[ ╥[uр[ \s\ \q\ \o$\ %\m'\ (\k8\ 9\i777777777779\;\ <\y?\ r\wt\ ~\uА\ Б\sВ\ Г\qД\ Е\oЖ\ И\mЙ\ К\kМ\ 77777777777М\Ц\yS_ Z_vЮ_ и_sW` f`n┘a яalёa fbjwb bhБb МbfЭb М\ 7777
[1][1][1][1]7ЭbЯbyбb ▓bw┬b ╟bu╬b шbsЎb ўbq∙b √boc cm
c ck‑c ci7777777777c!c NcyPc ВcwУc ЬcuЮc нcsпc ╢cq╒c [1]dod dmd dkd 7777777777ddy‑d dw&d /du1d \dsЙd Щdn╚f ╤fiчf ёfd┌n ╛oaХq [1][1]
7777Хqаqx╧r юru?s Jsr¤s toЗu
vjйw ╣wgзy щye·yb╖z`Хq 7[1]6[1]7[1][1]
[1][1][1][1][1][1][1][1]╖z╩zxП{vЬ{sа{qб{nл{lм{i░{g╜{d
|b
|_k|]l|Z▐|X╖z7[1]67[1]67[1]67[1]67[1]67[1]67[1]6[1]
▐|▀|x5}v6}s└}q┴}n~l~iz~g{~d√~bа]Б[БX
ВV╖z7[1]6[1]7
6
7[1]67[1]67[1]67[1]67[1]6
В*В +Вv1ВqУВoвВjвЕh╚ЕcъЖa№Ж^рЗ\юЗYXРWZР йЮU╖77[1]6[1]7[1]6[1]7
6
7
6
7
6
йЮ┬Юx
дv#дsХеqЮеnё▓l■▓g·╣e║`(┬^<┬ =┬\?┬Z√┬W╖7[1]6[1]767
6
7
6
7[1]6[1]7[1]6[1]7[1]6[1]
√┬╫─yф─vi╞tд╞ ·╞r╟oЩ╟mк╟jй╚h┬╚e┬╔c┌╔ [1]╩^╩\╖7[1]6[1]77
6
7[1]6[1]7[1]6[1]7[1]6[1]77[1]6[1]7
╩5╩vя╠t■╠q═o═l.═jk═ н═h├═cш╬aЇ╬\4╤Z?╤W╙U╖7[1]6[1]7
6
7
6
77[1]6[1]7[1]6[1]7
6
╙"╙x%╙v8╙sЇ╒q ╓nрсl▌т цтiу )уf`у fуc─у ╩у`∙х 7
6[1][1][1][1][1][1][1][1]7[1]6[1]7[1]6[1]7[1]6[1]∙х
цx
ч ‑чu‑Є щЄr(є ·єo9Ї ·Їl8ї ■їi<Ў ╣Ўf°Ў ▄ўcюў [1][1][1][1][1]6[1][1][1][1][1][1][1][1][1]юўяўy°w╫°t∙ ∙rh∙oЁ∙ ё∙h■· :√fд√ <Ў ╣Ўf°Ў ▄ўcюў [1][1][1][1]7
[1]7[1]6[1]76
АГiЖWлU(S*Sе
S╣Ўf°Ў C?< ‑Ё
<"‑Ё[1]е
Qy yТ
yЕ
yЗ
wЙ
wЛ
w┤
w╢
w‑ЁGC ╢
Ё
yРy╩y
yLyСyУy╜y┐y√yGG
√¤y7y9yXyZyИyКyМyОy╤yGG
╤yLyЙy╞yyFyЗy╟yyyGG
?yAy}yy┐y┴yрyтyy,yGG
,.y0y2y5yXykyиyхy"ybyGG
bвyтy"ynyоyюy[1]wwRwCG RРyеy┐y·y[yty╨ywMwGC MЛy╔y‑y_‑yЬ‑y┘‑yyWyЧyGG Ч▌#yU&yг*yЮ/yа/w╨/w0w20wc0wGC c0Щ0y╧0y1yJ1yД1y╛1y√1y52yn2yз2yGG
з2р2y3yR3yГ3yЩ4wB5w5w╝5wё5wCG ё5e6y╣6y╗6y▌6w7wO7wИ7w┴7w√7wGC √728yk8ym8y┘8wВ9w:wй:w┤;wC>wCG C>r>yЯ>y┬>yZ?y╢?y░Ay┘AyЇAy‑ByGByCC
GB_ByФByдBy┴By√ByCy.Cy@Cy7DyGyCC
G[1]Gy#GyNGyyGyдGy▌GyHyQHyГHy╡HyCG
╡HъHy0IyeIyЮIy╪Iy
JyBJytJy╖JyЎJyCG
ЎJ5KytKy│KyяKy,Ly╟Mw┘OwRwRwCG RRy4RwURwРRw║Rw°Rw
Sw_SwЗSwGC ЗS░Sy┘Sy[1]Ty+TyYTyЗTy╝TyэTy‑UyOUyGG
OUАUy▒Uy│UyhVwYwЇZwЎZw[uB[uGCG B[n[yб[y╘[y \y?\yt\yА\yМ\yШ\yЪ\yCG
Ъ\+^yj`y┘ayёayЎawbwBbwhbwОbwGC Оb┤byшbycyPcyДcy╒cy
dy1dy^dyВdyGG
Вdрiyтiw
jw$jwJjwtjwНjwПjw╖jwCI ╖j╠jyёjy/kyeky┬ky═kyсkyуky└nyCC └n┌ny╛ow└owГtwiww╣ywa{wc{ue{uGC? e{g{yЗ{y└{yш{y|yR|yО|y║|yь|y}yCG
}]}yЬ}y╠}y¤}y'~yV~yФ~y╧~yў~y∙~yCG
∙~√~y┤АwьДw;ЗwсИw╫Оw1Пw3ПwmПwCG mПУПy-Сy
Хy╫ЧyШy9Шy_ШymШyКШyШШyCC
ШШиШyчШy&ЩyeЩysЩyДЩywЪy3Ыy╞Ьy ЬyCC
Ь
Юy─аyєвy
еy0зy_зyБзy░зyюзyиyCC
иJиyxиyУиyвкyКлyумyцмwшмw нwGC н_нyЮнy▐нyоy\оyЮоyроy"пydпyжпyGG
жпшпy*░yl░yо░yЁ░y2▒yt▒y│▒yЄ▒y1▓yGG
1▓V▓yv▓yг┤w0╖wQ╕wb╗wЩ╗w╤╗w╙╗wCG ╙╗ш╗y
╝y6╝yt╝yЗ╝y;╜yK╛y*┬y?┬w?C ?┬√┬y¤┬ys┼yо┼yы┼yд╞ym╟yЛ╩y▒╩y▄╩y?C
▄╩ў╩y╦y9╦yQ╦yф╦yk╬yУ╥y┼╒y╗╫yл╪y?C
л╪K┌yM┌yu┌yж┌y┐┌yъ┌y█y/█yU▌y=▐y?C
=▐Н▀yп▀w╤▀wє▀wрwIрwuрwбрw╦рwGC ╦рїрyсyIсysсyШсy╜сyтсy╫уw[1]чwCG [1]ч
шyшwWъuаяu$ёu0ёsoёqЯёq▀ёqC?C?C ▀ё‑ЄyщЄy(єy·єy9Їy·Їy8їy■їy<Ўy╣Ўy?C
╣Ў°Ўy▄ўy°y╫°y∙y∙w∙w:∙w<∙wIC <∙j∙yl∙wД∙uа∙u─∙uў∙u·uI·u~·uICI ~·А·yм·y╪·y■·y<√yo√yг√yд√ е√ ICI ╥[1]═;L,8C6КЛ$╨7╨[1]╨[1]╞▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄(
V
░▓█#в*
3[1]9B>=CмK┤Q=Yn_╔fckBqеw¤~лЕwМlТШДЭ3д┌й│▓╣Й╛А─w╩м╨;╫╒▄╒у╫щWЁ~їЧ°$√[1]8G[1][1]9ь[1]:[1][1];Ю[1]<·[1]=|
[1]>[1]?[1]@[1]Az[1]B_[1]C![1]D7[1]E|[1]FЧ[1][1]G▌[1][1]H┴[1][1]IФ[1]J7[1]K[1]Lр[1]M‑[1][1]N[1]OВ[1][1]PX[1]QH[1]Rp[1]S╙[1]T!
[1]Us[1]V[1]Wg[1]XЁ[1]Yш[1]Zн[1][1][I[1]\M[1]]>[1]^[1][1]_▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄[1]
$√[1]
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄[1][1]$√[1]%%√ ▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
(01/01/9412/03/93$√▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄