П ОИСК В Ш ИРИНУ И Э ВРИСТИЧЕСКИЙ П ОИСК
Как было показано выше, поиск в глубину осуществляется пу-
тем обхода дерева вывода сверху вниз до завершения - успешного
или неудачного. Только после этого можно подняться вверх по де-
реву и, если поиск был неудачным, попытаться выбрать следующую
ветвь, а затем спуститься по ней вниз (отсюда и название поиска
" в глубину" ). В Прологе алгоритм поиска реализован по прин-
ципу " в глубину", поскольку новые цели добавляются в качало
212
списка ЦЕЛИ. А что бы произошло, если бы цели добавлялись в
конец списка? Тогда, вместо того чтобы продвигаться вниз по
уровням, мы сначала перебирали бы все альтернативные предло-
жения, т.е. обходили бы все узлы данного уровня и лишь потом
спускались уровнем ниже. Другими словами, мы не прорабатывали
бы одно решение на всю глубину, а параллельно пытались бы реа-
лизовать альтернативные решения. Конечно, это более длинный
путь, но и такой подход имеет свои преимущества. При поиске в
глубину можно успеть продвинуться достаточно глубоко перед
тем, как вы потерпите неудачу. При поиске в ширину исключается
возврат.
На заре создания ИИ поиск представлял собой одну из глав-
ных областей исследования. В то время были разработаны алго-
ритмы обхода дерева на основе эвристических правил, которые
зависели от конкретной прикладной области. Например, в шахмат-
ной игре для каждой позиции возможно множество вариантов
продолжения. Количество ветвей из заданного узла дерева вывода
огромно, и для нахождения решения (а это выигрышная позиция)
каждую ветвь нужно проработать на достаточную глубину, так как
число вероятных ходов велико. Поэтому поиск в глубину в данном
случае будет неэффективным. Применяя поиск в ширину, мы мо-
жем анализировать все возможные продолжения позиции на ход-
два вперед. Но и тогда вряд ли возможно просмотреть все вари-
анты в отведенное время. Требуется некоторый способ выбора
потенциально хорошего пути обхода дерева. Чтобы избежать заве-
домо неудачных ходов, можно применить, например, такое прави-
ло: " Предпочтение отдавайте ходам, ведущим к усилению вашей
позиции в центре доски". Подобные правила в большей степени
приходят с опытом, чем как результат изучения теории шахмат-
ной игры. Эти правила называются эвристическими. Они позволя-
ют управлять поиском, делая последний более эффективным. С по-
мощью так называемого алгоритма формирования весов ( uniform -
cost ) можно рассчитать вес каждой ветви и выбрать ветвь, имею-
щую в настоящий момент времени наименьший вес. Другой важ-
ный алгоритм поиска, так называемый А*алгоритм, осуществляет
поиск по оптимальному, эвристически выбираемому пути.
УНИФИКАЦИЯ
Основной недостаток реализации поиска в данном варианте
Пролога заключается в том, что термами могут быть только атомы.
Все они являются переменными Форта, главное назначение кото-
рых - хранить имена. Наш вариант Пролога может быть усилен
введением переменных особого рода: не обычных переменных
Форта, а логических. Тогда мы сможем записывать на Прологе ут-
верждения такого типа:
213
козел(Х): - млекопитающее(Х), имеет-рога(Х)
Здесь X - переменная, которая может заменять имя конкретного
козла. Пользуясь подобными переменными, можно средствами
Пролога получать атомы, являющиеся подстановками для этих
переменных (или конкретизированные переменные), что позволя-
ет посредством вывода отвечать на вопросы или восстанавливать
данные. К переменным, как вы помните, мы уже обращались при
определении слова соед. Чтобы убедиться в том, что с их помо-
щью можно отвечать на вопросы, рассмотрим утверждения:
козел(борька)
козел (грубиян)
Введя следующее выражение:
? - козел(X)
мы получим конкретизацию X. Вместо X могут быть подставлены
и " борька", и " грубиян". Пример с использованием правила
приведен ниже:
дед(Х, 2): - отец(Х,.У), отец(У, Z)
отец(карл, сэм)
отец(сэм, льюис)
Применяя эти предложения для выражения
? - дед(х, льюис)
путем конкретизации переменных в правиле мы получим:
" Х=карл". Подстановка переменных называется связыванием
( bindings ). Связывания могут быть представлены списком пар
(связок). Для приведенного выше примера возможны такие
связки:
((X карл)(У c3m)(Z льюис))
Первым элементом каждой пары является переменная, а вто-
рым - ее подстановка. Переменная задает область определения
для подстановки. Совокупность связок служит окружением, или
средой ( environment ).
Вы можете наблюдать за выполнением нашего примера интер-
претатором Пролога, отмечая среду на каждом шаге. Целевое
предложение верхнего уровня - дед(Х, льюис), следовательно, Z -
область определения для льюис. Две цели из правила помещаются
в список целей. Производя поиск на сопоставление с предикатом
oren(X, Y), интерпретатор находит второе предложение,
214
отец(карл, сэм), и осуществляет подстановку со следующим ре-
зультатом:
(( Y сэ м )(Х карлНг льюис))
Вторая цель, также с предикатом " отец', сопоставляется с тем же
самым предложением и осуществляется попытка выполнить
следующие подстановки:
((УкарлКгсэм))
Обе эти подстановки противоречат предыдущим. В данной ситуа-
ции сопоставление заканчивается неудачей, и поиск подходящего
предложеиих продолжается. В следующем предложении имеются
связки для Y и Z, которые полностью согласуются с предыдущими
подстановками. Иными словами, мы приходим к согласованию це-
ли верхнего уровня с базой знаний. Теперь подстановки можно
вывести.
В приведенном выше примере аргументами предикатов явля-
ются атомы. В более общем случае они могут быть также преди-
катами или переменными. Нияке приводится пример более слож-
ного сопоставления. Два предиадта:
f(XY), т(сэм, g(X))
имеют связки:
((Хсэм) (Yg(X)))
Эти предикаты могут быть выражены в виде списка:
(fXY) (теэм (дХ))
Процесс, который мы кратко рассмотрели, называется сопо-
ставлением с образцом ( pattern matching ). Здесь осуществляется
попытка унификации двух логических выражений путем подстано-
вок согласующихся переменных. Наиболее универсальный алго-
ритм унификации представлен на рис. 9.6.
Покажем на примере сопоставления нескольких выражений,
как выполняется алгоритм унификации - УНИФИКАЦИЯ
(UNIFY). Допустим, у нас имеются два предиката:
(аХХ), (а Yb)
Их первые элементы сопоставимы. Оба вторых элемента представ-
ляют собой переменные со связкой (X Y). Из сопоставления тре-
тьих элементов вытекает, что X - область определения для Ь, что
выражается связкой:
((XY)(Xb))
215
В контексте данного окружения Y должно бы быть областью опре-
деления для Ь, поскольку X служит такой областью для Y, но это
не так. Кроме того, X является областью определения более чем
для одной переменной. А чтобы получить окружение вида
(XYHYb))
67
| 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
\ АЛГОРИТМ УНИФИКАЦИИ
( С СП1 -> СП2> \ 2АСС0Ц-СПИС0К СОДЕРЖИТ^
\ ПАРЫ ПЕРСПИС-ЗНАЧЕНИЕ
: 2АСС0Ц DUP НОЛЬ
IFNIP
ELSE 2DUP ПЕРВЫЙ т
IF NIP
ELSE ХВОСТ ХВОСТ РЕКУРСИЯ
THEN
THEN
| О
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
68
S АЛГОРИТМ УНИФИКАЦИИ
( С1 @О -> СП2)
: ЗНАЧЕНИЕ OVER ПЕР?
IF 2DUP 2АСС0Ц DUP НОЛЬ
IF2DR0P
ELSE ROT DROP ХВОСТ ПЕРВЫЙ SWAP РЕКУРСИЯ
THEN
ELSE DROP
THEN
Рис. S.6. Алгоритм унификации Пролога. Предполагается, что
переменные могут входить в предикат только один раз
Экраны 67, 68. Алгоритм унификации: определение 2АССОЦ и
ЗНАЧЕНИЕ
216
217
вместо переменной в сопоставлении должна участвовать ее напар-
ница по связке. Тогда переменная X окажется связанной с Y, и
при сравнении третьих элементов сопоставляться с Ь будет напар-
ница X по связке, в результате чего получится (Y Ь).
Получение напарницы для переменной осуществляется алго-
ритмом ЗНАЧЕНИЕ (VALUE), приведенным на рис. 9.7. Слово
ЗНАЧЕНИЕ получает аргументы X и О, где X - переменная, а ее
Рис. 9.7. Применение ЗНАЧЕНИЯ словом УНИФИКАЦИЯ для получе-
ния связки логической переменной X в окружении О
218
напарница по связке восстанавливается из списка окружения О.
ЗНАЧЕНИЕ оставляет нетронутыми аргументы, не являющиеся
переменными. В противном случае с помощью АССОЦ отыскива-
ется X в О. Если поиск неудачен, аргумент X возвращается,
поскольку для него нет связки. Если X найден, выполняется
рекурсия по хвосту связки, который может быть следующей
переменной.
Слово ЗНАЧЕНИЕ просматривает цепочку подстановок пере-
менной до последней. Например, при заданном О вида
(( X W )( WU )( U V )( V Y ))
ЗНАЧЕНИЕ возвратит Y как связку для X. Поскольку для данной
переменной возвращается ее ближайшая связка, то при подста-
новках достаточно задавать имя только одной переменной. Кроме
того, выдерживается условие, согласно которому для переменной,
служащей идентификатором области определения по отношению к
другой переменной, ЗНАЧЕНИЕ доставляет атом. Так, в окруже-
нии
(( XY )( Za )( YZ ))
связкой для X будет а. Хотя и известно, что слову ЗНАЧЕНИЕ
первоначально из УНИФИКАЦИИ передается переменная X, тем
не менее необходимо предварительно проверить, является ли
новый аргумент X переменной, так как ЗНАЧЕНИЕ рекурсивно
вызывает само себя. Связки для исходного аргумента X может не
существовать.
Вернемся к алгоритму УНИФИКАЦИЯ. Первый предприни-
маемый шаг - замещение X и Y их связками. Затем, если X ока-
зывается переменной, она сцепляется с Y и такая пара добавляется
к окружению О, которое и возвращается в виде результата. Если
же переменной будет Y, то X и Y меняются местами, поскольку
первым элементом пары в связке должна быть переменная. Далее
пара помещается в О. Несмотря на то что в реализации списков,
описанной в гл.7, не используется механизм ячеек связи, при
следующем обращении к лиспоподобному слову СПИСОК (X Y)
создается ячейка связи (или точечная пара) с головой X и хвостом
Y, а это уже А-список Лиспа (см. гл.7). В нашем примере О реа-
лизовано в виде линейного списка.
В том случае, когда ни X, ни Y не являются переменными,
осуществляется их проверка на атомы. Если один из них ока-
зывается атомом, то другой должен быть сопоставимым атомом.
Иначе не получится новой связки, поскольку нет переменной.
Если же выясняется, что X и Y - не атомы и не переменные, зна-
чит, они должны быть списками, используемыми для представле-
ния предикатов. В такой ситуации УНИФИКАЦИЯ вызывается ре-
курсивно по первым двум элементам списков X и Y.
219
69
0 \ АЛГОРИТМ УНИФИКАЦИИ
1 ( С1 С2 О -> F) \ F * ИСТИНА, ЕСЛИ С1 и С2 УНИФИЦИРУЕМЫ;
2 \ О СОДЕРЖИТ СВЯЗКИ
3: УНИФИКАЦИЯ DUP > R @ ROT OVER ЗНАЧЕНИЕ -ROT
4 ЗНАЧЕНИЕ OVER ПЕР?
5 «F НУЛЬ -ROT R> СПИСОК TRUE
. 6 ELSE DUP ПЕР?
7 IF SWAP НУЛЬ -ROT R> СПИСОК TRUE
8 ELSE 2DUP ATOM? SWAP ATOM? OR MOT
9 IF 2DUP ПЕРВЫЙ SWAP ПЕРВЫЙ SWAP R# РЕКУРСИЯ
10 I F ХВОСТ SWAP X30CT SWAP R> РЕКУРСИЯ
11 ELSE 20Я0Р R> DROP FALSE THEN
12 ELSE R> DROP •
13 THEN
14 THEN
15 THEN;
Экран 69, Алгоритм унификации: определение слова УНИФИКАЦИЯ
Если при таком вызове УНИФИКАЦИИ добавляются новые
связки, то в результате получается обновленное окружение О'.
Далее уже в новом окружении УНИФИКАЦИЯ вызывается по ос-
тавшейся части списков X и Y. Это пример двойной рекурсии
(применявшейся нами ранее при определении слова РАВНО).
После второго вызова создается окончательное окружение. Слово
УНИФИКАЦИЯ, описанное на экране 69, при удачном сопостав-
лении возвращает истинное значение флага. По завершении двух
рекурсивных вызовов флаги логически умножаются (AND), поско-
льку результирующее сопоставление заканчивается успешно толь-
ко при условии, что оба вызова оказались удачными, Если нет ни
одного ложного флага, можно считать, что сопоставление состоя-
лось. Теперь попытаемся применить алгоритм УНИФИКАЦИЯ на
практике. Рассмотрим пример:
(аХЬ)
(a(cY)Y)
Здесь аргумент X будет связан с (с Y), a Y с Ь. Переменная Y в
c(Y) неявно служит и областью определения для Ь, поскольку это
указано непосредственно. Такие связки допустимы. Приведем дру-
гой пример:
(а XXX)
(aYYY)
220.
Здесь X - область определения Y при сопоставлении вторых
элементов каждого списка. Что касается третьих элементов, то
связка X или Y представляет собой область определения Y. На-
конец, при последнем сопоставлении слово ЗНАЧЕНИЕ ищет связ-
ку для X. Такой связкой будет Y. Затем ЗНАЧЕНИЕ отыскивает
связку для Y, а это Y. ЗНАЧЕНИЕ снова ищет связку для Y. По-
лучается бесконечный циклический процесс - зацикливание. Во
избежание зацикливания нужно не допускать, чтобы переменные
связывались сами с собой. Если переменная входит в некоторый
предикат более одного раза, то УНИФИКАЦИЯ не может выпол-
нить процесс унификаций правильно. В следующем примере:
(X)
((аХ))
УНИФИКАЦИЯ также не выдаст совместимую связку. X - область
определения (а X), но подстановка вместо X даст (а (а X)). При
повторе получим:
(а(а( аХ )))
Зацикливание в данном случае произошло потому, что имеется
вхождение X в функцию, для которой он сам служит областью
определения. В алгоритме УНИФИКАЦИЯ отсутствует контроль
вхождений, поскольку не отслеживается ситуация, когда X входит
в (а X).
Алгоритм УНИФИКАЦИЯ - типичный представитель алгорит-
мов унификации, применяющихся при реализации Пролога.
Быстрота его выполнения достигается ценой следующих огра-
ничений:
1. Переменная должна входить в некоторую функцию не
более одного раза.
2. Переменная не должна входить в функцию, по отношению
к которой сама является границей. Как правило, эти ограничения
не столь существенны, но позволяют достигать большой скорости
вычислений.
Существует еще одно осложнение, с которым необходимо счи-
таться при включении алгоритма УНИФИКАЦИЯ в ПОИСК: на
различных уровнях дерева вывода для одних и тех же имен пе-
ременных связки будут различными. Вы видели это в примере с
предикатом дед(Х, У). Отслеживать различные связки одной и той
же переменной можно двумя способами - копированием структур
и совместным использованием структур. Первый способ состоит
в копировании граничных выражений на каждом уровне вывода,
второй - в том, что каждая переменная в связке снабжается
индексом, отражающим уровень. При таком подходе связки имеют
ВИД ((X i) а), где i - индекс X, отражающий номер использования
л. В литературе по логическому программированию приводится
221
множество методов, повышающих эффективность реализаций
Пролога. Один из них (параллельные вычисления) излагается
в гл. 10.
УПРАЖНЕНИЯ
I. Измените порядок предложений в списке ПРЕДЛОЖЕНИЯ (экран 71) так,
чтобы предотвратить;
8) возврат для цели КОЗЕЛ;
б ) возврат вообще.
73
0 \ ВЫВОД РАСШИРЕННОГО ПЕРСП
1 ( @ -> ФЛАГ) \ ФЛАГ=ИСТИНЕ, ЕСЛИ @ ЯВЛЯЕТСЯ
2 \ PFA ПЕРЕМЕННОЙ
3: ATOM? BODY> @ ['] НУЛЬ < Э =;
4
5 ( @СПИСОК -> )
6: ВЫДАТЬСПСГ? ." ("
7 BEGIN DUP ПЕРВЫЙ DUP АТОМ?
8 1РОиРНОЛЬ
9 IF DROP ELSE BODY> > NAME. iD THEN
10 ELSE DUP ПЕР?
11 IF 2- BODY> > NAME. ID ELSE РЕКУРСИЯ THEN
12 THEN ХВОСТ DUP НОЛЬ
13 UNTIL 8 ( ЗАБОЙ) EMIT." ) " DROP
14;
15
74
| 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
\ ВЫВОД РАСШИРЕННОГО ПЕРСП
( ©СПИСОК -> )
: ВЫДАТЬ DUP @ НОЛЬ %
IF DROP CR." НУЛЬ"
ELSE DUP ATOM?
IFBODY> > NAME.ID
ELSE DUP ПЕР?
IF 2- BODY> > NAMECR." ПЕРСП " .ID
ELSE ВЫДАТЬСП
THEN
THEN
THEN
Экраны 73, 74. Вывод на начать расширенного слова ПЕРСП
2, Разработать мирксм сохранения недоказанных целей в списке
НЕУДАЧИ с тем, чтобы и просматривать этот список перед поиском цели в списке
ЦЕЛИ. Вели искомая цель будет обнаружена в сииске НЕУДАЧИ, то должен быть
прекращен немец и активирован возврат.
66
0 N АЛГОРИТМ УНИФИКАЦИИ
1
2
3 у
| \ ПЕРСП ОПРЕДЕЛЯЕТ ЛОГИЧЕСКИЕ ПЕРЕМЕННЫЕ
( -> P F A +2 )
; ПЕРСП CREATE HERE 2+, О, DOEa >
|
4
5
6
7 2+;
8
9
10 ПЕРСП FOO ' FOO @ FORGET FOO
11
12
13 ( С -> F) \ F ИСТИНА, ЕСЛИ ПЕРСП
14 ЛЕР? DUP @ 0** SWAP 4 - g> | DUP 1 LITERAL =
15 DROP
Экран 66. Алгоритм унификации: определение ПЕРСП и ПЕР?
3. Перепишите слово ДОБАВИТЬ-ЦЕЛИ таким образом, чтобы новые цели
п рнсоединялись к концу списка ЦЕЛИ, а не к его иачаяу. (Вам может понадо-
бится новый список для переупорлдочения целей.)
4. Используя модифированный вариант ДОБАВИТЬ-ШЛИ из упр.З, напи-
шите слово ШП0ИСК для выполнения поиска в ширину, Сравните его эффектив-
ность с зффективностью слова ПОИСК, приведенного из экране 71.
5. Только для модели APРLE II: объясните слова, применяемые при создании
логических переменных ш экране 66. Число, предшествующее С в (ПЕРСП), - код
222
223
машинной команды перехода. Почему логическими переменными не могут служить ]
переменные Форта?
6. Объясните слово 2АССО1Д на экране 67 и структуры данных, с которыми
оно выполняется. Объясните порядок использования этого слова в определении
слова ЗНАЧЕНИЕ на экране 68?
7. Модифицируйте слово УНИФИКАЦИЯ таким образом, чтобы имелась воз-
можность применения в одном предикате нескольких вхождений одной и той же
переменной.
8. Осуществите контроль вхождений. Создайте слово Форта, которое
выбирало бы два выражения в качестве аргументов, X и Y, и проверяло бы, не
входит ли X в Y.
Глава 10
ДОПОЛНИТЕЛЬНЫЕ ВОЗМОЖНОСТИ
9. Присоедините контроль вхождений из упр.8 к слову УНИФИКАЦИЯ из'
упр.7.
10. Модифицируйте алгоритм УНИФИКАЦИЯ из упр.7 так, чтобы его можно
было встроить в слово НАЙТИ-УТВЕРЖДЕНИЕ.
Обработка списков, поиск и сопоставление по образцу являют-
ся, важными понятиями для систем, основанных на знаниях, но это
лишь базовые методы, применяющиеся в данной области. В насто-
ящей главе мы кратко рассмотрим и другие идеи, возникавшие в
процессе исследований по ИИ. Более подробно они описаны в ли-
тературе, ссылки на которую приведены ь приложениях.
ВСТРОЕННЫЕ ПРЕДИКАТЫ ПРОЛОГА
В гл.9 обсуждалась простая реализация Пролога в виде алго-
ритма поиска в глубину. Алгоритм содержал единственную проце-
дуру. Программы представляли собой набор целевых предложений
в базе знаний. Программирование на Прологе было скорее описа-
тельным, чем прсдписательиым. Вместо того чтобы предписывать
выполнение тех или иных действий над данными, мы описывали
сами данные. Поскольку Пролог реализует некоторый вариант ло-
гики предикатов, а ПОИСК используется для доказательства тео-
рем, то одной только этой процедуры достаточно для решения за-
дач из области искусственного интеллекта. Этот язык может при-
меняться при построении экспертных систем, где список предложе-
ний представляет собой экспертные знания.
Пролег тем не менее обладает такими дополнительными сред-
ствами, как встроенные предикаты. Один из них, отсечение (сим-
вол! ), может быть вставлен в тело некоторого правила между це-
лями, чтобы форсировать возврат. Например, для правила:
С: - А, !, В
225
если вывод В заканчивается неудачей, то и С форсированно закан-
чивается неудачей. Отсечение вынуждает слово ПОИСК удалить
альтернативные ветви С на уровне ИЛИ и вернуться на предыду-
щий уровень И, Предикат отсечения не является описательным,
так как он влияет на функционирование слова П ОИСК. Приведем
еще несколько предписательных предикатов Пролога:
* включить(Х) (assert(X)) - включение утверждения X в виде
предложения в список ПРЕДЛОЖЕНИЯ и успешное завершение;
* удалить(Х) (retract(X)) - удаление X из списка ПРЕДЛО-
ЖЕНИЯ и успешное завершение. Если X не совпал ни с одним ут-
верждением в списке ПРЕДЛОЖЕНИЯ, - это означает н е удачу
.* вызвать(X) (call(X)}-вызов X в качестве цели и успеш-
ное завершение поиска, если цель доказывается. В Прологе имеют-
ся и другие встроенные предикаты, которые здесь не рассматрива-
ются.
ПРОЦЕДУРНОЕ ДОПОЛНЕНИЕ
И ВЫЗОВ ПО ОБРАЗЦУ
Некоторые интерпретаторы правил используют правила, кото-
рые представляют собой пары условие-действие. Ес ли условия удо-
влетворяются, то происходит не занесение заключения в базу зна-
ний, а выполнение данного заключения как процедуры Такая схе-
ма более удобна, чем чисто описательная, поскольку одна и про-
цедур может использоваться для занесения заключения. Этот спо-
соб известен под названием процедурное дополнение. Он сочетает к
себе элементы предписательных методов, например арифметичес-
ких вычислений, и описательных.
Вместо (почти) чисто описательною программирования в
Прологе можно создавать интерпретаторы правил-предписаний.
Развивая идею процедурного дополнения, мы можем выражать
правила в форме образца, сцепленного с процедурой, выполняемой
в том случае, если выполнено сопоставление с конкретным образ-
цом. Эта процедура аналогична слову Форта с той лишь разницей,
что слово Форта вызывается по имени, а процедура • в результате
сопоставления с образцом. Алгоритм сопоставления с образца
соответствует алгоритму УНИФИКАЦИЯ Пролога, в то время как
выполняемые процедуры являются частью функции ПОИСК. Об-
разцами могут работать процедуры: Д ОБАВИТЬ(А ОО ), УДАЛИТЬ
(REMOVE) или ВОССТАНОВИТЬ (RETRIEVE), которые добавля-
ют к базе данных, содержащей доказанные факты, новые факты
удаляют факты из нее или восстанав л ивю т их так же, как и
функция? - в Прологе. В системах, основанных на знаниях подоб-
ного рода, имеется база данных для хранения доказанных фактов.
В Прологе функция " включить(Х)" добавляет X к списку ПРЕД-
ЛОЖЕНИЯ.
Чтобы продемонстрировать использование правил в виде про-
цедур, приведем пример правила с обратным рассуждением:
| оте ц (Х, ¥ < )
OTe u ( Y. Z )
|
дед(Х.г)
ВОССТАНОВИТЬ
ВОССТАНОВИТЬ
КОНЕЦ
где отец(Х, 2) - образец, а слово КОН Е Ц означает завершение
процедуры. Правило прямого вывода п рограмм иру ем на следую-
щем примере: '
Oтец(X, Y), Oтeц(Y, Z)
ДОБАВИТЬ дед(ХД)
КОНЕЦ
Алгоритм сопоставления с образцом связывает переменные из
процедуры с переменными образца. В случае правила обратного
вывода X в первой команде ВОССТАНОВИТЬ служит областью
определения для X образца. При втором вызове команды ВОССТА-
НОВИТЬ это связывание остается. Такие связывания являются -
локальными по отношению к выполняемой процедуре поиска об-
разца.
