Автоматные схемы программ

Историческая ремарка к статье

©1983 Вячеслав Любченко

Тот, кто знает и не знает, что он не знает, - глупец, избегай его. Тот, кто не знает и знает, что он не знает, может научиться, научи его. Тот, кто знает и не знает, что он знает, спит, разбуди его. Тот, кто знает и знает, что он знает, - пророк, учись у него. Древнее персидское стихотворение (по кн. Э.Хамби. Программирование таблиц решений).

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

Целью данной работы является описание формальной модели программ, обладающей преимуществами, присущими ТР, и применимой для описания алгоритмов любой структуры. Предложенная модель принадлежит к классу автоматных моделей. Теоретической базой для автоматного подхода к заданию алгоритмов является теория конечных автоматов и теория вычислимых функций по Тьюрингу [3].

В общем случае программа может быть представлена как конечное множество операторов над памятью, для которых задан порядок выполнения. Формальная математическая модель программы тогда может быть представлена схемой программы, определяемой как тройка S = (M, A, G) [4]. Здесь M - множество ячеек памяти, A - множество операторов программы, которые в свою очередь могут быть программами, G - управление.

Во множестве A выделим операторы логического типа (предикаты) x_i X и операторы функционального типа (действия) y_i Y, т.е. A = (X,Y), где X = {x_i}, Y = {y_i} и X Y = 0, |A| = |X| + |Y|. Каждому оператору из A ставится в соответствие множество входных ячеек памяти D_a M. Множество выходных ячеек R_a M определено только для операторов функционального типа y_i Y. Значением логического оператора x_i X является константа 0, если вычисленное им условие ложно, и 1, если истинно. Таким образом, с помощью действий осуществляются необходимые преобразования над множеством ячеек памяти, а с помощью предикатов анализируются возникающие при этом ситуации.

Работу управления по анализу ситуаций и управлению действиями удобно описывать в терминах некоторой абстрактной машины с конечным числом состояний. Формальной математической моделью такой машины является модель конечного автомата [5]. Абстрактный конечный автомат - это кортеж или вектор S = (Q, Z, W, , , q₀), у которого

1. Q = {q₀, q₁, ... q_k} - множество состояний;
2. Z = { z₀, z₁, ... z_k } - множество входных сигнале;
3. W = { w₀, w₁, ... w_l } - множество выходных сигналов;
4. : Q Z Q - функция переходов;
5. : Q Z Y - функция выходов;
6. q0 - начальное состояние.

Если функции и заданы на всем множестве Q Z, то автомат называется полностью определенным, в противном случае - частичным. В зависимости от вида функций и выделяют два основных типа (рода) автоматов: автоматы Мили и автоматы Мура. Закон функционирования используемой далее модели автомата Мили задается уравнениями:

q(t+1) = (q(t), z(t)),
w(t) = (q(t), z(t)).

Для более подробного описания объекта моделирования (программы) необходимо перейти от абстрактного автомата S к структурному автомату G [5]. В структурном автомате G учитывается структура входных и выходных сигналов, определяемых уже как входные и выходные наборы автомата.

Структура наборов зависит от множества операторов из А. Входным наборам соответствуют ситуации программы, а выходные наборы определяют последовательность выполнения действий. Причем, если значение предиката x_i в конкретной ситуации должно быть истинным, то это обозначается как x_i, в противном случае - ~x_i.

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

Поскольку целью работы является демонстрация преимущества автоматного подхода по сравнению с ТР, примеры, приведенные далее, взяты из опубликованных работ по таблицам решений.

Рассмотрим пример, взятый из [6]. Основным результатом работы [6] является доказательство существования для любой блок-схемы программы эмулирующей ее повторновходимой таблицей решений. Для достижения поставленной цели в ТР вводится специальная переменная , принимающая целые положительные значения. Блок-схема программы примера из [6] представлена на рис. 2,

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

Таким образом, на примере из [6] можно видеть, что попытки обобщить ТР приводят лишь к табличной форме задания конечных автоматов. Дополнительным фактом, говорящим в пользу этого утверждения, является существование метода перехода от граф-схем алгоритмов (ГСА) к автоматному описанию дискретных устройств, предложенного в [5]. Переменной в этом случае соответствуют отметки ГСА.

Рассмотрим пример из [7]. Здесь поставлена следующая задача: разработать алгоритм обработки результатов слежения за значением некоторого технологического параметра. Исходными данными являются значения параметра r, текущее значение времени t, значение верхнего r^в и нижнего r^н пределов.

Алгоритм в виде ТР представлен табл. 2, где С₁, С₂, ... С₆ - предикаты, A₁, A₂, ... A₉ - действия и С₁ - r > r^в; С₁ - r < r^н; С₃ - r > r^э; С₄ - r < r^э; С₅ - признак выхода параметра за верхний предел, С₆ - признак выхода значения параметра за нижний предел; A₁ - t₂ := t; A₂ - оператор "Выдать запись"; A₄ - r^э := r; A₅ - C₅ := 0; A₆ - C₆ := 0; A₇ - C₅ := 1; A₈ - C₆ := 0; A₉ - оператор "Перейти к следующему измерению".

На рис. 3 и в табл. 3 представлены граф и таблица переходов автомата, реализующего ту же задачу. В результате множество операторов программы A = (X,Y), где X = { C₁, C₂, C₃, C₄}, Y = { A₁, A₂, A₃, A₄} сократилось с 15 до 8, количество решений (дуг) также уменьшилось Переменным C₅, C₆ из ТР стали соответствовать состояния a₂,a₃ автомата.

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

Литература

1. Иодан Э. Структурное проектирование и конструирование программ. - М.: Мир, 1979 - 415 с.

2. Фрайтаг Г., Годе В., Якоби X. и др. Введение в технику работы с таблицами решений. - М.: Энергия, 1979 -88 с.

3. Трахтенброт А.Б. Алгоритмы и вычислительные автоматы. - М.: Сов. радио, 1974-200 с.

4. Карп P.M., Миллер Р.Е. Параллельные схемы программ. - В кн. Кибернетический сборник (новая сер.). М.: Мир, 1975, вып. 13, с. 5-61.

5. Баранов С.И. Синтез микропрограммных автоматов. - Л.: Энергия, 1979 -232 с.

6. Lew A. On the emulation of flowcharts by decision tables/ - Commun. ACM, 1982, 25, №12, p. 895-905, Серия Э.И. "Вычислительная техника". - М.: ВИНИТИ, 1983, №32, с. 15-19.

7. Букин В.В., Жуковский В.Г. Об использовании формализованных спецификаций технологических программ систем управления. - УСиМ, 1983, №3, с. 43-47.