учебники, программирование, основы, введение в,

 

Автоматное программирование: от таблицы к программе

Анализ состояния дел
Построение таблиц заканчивает этап спецификации нашей программы. Таблицы -другое формализованное представление рисунков. Как всегда, разные формализмы отличаются по практической направленности. Граф в некоторых случаях может быть автоматизированно преобразован в прототип программы (попытайтесь сами проделать это со спецификацией на языке UML), но получающиеся программы всегда требуют ручной доработки. Табличное же представление допустимо рассматривать как мини-язык программирования. Для него возможно построение транслятора или интерпретатора, которые в частных типах таблиц давно уже используются (их широкому применению мешает привязка к конкретным предметным областям и приложениям, поскольку профессиональные системные программисты свысока смотрели на столь простые задачи).
Обратимся к семантике вычислений на языке таблиц. Рассматривается контекст некоторой программы на языке C++ (или на другом языке традиционного типа). В этом контексте определяется значение переменной Entry (множество ее значений совпадает с множеством наименований состояний), далее выполняются следующие действия:

  1. Выбрать вход в таблицу, соответствующий значению Entry (текущее состояние).
  2. Если Условие отсутствует, то перейти к шагу 4.
  3. Вычислить совместно все Условия срабатывания переходов (клетки второй колонки для данного входа):
  •  
    • Если среди результатов есть значения True, то выбрать одну из строк, Условие которой истинно, и перейти к шагу 4 для выбранной строки;
    • Если все значения Условий ложны и есть строка failure, то выбрать эту строку и перейти к шагу 4 для нее;
    • Если все значения Условий ложны и нет строки failure, то завершить вычисления.
  1. Выполнить Действие.
  2. В качестве значения переменной Entry установить наименование состояния-преемника (из четвертой колонки таблицы). Перейти к шагу 1.

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

  • start - указание действий, которые выполняются до основных действий и проверок условий перехода (здесь таким действием является чтение очередного символа из файла);
  • finish-указание действий, которые выполняются после основных действий и проверок, но до перехода.

Можно также определять локальные данные для состояний (в примере такие данные определены только для начального состояния), но это должно быть согласовано с правилами локализации имен языка программирования и с общим стилем, в котором написана программа. Заметим, что локальные данные всех состояний конечного автомата должны быть помещены в общий контекст, а приписывание их к конкретным состояниям является ограничением видимости, подобным тому, которое используется в модульном программировании (если Вы уже программировали на Object Pascal Delphi, Java либо Oberon, то знакомы с модульностью). Это прагматически следует из того положения, что работа теоретического конечного автомата не требует привлечения памяти.
Озаботимся теперь тем, как запрограммировать требуемые действия, когда нет возможности воспользоваться языком таблиц непосредственно. С таблицами, представляющими таблицу переходов, можно сделать следующее.

  1. Оттранслировать вручную.
  2. Отдать препроцессору для превращения в нормальнуюпрограмму.
  3. Использовать интерпретатор.

Рассмотрим последовательно эти три возможности.

http://localhost:3232/img/empty.gifРучная трансляция таблиц переходов

В решениях 1 и 2 возникает следующий вопрос: во что транслировать таблицу переходов? Вариантов множество, ниже рассматриваются лишь некоторые из них.
Вариант 1.Можно считать St1 и St2 функциями, реализующими все действия состояний.При использовании верно подобранных стиля и инструментальных средств этот подход дает отличный результат. Рассмотрим, в частности, как может быть реализована наша задача на языке Рефал.
Листинг 10.2.1. Длины слов: рефал
Эти программы настолько коротки и естественны, что практически не требуют комментариев. Единственная новая возможность, использованная здесь, в принципе излишняя, но делает программу красивее. Конструкции <Letters>: e.A s.1 e.B и e.2, <Lenw e.2>: являются, соответственно, вложенной проверкой условия на выражении, порождаемом вызовом <Letters>, и вызовом определяемой дальше анонимной функции на выражении, получившемся после запятой. Стандартная функция <Lenw e.2> добавляет первым символом к выражениюего длину (количество термов в нем). При проверке и при вычислении вспомогательной функции переменные, уже получившие значения, не изменяются.
Таким образом, структура управления на переходах хорошо согласуется со структурой управления в конкретизационном варианте сентенциального программирования. Вновь отметим, что, хотя некоторые описания функций кажутся рекурсивными, рекурсий нет, так как исходный вызов завершается до активизации порожденных им вызовов. Каждый шаг конкретизации начинается с проверки условий, поэтому действия естественно сопоставить именно переходам.
В данном случае удалось добиться столь красивого результата потому, что действия также полностью соответствовали той области, где применение языка Рефал наиболее выигрышно. Но даже в таком простом случае после минимальной ручной доработки программа стала еще лучше.
Формально функциональное представление состояний возможно как на языке традиционного типа, так и на LISP и Prolog. Но в этом случае мы проигрываем в выразительности и естественности программы, а также еще по одному важному критерию. Во всех этих случаях то, что выглядит как рекурсия, действительно ею является, а рекурсия в данном случае лишь мешает.
Вариант 2. Считать St1, St2, St3 значениями некоторого перечислимого типа State.
Листинг 10.2.2. Длины слов: явный цикл обработки потока
Хороша только в том случае, если ограничиться автоматными моделями в достаточно узком смысле. Программа точно соответствует табличному представлению автомата, почти все дублирования действий, связанные с таким представлением, остались. Возникает некоторая неудовлетворенность тем, что появилось лишнее действие: выбор выполняемого фрагмента по значению переменной State. Если ограничиться управляющими средствами методологии структурного программирования, то это - наилучший выход. Попытки применить циклы внутри фрагментов, помеченных как case St1: и case St2:, приводят лишь к уменьшению наглядности по сравнению с табличным представлением.
Есть еще один вопрос, который требуется решить при таком подходе, - выбор типа результата функций-состояний и способа возвращения результата. Естественный результат такой функции - это новое состояние, в которое попадает автомат при переходе. Он может быть представлен, например, глобальной переменной (такой как State в, которой присваивается новое значение при выполнении функции-состояния). Но предпочтительнее не трогать State в каждой из функций, а предоставить задачу фактического изменения состояния общему их контексту. Наиболее правильной реализацией состояний при таком подходе являются функции, которые вырабатывают в качестве результата значение типа, перечисляющего все состояния.
Следующая почти буквально реализует данную идею. В отличие от, тип States содержит четыре значения: St1, St2, St3 и Exit. Последнему из них не соответствует ни одна функция из-за тривиальности переходов и действий в данном состоянии.
Листинг 10.2.3. Длины слов: использование процедур для описания состояний.
Следует обратить внимание на то, что программа наглядна, строго соответствует таблице автомата. Можно сказать, что граф автомата определяет распределенную по состояниям схему потоковой обработки. На самом деле она гораздо лучше подходит модели вычислений в состояниях, а не на переходах. Более того, эта программа при небольшом увеличении числа состояний быстро теряет наглядность, если программировать на переходах, поскольку следующие состояния упрятаны внутри соответствующих процедур, но сохранит ее, если программировать в состояниях.
Таким образом, мы пришли к тому, что в рамках стандартной методики программирования все решения имеют некоторые недостатки. Надо искать другое, и здесь стоит вспомнить пословицу (на самом деле отражающую один из приемов творческого мышления): "Новое - хорошо забытое старое". Поищем решение среди того, что забраковано стандартными методиками.
Проанализировав граф автомата или таблицу, можно заметить, что в данном примере, наряду с циклом потоковой обработки, имеется еще один цикл: передача управления между состояниями. Это причина, из-за которой в двух предыдущих вариантах появились присваивание переменной State значения и выбор выполняемого фрагмента по этому значению.
Особенность последовательностей действий
State = <значение>;
switch ( State )
которая выполняется всякий раз в конце действий, ассоциированных с состояниями (точнее - реализаций действий в программах), в том, что в каждой точке программы, где встречается данное присваивание, можно точно указать результат динамически следующего оператора переключения, причем эта информация не зависит от обрабатываемого потока и может быть определена до вычислений статически.
А нельзя ли использовать это явно для организации управления конечным автоматом? Можно, это демонстрирует четвертый вариант решения обсуждаемой задачи.
Вариант 4. Матрица переходов и вектор-функций, соответствующих состояниям
Листинг 10.2.4. Длины слов: массив функций и переходов
Это решение неплохое, но оно годится лишь для вычислений в состояниях. Фактически оно резко расходится с канонами структурного программирования, где даже не предполагалось переключение между функциями внутри массива функций. Оно несколько утяжелено деталями, связанными с отработкой особых состояний ввода входного потока. Зато повторяющиеся действия не дублируются.
Рассмотрим последний вариант.
Вариант 5. Использование статической информации о разветвлениях вычислений.
Листинг 10.2.5. Длины слов: состояния - метки в программе.
В данном варианте исчезает необходимость вычисляемого перехода (результат внедрения статической информации в текст программы), и, как следствие, становятся избыточными описания типа States и переменной State этого типа. В программе появляются операторы безусловного перехода, из-за этого структура управления программы полностью расходится с канонами структурного программирования, что дает повод догматически мыслящим программистам и теоретикам подвергать критике такой вариант программы. Но в данном случае отступление от канонов структурного программирования полностью оправдано, поскольку за счет специального расположения фрагментов текста вся программа оказалась похожа на таблицу конечного автомата, а структура передач управления копирует граф конечного автомата. Более того, такое представление нейтрально по отношению к моделям Мура и Мили. Таким образом, лишь после полного отхода от канонов структурности программа стала адекватна своей спецификации.

http://localhost:3232/img/empty.gifАвтоматизированное преобразование таблиц переходов

Если автоматизировать работу с табличным представлением, то прежде всего требуется строго определить структуру данных, представляющих таблицу переходов. Способ задания таблицы зависит от стратегии дальнейшей обработки. В частности, если вручную строится текстовое представление таблицы, которое в дальнейшем преобразуется к исполняемому виду, то приемлемо, например, такое представление.
Листинг 10.3.1. Программа в виде размеченного текста.
Здесь <_i>, i = 1, . . . , 5 обозначают позиции таблицы. Эти сочетания символов, нигде в обычной программе не встречающиеся, легко могут распознаваться препроцессором. Размещаемые между ними последовательности символов разносятся по соответствующим полям нужной структуры, которая, в зависимости от выбранной стратегии, интерпретируется либо транслируется. С помощью этих сочетаний осуществляется разметка текста, которая дает возможность распознавать и осмысливать его фрагменты. Стоит обратить внимание на то, что за счет специального взаимного расположения символов в данном тексте представляемая им таблица автомата вполне обозрима. Если нет более подходящего представления, то данную структуру можно рекомендовать для ввода.
Однако непосредственная интерпретация универсального текстового размеченного представления довольно затруднительна. Предпочтительнее, чтобы единицами интерпретации были бы сами поля таблицы. Вообще, этому противоречит наличие в таблице полей, значения которых - фрагменты исполняемого кода на языке программирования (такая запись удобна для человека, так как для заполнения таблицы не приходится прибегать ни к каким дополнительным соглашениям). На самом деле противоречие возникает только для поля действий, поскольку последовательности символов между <_2> и <_3> имеют ясно выраженную семантику: это проверка условия. Если всегда рассматривать условия как проверку того, чему равен входной символ, то вполне понятны, легко задаются, распознаются и интерпретируются специальные обозначения: перечисления значений, их диапазоны и т.д. Трактовка этих обозначений не вызывает осложнений, а потому подобные приемы кодирования применяются довольно часто.
Если говорить о полях действий, то их представление для большинства языков программирования плохо разработано. Данное обстоятельство препятствует использованию автоматного программирования: кодирование действий усложняет обработку. Но если в языке можно задавать подпрограммы как данные, то описание структуры таблицы, которое будет согласовано с дальнейшей трансляцией или интерпретацией, возможно, в частности, в языках функционального программирования (семейство LISP и ML) и в языке Prolog. Но функциональное и сентенциальное программирование хорошо интерпретируют лишь частные случаи таблиц.
Пусть тип T_StructTableLine описывает структуру одной строки таблицы, а вся таблица представлена в виде массива Table таких структур. Пусть далее iSt - переменная, используемая для индексирования массива Table, некоторые из ее значений представляют состояния конечного автомата (но не все, а только те, к которым определен переход!). Наконец, пусть
int handler ( int );
-обработчик строки (ее интерпретатор или транслятор), <понимающий> структуру T_StructTableLine, специфицируемый как функция, при выполнении которой должно быть определено очередное значение iSt. Значение iSt, не указывающее ни на какую строку таблицы, служит сигналом для завершения обработки (при желании можно заняться кодированием того, как завершилась обработка с помощью задания различных таких значений).
Тогда схема программы, которая оперирует с таблицей с помощью функции handler, может быть задана следующим циклом:
iSt = 0;
do     {
iSt = handler ( iSt );
}
while ( OUTSIDE ( iSt ) );

Понятно, что выбор массива в качестве представления автомата непринципиален. Допустимо, а иногда и предпочтительнее, работать со списком строк. Также непринципиален способ вычисления предиката OUTSIDE, проверяющего условие окончания цикла, хотя он и зависит от выбранного представления автомата. Возможность не рассматривать явно имена состояний, напротив, принципиальна: тот факт, что строки таблицы сгруппированы вокруг (поименованных) состояний, ничего не значит ни для обработки, ни для интерпретации, поскольку у конечного автомата следующее состояние всегда определяется явно.
Логика функции handler, интерпретирующей таблицу, проста. Для правильной таблицы, не содержащей состояний, в которых возможны неопределенные переходы, она строится следующим образом:

  1. Извлечь значение Table[iSt];
  2. Активизировать вычисление условия обрабатываемой строки таблицы;
  3. Если условие истинно, то
    • активизировать подпрограмму действий;
    • читать очередной символ;
    • завершить handler со значением, извлекаемым из поля следующего состояния;
  4. Если условие ложно, то
    • iSt++;
    • Перейти к 1;

Осталось предусмотреть детали для заключительных состояний, но это сделать уже легко.
Таким образом, нужно научиться описывать структуру строки таблицы. На языке C++/С# эта задача может решаться довольно просто:
struct T_StructTableLine
{                           
// поле для имени состояния избыточно
int (*condition)();     // поле условия
void (*action)();       // поле действия
int ref;               
// поле перехода: индекс строки таблицы,
// которая будет обрабатываться следующей,
// или признак завершения процесса
}

Сама таблица описывается следующим образом:
T_StructTableLine Table[]
или
T_StructTableLine Table [Размер таблицы]
если значения строк задаются вне этого описания.
Однако сразу же видно ограничивающее соглашение, которое пришлось принять в связи с особенностями языка реализации: все условия и все действия оформлены как функции, тогда как задача, по своей сути, этого не требует. Более того, отделенное от таблицы описание функций, предписываемое языком С++/C#, резко снижает выразительность представления:
int Cond_St1_1() - условие в Table[1]
и
void Act_St1_1() - действие в Table[1] (строка 1 состояния St1);
int Cond_St1_2() - условие в Table[2]
и
void Act_St1_2() - действие в Table[2] (строка 2 состояния St1);
и т. д.
Еще один неприятный момент данного представления - невозможность единообразно с действиями представить их общий контекст (нулевая строка таблицы), а поскольку инициализацию естественно рассматривать как задание предварительных действий, готовящих собственно обработку, то ее предпочтительнее соединять с контекстом, а не с функциями, реализующими проверки и действия.
Последний недостаток неустраним ни в каком языке, если проверки и действия трактовать как процедуры, которые работают в общем контексте, задаваемом в заголовке таблицы. Так что лучше сразу отказаться от описания этого контекста в рамках таблицы (задание инициализации в ней возможно). Что касается первого недостатка, то он носит почти синтаксический характер, и если бы можно было задавать тела процедур как значения полей структур, то наглядность представления можно было бы сохранить. В языковом оформлении, похожем на С/С++/C#, это выглядело бы как следующее присваивание значения Table в качестве инициализации.
Table[]= {
{{return true;}, /* инициализация */, 1},
/*St1*/{{return 'a'<=symbol &&
symbol <= 'z';}, {printf ("%c", symbol);
cnt = 1;}, 4},
{{return symbol != '\n';},
/* Так как нужно печатать только слова,
действия не заполняются */,
1},
{{return true},
/* Переход не требует чтения,
symbol == '\n' не нужно читать */, 0},
/*St2*/{{return 'a'<=symbol &&
symbol <= 'z';}, {printf ("%c", symbol);
cnt++;}, 4},
{{return symbol!='\n';},
{printf ("-%i\n",cnt);},
1},
{{return true },
{printf ("- %i\n",cnt);}, 0}
};

Листинг 10.3.2.
Но для С/С++/C#, а также для других языков, не ориентированных на работу с таблицами, говорить о естественности представления не приходится. По-видимому, наиболее разумно строить автоматический преобразователь (типа препроцессора, но не путать этот термин с С!), который составляет текст программы по таблице. В этом случае снимается много проблем:

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

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

  • Когда читать? Поскольку прочитанный символ используется после его распознавания, естественно "не терять" его, пока выполняется действие. Следовательно, читать очередной символ целесообразно после отработки действия.
  • Как поступать в начале процесса: должен ли быть прочитан символ перед первым вызовом функции handler? Понятно, что чтение символов является частью функциональности этой функции. Если в ней реализовать чтение до вызовов условия и действия, то это противоречит предыдущему соглашению, а противоположное решение делает нестандартным начало процесса. В предлагаемой программе принято решение об особой обработке нулевой строки. Поскольку, являясь инициализацией, она действительно особая, это соответствует сделанному соглашению.
  • Как поступать в конце процесса? Чтение заключительного символа ('\n') должно прекращать возможные попытки последующего обращения к чтению. Следовательно, необходимо позаботиться о завершающих переходах. В предлагаемой программе принято решение о завершающем переходе к нулевой строке, которая, согласно предыдущему, является нестандартной.

Отметим, что данные соглашения не являются абсолютными, и поставленные вопросы нуждаются в решении всякий раз, когда реализуется переход от табличного представления к программе. В предыдущем параграфе Вы уже видели, как практически в каждой реализации метод чтения слегка изменялся.
С учетом сделанных замечаний программа, решающая задачу подсчета длин строк методом интерпретации таблицы, может быть записана следующим образом.
Листинг 10.3.3. Длины слов: интерпретатор конечного автомата.
Обсуждение решения
Как уже отмечалось, фрагменты, описывающие условия и действия в таблице переходов и реализованные как процедурные вставки, с точки зрения препроцессора (не препроцессора системы программирования, а специального преобразователя, генерирующего представление таблицы для интерпретации), являются нераспознаваемыми данными, которые он просто пропускает без изменений для обработки компилятором. Интерпретатор же, наоборот, не в силах сам исполнять процедуры, а потому трактует ссылки на них (в соответствующих полях) как данные. Таким образом, условия и действия в таблице двойственны: они являются одновременно и данными, и программными фрагментами. Автоматический преобразователь таблицы, не понимая языка таких двойственных данных, пытается, тем не менее, их объединить с обычными данными (в рассматриваемом случае это индексы строк переходов) в одной структуре.
На первый взгляд кажется, что ситуация существенно упростилась бы в языке, в котором есть возможность воспринимать данные как выполнимые фрагменты. Пример такого рода - команда <Вычислить строку>. Эта команда давала бы возможность интерпретатору понимать программы-данные, не оставляя их нераспознанными. Подобная команда порою встречается в языках скриптов, ориентированных на интерпретацию. А в языке LISP, в котором структуры данных и программы просто совпадают, указанная двойственность не возникает. Но по опыту известно, что столь общее решение чревато столь же общими и вездесущими неприятностями, и нужно искать частный его вариант, адекватный данной задаче.
Метод решения задач с помощью построения таблиц и графов состояний и переходов часто удобен для обработки потоков данных. Решения стоит оценить количественно и качественно: сколько требуется состояний и действий, как лучше получается в данном случае (в состояниях или на переходах). Может оказаться, что понадобятся средства, выходящие за рамки описанных методов. Это допустимо, следует только осознавать грань между использованием конечного автомата и применением другого подходящего метода, а также четко разделять внутри программы возможности, относящиеся к разным стилям программирования.
Подведем итоги
Таблица и граф - два теоретически эквивалентных (но практически разных) представления. Каждое из них имеет свои достоинства и недостатки (на графе информация беднее, но обозримость может быть лучше). Одна из этих спецификаций чаще всего делает ненужной другую.
Таблицы и графы гораздо лучше самой программы с точки зрения модифицируемости и преобразований.
Таким образом, табличное и графовое представления автомата являются спецификациями №1, о которых нужно думать в первую очередь, когда составляется автоматная программа.
Главный недостаток табличных и графовых методов представления автоматов в том, что их приходится дополнительно преобразовывать в программу. А в дальнейшем возникает соблазн модифицировать непосредственно программу, и спецификация перестает быть адекватной программе.
В связи с этим возникает вопрос об улучшении поддержки методов табличного и графового представления автоматных программ.


http://localhost:3232/img/empty.gifhttp://localhost:3232/img/empty.gif

 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика