научная статья по теме НОТАЦИЯ λ-АВТОМАТОВ КАК СПОСОБ ПРЕДСТАВЛЕНИЯ НЕЛИНЕЙНЫХ АЛГОРИТМОВ Науковедение

Текст научной статьи на тему «НОТАЦИЯ λ-АВТОМАТОВ КАК СПОСОБ ПРЕДСТАВЛЕНИЯ НЕЛИНЕЙНЫХ АЛГОРИТМОВ»

Технические на уки

Информатика, вычислительная техника и управление

Системный анализ, управление и обработка информации

х

Чугреева Е.Е.

Алиев Р. С., кандидат технических наук, доцент

(Московский государственный технический университет «Станкин»)

НОТАЦИЯ ^-АВТОМАТОВ КАК СПОСОБ ПРЕДСТАВЛЕНИЯ НЕЛИНЕЙНЫХ АЛГОРИТМОВ

В статье решается актуальная задача разработки графического представления термов 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 рублей.

Показать целиком

Пoхожие научные работыпо теме «Науковедение»