Обогащенные и структурированные схемы

1.7.1 Классы обогащенных схем

Выделяют следующие классы обогащенных схем: класс счетчиковых схем, класс магазинных схем, класс схем с массивами.

Классы счетчиковых имагазинных схем образован добавлением в базис ССП счетного множества счетчиков и магазинов с их интерпретированными операторами.

Счетчик — интерпретированная переменная, у которой областью значений является множество Nat; начальное значение счетчика равно 0.

Интерпретированные операторы имеют следующий вид:

c:= c + 1 — оператор прибавления единицы;

c:= c - 1 — оператор вычитания единицы;

c = 0 — условный оператор проверки равенства счетчика нулю.

При значении счетчика равном 0 оператор вычитания единицы не изменяет его, оно остается равным 0.

К интерпретированным операторам может быть добавлен оператор пересылки значения счетчика с₂:= с₁, который может быть получен при помощи стандартных операторов.

Рисунок 1.10

Магазин — неинтерпретированная переменная сложной структуры. В процессе выполнения интерпретированной схемы состояние магазина — это конечный набор элементов (d₁,d₂,…,d_n) из области интерпретации, где d_n — верхушка магазина.

Интерпретированные операторы имеют следующий вид:

М:= x — запись в магазин;

х:= М — выборка из магазина;

М = Æ — условный оператор проверки пустоты магазина,

где М – магазин, х — обычная переменная. Первый оператор меняет состояние (d₁,d₂,…,d_n) магазина М на состояние (d₁,d₂,…,d_n+1), где d_n+1 — значение переменной х. После выполнения этого оператора элемент d_n+1 становится новой верхушкой магазина. Второй оператор присваивает переменной х значение, равное верхушке магазина, состояние которого меняется с (d₁,d₂,…,d_n-1,d_n) на (d₁,d₂,…,d_n-1), при этом d_n.₁ становится новой верхушкой магазина. Если магазин Мпуст, то применение второго оператора оставляет его пустым, а переменная хне меняет своего значения. Третий оператор— предикат проверки магазина на пустоту; если магазин пуст, то значение предиката М = 0 равно 1, в противном случае — 0.

Класс схем с массивами — это расширение класса счетчиковых схем за счет добавления счетного множества массивов и операторов над ними.

Массив — неинтерпретированная переменная сложной структуры. При выполнении интерпретированной схемы состояние массива — бесконечная последовательность (d₁,d₂,…,d_i,…) элементов из области интерпретациии.

Интерпретированные операторы имеют следующий вид:

А[c]:= x — запись в магазин;

х:= А[c] — выборка из магазина,

где А — массив, [c] — целое число, равное текущему значению счетчика с.

На рисунке 1.10. приведены четыре схемы: стандартная (а), счетчиковая (б), магазинная (в) и схема с массивами (г). Все они эквивалентны друг другу и рекурсивной схеме:

F(x), F(x)= if p(x) then x else f(x, F(g(x))).

1.7.2 Трансляция обогащенных схем

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

Y — стандартные схемы;	Y(М) — магазинные схемы;
Y(R) — рекурсивные схемы;	Y(А) — схемы с массивами;
Y(с) — счетчиковые схемы;	Y(P) — схемы с процедурами.

Диаграмма показывает, что классы Y(М) и Y(А) являются универсальными в том смысле, что схемы всех других классов транслируемы в них. В то же время, в класс Y не транслируются схемы ни одного другого класса. Следует отметить, что класс Y(с) достигает полной мощности при количестве счетчиков не менее 2, т.е. класс Y(с) с одним счетчиком равномощен классу Y.

1.7.3. Структурированные схемы

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

Класс c труктурированных схем Y(S) определяется в том же (полном) базисе В, который был введен для ССП Y.

Различие между Y и Y(S) проявляется на уровне структур схем. Вместо специальных символов Y вводятся специальные символы: if, then, else, while, do, end. Вместо инструкций с метками вводятся три типа схемных оператора в базисе В: простой оператор, условный оператор и оператор цикла.

Простой оператор — это начальный (заключительный) оператор и оператор присваивания.

Условный оператор — это оператор вида

if p then s₁ else s₀ end,

где p — логическое выражение, s₁,s₀ — последовательности (может быть, пустые) схемных операторов, среди которых нет ни начального, ни заключительного.

Операторы цикла имеют вид

while p do s end или until p do s end,

где p,s имеют тот же смысл, что и выше.

Ниже приведен пример эквивалентных схем Y и Y(S).

Стандартная схема программ Y	Структурированная схема программ Y(S)
start(х), 1: y:= f(x), 2: ifp(y) then7 else 3, 3: y:= f(y), 4: ifp(y) then 5 else 7, 5: ifp(x) then 6 else 7, 6: x:= h(x) goto 5, 7: stop(х, y).	start(х), y:= f(x), ifp(y) then else y:= f(y), ifp(x) then while p(x) dox:= h(x) end else end end, stop(х, y).

Доказано, что класс Y мощнее класса Y(S), т.е. схемы Y(S) транслируемы в Y, но не наоборот.

Усилить класс Y(S) можно за счет усложнения логических выражений в условных операторах и операторах цикла Y(SL), введением символов логических операций NOT, OR, AND и атомарных формул, которыми являются логические выражения в старом смысле, например:

NOT p(x) AND q(y,x);

p(g(x, t)) OR q(h(x), x).

В этом случае справедлива

Теорема (Ашкрофт - Манн) Класс стандартных схем Y транслируем в класс схем с логическими операциями Y(SL).