Специализация функциональных программ методами суперкомпиляции

• Автор: Немытых, Андрей Петрович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Переславль-Залесский
• Количество страниц: 170 с. + Прил.(с. 171-322)

Оглавление
Введение
1 Анализ результатов диссертации в контексте исследований в области специализации программ

1.1 О двух постановках задачи специализации.

1.2 Обзор результатов в области специализации программ . . .

1.3 Исторический обзор развития методов суперкомпиляции . .

2 Схема структуры преобразователя программ БСР

3 Язык параметров

3.1 Параметризованные множества данных

3.2 Параметризованные множества полей зрения стеков и РЕФАЛвыражений.

4 Язык РЕФАЛграфов

4.1 Синтаксис.
4.1.1 Синтаксис входного подмножества.
4.2 Семантика.
4.3 Язык РЕФАЛ5 и язык РЕФАЛграфов
4.3.1 О неравномерности шагов РЕФАЛмашины
4.3.2 Дерево отождествления в языке РЕФАЛграфов. . .
5 Прогонка
5.1 Общая структура прогонки
5.2 Перестройка стека функций.
5.3 Стратегия выбора входного формата.
5.4 К вопросу о целях преобразований
6 Свртка
6.1 Вложение
6.2 Стратегия обхода дерева при факторизации
6.3 Обобщение.
6.3.1 Отношение похожести.
6.3.2 Обобщение конфигураций
6.3.3 Обобщение параметризованных выражений.
6.3.4 Обобщение и построение отрицательной информации.
6.3.5 Стратегия обхода метадерева при обобщении
6.3.6 Обнинское условие и транзитные вершины
6.4 К вопросу о целях преобразований
6.4.1 Изменение местности параметризованной среды при
е обобщении.
7 Развртка
7.1 Стратегия развития дерева
7.2 Стратегии развития стека функций.
7.3 К вопросу о целях преобразований
8 Подграф компонента факторизации
9 Чистка экранируемых ветвей
Глобальный анализ
.1 Анализ в терминах языка РЕФАЛграфов
.1.1 Пустые подграфы
.1.2 Выходные форматы.
.1.3 Графы определяющие константу.
.1.4 Проекции.
.2 Анализ в терминах языка РЕФАЛ.
.2.1 Тождественность
.2.2 Мономы конкатенации.
.2.3 Стратегия выбора гипотезы мономиалыюсти
.2.4 Частичные выражения
.3 Чистка поглощаемых ветвей.
Том II
Использование результатов глобального анализа
.1 Одношаговые подграфы.
.2 Пустые подграфы
.3 Рекурсивные подграфы. Повторная специализация
.4 Квазидистрибутивность подзадачи
.4.1 Правая квазидистрибутивность.
.4.2 Левая квазидистрибутивность.
.5 К вопросу о целях преобразований.
Чистка входных, выходных формальных параметров и
вызовов функций
Чистка повторных определений
.1 Глобальность базисных конфигураций внутри задачи и по задачам
.2 Повторные определения.
Неадекватная выразимость результата преобразований средствами РЕФАЛа5
Разметка свойств переменных и компиляция в Си или в язык сборки
.1 Уменьшение числа копирований
.2 Хвостовая рекурсия
Поднятие параметра уточнение языка параметров. О синтаксисе входных точек
.1 Постановка задач на специализацию.
.2 Подтипы параметров
.2.1 Уточнение прогонки.
.2.2 Уточнение свертки
.3 Синтаксические мономы в задаче самопримеиения.
.4 Язык схем.
Несколько примеров преобразований
.1 Простейшие примеры.
.2 Специализация самоописания РЕФАЛа
.3 Другие эксперименты
О соотношении сложности
.1 Анализ двух примеров.
.2 Общие замечания
.2.1 Простейшая модель суперкомпиляции.
.2.2 Ограничения на стиль программирования.
Разметка входной программы
.1 Псевдокомментарии
.2 Псевдофункции
О свойствах модели вычислений
Общее заключение
Результаты
Список литературы


Д. Джонс (Дания) предложил ослабить первоначально поставленные цели за счёт упрощения методов специализации («partial evaluation») [], []. Эта упрощённая техника «частичных вычислений» наиболее разработана к данному моменту. Она решает первую задачу специализации. Н. Д. Джонс с сотрудниками сделали ещё один принципиальный шаг в сторону упрощения, но теперь уже не постановки задачи, а ограничения подходов к её решению. В университете Копенгагена (И. Д. Джонс, П. Сестофт, X. Сондергаад) в году удалось решить аппроксимирующие задачи самоприменения Копенгагенского частичного вычислителя mix. Здесь следует отметить, что всегда существует сигнализирующая функция времени Т (см. Первые результаты самоприменения mix, содержательно, незначительно отличались от приведённой тривиальной остаточной программы. Н. Д. Джонс в статье года (), длина остаточной программы, полученной в результате решения простейшей задачи самоприменения mix(mix(po,x>y))1 mix по данной трёхстрочной программе ро(х,у), была пятьсот страниц текста. Здесь значения у неизвестны обеим копиям mix: значение аргумента х известно специализируемому mix, но неизвестно специализирующему mix. Анализируя остаточную программу, копенгагенская группа предложила понятия «online» и «offline» методов специализации []. Чуть ниже мы рассмотрим эти понятия. Здесь подчёркивание означает кодировку. Введя инструменты повышения местности («арности») специализируемых программ и их подпрограмм в рамках «offline» подхода, С. А. Романенко [], [], [] удалось в году существенно улучшить временные и структурные характеристики остаточных программ задач самоприменения Московского частичного вычислителя unmix. Название его статьи, описывающей unmix, говорит само за себя «Генератор компиляторов, порожденный самоприменением спсциализатора, может иметь ясную и естественную структуру» []. Offline специализация разделяет в отдельные стадии-проходы анализ исходной программы р и метаинтерпретацию локальных шагов этой программы, выполнение которых может быть выполнено без знания конкретных значений неизвестной части аргументов этих шагов. На вход первой стадии, которая называется связыванием по времени (ВТА2), подаётся р и указание, какие из её аргументов будут известны на второй стадии преобразований (метаиптерпретации), а ею сами значения этих аргументов, и какие неизвестны. Первые называются статическими, вторые - динамическими. На выходе у ВТА размеченная программа р*“1, в которой каждое элементарное действие помечено как статическое, если его можно однозначно проинтерпретировать без знания конкретных значений динамической части входов этих действий-шагов. Biding time analysis. ВТА. Задача, поставленная перед ВТА как таковая, очевидно, алгоритмически неразрешима. Повсюду здесь, по умолчанию, имеется в виду некоторая аппроксимация сформулированной ВТА-задачи. На вход второй стадии, которая собственно и называется, при этом подходе, словом «специализация» подастся результат ВТА - р*™ и значения её статических аргументов. Специализация» (вторая стадия) логически проста и алгоритмизируема; вес содержательные проблемы перенесены в ВТА. Группа Ы. Д. Джонса, как и С. А. Романенко, решили не оригинальную классическую задачу самоирименения, а задачу mix(mixann(pQnn,x,y)) , которая существенно проще классической: обе копии mix производят лишь вторую стадию преобразований, не занимаясь связыванием по времени. Позже эксперименты offline самоирименения Джонса-Романенко повторялись и уточнялись в разных направлениях рядом авторов. Здесь существенно, что входные данные (как статические, так и динамические, представленные параметрами) каждого шага программы просматриваются только один раз (одним проходом) на этапе «специализации» (второй стадии). Online специализация производит метавычисления шагов преобразуемой программы р по ходу дела анализа тех или иных свойств этой программы; никак не ограничивая, вообще говоря, a priori себя ни в средствах, ни в количестве проходов по программе р (или по частям этой программы; например, - по входным данным каждого шага программы). Здесь в задаче решённой С. А. Романенко нужно заменить оба mix па unmix.