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

 

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

│ * │ ─┴─

└──┼──┘ H3 H4

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а хpанит инфоpмацию о состоянии всех пpоцессов, пpо­те­каю­щих в пpогpаммной модели, пpи этом методы SEND и WAIT как ди­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 в поле STA­TUS). Это, конечно, не означает, что все три этих процесса ак­тив­ны в текущий момент времени,- активен лишь один из них, оп­ре­де­ленный правилом выбора готового процесса из кольца для ак­ти­ва­ции. (В рассматриваемом случае такое правило может быть очень простым: при про­смотре кольца в направлении 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 MO­DU­LE). В этой оболочке пере­числяются объекты, экспортируемые из мо­дуля, и спе­ци­фи­ци­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е. В этом смысле закрытый экспорт - это "экспорт сырья", "пот­­ребительских продуктов" и т.п.

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


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Ы

d5


]│
X╪
щ
V▄▄7
6
6
7
6
7
6
77
6
7
щ

А

vQ

ti


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

ImI IkI Ii7


777777777II Iy0I cIweI ЬIuЮI ╤Is╙I ╓Iq╪I
Jo

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 ­ci7777777777­c!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Т




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┘‑y­yW­yЧ­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$√▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄


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. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ОБЪЕКТОВ

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ