1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 41
Текст из файла (страница 41)
хссах)» = 1, яр= бр»ю в противном случае, с»ч»ю~ если (Рч»ю)» (Ям-» п»х)» = 1, Рг= у,»»ю в противном случае, для Й = 1,..., т, а»р (Й) — номер уравнения схемы, используе- мого иа й-и шаге построения протокола. Алгоритм трансляции. Опишем способ пастрое- яия стандартной схемы Яа, эквивалентной схеме В. В дополне- ние к переменной х схема Яя содержит еще три переменные и, и, »р и состоит из трех фрагментов-блоков А, В и С (см. рис. 8.4). Эти блоки, в свою очередь, составлены из множества злементариых фрагментов, которые строятся по уравнениям схемы В; »-му урав- нению соответствует фрагмент вида а »Н»» Ь с где р — одна из переменных и, »т или ю, а а, Ь и с — метки; если .либо ()о либо 6» — пустая цепочка, соответствующий оператор не включается во фрагмент.
»» приведенном ниже описании схемы Яя эти метки используются для понимания того, каким образом соединяются фрагменты при построении Яа. Когда соединяется несколько фрагментов, всякий выход ведет к фрагменту, имеющему ту же самую метку на входе. Приведенный вьппе фрагмент, соответствующий»-му уравнению, будем изображать следующим образом: Первыи блок схемы Яя (блок А) составлен из и + 1 фрагмента (рис. 8.3, а), а их соединение определяется метками входнглх и выходных дуг. Выход из блока А имеет метку О.
Блок изображен на рис. 8.4, "цикл указывает, что соединения (с метками б > ) 0) проиаеодятся внутри блока. На рис. 8.3, 6 изображен блок А для схемы В в. тат ал 6 Цв! гбО 8мкал сэ блока Ю Ряс. 8.8. Построение блока А стакдарткой схемы Лл, акакааловпюй схема Ж а — фрагменты Лля сборка блока А; 6 — блок А Лля стакдарвмой схомм- лв.в Понятно, что для свободной интерпретации 1 выход из блока А программы (Яв, 1) происходит со значением переменной и = 'я'„,я в ...ятктл', равным правой части результата ча)(8л, 1).
Таким образом, в блоках В и С к значению переменной и должны быть применены функции, составляющие левую часть результата схемы прн интерпретации 1. Для соединения фрагментов в блоках В и С использованы метки, представляющие собой пары чисел (см. рис. 8.4). Внутри блока В выход фрагмента, перевычисляющего значения переменном и, соединяется с фрагментом, перевычисляющим ю, и наоборот, однако выходы с метками 01 фрагментов, перевычнсляющих и, разрывают цикл в В и ведут к фрагментам, которые изменяют значение переменной и. Блок В имеет л входов В„..., В„. Если 1-е уравнение содержит выход схемы Я, то вход В» ведет к распоанавателю. е.! г>е ! Рвс. 8.4. Структура схемы 8в .с условием р!г, соответствующая выходная дуга которого (с меткой й)) ведет к заилючителыюму оператору стоп (и).
Эквивалентность слем В и Юв. Мы видели, что и моменту вывода из блока А при выполнении программы (Юв, 1) переменная и имеет значение (и и !... и и х)!. Предполо!ким, что переменной и к моменту очередного входа в блок В приовееио значение (р ! ... р„, гпмп д... и х)! с некоторым !па -'Й ~ я«, так что следующим к и должно применяться р „. Блок В ' »ожидает» входа по метке Вп где « — номер следующего уравнения, которое используется при подстановке ожидаемого значения (я„... ягх)г переменкой и.
Это значит, что после т — й повторений «цикла» внутри блока В переменная и получит значение (я„... ягх)п а переменная ю — значение (и„„»... я«х)ы— дело в том, по выход по метке Ст из блока В произойдет раньше (⫠— й)-го присванвання переменной «э. Таким образом, р» будет применяться к аиачению переменной и точно так, как это делается в схеме Л с использованием 1-го уравнения. После этого блок С использует значение перемекнои ю для того, чтобы вновь установить и на следующее значение, ожидаемое в блоке В. Происходит й + 1 повторений «цикла» в С, прежде чем «э получит значение (и ...
ягх)ы так что в момент выхода из блока С переменная и будет иметь значение (я» «... я«х)ы как и требовалось. Наконец, если мы,приходим к блоку В со значением переменной о = = (я~... ягв)г, то выполнение программы заканчивается выпалнением оператора стоп (и). Таким образом, описанкая конструкция стандартной схемы Яв позволяет восстанавливать левую часть результата программы (Л, 1) при любой свободной интерпретации 1.
Если же программа (В, 1) аациклизается, то программа (8э, 1) зацикливается уже в блоке А, что легко усматривается иэ структуры этого блока. Следовательно, построенная стандартыэя схема Юв эквивалентна исходной линейной унарной рекурсивной схеме В.
Ц На рис. 8.5 изображена стандартная схема 8»», эквивалентная рекурсивной схеме Я» «и построенная с помощью описанного в докааательстве алгоритма трансляции. 3.2. Праволииейиые уиириь«е схемы. Как видно из доказательства теоремы 8.4, алгоритм трансляции линейны* уиарных рекурсивных схем в стандартные схемы достаточно сложен, и получаю«цаяся схема громоздка.
С трудностью реализации рекурсивных процедур програзааюты столкнулись давно (в ряде ранних трансляторов языка Алгол-60 рекурсивные процедуры не были реализованы). В следующей главе мы рассмотрим стандартные схемы, обогащенные специальными программными примитивами или особой оргаиизапдей памяти, и эти новые средства позволяют значвтельно упростить проблему трансляции рекурсии. Класс линейных унарныт. рекурсивных схем не исчерпывает. все рекурсивные схемы, которые транслируются в стандартные. (например, схему Ю«.ы в задании 8.6, которая не является унарпой, можно транслировать).
Но класс укаркых схем не транслируем в класс стандартных схем. Примером унарной схемы, дли ко-- торой не существует эквивалентной стандартной схемы, является В Р (х), Р (л) = если р (х) то 1(л) иначе у(Р (Р(й (л)))). ттаюттит г ! и: ш !»:-» 1 ! 1 Ри с и:=Ге Я 1 О 1 О Ркс. 8.5. Стаядартяая схема л,л, экакаалеятяая рекурсивной схеме 8а.а В то же время класс стандвртяых схем не транслируем в класс унарных схем (например„схема Ба т), поэтому зтн классы схем не сравнимы по мощности.
В начале параграфа мы сравнили унарные рекурсивные сленге со схемами Янова. Из последнего примера (схема Юа.те) ясно, чтокласс унаркых рекурсивных схем мощнее класса схем Янова. Каков же подкласс унарных рекурсивных схем равномощен схемам Яио!та? »т ти»т=р» ! 1 ! ! аш 1 о ! ( ки ~ш ш: рш ! 1 1 1 1 1 Рш 1 0 1 1 ! 1 1 1 1 1 ! 1 1 ! ! ! ! ! 1 1 1 1 1 ! ! 1 1 1 г ! ! Ри 1 ! 1 1 степ!и! шт» 1 ! ! 1 т?» ! 1 о 1 ! ! 1 »=-~»»т р» ! ! ! ! ! и» 1 1 о 1 1 1 йш Юш 1 о 1 ! и. "уи.
и: ри .ш: Иа шт' уш Праеелинейнмми упорными рекурсиеними стеками называют линейные унаркые схемыь у которых термы-альтернативы в пра- вых частях уравнений — это или бааовые термы, или термы, начи- нающиеся определяемым функциональным символом. Т е о р е м а 8.5. Класс праеелинейнмх унарнмх рекурсивных схем и класс схак Янеза раенгмощаы.
Д о к а а а тельство. Схемы Янова транслируемы в ре- курсивные схемы как подкласс стандартных схем, и иа способа трансляции, предложенного в доказательстве теоремы 8А, прямо следует, что получаемые рекурсивные схемы являются праволикей- ными унарными. Легко заметить, что для любой свободной ннтерпретации ре- зультат та( (3, 1), где З вЂ” праволинейная унарная рекурсивная схема, имеет вид (см. доказательство теоремы 8.4) Ф и я ь ...
пьх, где и — число значений в протоколе; пь (( ( й ~( пь) — зто (8 <ю кли бг(ю; (р (й) — номер уравнения, используемого на й-м шаге построения протокола. Алгоритм трансляции праволкнейных унарных схем в схемы Янова теперь очевиден, Он совпадает с алгоритмом построения блока А стандартной схемы Зп в доказательстве теоремы 8.4, эа исключением следующего: вместо переменной и испольауется единственная в схеме переменная х, а выход иэ блока А присоеди- няется к оператору стоп (х).
Две переменные х и и в теореме 8.4 нужны были для того, чтобы сохранить для блоков В и С стандарт- ной схемы Зв информацию о начальном значении х, а сейчас этого не требуется делать. ( ) Задание 8.6. Травслкруйте рвкурсзввие ехмьиь а) двлз: е'(г), е' (г) = есгв р (г) те г вяа ае 1 (г, г" (е (г))); б) дель" Р (г). е (г) = есзв р (х) те х вязче 6 (г), 6 (х) = сслв г (г) тэ Г (г (е)) кааче 1(Р(г)). 4 4. Схемы е процедурамн 4А.
Сравнение с классом рекурсивных схем. Схема с процедурами — это модель алголоподобных программ с процедурами. Она строится в объединенном базисе классов стандартных и рекурсивных схем. Схема с процедурами состоит иэ двух частей — глазной стемм и множества схем процедур. Главная схема — это стандартная схема, в которой имеются операторы присваивания специального вида х .= Р<") (у,..., у„), где х, уд,..., у„— переменные, г"~"> — определяемый функциональный символ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
