«Мгновения минувшего»

или мои встречи с интересными людьми в мире просвещения

Автоматное программирование

В книге [1] и в ряде других статьях проф. А.Шалыто (из СПб. ИТМО) с сотрудниками проводит мысль о том, что потребность в автоматном подходе к программированию появляется тогда и в той мере, в какой программа или её часть описывает систему со сложным поведением и сама является таковой. Под сложным поведением здесь подразумевается выработка отклика программы на вход с учётом предшествующих событий (а не с «единственно правильным» ответом на все случаи жизни). Так, уже большинство школьников знают, что на слова «пойдём со мной», сказанные родителями или сказанные незнакомой тётей из проходящего табора обычно надо откликаться по-разному.

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

Так вот, если программа (или её часть) обладает сложным поведением, то естественно будет и описать это поведение в виде некоторого автомата. Понятие «более естественно» при этом равнозначно «более понятно», «легче сопровождаемо и изменяемо», «более надёжно» и т.д.

Из тех же понятий и стремлений к естественности исходят и такие подходы в программировании, как

«структурное программирование» (с самого первого этапа программа рассматривается как единое целое, части которого со временем уточняются и прописываются более подробно, в т.ч. с выделением в отдельные подпрограммы и т.д. Иными словами «подход зерна», брошенного в землю и прорастающего вверх и вниз ветвями и корнями в нужных направлениях в отличие от попыток сначала создать по отдельности различные части, а потом с трудностями пытаться «сколотить» их в единое целое);

«объектно-ориентированное программирование» - учёт того, что для человека естественно и привычно мыслить «предметно». И, соответственно, очень многое из того, что описывается человеком и для него, тоже естественно обозначить как некие «предметы» - objects.

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

Заметим, что автоматное программирование при этом уже имеет свою более чем двадцатилетнюю историю, свои успехи, его подходы вошли в ряд промышленных стандартов программирования (в [1] приводится ссылка на один из стандартов по разработке ответственных программных систем в энергетике). С начала 2000-х годов курсы по автоматному программированию читаются в СПб. институте точной механики и оптики (ИТМО), широко известном в т.ч. и успехами своих студентов на международных олимпиадах по программированию. В сети создана сетевая страница в помощь осваивающим этот курс, выложены курсовые работы и задания по данному направлению и т.д.

На факультете управления и прикладной математики МФТИ, где курсы по теории формальных языков и их приложениям к построению компиляторов читаются уже более 40 лет, это направление программирования также не осталось без внимания, но пока это выразилось в большей степени в успехах сотрудников и выпускников института в области разработки соответствующих инструментальных приложений. Пожалуй, наиболее известной и применяемой из них стала разработка «Генератора проектов» [3]. В ВЦ РАН разработаны также такие инструментальные системы с существенным применением теории формальных языков как компилятор компиляторов «СУПЕР» [4], САПР широкого класса систем реального времени с периодически поступающей на вход информацией «СРВ-Конструктор» и др.

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

Итак, Автоматное программирование — это парадигма программирования, при использовании которой программа или её часть осмысливается как модель какого-либо формального автомата.

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

Определяющими для автоматного программирования являются следующие особенности:

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

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

Полностью выполнение кода в автоматном стиле представляет собой цикл (возможно, неявный) шагов автомата.

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

В привычном императивном стиле эта программа может выглядеть, например, так:

#include <stdio.h>
int main(void)
{
 int c;
 do {
 c = getchar();
 while(c == ' ')
 c = getchar();
 while(c != ' ' && c != '\n' && c != EOF) {
 putchar(c);
  c = getchar();
 }
 putchar('\n');
 while(c != '\n' && c != EOF)
 c = getchar();
 } while(c != EOF);
 return 0;
}

Программа в автоматном стиле

Ту же задачу можно решить, применив мышление в терминах конечных автоматов. Заметим, что разбор строки разделяется на три фазы: пропуск ведущих пробелов, печать слова и пропуск знаков конца строки. Назовём эти три фазы состояниями before, inside и after. Программа теперь может выглядеть, например, так:

 
#include <stdio.h>
int main(void)
{
 enum states {
 before, inside, after
 } state;
 int c;
 state = before;
 while((c = getchar()) != EOF) {
 switch(state) {
 case before:
 if(c == '\n') {
 putchar('\n');
 } else
 if(c != ' ') {
 putchar(c);
 state = inside;
 }
 break;
 case inside:
 switch(c) {
 case ' ': state = after; break;
 case '\n':
 putchar('\n');
 state = before;
 break;
 default: putchar(c);
 }
 break;
 case after:
 if(c == '\n') {
 putchar('\n');
 state = before;
 }
 }
 }
 return 0;
}

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

Строго соблюдать разделение кода на обработчики отдельных состояний, вообще говоря, не обязательно. Более того, в некоторых случаях само понятие состояния может складываться из значений нескольких переменных, так что учесть все возможные их комбинации окажется практически невозможно. В рассматриваемом примере можно сократить объём кода, если заметить, что действия, выполняемые по знаку «конец строки», от состояния не зависят. Программа, равнозначная предыдущей, но написанная с учётом такого замечания, будет выглядеть так:

#include <stdio.h>
int main(void)
{
 enum states {
 before, inside, after
 } state;
 int c;
 state = before;
 while((c = getchar()) != EOF) {
 if(c == '\n') {
 putchar('\n');
 state = before;
 } else
 switch(state) {
 case before:
 if(c != ' ') {
 putchar(c);
 state = inside;
 }
 break;
 case inside:
 if(c == ' ') {
 state = after;
 } else {
 putchar(c);
 }
 break;
 case after:
 break;
 }
 }
 return 0;
}
 

Выделение шага автомата в отдельную функцию

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

#include <stdio.h>
enum states { before, inside, after };
void step(enum states *state, int c)
{
 if(c == '\n') {
 putchar('\n');
 *state = before;
 } else
 switch(*state) {
 case before:
 if(c != ' ') {
 putchar(c);
 *state = inside;
 }
 break;
 case inside:
 if(c == ' ') {
 *state = after;
 } else {
  putchar(c);
 }
 break;
 case after:
 break;
 }
} 
int main(void)
{
 int c;
 enum states state = before;
 while((c = getchar()) != EOF) {
 step(&state, c);
 }
 return 0;
}

Этот пример наглядно показывает основное свойство, благодаря которому код можно считать представленным в стиле автоматного программирования:

1. отдельные шаги автомата выполняются в неперекрывающиеся временные периоды
2. единственным средством передачи информации между шагами является явно определённое состояние (в данном случае переменная state)

Источники

1. Н. Поликарпова, А. Шалыто. Автоматное программирование (учеб. пос.). СПб.: Питер, 2010 г.

2. Статья «Автоматное программирование» из Википедии — свободной энциклопедии.

3. Подробнее о разработке «Генератор проектов» см. страницу www.genprj.ru.

4. Серебряков В.А. и др. Теория и реализация языков программирования. 2-е изд. М.: МЗ-Пресс, 2006.

Наверх