1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 49
Текст из файла (страница 49)
Зто позволяет перенести плюс-стрелку, идущую на вход х„прямо на Д, а оператор с х» убрать (рис. 7.6, е)). Повторение аналогичных рассуя«дений для следующей пары этажей приводит нас к программе, показанной на рис. 7.6, вх). После последней серии переноса стрелок мы получаем программу, изображенную на рнс. 7.6, в). Выбросив логический оператор с х„на который теперь не ведет ни одна передача управления, оклеив два одинаково работающих экземпляра оператора с условием х» и вернувшись к прежним обозначениям, мы обнаруживаем желаемый результат (сравните рис.
7.6, и) с 7.3, б)). Начальная постановка задачи. Этот пример позволяет нам сделать ряд важных наблюдений, аакладывающих основу нашего исследования. Мы рассматриваем программы, содерл«ащие условия, которь«е вычисляются как булевы функции от алементарных предикатов и изображаются в виде логических формул, содержащих основные логические оп1)рации. В этих программах можно выполнять эквивалентные преобразования, изменяющие структуру логических операторов, но не меняющие содержание программы.
Правила этих преобразований имеют вид тождественных соотношений между фрагментами программ в их графическом представлении. К ним относятся, в частности, правила расчленения (и сочленения, если читать их справа налево) условий (рис. 7.4), а также правила переноса стрелок (исключение повторных проверок), устранения неработающих операторов и «расклеивания» (или склеивания) одинаково работающих операторов (рис. 7.7). Частично эти соотношения опираются на свойства булевых функций, и частично — на правила выполнения логических операторов. Преобразования программ, опирающиеся на эти соотношения, могут приводить к улучшению тех или других характеристик программы (простота, более четкая структура, меньшее время работы). Поэтому естественно возникает задача: построить исчисление преобразований программ, сохраняющих эквивалентность и связанных с работой логических операторов.
Знакомство с исчислением высказываний сразу подсказывает нам, из каких частей должно состоять решение этвй задачи. 1. Надо построить язык, в котором будут конструктивно описываться формальные объекты, соответствующие реальным программам. Эти формальные объекты получат у нас наавание схем Янова. 2. Надо описать механизм интерпретации, позволяющий сопоставлять схемы Янова реальным программам и ввести отношение эквивалентности между программами. Гл.
1. Опгвдгленив схим янОВА 3. На основании эквивалентности программ надо дать определение еквивалентностн схем Янова и исследовать его. 1 1 Х~ Л.1 1 г «р . 1 11 1 1( х х г~ х 1 г 1 г 1 1 Ф Рис. ?.7. Дополнительные правила преобразоеаиий. ° ) непосредственный перенос плюс-стрелки. б) «Дистанционныа» перепое плюс-стрелки. е) Устранение неработающего логического оператора. в)'Скленеэние одинаково работающих логических операторов. 4. Надо ввести метаяаык, в котором будет описано исчисление равносильных (т.
в. сохраняющих эквивалентность) креобракований схем Янова, и придумать само исчисление. 5. Надо будет исследовать найденное исчисление на предмет его корректности и полноты, составляющих его аксиом и правил вывода. 5 ЬЗ. ПОИСК ОСНОВНЫХ ОПРЕДЕЛЕНИИ 5 7.2. Поиск основных определений Анализ ограничений. Первое, что надо сделать — это очертить рамки нашего формализма. Ряд важных ограничений мы уже отметили. Главное — это то, что мы изучаем такие свойства программ, которые связаны с условными операторами, при этом только с их «вторым ярусомэ — булевой функцией от элементарных предикатов. Это вначит, что остальные операторы программы нас сами по себе не интересуют, и для нас важно только, чтобы последовательность их вь7полнения, эадаваемая логическими операторами, не нарушалась бы при тех или иных манипуляциях с условиями.
Такой подход хорошо виден в примере «машины голосования«с мы исследовали механизм проверки условий в куске программы, содержащем только условия и имеющем один вход и два выхода — ДА н НЕТ, прн этом заботились лишь о правильности выбора в«ухода в зависимости от значений логических переменных, поступающих на вход. Можно было бы на этом остановиться, построив «алгебру логических операторовэ, вводя в качестве интерпретации функцию выбора нужного выхода и гарантируя сохранение атой функции при преобразовании логических Операторов.
Однако у7ке простые примеры показывают, что нам естественно хотеть большего. Мы видели, что одним из способов упрощения сложных логических операторов является «запоминание» результата проверки значений условий: это позволяло нам избегать повторных проверок и устранять становящиеся ненужными логические операторы. Влияние выбора направления, т. е. вычисленного значения условия, распространяется не только на блин«айшего преемника (рис. 7.7, а)), но при определенных условиях носит дистанционный характер (рис. 7.7, б)); ири этом цепочка условий, вдель которых как бы переносится информация о сделанных ранее выборах, мелеет быть достаточно длинной. Спрашивается, однако, как поступать, если на пути такой цепочки встает счетный оператор (рис. 7.8)? Очевидно, что ответ зависит только от того, перевычисляет А величину х или нет.
Действительно, если мы достоверно знаем, что оператор А не может изменить вначение переменной х, то дугу, выходящую иэ А, можно направить сразу на выход 1. В противном случае такое преобразование может екаааться незаконным. Таким обрааом, мы заключаем, что операторы целесообраано включить в формализм, а протяженность логических зависимостей НЪбуждает распространить наш формализм на понятие программы в целом. В качестве упрощающего Обстоятельства мы можем, однако, подчеркнуть, что формальное понятие счетного операторатребуетнемногого:умения отличать в программе один оператор от другого и внания для каждого ГЛ.
Ъ ОПРЕДЕЛЕНИЕ СХЕМ ЯНОВА оператора тех логических переменных, которые могут быть изменены этим оператором. Разумное определение программы требует введения памяти, хранящей перерабатываемые данные. Один вид памяти у нас уже есть — логические переменные, хранящие значения элементарных предикатов, вычисляемые тем или иным оператором или задаваемые перед началом работы программы. Что же касается памяти для остальных данных, перерабатываемых программой, то туг дело обстоит одновременно и проще и сложнее. Мы уже отметили, Е~пю Аня плияапнл х ю А 1 1 Ф Ряс. 7.8.
Перекос стрелки при наличии счетвого оператора. что все, что нам нужно от счетных операторов — это знать, какие условия какой оператор может перевычислять. Какие другие данные воспринимает или вырабатывает оператор — нам не интересно. Это пренебрежение к деталям работы оператора можно выразить допущением, что как аргументом, так и результатом оператора является как бы вся память з целом.
При таком подходе память для данных выглядит как некоторое монолитное устройство, не требующее разбиения на ячейки. Такая память может з операторах лишь подразумеваться, не требуя явного обозначения и, стало быть, просто не появляться в формальном определении схем Янова. Негативной стороной такого допущения является обеднение теории. «Тотальный» аффект действия любого счетного оператора — со всей памяти на всю память — является, конечно, слишком сильным предположением, не оправдывающимся для большинства реальных программ. Зато (несколько забегая вперед) мы заметим, что именно это огрубление исходных предпосылок поаволило придать теории Янова классическую ааконченность.
Как и в случае задачи об экономии памяти, нам естественно объединять операторы в программу с помощью графа переходов. И здесь первая задача — ато выбрать способ представления графа $7 2 ПОИСК ОСНОВНЫХ ОПРЕДЕЛЕНИИ 24$ и степень его общности. Поскольку мы уже ограничили себя логическими операторами с двоичными предикатами, сосредоточив на ннх все функции выбора направления счета, у нас появляется естественное требование, что бы любая вершина графа переходов имела не более двух преемников.
Поскольку при интерпретации схем Янова нужно будет. описывать вычислительный процесс, задаваемый программой, нам' надо указать в графе переходов начальный и заключительный операторы. Если мы допустим несколько начальных операторов, то мы должны подразумевать существование некоторого акта «самого начального» выбора начального оператора. Мы не видим особой надобности в создании такой дополнительной сущности и предполагаем обязательное наличие одного начального оператора, кпторый будет помечаться особой входной стрелкой. Заключительный оператор естественно трактовать как команду останова, т. е.
такой оператор не осуществляет никакого преобразования данных и не назначает преемника. Логично потребовать, чтобы в графе переходов соответствующая вершина не имела выходящей из нее дуги. Легко согласиться с тем, что нет принципиальной разницы между одним или несколькими заключительными операторами. Мы ограничимся для большей простоты одним. Следующей альтернативой является одно- или многосвязность графа переходов. Читатель помнит, что в задаче об экономии памяти мы потребовали свяаности. Там этого было достаточно, так как процедура экономии к каждой компоненте связности применялась независимо, а сам граф был неизменным. В нашем случае мы уже анаем, что граф переходов при преобразовании схем Янова будет меняться, в частности, возможно размножение вершин и перенос дуг с одних вершин на другие.
Уже примера с «машиной голосования» достаточно, чтобы догадаться, что даже если требовать связности исходного графа, в ходе преобрааований связность может нарушиться. Зто обстоятельство подсказывает нам не налагать дополнительных ограничений на граф переходов. Говоря о языке описания схем Янова, нам может покаааться необходимым предложить некоторое текстовое представление графа переходов. Автор, однако, в этом месте хочет показать читателю, что можне применять понятие языка не так уж буквально и, где возможно, трактовать конструктивные объекты как абстрактные, а где нужно, испольэовать другие наглядные формы представления объектов, нежели текстуальное.
В частности, мы дадим определение схем Янова, используя абстрактное понятие ориентированного графа и не вводя особых символов (до поры до времени) для таких его характеристик как входная стрелка, плюс- и минус-стрелка и заключительный оператор. Для того чтобы лучше сочетать абстрактную трактовку графа и символический язык, задающий операторы и логические 242 ' Гл. 1. Опгеделение схем яновл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
