1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 17
Текст из файла (страница 17)
е. задают одну и ту же функцию. Такая терминологическая связь становится отражением глубокой связи — связи, по существу, между схемами и программами, что дает воэможность изучать свойства программ, анализируя схемы — объекты болев простой природы, юм программы. Точно так же, выделив преобразования, сохраняющие или улучшающие какие-то свойства схем, например, преобразования, сокращающие количество операторов и одновременно гарантирующие эквивалентность исходной и результирующей схем, можно непосредственно применить этн преобразования для классов программ„порождаемых данными схемами.
В теории схем программ рассматривают равные классы схем, моделирующие различные классы программ. Схемы типа 8«» являются абстракциями'алголоподобных программ, но аналогичным методом можно определить схемы программ, записываемых с помощью более богатого илв, наоборот, более бедного набора примитивов, нли даже схемы программ, конструируемых на основаннв совершенно других принципов. Так, в гл. 8 вводится класс рекурсивных схем, которые моделируют программы «функционального» типа, например, программы на языке Лисп.
В гл. 9 рассматриваются магазинные схемы, которые моделируют программы, использующие такие структуры данных, как стеки магазинного тяпа. Схемы Янова (гл. 7) позволяют изучить преобразования программ, которые затрагивают только их логическую структуру. Сравнивая между собой нлассы схем программ, можно исследовать свойства и возможности разных наборов программных примитивов, установить связь ме»кду ними, изучить проблему трансляции программ, запксаиных на одном языке, в программы на другом языке. 13 $2.
Класс стандартных схем 2.1. Базис. Стандартная схема программы (в линейной форме) представляет собой текст на некотором формальном языке. Этот язык можно рассматривать как абстрактный язык программнрованвя, для которого не задана семантика данных и операцвй, т.
е. ве указана область значений переменных, и символы операций и функций не интерпретированы. Фиксация конкретной интерпретации превращает стандартную схему, которая до этого выступает как некоторая «заготовка» программы, в конкретную программу для некоторой гипотетической вычислительной машины. Таким образом, стандартную схему программы можно рассматривать как представитель семейства «стандартных» программ»). Из списка программных прнмнтивов, исполъзуемых в языках программированвя (см. и. 1.1), для стандартных схем и программ отобран небольшой набор, а именно: константы, простые переменные, выражения, операторы присваивания, условные операторы, метки и переходы на метки.
Классы схем программ, в том числе класс стандартных схем, характеризуются базисом класса и структурой схем. Базис класса фиксирует символы, из которых строятся схемы, указывает их роль (переменные, функциональные символы и т. и.), задает вид выражений и операторов схемы. Наряду с классом всех стандартных схем, характеризуемым полным базисом, будем исследовать некоторые его подклассы в базисах более «бедных», чем полный базис. И наоборот, в гл. 9 мы рассмотрим разлвчные классы обогащенных схем, баавс которых формируется из полного базиса (или его подбазисов) включением дополнительных примитивов, напрвмер, более сложных структур данных н операций над ними.
Полный базис Ж «ласса стаидарткмэ схем состоит иэ четырех непересекающихся счетных множеств символов и множества операторов — слов, построенных иэ этих символов. Множества символов полного базиса: 1) Ю = (л, х„..., у, у»..., з, э„...) — множество символов, называемых п«ремеяимли; 2) Я вЂ” ф») рц )Р) йм б(п ф«) М«) Мы й<«>,... ) — »шожество Яункцконалъних сил«о«о«; верхний индекс задает м«сшлосл«ъ символа; нулъместные символы ()Ф>, бЮ>, /э«>,... ) будем называть также константами и обозначать началънымн буквами латинского алфавита а, Ь, с,...; 3) У = (р~»~, рР~, ф»>, ..., ф«>, ф»~, ф»>,...) — множество яредиватнмл сил«ело«; верхний индекс задает местность символа; нулъмествые предикатные символы (роз, ф»>,...) будем называть также логическими константами; ) (старту сто~«(~)ое:= ) — множество специальных символов.
° ) мм эявузоызм а»лель»сват» этот т«ризк в«смотря ва яеудачвс«саввах«взе его «теркваоя «стаял«ртвая программа», вовика«мми эак эл«к«вт бабляот«ки стэнд«ртзых подэрогр«мм. 74 Через а (г) в дальвейшем будем обозначать местность (фупкциопалького или предккаткого) символа г. Термами (Функциональна.ии выражениями) называют слова, построекиые из перемепвых, фуккциопальиых и специальных символов по следующим правилам: д) одиосимволькые слова, состоящие из перемекяых или коистапт, являются термами; 2) слово т вида Р"> (тд, т,..., т„), где т, тг,..., т„— термы, является термам; 3) те и только те слова, о которых говорится в пунктах Ц и 2), являются термами. Примеры терман: х, (<г>, а, (Рд (х), удп (х, Мг> (у, рд> (х), а)).
Логическими еыраженолми, или жестами, взвывают логические коиставты и слова вида рдю (т, т,..., т„), где ро'д — предикатпый символ, а тд,..., т„— термы. Примеры логических выражений: рдгд, рдд> (х), фгд (х, у, г), рдд> (рд> (х, у)). условимся в фуккциопалькдгх и логических выражениях опускать индексы мествости, когда зто ке приводит к двусмыслевиости или противоречию. Множество операторов состоит из операторов пяти типов: 1) начальный оператор — слово вида старт (х,..., х„), где А ~ О, а х,..., х„— попарно различкые перемеииые из базиса Ю, называемые результатами етого операпюра; 2) гаклнгиипельный оператор — елово вида стоп (тд,..., т„), где и ~ О, а т„..., т„— термы; вхождения перемеипых в термы тд,..., т„иазываются при этом аргументами этого оператора; 3) оператор приееаиеания — слово вида х:= т, где х — переменная, а т — терм; вхождения перемекпых в терм т казываются аргуменпдами, а переменная х — регульвнипом этого оператора; 4) уелоеный операпюр (или тест) — логическое выражекие; гхождекия перезйкиых в логическое выражение иазываются аргументами этого оператора; 5) оперожор пот ид — одпосимволькое слово петля.
Среди операторов присваиззкия выделим специальиый случай, когда терм т — переменная, и казовем такие операторы пересылками (иапример, х:= у), а также случай, когда т — кокстакта, и назовем такие операторы засылками конепиидпд (иапример, х:= а). Нагисы подклассов стандартных схем образуются выделением подмножеств перечислеккых множеств полного базиса. Например, базис подкласса Р„который будет рассмотрев в следующей главе, состоит из множеств символов (х„хг), (а, Рдд), (рддд), (старт, стоп, (, ), „:= ) и множества операторов (старт (хд,,тг), хд:= ~(хд), хд:= 1 (хг), хд:= а, хд:= а, р (хд), р (хг), стоп (хд, хг)).
Друппги словами, схемы из класса гг используют всего лишь 75 две переменные х, и х„константу а, единственный одноместный фуннциональнгяй символ, единственный вреди к агний символ и операторы укаэанного вида. Множество переменных базиса схем Янова (см. гл, 7) состоит иэ единственной переменной.
В далышйщем мы не будем каждый раз упоминать общее для всех базисов этих подклассов множество специальных символов, а также начальные операторы. 2.2. Стандартная схема (графовая форма). Стандартную схему мы вводим здесь как размеченный граф, т. е. граф, вершинам которого приписаны операторы иэ некоторого базиса Ю (полного базиса или более узкого баанса). В практике программирования широко попользуется так называемое блок-схемное представление алгоритмов и программ, достоинством которого является наглядность изображения логической (или управляющей) структуры программы.
Такая форма представления оказывается удобной и для стандартных схем программ, особенно в примерах. Стандаряишй схемой е базисе Ж называется конечный (размеченный ориентированный) граф беэ свободных дуг и с вершвнамн следующих пяти типов: () Начальная есршина. В схеме имеется ровно одна начальная вершина. Она помечена начальным оператором. Иэ нее выходит ровно одна дуга. В графе вет дуг, ведущих к начальной вершние. 2) Заключительная вершина.
Ова помечена заключительным оператором, из нее не выходит ни одной дуги. В схеме может быть несколько заключительных вершин. 3) Вершшипнреобразоватгль. Ова помечена оператором присваивания, и из нее выходит ровно одна дуга. 4) Вершина-распознаватель. Она помечена условным оператором (называемым в этом случае также условием этой вершины), и из нее выходят розно две дуги, одна из которых (на рисунках обычно левая) помечена символом $ и называется $-дугой, а другая помечена символом О и называется О-дугой. 5) Вершина-петля. Ова помечена оператором петли. Иэ нее не выходит ви одной дуги. Конечное множество переменных, упоминаемых в схеме «) 8, составляет ее намять Хя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
