Введение
1 Анализ результатов диссертации в контексте исследований в области специализации программ 24
1.1 О двух постановках задачи специализации 25
1.2 Обзор результатов в области специализации программ . 27
1.3 Исторический обзор развития методов суперкомпиляции . 34
2 Схема структуры преобразователя программ SCP4 45
3 Язык параметров 55
3.1 Параметризованные множества данных 55
3.2 Параметризованные множества полей зрения (стеков) и РЕФАЛ-выражений 58
4 Язык РЕФАЛ-графов 60
4.1 Синтаксис 60
4.1.1 Синтаксис входного подмножества 63
4.2 Семантика 63
4.3 Язык РЕФАЛ-5 и язык РЕФАЛ-графов 66
4.3.1 О неравномерности шагов РЕФАЛ-машины 66
4.3.2 Дерево отождествления в языке РЕФАЛ-графов 70
5 Прогонка 72
5.1 Общая структура прогонки 73
5.2 Перестройка стека функций 84
5.3 Стратегия выбора входного формата 85
5.4 К вопросу о целях преобразований 86
6 Свёртка 91
6.1 Вложение 92
6.2 Стратегия обхода дерева при факторизации 97
6.3 Обобщение 99
6.3.1 Отношение «похожести» 101
6.3.2 Обобщение конфигураций 107
6.3.3 Обобщение параметризованных выражений 112
6.3.4 Обобщение и построение «отрицательной» информации . ИЗ
6.3.5 Стратегия обхода метадерева при обобщении 117
6.3.6 Обнинское условие и транзитные вершины 118
6.4 К вопросу о целях преобразований 120
6.4.1 Изменение местности параметризованной среды при
её обобщении 124
7 Развёртка 129
7.1 Стратегия развития дерева 130
7.2 Стратегии развития стека функций 130
7.3 К вопросу о целях преобразований 132
8 Подграф - компонента факторизации 135
9 Чистка экранируемых ветвей 137
10 Глобальный анализ 139
10.1 Анализ в терминах языка РЕФАЛ-графов 140
10.1.1 Пустые подграфы 141
10.1.2 Выходные форматы 143
10.1.3 Графы определяющие константу 146
10.1.4 Проекции 147
10.2 Анализ в терминах языка РЕФАЛ 147
10.2.1 Тождественность 149
10.2.2 Мономы конкатенации 152
10.2.3 Стратегия выбора гипотезы мономиальности 162
10.2.4 Частичные выражения 165
10.3 Чистка поглощаемых ветвей 168
Том II 170
11 Использование результатов глобального анализа 171
11.1 Одношаговые подграфы 171
11.2 Пустые подграфы 172
11.3 Рекурсивные подграфы. Повторная специализация 172
11.4 Квази-дистрибутивность подзадачи 176
11.4.1 Правая квази-дистрибутивность 177
11.4.2 Левая квази-дистрибутивность 179
11.5 К вопросу о целях преобразований 180
12 Чистка входных, выходных формальных параметров и вызовов функций 188
13 Чистка повторных определений 193
13.1 Глобальность базисных конфигураций внутри задачи и по задачам 193
13.2 Повторные определения 194
14 Неадекватная выразимость результата преобразований средствами РЕФАЛа-5 198
15 Разметка свойств переменных и компиляция в Си (или в язык сборки) 202
15.1 Уменьшение числа копирований 202
15.2 Хвостовая рекурсия 205
16 Поднятие параметра (уточнение языка параметров). О синтаксисе входных точек 208
16.1 Постановка задач на специализацию 208
16.2 Подтипы параметров 212
16.2.1 Уточнение прогонки 213
16.2.2 Уточнение свёртки 217
16.3 Синтаксические мономы в задаче самопримеиения 217
16.4 Язык MST-схем 220
17 Несколько примеров преобразований 227
17.1 Простейшие примеры 227
17.2 Специализация самоописания РЕФАЛа 242
17.3 Другие эксперименты 259
18 О соотношении сложности 262
18.1 Анализ двух примеров 262
18.2 Общие замечания 272
18.2.1 Простейшая модель суперкомпиляции 275
18.2.2 Ограничения на стиль программирования 279
19 Разметка входной программы 281
19.1 Псевдокомментарии 281
19.2 Псевдофункции 286
20 О свойствах модели вычислений 288 Общее заключение 291
21 Результаты 298
Список литературы
