| Предисловие |
| Введение |
| 1 | Схема структуры преобразователя программ SCP4 |
| 2 | Язык параметров |
| | 2.1. | Параметризованные множества данных |
| | 2.2. | Параметризованные множества полей зрения (стеков) и РЕФАЛ-выражений |
| 3 | Язык РЕФАЛ-графов |
| | 3.1. | Синтаксис |
| | | 3.1.1. | Синтаксис входного подмножества |
| | 3.2. | Семантика |
| | 3.3. | Язык РЕФАЛ-5 и язык РЕФАЛ-графов |
| | | 3.3.1. | О неравномерности шагов РЕФАЛ-машины |
| | | 3.3.2. | Дерево отождествления в языке РЕФАЛ-графов |
| 4 | Прогонка |
| | 4.1. | Общая структура прогонки |
| | 4.2. | Перестройка стека функций |
| | 4.3. | Стратегия выбора входного формата |
| | 4.4. | К вопросу о целях преобразований |
| 5 | Св\"ертка |
| | 5.1. | Вложение |
| | 5.2. | Стратегия обхода дерева при факторизации |
| | 5.3. | Обобщение |
| | | 5.3.1. | Отношение "похожести" |
| | | 5.3.1.1. | Обнинское условие выделения цикла |
| | | 5.3.1.2. | Условие упрощающего отношения |
| | | 5.3.1.3. | Другие условия "похожести" |
| | | 5.3.2. | Обобщение конфигураций |
| | | 5.3.3. | Обобщение параметризованных выражений |
| | | 5.3.4. | Обобщение и построение "отрицательной" информации |
| | | 5.3.5. | Стратегия обхода метадерева при обобщении |
| | | 5.3.6. | Обнинское условие и транзитные вершины |
| | 5.4. | К вопросу о целях преобразований |
| | | 5.4.1. | Изменение местности параметризованной среды при е\"е обобщении |
| 6 | Разв\"ертка |
| | 6.1. | Стратегия развития дерева |
| | 6.2. | Стратегии развития стека функций |
| | 6.3. | К вопросу о целях преобразований |
| 7 | Подграф -- компонента факторизации |
| 8 | Чистка экранируемых ветвей |
| 9 | Глобальный анализ |
| | 9.1. | Анализ в терминах языка РЕФАЛ-графов |
| | | 9.1.1. | Пустые подграфы |
| | | 9.1.2. | Выходные форматы |
| | | 9.1.3. | Графы, определяющие константу |
| | | 9.1.4. | Проекции |
| | 9.2. | Анализ в терминах языка РЕФАЛ |
| | | 9.2.1. | Тождественность |
| | | 9.2.2. | Мономы конкатенации |
| | | 9.2.3. | Стратегия выбора гипотезы мономиальности |
| | | 9.2.4. | Частичные выражения |
| | 9.3. | Чистка поглощаемых ветвей |
| 10 | Использование результатов глобального анализа |
| | 10.1. | Одношаговые подграфы |
| | 10.2. | Пустые подграфы |
| | 10.3. | Рекурсивные подграфы. Повторная специализация |
| | 10.4. | Квази-дистрибутивность подзадачи |
| | | 10.4.1. | Правая квази-дистрибутивность |
| | | 10.4.2. | Левая квази-дистрибутивность |
| | 10.5. | К вопросу о целях преобразований |
| 11 | Чистка входных, выходных формальных параметров и вызовов функций |
| 12 | Чистка повторных определений |
| | 12.1. | Глобальность базисных конфигураций внутри задачи и по задачам |
| | 12.2. | Повторные определения |
| 13 | Неадекватная выразимость результата преобразований средствами РЕФАЛа-5 |
| 14 | Разметка свойств переменных и компиляция в Си (или в язык сборки) |
| | 14.1. | Уменьшение числа копирований |
| | 14.2. | Хвостовая рекурсия |
| 15 | Поднятие параметра (уточнение языка параметров). О синтаксисе входных точек |
| | 15.1. | Постановка задач на специализацию |
| | 15.2. | Подтипы параметров |
| | | 15.2.1. | Уточнение прогонки |
| | | 15.2.2. | Уточнение св\"ертки |
| | 15.3. | Синтаксические мономы в задаче самоприменения |
| | 15.4. | Язык MST-схем |
| 16 | Несколько примеров преобразований |
| | 16.1. | Простейшие примеры |
| | 16.2. | Специализация самоописания РЕФАЛа |
| | 16.3. | Другие эксперименты |
| 17 | О соотношении сложности |
| | 17.1. | Анализ двух примеров |
| | 17.2. | Общие замечания |
| | | 17.2.1. | Простейшая модель суперкомпиляции |
| | | 17.2.2. | Ограничения на стиль программирования |
| 18 | Разметка входной программы |
| | 18.1. | Псевдокомментарии |
| | 18.2. | Псевдофункции |
| 19 | О свойствах модели вычислений |
| Заключение |
| Благодарности |
| Литература |
| Приложение А. Специализация интерпретатора MT по программе умножения натуральных чисел |
Технология программирования естественно развивается в сторону оперирования
понятиями задачи, которая стоит перед программистом, а не понятиями
универсального прибора, на котором программа будет исполняться. Это стимулирует
развитие языков программирования высокого уровня, позволяющих адекватно отражать
объектную область задачи. К таким языкам, например, относятся функциональные
и логические языки (LISP, REFAL, PROLOG, HASKELL, ML, SCHEME и др.), а также
различные языки, специализированные на конкретную область их применения.
С другой стороны, аппаратная реализация современных широко используемых ЭВМ
поддерживает фоннеймановскую модель вычислений, что приводит к неэффективной
реализации таких языков -- посредством интерпретации -- более того, часто
не прямой, а косвенной -- через другую интерпретацию. К подобной неэффективности
приводит и любое структурное программирование само по себе, ибо его целью
является создание гибких, легко понимаемых и изменяемых программ. Все чаще
программы вычисляются другими программами, а потому естественно ожидать, что
первые будут содержать простейшие структуры, ведущие к накладным расходам,
которые никогда бы не допустил квалифицированный программист.
Методы автоматической оптимизации структурированных программ высокого уровня
(а не программ, отшлифованных профессиональными программистами на языках
программирования низкого уровня) и призваны предоставить свободу развития новым
технологиям программирования.
Одним из активно развивающихся здесь направлений является автоматическая
специализация программ. Предположим, что вы купили дистрибутив операционной
системы LINUX. В момент ее установки на вашем компьютере вы должны указать
его аппаратные характеристики, т.е. эти характеристики являются аргументами
программы-установщика. Возникает желание максимально настроить LINUX на ваше
"железо", ибо в другом контексте он вам не понадобится. В этом и состоит задача
специализации. Операционную систему вы устанавливаете однажды, и потому стоит
предложить поработать автоматическому специализатору, даже если его работа
достаточно продолжительна во времени.
Суперкомпияция есть набор методов автоматической специализации программ,
написанных на функциональных языках. Основной механизм суперкомпиляции -- метаинтерпретация. Основополагающие идеи суперкомпиляции, как и сам термин,
были предложены В.Ф.Турчиным в 70-х годах XX века. Но первый реально
работающий свободно распространяемый экспериментальный суперкомпилятор был
создан относительно недавно. Описанию его структуры и принципов работы
и посвящена предлагаемая читателю книга.
Сам факт существования такого суперкомпилятора является значительным шагом
в направлении внедрения технологии суперкомпиляции в практику программного
обеспечения современных компьютеров.
Андрей Петрович НЕМЫТЫХ
В 1984 г. окончил Московский государственный университет им. М.В.Ломоносова,
где учился на механико-математическом факультете. С 1984 г. работает в
Институте программных систем Российской академии наук. Более двадцати лет
занимается проблемами функционального программирования. Основной круг
интересов -- автоматическая специализация программ. Принимал участие в
реализации нескольких диалектов функционального языка программирования
РЕФАЛ. Автор суперкомпилятора SCP4 (специализатора РЕФАЛ-программ), который
разработал и реализовал под руководством В.Ф.Турчина -- автора языка РЕФАЛ.
