Парадигмы программирования

       

Базовые понятия


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

По мнению Т.Хоара "Параллельная композиция действий внешне не сложнее последовательного сочетания строк в языке программирования" [[25]]. Функциональное программирование на Лиспе и других языках благодаря необычности (не смягчившейся за 40 с лишним лет) и более гибкой модели организации вычислений позволяет предоставить простые примеры для показа непривычных идей параллелизма, интуитивное понимание которых не требует напряжения [[8]].

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

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

Ряд моделей параллельных процессов концептуально сродни недетерминизму. Многие из них строятся как коллективное поведение объектов - автоматов с состояниями, изменение которых рассматривается как вычислительный процесс.

Термин "процесс" используется для обозначения поведения "объекта".

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

Первая абстракция при моделировании процессов - исключение времени, т.е. отказ от ответов на вопрос происходят ли события строго одно за другим.
Это обеспечивается следующими договоренностями:

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


Если известно, что процесс P может произойти вслед за событием x, влекущим этот процесс, то событие x называют префиксом процесса P.

x -> P -- P за x

Обычно для решения конкретной задачи вводится специальный объект - автомат, способный реагировать на определенное множество событий в зависимости от состояния автомата.

Поведение объекта, который способен действовать, можно описать в виде системы правил, внешне похожих на уравнения. Решением такой системы уравнений являются процессы, которые может выполнить автомат.

Пример 6.1. Рассмотрим автомат, установленный в здании НГУ на 4-ом этаже, продающий кофе.

Торговый автомат: {деньги, кофе} (деньги => ( кофе => автомат ) )

- нет кофе без денег - нет двойных порций

сломанный автомат - нет кофе

(деньги => СТОП )

- нет действий = нет событий

Пример 6.2. [25] Рассмотрим простые задачи типа перемещения фишки на клетчатой доске по свободным позициям.

X   
O X
На данной доске фишка может двигаться лишь вправо или вверх. При множестве событий - { враво, вверх } правильный процесс можно специфицировать как:

( враво вверх вправо => СТОП )

Пример 6.3. [25] Простейшая модель часов - типовой пример рекурсивного описания процессов.

Часы: { тик-так }

(тик-так - часы) - рекурсия

Пример 6.4. [25] Небольшое изменение разрешенных позиций на клетчатой доске показывает возможность выбора вариантов хода событий при выполнении процессов. Появляется понятие "меню".

X  
O
( вверх => СТОП | вправо вправо вверх СТОП )

| - представление вариантов в меню процесса



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

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

Высказывание: Если для всякой альтернативы меню дальнейшего поведения совпадают, то процессы тождественны.

Формулировка такого рода закономерностей позволяет разделить описание процесса на уровень спецификации и реализации.

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


Содержание раздела