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

Определение 5.4. Стандартная схема – это схема программ с памятью, называемая также алголоподобной или операторной схемой.

 

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

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

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

 

Каждому распознавателю сопоставляется некоторый предикатный терм, а преобразователю – оператор присваивания, имеющий вид y := t, где y – символ переменной, а t - функциональный терм.

Конечная совокупность всех переменных в схеме образуют ее память.

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

 

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

 

Программа выполняется при движении по графу переходов:

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

- при попадании на преобразователь с оператором x:= a вычисляется значение a и присваивается переменной x.

Результат выполнения программы – состояние памяти при попадании на выходную вершину.

 

Пример 5.2. Графическое представление схемы программы, приведенной в примере 5.1, приведено на рис.5.1.

 

 

 

m 0

 

 

m1

 

Рис.5.1. Графическое представление схемы программы

 

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

Для примера используем другую интерпретацию предложенной ранее схемы. Возьмем в качестве области интерпретации множество V* всех слов в некотором алфавите V. Константу а заменим пустым словом e. Функциональные и предикатные символы заменим операциями и предикатом над словами:

g – двуместной функцией CONSCAR, приписывающий первую букву первого слова ко второму слову (т.е. CONSCAR (ac,b) = ab, здесь и далее функции языка ЛИСП);

h – одноместной функцией CRD, стирающей первую букву слова (т.е.CRD(ac) = c);

p – предикатом «равно пустому слову e».

Такая интерпретация схемы порождает программу, которая любое слово a₁,a₂,…,a_n в алфавите V, поданное в качестве начального значения переменной х, превращает в «перевернутое» слово a_n,a_n-1,…,a_1.

 

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

 

начало целые х, у;

ввод (х);

у := e;

m: если х = e то на m1;

у := CONSCAR ( х, у);

х := CRD( х );

на m;

m1: вывод (у);

конец

 

 

Интерпретируя по-разному переменные, функциональные и предикатные символы, можно получить совершенно разные программы. Но все они будут устроены одинаково, имея одни и те же переменные, одни и те же типы операторов, одну и ту же логическую структуру и т.д. Значит, все эти программы имеют одну и ту же схему (здесь слово «схема» используется в общем смысле, подтверждая оправданность термина « схема программы»).

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

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

 

Между свойствами программ и свойствами схем программ устанавливается «терминологическая» связь. Например, говорят, что:

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

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

 

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

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

 

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