r4 - 22 Mar 2005 - 10:37:20 - Luba ParmyonovaYou are here: TWiki >  Refaldevel Web > SynIdent > Рефал-машина
Рефал-машина - это кибернетическое устройство, состоящее из двух потенциально бесконечных запоминающих устройств (поля памяти и поля зрения) и процессора, преобразующего их содержимое. В каждый момент времени поле памяти содержит некоторый набор предложений, а поле зрения - некоторое рабочее выражение. Работа рефал-машины представляет собой последовательность однотипных действий, называемых шагами.

Реализация Рефала возможна как на основе интерпретации, так и на основе компиляции. Ниже изложена идея, общая для интерпретаторов и компиляторов, относительно представления информации, образующей поле зрения абстрактной рефал-машины.

Поле зрения рефал-машины представляет собой списковую структуру, основной единицей которой является звено. Память, отведенная под поле зрения, представляет собой совокупность некоторого числа звеньев. Звено состоит из четырех полей: поля признака p и трех адресных полей A1, A2, A3. Полe A2 содержит адрес предыдущего звена в этой последовательности, поле A3 содержит адрес следующего звена. Содержимое поля A1 зависит от значения признака p, которое, в свою очередь, зависит от того, какому рефал-объекту соответствует данное звено. Если звено изображает символ, то поле A1 содержит код этого символа, если звено изображает скобку, то поле A1 содержит адрес парной скобки.

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

Язык, который является системой команд рефал-машины, называется языком сборки.

В процессе отождествления будут использоваться следующие переменые. Переменна НЭЛ всегда установлена на первую незаполненную строку в ТЭ. Переменные Г1 и Г2 в процессе отождествления содержат адреса каких-то двух элементов поля зрения. Они служат для запоминания адресов звеньев и всегда установлены на левый и правый конец той дыры, из которой в данный момент проектируются элементы. Проектирование очередного элемента приводит к тому, что либо Г1 сдвигается вправо, либо Г2 сдвигается влево (разрыв сужается).

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

Оператор ЗНАЧ,f; проектирует символ из левой части на соответствующий символ в поле зрения. В момент обращения к оперстору ЗНАЧ,f; Г1 и Г2 установлены на края какой-то дыры. Оператор ЗНАЧ,f; передвигает Г1 на следующее звено и проверяет, чтобы Г1 не совпала с Г2. Если Г1 совпала с Г2, то это значит, что символа f нет. Если Г1 не совпало с Г2, то оператор ЗНАЧ,f; проверяет, содержит ли звено, на которое передвинулась Г1, символ f. Если содержит, то проектирование возможно. Оператор заносит в ТЭ [НЭЛ] адрес этого звена, a НЭЛ увеличивает на единицу. Если это звено не содержит символа f, то проектирование элемента считается невозможным, и управление передается на подпрограмму НЕОТ (неотождествление).

Оператор ПРОВ; проверяет, что Г1 и Г2 установлены на соседние звенья. Его предназначение - убедиться, что между ними ничего нет. Если это не так, то управление передается на подпрограмму НЕОТ.

Оператор СКОБ; осуществляет проектирование пары скобок с левого конца дыры. Он сдвигает Г1 на одно звено вправо, проверяет, не занято ли оно уже Г2, затем проверяет наличие в этом звене левой скобки. Если левая скобка есть, ее адрес заносится в ТЭ [НЭЛ]. Затем по адресу, содержащемуся в поле звена a НЭЛ увеличивает на единицу. Если это звено не содержит символа f, то проектирование элемента считается невозможным, и управление передается на подпрограмму НЕОТ (неотождествление).

Оператор ПРОВ; проверяет, что Г1 и Г2 установлены на соседние звенья. Его предназначение - убедиться, что между ними ничего нет. Если это не так, то управление передается на подпрограмму НЕОТ.

Оператор СКОБ; осуществляет проектирование пары скобок с левого конца дыры. Он сдвигает Г1 на одно звено вправо, проверяет, не занято ли оно уже Г2, затем проверяет наличие в этом звене левой скобки. Если левая скобка есть, ее адрес заносится в ТЭ [НЭЛ]. Затем по адресу, содержащемуся в поле звена A1 (адресу парной скобки) находит правую скобкуи ее адрес заносит в ТЭ [НЭЛ + 1]. После этого Г2 устанавливается на правую скобку, а НЭЛ сдвигается на две единицы. Таким образом, СКОБ; проектирует сразу два элемента и заполняет две строки в ТЭ.

Оператор УГР,n,m; производит установку границ Г1 и Г2, занося в Г1 адрес из ТЭ [n], а в Г2 из ТЭ [m].

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

Оператор СИМ; осуществляет проектирование главного вхождения переменной символа. Он сдвигает вправо Г1 на одно звено, проверяет Г1 и Г2 на совпадение, и если Г1 и Г2 не совпадают, убеждается, что в том звене, на которое указывает Г1, находится не скобка. Оператор СИМ; не интересуется, какой конкретный символ там стоит.

Проектирование повторных вхождений переменных символа вместо оператора СИМ; осушествляет оператор СТС,n. Аргумент n - номер главного вхождения переменной символа.Этот оператор делает проверку на совпадение поля A1 у главного и повторного вхождений.

Оператор ЗАКР; производит проектирование закрытой переменной вхождения. Для каждой переменной выражения отводится две строки таблицы элементов, где запоминаются адреса начала и конца непустого выражения. Если выражение пустое, вместо адреса начала записывается нуль, а адрес конца - это адрес звена, предшествующего выражению. Оператор ЗАКР учитывает это различие между пустым и непустым выражением.

Оператор СТВ,n; осуществляет проектирование повторного вхождения переменной выражения. Его аргумент является номером элемента левой части, соответствующего главному вхождению проектируемой переменной. При обращении к этому оператору он находит в ТЭ[n - 1] и в ТЭ[n] адреса начала и конца главного вхождения. Затем в ТЭ[НЭЛ] заносится адрес звена, следующего за Г1. Затем Г1 начинает двигаться по полю зрения слева направо. При этом каждое очередное звено сравнивается с соответствующим звеном главного вхождения. Если произойдет несовпадение содержимго хотя бы двух звеньев, проектирование считается невозможным. Проектирование считается законченным, если все звенья главного вхождения исчерпаны. При этом Г1 оказывается установленным как раз на конец выражения, и его содержимое заносится в ТЭ[НЭЛ + 1], после чего НЭЛ сдвигается на две единицы. Оператор ТЕРМ проектирует главное вхождение терма. Терм иногда может рассматриваться как частный случай выражения, поэтому в ТЭ ему отводятся две строки. Оператор ТЕРМ сдвигает Г1 на соседнее звено вправо. в ТЭ[НЭЛ] заносится содержание Г1. Если Г1 указывает на левую скобку, Г1 переставляется на парную к ней правую скобку, если же он указывает на символ, то остается неподвижным. Затем в ТЭ[НЭЛ + 1] заносится содержимое Г1, а НЭЛ сдвигается на две единицы.

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

Чтобы обеспечить проектирование открытых вхождений e-переменных, используется стек переходов СП, который представлет собой одномерный массив. Переменная ГП содержит ном,ер первой свободной строки стека переходов. Каждая строка СП состоит из четырех полей, которые служат для запоминания значений переменных Г1, Г2, НЭЛ и счетчика адреса СЧА. Каждый раз, когда какой-то оператор отождествления потерпел неудачу, ГП уменьшается на 1, а в Г1, Г2, НЭЛ и СЧА загружаются значения из СП[ГП]. После этого выполняется оператор, имеющий адрес СЧА. Проектирование открытого вхождения e-переменной производится с помощью комбинации двух операторов: ПУД и УД. ПУД запоминает в СП[ГП] текущие значения Г!, Г2, НЭЛ, СЧА (СЧА в этот момент установлен на УД). Затем заполняются ТЭ[НЭЛ], ТЭ[НЭЛ + 1]. НЭЛ увеличиваетсяна 2 и управление передается на оператор, следующий за УД. Теперь, если какой-то оператор отождествления потерпит неудачу, то управление будет передано на оператор УД, который изменит ТЭ[НЭЛ] и ТЭ[НЭЛ + 1] и передаст управление на следующий оператор.

Если какой-либо из операторов отождествления не может произвести проектирование элемента, происходит ли возврат на удлинение, либо переход на следующее предложение. Для управления переходами с одного на другое предложение служит оператор УПЕР,F. В начале каждого предложения, переведенного на язык сборки, ставится оператор УПЕР,F; его аргументом является метка, которой помечено следующее предложение. Перед последним предложением процедуры УПЕР,F не ставится. В случае неотождествления в последнем предложении отождествление вообще невозможно и управление будет передано на авостную подпрограмму IMP.

Пример.
e1 + e2 * e3 = ....
Переведем левую часть предложения на язык сборки:
ПУД; УД; ЗНАЧ,+; ПУД; ЗНАЧ,*; ЗАКР; ....

Пусть ведущая область конкретизации имеет вид:
++++....+++ (100 раз)

Сначала e1 примет значение "пусто", отождествится первый +. Затем e2 будет удлиняться 99 раз в поисках *. Когда дальнейшее удлинение e2 станет невозможным, удлинится e1, после чего e2 будет уллиняться 98 раз и т.д. В конце концов удлинение станет невозможным.

Очевидно, что если выражение не содержит *, то любая его часть тем более не содержит ее. После того, как e2 "просмотрела" область конкретизации и "не нашла" *, сразу можно сделать вывод о невозможности отождествления.

Для исключения лишних удлинений открытых e-переменных используется оператор КУД,n; который уменьшает значение ГП на n.

В данном примере можно исключить лишние удлинения e1, вставив после оператора ЗНАЧ,+ оператор КУД,1.

Рассмотрим еще пример. Пусть функция содержит два предложения.
e1 + e2 * e3 = ....
e1 + e2 A e3 = ...

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

Предложения этой функции с учетом оптимизации можно перевести на язык сборки следующим образом:
УД; ЗНАЧ,+; КУД,1; УПЕР,М1; УД; ЗНАЧ,*; ЗАКР;
М1: УД; ЗНАЧ,А; ЗАКР;


В компиляторе с Рефала на язык сборки используются два метода исключений лишних удлинений e-переменных с использованием оператора КУД,n.

Вводятся следующие обозначения.

Пусть E - типовое выражение. Неупорядоченное множество переменных, входящих в E, обозначим через ||E||. В каждый момент компиляции левой части L некоторые элементы L уже спроектированы, а некоторые еще не спроектированы. Дырой называется всякое подвыражение L, такое что, все его элементы еще не спроектированы, а элементы, непосредственно примыкающие к нему слева и справа уже спроектированы. Пусть (E1, E2, ..., En) - упорядоченный список дыр, входящих в L в некоторый момент компиляции.

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

Две дыры Ei и Ej непосредственно зависимы, если i = j или пересечение множества переменных, входящих в Ei и множества переменных, входящих в Ej включается в множество всех переменных из L, для которых уже спроектировано некоторое значение. Транзитивное замыкание отношения непосредственной зависимости называется отношением зависимости дыр. Это отношение является отношением эквиваленстности, поэтому оно разбивает все множество дыр на r непересекающихся классов. C1, C2, ..., Cr - упорядоченный список дыр, где Ck получается из исходного списка дыр вычеркиванием всех дыр, не принадлежащих k-му классу. Далее компилятор проектирует все элементы C1, и после этого порождает оператор КУД,m, где m выбрано так, чтобы восстановить глубину стека переходов, которая была перед началом проектирования C1. Затем точно так же обрабатывается C2, ..., Cr.

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

Пусть самая левая дыра имеет вид E1 = ex Ea ey Eb, где ex, Ea, ey удовлетворяют следующим условиям:

  1. каждая е-переменная, входящая в Ea на нулевом уровне скобок, является одной из переменных, для которых уже спроектировано хотя бы одно значение, либо переменной ex;
  2. для переменных, которые одновременно входят в множество переменных Eb E2 ... En, и в множество переменных Ex, объединенном с ex, уже спроектировано хотя бы одно значение;
  3. для переменной ey спроектировано хотя бы одно значение, либо она входит в множество переменных ex Ea, либо в множество переменных Eb E1 E2 ... En.

Компилятор временно прекращает проектирование элементов из E1 E2 ... En, а проектирует элементы из ex Ea, пока все они не будут спроектированы. После этого компилятор порождает оператор КУД,m, где m выбрано так, чтобы восстановить глубину стека переходов, которая была перед началом проектирования элементов из ex Ea.

Несколько примеров оптимизации сопоставления с образцом.

-- Luba Parmyonova - 25 Feb 2005

Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r4 < r3 < r2 < r1 | More topic actions
 
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