г. Новосибирск, 15-17 октября 2012 г.

Каблуков И.В.  

Реализация склеивания переменных в предикатной программе

Склеивание переменных [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>.

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

Регионы оператора уточняются на основе регионов подоператоров для операторов суперпозиции, условного и параллельного операторов. Для параллельного оператора регионы объединяются, для условного — обобщаются, для суперпозиции дополнительно реализуется склеивание через локалы.

 

Список литературы

  1. Петров Э.Ю. Склеивание переменных в предикатной программе // Методы предикатного программирования. Новосибирск, 2003. С. 48-61.

  2. Шелехов В.И. Введение в предикатное программирование. - Новосибирск, 2002. - 82с. - (Препр. / ИСИ СО РАН; N 100).

  3. Ершов А.П. Введение в теоретическое программирование - М.: Наука, 1977. - 288с.

 

Работа выполнена при финансовой поддержке РФФИ (код проекта № 12-01-000686).

 

Тезисы доклада:abstracts_138078_ru.pdf
Файл с полным текстом: Kablukov_proc.pdf


К списку докладов

Комментарии

Имя:
Код подтверждения: