Каблуков И.В.
Реализация склеивания переменных в предикатной программе
Склеивание переменных [1] - одно из оптимизирующих трансформаций, применяемых при трансляции программы на языке предикатного программирования P [2] в эффективную программу на один из языков: С++, ФОРТРАН и др. Склеивание переменных – это замена (сохраняющая эквивалентность) в тексте программы всех вхождений одной переменной на другую. Значительный эффект достигается при склеивании структурных переменных, таких как массивы и списки, поскольку склеивание обычно позволяет избежать копирования структур.
Постановка задачи. В отличие от задачи экономии памяти [3], склеиванию в программе подлежат результаты с аргументами, аргументы с локалами и локалы с результатами. Набор склеиваний может быть частично задан пользователем. Необходимо проверить его корректность и дополнить. В языке P правилами языка запрещено присваивание вида: x:=op(x, y). Поэтому в языке P существуют только присваивания x:=op(x1, y). При трансляции x1 склеивается с x. Например, при склеивании переменных c и d оператор c:=d+1 будет преобразован в оператор присваивания c:=с+1, а оператор a:=b при склеивании a и b превратится в оператор a:=a, удаляемый из программы. Типы склеиваемых переменных должны совпадать.
Анализ и метод решения. Склеивание переменных использует результаты потокового анализа программы, который для каждого оператора программы определяет аргумены, результаты и используемые в следующих операторах переменные.
Регион склеивания для оператора G есть набор аргументов и результатов одного типа <x: y>, где х — список аргументов и у — список результатов оператора. Пример. Пусть имеется оператор F с аргументами a, b, c, d, e и результатами f, g, h. Пусть переменные a, b, d и g, h имеют натуральный тип, а переменные c, e и f — массивы. Тогда для оператора F регионы склеивания таковы: <a, b, d: g, h> и <c, e: f>.
Алгоритм склеивания реализуется уточнением регионов. Уточнение регионов — это процесс, в результате которого исходный регион преобразуется в набор регионов, состоящих из одного аргумента и одного результата.
Регионы оператора уточняются на основе регионов подоператоров для операторов суперпозиции, условного и параллельного операторов. Для параллельного оператора регионы объединяются, для условного — обобщаются, для суперпозиции дополнительно реализуется склеивание через локалы.
Список литературы
-
Петров Э.Ю. Склеивание переменных в предикатной программе // Методы предикатного программирования. Новосибирск, 2003. С. 48-61.
-
Шелехов В.И. Введение в предикатное программирование. - Новосибирск, 2002. - 82с. - (Препр. / ИСИ СО РАН; N 100).
-
Ершов А.П. Введение в теоретическое программирование - М.: Наука, 1977. - 288с.
Работа выполнена при финансовой поддержке РФФИ (код проекта № 12-01-000686).
Тезисы доклада: | abstracts_138078_ru.pdf |
Файл с полным текстом: | Kablukov_proc.pdf |
К списку докладов