Workflow - процессор на алгорифмах Маркова.
Этот материал можно рассматривать как пример того, что может собрать обычный инженер из уже существующих элементов. Несмотря на то, что «оригинальные идеи редко бывают хорошими» (А.А. Степанов), при соблюдении определенной осторожности можно получить вполне рабочий результат.
Конечно, на текущий момент существует немало workflow - процессоров. Конечно, одиночке бесполезно тягаться с корпорациями, но я могу показать, как изготовить workflow - процессор буквально за пару часов. И он будет практически такой же, как и любой из его корпоративных собратьев.
Задача любого workflow (WF) - языка состоит в том, чтобы описать состояния, которые возникают при исполнении задачи и связи, которые существуют между этими состояниями. Принято различать несколько видов состояний, однако любое из них можно отнести к одной из 3-х групп без потери смысла. Вот эти группы:
1. стартовые состояния;
2. внутренние состояния;
3. конечные состояния.
Связи, или иначе - переходы, принято делить на условные и безусловные. Так или иначе, но решение о совершении перехода принимается за пределами WF. То есть событие, вызывающее переход, приходит извне потока работ. В то же время логично предположить, что при исполнении WF могут возникать какие-то события, которые порождаются самим потоком. Таким образом, события, которые управляют переходами из состояния в состояние WF можно разделить на:
1. внешние;
2. внутренние.
Внутренние события в сточки зрения внешнего наблюдателя чем-то напоминают ипсилон - переходы недетерминированного конечного автомата, когда WF «просто так» изменяет свое текущее состояние.
Следующий шаг состоит в том, что и состояния и события обозначим символами. Под символом будем понимать объект. Это корректно, потому что в [1] символ употребляется в математическом смысле, что на обычный язык может быть приблизительно переведено как «именованная сущность».
Теперь можно описать процесс функционирования WF. Пусть все состояния обозначаются символом S с индексом, а события - e с индексом. Тогда переход из состояния Si в Sj по событию ek можно записать так:
Si ek -> Sj,
то есть с помощью операции алгорифма Маркова (АМ). Если продолжить далее рассуждать в этом направлении, то получается следующее.
В основе лежит объект символ. У символа могут быть любые свойства и методы, необходимые для выполнения задачи. Набор всех символов образует алфавит WF.
WF описывается несколькими алгорифмами, которые могут исполняться параллельно. Все алгорифмы равноправны между собой. Каждый из них - это всего лишь набор правил обработки информации.
Алгорифм состоит из упорядоченного набора операций. Поиск сработавшей всегда начинается с 1-й операции. Если операция сработала, то дальнейший поиск прекращается. Если ни одна операция не сработала, то ничего и не произойдет. Если не сработала ни одна операция ни одного алгорифма, то состояние WF остается без изменения.
Операция состоит из двух частей: образца и подстановки и в общем случае имеет вид:
L -> D, где L - образец, D - подстановка. L и D - неупорядоченные множества с уникальными значениями, которые состоят из символов.
Состояние WF описывается с помощью слова состояния. Это неупорядоченное множество с уникальными значениями, состоящее из символов. Символы добавляются в слово состояния с помощью специальной процедуры. Изъятие символов из слова состояния не должно производиться.
Стартовое состояние WF задается отдельной процедурой. По умолчанию эта процедура добавляет в слово состояния все символы, тип которых указан как начальный.
Остановка набора алгорифмов определяется истинностью специального предиката. По умолчанию, предикат является истинным, если в слово состояния входит хотя бы один символ, тип которого - конечный.
Цикл обработки информации:
1) Добавить символ события в слово состояния.
2) Если исполнение набора алгорифмов завершено - то прекратить обработку.
3) Создать пустые множества образцов и подстановок.
4) Найти все сработавшие операции.
a. Взять алгорифм.
b. Найти первую такую операцию, левая часть которой полностью входит в слово состояния.
c. Если такая операция найдена, то добавить ее образец в множество образцов, а ее подстановку - в множество подстановок
5) Найти разницу между словом состояния множеством образцов.
6) Эту разницу объединить с множеством подстановок и присвоить значение слову состояния.
7) Если предикат завершения равен истине, то выставить флаг завершения работы WF.
Применение АМ имеет много положительных сторон. Наиболее важным из них является легендарная краткость. Для того, чтобы создать процессор АМ достаточно определить всего 3 операции: запуск, перехода в другое состояние и останова. При этом, в отличии от большинства моделей, все три процедуры можно определить в виде конкретного кода для целого класса АМ.
Немного теории.
Теория множеств и конструктивная математика. Это наиболее узкое место во всей работе. Применение множеств для описания работы алгорифмов Маркова (АМ) влечет однозначное уменьшение их вычислительных возможностей. Я не возьмусь утверждать, что реализация АМ с использованием множеств обладает полнотой по Тьюрингу в отличии от оригинала. И даже не возьмусь оценить, сколько потеряет модель при таком подходе. Однако, положение спасает то, что WF - процессор не вычисляет, а управляет. Что поделать, в этот раз накормить всех программистов одной машиной не удалось.
«КТ головного мозга». Попытка создать новый язык для описания WF закончится тем, что полученный язык будет эквивалентен существующим. Это очевидно с точки зрения теории, но не совсем очевидно с точки зрения практики: мешают все эти значки, от которых рябит в глазах. АМ дают возможность сравнивать функциональность паттернов и однозначно сопоставлять их.
Как это можно применять на практике.
Тема WF хороша тем, что не нужно ничего особо придумывать: все уже сделали до тебя. Поэтому для тестовых примеров я взял паттерны из [2]. Сам пример находится http://sourceforge.net/projects/mnamespaceexamp/
Процесс программирования WF выглядит следующим образом:
1. Нарисовать WF.
2. Обозначить все состояния и переходы соответствующими символами. Начальные состояния буду стартовыми символами, конечные - финишными символами, все прочие - внутренними символами. Условия выражаются с помощью символов - внешних событий. Если переход безусловный, то это следует отразить событием "передача управления при окончании действия". Если WF должен без дополнительных условий сразу же перейти в какое-то состояние, то для этого надо использовать символ - внутреннее событие.
3. Закодировать операции, наследуясь от объектов библиотеки.
4. Пользоваться.
Пару слов о реализации библиотеки. В текущем виде её применение в промышленном программирование невозможно. Реализация не учитывает большого количества моментов, которые обычно возникают на практике. Однако, в данном случае, речь идет прежде всего об идее, о принципе. С другой стороны, это не так уж и плохо: поскольку библиотека представляет лишь набор продуктов, то каждый волен смешать салат по своему вкусу.
1. Марков А.А. Нагорный Н.М. Теория алгорифмов. - М: Наука. 1984.
2. Андрей Михеев, Михаил Орлов. Перспективы WorkFlow-систем. Паттерны - попытка навести порядок в "мире" workflow. http://wf.runa.ru/rus/images/3/3c/Article.pdf
Конечно, на текущий момент существует немало workflow - процессоров. Конечно, одиночке бесполезно тягаться с корпорациями, но я могу показать, как изготовить workflow - процессор буквально за пару часов. И он будет практически такой же, как и любой из его корпоративных собратьев.
Задача любого workflow (WF) - языка состоит в том, чтобы описать состояния, которые возникают при исполнении задачи и связи, которые существуют между этими состояниями. Принято различать несколько видов состояний, однако любое из них можно отнести к одной из 3-х групп без потери смысла. Вот эти группы:
1. стартовые состояния;
2. внутренние состояния;
3. конечные состояния.
Связи, или иначе - переходы, принято делить на условные и безусловные. Так или иначе, но решение о совершении перехода принимается за пределами WF. То есть событие, вызывающее переход, приходит извне потока работ. В то же время логично предположить, что при исполнении WF могут возникать какие-то события, которые порождаются самим потоком. Таким образом, события, которые управляют переходами из состояния в состояние WF можно разделить на:
1. внешние;
2. внутренние.
Внутренние события в сточки зрения внешнего наблюдателя чем-то напоминают ипсилон - переходы недетерминированного конечного автомата, когда WF «просто так» изменяет свое текущее состояние.
Следующий шаг состоит в том, что и состояния и события обозначим символами. Под символом будем понимать объект. Это корректно, потому что в [1] символ употребляется в математическом смысле, что на обычный язык может быть приблизительно переведено как «именованная сущность».
Теперь можно описать процесс функционирования WF. Пусть все состояния обозначаются символом S с индексом, а события - e с индексом. Тогда переход из состояния Si в Sj по событию ek можно записать так:
Si ek -> Sj,
то есть с помощью операции алгорифма Маркова (АМ). Если продолжить далее рассуждать в этом направлении, то получается следующее.
В основе лежит объект символ. У символа могут быть любые свойства и методы, необходимые для выполнения задачи. Набор всех символов образует алфавит WF.
WF описывается несколькими алгорифмами, которые могут исполняться параллельно. Все алгорифмы равноправны между собой. Каждый из них - это всего лишь набор правил обработки информации.
Алгорифм состоит из упорядоченного набора операций. Поиск сработавшей всегда начинается с 1-й операции. Если операция сработала, то дальнейший поиск прекращается. Если ни одна операция не сработала, то ничего и не произойдет. Если не сработала ни одна операция ни одного алгорифма, то состояние WF остается без изменения.
Операция состоит из двух частей: образца и подстановки и в общем случае имеет вид:
L -> D, где L - образец, D - подстановка. L и D - неупорядоченные множества с уникальными значениями, которые состоят из символов.
Состояние WF описывается с помощью слова состояния. Это неупорядоченное множество с уникальными значениями, состоящее из символов. Символы добавляются в слово состояния с помощью специальной процедуры. Изъятие символов из слова состояния не должно производиться.
Стартовое состояние WF задается отдельной процедурой. По умолчанию эта процедура добавляет в слово состояния все символы, тип которых указан как начальный.
Остановка набора алгорифмов определяется истинностью специального предиката. По умолчанию, предикат является истинным, если в слово состояния входит хотя бы один символ, тип которого - конечный.
Цикл обработки информации:
1) Добавить символ события в слово состояния.
2) Если исполнение набора алгорифмов завершено - то прекратить обработку.
3) Создать пустые множества образцов и подстановок.
4) Найти все сработавшие операции.
a. Взять алгорифм.
b. Найти первую такую операцию, левая часть которой полностью входит в слово состояния.
c. Если такая операция найдена, то добавить ее образец в множество образцов, а ее подстановку - в множество подстановок
5) Найти разницу между словом состояния множеством образцов.
6) Эту разницу объединить с множеством подстановок и присвоить значение слову состояния.
7) Если предикат завершения равен истине, то выставить флаг завершения работы WF.
Применение АМ имеет много положительных сторон. Наиболее важным из них является легендарная краткость. Для того, чтобы создать процессор АМ достаточно определить всего 3 операции: запуск, перехода в другое состояние и останова. При этом, в отличии от большинства моделей, все три процедуры можно определить в виде конкретного кода для целого класса АМ.
Немного теории.
Теория множеств и конструктивная математика. Это наиболее узкое место во всей работе. Применение множеств для описания работы алгорифмов Маркова (АМ) влечет однозначное уменьшение их вычислительных возможностей. Я не возьмусь утверждать, что реализация АМ с использованием множеств обладает полнотой по Тьюрингу в отличии от оригинала. И даже не возьмусь оценить, сколько потеряет модель при таком подходе. Однако, положение спасает то, что WF - процессор не вычисляет, а управляет. Что поделать, в этот раз накормить всех программистов одной машиной не удалось.
«КТ головного мозга». Попытка создать новый язык для описания WF закончится тем, что полученный язык будет эквивалентен существующим. Это очевидно с точки зрения теории, но не совсем очевидно с точки зрения практики: мешают все эти значки, от которых рябит в глазах. АМ дают возможность сравнивать функциональность паттернов и однозначно сопоставлять их.
Как это можно применять на практике.
Тема WF хороша тем, что не нужно ничего особо придумывать: все уже сделали до тебя. Поэтому для тестовых примеров я взял паттерны из [2]. Сам пример находится http://sourceforge.net/projects/mnamespaceexamp/
Процесс программирования WF выглядит следующим образом:
1. Нарисовать WF.
2. Обозначить все состояния и переходы соответствующими символами. Начальные состояния буду стартовыми символами, конечные - финишными символами, все прочие - внутренними символами. Условия выражаются с помощью символов - внешних событий. Если переход безусловный, то это следует отразить событием "передача управления при окончании действия". Если WF должен без дополнительных условий сразу же перейти в какое-то состояние, то для этого надо использовать символ - внутреннее событие.
3. Закодировать операции, наследуясь от объектов библиотеки.
4. Пользоваться.
Пару слов о реализации библиотеки. В текущем виде её применение в промышленном программирование невозможно. Реализация не учитывает большого количества моментов, которые обычно возникают на практике. Однако, в данном случае, речь идет прежде всего об идее, о принципе. С другой стороны, это не так уж и плохо: поскольку библиотека представляет лишь набор продуктов, то каждый волен смешать салат по своему вкусу.
1. Марков А.А. Нагорный Н.М. Теория алгорифмов. - М: Наука. 1984.
2. Андрей Михеев, Михаил Орлов. Перспективы WorkFlow-систем. Паттерны - попытка навести порядок в "мире" workflow. http://wf.runa.ru/rus/images/3/3c/Article.pdf