Реферат: Программирование, ориентированное на объекты
p>Заметим, что в этой интерпретации дерево реализуется на одно
ных списках (в отличие от набора). Особое положение корня оп
деляется единственным свойством - отсутствием вершин-предков, любой лист дерева характеризуется полным отсутствием вершин-потомков. Поскольку любая вершина в связанной структуре дерева от
крывает доступ только "вниз" (только к своим поддеревьям), она может интерпретироваться как корень соответствующего поддерева. В этом смысле лист является корнем "не выросшего" дерева и оп
ляет его своеобразную "точку роста". Включение в дерево новой вершины и удаление старой не должно нарушать общего отношения по
ка на множестве вершин.
Примером такого отношения может служить отношение "больше- меньше", определяющее структуру бинаpного дихотомического дере
ва. В таком деpеве все вершины любого правого поддерева имеют значение инфор
ледовательности целых чисел 30,70,80,21,25,17,4, начиная с 30, должно приводить к созданию следующей структуры:
Нетрудно заметить, что процесс конструирования такого дерева про
исходит сверху-вниз, начиная с корня, путем последовательного сравнения числовых значений, pазмещаемых в веpшинах, с целью определения места размещения соответствующей вершины в структуре дерева. Любая модификация дихотомического деpева (удаление ве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 * + ", определяющей "польский" эквивалент исходной стро
ки. Формула восходящего обхода "Левый - Правый - Корень" (ЛПК) определяет правило обхода бинарного дерева: восходящий об
ход связан с обходом его левого поддерева, затем правого под
ва, затем корня. Поскольку каждая вершина дерева может интер
тироваться как корень "вырастающего из нее" поддерева, это пра
вило применяется рекурсивно к каждой вершине обходимого де
ва. Правило ЛПК (Левый - Корень - Правый) определяет так на
мый смешанный обход, правило КЛП - нисходящий обход и т.д. Нет
дно заметить, что смешанный обход дерева дихотомии по пра
вилу ЛКП приведет к формированию строки чисел (хранящихся в вершинах этого дерева), упорядоченной по возрастанию, а такой же обход по правилу ПКЛ - к формированию строки, упорядоченной по убыванию соответствующих чисел. Таким образом, между структурой дерева, от
ношением порядка на множестве информационных компонент его вер
шин и видом обхода существует глубокая связь, определяемая ре
курсивной природой структуры дерева. Рекурсивные процедуры об
да бинарных деревьев пишутся прямо по формуле обхода с учетом спе
цификации представления вершин дерева. Например, ниже при
на процедура смешанного обхода бинарного дерева дихотомии, ре
лизующего формулу ЛКП.
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)
*
п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аммы связано с по
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
