ция Яла как особого вида лодки связана с использованием всех трех слоев: А,В,С. Декларация вида "Структура_Яла" в объектно-ориентированном языке заменяется отношением
Ял ---+ +------->-------+
то его восходящий обход (пунктир на рисунке) приведет к стро
ке " 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)
*