1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 39
Текст из файла (страница 39)
3 а д а н в е 8.2. Л. Определвте подходящим образом поватяе цепочкв рекурсвввой схе мы, понятие допустимой цепочки, саободвой рекурсвзвой схемы. Б. Покажите, что теоремы 4Л вЂ” 4.3 о свободных ввтерпретацвях переносятся ка случай рекурсвавых схем. й 2. Проблемы трансляции 2Л. О сравнении классов схем. Программы для ЭВМ, будьто программы, записанные на операторном яаыке, или программы на рекурсивном языке, универсальны в том смысле, что любую внчислимую функцию можно запрограммировать и найти ее аначения для заданных аначений аргументов.
При этом, как уже указывалось, не требуется богатого набора программных примитивов и базовых операций: достаточно тех средств, которые моделируются стандартными схемами, плюс одна интерпретированная операция и один предикат Зто щшчит, что различные классы программ не имеет смысла сравнивать по мощности, понимаемой как способность реализовать различные алгоритмы,— все они оказываются универсальнымн. В то же время программисты знают, что одни программные примитивы являются «более выраэительнымиз, чем другие, что вались алгоритмов с привлечением рекурсии короче, чем итерационное представление, но вычисления по такой программц могут потребовать больше времени, и т. д.
При переходе к схемам программ возникает возможность поставить и исследовать проблему выражения одних наборов примитивов через другие в более чистом виде. Задачи такого типа образуют сравннтелъную схематологяю, основу которой составляют теоремы о возможности или невозможности преобразования схем нз одного класса в схемы другого. При этом наряду с основной аадачей — выяснением соотношений между рааличными средствами программирования — решается и друтая, внутренняя задача схематологии. Действительно, если мы умеем трансформировать один класс схем в другой„то сможем переносить реэулътаты, полученные для некоторого класса схем, на другие классы. В этой главе рассматриваются рекурсивные схемы, но так как в следующей главе речь пойдет о других классах схем программ, имеет смысл ввести необходимые понятия сравнителыюи схематология для произвольных классов схем программ.
Пусть 7 — класс схем программ в некотором базисе лз, д"— класс схем программ в базисе У'. Базис любого иэ рассматриваемых классов схем включает множества: переменных, базовых функционалъннх символов, предикатных символов, другие множества, специфичные для данного класса (см. гл. 9). Мы будем сравнивать классы схем, у которых базисы аиласояамыы в том смысле, что первые три иа перечисленных множеств одинаковы в данных базисах. Это дает возможность превращать в программы схемы иэ разных классов с помощъю одной и той же интерпретации бааисов. Например, полные базисы стандартных и рекурсивных схем согласованны, т. е. определение функцио«У8 налыюй эквивалентности может быть обобщена на схемы вз разных классов.
Схема Юг из класса У н схема Юг иа класса Э" фуиюуионально эквивалентны, если для любой интерпретации 1 согласованных базисов классов У и .У' программы (Ю, 1), (Юм 1] или обе зацыкляваияся, или обе останавливаются с одним и тем же результатом. Говорят, что класс схем У мощнее класса схем Р', или клаве О' юпранелируем в клаве У(обозначенве: У э У'), если'для любой схемы из а" существует эквивалентная ей схема в классе У. Клаве У строго мощнее класса К' (К ).У'), если У мощнее У' и в У существует схема, для ыоторой нет эквивалентной схемы в У' (класс У' не транслируем в класс К).
Класси К и У' раеномощны, если У мощнее 'Р' н У' мощнее У. Клаве схем о" эффективно транслируем е клаве схем о'-', если существует алгоритм, преобразующив любую схему из,У в эквивалентную схему из У'. Классы ~У и о" аффективно раеномощнм, если У эффективно транслируем в У' и в' эффективно транслируем в Р. Ниже, когда устанавливается транслируемость одного класса схем в другой или их равномощыость, фактическы демонстрируется эффективная транслируемость или эффективная равномощность. 2.2.
Трансляция ставдартыых схем в рекурсивные. В рекурсивных схемах результат поставляет ровно одиы терм, а в стандартных схемах заклю ппелышй оператор может содержать любой конечный набор термов и тогда результат программы— не один элемент из области интерпретации, а набор таких элементов. Однако такое отличие не имеет принципиального значения для транслируемости схем.
Можно было бы определить рекурсивные схемы, поставляющие в качестве результата наборы термов, например, используя интерпретированную функцию яе чать (тп..., т„). Мы поступим проще — ограничим класс стандартных схем схемами над базисом, содержащим заключительные операторы только следующего вида: стоп (х), х ~х Ю.
Т е о р е м а 8Л (Маккарти). Клаве стандартных схем транслируем в клаве рекурсивных схем. Д о к а а а т е л ь с т в о. Пусть исходная стандартная схема задана в трафовой форме. Доыаэательство будет состоять в непосредственном описании алгоритма трансляции, который состоит из двух этапов.
На первом этапе с помощью эквивалентных преобразований добьемся, чтобы к каждой вершине-преобразователю (помеченному оператором присваивания) вела ровно одна дуга. Делается зто точно так же, как в п. 3.2 гл. 6 при приведении фрагментов. Для этого достаточно применением ЛТ2 добиться, чтобы от каждого преобрааователя имелся хотя бы одни путь к заключительному оператору, а затем применением правил копирования (см.
рис. 6.7, в) обеспечить выполнение требуемого условия. Второй этап состоит в построении рекурсивной схемы Кв по построенной на первом этапе стандартной схеме Я. Пусть Хз = = (хм..., х„» — память схемы 8. Каждой вершине А схемы 8, не являющейся преобразователем, в соответствии с правилами, перечнсленнымн на рнс. 8Л, сопоставим определение реиурсивной функции Гл. На этом рисунке «ве означает путь, начинающийся Ет-дутой распознавателя А и кончающився дугой, ведущей к вершине Ве, отличной от преобразователя, а (в — путь, начинающвйся выходной дутой началыюй вершины и кончающийся дугой, ведущей к вершине В, которая опять-таки отлична от преобразователя.
Я стел (и) — '~ лл (х,...., л„) л д ~иетля ) лл (ео " аь) б (е1 -- ли — — и Гл (хо...,.ел ) если Л тс лв (С(в', ),...,В(в~,.есэ ииече Гц (С(ос,л1),...,((вс"ел)) в, в1 вс О отлит (...) —" Го И~ -'~л) "Гв(с(ввзц) -' (м~™ Р с а (. Правиле построения урезаеаай Рекурсивной схемы Лз Напомним, что в ((в, т) — зто термальное значение (см.
п. 3.5 в гл. 4) терма т для пути (в. В качестве главного терка схемы Вз возьмем терм Го (зх х~) Вот рекурсивная схема Яв.с, построенная описанным выше алгоритмом для стандартной схемы Все из рис. 4.2: Ге (л» у)1 Г (з, у) = Г (л, я)» Гв (х, у) = если Г (л) то Гв (х, у) иначе Гв (Ь (х), у (х, у)), Гв(х,у) = у. Тот факт, что преобразование первого этапа алгоритма сохраняет эквивалентность, следует из теоремы 6.3 и корректности лт-эквивалентности. Покажем, что рекурсивная схема Вз, построенная на втором этапе, эквивалентна стандартной схеме Я.
Зафиксируем для этого произвольную интерпретацию 1. Выписывая протоколы выполнения программ (8, Е) н (Вл, 1), будем отмечать значения переменных в схемах при «прохождении» очередной вершины А, отличной от преобразователя, н соответственно при подстановке этих значений в определение рекурсивной функции Гл. В начальный момент эти значения совпадают, так. как для любой переменной з начальное значение равно 1 (х). На- чальной вершине схемы В соответствует главный терм схемы Вз Остается эазютить, что если при переходе от распознавателя А в протоколе программы (8, 1) к следующему распознавателю или эаключнтелънон вершине В, а также при переходе от вызова функции Рл в протоколе программы (Вз, 1) к следующему вызову Рс условия проверяются на одном и том же состоянии памяти, то результаты проверки условий будут совпадать (так что В = С), а изменение значении переменных х,..., х„будет осуществляться по одним и тем же правилам: для перевычисления этих аначеиий в обоих случаях используются одни н те же термы, а именно Ю (иуа, хз),..., Ф (ирь, х„).
В протоколе выполнения программы (Вз, 1) любое значение терка содержит ие более одного вхождения определяемого функционального символа. Если протокол программы (8, 1) бесконечен, то бесконечным будет и протокол программы (Вз, 1). В нем с прохождением череа очередной распознаватель А вызов фузкцин Гл заменится на новый вызов г"в и т. д. Если жв протокол выполнения программы (8, 1) конечен, то протокол выполнения рекурсивной программы (В„1) тоже конечен, так как, согласно устаповлвнной выше связи между протоколами, в рекурсивном уравнении, соответствующе«) эаключителънои вершине, произойдет замена вызова базовым термом.
При этом та1 (8, 1) = уа1 (Вз, 1). П, Задакке 83. А. Постройте протоколы аыполаеааа программ (8е.е. 1«), (Я«.«, 1«), (3« °, 1а), где 1« и 1« — аатеРпуетадал аз п. 2.3 гл. 4, а 1а — саобоДааа вктерпретадаа вз и. 3.2 этой же главы. Б. Траасларуйте а рекурскэвые схемы стакдартаые слепы 3«л, 3«. °, 8«.з и 3«.«.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
