ISSN 1991-3087
Рейтинг@Mail.ru Rambler's Top100
Яндекс.Метрика

НА ГЛАВНУЮ

Оптимизирующие трансформации рекурсивных структур в системе предикатного программирования

 

Булгаков Кирилл Владимирович,

студент Новосибирского государственного университета.

Научный руководитель – кандидат технических наук, зав. лаб. ИСИ СО РАН

Шелехов Владимир Иванович.

 

Введение

 

Предикатная программа относится к классу программ-функций и является предикатом в форме вычислимого оператора, адекватно представляющим логику решения задачи, обеспечивая хорошее понимание программы. Язык предикатного программирования P [5] обладает большей выразительностью, в сравнении с языками функционального программирования, и по стилю ближе к императивному программированию.

В предикатном программировании запрещены такие языковые конструкции, как циклы и указатели, серьезно усложняющие программу. Вместо циклов используются рекурсивные функции, а вместо массивов и указателей – списки и деревья.

Предикатная программа с алгебраическими типами (списками, деревьями и т. п.) существенно проще аналогичной императивной программы, реализующей действия с рекурсивными структурами через массивы и указатели. Эффективность предикатных программ достигается применением при трансляции оптимизирующих трансформаций, переводящих программы на язык императивного расширения языка предикатного программирования P [3]. Они определяют оптимизацию среднего уровня с переводом предикатной программы в эффективную императивную программу. Эта оптимизация отлична от классической.

Базовыми трансформациями являются:

1)                 склеивание переменных, реализующее замену нескольких переменных одной [2];

2)                 замена хвостовой рекурсии циклом;

3)                 подстановка определения предиката на место его вызова;

4)                 кодирование рекурсивных структур, таких как списки и деревья, при помощи массивов и указателей.

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

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

 

Списки в языке предикатного программирования

 

Тип «список» – встроенный алгебраический тип со следующим определением:

type list (type T) = union (

nil,

cons(T car, list(T) cdr)

);

Здесь T – тип элемента списка, nil и cons – конструкторы. Канонический способ работы со списками определяется оператором выбора:

switch (s) {

case nil: <оператор1>

case cons(head, tail): <оператор2>

};

Где переменная head – начальный элемент списка s, а tail – «хвост» списка s.

Пусть s переменная типа список, тогда для нее возможны следующие конструкции:

·                    s.car - голова списка, т.е. первый элемент списка;

·                    s.cdr - хвост списка, т.е. список без первого элемента;

·                    prec(s) - список без последнего элемента;

·                    last(s) - последний элемент списка;

·                    s[i] - получение элемента списка по индексу;

·                    s[i .. j] - вырезка списка, начинающаяся элементом с номером i и заканчивающаяся элементом с номером j;

·                    s[i .. ] - вырезка списка, начинающаяся элементом с номером;

·                    len(s) - длина списка.

Для списков возможно использование оператора ветвления:

if (nil?(s)) <оператор1> else { { T c = s.car || list(T) y = s.cdr}; <оператор2> };

Распознаватель nil?(s) позволяет проверить список на пустоту, а распознаватель cons?(s) истинен для непустого списка.

Для списков определяется следующий набор языков конструкций:

<выражение типа список> ::=

            <терм типа список> | <конкатенация списков> |

            <список-агрегат> | <конструктор списка> | <терм типа элемента списка>

<терм типа список> ::=

            <переменная типа список> | <терм типа список> . cdr |

            prec ( <выражение типа список> ) | <вырезка списка>

<конкатенация списков> ::=

            <выражение типа список> + <терм типа список> |

            <выражение типа список> + <терм типа элемента списка>

Список-агрегат это конструкция, позволяющая определить список путем перечисления его элементов, например, [[a, b, c]].

<вырезка списка> ::=

            <терм типа список> [ <выражение> .. <выражение>] |

            <терм типа список> [ <выражение> .. ]

<конструктор списка> ::=

            nil |

            cons ( <терм типа элемента списка> , <выражение типа список> ) |

            <специальный конструктор списка>

<терм типа элемента списка> ::=

            <переменная типа элемента списка> | <терм типа список> . car |

            last ( <выражение типа список> ) | <терм типа список> [ <индекс> ]

Более подробно списки и особенности их реализации описаны в статье «Списки и строки в предикатном программировании» [4].

 

Кодирование списков в императивном расширении предикатного программирования

 

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

Для представления значения типа list(T) в императивном расширении используется следующая структура:

struct list {

            T *data;

            int max_len;

            int m;

            int n;

}

Здесь T – тип элемента списка, max_len – максимальная длина списка, m,n – индексы начала и конца текущей вырезки массива, причем 0 ≤ m ≤ n ≤ max_len, data – массив в котором хранятся данные.

Для эффективного кодирования списков используется потоковый анализ программы [1]. Потоковый анализ программы включает: построение графа вызовов программы, определение аргументов и результатов языков конструкций, а также времени жизни переменных.

Приведем каталог преобразований для основных операций списка при кодировании через массив таблица 1. В каталоге образов используется предикат pArg. pArg(variable_name) – значит, что переменная с именем variable_name является постаргументом конструкции в которой участвует данная переменная. Переменная является постаргументом, если ее значение используется при исполнении программы после данной конструкции.

 

Таблица 1

Конструкция

Образ конструкции

Условия применимости

list(T) l;

list *l = new list();

l→max_len = DEFAULT_MAX_LEN;

l→data = new T[l→max_len];

l→m = 0;

l→n = 0;

Всегда

 

 

list(T, L) l;

list *l = new list();

l→max_len = L;

l→data = new T[l→max_len];

l→m = 0;

l→n = 0;

Всегда

 

 

l = consLeft(y, m);

delete[] l→data;

l→max_len = y→max_len + m;

l→data = new T[l→max_len];

l→m = m;

l→n = y→max_len + m;

<копирование массива из y в l со сдвигом на m относительно начала>

Всегда

 

 

l = consRight(y);

delete[] l→data;

l→max_len = DEFAULT_MAX_LEN + y->max_len;

l→data = new T[l→max_len];

l→m = DEFAULT_MAX_LEN;

l→n = l→max_len;

<копирование из массива y в l прижатым вправо>

Всегда

 

 

l = consRight(y, L);

delete[] l→data;

l→max_len = L;

l→data = new T[l→max_len];

l→m = L – (y→n – y->m);

l→n = l→max_len;

<копирование из массива y в l прижатым вправо>

Всегда

 

 

max_len(s);

s->max_len;

Всегда

 

 

store(s);

s→max_len – s->n;

Всегда

 

 

left_sore(s);

s->m;

Всегда

 

 

resize(s, n);

T *new_data = new T[n];

<копируем данные из s→data в new_data>

delete[] s→data;

s→data = new_data;

s→max_len = n;

Всегда

 

 

len(s);

s→n – s→m;

Всегда

 

 

nil?(s);

s == NULL;

Всегда

 

 

cons?(s);

s != NULL;

Всегда

 

 

s = s1 + .. + sn;

int result_len = len(s1) + len(sn);

if (max_len(s) >= result_len) {

  int shift = 0;

  <копирование s1 в s со сдвигом на shift относительно начала>

  shift += len(s1);

  …

  <копирование sn в s со сдвигом на shift относительно начала>

} else {

  list(T, result_len) result;

  int shift = 0;

  <копирование s1 в result со сдвигом на shift относительно начала>

  shift += len(s1);

  …

  <копирование sn в result со сдвигом на shift относительно начала>

}

Присваивание вида копирование

 

 

s = s + e;

if (store(s) >= len(e)) {

  <копировать e вслед за значением s>

} else {

  resize(s, len(s) + len(e));

  <копировать e вслед за значением s>

}

 

Присваивание вида модификация

 

 

s = e + s;

if (left_store(s) >= len(e)) {

  <копировать e перед значением s>

} else {

  s = consRight(s, len(s) + len(e));

  <копировать e перед значением s>

}

Присваивание вида модификация

 

 

s = s.car;

s→n = s→m + 1;

Присваивание вида модификация

 

 

s = s[m..n];

s→m = m;

s→n =n;

Присваивание вида модификация

 

 

s = s[m..];

s→m = m;

Присваивание вида модификация

 

 

s = s.cdr;

s→m = s→m + 1;

Присваивание вида модификация

 

 

s = prec(s);

s→n = s→n - 1;

Присваивание вида модификация

 

 

s = last(s);

s→m= s→n - 1;

Присваивание вида модификация

 

 

s = s.cdr;

it→max_len = s->max_len;

it→data = s->data;

it→m = s→m;

it→n = s→n;

<итерации сканирования>

it→m = it→m + 1;

Сканирование

 

 

s = prec(s);

it→max_len = s->max_len;

it→data = s->data;

it→m = s→m;

it→n = s→n;

<итерации сканирования>

it→n = it→n - 1;

Сканирование

 

 

s = s[m..n];

it→max_len = s->max_len;

it→data = s->data;

it→m = s→m;

it→n = s→n;

<итерации сканирования>

it→m = m;

it→n = n;

Сканирование

 

 

s = s[m..];

it→max_len = s->max_len;

it→data = s->data;

it→m = s→m;

it→n = s→n;

<итерации сканирования>

it→m = m;

Сканирование

 

 

 

Заключение

 

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

 

Литература

 

1.                  Касьянов В. П. Оптимизирующие преобразования программ. М.: Наука, 1988. — 336 с.

2.                  Петров Э. Ю. Склеивание переменных в предикатной программе. Новосибирск, 2003. — 61 c.

3.                  Шелехов В.И. Предикатное программирование. Учебное пособие. — НГУ, Новосибирск, 2009. — 109 с.

4.                  Шелехов В.И. Списки и строки в предикатном программировании. — Системная информатика, 2014. — 19 с.

5.                  Шелехов В.И. Язык предикатного программирования P. Описание языка.

 

Поступила в редакцию 24.03.2015 г.

2006-2019 © Журнал научных публикаций аспирантов и докторантов.
Все материалы, размещенные на данном сайте, охраняются авторским правом. При использовании материалов сайта активная ссылка на первоисточник обязательна.