УДК 004.3 +519.6                                                                                             

gsivanova@gmail.com

МГТУ им. Н.Э. Баумана

При разработке и/или анализе сложных программ достаточно часто возникает необходимость осуществить эквивалентное преобразование структуры уже имеющегося алгоритма [1-5 и др.]. Такие преобразования могут осуществляться с целью приведения алгоритмов к структурному виду, для последующего их распараллеливания, а также для распознавания типовых алгоритмических фрагментов при автоматическом анализе текстов программ.

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

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

Выполнение оператора ветвления приводит к тому, что множество возможных комбинаций значений данных для дальнейшей обработки делится на два: для элементов одного из них предикат условия принимает значение «истина», для элементов другого – «ложь». Слияние, в свою очередь, означает, что объединяемые множества комбинаций значений данных далее будут обрабатываться одинаково.

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

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

1. Инверсия условий передачи управления.

Данное преобразование может понадобиться для согласования условия выхода из цикла с типом цикла. В основу преобразования инверсии условий положим аксиому А2 из [5] – см. рис. 1.

Рис. 1.  Эквивалентные куски уграфа при инверсии условия передачи управления

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

,

соответствующих альтернативным передачам управления (см. рис. 2, а).

Рис. 2. Преобразование «Инверсия условий передачи управления»:

а – модель исходного фрагмента; б – модель преобразованного фрагмента

Исходный G_У1 и полученный G¢_У1 куски уграфа эквивалентны, если во всех возможных реализациях для этих кусков совпадают множества комбинаций значений данных, при которых осуществляются передачи управления на метки m₁, m₂:

где Z(m₁), Z¢(m₁), Z(m₂), Z¢(m₂) – множества комбинаций значений данных, при которых происходит передача управления на указанную метку в исходном и преобразованных фрагментах алгоритма.

Причем, если управление было передано на метку m₀, то оно обязательно будет передано на метку m₁ или на метку m₂:

Z(m₁) È Z(m₂) = Z¢(m₁) È Z¢(m₂) = Z(m₀),                                                                 (2)

Z(m₁) Ç Z(m₂) = Z¢(m₁) Ç Z¢(m₂) = Æ,                                                                       (3)

где Z(m₀) – множество комбинаций значений данных, при которых происходит передача управления на метку m₀. С учетом (1) – (2) для эквивалентности кусков уграфа достаточно выполнения любого равенства из условия (3).

В соответствии со схемами фрагментов

Z(m₁) = {z(m₀): b_k1 « p_k},                                                                        

Z¢(m₁) = {z(m₀): b¢_k1 « p¢_k},                                                                      

где   p_k, p¢_k – предикаты условий вершин ветвлений исходного и полученного кусков уграфа; b_k1, b_k2, …Î {true, false} – логические переменные, совпадение значений которых с результатами вычисления предикатов условий приводит к осуществлению соответствующих переходов.

Совпадение множеств комбинаций значений данных, при которых происходит передача управления на указанные метки, для единственного входного потока обеспечивается тождественностью условий передачи управления на эти метки в обоих уграфах. Так для метки m₁ получаем:

Из (4) окончательно получаем, что преобразование эквивалентно, если

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

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

                                                                                                                               Таблица 1

                                                                                                                  Таблица 1 (окончание)

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

2. Изменения последовательности слияния потоков управления.

Данное преобразование (см. рис. 3) может применяться и к кон­струкциям ветвления и к конструкциям циклов и к их комбинациям.

Рис. 3. Преобразование «Изменения последовательности слияния потоков управления»

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

где  z(m₁), z¢(m₁) – комбинации (n-ки) значений данных на выходе, по­лученные в процессе вычислений по исходному и преобразованному алгоритмам в конкретных реализациях; z_i – комбинация значений данных на одном из входов фрагмента алгоритма (m₀₁ или m₀₂ или m₀₃ в зависимости от реализации) в силу несовместности событий передачи управления на эти входы в конкретной реализации;Z(m_k) – множества комбинаций значений данных в указанных точках алгоритма, полученных во всех возможных реализациях, причем Z(m₀₁) È Z(m₀₂) È Z(m₀₃) = Z(m₁).

Из (5) – (6) получаем, что 

"z_i Î{Z(m₀₁), Z(m₀₂), Z(m₀₃)}   z(m₁) = z¢(m₁),                                                         

т. е. преобразование эквивалентно на всех комбинациях исходных данных.

3. Вынесение начала ветвления или условия выхода из цикла из конструкции ветвления.

Преобразование (см. рис. 4) позволяет вынести начало ветвления или условие выхода из цикла – вершину x_n из ветвления, завершающегося вер­шиной x_s. Если дуга, проходящая через метку m₀₂,  замыкает цикл, то фрагмент всегда структурен.

Рис. 4. Преобразование «Вынесение начала ветвления или условия выхода из цикла из конструкции ветвления»

Исходный G_У1 и полученный G¢_У1 куски уграфа эквивалентны, если во всех возможных реализациях для этих кусков совпадают множества комбинаций значений данных, при которых осуществляются передачи управления на метки m₁, m₂:

где   Z(m₁), Z¢(m₁), Z(m₂), Z¢(m₂) – множества комбинаций значений данных, при которых происходит передача управления на указанную метку в исходном и преобразованных фрагментах алгоритма.

Аналогично преобразованию 1, если управление было передано на метки m₀₁ или m₀₂, то оно обязательно будет передано на метку m₁ или на метку m₂:

Z(m₁) È Z(m₂) = Z¢(m₁) È Z¢(m₂) = Z(m₀₁) ÈZ(m₀₂),                                                   (8)

Z(m₁) Ç Z(m₂) = Z¢(m₁) Ç Z¢(m₂) = Æ,                                                                         (9)

где Z(m₀₁) и Z(m₀₂) – множества комбинаций значений данных, при которых происходит передача управления на метки m₀₁ или m₀₂, причем события передачи управления на эти метки не совместны. С учетом (8) – (9) для эквивалентности кусков уграфа достаточно выполнения любого равенства из условия (7).

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

Z(m₁) = {z(m₀₁): p_n « b_n2},                                                                                          (10)

Z(m₁) = {z(m₀₁): p¢_n « b¢_n2}È{z(m₀₂): p¢_n « b¢_n2},                                                     (11)

где   p_n, p¢_n – предикаты условий вершин ветвления исходного и результирующего уграфов; b_n1, b_n2, …Î {true, false} – логические переменные, совпадение значений которых с результатами вычисления предикатов условий приводит к осуществлению соответствующих переходов.

Из (10–11) получаем, что

Откуда

Из (12) следует, что предикат p¢_n для наборов Z(m₀₁) и Z(m₀₂) принимает различные значения, поэтому вычисление значений p¢_n будем осуществлять в соответствующих ветвях алгоритма (см. вершины x_r и x_i) и записывать полученное значение в дополнительную память (вершина y¢_n графа данных, соответствующая добавленной переменной).

4. Разделение потока управления в точке слияния, за которой следует оператор изменения данных.

 Данное преобразование может использоваться как для ветвлений, при необходимости разделить ветви, так и для циклов, если необходимо вынести оператор изменения данных из цикла. Оно предполагает разделение об­работки комбинаций значений данных, приходящих через входы m₀₁ и m₀₂. Обработка выполняется оператором изменения данных (см. рис. 5).  

Рис. 5. Преобразование «Разделение потока управления в точке слияния,

за которой следует оператор изменения данных»

Исходный G_У1 и преобразованный G¢_У1 куски уграфа эквивалентны, если любая комбинация данных исходных данных соответствующими фрагментами алгоритмов преобразуется одинаково:

,                                           

где  z(m_k)ÎZ(m_k), z¢(m_k) ÎZ¢(m_k) – комбинации значений данных на выходах исходного и преобразованного фрагментов соответственно;

Z(m_k), Z¢(m_k) – множество комбинаций значений данных, полученных в указанном месте алгоритма во всех возможных реализациях соответственно исходного и пре­образованного фрагментов;

Z(m₀₁), Z (m₀₂) – множество комбинаций значений данных, поступающих на соответствующие входы, причем по­ступление данных на эти входы – события не совместные.

Соответствие комбинаций данных обеспечивается идентичными по­следовательностями преобразований для любых комбинаций данных.

Опре­делим z(m₁) и z¢(m₁):

Откуда следует эквивалентность преобразования при любых исходных данных.

5. Разделение потока управления в точке слияния, за которой следует оператор ветвления.

Данное преобразование может использоваться как для ветвлений, при необходимости разделить ветви, так и для циклов, если необходимо вынести оператор ветвления из цикла. Оно предполагает разделение обработки комбинаций значений данных, приходящих через входы m₀₁ и m₀₂. Обработка выполняется оператором ветвления (см. рис. 6).

Рис. 6. Преобразование «Разделение потока управления в точке слияния, за которой следует оператор ветвления»

Исходный G_У1 и преобразованный G¢_У1 куски уграфа эквивалентны, если во всех возможных реализациях для этих кусков совпадают множества комбинаций значений данных, при которых осуществляются передачи управления на метки m₁, m₂:

где   Z(m₁), Z¢(m₁), Z(m₂), Z¢(m₂) – множества комбинаций значений данных, при которых происходит передача управления на указанную метку в исходном и преобразованных фрагментах алгоритма.

 Аналогично преобразованиям 1 и 3, если управление было передано на метки m₀₁ или m₀₂, то оно обязательно будет передано на метку m₁ или на метку m₂:

Z(m₁) È Z(m₂) = Z¢(m₁) È Z¢(m₂) = Z(m₀₁) ÈZ(m₀₂),                                                   (14)

Z(m₁) Ç Z(m₂) = Z¢(m₁) Ç Z¢(m₂) = Æ,                                                                         (15)

где Z(m₀₁) и Z(m₀₂) – множества комбинаций значений данных, при которых происходит передача управления на метки m₀₁ или m₀₂, причем события передачи управления на эти метки не совместны.

С учетом (14) – (15) для эквивалентности кусков уграфа достаточно выполнения любого равенства из условия (13).

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

Z(m₁) = {z(m₀): p_n « b_n1},                                                                                              (16)

Z¢(m₁) = {z(m₀₁): p_n « b_n1}È{z(m₀₂): p_n « b_n1},                                                   

где   p_n – предикат условия вершины ветвления уграфа;

b_n1, b_n2, …Î {true, false} – логические переменные, совпадение значений которых с результатами вычисления предикатов условий приводит к осуществлению соответствующих переходов.

С учетом того, что в (16) z(m₀) Î Z(m₀₁) ÈZ(m₀₂) – элемент объединенного множества комбинаций значений данных, поступающих через оба входа, получаем, что преобразование эквивалентно при любых исходных данных.

6. Изменение последовательности ветвления потоков управления.

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

Рис. 7. Преобразование «Изменение последовательности ветвления потоков управления»

Исходный G_У1 и полученный G¢_У1 куски уграфа эквивалентны, если во всех возможных реализациях для этих кусков совпадают множества комбинаций данных, при которых осуществляются передачи управления на метки m₁, m₂ и m₃:

где  Z(m_k), Z¢(m_k) – множества комбинаций значений данных, при которых происходит передача управления на соответствующие метки в исходном и преобразованном фрагментах. С учетом того, что, как и в предыдущих слу­чаях,

Z(m₁) È Z(m₂) È Z(m₃) = Z(m₀),                                                                             

Z(m₁) Ç Z(m₂) = Z(m₂) Ç Z(m₃) = Z(m₁) Ç Z(m₃) = Æ,                                           

для эквивалентности кусков уграфа достаточно выполнения любых двух равенств из условия (17).

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

Z(m₃) = {z(m₀): (p_k « b_k2)&(p_n « b_n2)},                                                               

Z¢(m₃) = {z(m₀): p¢_kn « b¢_n2},                                                                                 

где   p_r – предикат условия соответствующей вершины ветвления уграфа;

b_r1, b_r2, …Î {true, false} – логические переменные, совпадение значений которых с результатами вычисления предикатов условий приводит к осуществлению соответствующих переходов;

z(m₀)Î Z(m₀) – комбинация значений данных на входе фрагментов.

Откуда, переходя к тождественности условий передачи управления на метку m₃, получаем условие эквивалентности кусков уграфа:

,                                                          

или окончательно:

.                                                     

Аналогично для метки m₁

Z(m₁) = {z(m₀) Î Z(m₀): (p_k « b_k1)},                                                                          (18)

Z¢(m₁) = {z Î Z(m₀)\Z(m₃): (p_k « b_k1)},                                                                      (19)

Для комбинаций значений данных Z(m₃) в исходной схеме значение предиката p_k « b_k2. Но b_k2 = , следовательно, для комбинаций значений данных Z(m₃) условие p_k « b_k1 не выполняется и эти комбинации из Z(m₀) в (3.27) можно исключить, записав вместо  Z(m₀) выражение Z(m₀)\Z(m₃).

Тогда выражения (18) и (19) становятся идентичными, подтверждая эквивалентность выполняемого преобразования.

7. Вынесение оператора изменения данных из ветвления или изменение данных до выхода из цикла.

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

Рис. 8. Преобразование «Вынесение оператора изменения данных

из ветвления или изменение данных до выхода из цикла»

Исходный G_У1 и преобразованный G¢_У1 куски уграфа на рисунке 8 эк­вивалентны, если любая комбинация данных соответствующими фрагментами алгоритмов обрабатывается одинаково. При наличии во фрагменте, как оператора изменения данных, так и оператора ветвления одинаковая обработка означает, что на выходах фрагментов совпадают как наборы значений, так и сами значения, т. е.:

где  z(m_k)ÎZ(m_k), z¢(m_k) ÎZ¢(m_k) – комбинации значений данных на выходах исходного и преобразованного фрагментов соответственно;Z(m_k), Z¢(m_k) – множество комбинаций значений данных, полученных в указанном месте алгоритма во всех возможных реализациях исходного и преобразованного фрагментов, причем с учетом того, что, как и в предыдущих случаях,

Z(m₁) È Z(m₂) = Z(m₀),     Z(m₁) Ç Z(m₂) = Æ.                                                                                                  

для выполнения второго условия выражения (20) достаточно выполнения одного любого равенства из  этого условия.

Определим z(m₁), z(m₂) и z¢(m₁) z¢(m₂): 

,                                

.                               

Т. е. при любых исходных данных комбинации на выходах фрагментов равны.

Теперь определим множество комбинаций значений данных, при которых управление передается на метку m₁:

Z(m₁) = {z(m₀)ÎZ(m₀): (p_k (z_k  Í z(m₀)) « b_k1)},                                                      (21)

Z¢(m₁) = {z(m₀)ÎZ(m₀): (p_k (z¢_k  Í z(m¢₀)) « b_k1)},                                                   (22)

где z_k  Í z(m₀) и z¢_k  Í z(m¢₀) – аргументы предиката условия вершины ветвления в исходном и преобразованных фрагментах.

Из (21) – (22) следует, что Z(m₁) = Z¢(m₁), если z_k = z¢_k ,

т. е. после выполнения фрагмента операторов изменения данных, соответствующих вершине x_i, значения аргументов предиката условия не меняются. Это возможно только, если множество результатов фрагмента операторов изменения данных Y_i, соответствующих вершине x_i, и множество аргументов предиката условия Y_g не пересекаются: Y_i Ç Y_g = Æ.                                                                                                          

Таким образом, данное преобразование получается ограниченно применимым. Однако его можно сделать тождественным, если повторно не вычислять предикат, запомнив предыдущее значение z¢¢_k в дополнительной памяти y¢_k (см. рис. 9).

Рис. 9. Тождественный вариант преобразования

В этом случае (22) будет записываться как

Z¢(m₁) = {z(m₀)ÎZ(m₀): (p_k (z_k  Í z(m₀)) « b_k1)},                                                 

и преобразование станет эквивалентным при любых исходных данных.

8. Внесение оператора изменения данных в ветвление или проверка условия выхода из цикла до изменения данных.

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

Рис. 10. Преобразование «Внесение оператора изменения данных в ветвление или проверка условия выхода из цикла до изменения данных»

Аналогично предыдущему преобразованию, исходный G_У1 и преобразованный G¢_У1 куски уграфа эквивалентны, если любая комбинация данных соответствующими фрагментами алгоритмов обрабатывается одинаково. При наличии во фрагменте, как оператора изменения данных, так и оператора ветвления одинаковая обработка означает, что на выходах фрагментов совпадают как наборы значений, так и сами значения, т. е.:

где  z(m_k)ÎZ(m_k), z¢(m_k) ÎZ¢(m_k) – комбинации значений данных на выходах исходного и преобразованного фрагментов соответственно;

Z(m_k), Z¢(m_k) – множество комбинаций значений данных, полученных в указанном месте алгоритма во всех возможных реализациях исходного и преобразованного фрагментов, причем с учетом того, что, как и в предыдущих случаях,

Z(m₁) È Z(m₂) = Z(m₀),                                                                                             

Z(m₁) Ç Z(m₂) = Æ,                                                                                                   

для выполнения второго условия выражения (23) достаточно выполнения одного любого равенства из  этого условия.

Определим z(m₁), z(m₂) и z¢(m₁) z¢(m₂): 

,                                                                           

.                                                                         

Т. е. при любых исходных данных комбинации на выходах фрагментов равны.

Теперь определим множество комбинаций значений данных, при которых управление передается на метку m₁:

Z(m₁) = {z(m₀)ÎZ(m₀): (p_k (z_k  Í z(m¢₀)) « b_k1)},                                                 (24)

Z¢(m₁) = {z(m₀)ÎZ(m₀): (p_k (z¢_k  Í z(m₀)) « b_k1)},                                                (25)

где  z_k  Í z(m¢₀) и z¢_k  Í z(m₀) – аргументы предикатов операторов ветвления в исходном и преобразованном фрагментах.

Из (23) – (25) следует, что

Z(m₁) = Z¢(m₁), если z_k = z¢_k ,

т. е. после выполнения фрагмента операторов изменения данных, соответствующих вершине x_i, значения аргументов предиката условия не меняются. Это возможно только, если множество результатов фрагмента операторов изменения данных Y_g, соответствующих вершине x_i, и множество аргументов предиката условия Y_j не пересекаются:

Y_j Ç Y_g = Æ.                                                                                                            

Заключение.

Анализ полученных условий эквивалентности преобразований показал, что при их реализации возможны следующие варианты:

1)      сохраняются все возможные последовательности обработки данных во всех возможных реализациях – такие преобразования эквивалентны на всем диапазоне допустимых комбинаций данных, т. е. тождественны;

2)      меняется последовательность операций анализа данных в таких фрагментах алгоритма, в которых отсутствуют операторы изменения данных, – эквивалентность таких преобразований обеспечивается изменением предикатов условий;

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

а) ограничением области применимости преобразования фрагментами, операторы которых не зависят по данным,

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

Таким образом, преобразования типов 1, 2 и 3б применимы независимо от связей операторов по данным, т. е. универсальны. В то же время пре­образования 1-го типа не требуют модификации операторов обработки данных в отличие от преобразований 2-го типа, предусматривающих изменение предикатов, или преобразований типа 3б, использующих до­полнительную па­мять и предполагающих добавление новых операторов изменения данных. Преобразования типа 3а с рассматриваемой точки зрения назовем ограниченно применимыми.

Окончательно получаем классификацию преобразований по усло­виям эквивалентности, представленную на рис. 11.

Рис. 11. Классификация структурирующих преобразований по условиям эквивалентности

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

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

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

Литература:

1.       Мартынюк В.В. Об изменении порядка выполнения операторов в операторной схеме // ЦВТ и программирование. – М.: Советское радио, 1967. – Вып. 2. – С. 67-72.

2.       Ершов А.П. Современное состояние теории схем программ // Проблемы кибернетики (М.). – 1973. – Вып. 27 (4). – С. 87-111.

3.       Цейтлин Г.Е. Формальная трансформация структурированных алгоритмов сортировки // Программирование. – 1985. – ╧ 2. – С. 88-100.

4.       Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ – Петербург, 2003. – 1104 с.

5.       Иванова Г.С. Формальная постановка задачи структуризации алгоритмов // Вестник Московского государственного технического университета им. Н.Э. Баумана. Приборостроение. –  2005. – ╧ 3(60). – C. 64-73.

6.       Овчинников В.А., Иванова Г.С. Информационно-логическая модель алгоритма // Вестник Московского государственного технического университета им. Н.Э. Баумана. Приборостроение. –  2005. – ╧ 2(59). – C. 109-121.

7.       Ершов А.П. Операторные алгоритмы. III (Об операторных схемах Янова) // Проблемы кибернетики (М.). – 1968. – Вып. 20. – С. 25-43.