Теория вычислительных процессов
Лекция 2
назад | содержание | вперед

Лекция 2

1.2. Стандартные схемы программ

1.2.1. Базис класса стандартных схем программ

Стандартные схемы программ (ССП) характеризуются базисом и структурой схемы.

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

Полный базис В класса стандартных схем состоит из 4-х непересекающихся, счетных множеств символов и множества операторов - слов, построенных из этих символов.

Множества символов полного базиса:

1. Х = {х,x1,x2…,y,y1,y2…,z,z1,z2…} - множество символов, называемых переменными;

2. F = {f(0),f(1),f(2)…,g(0),g(1),g(2)…,h(0),h(1),h(2)…} – множество функциональных символов; верхний символ задает местность символа; нульместные символы называют константами и обозначают начальными буквами латинского алфавита а, b, с...;

3. Р = {р(0),p(1),p(2)…;q(0),q(1),q(2)…; } - множество предикатных символов; p(0),q(0) -; нульместные символы называют логическими константами;

4. {start, stop, …,:= и т. д.} - множество специальных символов.

Термами (функциональными выражениями) называются слова, построенные из переменных, функциональных и специальных символов по следующим правилам:

Примеры термов: x, f(0), a, f(1)(x), g(2)(x,h(3),(y,a)).

Тестами (функциональными выражениями) называются логические константы и слова вида p(n)12,…,фn). Примеры: p(0), p(0)(x), g(3)(x,y,z), p(2)(f(2)(x,y)). Допускается в функциональных и логических выражениях опускать индексы местности, если это не приводит к двусмысленности или противоречию. Множество операторов включает пять типов:

1) начальный оператор - слово вида stаrt(x1,x2…xk), где k0, а x1,x2…xk - переменные, называемые результатом этого оператора;

2) заключительный оператор - слово вида stop12…фn), где n, а ф12…фn - термы; вхождения переменных в термы ф называются аргументами этого оператора;

3) оператор пpuсваиванuя - слово видa х:=ф, где х - переменная (результат оператора), а ф - терм; вхождения переменных в термы называются аргументами этого оператора;

4) условный оператор (тест) - логическое выражение; вхождения переменных в логическое выражение называются аргументами этого оператора;

5) оператор петли - односимвольное слово loop.

Среди операторов присваивания выделим случаи: когда ф - переменная, то оператор называется пересылкой (х:=у) и когда ф -константа, то оператор называется засылкой (х:=а).

Подклассы используют ограниченные базисы. Так, например, подкласс У1 имеет базис: {x1,x2}, {а, f(1)}, {р(1)}, {start, stop, (,),:=, ,} и множество операторов {start(x1,x2); х1:= f(x1), х2:= f(x2), х1:=a, х2:=a, p(x1),p(x2), stop(x1,x2)}, т. е. схемы из этого подкласса используют две переменные, константу а, один одноместный функциональный символ, один предикатный символ и операторы указанного вида.


1.2.2. Графовая форма стандартной схемы

Представим стандартную схему программ как размеченный граф, вершинам которого приписаны операторы из некоторого базиса В.

Стандартной схемой в базисе В называется конечный (размеченный ориентированный) граф без свободных дуг и с вершинами следующих пяти видов:

1. Начальная вершина (ровно одна) помечена начальным оператором. Из нее выходит ровно одна дуга. Нет дуг, ведущих к начальной вершине.

2. Заключительная вершина (может быть несколько) помечена заключительным оператором. Из нее не выходит ни одной дуги.

3. Вершина-преобразователь помечена оператором присваивания. Из нее выходит ровно одна дуга.

4. Вершина-распознаватель помечена условным оператором (называемым условием данной верины). Из нее выходит ровно две дуги, помеченные 1(левая) и 0 (правая).

5. Вершина-петля помечена оператором петли. Из нее не выходит ни одной дуги.

Конечное множество переменных схемы S составляют ее память XS.

Из определения следует, что один и тот же оператор может помечать несколько вершин схемы. Вершины именуются (метки вершины) целым неотрицательным числом (0,1,2,...). Начальная вершина всегда помечается меткой 0.

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

Пример правильной ССП S1 в графовой форме приведен на рисунке 1.3, а.

Вершины изображены прямоугольниками, а вершина-распознаватель овалом. Операторы записаны внутри вершины.


1.2.3. Линейная форма стандартной схемы

Для использования линейной формы СПП множество специальных символов расширим дополнительными символами {:, goto, if, then, else}. СПП в линейной форме представляет собой последовательность инструкций, которая строится следующим образом:

1) если выходная дуга начальной вершины с оператором start(x1,..., хn) ведет к вершине с меткой L, то начальной вершине соответствует инструкция:

0: start(x1,..., хn) goto L;

2) если вершина схемы S с меткой L - преобразователь с оператором присваивания х:=ф, выходная дуга которого ведет к вершине с меткой L1, то этому преобразователю соответствует инструкция:

L: х:= Ф goto L1;

3) если вершина с меткой L - заключительная вершина с оператором stop1,…,фm), то ей соответствует инструкция

L: stор1,…,фm); .

4) если вершина с меткой L - распознаватель с условием p(ф1,…фk), причем 1-дуга ведет к вершине с меткой L1, а 0-дуга - к вершине с меткой L0, то этому распознавателю соответствует инструкция

L: if p(ф1,…фk) then L1 else L0;

5) если вершина с меткой L - петля, то ей соответствует инструкция

L: lоор.

Обычно используется сокращенная запись (опускание меток). Полная сокращенная линейные формы ССП (рисунок 1.3, а) приведены ниже

Рис. 1.3.


1.2.4. Интерпретация стандартных схем программ

ССП не является записью алгоритма, поэтому позволяет исследовать только структурные свойства программ, но не семантику вычислений. При построении “семантической” теории схем программ вводится понятие интерпретация ССП. Определим это понятие.

Пусть в некотором базисе В определен класс ССП. Интерпретацией базиса В в области интерпретации D называется функция I, которая сопоставляет:

1) каждой переменной х из базиса В - некоторый элемент d = I(x) из области интерпретации D;

2) каждой константе а из базиса В - некоторый элемент d = I(a) из области интерпретации D;

3) каждому функциональному символу f(n) - всюду определенную функцию F(n)=I(f(n));

4) каждой логической константе р(0) - один символ множества { 0,1 };

5) каждому предикатному символу р(n) - всюду определенный предикат P(n) = I(p(n)).

Пара (S,I) называется интерпретированной стандартной схемой (ИСС), или стандартной программой (СП). .

Определим понятие выполнения программы.

Состоянием памяти программы (S,I) называют функцию W: Xs D, которая каждой переменной х из памяти схемы S сопоставляет элемент W(x) из области интерпретации D.

Значение терма ф при интерпретации I и состоянии памяти W (обозначим фl(W)) определяется следующим образом:

1) если ф=х, х - переменная, то фI(W) = W(x);

2) если ф=а, а - константа, то фI(W) = I(a);

3) если ф=f(n)(ф12,…,фn), то фI(W)=I(f(n))(ф11(W),ф21(w),…,фn1(W)).

Аналогично определяется значение теста при интерпретации I и состоянии памяти W или I(W):

если (n)( ф12,…,фn), то I(W) = I(р(n)( ф11(W),ф21(w),…,фn1(W)),... фnI(W)), n 0.

Конфигурацией программы называют пару U=(L,W), где L - метка вершины схемы S, а W - состояние ее памяти. Выполнение программы описывается конечной или бесконечной последовательностью конфигураций, которую называют протоколом выполнения программы (ПВП).

Протокол (U0, U1,...,Ui, Ui+1,…) выполнения программы (S,I) определяем следующим образом (ниже ki означает метку вершины, а Wi - состояние памяти в i-й конфигурации протокола, Ui=(ki,Wi):

U0=(0, W0), W0 - начальное состояние памяти схемы S при интерпретации I.

Пусть Ui=(ki,Wi) - i-я конфигурация ПВП, а О - оператор схемы S в вершине с меткой ki. Если О - заключительный оператор stoр{ ф12,…,фn), то Ui- последняя конфигурация, так что протокол конечен. В этом случае считают, что, программа (S,I) останавливается, а последовательность значений ф11(W),ф21(w),…,фn1(W) объявляют результатом val(S,I) выполнения программы (S,I).

В противном случае, т. е. когда О - не заключительный оператор, в протоколе имеется следующая, (i+1)-я конфигурация Ui+1 = (ki+1, Wi+1), причем

а) если О - начальный оператор, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L и Wi+1 = Wi;

б) если О - оператор присваивания х:=ф, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L, Wi+1 = Wi, Wi+1(x) = ф1(Wi);

в) если О - условный оператор и I(Wi) = Д, где Д {0,1}, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L и Wi+1 = Wi;

г) если О - оператор петли, то ki+1 = L, Wi+1 = Wi, так что протокол бесконечен.

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

Рассмотрим две интерпретации СПП S1 (рисунок 1.2, а). Интерпретация (S1,I1) задана так: .

Программа (S1, I1) вычисляет 4! (рисунок l.3,б).

Интерпретация (S1, I2) задана следующим образом:

область интерпретации D2=V*, где V={а,Ь,с}, V* - множество всех возможных слов в алфавите V;

Программа (S1, I2) преобразует слово аbс в слово сbа (рисунок 1.3, в).

ПВП (S1, I1) и (S1, I2) конечен, результат - 24 и - сbа (таблица 1.1 и 1.2).

Табл.1.1.

Конфигурация

U0

U1

U2

U3

U4

U5

U6

U7

U8

U9

U10

U11

U12

U13

Метка

0

1

2

3

4

2

3

4

2

3

4

2

3

Значения

х

4

4

4

4

3

3

3

2

2

2

1

1

1

0

y

0

1

1

4

4

4

12

12

12

24

24

24

24

24

 

 

Табл.1.2.

Конфигурация

U0

U1

U2

U3

U4

U5

U6

U7

U8

U9

U10

U11

U12

Метка

0

1

2

3

4

2

3

4

2

3

4

2

5

Значе-ния

х

аbс

аbс

аbс

аbс

с

с

с

у

а

а

а

сbа

сbа

cbа

сbа


1.3. Свойства и виды стандартных схем программ

1.3.1. Эквивалентность, тотальность, пустота, свобода

ССП S в базисе В тотальна (пуста), если для любой интерпретации I базиса В программа (S, I) останавливается (зацикливается).

Стандартные схемы S1 и S2 в базисе В функционально эквивалентны (S1 ~ S2), если либо обе зацикливаются, либо обе останавливаются с одинаковым результатом, т. е. val (S1, I) val(S2, I).

Примеры тотальных, пустых и эквивалентных схем S2, S3, S4, S5 приведены на рисунке 1.4.

Цепочкой стандартной схемы (ЦСС) называют:

1) конечный путь по вершинам схемы, ведущий от начапьной вершины к заключительной;

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

Рис. 1.4.

В случае, когда вершина-распознаватель (v), то дополнительно указывается верхний индекс (1 или 0), определяющий 1-дугу или 0-дугу, исходящую из вершины.

Примеры цепочек схемы S1 (рисунок 1.3,а):

(0,1,21,5); (0,1,20,3,4,20,3,4,21,5) и т. д.

Цепочкой операторов (ЦО) называется последовательность операторов, метящих вершины некоторой цепочки схемы.

Например, для S1: (start(x), у:=а, р1(х), stop(y)) или

(start(x), у:=а, р0(х), y:=g(x, у), x:=h(x), р0(х), y:=g(x, у), x:=h(x), р0(х), y:=g(x, у), x:=h(x), …)) и т. д.

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

Пусть S -ССП в базисе В, I - некоторая его интерпретация, (0, 1, k2,k3,...) - последовательность меток инструкций S, выписанных в том порядке, в котором эти метки входят в конфигурации протокола выполнения программы (S, I). Ясно, что эта последовательность - цепочка схемы S. Считают, что интерпретация I подтверждает (порождает) эту цепочку.

ЦСС в базисе В называют допустимой, если она подтверждается хотя бы одной интерпретацией этого базиса.

Не всякая ЦСС является допустимой. В схеме S2 (рисунок 1.4,а) цепочки (0, 1,20,5,61, 7), (0, 1,21,3,40, 7) и все другие конечные цепочки не подтверждаются ни одной интерпретацией.

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

ССП свободна, если все ее цепочки допустимы.

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

Рассмотренные свойства распространяются на все другие классы стандартных схем и образуют опорные пункты схематологии программирования.


1.3.2. Свободные интерпретации

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

Все СИ базиса В имеют одну и ту же область интерпретации, которая совпадает со множеством Т всех термов базиса В. Все СИ одинаково интерпретируют переменные и функциональные символы, а именно:

а) для любой переменной х из базиса В и для любой СИ Ih этого базиса Ih(x) = х;

б) для любой константы а из базиса В Ih(a)=a;

в) для любого функционального символа f(n) из базиса В, где n 1, Ih(f(n)) =F(n): ТnТ, где F(n) - словарная функция такая, что

F(n)(1,2,…n) = f(n)(1,2,…n),

т. е. функция F(n) по термам 1,2,…n из Т строит новый терм, используя функциональный смысл символа f(n).

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

Таким образом, после введения СИ термы используются в двух разных качествах, как функциональные выражения в схемах и как значения переменных и выражений. В дальнейшем термы-значения будем заключать в апострофы. Например, если где 1='f(x,a)' - терм-значение переменной х, а где 2 = 'g(y)' терм-значение переменной у, то значение свободно интерпретированного терма 3=f(х, h(y) равно терму-значению 'f(f(x,a), h(g(y)))'.

Пример 1.1. Пусть Ih - СИ базиса, в котором определена схема S1 (рисунок 1.3, а), и в этой интерпретации предикат P=Ih(p) задан так: P()=1, если число функциональных символов в больше двух; P()=0, в противном случае.

Тогда ПВП (S1,lh) можно представить таблицей 1.3.

Таблица 1.3.

Конфигурация

Метка

Значения

   

X

Y

U0

0

‘x’

‘y’

U1

1

‘x’

‘a’

U2

2

‘x’

‘a’

U3

3

‘x’

‘g(x,a)’

U4

4

‘h(x)’

‘g(x,a)’

U5

2

‘h(x)’

‘g(x,a)’

U6

3

‘h(x)’

‘g(h(x),g(x,a))’

U7

4

‘h(h(x))’

‘g(h(x),g(x,a))’

U8

2

‘h(h(x))’

‘g(h(x),g(x,a))’

U9

3

‘h(h(x))’

‘g(h(h(x)),g(h(x),g(x,a)))’

U10

4

‘h(h(h(x)))’

‘g(h(h(x)),g(h(x),g(x,a)))’

U11

2

‘h(h(h(x)))’

‘g(h(h(x)),g(h(x),g(x,a)))’

U12

5

‘h(h(h(x)))’

‘g(h(h(x)),g(h(x),g(x,a)))’

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

Например, терму g(2)(h(1)(x), g(2)(x,y)) соответствует бесскобочный терм ghxgxy. Правила восстановления терма по бесскобочной записи аналогичны правилам восстановления арифметических по их прямой польской записи, которая просто и точно указывает порядок выполнения операций.

В этой записи, впервые примененной польским логиком Я. Лукашевичем, операторы следуют непосредственно за операндами. Поэтому ее иногда называют постфиксной записью. Классическая форма записи, как мы обычно пишем, называется инфиксной. Например:

А*В => АВ*; А*В+С =>АВ*С+; A*(B+C/D) =>ABCD/+*

А*B+C*D =>AВ*CD*+.

Правила представления в польской записи:

1) Идентификаторы следуют в том же порядке, что и в инфиксной записи.

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

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


1.3.3. Согласованные свободные интерпретации

Полагают, что интерпретация I и СИ Ih (того же базиса В) согласованы, если для любого логического выражения справедливо Ih()=I().

Пусть, например, ='g(h(h(x)), g(h(x), g(x,a)))', а интерпретация I3 совпадает с интерпретацией I1 из

п. 1.2.4 за исключением лишь того, что I(x)=3. Так как I3(a)=1; I3(g) - функция умножения; I3(h) - функция вычитания 1; получаем I3() = ((3-1)-1)*((3-1)*(3* 1)) = 6.

В этом случае Ih примера из п. 1.3.2. согласована с только что рассмотренной интерпретацией I3, а так же с I2 (рисунок 1.3, в), но не согласована с I1 (рисунок l.3, б).

Справедливы прямое и обратное угверждения, что для каждой интерпретации I базиса В существует согласованная с ней СИ этого базиса.

Так, например, выше было сказано, что Ih рассмотренного примера не согласована с I1. Чтобы сделать Ih согласованной, необходимо условие P() видоизменить: P()=1, если число функциональных символов в больше трех, P() = 0, в противном случае.

Можно поступить и по другому. Оставить Ih без изменения и согласовать с ней I1. Для этого необходимо будет заменить I1(x) = 4, на I1(x) = 3.

Введем важное вспомогательное понятие подстановки термов, используемое в дальнейшем. Если x1,…,xn (n0) - попарно различные переменные, 1,…,n - термы из Т, а - функциональное или логическое выражение, то через [1/x1,..., ,n/xn] будем обозначать выражение, получающееся из выражения одновременной заменой каждого из вхождений переменной xi на терм I (i = 1, ..., n). Например:

а[у/х]=а, f(x, у)[у/х, x/y]=f(y, х), g(x)[g(x)/x]=g(g(x)), р(х){а/х]=р(а).

Приведем без доказательства несколько важных утверждений.

Если интерпретация и свободная интерпретация Ih согласованы, то программы (S,I) и (S,Ih) либо зацикливаются, либо обе останавливаются и I(val(S,lh)) = val(S,I), т.е. каждой конкретной программе можно поставить во взаимно-однозначное соответствие свободно интерпретированную (стандартную) согласованную программу.

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

Теорема Лакхэма - Парка - Паттерсона. Стандартные схемы S1 и S2 в базисе В функционально эквивалентны тогда и только тогда, когда они функционально эквивалентны на множестве всех свободных интерпретаций базиса В, т.е. когда для любой свободной интерпретации Ih программы (SI,lh) и (S2,Ih) либо обе зацикливаются, либо обе останавливаются и

val(S1,I) = {I(val(S1, Ih)) = I(val(S2, Ih))} = val(S2,I).

Стандартная схема S в базисе В пуста (тотальна, свободна) тогда и только тогда, когда она пуста (тотальна, свободна) на множестве всех свободных интерпретаций этого базиса, т.е. если для любой свободной интерпретации Ih программа (S, Ih) зацикливается (останавливается).

Стандартная схема s в базисе В свободна тогда и только тогда, когда она свободна на множестве всех свободных интерпретаций базиса В, т. е. когда каждая цепочка схемы подтверждается хотя бы одной свободной интерпретацией.


1.3.4. Логико-терминальная эквивалентность

Отношение эквивалентности Е, заданное на парах стандартных схем, называют корректным, если для любой пары схем S1 и S2 из S1ES2 следует, что S1S2, т. е. S1 и S2 функционально эквивалентны.

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

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

Одним из отношений эквивалентности является логико-термальная зквивалентность (ЛТЭ).

Определим термальное значение переменной х для конечного пути щ схемы S как терм t(щ, х), который строится следующим образом.

1) Если путь щ содержит только один оператор А, то: t(щ, х) = , если А - оператор присваивания, t(щ, х) = х, в остальных случаях.

2) Если щ = щ' А е, где А - оператор, е - выходящая из него дуга, щ' - непустой путь, ведущий к А, а х1, ..., xn - все переменные терма t(Ae, х),

то t(щ, х) = t(Ae, х)[ t(щ', х1)/х1, ..., t(щ', xn)/хn].

Понятие термального значения распространим на произвольные термы :

t(щ, х) = [ t(щ,x1)/x1, ..., t(щ, xn)/xn]

Например, пути start(x); у:=х; р1(х); x:=f(x); р0(у); у:=х; p1(x); x:=f(x) в схеме на рисунке 1.5, а соответствует термальное значение f(f(x)) переменной х.

Для пути щ в стандартной схеме S определим ее логико-термальную историю (ЛТИ) lt(S, щ) как слово, которое строится следующим образом.

1) Если путь щ не содержит распознавателей и заключительной вершины,

то lt(S, щ) - пустое слово.

2) Если щ = щ've, где v - распознаватель с тестом p(1, ...,k), а е - выходящая из него Д-дуга, Д {0,1}, то lt(S, щ) = lt(S, щ') рД(t(щ', 1), ...,t(щ',k)).

3) Если щ = щ'v, где v - заключительная вершина с оператором

stop(1, ...,k), то

lt(S, щ) = lt(S, щ') t(щ',1) … t(щ', k),

Например, логико-термальной историей пути, упомянутого в приведенном выше примере, будет p1(X) р0(х) p1(f(x)).

Детерминантом (обозначение: det(S)) стандартной схемы S называют множество ЛТИ всех ее цепочек, завершающихся заключительным оператором.

Схемы S1 и S2 называют ЛТЭ (лт - эквивалентными) S1 ЛТ S2, если их детерминанты совпадают.

Рис. 1.5.

Приведем без доказательства следующее утверждение:

Логико-терминальная эквивалентность корректна, т. е. из ЛТЭ следует функциональная эквивалентность (S1 ЛТ S2=> S1 S2), Обратное утверждение как видно из рисунка 1.5 не верно.

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


назад | содержание | вперед