Программные продукты и системы

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

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

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

В работе А.С. Клещева и М.А. Князевой «Управление информацией о преобразованиях программ. I. Анализ проблем и пути их решения на основе методов искусственного интеллекта» (2005) для решения научных, практических и образовательных проблем в области преобразования программ, была  предложена  концепция управления информацией о преобразованиях программ в рамках Специализированного банка знаний о преобразованиях программ (СБкЗ_ПП).

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

В процессе потокового анализа происходит извлечение определенных семантических свойств программы. Традиционно потоковый анализ разделяют на анализ потока управления и анализ потока данных.

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

Рассмотрим архитектуру и контекст подсистемы потокового анализа, управляемого знаниями, в рамках системы преобразований программ СБкЗ_ПП.

Входной информацией подсистемы потокового анализа, управляемого знаниями в системе преобразований программ, являются: модель структурной программы (МСП), методы потокового анализа и задание на потоковый анализ программ. Входная информация формируется подсистемой управления СБкЗ_ПП, которая осуществляет взаимодействие с редакторами и передает управление подсистеме потокового анализа. На выходе подсистемы формируется МСП, расширенная терминами потокового анализа программ.

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

Задание на потоковый анализ представляет собой список атрибутов, фрагментов, дуг и отношений, которыми необходимо расширить МСП.

База программ содержит программы на языках программирования высокого уровня в терминах онтологий языков программирования.

База методов потокового анализа формируется экспертом предметной области. При помощи редактора методов потокового анализа (МПА) пользователи системы пополняют и модифицируют базу МПА. Для описания МПА разработан язык описания МПА.

При разработке языка для записи МПА были проанализированы основные формы записи МПА, описанные в литературе. Язык описания МПА содержит:

·     переменные, которые в качестве значений могут принимать ссылки на различные элементы модели программы;

·     основные конструкции алгоритмических языков программирования (цикл, выбор, присваивание);

·     операции с множествами, поскольку в процессе накопления информации о программе необходимо выполнять различные операции над множествами  переменных и идентификаторов;

·     операции обходов деревьев и операции с древовидными структурами.

Рассмотрим пример представления МПА в базе методов потокового анализа. Неформально метод задан следующим образом: необходимо скопировать аргументные множества всех фрагментов программы в результатные. Аргументное множество есть множество переменных, значение которых могут повлиять на выполнение какого-либо оператора в программе, а результатное – множество переменных, на которые может повлиять выполнение оператора. Информация об аргументных множествах операторов используется в оптимизирующих преобразованиях «удаление неиспользуемых переменных», «вынос инвариантного оператора из цикла» и прочих.

Метод_потокового_анализа(Копирование_множеств)

Тип-фрагмент: Текущий_фрагмент;

Тип-атрибут: Временный_атрибут;

{

Дерево_обхода_программы(Функция_Главная;

Текущий_фрагмент;Класс_фрагмента(Текущий_фрагмент)==

Присваивание){

Атрибут_фрагмента(Текущий_фрагмент;

Аргументное_множество; Временный_атрибут);

Создание_атрибута(Текущий_фрагмент;

Результатное_множество; Временный_атрибут);

}

}

Первая строка метода имеет следующий вид:

Метод_потокового_анализа(Копирование_множеств)

Описание метода на языке методов МПА начинается с ключевого слова Метод_потоково­го_анализа, за которым в круглых скобках указывается название метода.

Далее следует раздел описания переменных:

Тип-фрагмент: Текущий_фрагмент;

Тип-атрибут: Временный_атрибут;

В данном примере описано две переменных: первая имеет тип Тип-фрагмент и называется Текущий_фрагмент, вторая, Тип-атрибут, называется Временный_атрибут. Тип переменной Тип-фрагмент обозначает, что данная переменная может в качестве значения принимать ссылку на фрагмент конкретной программы на МСП или на объект, находящийся в памяти, который отображает все свойства фрагмента МСП. Описание переменных разных типов разделяются точкой с запятой. Если есть описание нескольких переменных одного типа, их перечисляют через запятую.

Непосредственно за разделом описания переменных следует тело метода, которое состоит из последовательности конструкций:

{

Дерево_обхода_программы(…)

{

Атрибут_фрагмента(…);

Создание_атрибута(…);

}

}

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

Конструкция Дерево_обхода_программы представляет собой функцию с тремя аргументами, которые следуют за ключевым словом, заключены в круглые скобки и разделены точкой с запятой и телом, заключенным в фигурные скобки:

Дерево_обхода_программы(Функция_Главная;

Текущий_фрагмент; Класс_фрагмента(Текущий_фрагмент) ==

Присваивание)

{

…

}

Эта функция реализует обход дерева фрагментов МСП. Первый аргумент задает фрагмент МСП, который является корнем поддерева, которое предстоит обойти. Второй аргумент – это переменная, которая принимает значение фрагмента на очередном шаге обхода. Третий аргумент – это логическая формула, в случае истинности которой выполняется последовательность конструкций из тела. В данном примере первый аргумент – константа Функция_Главная, значением которой является ссылка на корневой фрагмент дерева МСП. Второй аргумент – переменная Текущий_фраг­мент, которая будет принимать значения очередного фрагмента на каждом шаге обхода. Третий аргумент – логическая формула – принимает значение истина, если фрагмент МСП, на который ссылается Текущий_фрагмент, имеет класс Присваивание.

Конструкция Атрибут_фрагмента называется формулой:

Атрибут_фрагмента(Текущий_фрагмент, Аргументное_множество, Временный_атрибут);

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

Создание_фрагмента, как и Атрибут_фраг­мента, является формулой:

Создание_атрибута(Текущий_фрагмент, Результатное_множество,

Временный_атрибут);

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

В данной работе представлена концепция потокового анализа, управляемого знаниями. На примере было продемонстрировано, каким образом при помощи описанного языка можно определить МПА. На основе концепции потокового анализа, управляемого знаниями, разработана подсистема потокового анализа в рамках системы преобразований программ в СБкЗ_ПП. Система реализована в среде программирования Java IntelliJ Idea с использованием ресурсов многоцеле- вого банка знаний (http://www.iacp.dvo.ru/es/mpk­bank).