Эквивалентные преобразования рекурсивных функций, описанных на языке РЕФАЛ1

В.Ф.Турчин

Киев-Алушта, 1972

Если наложить на язык РЕФАЛ [1] некоторые ограничения, то можно построить чрезвычайно мощную систему эквивалентных преобразований алгоритмов (точнее - рекурсивных функций), описанных на этом языке. Ограничения таковы:

1) Исключаются символы обмена и связанные с ними возможности менять состояние поля памяти рефал-машины в процессе ее работы,

2) Исключаются свободные переменные терма.

3) Исключаются рекурсивные переменные2.

4) Запрещается использование открытых и повторных переменных выражения.

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

Для сокращения записи исключим малые латинские буквы из числа возможных объектных знаков и резервируем их для собственных знаков рефала. Вместо K, S, Е будем писать, соответственно, k, s, e. Идентификатор свободной переменной превратим в нижний индекс: s1, s2, e1, ea и т. д. (в индексе можно использовать и малые буквы). Предложения будем всегда начинать с новой строки, с абзацным отступом; знак § опускается. Правая функциональная скобка . (подчеркнутая точка) стилизуется в знак ^. В качестве метасимволов для изображения рефал-объектов будем использовать рукописные заглавные латинские буквы.

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

Типовое выражение называется L-выражением, если:

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

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

Примеры L-выражений:

ABC

ўRSў (s1 e2 (A e3 B)) s1

Примеры типовых выражений, не являющихся L -выражениями:

e1 + e2

s1 e2 (s3 e2)

В ограниченном рефале левые части предложений могут быть только L-выражениями.

Теорема 1 . Каждое подвыражение L-выражения является L-выражением.

Теорема 2 . Пусть El - L-выражение, которое при замене свободных переменных на некоторые значения переходит в объектное выражение E0. Тогда не существует другого набора значений, используя который можно перевести El в E0.

Каждому типовому выражению Et можно сопоставить множество всех тех объектных выражений, которые могут быть отождествлены как Et. Это множество мы назовем классом, изображаемым выражением Et, или просто, классом Et. Класс, изображаемый L -выражением, назовем L -классом. Отношения включения и равенства между множествами объектных выражений будем записывать с помощью знаков М и =, а операции пересечения и соединения - с помощью знаков З и И. Знак Ж будет изображать пустое множество. Объектное выражение, (рассматриваемое как частный случай типового) изображает класс, состоящий из единственного элемента. Запись E0 М Et, где E0 - объектное выражение, означает отождествимость E0 как Et.

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

1) Значением свободной переменной символа может быть только символ или свободная переменная символа.

2) Значения всех вхождений одной переменной должны совпадать.

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

Результат применения правильной подстановки D к выражению E будем изображать в виде D//E.

Теорема 3 . Если Et - типовое выражение, а D - правильная подстановка, то D//Et М Et.

Класс Eўt = D//Et будем называть подклассом класса Et, или его сужением. Процедуру выделения подкласса из класса Et мы также будем называть сужением Et. Заметим, что подкласс L -класса не является, вообще говоря, L-классом. Так, любой класс есть подкласс L-класса e1.

2. Обобщенный алгоритм проектирования

Пусть El - L-выражение, а Et - произвольное типовое выражение. Поставим, задачу отыскания пересечения El ЗEt. Очевидно, это есть обобщение задачи отождествления. Если Et - объектное выражение, то ответ находится путем проектирования El на Et (см. [1]), которое в данном случае (вследствие ограничений, наложенных на язык) производится весьма просто. Если Et содержит свободные переменные, необходимо обобщение алгоритма проектирования, которое мы и опишем ниже. Суть его состоит в том, что Et теперь представляет множество объектных выражений, и в процессе проектирования мы будем, если потребуется, сужать это множество, выделяя из него те подмножества, на которые проектирование El возможно.

Результатам проектирования El на Et является совокупность r подстановок Dt1,ј,Dtr в выражении Et, таких что Dti//Et М El. Эти r сужений Et исчерпывают пересечение El и Et, то есть
El ЗEt = Dt1//Et ИјИDtr//Et
В частности, если r=0, то El ЗEt = Ж.

Каждое сужение Dti формируется путем ряда последовательных d-сужений, затрагивающих не более одной переменной. Мы будем записывать d-сужения с помощью стрелки, например: ex ® A ex. При этом остальные переменные переходят, сами в себя. В состав Dt-сужения может войти несколько d-сужений, затрагивающих одну и ту же переменную. Так как на некоторых шагах алгоритма представляются два возможных d-сужения, порождение Dt-сужений есть процесс с ветвлением, который и приводит в конечном счете к появлению r последовательностей d-сужений, имеющих общее начало и успешно доведенных до точки "отождествление закончено".

Каждой подстановке Dti ставится в соответствие подстановка Dli в El, такая что
Dli//El = Dti//Et;
иначе говоря, Dli дает те значения свободных переменных, которые им надо присвоить для отождествления Dti//Et как El. Эти подстановки также формируются последовательно, и мы будем записывать их с помощью стрелки, направленной влево; например, ex ¬ s1 ey A, что означает: переменной ex из El присваивается значение s1 ey A, где s1 и ey - свободные переменные из Dti//Et.

Алгоритм проектирования определяется приводимыми ниже правилами P1-P4. (Идентификаторы x, y и z надо понимать в дальнейшем как произвольные идентификаторы свободных переменных).

P1. Если El пусто, то отождествление возможно, если Et либо пусто, либо есть последовательность свободных переменных выражения ex ј ez. В последнем случае производится сужение
ex ® < пусто > , ј, ez ® < пусто >

P2. Если El есть ex, то отождествление успешно заканчивается присваиванием ex ¬ Et.

P3. Пусть El имеет вид Tl Eўl , где Tl - терм, не являющийся свободной переменной выражения. Если Et пусто, отождествление невозможно. В противном случае представим его в виде Tt Eўt, где Tt - терм. Затем производится проектирование Tl на Tt по правилам, описанным ниже. Если оно невозможно, то невозможно и проектирование El на Et. Если оно возможно, то учитываются сужения и присваивания, сделанные при проектировании Tl на Tt и продолжается проектирование Eўl на Eўt. Если образовалось более одной ветви, то каждая из них обрабатывается независимо.

Правила проектирования термов таковы (в первых фразах сокращенно записано условие):

Р3.1 Tl = S, Tt = S. (S - произвольный символ). Никаких действий.

P3.2 Tl = S, Tt = sx. sx ® S.

P3.3 Tl = S, Tt = ex. Ветвление

ex ® < пусто >

ex ® Sex

P3.4 Tl = sy, Tt = S. sy ¬ S.

P3.5 Tl = sy, Tt = sx. sy ¬ sx. Кроме того, в Eўl производим замену sy на ax (читать: чужая переменная sx).

P3.6 Tl = sy, Tt = ex. Ветвление:

ex ® < пусто >

ex ® sz ex

Идентификатор z должен быть отличен от всех остальных идентификаторов (новый идентификатор).

P3.7 Tl = (E0l), Tt = (E0t). Проектируется E0l на E0t.

P3.8 Tl = (E0l), Tt = ex. Ветвление:

ex ® < пусто >

ex ® (ez) ex

(Идентификатор z - новый).

P3.9 Tl = ax, Tt = S. sx ® S, ax ® S.

P3.10 Tl = ax, Tt = sy. sy ® sx.

P3.11 Tl = ax, Tt = ey. Ветвление:

ey ® < пусто >

ey ® sx ey

В остальных случаях проектирование Tl на Tt невозможно.

P4. Пусть El имеет вид ex Eўl Tl, Если Et пусто, отождествление невозможно. В противном случае представим Et в виде Eўt Tl и будем поступать аналогично пункту P3.

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

Теорема 4 . Пусть Di - коноригинальные подстановки, а E - некоторое выражение. Тогда Di//E - попарно непересекающиеся L-классы.

Следствие. Пересечение двух классов, построенное с помощью алгоритма проектирования, является объединением попарно непересекающихся L-классов.

3. Правила эквивалентных преобразований

Функцию Fў назовем эквивалентной функции F, если при всяком E, при котором существует результат конкретизации kF E^, существует и совпадает с ним результат конкретизации kFў E^. Последовательность промежуточных - шаг за шагом - выражений при конкретизации kFў E^ не обязана, вообще говоря, совпадать с аналогичной последовательностью при конкретизации kF E^; если же она совпадает, мы будем говорить, что не только функция Fў, но и определяющий ее алгоритм (набор предложений) эквивалентен алгоритму, определяющему функцию F. Сформулируем правила эквивалентных преобразований алгоритмов (EAl - EA5) и собственно функций (EF1 - EF2).

EA1. К алгоритму можно приписать (в конце) любое предложение.

EA2. Пусть два предложения с левыми частями L1 и L2, такими что L1 ЗL2 = Ж, стоят в алгоритме рядом. Тогда их можно поменять местами.

EA3. Пусть предложение с левой частью L1 предшествует предложению с левой частью L2, такой что L2 М L1. Тогда второе предложение можно удалить.

EA4. Пусть в алгоритме стоят рядом два предложения:

k L1 ~ R1

k L2 ~ R2

причем L1 М L2, и если в R2 заменить все свободные переменные теми значениями, которые они принимают при отождествлении L1 как L2, то R2 совпадет с R1. Тогда первое предложение можно удалить.

EA5. Пусть алгоритм содержит предложение

k L ~ R
и пусть L1 = D//L есть L -класс, являющийся сужением L путем правильной подстановки D. Тогда указанное предложение можно заменить на пару:
k L1 ~ D//R

k L ~ R

EF1. Пусть одно из предложений, описывающих функцию F, имеет вид

(*)     k Lf ~ C1  k G Et ^  C2
где Et - типовое выражение, C1 и C2 - последовательности знаков, а G - функция с описанием
kG L1g ~ R1g

...

kG Lng ~ Rng

С помощью алгоритма проектирования, найдем n наборов коноригинальных подстановок {Di1,ј,Dirn}, определяющих n пересечений
Et ЗLig = ri
И
j=1 
 Dij//Et,   i=1,ј,n

Предложение (*) можно заменить на r1+ј+rn предложений, расположенных в порядке возрастания индекса i.

Dij//Lf ~ {Dij//C1Rijg {Dij//C2}
где Rijg получается из Rig заменой свободных переменных на те значения, которые они принимают при отождествлении Dij//E как Lig. (Фигурные скобки ограничивают область действия знака //.)

Заметим, что если, для какого-то i, Et ЗLig = Et, то есть Et М Lig, то по правилу EA3 остальные предложения можно не выписывать.

EF2. Пусть одно из предложений, описывающих функцию F, имеет вид

k F Lf ~ C1  k G E^  C2
где E - произвольное (общее) выражение. Заменим в выражении E все термы, начинающиеся со знака k, на различные новые свободные переменные выражения, которые назовем неразменными переменными. Если предложение, видоизмененное таким образом, допускает применение правила EF1 с тем ограничением, что не требуется сужений, затрагивающих неразменные переменные, то исходное предложение может быть подвергнуто аналогичному преобразованию. Для этого надо преобразовать видоизмененное предложение, а затем снова заменить неразменные переменные на те термы, которые они представляют (произведя в них необходимые подстановки).

4. Пример эквивалентного преобразования

Определим функцию сложения двоичных чисел (детерминатив +):

k+(ea)() ~ ea

k+()(eb) ~ eb

k+(ea s1)(eb 0) ~ k+(ea)(eb)^s1

k+(ea 0)(eb 1) ~ k+(ea)(eb)^1

k+(ea 1)(eb 1) ~ k+(k+(ea)(1)^)(eb)^0

Поставим вопрос: каков должен быть второй аргумент, чтобы при первом аргументе 101 сумма была равно 1010? Чтобы ответить на него путем формального преобразования, введем предикат равенства, который на ограниченном рефале описывается так:

k=()() ~ И

k=(ea s1)(eb s1) ~ k=(ea)(eb)^

k=ex ~ Л

и предикат w, который принимает значение И при тех и только тех аргументах, которые удовлетворяют поставленному условию:
w ex ~ k=(k+(101)(ex)^)(1010)^

Подвергнем это предложение эквивалентному преобразованию. Сначала применим EF1 с термом k+(101)(ex)^ в качестве выделенного терма kG Et^. Следовательно, в первую очередь надо найти пересечение (101)(ex) и левой части §+.1 , то есть, +(ea)(). В процессе проектирования применяем следующие правила (в квадратных скобках указывается результат применения правила): P3.1, P3.7, P2 [ea ¬ 101], P3.7, P1 [ex ® < пусто > ]. Итак, мы получили одно сужение D11, определяемое единственным d-сужением ex ® < пусто > . По правилу EF1 записываем предложение

w ~ k=(101)(1010)^

Пересечение +(101)(ex) и левой части §+.2 дает пустое множество. Пересечение с левой частью §+.3, то есть +(ea s1)(eb 0), дает один подкласс, определяемый сужением ex ® ex 0, откуда по правилу EF1 появляется еще одно предложение:

w ex 0 ~ k=(k+(10)(ex)^1)(1010)^

Пересечение с левой частью §+.4 дает пустое множество, а для §+.5 получаем одно сужение ex ® ex 1, что дает третье (и последнее) предложение:

w ex 1 ~ k=(k+(k+(10)(1)^)(ex)^0)(1010)^

Этим применение EF1 заканчивается. Теперь преобразуем каждое из трех полученных предложений. Для первого сразу получаем

w ~ Л

Во втором предложении объявим по правилу EF2 терм

k+(10)(ex)^
неразменной переменной и воспользуемся определением равенства. Получаем:
w ex 0 ~ Л
Точно так же, используя EF2 и EF1, преобразуем третье предложение
w ex 1 ~ k=(k+(11)(ex)^)(101)^

Теперь по правилу EA1 допишем в конце четвертое предложение:

w ex ~ Л
По правилу EA2, примененному дважды, переставим третье предложение на первое место, а два предложения с правой частью Л поглотим по правилу ЕА4 последним предложением. В результате получаем описание w из двух предложений:
w ex 1 ~ k=(k+(11)(ex)^)(101)^

w ex ~ Л

Продолжая таким образом преобразования, получим в конце концов:

w 101 ~ И

w 0101 ~ Л

w ex ~ Л

5. Алгоритм обращения алгоритмов

В приведенном выше примерe, применение правил эквивалентных преобразований рефал-программы свелось, в сущности, к двоичному вычитанию столбиком. Стратегия, которую мы использовали при выборе правила и объекта, к которому оно применяется, была весьма проста и естественна; ее легко сформулировать в виде алгоритма. В результате мы получаем определенный алгоритм преобразования алгоритмов, описанных на рефале. Этот алгоритм можно описать (и он, действительно, описан) на рефале же (ограниченном). Пусть a - детерминатив соответствующей рекурсивной функции. Аргументом функции a является метакодовая запись некоторого набора предложений. Договоримся, что функция a всегда преобразует функцию (точнее, метакодовую запись алгоритма, определяющую эту функцию) с детерминативом ўOMEGAў. Рассмотрим выражение:

a!П!K(ўOMEGAў!EX)!K(=(!K(+(101)(!EX)))(1010)) ј^
Здесь непосредственно за a следует метакодовая запись предложения, определяющего функцию ўOMEGAў. Мы не приводим описания метакода; его можно восстановить, сравнивая метакод с оригиналом на стр. 9 настоящего доклада (предложение, определяющее функцию w). Многоточием мы заменили метакод описания функций + и =, который нужен для функции a, но не меняется в процессе конкретизации. В результате выполнения конкретизации мы получим преобразованное описание функции ўOMEGAў в метакоде, то есть:
!П!K(ўOMEGAў101)И!П!K(ўOMEGAў0101)И

!П!K(ўOMEGAў!EX)Лј

Если обозначим через b несложную функцию, которая из метакода описания функции ўOMEGAў извлекает первый аргумент первого предложения при условии, что правая часть есть И, то конкретизация

b k a Ew^^
где Ew - тот же аргумент, что и выше, даст 101, то есть разность между 1010 и 101 - числами, входящими в аргумент.

Введем теперь функцию g предложением:

g(ea)(eb) ~ b k a !П!K(ўOMEGAў !EX)

!K(=(!K(+(eb)(!EX)))(ea))ј^^

Как легко понять, эта функция осуществляет двоичное вычитание из второго аргумента первого. Комбинация функций k b k aј^^ служит в качестве универсального решающего алгоритма. Для получения обратного алгоритма надо только в аргумент a ввести описание прямого алгоритма вместе с описанием предиката равенства и предиката w, который фиксирует точную постановку задачи. В частности, алгоритм сложения столбиком в позиционной системе счисления преобразуется в алгоритм вычитания. Подчеркнем, что этот алгоритм эффективен (вычитание столбиком): он не требует экспоненциального перебора (универсальный алгоритм с экспоненциальным перебором написать нетрудно), а требует числа действий, пропорционального числу цифр в аргументе. Вопрос о том, при каких условиях описанный алгоритм (или его усиленный вариант) решает задачу без экспоненциального перебора, выходит за рамки настоящего доклада. Заметим только, что при обращении алгоритма умножения столбиком, мы также получаем эффективный алгоритм деления, и что класс алгоритмов, допускающих эффективное обращение этим методом, весьма широк.



ЛИТЕРАТУРА

1. В.Ф.Турчин, Программирование на языке РЕФАЛ. Препринты ИПМ АН СССР №№ 41, 43, 44, 48, 49 (1971).


Footnotes:

1 В.Ф.Турчин, Эквивалентные преобразования рекурсивных функций, описанных на языке РЕФАЛ. В сб.: Труды симпозиума ``Теория языков и методы построения систем программирования'', Киев-Алушта: 1972. Стр. 31-42.

2 Из соображений экономии места мы описываем упрощенный вариант системы эквивалентных преобразований. В полном варианте разрешается использовать некоторые рекурсивные переменные символа.


File translated from TEX by TTH, version 3.05.
On 25 Feb 2002, 18:16.