Технические на уки
Информатика, вычислительная техника и управление
Системный анализ, управление и обработка информации
х
Чугреева Е.Е.
Алиев Р. С., кандидат технических наук, доцент
(Московский государственный технический университет «Станкин»)
НОТАЦИЯ ^-АВТОМАТОВ КАК СПОСОБ ПРЕДСТАВЛЕНИЯ НЕЛИНЕЙНЫХ АЛГОРИТМОВ
В статье решается актуальная задача разработки графического представления термов X-исчисления; проводится сравнительный анализ традиционной формы записи X-термов и соответствующих характеристик абстрактных автоматов; вводится понятие X-автомата и предлагается новая нотация с помощью изображения этих автоматов.
X -AUTOMATON NOTATION AS A WAY OF NONLINEAR ALGORITHM REPRESENTATION
The article deals with development of X-terms graphical description. Comparative analysis of X-terms traditional notation and abstract automation characteristics is realized. X-automaton defmition and the way of X-terms representation with X-automaton graphical description are done in this paper.
Значительный интерес к теории и инструментарию функционального программирования, проявляемый в настоящее время как академическим сообществом, так и индустрией ИТ, объясняется естественным поиском средств борьбы со сложностью. Брукс утверждал: «Сложность программного обеспечения является существенным, а не случайным обра-зом»[2]. В крупных системах из-за большого количества возможных состояний возникает так называемый комбинаторный взрыв - эффект резкого экспоненциального роста временной сложности алгоритма. Концепция Х-исчисления предполагает отказ от учёта состояния как вычислительной системы в целом, так и отдельных элементов систем. Возникнув в основаниях математики, теория Х-исчисления была построена как теория вычислений с естественной бестиповой операционной семантикой, чтобы подчеркнуть вычислительные аспекты функций [1].
Для описания Х-выражений используется Х-нотация, содержащая лингвистические средства описания изучаемых функций. Основной интерес представляет изучение этих объектов с применением всевозможных математических средств, выражаемых в виде Х-термов, которые составляют множество Л и строятся из переменных с помощью операций аппликации и абстракции. Предложения Х-теории представляют собой равенства между Х-термами, при этом Х-термы являются словами в следующем алфавите: x, y... - переменные, X - абстрактор, (,) - скобки [1].
Аппликация (применение функции к аргументу) — исходная операция системы X. Функция / в применении к аргументу а обозначается как/а.
Сами же функции строятся с помощью операции, называемой абстракцией. В общем случае она выражается в виде Хх. у, где X - обозначение абстракции, х - свободный аргумент функции, у - функция от аргумента x.
Приведём примеры некоторых Х-термов:
1) x x;
2) Хх.х x;
3) Хх у.у х (=Хх(Ху(у х))).
Многие важные понятия программирования (в первую очередь те из них, которые связаны с передачей параметров) допускают точное описание на языке Х-исчисления, причём зачастую это единственное имеющееся точное описание[1]. Х-исчисление представляет собой удобную модель, позволяющую выявлять многие важные аспекты построения и работы программ, написанных на алгоритмических языках. Так, например, в предисловии к переводу книги П.Хендерсона «Функциональное программирование» Ершов отмечает: «Х-исчисление ... можно считать не чем иным, как теоретической моделью современного функционального программирования»[5].
В теоретической информатике такой способ описания функций, игнорирующих понятие «состояние системы», действительно удобен. Однако Х-выражения имеют тенденцию по мере роста сложности приобретать громоздкий вид, затрудняющий их восприятие человеком. Например, выражение, имеющее вид:
Хх у.у х(Х2.2)(= х(Ху((у х)(Х2.2)))) ,
уже достаточно сложно для восприятия. Как правило, при записи подобных формул прибегают к декомпозиции выражений либо специфичным приёмам упрощения.
В качестве недостатков Х-исчисления традиционно указывают:
1) трудность лексического, синтаксического и семантического анализа выражений;
2) выражение итеративных, рекурсивных и, в целом, нелинейных алгоритмов является неестественным [1] и, как правило, имитируется путём последовательного вызова семантически схожих функций (либо алгоритм подвергается существенной переработке, что не всегда рационально).
В качестве одного из возможных путей преодоления указанных проблем в представлении функциональной логики предлагается нотация т. н. «Х-автоматов».
Абстрактный автомат являющийся синхронным дискретным автоматом и имеющий конечные множества значений входных и выходных сигналов, формально описывается пятеркой А = (X, У, Q, 3, X), где X и У - входной и выходной алфавиты соответственно; Q - множество состояний; 3: X, Q ^ Q - функция переходов; X: X, Q ^ У - функция выходов[3]. Формализация конечного автомата является результатом исключения из списка параметров У и X, а описание автомата автономного - исключением входного алфавита X. Проводя подобные манипуляции с характеристиками абстрактного автомата, получают инициальный, вероятностный и прочие варианты автоматов.
Предположим, что абстрактный автомат не имеет внутреннего состояния и, таким образом, описывается только тройкой А = (X, У, X), где X: X ^ У - выходная функция. Получим автомат без памяти, в котором выходной символ зависит только от входного символа в данном такте и не зависит от ранее поступивших символов [4]. Назовём такой автомат Х-автоматом и введём нотацию, использующую изображение автоматов.
Пусть 1( = Цх)) - выражение, содержащее переменную х. Тогда кхЛ(х) есть функция/, которая ставит в соответствие аргументу а значение Ц.а). Иными словами, имеет место равенство:
(ХхЛ(х)) a = ^а) .
Графически данное выражение может быть представлено с помощью нотации Х-автоматов (рис. 1)
А
а
V
х
Рис. 1. Представление выражения (ХхЛ(х)) а в нотации Х-автоматов
Основным преимуществом такого представления является его очевидность. Отметим также, что при графическом описании выражений программист получает возможность явного контроля последовательности исполнения отдельных элементов выражения.
Приведём в качестве иллюстрации ряд примеров Х-выражений в нотации Х-автоматов (табл. 1):
Таблица 1
Соответствие Х-выражений и нотации Х-автоматов
Х-нотация Нотация Х-автоматов
Хх.х =*> х :
Хх.(х+1) х+1 Е">
Хх.(Хх.х)
х
Хх.(х+1) у V 1 V»' х+1 V +1
Запишем в виде нотации Х-автоматов выражение
Ха.(Хк.(ХЬ.(Х2.(Х2. (Ху. (Хх.х+1)+1)+1)+1)+1)3 .
В этом случае имеет место цепочка из пяти Х-автоматов, вычисляющих данное выражение и получающих результат - 8 (рис.2)
х+1 х+1 х+1 х+1 х+1
-Е-1 -Е-1 -Е^ -Е^
Рис. 2. Цепочка Х-автоматов
Добавим нумерацию автоматов, что позволит сократить запись. Рисунок 3 расшифровывается как «повторить блок номер 1 пять раз» (рис.3).
Рис. 3 Блок №1 (слева) повторяется 5 раз (запись справа)
Таким образом, предлагаемая нотация, сохраняя математическую строгость Х-исчисления, позволяет записывать исследуемые выражения в более эффективном по ряду критериев виде. Это позволяет решить следующие важные задачи:
1) упрощение анализа Х-выражений;
2) введение естественного аппарата для выражения итеративных и рекурсивных процессов в терминах Х-исчисления.
При этом сохраняются следующие преимущества Х-исчисления:
1) лаконичность - небольшое количество аксиом и правил вывода, ограниченный необходимыми элементами алфавит, две операции для построения сколь угодно сложных выражений;
2) полнота - точное и полное описание важных понятий программирования и произвольных сколь угодно сложных функций.
Применимость предлагаемой нотации не исчерпывается возможностью описания систем без состояния. Легко показать, что такое принципиальное различие между представлением системы в виде, например, графа переходов и в виде нотации Х-автоматов, как необходимость явного либо неявного учёта состояния автомата (в части, касающейся порядка вычислений), оказывается несущественным в рамках нотации Х-автоматов (таб. 2):
Таблица 2
Представление семантики функциональной системы в различных нотациях
Математические функции Граф переходов Нотация Х-автоматов Х-нотация
f(y)=1+y; f(y)=1-y; с+У^ 1 1+у Ху.(у+1) Ху.(у-1)
\/ 2 1-У
В настоящее время широкую популярность обрели работы в области автоматизации программирования, позволяющие разработчику оперировать графическими представлениями абстрактных автоматов для последующей автоматической конвертации данных изображений в код целевого языка[6,7]. Однако исторически такая практика предполагает использование императивных языков программирования. Предлагаемая нотация Х-автоматов позволяет в естественной форме сблизить графические представления языков программирования разных семейств и адаптировать развитые инструментальные средства императивных ЯВУ для анализа и синтеза функциональных ЯВУ. Таким образом, теоретическая значимость нотации Х-автоматов может быть использована для развития средств автоматизации программирования на языках, основанных на Х-исчислении.
Литература
1. Барендрегт Х. Ламбда-исчисление. Его синтаксис и семантика: пер. с англ. - М.: Мир, 1985. - 606с.
2. Брукс Ф. Мифический человеко-месяц, URL: http://os24.org/files/books/Frederick_ Brooks-The_Mythical_Man-Month-RU-1995.pdf , 1975. - 171с.
3. Глушков В.М. Синтез цифровых автоматов/ В.М.глушков. - М.:Физматгив, 1962. -476 с., ил.
4. Глушков В.М. Энциклопедия кибернетики: в 2.т./ В.М. Глушков; Н.М. Амосов, И.А. Артеменко, А.А. Бакаев, В.В. Иванов, Л.А. Калужнин, В.А. Ковалевский, В.С. Королюк, М.И. Кратко, В.М. Кунцевич, А.И. Кухтенко, Б.Н. Малиновский, В.С. Михалевич, П.В. По-ходзило, Г.Е. Петухов, Б.Н. Пшеничный, Э.Л. Рабинович, Б.Б. Тимофеев, Е.Л. Ющенко. -Киев.: Главная редакция УСЭ, 1974. Т.1. - с.608.
5. Хендерсон П. Функциональное программирование. Применение и реализация. / П. Хендерсон. - М.: Мир, 1983. - 349с.
6. http://mindstorms.lego.com/en-us/Default.aspx
7. http://www.automation.siemens.com/mcms/programmable-logic-controller/en/logic-module-logo/logo-software/Pages/Default.aspx
А
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.