WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

В шестой главе описываются алгоритмы свёртки метадерева возможных вычислений преобразуемой программы p. Подробно рассматриваются принципы стратегий, на которых основаны эти алгоритмы. Алгоритмы свёртки являются критическими алгоритмами, суперкомпиляции с точки зрения успешной оптимизации по времени программыp: именно они (вместе с алгоритмами глобального анализа) аппроксимируют решение задачи специализации как таковой. Опорными узлами в метадереве возможных вычислений программы p называются узлы, которые могут быть объявлены входными точками функцийподпрограмм остаточной программы.

Алгоритмы свёртки, в частности, включают в себя:

• Механизм выделения функции-цикла в результате анализа последовательности параметризованных стеков, находящихся в опорных узлах метадерева развертки вдоль пути от корня этого дерева к текущему (анализируемому) узлу (Глава 6).

• Алгоритмы вложения (раздел 6.1) и обобщения параметризованных конфигураций (раздел 6.1).

• Обнинский алгоритм расщепления стека функций, принадлежащий В. Ф. Турчину (раздел 6.3.1.1).

• Алгоритм расщепления данной задачи на специализацию на подзадачи (раздел 6.1).

Введено отношение «похожести» (раздел 6.3.1), связывающее семантическое проявление цикла в метадереве с синтаксическими структурами в этом дереве. Это отношение представлено, как пересечение отношения «похожести» чисто функциональной структуры стеков (последовательности имён функций) и «похожести» параметрического описания аргументов разных вызовов одной функции. Отношение «похожести» аргументов вызовов функций является модификацией отношения Хигмана-Крускала, которое адаптировано на множество РЕФАЛ-термов. Сформулированы свойства этих отношений и непосредственно алгоритма обобщения обеспечивающие конечность процедуры факторизации метадерева вычислений, часть из которых доказана.

Введено понятие последовательности временн развития стека ого (раздел 6.3.1.1).

Определение 2 Пусть дан конечный алфавит A ::= {aj}. Пусть W – множество конечных слов над A, включая пустое слово.

Пусть даны функция G: A W и некоторое слово s W.

Определим последовательность (быть может, конечную) с записью времён рожденияstackn:

1.stack0 ::= (s,0) 2. пусть определен stacki ::= (ai, t) ui, где ai A, t N, а ui – оставшаяся часть последовательностиstacki. Тогда stacki+1 ::= Time(G(ai), MaxTime) ui, гдеMaxTimeесть максимум по вторым компонентам пар изstacki.

Time(a w, time) ::= (a,time+1) Time(w, time+1);

Time(, time) ::= ;,гдеa A,w W.

Последовательностьstackn назовём временным развитием стека(G,s).

Описаны стратегии алгоритмов свёртки:

• Алгоритм вложения просматривает опорные узлы, лежащие на пути от корня метадерева до текущего узла, в порядке времени создания этих узлов (раздел 6.2).

• Обобщение просматривает опорные узлы вдоль пути от текущего узла до корня мета-дерева, то есть в направлении противоположном ориентации (противоположном просмотру этих узлов алгоритмом вложения) (раздел 6.3.5).

Доказано, что местность сред двух префиксов, выделяемых обнинским алгоритмом Турчина, совпадают (раздел 6.3.1.1, Утверждение 2).

Доказаны теоремы:

• Частично рекурсивная функция, определяемая обобщённым параметризованным стеком, является расширением частично рекурсивной функции, которая определена стеком заменяемого предыдущего опорного узла (раздел 6.3.2, Теорема 1).

• Результат подстановки параметров, построенной обобщением предыдущего стека, в параметризованные вызовы функций в обобщённом стеке определяет частично рекурсивную функцию заменяемого предыдущего опорного узла (раздел 6.3.2, Теорема 2).

Рассмотрены свойства результатов вложения и обобщения, с точки зрения временной эффективности последующего выполнения результата преобразований (раздел 6.4). В частности, показано, что в процессе обобщения информация о параметризованных средах может быть потеряна тремя принципиально разными способами:

• разбиением задачи на подзадачи и описанием связей между ними;

• обобщением параметризованных выражений с построением нерекурсивных (без функциональных вызовов) сводящих подстановок, которые остаются в метадереве возможных вычислений;

• обобщением параметризованных выражений с построением рекурсивных сводящих подстановок, которые остаются в метадереве возможных вычислений.

В седьмой главе даны принципы развёртки специализируемой программы. Развёртка перестраивает структуру параметризованных стеков функций в листьях грозди прогонки, согласно некоторой стратегии;

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

В восьмой главе вводится понятие компоненты факторизации метадерева возможных вычислений. Дана классификация компонент факторизации с точки зрения их глобального анализа.

В процессе свёртки могут быть построены три типа компонент:

1. самодостаточные – все рёбра исходящие из вершин таких подграфов заканчиваются только в вершинах данного подграфа;

2. компоненты содержащие только вершины, исходящие рёбра из которых заканчиваются либо в вершинах данного подграфа, либо в вершинах компонент факторизации, построенных ранее (далее мы будем говорить, что подграф ссылается на построенные подграфы);

3. компоненты, в которых существуют вершины с исходящими из них рёбрами, которые заканчиваются на базисных узлах являющихся корнями поддерева, факторизация которого ещё не завершена (далее в этом случае мы будем говорить, что подграф ссылается на непрофакторизованную часть мета-дерева).

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

В десятой главе описываются алгоритмы глобального анализа компоненты факторизации F, ключевыми из которых являются алгоритм автоматического построения выходного формата функции F по ходу дела суперкомпиляции (раздел 10.1.2) и алгоритм распознавания мономов конкатенации (раздел 10.2). Вводится понятие частично рекурсивного монома конкатенации (раздел 10.2.2).

Определение 3 Пусть дана n-местная частичная функция F (x1, x2,..., xn) : DAT An DAT A где DAT A – множество данных РЕФАЛа. Скажем, что F частичный моном приписывания, если существует такая конечная последовательность натуральных чисел k1, k2,..., km, что на области определения функции верно тождество 1 2 m F (x1, x2,..., xn) = xk xk...xk j1 j2 jm где s : (0 < s m) 0 < js n. Здесь операция умножения – приписывание, возведение в степень относится к этой же операции.

Пусть Refaln есть РЕФАЛ-подобный язык, в котором разрешены только n-местные функции-определения (точное определение см. в разделе 10.2.2).

Определение 4 Пусть дана Refaln программа P такая, что местности всех определений из P совпадают и равны n. Пусть Fi(x1, x2,..., xn) входные форматы определений из P. И пусть дана конечная последовательность натуральных чисел k1, k2,..., kn, где kj > 0 для всех j. Пусть [y]j обозначает y,..., y,где y повторено j раз.

Формальным повышением местности программы P по отношению к n-ке k1, k2,..., kn назовём её следующее преобразование:

для всех i • каждую левую частьleft-part= p1,..., pn каждого предложения 1 n из P преобразуем к виду [p1]k,..., [pn]k ;

• каждый функциональный вызов программы P 1 n преобразуем к виду.

k1,k2,...,kn Построенную программу обозначим P и назовём k1, k2,..., kn k1,k2,...,kn местной по отношению к P. (Определения из P будем обозначать аналогично: Fik,k2,...,kn.) Определение 5 Пусть дана Refaln программа P такая, что местности всех определений из P совпадают и равны n. Пусть Fi(x1, x2,..., xn) входные форматы определений из P. И пусть дана перестановка элементов последовательности 1,..., n. Формальной перестановкой параметров программы P посредством, назовём её следующее преобразование:

для всех i • каждую левую частьleft-part= p1,..., pn каждого предложения из P преобразуем к виду p(1),..., p(n);

• каждый функциональный вызовпрограммы P преобразуем к виду.

Построенную программу обозначим P и назовём -переставленной по отношению к P. (Определения из P будем обозначать аналогично: Fi.) Определение 6 Назовём Refaln программу P синтаксическим мономом, если существует конечная последовательность натуральных чисел k1,..., kn (где kj > 0 для всех j), для которой определена программа k1,k2,...,kn P, и существует такая перестановка последовательности 1,..., m ( m = k1 +... + kn ), что после формальной замены в программе k1,k2,...,kn P • каждого функционального вызова конкатенацией его аргументов arg(1)... arg(m), • каждой левой части pattern(1),..., pattern(m) каждого предложения конкатенацией его образцов pattern(1)... pattern(m), левая частьleft-sideкаждого предложенияsentenceпрограммы k1,k2,...,kn P будет графически совпадать с правой частью этого предложения.

Доказана теорема о достаточном условии частичного монома конкатенации (раздел 10.2.2, Теорема 2).

Теорема 1 (достаточное условие мономиальности) В обозначениях определения 6. Пусть Fj(x1,..., xn) есть входной формат определения definition Fj. Пусть yi обозначает i-тый 1 n член последовательности [x1]k,..., [xn]k, тогда для всех j – Fj из синтаксического монома P определяет частичную функцию Fj, являющуюся частичным мономом y(1)...y(m) :

Fj(x1,..., xn) = y(1)...y(m).

Описана стратегия выбора гипотезы мономиальности (раздел 10.2.3).

Пусть программа P содержит ровно одно определение F и пусть есть его входной формат. Рассмотрим все пассивные предложения2 из F : p1,..., pn = right-sidei. Пусть dj обозначают i i i некоторые фиксированные данные РЕФАЛа. Предположим, что для каждого i существует хотя бы одна точка d1,..., dn такая, что i i определение F описывает частичную функцию, при вызове которой на первом же шаге машины, отождествление произойдёт в i i предложении p1,..., pn = right-sidei. То есть набор данных d1,..., dn i i i i представляет собой один из базисных случаев рекурсивного определения F. Правая часть right-sidei, по определению, не будет изменена в предполагаемом процессе анализа на мономиальность. Следовательно, если P частичный синтаксический моном, тогда существует моном Mi от формальных переменных x1,..., xn такой, что результат подстановки вместо этих переменных соответственно p1,..., pn естьright-sidei. Для i i всех i и j должно выполняться графическое равенство Mi(x1,..., xn) = Mj(x1,..., xn).

Описанная выше стратегия порождения гипотезы обладает одним существенным недостатком: построение гипотезы неоднозначно.

Правые части которых не содержат вызовов функций.

Теорема 2 В обозначениях данного раздела (см. выше), пусть в программе P существует хотя бы одно предложение p1,..., pn = i i right-sidei такое, что right-sidei не содержит вызовов функций и для всех k образцы pk отличны от пустых выражений. Тогда может i существовать лишь конечное число гипотез, которые можно построить в рамках описанной выше стратегии.

Показано, что на некоторых примерах эти алгоритмы способны понижать временн сложность программы с экспоненциальной до ую константной O(1).

В одиннадцатой главе описываются принципы использования результатов глобального анализа компоненты факторизации. Повторная специализация подграфа специализирует компоненту факторизации по структуре выходных форматов подграфов Fi, на которые эта компонента ссылается (то есть существует ребро с началом в некотором узле этой компоненты и концом во входной точке одного из Fi), и по инвариантам, обнаруженным глобальным анализом. Повторная специализация проводится без дополнительных разверток.

В двенадцатой главе описывается алгоритм уменьшения местности (арности) функций.

В тринадцатой главе описывается стратегия глобальности использования заголовков (входных форматов) подфункций. Глобальность заголовков компонент факторизации может сократить число этих компонент в остаточной программе.

В четырнадцатой главе анализируются семантические понятия временн эффективности представленные в остаточной программе на ой языке РЕФАЛ-графов (внутреннем языке преобразований SCP4), которые не могут быть адекватно описаны терминами РЕФАЛа-5 – в его конкретной модели вычислений.

В пятнадцатой главе анализируются принципы анализа остаточной программы, позволяющие отобразить ее на языке Си достаточно эффективно.

В шестнадцатой главе описывается формальный язык постановки задач на суперкомпиляцию и связи его с языком параметров описаний конфигураций в момент преобразований. Последний был описан выше и в данной главе уточняется: вводится подтипизация параметров (раздел 16.2), уточняются алгоритмы прогонки (раздел 16.2.1) и свёртки (раздел 16.2.2). Рассматривается приложение алгоритма распознавания мономов конкатенации в задаче самоприменения (раздел 16.3).

В семнадцатой главе описано большое число преобразований простых программ, демонстрирующих возможности суперкомпилятора SCP4. Даны примеры классического использования специализатора в качестве компилятора из некоторого языка L в объектный язык специализатора, в нашем случае РЕФАЛ. В качестве языка L используются язык Машины Тьюринга и язык Регистровой Машины. Указывается на удачное приложение методов суперкомпиляции для верификации параметризованных коммуникационных протоколов.

В восемнадцатой главе формулируется модель вычислений РЕФАЛ программ. В рамках этой модели даётся оценка ускорения, получаемого в результате суперкомпиляции рассмотренного ранее интерпретатора Машины Тьюринга Turing (раздел 17.1, пример 10).

Рассматривается вопрос о соотношении логического и физического времени исполнения программы. Исследуются характеристики суперкомпилятора SCP4; в частности, доказана следующая теорема (раздел 18.1, Теорема 1):

Теорема 3 Для любой программы Prog на языке Машины Тьюринга (MT ) результат специализации суперкомпилятором SCP4 интерпретатора Turing по Prog не содержит терминологии программы Prog. То есть включает в себя только синтаксические единицы Prog, описывающие данные на ленте: текущие символы в ячейках и записываемые в ячейки символы. Следовательно, происходит «эффективная» компиляция программыProgиз языка MT в РЕФАЛ.

В девятнадцатой главе рассмотрен язык разметки программы, посредством которого программист может объявить суперкомпилятору SCP4 стратегии преобразований этой программы или подсказать ему правильный выбор конкретных локальных действий.

В двадцатой главе описаны некоторые свойства рассматриваемой нами реализации РЕФАЛа-5, которые являются принципиальными с точки зрения простоты построения суперкомпилятора.

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»