1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 18
Текст из файла (страница 18)
Иэ этого определения стандартной схемы следует, что однв и тот же оператор может помечать несколько вершин схемы. В тех случаях, когда это не приводит к двусмысленности, условимся говорить о вершинах схемы как об ее операторах. Ото позволит вам вместо длинных выражений вроде «вершина схемы, помеченная оператором х:= у (х)» употреблять более короткие: «оператор х:= у (х)».
Чтобы можно было упомвнать вершины схемы в рассуждениях о них, вершвны снабжаются именамн. В качестве таких имен обычно попользуются целые неотрицательные числа (мы будем назм- «) В тол «луч«як, когда вз ковт»котя аско, о каком классе схем идет речь, мм будем кротко гозорат» «слома» вместо, капркмвр, «ставдартвля ело° с» программ». 7б вать их метками вершин).
Будам считать, что начальная вершина схемы всегда помечена меткой О; если в схеме п вершин, то они помечены метками (О,..., и — 1). Введем обозначение арг (и) для множества переменных, ввляющихся аргументамв оператора и, и реэ (и) — для множества переменных, являющихся результатами оператора и в стандартной схеме.
Говорят,что переменная х задана на дуге е схемы 8, если любой путь в 8, начинающийся начальной вершиной и иокчалкцийся дугой е, содержит хотя бы один оператор с результатом х. Схема 8 называется праеиаьяой, если на каждой ее дуге е заданы все переменные из множества арг(кон(е)). В дальнейшем мы будем предполагать, что стандартные схемы правильны. Требовввие правильности схемы соответствует программистскому правилу аапрета использования значений таких переменных, которые не заданы. 3 а д е и и е 4Л. Сформулируем задачу глобальвого анализа схемы о следующим обрезом. Злемевтеми полурешетки свойств будут подмиожестее перемеввых вз Хв.
В качестве ояерзцви /~ этой полурсшетки вою мем обьедввекие подмиожестэ ююжестве Хл. Начельвея резметяе сопоставляет веждой дуге пустое мвакестэо перемеввы* (т.е. едпквцу втой полурешетви). Семзвткчесяея функция определена следувецвм обрезом: для пары смювяых дуг (г, е') /~~ (Ж) М () рез(кеч(е)). Докежвте, что схема б преевльва тогда к только тогда, вогдз прв стзцкояервой разметке р для опксеикой задачи еключеиие арг (кои (е)) ~ р (е) еыполкяется для всех дуг е сземм б.
3 е де и п е 4.2. В предыдущем седекии для определепия свойства превпльвоств схемы использована разметка для решоккя прямой зедзчи злобзлького еюипие. Можво лв распознавать прееилыюсть схемы с помощью алгоритме резметкв, решающего сбреткую задачу глобельиого анализа (с дкстрвбутаввымк преобразователями свойств)7 Пример (правилъной) стандартной схемы в графовой форме приведен па ррс. 4.2, а. Начальная и заключительная вершины,. а также вершины-преобразователи изображены прямоугольниками, воршины-распознаватели — овалами. Операторы, мстящие вершимы, выписаны внутри прямоуголышков в овалов.
2.3. Стандартная схема (ливейиап форма). Опишем, каи по стандартной схеме 8 в графовой форме можно строить ее линейную форму. Для этого множество специальных символов расширвм дополнительными новыми символами (:, иа, если, те, иначе). Стандартная схема в линейной форме представляет собой последовательность инструкций, которая строится следующим образом: 1) если выходная дуга началъной вершины с оператором старт (хю ..., х„) ведет к вершине с меткой (, то начальной вершине соответствует инструкция рл старт (хю..., х„) на ц 2) если вершина схемы 8 с меткой 1 — преобразователь с оператором присваивания х:= т, выходная дуга иоторого ведет 77 а Ю д Рэс. 4.2. Схема и программы: о — азама 8 .а; 6 — программа (8а.а, Хг); а — . программа (Яа.а, 1а) и вершине с меткой й, то этому преобразователю соответствует пнструкцня йх:=ъ ней; 3) если вершина схемы Я с меткой 1 — эаключителэная вершина с оператором стоп (г„..., г ), то ей соответствует инструкция й стоп (ъ, 'та)' 4) если вершина схемы 8 с меткой г — распознаватель с условием р (тг,..., та), причем ъ-дуга ведет к вершине с меткой й, а О-дуга — к вершине с меткой гО, то этому распознавателю соответствует инструкция й если р (т,..., ъа) то й иначе гО; Ь) если вершпка схемы 8 с меткой г — петля, то ей соответствует инструкция й петля.
Таким образом, если в схеме 8 имеется и верпшн, то в линейной форме ей соответствует последователэпость иа и инструкций, помеченных метками О,..., и — 1. В линейной форме схем часто исполээуют следующие сокращения записи: =' 1. Если некоторая инструкция кисет вид й А иа й, где А— оператор присваивания или началэиый оператор, причем й = = 3 + $, то вместо нее пишут й А (опускание переходов на следующую инструкцию). 7В 2. Если на некоторую инструкцию нет переходов, то ее метки можно опускать (опускание меток). В частности, первую инструк- цию схемы можно записывать без метки О, поскольку, в соответст- вии с определением схемы, на нее нет переходов.
Вот полная и сокращенная линейные формы схемы Я«г, при- веденной на рис. 4.2, а: О: старт (х) на $, старт (х), 1:у:=ана2, у:= а, 2: если р (х) то 5 иначе 3, 2: сели р (х) то 5 иначе 3, 3: у:= у (х, у) иа 4, 3: у:= у (х, у), 4: х:= Ь (х) на 2, х:= Ь (х) на 2, 5: стоп (у). 5: стоп (у). 2 4. Итерпретация, программа. Стандартная схема не явля- ется, как уже не раа отмечалось, записью алгоритма, и с ее по- мощью можно исследовать только структурные свойства программ, но нэ семантику вычислений. При построении «семаптическойг теории схем центральными становятся такие понятия, как интер- претация, интерпретированная схема (программа) и функциональ- ная эквивалентность схем программ.
Отметим сразу, что это не единственная возможность построения содержательной теории схем, существует другой подход, так называемая «формальнаяэ теория схем программ, которая пе нсполъвует вводимое ниже по- нятие интерпретации и, таким образом, не устанавливает явной связи между схемами и вычислениями.
С этим подходом мы по- знакомимся в п. 3.5 настоящей главы. Пусть задан некоторый базис 5«, в котором определен класс стандартных схем. ЕЕнэзгриргтацигй базиса 33 е обаагвзи изяягр- яргвиярги Р называется функция 1, которая сопоставляет: Ф) каждой переменной х иэ базиса зг — некоторый элемент' «) = 1 (х) из области интерпретации Р; 2) каждой константе а иэ базиса — некоторый элемент гг = =1(а) изЮ; 3) каждому функцианалъному символу ф"> (я,.в 1) — всю- ду определенную функцию р("> = 1 (р">)г Ю"-«-Р; 4) каждой логической константе рээ — одвп ка символов гпзо- жества (О, 1); 5) каждому предикатпому символу р~">, где п ~1,— всюду определенный предикат ЕК"> = Е (р~">)г Р" -«(О, Ц.
Определение ннтерпретации не уточняет природу объектов мно- жества Р, в конкретнъзх примерах мы будем фиксировать в ка- честве области интерпретации множество всех чисел илн множест- во всех слов в некотором алфавите или подмножества этих мно- жеств. Интерпретация называется конечной, если ее область Ю— конечное множество. Пара (8, 1), где 8 — схема в базисе бг, а 1 — интерпретации етого базиса, называется ияэггряргягирогаяной сеаибартиой азг- люй, кли (стандартяой) программой.
Определим понятие еыяаа- ягяиа ярогрампм. Сестолнием памяти программы (8, 1) назовем фуикцзю И»: Хя Р, которая каждой переменкой х из памяти схемы 8 сопоставляет элемевт»Г (х) из области интерпретации Р. Влемеит '$т' (х) называется значением леременной х е сося»сании»»; запись»у = = »Р" озвачает, что два состояния памяти»У и И'" совпадал»г с точностью до зкачеиий переменной х, т.
е. для всех уб"- Хз у чь х-+»у(у) = И" (у). Еслв Х = (х„..., х„) — некоторый вабор перемеивых из Хо, то )т'(Х) = (»у(х»),..., )т (х„))— набор апачевий перемевиых хм..., х„. Начаяьнмм состоянием ламяти Хз при иитерпретацки 1 назовем состоявие И" такое, что»т'» (х) = 1 (х) для любой переменной х из Хз. Значение терна с при ивтерпретацви 1 и состоянии памяти»у (обозиачевве: т, (»Р)) определяется следующим образом: $) если т = х, где х — переменная, то тг (И') = »У (х); 2) если т = а„где а — константа, то т» (»У) = 1 (а); 3) если т =)оо (с„...,т„), то т» (И') =1(1~">) (гы (»У), т» (%У), т»» (Щ,..., т„» (Щ). Аиалогичяо определяется значение теста л при интерпретации 1 и состоявви памяти»У (обозначение: л» ()т')): если я = =рос(т„...,т„), л »0, то 1 (р(ю) (т ()У) т„г ()У)) Конфигурацией о) прогрея»ми (8, 1) назовем пару и = (», Щ, где» вЂ” метка вершины схемы 8, а»У — состоявие ее памяти.
Выполиепие программы описывается конечной или бесконечной последозательвостыо конфигураций, которую мы назовем лротоколом еиногненил программы. Протокол (и», и»,..., и„и,+„...) выполнения программы (8, 1) определим следующим образом (виже Ц означает метку вершины, а )у» — состояние памяти в (-й конфигурации протокола, и, = (й», уЮ): $) и» = (О, И'»), где И'о — иачальиое состояние памяти схемы 8 при иитерпретацви 1. 2) П ъ и, — (ь, )у,.) (-я коифигурацвя протокола, а О— оператор схемы 8 з вершине с меткой йо Если Π— заключительвый оператор стоп (т,..., т„), то и, — последняя ковфигурацкя протокола, так что протокол коиечев. В этом случае говорят, что программа (8, 1) останазяиеается, а последовательность авачеввй т»г (Щ, тгг (Щ,..., т„г (Иг») объявляют резуль»лаппьв та) (8, 1) омлогнения лрограмми (8, 1). В противном случае, т.
е. когда Π— ие заключвтелввый оператор, в протоколе имеется следующая, ((+ $)-я конфигурация и,+г — — (й»+„Туот), причем ° ) В лвтсратуре попользуются териппи гссстсявве яппоявсяая» (сошрптамоп зиао, схгспйсп вФате) вместо «повфягуузцвя» в спослвдоязтеяьвссть гяпсявсвяя» (ссшрпФа»»оп авопессс, ехгспмоп гсспспсс) яигсто «протокол». Наши тсриавя завис»яомс»и вг тгсрвк машяв .»ьюрвягя для того, чтобы педчсрввуть аваяогшо изыду состзетстяующяив повятпяип. 80 а) если Π— началыпдй оператор, а выходящая иа него дуга ведет к вершине с меткой д, то йд+, — — 1 и И'„, = дг;; б) если Π— оператор присваивания х:= г, а выходящая нз него дуга ведет к вершние с меткой д, то Й<+д = д, дгыд = »до «д мд (х) = тд ( дд)в в) если Π— условный оператор и и пд (»г;) = 1д, где Л 6= е= (О, Ц, а выходящая из этого распознавателя Л-дуга ведет к вершине с меткой (, то йд+д = ( и $г'д+, —— »К,; г) если Π— оператор петли, то й,+д — — лд и Идд+д — — И'„так что протокол бесконечен.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
