Единое окно доступа к образовательным ресурсам

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

Голосов: 0

Данный материал представляет собой дополнительные главы к курсу "Метавычисления и их применение". Материал подготовлен сотрудниками Института программных систем РАН Абрамовым С.М., Парменовой Л.В. Для научных сотрудников и студентов, изучающих методы автоматического преобразования программ или проводящих исследования в данной области. Данная публикация входит в состав <a target=_blank href="http://www.microsoft.com/Rus/Msdnaa/Curricula/">"Библиотеки учебных курсов"</a>, формирование которой ведется в рамках программы академического сотрудничества <a target=_blank href="http://www.microsoft.com/rus/msdnaa/">MSDN Academic Alliance (MSDN AA)</a>.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
             С.М.Абрамов, Л.В.Пармёнова

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


    Данный материал представляет собой дополнительные главы к курсу «Метавычис-
ления и их применение». Материал подготовлен сотрудниками Института программных
систем РАН Абрамовым С.М., Парменовой Л.В.
    Для научных сотрудников и студентов, изучающих методы автоматического преобра-
зования программ или проводящих исследования в данной области.




                                       c 2006 Институт программных систем РАН


Оглавление

1 Введение                                                                                                                                   7
  1.1 Область исследования . . . . . .      .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .    7
  1.2 Система обозначений и понятий         .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .    9
  1.3 Структура изложения . . . . . .       .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .    9
  1.4 FTP-приложение . . . . . . . . .      .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   11

2 Wh—алгоритм обнаружения возможного зацикливания                                                                                           13
  2.1 Упрощающее отношение . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                        .   14
  2.2 Реализация алгоритмa обнаружения возможного зацикливания . . . . .                                                                .   14
      2.2.1 Функция wh—упрощающее сравнение двух c-выражений . . . . .                                                                  .   14
      2.2.2 Алгоритм numprog перенумерации термов исходной программы .                                                                  .   15
      2.2.3 Функция theSameTerm . . . . . . . . . . . . . . . . . . . . . . . . .                                                       .   17
      2.2.4 Функция whConf . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                      .   18
  2.3 Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                  .   19

3 Gener—алгоритм построения тесной общей надконфигурации                                                                                    21
  3.1 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                               .   .   .   21
  3.2 Обобщение c-баз конфигураций . . . . . . . . . . . . . . . . . . . . .                                                    .   .   .   22
      3.2.1 Вспомогательные конструкции и функции . . . . . . . . . . .                                                         .   .   .   22
      3.2.2 Обобщение c-выражений . . . . . . . . . . . . . . . . . . . . .                                                     .   .   .   24
      3.2.3 Обобщение c-сред . . . . . . . . . . . . . . . . . . . . . . . . .                                                  .   .   .   25
  3.3 Функция genTabToSubsts. Построение подстановок sGenUp и sGenDn                                                            .   .   .   26
  3.4 Обобщение рестрикций . . . . . . . . . . . . . . . . . . . . . . . . . .                                                  .   .   .   27
      3.4.1 Общая схема выполнения обобщения рестрикций . . . . . . .                                                           .   .   .   29
      3.4.2 Функция mkRestr . . . . . . . . . . . . . . . . . . . . . . . . .                                                   .   .   .   29
      3.4.3 Функция genRestr. Обобщение рестрикций . . . . . . . . . .                                                          .   .   .   32
  3.5 Функция genConf. Обобщение конфигураций . . . . . . . . . . . . .                                                         .   .   .   32
  3.6 Функция isEqCUpCGen . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                 .   .   .   33
      3.6.1 Функция mkSubstUpDn . . . . . . . . . . . . . . . . . . . . . . .                                                   .   .   .   35
  3.7 Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                              .   .   .   36

4 Суперкомпилятор для языка TSG                                                                                                             37
  4.1 Структура графа конфигураций и основные                           типы данных                     .   .   .   .   .   .   .   .   .   37
      4.1.1 Сведение конфигураций в S-графе .                           . . . . . . . .                 .   .   .   .   .   .   .   .   .   37
      4.1.2 Синтаксис графа конфигураций . . .                          . . . . . . . .                 .   .   .   .   .   .   .   .   .   38
      4.1.3 Nodeinfo—информация о вершине . .                           . . . . . . . .                 .   .   .   .   .   .   .   .   .   39
  4.2 Вспомогательные функции . . . . . . . . . .                       . . . . . . . .                 .   .   .   .   .   .   .   .   .   39

                                                3


4                                                                                   Оглавление

    4.3   Входные данные суперкомпилятора . . . . . . . . . . . . . . . . . . .          .   .   .   40
    4.4   Развитие вершины . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     .   .   .   40
          4.4.1 Функция evalG. Построение пассивной вершины . . . . . . .                .   .   .   40
          4.4.2 Функция drive. Прогонка непассивной вершины на один шаг                  .   .   .   41
          4.4.3 Функция procDR. Анализ результатов прогонки . . . . . . . .              .   .   .   42
          4.4.4 Функция mkDbr. Построение ветвей продолжений . . . . . . .               .   .   .   46
          4.4.5 Функция procWh. Обработка возможного зацикливания . . .                  .   .   .   47
    4.5   Функции вывода результата суперкомпиляции . . . . . . . . . . . . .            .   .   .   48
    4.6   Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   .   .   .   49

5 Примеры суперкомпиляции                                                                            51
  5.1 Специализация программ . . . . . . . . . . . . . . . . . . . . . . . . . .             .   .   51
      5.1.1 Суперкомпиляция как метод специализации программ . . . . .                       .   .   52
  5.2 Специализация: KMP-тест . . . . . . . . . . . . . . . . . . . . . . . . .              .   .   55
      5.2.1 Пример 1. Поиск подстроки “AAB” в произвольной строке . . .                      .   .   55
      5.2.2 Пример 2. Поиск подстроки “AABAAC” в произвольной строке                         .   .   56
      5.2.3 Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .           .   .   60
  5.3 Проекции Футамуры-Турчина . . . . . . . . . . . . . . . . . . . . . . .                .   .   60
      5.3.1 Определение проекций Футамуры-Турчина . . . . . . . . . . .                      .   .   60
      5.3.2 Компиляция конечных автоматов auto1 и auto2 в TSG . . . . .                      .   .   62
      5.3.3 Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .           .   .   69

6 Заключение                                                                                         71

Литература                                                                                           73


Список иллюстраций

 2.1   Функция     wh—упрощающее сравнение двух c-выражений                           .   .   .   .   .   .   .   .   .   .   15
 2.2   Функция     numterm . . . . . . . . . . . . . . . . . . . . . .                .   .   .   .   .   .   .   .   .   .   16
 2.3   Функция     numdefs . . . . . . . . . . . . . . . . . . . . . .                .   .   .   .   .   .   .   .   .   .   16
 2.4   Функция     numprog . . . . . . . . . . . . . . . . . . . . . .                .   .   .   .   .   .   .   .   .   .   17
 2.5   Функция     theSameTerm . . . . . . . . . . . . . . . . . . . .                .   .   .   .   .   .   .   .   .   .   17
 2.6   Функция     whConf . . . . . . . . . . . . . . . . . . . . . . .               .   .   .   .   .   .   .   .   .   .   18

 3.1  Функция gLookUp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                         23
 3.2  Функции isAExp и isAtom . . . . . . . . . . . . . . . . . . . . . . . . . . .                                           23
 3.3  Функция genCExp. Обобщение c-выражений . . . . . . . . . . . . . . . . .                                                24
 3.4  Функция genCEnv. Обобщение c-сред . . . . . . . . . . . . . . . . . . . . .                                             25
 3.5  Функция genTabToSubsts. Построение подстановок sGenUp и sGenDn по
      таблице обобщений t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                         27
 3.6 Функция mkRestr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                          31
 3.7 Функция genRestr. Обобщение рестрикций . . . . . . . . . . . . . . . . .                                                 32
 3.8 Функция genConf. Обобщение конфигураций . . . . . . . . . . . . . . . .                                                  33
 3.9 Функция isEqCUpCGen. Проверка вложения конфигураций: cUp                 cDn .                                           34
 3.10 Функция mkSubstUpDn. Построение подстановки sUpDn, приводящей кон-
      фигурацию cUp к cDn (для случая cUp        cDn) . . . . . . . . . . . . . . .                                           35

 4.1  Вспомогательные функции для сведения конфигурации . . . . . . . . . .                                                   38
 4.2  Вспомогательные функции суперкомпилятора . . . . . . . . . . . . . . . .                                                39
 4.3  Суперкомпилятор. Функция scp . . . . . . . . . . . . . . . . . . . . . . . .                                            40
 4.4  Суперкомпилятор. Функция evalg . . . . . . . . . . . . . . . . . . . . . .                                              41
 4.5  Суперкомпилятор. Функция drive . . . . . . . . . . . . . . . . . . . . . .                                              42
 4.6  Функция delEmptyDBr—удаление сухих ветвей в списке вариантов про-
      гонки вершины . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                       42
 4.7 Функция procDR. Анализ результатов прогонки . . . . . . . . . . . . . . .                                                43
 4.8 Вариант функции procDR, поддерживающий различные стратегии работы
      с транзитными вершинами . . . . . . . . . . . . . . . . . . . . . . . . . . .                                           45
 4.9 Функция mkDbr. Построение ветвей продолжений . . . . . . . . . . . . . .                                                 46
 4.10 Функция procWh. Обработка возможного зацикливания . . . . . . . . . .                                                   48

 5.1   KMP   для   строки   "AB". Функция "F2". . . .     .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   56
 5.2   KMP   для   строки   "AB", функция "F11" . . .     .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   57
 5.3   KMP   для   строки   "AABAAC". Функция "F2" .      .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   58
 5.4   KMP   для   строки   "AABAAC". Функция "F21"       .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   59
 5.5   KMP   для   строки   "AABAAC". Функция "F31"       .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   61

                                              5


6                                                                     Список иллюстраций

    5.6    Интерпретатор языка конечных автоматов, функции        auto и loop       .   .   .   .   63
    5.7    Интерпретатор языка конечных автоматов, функция        NewState . .      .   .   .   .   64
    5.8    Интерпретатор языка конечных автоматов, функция        NewStateDef       .   .   .   .   65
    5.9    Конечные автоматы auto1 и auto2 . . . . . . . . . .    . . . . . . . .   .   .   .   .   66
    5.10   Функции для записи выражений . . . . . . . . . . . .   . . . . . . . .   .   .   .   .   66
    5.11   Функция "F2" для автомата auto1 . . . . . . . . . .    . . . . . . . .   .   .   .   .   67
    5.12   Функция "F2" для автомата auto2 . . . . . . . . . .    . . . . . . . .   .   .   .   .   68
    5.13   Функция "F18" для автомата auto2 . . . . . . . . . .   . . . . . . . .   .   .   .   .   68


Глава 1

Введение

1.1           Область исследования
   Данная работа относится к теории и практике метавычислений. Метавычисления—
это раздел программирования, посвященный разработке методов анализа и преобразо-
вания программ за счет реализации конструктивных метасистем (метапрограмм) над
программами. В метавычисления в первую очередь включают теорию суперкомпиля-
ции и близкие методы и средства [6, 9, 14, 17, 18, 4, 3]. Приставка “мета” указывает
на то, что программа в метавычислениях рассматривается как объект анализа и/или
преобразования.
   Первые работы по метавычислениям были выполнены В.Ф.Турчиным, при участии
других членов московской Рабочей группы по языку Рефал, в 1970-тых годах [6, 8, 9].
Базовыми идеями данных работ являлись:

          • применение теории метасистем и метасистемных переходов [7, 9, 20, 7];

          • процесс-ориентированный подход к построению методов анализа и преобразова-
            ния программ—разработка метапрограмм, которые “наблюдают” за процессами
            вычисления исходной программы и управляют ими;

          • использование языка программирования Рефал [13] и его диалектов в качестве
            языка реализации метапрограмм и программ, над которыми выполняются мета-
            вычисления.

   Рассмотрим подробнее основные принципы разрабатываемых в данных работах ме-
тодов.
   Для проведения метавычислений над некоторой программой p вводится в рассмот-
рение метапрограмма M, для которой программа p является объектом анализа, преоб-
разования и т.п. Метапрограмма M должна быть способна анализировать процессы вы-
полнения программы p на конкретных данных d и на классах (множествах) C данных.
По сути, метапрограмма M наблюдает за множеством процессов1 выполнения програм-
мы p и управляет данными процессами. Таким образом, M является метасистемой по
отношению к системе p. Именно из результатов наблюдения за процессами выполнения
      1
          Процесс-ориентированность—одна из принципиальных отличительных черт подхода В.Ф.Турчи-
на.

                                                  7


8                                                               Глава 1. Введение

программы p метапрограмма M определяет наличие тех или иных свойств программы
p, выводит возможность применения того или иного преобразования программы.
    Для построения методов анализа процессов выполнения программ необходимо опре-
делить и зафиксировать некоторый язык программирования R—язык реализации. Все
программы p, к которым можно применять метапрограмму M, должны быть написаны
на языке R. Если сама метапрограмма M будет написана на языке R, то будет возможно
применить к ней ее самою (самоприменение) или другие метапрограммы. Это откры-
вает возможность автоматического выполнения нескольких метасистемных переходов.
На практике это означает возможность автоматических кардинальных преобразова-
ний программ—как эквивалентных преобразований, так и построение новых программ,
функции которых сложным образом определяются через функции исходных программ.
    Главные усилия большинства работ по метавычислениям были направлены на раз-
работку суперкомпилятора [8, 12]. Эти усилия оказались плодотворными—в послед-
нее время появились первые реализации суперкомпилятора [11, 21, 22], демонстриру-
ющие на практике нетривиальные примеры метавычислений, принципиальная осуще-
ствимость которых была показана еще в первых работах по метавычислениям.
    Стремление к скорейшему завершению работ по созданию теории суперкомпиляции
и практической реализации суперкомпилятора привело к тому, что некоторые мето-
ды метавычислений и некоторые вопросы применения метавычислений в практическом
программировании были недостаточно исследованы.
    Во многом указанный пробел был закрыт работой [3], которая была посвящена сле-
дующим вопросам:

    1. Базовые понятия метавычислений.

    2. Разработка и исследование окрестностного анализа—одной из разновидностей
       метавычислений.

    3. Применение окрестностного анализа в тестировании программ. Построение и ис-
       следование свойств нового метода тестирования программ—окрестностного те-
       стирования.

    4. Изучение инвертирования программ, основанного на использовании одного из
       средств метавычислений—универсального решающего алгоритма, УРА. Введение
       понятий инверсной семантики и инверсного программирования.

    5. Исследование понятия нестандартная семантика языка программирования. Ана-
       лиз окрестностного тестирования и инверсного программирования как двух при-
       меров нестандартных семантик. Исследование возможности автоматического по-
       лучения при помощи метавычислений эффективных реализаций нестандартных
       семантик.

   Таким образом, в работе [3] дан систематическое описание базовых понятий мета-
вычислений и показано, что даже простейшие метапрограммы способны реализовать
нетривиальные методы анализа и преобразования программ. Однако, вопросы теории
и практики суперкомпиляции (из которых и начала формироваться теория метавычис-
ления) остались за рамками рассмотрения данной работы.


1.2. Система обозначений и понятий                                                          9

Цель и задачи исследования. Главной целью данной работы являлось разработка
дополнения к [3], которое бы основываясь на стиле, системе обозначений и базовых
понятиях из [3] было бы посвящено вопросам теории суперкомпиляции и примерам
использования суперкомпилятора.
   Данная цель подразумевает решение следующих задач:

  1. Разработку, реализацию, описание и обоснование суперкомпилятора для языка
     TSG (использующего базовые понятия метавычислений над TSG из работы [3]),
     что включает:

      (a) Разработку алгоритма обнаружения возможного зацикливания.
      (b) Разработку алгоритма обобщения двух конфигураций cUp и cDn.
       (c) Разработку алгоритма проверки вложенности двух конфигураций cUp cDn.
      (d) Разработку (на базе упомянутых выше в пунктах 1a–1c функциональных бло-
          ков и с использованием алгоритмов из [3]) собственно алгоритма суперком-
          пилятора.

  2. Проведение и описание реальных примеров суперкомпиляции, призванных проде-
     монстрировать способность выполнения суперкомпилятором нетривиальных глу-
     боких преобразований программ.


1.2     Система обозначений и понятий
   Как и в [3] в данной работе в качестве языка реализации (для которого строит-
ся суперкомпилятор) используется язык TSG—простой и компактный алгоритмически
полный язык. Простота TSG и предметной области языка позволяет значительно упро-
стить изложение методов суперкомпиляции для TSG, в то же время не упуская ни
одного существенного момента.
   Заметим, что все построения и рассуждения могут быть повторены и для любого
другого языка реализации, если он удовлетворяет тем свойствам, которые существенно
использовались в алгоритмах метавычислений и в доказательствах свойств этих алго-
ритмов2 .
   В данной работе широго используются терминология, понятия, алгоритмы и утвер-
ждения из [3]. В некотором смысле, данная работа является продолжением (второй
частью) книги [3]. Тем самым, предполагается глубокое знание читателем материала
работы [3].


1.3     Структура изложения
   В главе 2 описан алгоритм (один из возможных вариантов) Wh, реализующий обна-
ружение возможного зацикливания суперкомпилятора—то есть, обнаружение ситуации
похожей на построение суперкомпилятором в графе конфигураций бесконечной ветви.
  2
   В данной работе во всех построениях используются только следующие свойства языка TSG: алго-
ритмическая полнота языка и определение предметной области языка при помощи конечного набора
жестких конструкторов над конечным алфавитом атомов.


10                                                              Глава 1. Введение

   В нашем проекте реализован алгоритм (функция whConf), основанный на упроща-
ющем сравнении ( ) двух конфигураций. Если на некоторой ветви (начинающейся в
корне) графа конфигураций обнаруживаются две вершины с конфигурациями cUp и
cDn (cUp—предок cDn) такие, что:
       (cDn     cUp) == True
то считают, что конфигурация cDn и cUp опасно похожи (опасно близки друг к дру-
гу), и следует объявить ситуацию возможно зацикливание суперкомпилятора в случае
продолжения построения данной ветви.
   В главе 3 рассмотрен алгоритм обобщения двух конфигураций Gener. Показано,
что обобщение двух конфигураций реализуется в две фазы: обобщение баз конфигура-
ций и обобщение рестрикций конфигураций.
   Первая фаза реализована при помощи известного алгоритма least common generati-
on, запрограммированного с учетом конструкции конфигураций для языка TSG.
   Для реализации второй фазы разработан и обоснован алгоритм обобщения рестрик-
ций, используемых для TSG.
   В результате получен алгоритм обобщения, обладающий следующим свойством: если
выполнено cUp      cDn, то в результате обобщения будет построена конфигурация
cGen, совпадающая с cUp с точностью до переименования c-переменных .
   Данное свойство реализованного алгоритма обобщения:
     • Демонстрирует, что он строит тесные обобщения конфигураций.
     • Позволяет легко реализовать проверку условия cUp   cDn за счет анализа ре-
       зультатов работы алгоритма обобщения (функция isEqCUpCGen).
   Тем самым, в данном проекте проверка условия cUp    cDn была отнесена к модулю
обобщения, что позволило упростить структуру суперкомпилятора.
   В главе 4 введен синтаксис представления графа конфигураций (S-графа) для TSG,
рассмотрена операция сведения двух конфигураций в S-графе, определены вспомога-
тельные синтаксические конструкции и функции для суперкомпилятора.
   Затем, определен и обсужден собственно суперкомпилятор для языка TSG, основан-
ный на идее выполнения обобщения конфигураций в нижней конфигурации (в ситуации
возможное зацикливание). Данный суперкомпилятор использует алгоритмы Wh и Gener
(определенные в главах 2 и 3) и алгоритмы, функции и операции из [3].
   В завершении главы 4 рассмотрены вспомогательные функции, предназначенные
для вывода результата суперкомпиляции (графа конфигураций) в читабельном виде (в
виде TSG-программы).
   В главе 5 рассмотрены и проанализированы две группы примеров суперкомпиля-
ции TSG-программ разработанным суперкомпилятором:
     1. Примеры суперкомпиляции алгоритма pmatch на классах вида
              (([string , E.1), [ ]),
       где string —некоторая константная строка.
       Рассмотренные примеры позволяют сделать следующий вывод: реализованный
       по проекту суперкомпилятор способен выполнять нетривиальную специализацию
       программ.



    
Яндекс цитирования Яндекс.Метрика