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

В.Ф.Турчин

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

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

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

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

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

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

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

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

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

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

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

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

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

ABC

ўRSў (s₁ e₂ (A e₃ B)) s₁

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

e₁ + e₂

s₁ e₂ (s₃ e₂)

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

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

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

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

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

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

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

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

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

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

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

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

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

Результатам проектирования E_l на E_t является совокупность r подстановок D^t₁,ј,D^t_r в выражении E_t, таких что D^t_i//E_t М E_l. Эти r сужений E_t исчерпывают пересечение E_l и E_t, то есть

El ЗEt = Dt1//Et ИјИDtr//Et

В частности, если r=0, то E_l ЗE_t = Ж.

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

Каждой подстановке D^t_i ставится в соответствие подстановка D^l_i в E_l, такая что

Dli//El = Dti//Et;

иначе говоря, D^l_i дает те значения свободных переменных, которые им надо присвоить для отождествления D^t_i//E_t как E_l. Эти подстановки также формируются последовательно, и мы будем записывать их с помощью стрелки, направленной влево; например, e_x ¬ s₁ e_y A, что означает: переменной e_x из E_l присваивается значение s₁ e_y A, где s₁ и e_y - свободные переменные из D^t_i//E_t.

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

P1. Если E_l пусто, то отождествление возможно, если E_t либо пусто, либо есть последовательность свободных переменных выражения e_x ј e_z. В последнем случае производится сужение

ex ® < пусто > , ј, ez ® < пусто >

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

P3. Пусть E_l имеет вид T_l Eў_l , где T_l - терм, не являющийся свободной переменной выражения. Если E_t пусто, отождествление невозможно. В противном случае представим его в виде T_t Eў_t, где T_t - терм. Затем производится проектирование T_l на T_t по правилам, описанным ниже. Если оно невозможно, то невозможно и проектирование E_l на E_t. Если оно возможно, то учитываются сужения и присваивания, сделанные при проектировании T_l на T_t и продолжается проектирование Eў_l на Eў_t. Если образовалось более одной ветви, то каждая из них обрабатывается независимо.

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

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

P3.2 T_l = S, T_t = s_x. s_x ® S.

P3.3 T_l = S, T_t = e_x. Ветвление

e_x ® < пусто >

e_x ® Se_x

P3.4 T_l = s_y, T_t = S. s_y ¬ S.

P3.5 T_l = s_y, T_t = s_x. s_y ¬ s_x. Кроме того, в Eў_l производим замену s_y на a_x (читать: чужая переменная s_x).

P3.6 T_l = s_y, T_t = e_x. Ветвление:

e_x ® < пусто >

e_x ® s_z e_x

P3.7 T_l = (E⁰_l), T_t = (E⁰_t). Проектируется E⁰_l на E⁰_t.

P3.8 T_l = (E⁰_l), T_t = e_x. Ветвление:

e_x ® < пусто >

e_x ® (e_z) e_x

P3.9 T_l = a_x, T_t = S. s_x ® S, a_x ® S.

P3.10 T_l = a_x, T_t = s_y. s_y ® s_x.

P3.11 T_l = a_x, T_t = e_y. Ветвление:

e_y ® < пусто >

e_y ® s_x e_y

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

P4. Пусть E_l имеет вид e_x Eў_l T_l, Если E_t пусто, отождествление невозможно. В противном случае представим E_t в виде Eў_t T_l и будем поступать аналогично пункту P3.

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

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

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

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

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

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

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

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

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

k L₁ ~ R₁

k L₂ ~ R₂

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

k L ~ R

k L₁ ~ D//R

k L ~ R

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

(*)     k L_f ~ C₁  k G E_t ^  C₂

kG L¹_g ~ R¹_g

...

kG Lⁿ_g ~ Rⁿ_g

С помощью алгоритма проектирования, найдем n наборов коноригинальных подстановок {Dⁱ₁,ј,Dⁱ_rn}, определяющих n пересечений

Et ЗLig = ri И j=1   Dij//Et,   i=1,ј,n

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

k Dⁱ_j//L_f ~ {Dⁱ_j//C₁} R^ij_g {Dⁱ_j//C₂}

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

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

k F L_f ~ C₁  k G E^  C₂

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

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

k+(e_a)() ~ e_a

k+()(e_b) ~ e_b

k+(e_a s₁)(e_b 0) ~ k+(e_a)(e_b)^s₁

k+(e_a 0)(e_b 1) ~ k+(e_a)(e_b)^1

k+(e_a 1)(e_b 1) ~ k+(k+(e_a)(1)^)(e_b)^0

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

k=()() ~ И

k=(e_a s₁)(e_b s₁) ~ k=(e_a)(e_b)^

k=e_x ~ Л

k w e_x ~ k=(k+(101)(e_x)^)(1010)^

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

k w ~ k=(101)(1010)^

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

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

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

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

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

k w ~ Л

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

k+(10)(e_x)^

k w e_x 0 ~ Л

k w e_x 1 ~ k=(k+(11)(e_x)^)(101)^

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

k w e_x ~ Л

k w e_x 1 ~ k=(k+(11)(e_x)^)(101)^

k w e_x ~ Л

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

k w 101 ~ И

k w 0101 ~ Л

k w e_x ~ Л

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

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

k a!П!K(ўOMEGAў!EX)!K(=(!K(+(101)(!EX)))(1010)) ј^

!П!K(ўOMEGAў101)И!П!K(ўOMEGAў0101)И

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

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

k b k a E_w^^

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

k g(e_a)(e_b) ~ k b k a !П!K(ўOMEGAў !EX)

!K(=(!K(+(e_b)(!EX)))(e_a))ј^^

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

ЛИТЕРАТУРА

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

Footnotes:

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

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