1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 46
Текст из файла (страница 46)
Здесь также используется обычный программистский прием. .Элементы Ны И», ..., д„ состояния магазина М становятся элементами состояния массива Ам с теми же порядковыми номерами. 'Нулевой элемент состояния массива и элементы с номерами боль'ше и равны 1(А) или содержат так называемый «мусор». Значение ;, четчика в процессе выполнения построеннной интерпретиро''ванной схемы с массивами указывает на «верхушку магазина» ;.и массиве Ам. П) Т е о р е м а 9.9.
Классы У (А) и,'У (М) равнсмои)ны. Д о к а з а тел ь с т в о. Прямое следствие из теорем 9.7 )и 9.8. П 3 а д а и и е 9А. Покажите, что классы Я (А) и,9' (»А) рави«мощны. 2.5. Магазинные и рекурсивные схемы. В этом разделе мы по,,кажем, что рекурсивные схемы транслируются в магазинные, ."и зто не является неожиданностью, так как почти все практичес,'кие методы реализации рекурсии основаны на применении мага(:зинной (или становой) памяти.
з» 2»1 В предыдущей главе установлено, что рекурсивные схемы транслируются в схемы с процедурами. Поэтому достаточно продемонстрировать транслируемость класса ~х'(Р) в класс магаанниых схем. Описываемый алгоритм трансляции включает как первый этап трансляцию схем с процедурами в класс схем с одним матаакном, но эти схемы обогащены дополнительным средством, а именно — метками-символами и специально выделенной переменной, значениями которой являются метки.
Таким образом, метки-символы могут запоминаться, в том числе в магазине, и затем использоваться в переходах. Этот этап трансляцки отслеживает практические методы реализации рекурсии, На втором этапе осуществляется освобождение магазинной схемы от меток, и результатом является схема из класса У (1М). Промежуточная магазинная схема с метками принадлежит классу .У (1М, л.).
Схемы нэ этого класса — схемы с одним магазином и со следующими особенностями: а) инструкции не имеют числовых меток, но могут помечаться метками-символами; б) базис класса содержит выделенную интерпретированную переменную, областью значений которой является множество меток (Ь„Ьм..., Ь ); в) все переходы в инструкциях присваивания и условных операторах — метки-символы или выделенная переменная; г) кроме того, выделенная переменная и может входить только в специальные операторы засылки метки (ю:= л",) и в операторы над магазином (М:= и, ю:= М).
Смысл использования меток-символов, выделенной переменной и модифицированных операторов при выполнении интерпретированных схем иа класса У(1М, А) не требует специальных пояснений. Л е м м а 9.1. Классы рекурсивных схем и схем с процедурами трапслируемы в класс г" (1М, А). Д о к а з а т е л ь с т в о. Рекурсивная схема транслируется в схему с процедурами посредством алгоритма из теоремы 8.6.
Пусть 2 = (г, г„..., г ) — множество переменных, получающееся в результате объединения памяти главной схемы и памяти всех схем процедур исходной схемы с процедурами. Каждая инструкция вызова к: г:= г"';"~ (у„..., у„) на т з аменяется следующим фрагментом: к: М:= г1,..., М:= г, — запоминание состояния памяти перед переходом к процедуре; и:=Ь вЂ” запоминание метка возврата; М;=ю х:= у„..., х„:= у„иа Ьг — передача аргументов в за.
головок процедуры и переход к процедуре; Х: г:= г на л« вЂ” переменной г присваивается вычисленное значение функции, где М вЂ” магазин; и — выделенная переменная для хранения меток-символов; г — новая переменная, г Я~ Е; Х вЂ” метка-символ возврата. Заголовок каждой схемы процедуры Р,(х„ ...,х„) и оператор старт злимвнируются, а метка 1 в теле процедуры заменяется меткой Хг . Оператор стоп (о) в теле каждой схемы процедуры заменяется фрагментом г:= о, и:= М г,:=М,...,г,:=-М на ю, Результат такого преобразования — магазинная схема с одним магазином М и метками-символами, которые используются наря- ду с метками-числами.
Очевидным способом метки-числа можно элимн пировать, заменив их в переходах метками-символами. Полученная схема Яь принадлежит классу г' (1М, Х). В том, что схема Яь и исходная схема эквивалентны, убеждает содер- жательный анализ алгоритма трансляции. Магазин М может хранить любое число меток-символов и последовательных набо- ров значений переменных из 2. Прн рекурсивном вызове «старые» значения этих переменных запоминаются в магазине вместе с меткой возврата, указывающей контекст вывоза, т. е. следующий оператор, на который следует вернуться после того, как будет получено значение вызываемой функции. Когда значение функ- ции найдено, восстанавливается контекст и значения переменнь|х в этом контексте. Магазин оказывается пустым после возврата в главную ' схему.
Д В качестве примера приведем магазинную схему с метками Б «, эквивалентную рекурсивной схеме Я л (см. пп. 1.2 и 2.3 предыдущей главы) и схеме с процедурамн 3~л« (см. и. 4.1 той жв главы). Напоминаем, что для этих схем не существует эквивалент- ных стандартных и счетчиковых схем. Ю«».' Р (х) Р (х) = если р (х) то х иначе Х (Р (у (х)), Р (Ь (х))), Я ««. (старт (х), 1: у:= Р (х)„ 2: стон (у)), Р (х) = (старт, 1: если р (х) то 2 иначе 3, 2:э:=х на 8, 3: г:=у(х), 4: г:= Р (г)„ 5: и:= й(х), 6: и:.= Р (и), 7: е «= Х (г, и), 8: стоп (э)).
213 Условимся в примерах изображать последовательность опера. торов М:=- у„..., М:= у, одним «оператором групповой за- писи з магазин»: М:= (у„..., у„), а последовательность опера- торов у,:= М,..., у,:= М вЂ” одним еоператором групповой выборки из магазинам (у„..., у,):= М. Аналогично, (х,... ..., х„):= (у,,..., у„) — сокращенная запись «последователь- ной групповой пересылииг х,:= у,..., х,:= у„.
Яг «» (старт (у, х, з, и, о), М:= (у, х, з, и, и), .= Х'« М:= »э, х:=х на Хе, Х«» у стоп (у), Хе. 'если р (х) то Х иначе Х«, Х»» о:= х иа Х,», Х«: з:= д(х), М:= (у,х,з, и,о), ш»=Х« М:=ш, х:= г на Хэ, Ха. х:= 1, и:= Й (х), М:= (у,х,з,и,о), Хы М:= ш, х «'= и на Х», Х;. о:= ( (з, и), Х». 1:= о, »э:= М, (о,и,з,х,у):=М иа ш). Л е м м а 9.2. Путь Я вЂ” схема с процедурами, Х вЂ” инп»ер- праяация и во время выполнения программы (Ю„Х) некоторая про- цедура вызываеп»ся рекурсивно, т.
е. косее некоторого шага началь- ный оператор тела этой процедуры выполнялся и раз (и ) 1), а заключительный оператор — ни разу. Тогда для того, чтобы заключи»пельный оператор тела втой процедуры выполнялся и раз, необходимо, чтобы некоторый условный оператор р (х»,... ..., х,) выполнился дваясды при разных состояниях памяти И' и »у Х (р) (И'(~ ) ° - ' гу (~»)) чь Х (р) (Т+ ((~). ° ° ' »у (~»))- Доказательство.
Пусть й„й„...,й — последова- тельность меток инструкций тела процедуры, выписанная в том порядке, в котором эти инструкции выполняются в программе (Я, Х), причем Й =- 0 — метка начального оператора тела про- цедуры, выполненного первый раз, й, = Π— метка того же опе- ратора, выполненного и-й раз, и в этой последовательности нет ни одного вхождения метки заключительного оператора тела этой процедуры. Далее, пусть й;, й«,..., к„— последовательность 214 меток операторов тела процедуры, где й» = Π— метка я-го выполнения начального оператора тела, а й; — метка первого выполнения заключительного оператора тела процедуры. Если г ч. т, то й„' чь й, так как к„' — метка заключительного оператора, а й не может метить заключительный оператор. Если т~ т, то й Фй, так как к =О, а к' не может метить начальныи оператор тела процедуры. В обоих случаях видно, что начала последовательностей меток совпадают (по крайней мере, кь = = к,'), но затем последовательности различаются.
Это значит, что сунзгствует такое ь, 1 ( 1( ппп (т, г), что Й, = к;, но й,, чь чь к ы. Но зто может быть только в том случае, если й~ и к;- — два вхождения метки одного и того же условного оператора, причем результаты его выполнения в первом и во втором случае различны. ( ) Л е м м а 9.3. Есги Я вЂ” приведенном схема с процедурами (см. п. 4.2 гл. 8), то для любой интерпретации 1, прежде чем выполнится хотя бы один раз заключительный оператор в теле любой процедуры, дважды вычисляется некоторый, один и тот же, предикат 1 (р) при двух различных наборах аргументов (б„... ..., НД и (И(,..., И(), причем 1(р)(И„..., И,) ~1 (р) (б(,...
..., 4). Д о к а з а те л ь с т в о. Так как схема Я получена частичной трансляцией некоторой схемы с процедурамн, в главной схеме есть фрагменты-копни всех тел схем процедур и все оставшиеся в главной схеме вызовы — рекурсивные вызовы. Поэтому перед выполнением заключительного оператора в теле любой процедуры обязательно дважды вычнслится один и тот же преднкат, причем его значения будут различны (см. лемму 9.2). ( ) Л е м м а 9.4. Магазинные схемы из класса т' (1М, А), полученные трансляцией рекурсивных схем или схем с процедурами, транслируемы в магазинные схемы из класса т'(1М). Д о ка з а те л ь с т в о. Пусть магазинная схема Юс с метками получена из рекурсивной схемы или схемы с процедурами с помощью алгоритма трансляции, описанного в доказательстве. леммы 91. Пусть М вЂ” магазин в схеме Яс, ю — единственная выделенная переменная, значениями которой являются метки 1, Ь„..., А .
Магазинная схема Я из класса У(1М), эквивалентная схеме Юс, строится из й + 1 вспомогательной схемы из класса У (1М), где й — число предикатных символов в схеме Юс. Среди этих вспомогательных схем есть схема Яз, которую Грие и Кон- . стебль (92) назвали локатором, и схемы Ю,, Яг,..., Яю названные ими ркимитаторами схемы Юы 1 < 1 ~ (й. Схема р,-имитатор эквивалентна схеме Яс на множестве всех тех интерпретаций 1, в которых 1 (р) обладает некоторым заданным свойством (о немречь пойдет ниже). Схема локатор Я обнаруживает в схеме Яь предикатный символ, который для данной интерпретации 1 обладает заданным свойством, а если такого предикатяого символа. н е найдется, то локатор игнорирует рпимнтаторы, так как в этом случае оя сам способен повторить вычисления программы (Бы 1), пе используя переменную ш.
Построение р-имитатора. Сначала покажем, как строится р-имитатор схемы Бь для произвольного предикатного символа р. Для простоты полагаем, что р — одноместный символ. Переменной ш из схемы Бь в р-имитаторе соответствует т переменных ш„ ш, ..., ш , где т — число меток в схеме Бс,. Преобразование схемы в р-имитатор осуществляется следующим образом: а) каждый оператор присваивания ш:= Аь 1 ~ Ь*~ ~го, заменяется последовательностью операторов ш,:=- а, ..., ш,,:= а, ш~ .=- Ь, ш;,1:= а, ..., ш„,:= а, где а и Ь вЂ” некоторые константы, добавляемые в базис схемы Бь, б) каждый оператор ш:= М заменяется последовательностью операторов ш:= М,..., ш,:=- М; в) каждый оператор М:= ш заменяется последовательностью операторов М:= ш„..., М:= ш; г) каждый оператор присваивания х:= т иа ш ааменяется фрагментом (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
