[ 1
| 2
| 3
| Литература
| Приложение
| >>>
]
Отсюда можно скачать полный текст статьи в формате html (35 кб)
© Б.П. Кузнецов
boris@actor.ru
Федеральный научно-производственный центр
ГУП "НПО "Аврора""
Опубликована в журнале BYTE/Россия, 2000, №11
Статья предназначается программистам, работающим в среде C/C++, желающим ознакомиться с автоматным программированием, которое предполагает использование аппарата конечных автоматов. Данный подход требует определенных психологических усилий. Однако после его освоения возникает вопрос: как я мог программировать иначе? Автоматное программирование позволяет решать практически любые сложные циклические задачи с минимальными затратами на отладку. Приводятся абстрактный и конкретный примеры с листингом на языке программирования C, доступные, в том числе, начинающим программистам.
Наиболее важными вехами последних 15–20 лет в создании программ на языках высокого уровня являются методологии структурного [1] и объектно-ориентированного программирования [6]. Параллельно с ними сравнительно давно используется метод “автоматного” программирования. Этот метод назван так потому, что в основу проектирования программы закладывается алгоритм - конечный автомат в виде диаграммы состояний, или таблицы последовательных переходов и выходов [2].
Долгое время в русскоязычной литературе по программированию, за исключением руководств по проектированию компиляторов (например, [3]) и ряда мало известных публикаций по программной реализации конечных автоматов в логическом управлении (например, [4]), методология автоматного программирования задач разнообразного назначения замалчивалась.
Тем временем, на Западе эта методология активно развивалась, в первую очередь Харелом (например, [5]). Диаграммы состояний (как основа автоматного подхода к реализации различных задач, решаемых программным путем), вошли неотъемлемой частью в основные принципы объектно-ориентированного программирования [6]. Кроме того, такие диаграммы входят и в стандарт UML [7]. Но по этим книгам даже опытному программисту трудно перешагнуть некий психологический барьер для перехода на автоматное программирование.
Предпосылки написания статьи.
Теорию автоматов преподают не везде. В технических ВУЗах преподают эту теорию применительно к синтезу цифровой аппаратуры, но не применительно к программированию (Такие выводы сделаны моим коллегой Шалыто А.А. для ведущих Питерских ВУЗов). По специальностям, связанным с программированием, теория автоматов преподается либо абстрактно, либо применительно к задачам распознавания языковых конструкций, и только на основе табличной интерпретации. В итоге, выпускник современного ВУЗа не способен использовать конечные автоматы для широкого круга задач. Когда-то я работал руководителем очень большой группы программистов и пытался внедрить "в массы" использование автоматов в программах различного назначения. Ничего не вышло. Только один - двое могли усвоить лишь некоторые мои программы, но самостоятельно решать подобные задачи не могли. Лишь теперь набран необходимый материал для широкого распространения метода автоматного программирования в задачах циклической природы различного назначения.
Табличная программная интерпретация конечного автомата использовалась мною с 1975 по 1992 годы. То есть до тех пор, пока не появилась книга [12], где вместо таблицы предложено использовать оператор switch-case (Примерно в то же время, этот оператор предложил использовать наш сотрудник Кондратьев, что привело впоследствии к выходу в свет книги [9], посвященной задачам логического управления).
Основной недостаток использования таблицы состоит в том, что абсолютно все буквы входного алфавита необходимо вычислять до входа в таблицу, или до вычисления нового состояния и выхода по таблице. Хорошо, если буквам входного алфавита соответствуют сигналы от клавиатуры или синтаксические единицы распознаваемого текста. В противном случае следует вычислять для каждой упомянутой буквы соответствующее логическое выражение, да к тому же, предварять такое вычисление некоторыми действиями по модификации аргументов этих выражений. Это не всегда возможно совместить без порчи указанных аргументов. Помимо этого, для реализации действия на переходе требуется переключатель switch(идентификатор_действия). И такая программа начисто теряет смысл и наглядность. Поэтому она никому кроме автора не понятна.
Абсолютно нигде в современной литературе не указывается явно тот факт, что программа, реализующая граф (таблицу) переходов, должна быть циклической. Пока я этого не понял, никому ничего объяснить было нельзя. Рисуя граф переходов, мы с Вами заведомо полагаем, что подразумевается цикл, который на этом рисунке нигде не фигурирует. Поэтому большинству программистов и непонятно ничего
Излагаемый ниже подход поможет начинающим и опытным программистам снять эти психологические препоны и начать разработку циклических программ с составления графов переходов (диаграмм состояний).
Автору этой статьи повезло: в ВУЗе нам читали лекции по теории автоматов, в том числе методику перехода от блок-схем (граф-схем) алгоритмов к графу переходов конечного автомата. С тех пор я твердо усвоил: практически любой алгоритм, включающий цикл (циклы) реализуется конечным автоматом. Почти во всех своих программах мне было очень удобно использовать конечные автоматы, причем такие программы почти никогда не требовали отладки. В [8] автором предложены автоматы со скрытыми переходами, расширяющие область применения конечных автоматов в программировании. Далее до 1998 г. автор не публиковал свои результаты в области автоматного программирования, ошибочно полагая, что этот вопрос в программировании давно решен.
Однако, как показала публикация [9] моего коллеги, даже в такой, казалось бы заезженной области, программной реализации алгоритмов логического управления, использование автоматного подхода является в нашей державе нонсенсом. Что уж говорить об автоматной реализации обычных циклических программ!
[ 1
| 2
| 3
| Литература
| Приложение
| >>>
]
|