Softcraft: новости сайта и не только (016)

Softcraft: новости сайта и не только (016)

http://www.softcraft.ru

О новом материалe

Появилась статья Вячеслава Любченко: "Конечно автоматная технология программирования" (КА-технология). Думаю, что читающим "Мир ПК", представлять автора не надо. Там постоянно выходят его материалы на эту тему. Оттуда же также скачать библиотеку, облегчающую построение автоматных программ. Да, в полку автоматчиков, дислоцированном на сайте, очередное прибавление. Их уже больше трех. Поэтому, могут не только "сообразить", но и "подраться". Предпосылки к этому появились, так как Вячеслав проводит сравнение КА-технологии со SWITCH. Да у меня, очередной раз, возникло желание схватиться за автомат, но, подавив его, я решил остаться прислугой, подающей питье и пищу для размышлений-раздоров. Ну, подумаешь, кое-где, вставлю свою шпильку:). А тем для разногласий более чем предостаточно. Лично мне интересны дискуссии по параллелизму, а также сопоставлению автоматной и алгоритмической моделей. И вот, моя "ворчалка".

Где же спрятался параллелизм автоматов?

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

Например, в UML существует возможность описания асинхронного взаимодействия параллельно работающих последовательных автоматов с применением диаграмм состояний (statechart diagramm). При этом автомат может являться иерархическим, то есть состоять из вложенных автоматов. Каждое состояние может определять несколько, параллельно работающих автоматов, содержащих общие точки синхронизации, порождения параллельных переходов и их слияния. Но это описание страдает общностью, так как предназначено для поддержки этапа проектирования.

Наиболее полно и интересно применение КА автоматов рассматривается в книге Ч. Хоара "Взаимодействующие последовательные процессы" (М.: Мир, 1989). Правда, описание процессов в ней опирается на язык, напоминающий праволинейные грамматики. Однако эквивалентность этих грамматик конечным автоматам общеизвестна. Эта модель была положена в основу языка параллельного программирования ОККАМ и транспьютерных систем, обладающих истинным параллелизмом. В свое время транспьютерные архитектуры были весьма популярны и продаваемы. Причина же неудач этих систем во многом оказалась обусловлена технологическими проблемами.

Не могу не упомянуть идеи, которые были положены в основу проекта машины с динамической архитектурой (МДА), разрабатываемой в Ленинградском научно-исследовательском вычислительном центре под руководством В.А. Торгашева. Сошлюсь на его статью: "Управление вычислительными процессами в машинах с динамической архитектурой" (В кн.: Вычислительные системы и методы автоматизации исследований и управления. М.: Наука, 1982, с. 172-187). Вряд ли сейчас многие знают об этом проекте. Поэтому, приведу цитату: "В данной работе рассматривается виртуальная машина с параллельным управлением, базирующаяся на математической модели параллельных вычислений, предложенной Барздинем (Барздинь Я.М. Проблемы универсальности в теории растущих автоматов. - Докл. АН СССР, 1964, 157, №3, с. 542-545). Эта модель представляет собой сеть конечных автоматов, для каждого из которых, помимо обычных функций переходов и выходов, определены две специальные функции, первая из которых изменяет связи автомата с другими автоматами сети, что обеспечивает изменение конфигурации сети, а вторая порождает новые автоматы, что приводит к росту сети. Таким образом, модель соответствует растущему автомату".

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

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

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

Так что, коллективное поведение автоматов изучалось достаточно давно. Были построены модели, которые находили практическое применение. Возможно, эти методы и сейчас имели практическое применение, если бы не технологических прорыв в микроэлектронике, резко повысивший эффективность последовательных архитектур. Но все возвращается. И возможно, что скоро многие идеи будут открыты заново и реализованы с использованием современной технологии.

Подводя первый промежуточный итог, могу сказать: разработанная Вячеславом библиотека действительно может быть весьма полезной для моделирования одновременного поведения нескольких автоматов. Но это, все же, моделирование, так как описанный процесс все равно выполняется последовательно. К сожалению, используемая модель коллективного поведения автоматов (или одного параллельного автомата), нигде однозначно не описана. Примеров же программ, для представления всех возможных особенностей параллелизма (синхронизация, конфликты, тупики, хорошее поведение и т.д.) явно недостаточно.

P.S. Из дополнительной переписки уже выяснилось, что в основе лежит модель синхронно функционирующих автоматов. Осталось (для гурманов:) дождаться формализма (м-а-а-леньког:).

Разные ли уровни восприятия?

Не совсем правомерно, на мой взгляд, сравнение автоматного программирования с нисходящим проектированием, структурным подходом и ООП, которые изначально ориентированы не на моделирование предметной области, а на методы более эффективного написания кода для фон-неймановской архитектуры. Конечный же автомат в начале был предназначен для формального представления моделируемых явлений. Конкретно, логики управления. На следующем шаге он стал рассматриваться как система, трансформируемая в граф-схему, чтобы можно было ее реализовать как программу. Однако, и тогда процесс обработки, привязанный к переходу, детально не проговаривался. Модель КА может быть разработана совершенно независимо от способа написания программы. А вот методы ее кодирования могут быть различными. Можно использовать процедурное программирование, можно - ООП, можно интерпретировать таблицы. Суть автомата от этого не изменяется и никоим образом не зависит от стиля написания программы. Основная идея КА - это отразить более выпукло одну из сторон алгоритма: его логику управления. Это позволяет более эффективно разрабатывать программы в соответствующих предметных областях за счет сокрытия несущественных (на некотором этапе разработки) деталей, связанных с вычислениями. То есть, типичный прием по уменьшению размерности решаемой задачи. Сам пользуюсь таким же приемом, когда описываю распознаватель в синтаксическом анализаторе, являющийся иерархически порождаемым конечным автоматом. Семантика дописывается позднее.

Формализм перехода от КА к алгоритмическому его представлению кричит, что модель КА можно непосредственно использовать как программу, написанную на специализированном языке. Именно такой язык и представлен Вячеславом в виде библиотеки автоматной модели. Теперь не надо моделировать состояния и переходы переключателями или условными операторами. Достаточно их просто описать. Но возможности этой библиотеки пока весьма ограниченны. Состояния приходится описывать ограниченным числом символов. Нельзя напрямую построить иерархический автомат. Ограничены предикаты, определяющие условия перехода. Может эти возможности и не нужны?

Вместе с тем, существуют мощные языки, которые могут взять на себя эту роль. В UML - это диаграммы состояний, опирающиеся на теорию КА. Другим языком, который одновременно может восприниматься как алгоритмический и автоматный (что говорит о достаточно близком родстве этих двух моделей поведения), является графический R-язык (Технологический комплекс производства программ на машинах ЕС ЭВМ и БЭСМ-6/И.В. Вельбицкий и др. - М.: Статистика, 1980). Не смотря на древность, я считаю, что описанные там идеи являются весьма интересными, особенно с точки зрения автоматного программирования. На основе языка разработаны R-технология и R технологический комплекс. Сами диаграммы языка зафиксированы государственным стандартом. Графическое представление программы возможно даже на текстовом терминале (были соответствующие системы). Как пишется в предисловии, "эта технология сформировалась ... на базе фундаментальных исследований по теории автоматов и машин с интерпретацией языков высокого уровня". То, что графические символы R-языка легко интерпретировались как автоматные диаграммы, элементы алгоритма и даже как синтаксические диаграммы, сослужило в дальнейшем плохую службу R-технологии (на мой взгляд). Произошел перекос в сторону алгоритмов. Появились препроцессоры над языками Паскаль (R-Паскаль), Си (R-Си) и другими. А уникальная R-машина сошла на "нет".

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

Напоследок

Отразив свое мнение, я желаю Вячеславу Любченко дальнейших успехов по развитию библиотеки и ее использованию. Это как раз тот случай, когда конфликты с теорией мало отражаются на практике, потому что именно эта часть теории не нужна для успешной разработки и эксплуатации конечных автоматов. Однако, лично мне, очень хочется увидеть формальное описание используемого параллельного конечного автомата!

Вместе с тем я еще раз (с одной из предыдущих рассылок:) думаю, что для того, чтобы быть полновесной технологий КА и SWITCH не хватает мощного входного языка. Тогда, написав автоматную программу, пользователь не стал бы и вспоминать о поддерживающих ее библиотеках и методах формального преобразования в алгоритмическую модель. Вот бы прицепить R-язык или диаграммы состояний UML...А переводить всякий раз в C++ или что-то еще формальное высокоуровневое представление - это все равно что переписывать аналогичным образом программы, написанные на Perl'е.

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

С наилучшими пожеланиями!

А.Л.