Определение 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».
Такая интерпретация схемы порождает программу, которая любое слово a1,a2,…,an в алфавите V, поданное в качестве начального значения переменной х, превращает в «перевернутое» слово an,an-1,…,a1.
Программа переворачивания слов:
начало целые х, у;
ввод (х);
у := e;
m: если х = e то на m1;
у := CONSCAR ( х, у);
х := CRD( х );
на m;
m1: вывод (у);
конец
Интерпретируя по-разному переменные, функциональные и предикатные символы, можно получить совершенно разные программы. Но все они будут устроены одинаково, имея одни и те же переменные, одни и те же типы операторов, одну и ту же логическую структуру и т.д. Значит, все эти программы имеют одну и ту же схему (здесь слово «схема» используется в общем смысле, подтверждая оправданность термина « схема программы»).
Анализ схемы позволяет сделать заключения, относящиеся ко всем программам, полученным их схемы с помощью всех возможных интерпретаций.
Пример очень простого заключения: если в схеме нет ни одного условного оператора и оператора перехода, то любая программа из множества программ, порождаемых этой схемой, будет выполняться конечное время, после чего остановится.
Между свойствами программ и свойствами схем программ устанавливается «терминологическая» связь. Например, говорят, что:
схема пуста, если любая программы, полученная из нее с помощью интерпретации, пуста, т.е. никогда не останавливается (зацикливается);
две схемы эквивалентны, если программы, полученные из этих схем одинаковой интерпретацией одноименных функциональных и предикатных символов, эквивалентны, т.е. задают одну и ту же функцию.
Такая терминологическая связь является отражением глубокой связи между схемами и программами, что дает возможность изучать свойства программ, анализируя схемы – объекты более простой природы, чем программы.
Выделив, таким образом, преобразования, сохраняющие или улучшающие какие-то свойства схем и одновременно гарантирующие эквивалентность исходной и результирующих схем, можно непосредственно применить эти преобразования для классов программ, порождаемых данными схемами.
В теории схем программ рассматривают разные классы схем, моделирующие различные классы программ. Сравнивая между собой классы схем программ, можно исследовать свойства и возможности разных наборов программных примитивов, установить связь между ними, изучить проблему трансляции программ, записанных на одном языке, в программы на другом языке.