Теория и практика программирования

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

Инсерционное программирование - это программирование на базе модели поведения агентов в средах []. В основе модели лежит понятие размеченной транзиционной системы, т.е. системы, определенной так же, как и автомат, множеством состояний и множеством переходов (пары состояний), размеченных действиями или событиями. Формально, понятие транзиционной системы совпадает с понятием недетерминированного частично определенного автомата, однако, в отличие от теории автоматов, отношение эквивалентности транзиционных систем более сильное. Если для автоматов эквивалентность состояний определяется совпадением языков в алфавите входных сигналов, порождаемых этими состояниями, то эквивалентность состояний транзиционных систем определяется эквивалентностью деревьев поведений, размеченных действиями системы. Это отношение называется бисимуляционной эквивалентностью. Оно было введено в работах Милнера и Д.Парка еще в 70-х годах. В настоящее время понятие транзиционной системы и бисимуляционной эквивалентности используется в качестве основного стандарта в поведенческой теории взаимодействующих процессов в сочетании с различными более слабыми, чем бисимуляция, отношениями эквивалентности на множестве состояний систем.
Содержательные мотивы инсерционного программирования строятся на представлениях о поведении систем (агентов), взаимодействующих со своим окружением (средой). Поэтому ближе всего к инсерционному программированию находятся современные декларативные языки моделирования типа UML, SDL, MSC, а также языки, основанные на алгебрах взаимодействующих процессов (CCS, CSP, и т.п.). Агентное программирование концентрируется в большей степени на проблемах интеллектуализации, однако его поведенческие аспекты естественным образом покрываются инсерционным программированием.

Отличительной чертой инсерционного программирования является формализация понятия среды и функции погружения (insertion) агентов в среду. Функция погружения Ins(e,u)= e[u] определяет композицию среды e и агента u, результатом которой является новая среда e[u], готовая для погружения других агентов: (e[u])[v]=e[u,v]. Агенты и среды рассматриваются как объекты разных типов, обладающие поведением, представляемым с помощью транзиционных систем, состояния которых рассматриваются с точностью до бисимуляционной эквивалентности. Среда ограничивает поведения агента и может даже его трансформировать, поэтому поведение агента в среде существенно отличается от его поведения, определенного независимо от среды. Это обстоятельство приводит к новой более слабой по отношению к бисимуляционной эквивалентности агентов. Именно, агенты u и u' называются эквивалентными относительно заданной среды, если для любого состояния е этой среды e[u]=e[u'], где равенство означает бисимуляционную эквивалентность. Единственное ограничение на функцию погружения, необходимое для конструктивности есть непрерывность (в подходящей топологии). Благодаря этому ограничению для определения функций погружения можно использовать системы переписывания (алгебраическое программирование), исчисления, рекурсивные определения.

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

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

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

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

В системе инсерционного программирования, разработанной в Институте Кибернетики на базе системы алгебраического программирования APS, для представления агентов используется Язык Действий (AL). Основные конструкции этого языка сводятся к префиксингу ахР, где а есть действие, Р - программа, недетерминированному выбору P+Q последовательной и параллельной композиции (P;Q) и (P||Q), соответственно. К этому добавляется возможность рекурсивных определений с использованием систем переписывания.

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

Руководители разработки: Капитонова Ю.В., Летичевский А.А.
Основные разработчики АПС: Волков В.А., Матвеева Л.Е., Канозенко С.В., Гречко В.О., Чугаенко А.В.

Капитонова Ю.В., Летичевский А.А.