Абрамов С.М. Методы метавычислений и их применение

Подождите немного. Документ загружается.

С.М.АбрамовС.М.Абрамов

етавычисления

их применение

етавычисления

их применение

ММ

С.М.Абрамов

Метавычисления

и их применение

ББК 32.97

C72

УДК 681.322

Абрамов С.М.

Методы метавычислений и их применение.—Издание второе, дополнен-

ное и переработанное, Переславль-Залесский, Издательство «Университет

города Переславля имени А.К.Айламазяна», 2006.—128 с., ил.

Книга сотрудника Института программных систем РАН, представляющая собой опи-

сание вопросов теории метавычислений и их применения. Метавычисления—раздел теории

и практики программирования, посвященный разработке методов анализа и преобразова-

ния программ за счет реализации конструктивных метасистем (метапрограмм) над про-

граммами. В книге приводятся основные понятия метавычислений, примеры построения и

использования простых метапрограмм. Изложение рассчитано на специалистов в области

программирования.

Для научных сотрудников и студентов, изучающих методы автоматического преобра-

зования программ или проводящих исследования в данной области.

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

Оглавление

Введение 7

1 Язык реализации 13

1.1 Данные в языке TSG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.2 Синтаксис языка TSG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3 Семантика я зыка TSG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 Представление множеств 21

2.1 C-переменные, c-выражения . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2 C-связи, c-среды и c-состояния . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.3 Рестрикции c-переменных . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.4 C-конструкции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.5 Подстановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.6 Отождествление c-выражений . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.7 Представляемое множество . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.8 Суперпозиция подстановок . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.9 Сужения и разбиения множеств . . . . . . . . . . . . . . . . . . . . . . . . 38

3 Дерево процессов 45

3.1 Дерево конфигураций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.2 Построение дерева процессов . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4 Окрестностный анализ 55

4.1 Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.2 Окрестности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.3 Окрестностный анализатор . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

4.4 Операции над классами и окрестно стями . . . . . . . . . . . . . . . . . . . 66

5 Окрестностное тестирование программ 73

5.1 Tестированиe. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . 73

5.2 Постановка проблемы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

5.3 Построение окрестностного тестирования . . . . . . . . . . . . . . . . . . 78

5.4 Окрестностный критерий выбора тестов . . . . . . . . . . . . . . . . . . . 81

5.5 Свойства окрестностного тестирования . . . . . . . . . . . . . . . . . . . . 82

5.6 Решение традиционных проблем теории тестирования . . . . . . . . . . . 83

4 Оглавление

6 Универсальный решающий алгоритм 91

6.1 Постановка проблемы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

6.2 Приведение функции программы к табличной форме . . . . . . . . . . . . 92

6.3 Алгоритм инверсного вычисления программ . . . . . . . . . . . . . . . . . 95

6.4 Различные подходы к инверсии программ . . . . . . . . . . . . . . . . . . 99

7 Инверсное программирование 101

7.1 Инверсная семантика языка реализации . . . . . . . . . . . . . . . . . . . 101

7.2 Инверсное и логическое программирова ние . . . . . . . . . . . . . . . . . 102

7.3 Перенос инверсной семантики . . . . . . . . . . . . . . . . . . . . . . . . . 109

8 Нестандартные семантики 113

8.1 Модификаторы семант ик . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

8.2 Специализация программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

8.3 Эффективная реализация нестандартных языков . . . . . . . . . . . . . . 119

Литература 121

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

1.1 Синтаксис данных и программ в языке TSG . . . . . . . . . . . . . . . . . 14

1.2 Программа проверки вхождения подстроки в строку . . . . . . . . . . . . 15

1.3 Синтаксис среды в языке TSG . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.4 Вспомогательные функции интерпретатора языка TSG . . . . . . . . . . 18

1.5 Интерпретатор языка TSG . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.1 Синтаксис c-переменных и c-выражений . . . . . . . . . . . . . . . . . . . 22

2.2 Синтаксис c-сост ояния, c-среды и c-связи . . . . . . . . . . . . . . . . . . . 23

2.3 Рестрикции c-переменных . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.4 C-конструкции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.5 Подстановка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.6 Алгоритм отождествления списков c-в ыражений . . . . . . . . . . . . . . 32

2.7 Синтаксис сужения для языка TSG . . . . . . . . . . . . . . . . . . . . . . 38

2.8 Определение отношения < на множестве c-выражений . . . . . . . . . . . 42

3.1 Синтаксис представления дерева конфигураций . . . . . . . . . . . . . . . 46

3.2 Алгоритм построения дерева процессов. Функции pt r и eval T . . . . . . 47

3.3 Алгоритм построения дерева процессов. Функция ccond . . . . . . . . . . 48

3.4 Улучшенный алгоритм построения дерева процессов . . . . . . . . . . . . 52

4.1 Вспомогательная функция mkCExps . . . . . . . . . . . . . . . . . . . . . . 58

4.2 Окрестностный анализатор для языка TSG . . . . . . . . . . . . . . . . . 60

4.3 Пересечение и разно сть классо в . . . . . . . . . . . . . . . . . . . . . . . . 67

4.4 Декомпозиция о крестност и . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

4.5 Алгоритм декомпозиции окрестност и . . . . . . . . . . . . . . . . . . . . . 70

5.1 Процесс тестирования программы . . . . . . . . . . . . . . . . . . . . . . . 75

5.2 Конечно-автоматное преобразование строки . . . . . . . . . . . . . . . . . 77

5.3 Синтаксис конструкций языка JobSL . . . . . . . . . . . . . . . . . . . . . 86

5.4 Программа corr(ϕ,p,ψ) на языке JobSL . . . . . . . . . . . . . . . . . . . 87

5.5 Вспомогательные функции интерпретатора языка J obS L . . . . . . . . . . 87

5.6 Интерпретатор языка Jo bS L . . . . . . . . . . . . . . . . . . . . . . . . . . 88

6.1 Алгоритм построения табличной формы функции . . . . . . . . . . . . . 94

6.2 Алгоритм инверсного вычисления программ . . . . . . . . . . . . . . . . . 97

6.3 Альтернативное представление результатов инверсного вычисления . . . 98

7.1 Синтаксис представления графов, пример представления . . . . . . . . . 105

7.2 Алгоритм инверсного вычисления в произвольном языке L . . . . . . . . 111

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

С благодарностью посвящается Учителю

Валентину Федоровичу Турчину

Введение

В 19 75 году автору данной работы, тогда студенту, посчастливилось быть вовле-

ченным в работу неформальной Московской рефал-группы и позна комиться с руко-

водителем группы, замечательным ученым и человеком В.Ф.Турчиным. Рефал-группа

занималась разработкой теории метавычислений и практической реализацией средств

метавычислений для языка Рефал. С тех пор теория и практика метавычислений стали

главными научными интересами автора, чему он всегда будет обязан В.Ф.Турчину и

всем участникам рефа л-группы.

В данной работе рассмотрены различные результаты, полученные в теории и прак-

тике метавычислений. Это не означает, что здесь соб раны все результаты. Даже, наобо-

рот, самая большая (самая интересная, но и самая сложная) часть—теория суперкомпи-

ляции—осталась за рамками рассмотрения. Здесь главное внимание было уделено ос-

новным, общим для различных метапрограмм, понятиям, пост роению простейших ме-

тапрограмм и демонстрации того, чего можно достичь применением даже этих триви-

альных метапрограмм в т еорет ическом и практическом программировании.

Было бы ошибкой считать, что представлены только результаты, полученные самим

автором. Некоторые результаты принадлежат В.Ф.Турчину, некоторые—участникам

рефал-группы, некоторые—автору данной работы, а остальные были получены в дис-

куссиях на рефал-семинарах, то есть в условиях, когда установить конкретное автор-

ство достаточно тяжело. Тем не менее, в дополнительных материалах [FTP ]

к данной

работе среди прочего приводится список ссылок на авторов идей и результатов, вклю-

ченных в да нную книгу.

В последнии годы исследователи за рубежом, которые занимались в близких об-

ластях (например, смешанными вычислениями), проявляют большой интерес к теории

метавычислений Турчина. Отрадно видеть, что и на родине теории (даже в нынешнее

время) интерес к ней сохранился. Более того, к данной работе присоединяются новые

научные силы. Особенно приятно, что в Институте программных систем РАН склады-

вается коллектив исследователей, активно занимающихся теорией и практикой мета-

вычислений, и что эта работа выполняется в тесном сотрудничестве с В.Ф.Турчиным.

Хочу выразить свою благодарность Институту за то, что он всегда признавал важность

данных работ и поддерживал их. Так и с этой книгой—без поддержки Института она

бы не состоялась.

Основное содержание работы

В данной работе рассматриваются вопросы т еории метавычислений и примеры ис-

пользования методов метавычислений. Мета вычисления—это раздел теории и практики

программирования, посвященный разработке методов анализа и преобразования про-

грамм за счет реализации конструктивных метасистем (метапрограмм) над программа-

ми. В метавычисления в первую очередь включают теорию суперкомпиляции и близкие

О дополнительных материалах [FTP]—см. в конце Введения.

8 Введение

методы и средства [1, 4, 10, 14, 1 5, 35]. Пристав ка “мета” указывает на то, что программа

в метавычислениях ра ссматрив ает ся как объект анализа и/или преобразования.

Первые работы по метавычислениям были выполнены В.Ф.Турчиным, при участии

других членов московской Рабочей группы по языку Рефал, в 1970-тых годах [1, 3, 4].

Базовыми идеями данных ра бо т являлись :

• применение теории метасистем и метасистемных переходов [2, 4, 19, 2];

• процесс-ориентированный подход к построению методов анализа и преобразова-

ния программ—разработка метапрограмм, которые “наблюдают” за процессами

вычисления исходной программы и управляют ими;

• использование языка программирования Рефал [8] и его диалектов в качестве

языка реализации метапрограмм и программ, над которыми выполняются мета-

вычисления.

Рассмотрим подробнее основные принципы разрабатываемых в данных работах ме-

тодов.

Для проведения метавычислений над некоторой программой p вводится в рассмот-

рение метапрограмма M, для которой программа p является объектом анализа, преоб-

разования и т.п. Метапрограмма M должна быть способна анализировать процессы вы-

полнения программы p на конкретных данных d и на классах (множествах) C данных.

По сути, метапрограмма M наблюдает за множеством процессов

выполнения програм-

мы p и управляет данными процессами. Таким образом, M является метасистемой по

отношению к системе p. Именно из результатов наблюдения за процессами выполнения

программы p метапрограмма M определяет наличие тех или иных св ойст в программы

p, выводит возможность применения того или иного преобразования программы.

Для построения методов анализа процессов выполнения программ необходимо опре-

делить и зафиксировать некоторый язык программирования R—язык реализации. Все

программы p, к которым можно применять метапрограмму M, должны быть написаны

на языке R. Если сама метапрограмма M будет написана на языке R, то будет возможно

применить к ней ее самою (самоприменение) или другие метапрограммы. Это откры-

вает возможность автоматического выполнения нескольких метасистемных переходов.

На практике это означает возможность автоматических кардинальных преобразова-

ний программ—как эквивалентных преобразований, так и построение новых программ,

функции которых сложным образом определяются через функции исходных программ.

Главные усилия б оль шинства работ по метавычислениям были направлены на раз-

работку суперкомпилятора [3, 7]. Эти усилия оказались плодотворными—в последнее

время появились первые реализации суперкомпилятора [5, 21, 22], демонстрирующие на

практике нетривиальные примеры метавычислений, принципиальная осуществимость

которых была показана еще в первых работах по метавычислениям.

Стремление к скорейшему завершению работ по созданию теории суперкомпиляции

и практической реализации суперкомпилятора привело к тому, что некоторые мето-

ды метавычислений и некоторые вопросы применения метав ычислений в практическом

программировании были недостаточно исследованы. Желание хотя бы ча стично за-

крыть данный пробел и привело к появлению этой работы.

Процесс-ориентированность—одна из принцип иальн ых отличительных черт подхода В.Ф.Турчи-

на.