1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 42
Текст из файла (страница 42)
Такие операторы называют операпьоральи гьыоеа процедур. Схема процедуры состоит нз заголовка и тела, разделенных символом равенства. Заголовок аземи процедуры имеет тот же вид, что и левые части Рекурсивных уравнений: Рт > (хь,..., х„). Тело схемы процедуры — это стандартная схема того же тьша, что и главная схема. Заключитель- ный оператор в теле процедуры всегда одноместен (стоп (х)). Па- мять схемы процедуры (т. е.
переменные, входящие в заголовок и тело схемы процедуры) не пересекается с памятью главной схе- мы и памятями других схем процедур. Примеры схем с процеду- рами: а) 8, 1з. (старт (х), Р (у, о, ю) = (старт, 1: з:= х, 1: если р (у) те 2 иначе 4, 2: и:=а, 2: у:=5(у). 3: х:= Р (х, х, и), 3: о:= б (о, ю) на 1, 4: и:= Ь, 4: если д(ю) те 5 вязче 6, 5: з:= Р (з, х, и) 5: у:= о, 6: стоп (з)) 6: стоп (у)) С(г, г) = (старт, 1: если д (г) то 2 иначе 3, 2: с.=У(г), 3: стоп (г)); б) Я 4: (старт (х), Р (х) = (старт, 1: у:= Р (х), 1: еслн р (х) то 2 иначе 3, 2: степ (у)) 2: о:= х на 8, 3: з:=у(х), 4: з:=Р(з), 5: и:=й(х), 6:..:.= Р (и), 7: о:= 7'(х, и), 8: стоп (о)). Выполнение интерпретированных схем с процедурами подоб- но выполнению стандартных схем, но имеет следующие особенно- сти.
1. Первой начинает выполняться интерпретированная главная схема (главная программа), все операторы которой, отличные от вызова процедуры, выполняются так же, как и операторы интер- претированной стандартной схемы. 2. Выполнение оператора вызова й: х:= Роо (у„..., у„) (как в главной схеме, так и в телах процедур) при текущем состоя- нии памяти Ю включает следующие действия: а) осуществляется переход к выполнвнвю (интерпретирован- ной) схемы процедуры (или процедуры) с заголовком Ро*> (хг,...
..., х„), причем в качестве качельного значения каждой перемен- ной х„1 ~( $ с л, берется значение )У(у,), а начальное значение любой другой переменной х в теле процедуры равно Г (з), где У— интерпретация; б) посла завершения выполнения процедуры результат (зна- чение переменной, упомянутой в заключительном операторе тела процедуры) присваивается переменной х в операторе вызова рл х:= Р (ут,..., у„), а значение любой другой переменной у из па- мяти главкой схемы остается равным значению )у (у); в) осуществляется переход к выполнению оператора с меткой й + 1 или оператора с меткой, указанной в переходе оператора вызова.
3. Выполнение тела процедуры осуществляется точно так же, '"как выполнение главной схемы. Обозначим класс схем с процедурами т". (Р). Т е о р е и а 8 6. Класс рекуреиеных схем тракелируем в класс сдтм с проце0урами, т. е. т"(В) «( У (Р). Д о к а з а т е л ь с т в о. Алгоритм трансляции рекурсивных схем в схемы с процедурами: 1) строится главная схема вида (старт (уд,..., у„), 1» у:= т (у„..., у„), 2: степ (у)), где у — новая переменная, не входящая в память рекурсивной схе- мы, а т (уд,..., у„) — главный терм рекурсивной схемы; 2) памяти всех рекурсивных уравнений переименовываются так, чтобы они взаимно не пересекалвсь я не пересекались с па- мятью главной схемы; 3) каждое рекурсивное уравнение Р» (хд,..., х„) = если р (х»„..., х»,) то т», иначе т,о заменяется схемой процедуры Р» (х„..., х„) = (старт, 1: если р (х»„..., х»,) то 2 иначе >», 2: К (о, т»д) на т, ул о (" т»о) т: стоп (и)) ° где Ю (о, т»д) и Я (д>, т»,) — фрагменты схем, называемые операки>р- пыми раскрытиями простых термез т»д и т»о.
Операторное раскры- тие Я (о, т) простого герма ч определяется следующим образом: а) если ъ = х, то Я (и, т) = »> д= х; б) если т = $<"> (тд,..., т„), где 5»"> — базовый или опреде- ляемый функциональный символ, то Я (о, т) представляет собой последовательность а„а„..., а„, и >= $»"> (з ..., з„), г де хд,..., з — новые переменные, а з»:=х, если т» — переменная х, а»= Я(з», т») в противном случае. Например, 8 (о, ) (Р (у (х)), Р (тд (х)))) — зто последовательность операторов и: = у (х), зд:= Р (и), ю: = й (х), зо: = Р (а>), и : = ~ (хд, «,). На этом мы завершаем докааательство, считая, что содержательддого анализа алгоритма трансляции и правил выполнения свободао интерпретированных рекурсивных схем и схем с процедурамв достаточно для того, чтобы убедиться в эквивалентности исходной и построенной схем.
Факт, что исходная в построенная схемы имеют разные памяти (в частности, в схеме с процедурзмв болыпе переменных за счет раскрытня термов), не вносит осложнений, так как все добавляемые переменные используются в качестве времен- У В. Е. Котов, В. К. Саеельфельд 493 ных «рабочих ячеек», они не входят в заключительный оператор главной схемы и их начальные значения, задаваемые интерпретациями, ке вляяют на результаты.
( ) Т е о р е м а 8.7. Класс схем с процедурами транслируел» в класс рекурсивных схем, т. е. У (Р) в У (В). Дока з а тел ь с та о. Нюне описан несложный алгоритм трансляции. Прежде всего, с помощью описанного в теореме 8 1 алгоритма главная схема Я и тела схем процедур Р„ ..., Р„ независимо транслируются в рекурсивные схемы Вз и В»р» (1 = = 1, ...,и). При этом не делается никаких различий между базовыми и определяемыми функциональнымн символами исходной схемы. Пусть т» — главный терм схемы Вз, а т~ (1 = 1,..., и)— главный терм схемы Вр, К системе рекурсивных уравнений, получающейся объединением уравнений схем Вз и Вр«(1 ~ 1 «( и), добавим каждое из уравнений Р» (х1» . » хп) = ти где Г» (хм..., х„) — заголовок схемы процедуры Ри для $ = = 1,..., и.
В качестве главного герма получающейся при этом рекурсивной схемы возьмем терм с,, [ ] Т е о р е м а 8.8. Класс рекурсивных схем и класс схем с процедурами раеномощны. Д о к а з а т е л ь с т в о. Следствие теорем 8.6 и 8.7. ( ) Т е о р е м а 8.9. Класс схем с процедурами строго мощнее класса стандартных схем, т. е. У с У (Р), где У вЂ” класс стандартных схем, Д о к а з а тел ь с т в о. Следствие теорем 8.3 и 8.8. П 4.2. Частичная трансляция схем с процедурами.
Хотя не существует алгоритма трансляции схем с процедурами в стандартные схемы, рассмотрим преобразование схем с процедурами, которое можно назвать частичной транслзцией. Преобразование представляет собой итеративный процесс, который всегда завершается построением схемы, причем зто или стандартная схема, или схема с процедурамя (часто с меньшим числом процедур, чем исходная). Основу рассматриваемого преобразования составляет операция подстановки тел схем процедур вместо операторов вызовов. Этз операция — аналог известной в программировании открытой подстановки процедур.
Подстановка вместо инструкции вызова й: г:=Р,(уи...,у„) иа 1 тела схемы процедуры, определяющей функциональный символ Ри производится следующвм образом. Схема процедуры копируется, каждой переменной памяти этой схемы сопоставляется взаимно однозначко новая переменная, а каждой мотке в теле схемы — новая метка, ие встречающаяся в главной схеме и в телах !94 всех схем процедур. Все вхождения старых переменных и меток в инструкции копии тела заменяются соответствующими новызди переменными и метками. Заголовок копии и оператор старт в копни тела элнмиивруются, а метка 1 заменяется новой меткой ш. Заключителыдый оператор стоп (и) заменяется на з: = о нв 1; инструкция дд: х:= Р~ (уд,..., у„) — последовательностью инструкций яд х,д=уд,...,х„д=у ва ш, где хд,..., х„— новые переменные копни схемы процедуры, со- ответствующие старым переменным из заголовка этой схемы про- цедуры.
На этом подстановка завершается. Например, подстановка вместо оператора вызова й у:= г' (у), входящего в главную схему схемы Я д, тела схемы процедуры следующим образом меняет главную схему: (старт (х), 1:х:=х яа9, 2: стоп (у), 9: если р (хд) то 10 вначе 11, 10; од:= хд иа 16, 11: *д ..— — у(хд), 12: з,:= Р(зд), 13д ид:= дд(хд), 14: ид .
—— Р (ид), 15: ид.— — 1(~ь ид)» 16д у:= ддд ва 2). Начальный шаг частичной трансляции — сопоставление каж- дой инструкцви вызова в главной схеме и в схемах процедур вспо- могателъвого списка определяемых функционалъных символов. Для инструкций вызова в главной схеме этот список пустой, а для инструкций вызова в схемах процедур он состоит из одного сим- вола, определяемого этой схемой процедуры. Следующий шаг повторяется итеративно сначала для главной схемы, затем для каждой схемы процедуры, затем снова для глав- ной схемы и так далее, пока можно осуществлять хотя бы одну подстановку.
На этом шаге вместо каждой инструкции вызова Й: г д = Р; (у»..., у„), во всяомогателъном списке которой (уъ,..., гдд) нет символа Гд, подставляется тело схемы процедуры, определяющей функ- циональный символ Гд. В списки всех новых внструкций вызова, вошедших вместе с подставленным фрагментом, добавляются эле- менты списка (Ръ,..., дгб) и символ Рд. Если в главной схеме после некоторого очередного шага нет инструкции вызова или нельзя осуществить ни одной вз подста- новок из-за невыполнения условия применения подстановки, час- тичная трансляция заканчввается, а те схемы процедур, которые определяют функциональные символы, не встречающиеся боль- ше в главной схеме в ни в одной вз схем процедур, элиминируют- 7Ф 1йъ ся.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
