Метавычисления и их применение. Суперкомпиляция: Учебник

Данный материал представляет собой дополнительные главы к курсу ''Метавычисления и их применение''. Материал подготовлен сотрудниками Института программных систем РАН Абрамовым С.М., Парменовой Л.В. Для научных сотрудников и студентов, изучающих методы автоматического преобразования программ или проводящих исследования в данной области. Данная публикация входит в состав ''Библиотеки учебных курсов'' , формирование которой ведется в рамках программы академического сотрудничества MSDN Academic Alliance (MSDN AA) Область исследования......Page 9 Структура изложения......Page 11 FTP-приложение......Page 13 Wh---алгоритм обнаружения возможного зацикливания......Page 15 Функция wh---упрощающее сравнение двух c-выражений......Page 16 Алгоритм numprog перенумерации термов исходной программы......Page 17 Функция theSameTerm......Page 19 Функция whConf......Page 20 Выводы......Page 21 Постановка задачи......Page 23 Вспомогательные конструкции и функции......Page 24 Обобщение c-выражений......Page 26 Обобщение c-сред......Page 27 Функция genTabToSubsts. Построение подстановок sGenUp и sGenDn......Page 28 Обобщение рестрикций......Page 29 Функция mkRestr......Page 31 Функция genConf. Обобщение конфигураций......Page 34 Функция isEqCUpCGen......Page 35 Функция mkSubstUpDn......Page 37 Выводы......Page 38 Сведение конфигураций в S-графе......Page 39 Синтаксис графа конфигураций......Page 40 Вспомогательные функции......Page 41 Функция evalG. Построение пассивной вершины......Page 42 Функция drive. Прогонка непассивной вершины на один шаг......Page 43 Функция procDR. Анализ результатов прогонки......Page 44 Функция mkDbr. Построение ветвей продолжений......Page 48 Функция procWh. Обработка возможного зацикливания......Page 49 Функции вывода результата суперкомпиляции......Page 50 Выводы......Page 51 Специализация программ......Page 53 Суперкомпиляция как метод специализации программ......Page 54 Пример 1. Поиск подстроки ``AAB'' в произвольной строке......Page 57 Пример 2. Поиск подстроки ``AABAAC'' в произвольной строке......Page 58 Определение проекций Футамуры-Турчина......Page 62 Компиляция конечных автоматов auto1 и auto2 в TSG......Page 64 Выводы......Page 71 Заключение......Page 73 Литература......Page 75