Алгебраическое программирование (АП)

АП обеспечивает описание процессов конструирования программ, алгебраические преобразования, доказательство математических теорем и создание интеллектуальных агентов с помощью математиского аппарата, в качестве которого используется понятие транзитивной системы [31–34].

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

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

Расширением понятия транзитивных систем является множество заключительных состояний с успешным завершением функционирования системы и без неопределенных состояний_. Главным инвариантом состояния транзитивной системы является поведение системы, которое можно задать выражениями алгебры поведения F(A) на множестве операций алгебры А, а именно две операции префиксинга a× u, задающие поведение u на операции а, недетерминированный выбор u+v одной из двух поведений u и v, который является ассоциативным и коммутативным. Конечное поведение задается константами: D, ^, 0, обозначающими соответственно состояние успешного завершения, неопределенного и тупикового состояния.

Алгебра поведения частично задается отношением £, для которого элемент ^ является наименьшим, а операции алгебры поведения – монотонными. Теоретически алгебра поведения F(A) проверена путем доказательства теоремы про наименьшую неподвижную точку.

Транзитивные системы называют бисимуляцийно эквивалентными, если каждое состояние любой из них эквивалентно состоянию другой системы. На множестве

поведений определяются новые операции, которые используются для построения программ агентов. К ним относятся операции: последовательная композиция (u; v) и параллельная композиция u//v.

Среда Е, где находится объект, определяется как агент в алгебре действий А и функции погружения отдвух аргументов Ins(e, u) = e[u]. Первый аргумент – это поведение среды, второй – поведение агента, который погружается в эту среду в заданном состоянии. Алгебра агента – это параметр среды. Значения функций погружения – это новое состояние одной и той же среды.

Разработанная общая теория выходит за рамки определения вычислительных и распределенных систем, а также механизмов взаимодействия со средой. Базовым понятием является “действие”, которое трансформирует состояние агентов, поведение которых, в конце концов, изменяется.

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

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

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

выборе. Установлено, что последовательная композиция – ассоциативная, а параллельная композиция – ассоциативная и коммутативная. Параллельная композиция раскладывается на комбинацию действий компонентов.

Агенты рассматриваются как значения транзитивных систем с точностью до бисимиляционной эквивалентности. Эквивалентность характеризуется в алгебре поведения непрерывной алгеброй с аппроксимацией и двумя операциями: не детерминированным выбором и префиксингом. Среда вводится как агент, куда погружения функция, имеет поведение типа агент и среды. Произвольные непрерывные функции могут быть использованы как функции погружения и эти функции, определены значениями логики переписывания. Трансформации поведения среды, которые определяются функциями погружения, составляют новый тип эквивалентности – эквивалентность погружения.

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

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

Наибольшую актуальность имеют системы символьных вычислений, которые дают возможность работать с математическими объектами сложной иерархической структуры. Многие алгебраические структуры (группы, кольца, поля) являются иерархически – модулярными. Теория АП обеспечивает создание математической информационной среды с универсальными математическими конструкциями, вычислительными механизмами, учитывающими особенности разработки ПС и функционирования. АП является основой формирования нового вида программирования – инсерционного, обеспечивающего программирование систем на основе моделей поведения агентов, транзитивных систем и бисимуляционной эквивалентности [14].

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