УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Автоматное проектирование программ. Алгоритмизация и программирование задач логического управления

(c) А.А.Шалыто

1. Классические языки логического управления

1.1.Булевы функции, таблицы истинности и таблицы решений.

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

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

1.2.Булевы формулы и другие аналитические формы представления алгоритмов логического управления.

Аналитической формой представления булевых функций являются булевы формулы и системы булевых формул, которые позволяют описывать как комбинационные схемы, так и автоматы с памятью большой размерности. Системы булевых формул могут быть изоморфно реализованы лестничными или функциональными схемами. Иногда используются также и другие аналитические формы представления булевых функций, например пороговые [6], спектральные [7] или арифметические [8,9].

Основным ограничением на применение систем булевых формул для автоматов с памятью является их низкая наглядность.

1.3.Функциональные схемы.

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

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

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

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

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

1.4.Временные диаграммы и циклограммы.

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

1.5.Схемы алгоритмов.

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

К недостаткам схем алгоритмов относятся:

• применение в литературе двух видов автоматных схем алгоритмов, первый из которых характеризуется тем, что в схемах этого вида по умолчанию считают, что ввод входных переменных осуществляется в каждой условной вершине, а вывод значений выходных переменных - в каждой операторной вершине [11]. В схемах алгоритмов второго вида считают, что ввод входных переменных осуществляется в начале тела схемы алгоритмов, а вывод значений выходных переменных - в его конце. Использование в явном виде операторов "Ввод" и "Вывод" в таких схемах позволяет различать указанные разновидности схем;
• отсутствие требований к тому, что должна отражать схема алгоритма, а именно: алгоритм управления (схема алгоритма с внутренними обратными связями, но без внутренних переменных); алгоритм реализации алгоритма управления (схема алгоритма без внутренних обратных связей); алгоритм, учитывающий свойства управляющих конструкций применяемого языка программирования (схема алгоритма, линеаризованная и структурированная, возможно, специальным образом); алгоритм выполнения программы (схема алгоритма, в которой упоминаются компоненты процессора, например, аккумулятор);
• отсутствие требований к их организации (за исключением структурирования), обеспечивающих простоту "чтения";
• необходимость в общем случае их многократных преобразований с целью обеспечения возможности одновременного решения нескольких задач в одном управляющем вычислительном устройстве (расцикливание) и учета свойств управляющих конструкций языка программирования (например, линеаризация и структурирование);
• наличие внутренних (промежуточных) переменных, отсутствующих в "словесном алгоритме" логического управления, резко затрудняющих возможность чтения схем алгоритмов другими, отличными от Разработчика, Специалистами, и в особенности Заказчиком;
• применение обычно большого числа битовых внутренних переменных, каждую из которых приходится не только устанавливать, но и принудительно сбрасывать. Эти переменные характеризуют лишь отдельные компоненты состояний автомата, а его состояния в целом обычно не определяются. Использование этих переменных является естественным при аппаратной реализации алгоритмов, но при реализации алгоритмов с помощью языков программирования, позволяющих обрабатывать многозначные переменные, применение битовых внутренних переменных нецелесообразно;
• наличие флагов и умолчаний значений внутренних и выходных переменных в операторных вершинах, которые затрудняют чтение схем алгоритмов ввиду необходимости помнить предысторию, особенно в тех случаях, когда значения переменных в этих вершинах изменяются в зависимости от путей, по которым можно "попасть" в рассматриваемую вершину;
• проверка в условных вершинах значений обычно только одиночных двоичных переменных, что приводит к громоздкости схем алгоритмов;
• связь операторных вершин через условные вершины, затрудняющая внесение изменений, так как модификация условий перехода между двумя операторными вершинами влияет на условия переходов в другие такие вершины.

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

Остановимся более подробно на использовании умолчаний значений выходных переменных в операторных вершинах автоматных схем алгоритмов.

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

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

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

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

Рассмотренный язык используется фирмой "Oпто" (США) для программирования логических контроллеров "Mistic" [12]. Применение схем алгоритмов в форме диаграмм Несси-Шнейдермана [13] практически не устраняет указанных недостатков.

1.6.Логические схемы алгоритмов.

Логические схемы алгоритмов, предложенные А.А. Ляпуновым [14], являются строчной формой записи линеаризованных схем алгоритмов и образованы буквами (которые соответствуют условным, безусловным и операторным вершинам линеаризованных схем алгоритмов) и пронумерованными стрелками, указывающими переходы, осуществляемые при не выполнении условий.

Логические схемы алгоритмов обеспечивают компактность описания, но они весьма ненаглядны и трудно читаются.