1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 22
Текст из файла (страница 22)
2. Если ю = ю'эе, где и — распознаватель с тестом р (ты... ..., тз), а е — выходшцая из него Ь-дуга, Ь е- "(О, Ц, то И(8, ю) = И(Я, и')Ре (г(иЯ',тг),..., Ф(ю', тз)). Ркс. 4.4. Дзг фтккцксвьлько экзккьлгвтвмг скгмн, которне логкко-тгрмгль- ко кв ькзкзьлевтзм 3. Если ю = и'о, где о — заключнтелышя вершина с оператором стоп (т„..., ть), то 11(8,ю) =Ир, ') С(ю',т,)...с(ю'ьт,). Например„логике-термальной историей пути, упомянутого в приведенном выше примере, будет рь (х) рг (х) рь д (х)). Детерминантам (обозначение: ЙеФ (8)) стандартной схемы 8 назовем множество логика-термальных историй всех ее цепочек, завершающихся заключительным оператором.
Схемы Юь и Юг называются логика-тергиьььно гнгивалентнььки (сокращенно лт миивалентнгьви, обозначение 8, ~ Яг), если их детерминанты совпадают. Л е и м а 4.6. Логика-терлкьььнан гнвиволентность корренте Д о и а з а т е л ь с т в о. Будем говорить, что интернрета.иил 1 согласована с ловило-термальной историей Й некоторой конечной цепочки ю схемы 8, если Х подтверждает цепочку ю, т.
е. 'для й = яь... я„Фь... г„(т кО, п, О), где я~ = р~Р~ (тм,... , 'гт ), Ь| е= (О, Ц, с> ~ Т, выполнено й~ = 1 (р~ ('гь,... ..., твз)) для всех г = 1,..., т. Понятно, что всякая интерпретация согласована не болев чем с одной историей нз детерминанта схемы о. Более того, если г подтверждает некоторую бескокечиую цепочку или цепочку, заканчивающуюся оператором петли, 93 то с такой интерпретацией не согласована ни одна кз логнко-термальных историй схемы. Пусть 3« — "' 8«, а 1 — произвольная свободная интерпретация базиса 33. Тогда возможны два случая. С. Одна нэ программ (3, 1) нлн (8«, 1) эацнклтшается прн 1. Тогда интерпретация 1 не согласована нк с одной на логнко-термальных которнй нз ЙеС (Я,) = ЙеС (3«).
Это означает, что зацнклкзаются обе программы (8„1) н (8„1). 2. Обе программы (Ям 1) н (3«, 1) останавливаются. Пусть ю, и ю« — цепочки схем 3«к 8 соответственно, подтверждаемые интерпретацией 1. Тогда [С (Я«, и«) ~ беС (Ю«), а в силу беС (Ю«) = = беС (8 ) существует такая цепочка иъ схемы 8«, что [С (Уп ку«) = = 1С (Я„ю«). Поскольку разные цепочки одной н той же схемы порождают разкые логнко-термальные истории, отсюда следует вэ = и«', так что 1С (Яп и,) = 1С (8«, ю«). Для завершения докаэателъства леммы осталось заметить теперь, что значения схем Я«н 8 при интерпретации 1 записаны в (совпадающнх) логикотермалъных историях путей ю, н ю схем 8, н 8«соответственно, т. е. если обозначить через ю«н ю« путя, получающиеся из цепочек ю«к и«соответственно отбрасыванием заключнтельных операторов, то [С (Юы ю«) = [С (Яп и«) та[ (8~, 1) = [С (Ю«, ю ) = = [С (в«ю«) та[ (ув 1).
откуда та[ %. 1) = та[ Фв* 1) П Как показывает пример на рис. 4.4, утвержденне, обратное сформулированному в лемме 4.6, неверно. Можно сказать, что лт-эквивалентность допускает меньше сохраняющих ее преобразований, чем функциональная эквивалентность. В гл. 6 будет построен алгорктм распознавания лт-эквивалентности стандартных схем, а также полная система лт-эквивалентных преобразований. Краткнй обзор н комментария Идея схематизации алгоритмов н программ принадлвкит вы, дающемуся советскому математику А.
А. Ляпунову. В 4953 г; исходя нз общей концепция необходнмостн н возможности формализации процесса программирования, он ввел понятие схемы программы, которое в течение ряда последних лет нсполъзовалось в двух смыслах. Под схемой программы понималось представленне программы, кспольэую«цее некоторую специальную символику, облегчающую анализ н автоматические преобразования программ [38!. Одновременно этот термин употреблялся в том смысле, который мы сейчас в него вкладываем. Идеи Ляпунова были развиты в конце 50-х и в 60-е гг. его учениками и коллегамн — Яновым, Ершовым, Крнннцккм, Калужнкным, Подловчен-' ко.
В ставпюй сейчас классической работе «О логических схемах программ« [78[ Янов формализовал понятие схемы программы„ определил отношение эквивалентности схем н нсследовал проблему эквивалентности для класса схем, получивших впоследствки название схем Янова (этот класс схем будет рассмотрен в гл. 7). Ершов [$3[ исследовал проблему алгоритмической полноты (нлн 94 универсальности) систем операций в операторных алгоритмах, предложив полную систему операций, которая упоминалась в п.
1 1. В рамках схематологии этот результат можно трактовать так: алгоритмически уяиэерсальнынн являются программы, порождаемые подклассом стандартных схем с базисом, содержащим константу, одноместный функциональный символ и двухместный предикатный символ, и множеством интерпретаций, содержащим ешшственную функцию прибавления единицы и один предикат проверки равенства (область ннтерпретации — неотрицательные числа).
Криницкий [28, 29[ исследовал проблему эквивалентности и эквивалентных преобразований стандартных схем, причем для подкласса схем беэ циклов (т. е. схем, граф которых не содержит контуров) нацден алгоритм распознавания эквивалентности и построена полная система преобразований, позволяющая любую пару эквивалентных схем автоматически преобразовать друг з друга. Графовая форма схем была предложена Калужниным [24).
После результатов Янова следующей важной вехой в истории схематол огни стало доказательство неразрешимости проблемы фуккциональной эквивалентности и других главных проблем для стандартных схем. Этот факт был установлен почти одновременно и независимо Лакхэмом, Парком, Патерсоном [119, 126) и Летичевским [31, 32). Доказательству неразрешимости главных проблем посвящена гл. 5. Данную главу мы завершим кратким обзором работ по схематологии, относящимся к периоду между «положительным» результатом Янова и «отрицательным» результатом Лакхзма — Парка— Патерсона и Латичевского. (Более детально с историей исследований в этот период можно познакомиться в обзорных статьях Ершова и Ляпунова [17, 18), а в заключении гл. 7 упомянуты работы по схемам Янова.) Термин «стандартная схема программы» предложен Иткиным и Ершовым [17, 22) по отношению к вполне определенному классу схем, близкому к введенному нами в этой главе.
В разное время разными авторами рассматривались аналогичные классы схем программ, отличающихся в деталях. Для всех стандартных схем, если употребить этот термин в широком смысле, характерны следующие особенности: схемы имеют структуру алголоподобвых (операторных) программ; в схеме 'учт«на струк'тура памяти, представляющая собой конечное множество (простых в смысле языка Алгол-60) переменных; операторы схемы имеют структуру, подобную структуре операторов присваивания н условных операторов Алгола-60.
Рассмотренное нами определение эквивалентности схем (и других главных свойств) имеет семантический характер, т. е. вводится с использованием понятия интерпретации. Другой, «синтаксический», подход к определеюпо отношения эквивалентности состоит в следующем [58). Понятие интерпретации и интерпретированной схемы отсутствует, вместо него описывается некоторый процесс блуждания по схеме, порождающий множество цепочек схемы.
Схемы считаются эквивалентными, если между порожденными множествами цепочек этих схем существует некоторое вааимко однозначное соответствие такое, что сопоставленные друг другу цепочки эквивалентны. Цепочки обычно считаются эквивалентными, если нм соответствует один и тот же объект, называемый нквариантом цепочек.
Таким инвариантом может быть некоторая более или менее детальная информация о свойствах цепочки. В частности, инвариантом может считаться сама цепочка, или построенная по ней цепочка операторов (тогда отношение эквивалентности становится блиаким к отношению изоморфизма), илн термальное значение цепочки, которое строится подобно тому, как находится результат программы при свободных интерпретациях, или информационный граф [27, 45[, описывающий информационные связи между вхождениями операторов в цепочки. Не~ смотря на то, что отношение функциональной эквивалентности и различные (корректные) неинтерпретационные эквивалентности определяются исходя из существенно равных пршщипов, между ними существует связь, о которой мы впскажем следующую типов гезу.
Для любой пары (,ӄ— ), где У вЂ” некоторый класс схем л % а — корректная неннтерпретационная эквивалентность, существует пара (У', ° ) и гомоморфиэм К: 3'-~ У' такие, что для любых двух схем 8п Кз 6:— '7, 81 — Кз тогда и только тогда, когда л К (Я,) ° К (Яз). Другими словами, изучение проблемы неинтерпретационной эквивалентности для класса стандартных схем равносильно изучению проблемы функциональной эквивалентности для подходящего класса стандарткых схем.
Выбор того или иного пути диктуется методологическими соображениями. Наряду со стандартными схемами в рассматриваемый период истории схематологии изучались зболее абстрактныеэ классы схем, в которых отсутствует„например, информация о структуре памяти или структуре операторов. Так, Мартынюк [41, 42[ ввел и изучал класс схем, в ноторых операторы программы представлены символами, а схемы содержат лишь сведения о возможных последовательностях выполнения операторов. Схема Мартынюка представляет собой граф (специального вида), множество вершин которого — это множество симвозов-операторов, а дуги указывают передачи управления от оператора к оператору (такой 1раф называют графом переходов или логическим графом).
Эти схемы оказались удобным инструментом для постановки и решения задач декомпозиции программы, возникающих при ее трансляции и оптимизации, когда необходимо раабиение на фрагменты с минимизацией переходов иэ одного фрагмента в другой. Для исследования более глубоких оптимизационным преобразований программ Лавров [ЗО[ предложил схемы, представляющие собой схемы Мартынюка, обогащенные информацией о раснределенни переменных по операторам. Каждому символу-оператору приписывакнся два наборзк переменных — набор входных и набор вы 96 кодных переменных, О помощью схем Лаврова был получен первый аиачителапый ревулътат теории схем программ, нашедший практическое прнменеппе, а именно — сформулирована в терминах теории гра$ов и решена задача минимизации числа переменных в программе (задача зкономви яамятн) И4, 301.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
