OPTIMIZING TRANSFORMATIONS FOR OPERATIONS ON LISTS AND TREES IN THE PREDICATE PROGRAMMING SYSTEM
Kiril Bulgakov, Ivan Kablukov, Erdem Tumurov, Vladimir Ivanovich Shelekhov · System Informatics · 2017
System Informatics (Системная информатика), No. 9 (2017) 63 УДК 004.43 Оптимизирующие трансформации списков и деревьев в системе предикатного программирования Булгаков К.В.(Новосибирский государственный университет), Каблуков И.В., Тумуров Э.Г.(Институт систем информатики СО РАН), Шелехов В.И.(Институт систем информатики СО РАН, Новосибирский государственный университет) Описываются оптимизирующие трансформации для операций над списками и деревьями в системе предикатного программирования.Кодирование операций представлено набором правил, определяющих замену исходной операции на ее образ в императивном языке.Результатом трансформаций является императивная программа по эффективности сравнимая с написанной вручную.Ключевые слова: функциональное программирование, трансформации программ, алгебраический тип данных.Вхождения переменных head и tail являются определяющими, причем head -начальный элемент списка s, а tail -«хвост» списка s.Оператор выбора эквивалентен следующему оператору: if (nil?(s)) else { { T c = s.car|| list(T) y = s.cdr}; }; Определены следующие операции со списками: s.car -первый элемент списка s.cdr -список без первого элемента last(s) -последний элемент списка s[m] -элемент под номером m len(s) -длина списка nil?(s) -проверка на пустоту списка s == nil -проверка на пустоту списка cons?(s) -проверка на непустоту списка s != nil -проверка на непустоту списка prec(s) -список без последнего элемента s + t -конкатенация списков s + e -добавление элемента в конец списка s[m..n] -вырезка списка от номера m до номера n s[m..] -вырезка списка от m до конца Здесь s -выражение типа список, t -терм типа список, e -выражение типа элемента списка, m, n -выражение типа nat.Элементы списка нумеруются с нуля.Конструкторы списка: nil cons(head, tail) consLeft (list, m) | consRight (list) | consRight (list, n) Здесь nil и cons(head, tail), где head -элемент списка и tail -список, являются стандартными конструкторами в соответствии с определением типа list.Описание специальных конструкторов consLeft и consRight дано в разделе 4.2.Для изображения типа списка допускается использование следующих типовых термов: list(T) list(T, L) Здесь T -тип элемента списка, L -максимальная длина списка.Размер памяти, отводимой для переменной типа list(T, L), будет достаточным для размещения L элементов списка.