URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог
Обложка Немытых А.П. Суперкомпилятор SCP4: Общая структура
Id: 55806
 
299 руб.

Суперкомпилятор SCP4: Общая структура

URSS. 2007. 152 с. Мягкая обложка. ISBN 978-5-382-00365-8.

На основе технологии суперкомпиляции автор реализовал преобразователь функциональных программ SCP4. SCP4 реализован на функциональном языке программирования Рефал-5. Этот же язык является и входным языком для SCP4. В работе мы рассматриваем общую структуру суперкомпилятора SCP4 и показываем несколько примеров преобразований посредством SCP4.

Nemytykh Andrei Petrovich

The Supercompiler SCP4: General Structure

The author constructed a transformer SCP4 of functional programs. The transformer uses the technology known as Turchin's supercompilation. SCP4 was implemented in a functional language Refal-5. The input language for SCP4 is also Refal-5. In the book we consider the general structure of the supercompiler and give a number of examples of transformations.


Оглавление
Предисловие
Введение
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 (специализатора РЕФАЛ-программ), который разработал и реализовал под руководством В.Ф.Турчина -- автора языка РЕФАЛ.

 
© URSS 2017.

Информация о Продавце