1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 49
Текст из файла (страница 49)
Прежде всего следует отметить, что для классов схем е равенством теряют силу теоремы о свободных (эрбрановых) интерпретациях [см. 5 3 гл.4). Так, следующая схема Лзл нэ класса стандартных схем с равенством зацикливается при некоторых интерпретациях, а при некоторых останавливается: (старт, 1: х:=а, 2: если х = Ь то 4 иначе 3, 3." петля, 4: стоп (х)).
Однако при любой свободной интерпретации эта схема зациклнвается, т. е. она является пустой на множестве свободных интерпретаций, но не пустой на множестве всех интерпретаций. Такие схемы называются неэрбрановымн. Существуют и эрбрановы схемы с равенством. Легко убедвтъся, что проблема, является ли данная схема эрбрановой, не будет частячно раарешнмой. Введение проверок равенства термов отменяет и многие другие теоремы о свойствах классов схем. Так, в классе схем Янова с проверками все главные проблемы становятся неразревшмымн.
Введение проверок равенства увеличивает мощность стандартных схем, так что класс 'т" (=) строго мощнее класса т" [88)„Например, для схемы 3 т не существуег эквивалентной стандартной схемы. Более того, как показал Чандра [88), любой нз рассмотренных нами чистых классов слабее соответствующего класса. обогащенного нроверкамн равенства. При атом проверки равенства оказываются дополнением, ортогональным к другим рассмотренным обогащениям.
Например, Р (с) ) 3, У (=-) > У, Р (с, =) ) У (с), но классы,У (с) и,'У (=) несравнимы по мощности. В силу этой ортогоналъности классы У (А, =) и т" (М, =) оказываются «более универсалънымиэ, чем классы Р (А) и У (М). Следует отметить, что енадбавка мощностиз, которую дают проверки равенства, зависит от сложности допускаемых к проверке термов. Грис н Констебль [92) показали, что добавление к схеме с массивами проверок равенства термов типа х = у, где х и у— переменные, дает класс схем той же мощности„но этот класс не транслируем эффективно в класс Р (А). Харник [ИМ) установил, что класс,У (1М, 1с, =) имеет ту же мощность, что н классы Ь".
(М) и,У (А), чего нельзя сказать о классе Р (1М, =). В обоих случаях подразумевается, что допустимы только проверки типа х = у. Когда в п. 2.6 этой главы говорилось об универсальных классах схем как о классах, в которые транслируются все другие классы, имелось в виду то, что круг сравниваемых типов схем отравичен теми, что рассматривались в атой книге. Но такое определение универсалъности относителъно, так как появление новых, белее мощных, классов меняет ситуацию. Были предложены «абсолютныеэ определенна универсальных классов 539, 70, ИФ. В частности, Трахтенброт (70) орормулировал постулаты, которые должны выяолняться прн интувтнвно разумяых определениях схем программ и классов схем, н продемонстрировал, что при соблюдении этих постулатов можно доказать, что действнтелыю существуют абсолютно универсальные классы схем, например, класс У (А, юв, =).
Все уаоминаемые в этой пните классы схем удовлетворяют предложенным постулатам, но одни иэ этих постулатов исключает недетермннированные и параллельные схемы, поэтому класс Р (А, т, =) вновь может стать относительно универсальным, если выйтн за рамки последовательных детерминированных схем. Действительно, Чандра (бб) провел сравнительный анализ классов схем, допускающих недетерминизм выполнения н особого рода параллелизм, и показал, что оба эти обогащения ортогональны другим обогащениям и друг другу. ГЛАВА 16 СХЕМЫ СТРУКТУРИРОВАННЫХ ПРОГРАММ Возрастающая сложность программ привлекает все большее внимание к проблемам технологни программирования.
Технологические соображения заставнля, в первую очередь, пересмотреть прин»иглы организацви программ„их структуру. Дейкстра [12) первым высказался против неупорядоченного использования переходов на метки, которое может @рнвести н фактически приводит к переусложнению структуры программы, затрудняющему ее вовнмание и декомпозицню на более простые фрагменты. Реалиауя концепцию так нааываемого структурированного программирования, ов предложил, в частности, отказаться от испольаования переходов в алголоподобвых языках и ограничиться более дисциплинирующими средстзамн управления вычислениями.
такими, как условные операторы алголовского типа и операторы цикла. Следует ааметить, что еще раньше в ряде теоретических работ был исследован вопрос о сохранении функциональной мощности программ при наложенви подобных структурных ограничений. Так, Р. Петер е), Бем и Явопвни ««), Глушков [6) и ряд других авторов установнлн, что структуру программ можно «регуляризовать» без уменьшения их функциональной мощности Проблемы струнтурированного программирования не были обойдены вниманием схематологии, в результате чего появилась серия работ, связанная с изученнем мощности разных классов структурированных схем и их основных свойств. В этой главе рассмотрены основные факты, относящиеся к сопоставлению стандартных и структурированных схем.
9 1. Структурвровзивые схемы 1.1. Класс структурированных схем. Класс структурированных схем будет определен в том же (полном) базисе, который был введен для класса стандартных схем (1 2, гл. 4). Различия между стандартными и структурировавнымв схемами проявляются на уровне структур схем. Вместо дополнительных специальных снм- ° ) Р е Ф е г В.
Оиарй»сйеш«Ф« пп6 г«Ьпч!те Рпп)гпопеп.— «В)а)есг)с«», 1938, У. 12, Р. 373 — 386. »«) ВзйшС., 1«перга)О. Р)е»г Вг«6»«пи, Т»и)пз М««Ыпе» аш) 1апап«6«» пй«)г Оп)у Тео Регшапеп Вп)е».— «Сспйпппмапсп «1 АСМ», 1966, ». 9, 36 6, Р. 366 — 371. 228 волов, указанных в п. 2.2 гл.
4, вводятся символы (если, то, иначе, пока, цикл, конец). Вместо инструкций с метками определяются три типа схемлмх операторов в базисе Й: простой оператор, условный оператор н операторы цикла. Простом олгралюр — зто оператор присваивания, или начальный оператор, или заключительный (все они — операторы базиса). Углоглый оигратор имеет вид если я то а иначе а конец, где я — логическое выражение, о1 н аг — последовательности (быть может, пустые) схемных операторов, среди которых ветви началыюго, ни заключительного.
Операторы цикла имеют вид вова л цикл а венец нли до я цикл о конец, где и — логическое выражение, а — последовательность (быть может, нустая) схемных операторов, среди которых нет пи на- чального, ни заключительного. Структурированной схемой в баавсе Ж назьшается конечвал последователъность (ог, о,..., о„) схемных операторов в базисе зг, где о„— началъвый оператор, о„— заключительный оператор, остальные операторы — зто операторы присваивания, илн услов- ные операторы, или операторы цикла.
Примеры структурированных схем: С г Слава Лгаг (старт (х), (старт (т)1 у:=а, у:= У(х). до р (х) цвкл если р (у) то иначе у:= у(х. у) у:= У (у). х:= а(х) конец, если р (х) то стоп (х, у)) () цикл х:=- а (х) конец иначе певец конец, степ (х, у)). Пара (8, 1), где Ю вЂ” структурированная схема в базисе %, а 1 — интерпретация етого базиса, называется струатурирооан- ной программой.
Понятие выполнения структурированной программы опишем менее формалъно, чем выполнение стандартной программы. По- следовательность простых (ннтерпретпрованных) операторов вы- полняется так же, как в последовательность аналогичных опе- раторов стандартной схеъпг, Выполнение интерпретированного условного оператора если р (т„.. „т„) те о, вваче ае конец состоит иа (а) вычисления значения предввата 1(р) (ты (гу),..., тш (гу)), где тп (гр) — значение интерпретированного герма при тонувшая состоянии памяти )К (б) выполнения последовательности аю если вычисленное аначенке преднката равно 1, или выполнения последовательности ае, если вычисленное аначение — О.
Выполнение интерпретированного оператора цнква попа р (т„..., т„) цввл а конец состоит иэ (а) вычисления свечения предивата 1 (р) (ты (ИР),..., т„г (Щ) при тскущем состоянии памяти 1г', (б) выполнения последователъноств а, если вычисленное значение преднката равно $, и последующего перехода к шагу (а). В1еполнение ивтарпретнроваиного оператора цикла ДЙ р~(т, ..., т„) цвви а конец аналогично выполненшо предыдущего оператора, но шаг (б) выполняется в случае, когда значение предиката равно О.
Если выполнение программы (Я, Х) завершается н 1à — заключительное состояние памяти, то 1У (2), где Я вЂ” набор выходных переменных в заключнтелънои операторе, является резуль'татоы та1 (8, 1) атой программы. Йа структурированные схемы переносятся определения Функциональной эпвивалентности и других главных свойств стандарт ннх схем. Естественным обраэом отношение функциональной акаввалевтности распространяется на объединение классов структурированных н стандартных схем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
