Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 104
Текст из файла (страница 104)
Однако для вупэсго(Х + У 7)2 ?), вулзсгр(?. 7 + ? ?): не существует набора присваиваний переменным А, В или 0 такого, чтобы эти макрооператоры представляли собой одинаковые вычисления. Суть унификации заключается в определении правильного набора подстановок вместо знаков вопроса.
В то время как подстановка есть результат применения новых значений к параметрам макроса-образца, унификация есть результат одновременных подстановок в несколько макросов-образцов, имеющих целью показать, что все они эквивалентны прн некотором наборе одновременных подстановок. Общая унификация. Как отмечалось ранее, чтобы унифицировать два выражения () и Ч, нужно найти такие подстановки для переменных в этих выражениях, которые делают оба ныражения одинаковыми. Например, для унификации ВИС 3алп) и У(д(Запп).
7) свяжем Х с д(3оЬп), а 7 — с Оопп и в качестве унифицированного экземпляра обоих выражений получим У(д(Залп), 3озп). Если мы унифнцируем выражения 0 и У, то зачастую обозначаем сделанные подстановки буквой о (сигма) и записываем Во = Уо, Разница между подстановкой и унификацией демонстрируется на рис.
8.11. Когда мы применяем подстановку, у нас есть некоторое определение-шаблон (например, Г(А. В) ), которое может представлять собой сигнатуру подпрограммы или макроопределение, и экземпляр шаблона (например, Г(д(У) М(3))), который может представлять вызов подпрограммы или расширение макроса. Подстановка требует переименования параметров определении-шаблона в действительные зна- 8.4. Последовательность вычисления неарифметических выражений 375 чения этого экземпляра.
Однако в случае унификации обычно имеются два отдельных определения-шаблона г'например, Е(А. В) и М(С, О) ) и экземпляр шаблона (например, Е(Оопп МОп(у) . 7) )), Вопрос в этом случае ставится следующим образом; возможно ли присвоить какие-либо значения переменным А, В, С и О, так чтобы экземпляр шаблона стал подстановкой для обоих определений-шаблонову Е(А, В) = С(А, В) 06резец Е(А, В) = 0(А, В) М(С, О) = М(С, О) 06рвзец Пример Е(вр), "8)) Пример Е(оопп, М(п(у) 7)) Подстановка 9(О (ог А Падствнсвкв Зола (ог д ВВ) (ог В М(п(у), 7) (ог В е(А, в) = с(п(О, яб)) Е(А, В) = С(Зовя, М(В(у), тй П(у) (ог С 7 (ог 0 М(С, О) = М(В( ), 7) Унификация Е("о"", М(Н(у) 7)) 0(до)гп, М(П(у), 7О С 0 А В А В Рис.
8.11. Различие между подстановкой и унификацией Сначала применяем п Е(эонп, МШ(т). 7)) - Вшо)т„н(щт), 7)) Снвчвлвприменяемн ЕИонп. МЕР(ч) 7)) = Е(оолп. ХСп(у), 7)) После применения второй подстановки получим тот же результат: О(ЛР)пп, И(М(у) . 7) ). Говорят, что этот набор подстановок унифицирует экземпляр шаблона как с Е, так и с М. Применение унификации в языке Рго)ой. Предположим, что у нас есть запрос С такой, что и = Сп Сь где ц, и Сг — подзапросы. Сначала мы пытаемся унифицировать сг с помощью какого-либо правила Р из базы данных. Если запрос г)г унифицируется с помощью р: Р " Р~ Рг Р тогда мы можем создать новый запРос, нодставлЯЯ Ро вместо Сгп: Ра, О,а - Р,а.
Р,а.. Р„а. Яга = Р,.Р,,Ц.г(. Для применения определения шаблонов, возможно, мы должны сделать подстановки в обоих направлениях. Так, в приведенном примере если мы в определение Е подставим Зппп вместо А, в определение М подставим 7 вместо О, а также в определение Е подставим шаблон М(п(ч) . 7) вместо В и в определение М подставим н( у) вместо с, то наш экземпляр шаблона будет представлять правильную подстановку для обоих исходных определений-шаблонов Е и М. Из нашего исходного выражения ЕЯопп, М(Ы у), 7) ) можно получить два различных результата в зависимости от того, определение какого шаблона мы применяем первым — Е или М: 376 Глава 8. Управление последовательностью действий где апостроф (') обозначает исходный запрос, модифицированный преобразованиями о.
Теперь мы хотим разрешить этот новый запрос. Однако если запрос унифицируется фактом г, тогда мы можем заменить ~), на истину, и наш запрос теперь становится истинньгм, фо = фо = Л,. Тогда это является процессом выполнения для языка Рго!ой. Запросы унифицируются правилами или фактами из базы данных, пока в результате не получится истини. Конечно, если запрос ф унифицировался неподходящим правилом р или фактом г, то может получиться и ложь. В таком случае, если существует какая-либо альтернатива, ее надо проверять, пока не будет найдена верное решение. Набор преобразований а, необходимых для разрешения запроса, становится ответом на наш запрос. Основной принцип, применяемый здесь, называется принципом резолюции и более подробно будет описан в разделе 8А.5.
Приведем более полный пример на языке Рго!ой — набор операторов (называемых предложениями) для определения сложения: 1. васс(Х,Х) -у тз Х»1. 2. аааЛ,О,Х) :-У=Х. 3. асЫ(Е,Х,У) :-)1 ~з Х-1. асЫ(0,Ы,У). эвсс(_#_,0). Правило звсс (знссевэог — последующий элемент) вычисляет у =- Х + 1 путем унификации переменной У суммой Х + 1. Таким образом, значение, подставляемое вместо У, которое унифицирует У и Х» 1, есть значение выражения Х + 1. (Следует помнить, чта ~ з вычисляет значение выражения, в то время как = обозначает невы- численную строку.) Правила зао вычисляют сумму путем использования двух фактов о сложении: 0 + х = х (правило 2) (х + 1) + у = х + (у + 1) = х + зосс!у) (правило 3) Правило 3 сводит сложение к выполнению одинакового количества шагов— «вычитание 1 из первого члена» и «прибавление 1 ко второму члену» — до тех пор, пока первый член не станет равным 0 (нравило 2).
Например, для вычисления результата сложения 2 и 3, у должен бы гь унифицирован в запросе аа01У,2,3). Рго1ой выдает следующий результат: асшт.2.3) т = 5 где у = 5 —. преобразование о, которое унифицирует запрос с помощью правил базы данных, определяющих сложение. Реализация. Выполнение программы на языке Рго!ой иллюстрирует рис. 8.12, Оно представляет собой стандартный алгоритм обхода дерева.
Набор фактов в базе данных языка Рго1ой (рис. 8.12, и) представляет собой набор из М целей, по одной для каждого правила, связанного с определенным отношением в базе данных. В примере со сложением асс будет иметь две возможных цели: а001 с падцелью У = Х и а002 с подцелями )Х та Х - 1, а0010,й. у) и васс(Л,0) (рис.
8 12, б), Для каждой цели (например, правила аао2) Рга1ой последовательно пытается найти соответствие каждой подцели. Сначала И унифицируется с помощью Х - 1. Эта операция присваивает й значение выражения Х - 1. Затем Рго!ой пытается найти соответствие подцели асс! 0,й, У), рекурсивно вызывая правила ао0 (снача- 8.4. Последовательность вычисления неарифметических выражений 377 ла абб1, затем збб2 в поисках совпадения). Если совпадения найдены, то 0 становится суммой и'и У (тоесть (Х - 1) + У). Если найдено соответствие с этой подцелью, тогда ьнсс(7,0) унифицирует 7 с помощью 0 + 1 или 7 устанавливается равным ((Х вЂ” 1) + У + 1) = (Х + У).
Найдено соответствие с последней подцелью, и правило абб2 выполнено путем унификации 7 суммой Х + У. ЗцЬдоа(11 ЗиЬдоа)12 ЗцЬдоа(13 ... Зцьдоа)1Ы ЗцЬцоа(21 ЗцЬдоа(22 ЗиЬдоа( 23 ... Зцьдоа(2Ы Правило ЗоЬдоа(М1 ЗцЬдоа(М2 ЗиЬдоа)МЗ .. Зиьдоа(ММ Рно. 8.12. Выполнение программы на языке Рго(оц: а — база данных; б — унификация правила ееб2 Если соответствие с любой из подцелей не найдено, то применяется стандартный алгоритм отката.
Предыдущая подцель проверяется на альтернативное соответствие. Если ни одно нз соответствий не найдено, то проверяется еще одна предыдущая подцель и т. д. Если для всех подцелей соответствия не найдено, тогда правило не выполняется, и если есть какое-либо другое правило збф то выполняется оно.
Использование этого общего алгоритма обхода дерева позволяет вычислить абб(У. 2. 3) следующим образом(рис.8.13): 1. абб(У, 2, 3) пытается найти соответствие правилу 3. И, принимает значение 2-1=1, 2. Рго1оя пытается унифицировать абб(0л 1. 3), ьцсс(7г, 0г). 3, абб(0п 1. 3) устанавливает значение (Ь равным 0 и пытается унифициро- вать абб(0,, О, 3), ьцсс(7п 0к). 4. абб(0ы О, 3) выполняетсяпутемунификацни(Ьс3прииспользованиипер- вого правила абб. 5.
зцсс(7ы 0к) = кпсс(7г. 3) выполняется путем унификации 7гс 4. 378 Глава 8. Управление последовательностью действий 6. 1, (то есть 4) затем унифицируется с О, нз оттюшения асс(Ои1. 3). 7. ьосс(ЛнО1) унифицирует У, с О, + 1 - 4 + 1 = 5. 8. Наконец, У унифицируется с 71 = 5, и это значение выводится на печать. воз(У, 2, 3) Унификация в языке Ргфсд: — > Ствковыв операции поиска соотввтствив --.В' Операции унификации, возвращающие значение Рис. 8.13. Унификация в языке Рко)оц Из этого примера должно быть видно, что стеки играют важную роль в реализации языка Рго!ой.
Каждое предложение языка Рго!ой и каждая подцель сохраняются в стеке, пока не будет найдено соответствие цели. 8.4.4. Откат При описании выполнения операции э00 на языке Рго!о8 в предыдуцгем примере в процессе вычисления асс!У. 2, 3) было найдено соответствие со всеми подцелями. А что случится, если этого не произойдет? Что, если некоторая цель не сможет быть унифицирована с помощью правила из базы данных? В этом случае говорят, что правило не является логическим следствием программы.
Как показано на рис. 8.12, цели перечислены в некотором порядке 1... )). Но этот порядок произвольный, Рго!ой просто использует порядок, в котором факты записывались в базу данных. Пусть в некоторый момент времени мы пытаемся найти соответствие для некоторой подцепи.
Если соответствие найдено, то одна из возможных целей будет истинной, правда, мы не знаем, какая нз них. В этом случае мы просто перебираем все возможные цели. Если последняя из возможных целей также не привела к успеху, тогда говорят, что текущая подцель не выполнилась. Поскольку мы сохранили в стеке набор подцелей, среди которых производился поиск, мы возвращаемся к предыдущей подпели, соответствие с которой обнаружено, и пробуем найти соответствие с другой 8.4.
Последовательность вычисления неарифметических выражений 379 возможной для нее целью. Мы называем описанный процесс общим алгоритмом откити, который можно описать, используя рис. 8. 12, б. 1. Для подцели 5иЬосз1,,; установить 1 1 в качестве новой цели. 2. Последовательносопоставлятьцельдса1,для1 = 1...Миилидобитьсяуспеха, или нет в зависимости от того, выполнится ли какая-либо цель или все они не выполняются. 3. Если цель ооа1, выполняется, тогда выполняется и подпель 5иЬсса1,, Сохраняем ~ и ин1см соответствие для 5цЬВоз1~ „ч.
4. Если цель дса1, ложна для всех 1, значит, ложна и по11цель 5иЬсоа1, Возвращаемся к подцели 5аЬоса1..ч и пробуем для нее следующую цель 1 + 1 5. Если найдено соответствие с нодцслью 5иЬВоа1, в то возвращаем в качестве результата для родительской цели соа1~ истину. 6. Если не найдено соответствие с нодцелью 5иЬдса1,, ци для одного значения З, то возвращаем в качестве результата родительской цели Воа1, ложь. Приведенный алгоритм в поисках правильного результата проверяет все возможные совпадения путем последовательного сохранения и удаления из стека частичных результатов. Этот часто используемый, хотя и медленный алгоритм лежит в основе различных поисковых стратегий. Язык Рго!ой использует функцию ! (сШ вЂ” вырезать) в качестве указателя на то, что не следует выполнять процедуру отката.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
