EditWYSIWYGAttachPrintable
r3 - 10 Jun 2005 - 15:18:39 - Luba ParmyonovaYou are here: TWiki >  Refaldevel Web > FuturePlans > MacroComp

Частичные вычисления и прогонка

Используются материалы статей
  1. А.В. Климов, С.А. Романенко. Метавычислитель для языка Рефал. Основные понятия и примеры. Москва, 1987г.
  2. Обобщенный алгоритм отождествления для языка Рефал. Курсовая работа студента МГУ факультета ВМК 409 группы Абрамова С.М. Научные руководители: Кондратьев Н.В., Романенко С.А.

Рассмотрим программу, описывающую функцию двух аргументов F(x,y). Если зафиксировать один аргумент, к примеру, x, положив его равным константе a, то получим функцию одного аргумента F1(y) = F(x,a). F1 называется результатом специализации функции F по первому аргументу, равному a.

Специализатором называется программа spec, которая по описанию функции двух аргументов F на метаязыке M и по значению a ее первого аргумента строит описание функции одного аргумента F1 такой, что для любого y выполняется F1(y) = F(a,y), таким образом, F1 = spec(F,a).

F(x,y) = spec(F,x)(y) - основная схема применения специализатора.

Работа специализатора состоит в преобразовании программы F1:
spec(F,a) = opt(F1), где opt - "оптимизатор" программ на метаязыке M, opt специализирует функции, использую частичную определенность аргументов в программе, и делает это для всех вызовов функций. В частности, он может оставить обращение к функции без изменения или, если удастся, вычислить вызов функции до конца и заменить его константой. Оптимизатор, удовлетворяющий таким неформальным требованиям, называется метавычислителем.

При метавычислениях в качестве аргументов функции используются не настоящие значения, а символические обозначения классов значений. Метод преобразования рефал-программ, используюшийся при метавычислениях, называется прогронкой. Идея его состоит в следующем.

Обращение к функции из правой части рефал предложения рассматривается как множество конкретных вызовов, получающихся подстановками вместо переменных всех возможных их значений. Это множество при выполнении шага рефал-машины распадается на подмножества, элементы каждого из которых "проходят" через одно и то же предложение. Нас интересуют подмножества, которые получаются подстановками вместо переменных некоторых выражений (возможно, содержащих переменные). Такие подмножества (и формирующие их подстановки) называются сужениями.

По выражению с переменными, стоящему в обращении к функции, и набору левых частей описания функции, строится конечный набор сужений, таких что для каждого можно выполнить шагрефал-машины в общем виде только по одному из предложений. Предложение, содержащее обращение к функции, заменяется на несколько "суженных". В каждом из них обращение к функции заменяется на результат выполнения шага. Это преобразование можно выполнить лишь при некотором ограничении на вид левых частей. Самый строгий вариант: запрещаются открытые E-переменные и повторные E- и W-переменные.

Основа прогонки - алгоритм обобщеного отождествления произвольного выражения, содержащего переменные, с левой частью рефал-предложения. При описанных выше ограничениях он вычисляет пересечение этих выражений, представленное в виде объединения конечного числа сужений.

Метод частичных вычислений можно обобщить и сформулировать так: если выражение, стоящее в обращении к функции, не пересекается с левыми частями нескольких первых предложений, а со следующим отождествляется целиком, то выполняется шаг прогонки.

Если выражение, стоящее в обращении к функции, не пересекается со всеми левыми частями описания функции, кроме одного, а пересечение с оставшейся левой частью описывается единственным сужением, то выполняется шаг прогонки. Это правило называется прогонкой единственных сужений.

Частичные вычисления и прогонка единственных сужений всегда завершаются для "правильных" программ - правильных в следующем смысле: для правой части предложения рефал-программы существует набор значений переменных, при котором ее вычисление доходит до нормального конца.

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

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

Обобщенный алгоритм отождествления для языка Рефал.

Понятия и обозначения, которые используются в работе.

El - множество всех l-выражений (выражений, для которых выполняются следующие два условия:

  1. ни одна t-, e-, v-переменная не входит в него более одного раза;
  2. ни одно его подвыражение не содержит более одного мягкого терма (терма вида e<индекс> и v<индекс>) на нулевом уровне скобочной структуры). Et - множество всех типовых выражений (выражений, не содержащих конкретизационных скобок).

Подстановкой называется конечное множество упорядоченных пар вида:
{vi -> Ei}, где vi - переменная, Ei принадлежит E - множеству всех выражений. Ei называется значением vi.

Элементарное сужение дельта - это объект одного из следующих видов:

  1. (v -> E)
  2. (sj -> s[E']j)
  3. (tj -> t[E']j)
где v - переменная, E принадлежит Et, j - индекс, E' - либо символ, либо s-переменная.

Расщепления - конечные множества сужений.

Системой называется упорядоченная тройка СИГМА = (X,Y,Z), где X - конечное множество равенств, Y и Z - конечные множества неравенств. Отношения, входящие в X и Y называют условными, отношения, входящие в Z - безусловными.

Правильно специфицированная система - система, в которой любая переменная с признаками s-, t-, e-, v- , входящая в Y, входит в X.

Деревом сужений правильно специфицированной системы СИГМА0 называется дерево, удовлетворяющее следующим условиям:

  1. в каждой вершине этого дерева записана система, а каждому ребру приписано некоторое сужение; в корневой вершине записана P[СИГМА0];
  2. если вершина n, в которой записана система СИГМА имеет k дочерних вершин n1, ... nk, в вершине ni записана система СИГМАi, а дуге, ведущей из вершины n в вершину ni приписано сужение дельтаi, то должны выполняться следующие условия:
  3. {дельта1, ..., дельтаk} = ГАММА[СИГМА];
  4. СИГМАi = P[дельтаi // СИГМА] (i = 1, ..., k)

(P - расщепление) ГАММА - отображение, реализуемое некоторым алгоритмом и ставящее в соответствие любой системе СИГМА из Su расщепление, которое требует СИГМА, и новые индексы которого не используются в СИГМA. То есть, если СИГМА принадлежит Su, то СИГМА требует расщепления ГАММА[СИГМА].

Систему называют терминальной, если в ней нет противоречий.

Система называется нераскрытой, если она принадлежит множеству всех приведенных систем, но не принадлежит множеству всех терминальных систем и правильно специфицирована.

Систему называют приведенной, если Pпси[СИГМА] = СИГМА (Pпси операция удаления тавтологий), P1[СИГМА] = СИГМА (операция P1 каждое ее равенство из X заменяет на терминальное равенство из его дерева рабора, композиция операций Pпси и Pa [СИГМА] = СИГМА (операция Pa выполняет присваивание в СИГМА).

Su - множество всех нераскрытых систем.

В работе "Обобщенный алгоритм отождествления" Абрамова С.М. описан алгоритм, который по заданным классам (El, Nl</sub)> и (Et, Nt), где El принадлежит El, Et принадлежит Et, Nl, Nt принадлежит множеству всех отрицательных спецификаций (конечное множество неравенств) и любая переменная из Nl входит в El, строит дерево D[(El,Nl),(Et,Nt)].

В приложении к рассматриваемой работе приведены следующие пояснения:
"В ... работе описан и обоснован алгоритм обобщенного отождествления без использования конкретной реализации отображения ГАММА (генерация расщепления, требуемого системой) и P (приведение системы, то есть выполнение разбора мягких [равенств], удаления тавтологий, выполнения присваивания в системе). В конкретной реализации алгоритма, используя свободу выбора расщепления, требуемого системой (ГАММА), можно добиваться различных свойств получаемых решений."

-- Luba Parmyonova - 07 Jun 2005

Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r4 < r3 < r2 < r1 | More topic actions...
Refaldevel.MacroComp moved from Refaldevel.Macrocomp on 07 Jun 2005 - 15:32 by OrloV - put it back
 
R+

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback