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 2016.

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