Реферат: Программирование на языке CLIPS
· между высказываниями в разных «мирах».
Для анализа вариантов возникновения противоречий целесообразно разработать четыре правила. Разобьем первую из указанных ситуаций на два случая:
· обнаруживается противоречие между предположением и высказыванием, которые существуют в одном и том же контексте (например, если из предположения Т(А) непосредственно следует заключение F(A), как в заявлении персонажа А: F(A));
· обнаруживается противоречие между предположением и одним из дизъюнктов составного высказывания, как в заявлении персонажа А: T(B) v F(A).
Ситуацию, когда противоречие существует между высказываниями в разных “мирах”, тоже можно разделить на два случая:
· текущий “мир” рассматривается в предположении, что персонаж говорит правду (в поле scope объекта world содержится значение truth);
· текущий «мир» рассматривается в предположении, что персонаж лжет (в поле scope объекта world содержится значение falsity).
Если, предположив правдивость персонажа, программа обнаружит противоречие, она должна проанализировать и следствие из противоположного предположения – что персонаж лжец. И только при условии, что оба варианта предположения приводят к противоречию, нужно выполнить откат.
Анализ каждого из четырех вариантов ситуации выполняется отдельным правилом, программы которых представлены ниже. Обратите внимание, что все правила имеют довольно высокий приоритет (значение параметра salience). Это обеспечивает их первоочередную активизацию механизмом разрешения конфликтов между правилами. Кроме того, правила, анализирующие противоречие в пределах одного и того же «мира», имеют более высокий приоритет, чем правила, анализирующие противоречие между разными «мирами». Тем самым обеспечивается реализация стратегии по возможности избегать откатов в процессе решения проблемы.
;; ЕСЛИ обнаруживается противоречие между предположением
;; и производными от него фактами в пределах одного и
;; того же “мира” и в одном и том же контексте,
;; ТО зафиксировать противоречие и удалить
;; противоречивые утверждения (объекты claim)
;; из базы фактов.
(defrule contradiction
(declare (salience 100))
?W <- (world (tag ?N) (task check) (context ?S)
(prior 0))
?P <- (claim (content ?F ?X) (reason ?N)
(context ?S))
?Q <- (claim (content ?G&: (not (eq ?G ?F)) ?X)
(reason ?N (context ?S))
=>
(printout
t crlf
“CONTRADICTION: “ ?F ?X “ versus “
?G ?X “in world “ ?N
;; “ПРОТИВОРЕЧИЕ между: “ ?F ?X “ и “?G ?X “в мире” ?N
t crlf)
(retract ?P)
(retract ?Q)
(modify ?W (task contra))
)
;; ЕСЛИ обнаруживается противоречие между предположением
;; и производными от него фактами в пределах одного и
;; того же “мира”, но в разных контекстах,
;; ТО зафиксировать противоречие.
(defrule transcontext
(declare (salience 90))
?W <- (world (tag ?N) (task check) (context ?T)
(prior 0))
(claim (content ?F ?X) (reason ?N)
(context ?S&: (< ?S ?T)))
(claim (content ?G&: (not eq ?G ?F)) ?x)
(reason ?N) (context ?T))
=>
(printout t crlf
“TRANSCONTEXT CONTRADICTION: “ ?F ?X ” versus “
?G ?X “ in world “ ?N
;; “ТРАНСКОНТЕКСТНОЕ ПРОТИВОРЕЧИЕ между: “ ?F ?X
;; “ и “ ?G ?X “ в мире “ ?N
t crlf)
(modify ?W (task contra))
)
;; ЕСЛИ обнаруживается противоречие между
;; текущим “миром” в предположении о правдивости
;; и ранее покинутым “миром”,
;; ТО зафиксировать противоречие.
(defrule transworld-truth
(declare (salience 80))
?W <- (world (tag ?N) (scope truth) (task check)
(prior 0))
(claim (content ?F ?X) (reason ?N))
(claim (content ?G&: (not (eq ?G ?F)) ?X)
(reason ?M&: (< ?M ?N)))
=>
(printout
t crlf
“TRANSWORLD CONTRADICTION: “ ?F ?X “ versus “
?G ?X “ in worlds “ ?N “I” ?M
;; “МЕЖМИРОВОЕ ПРОТИВОРЕЧИЕ: “ ?F ?X “ противоречит “
;; ?G ?X “ в мирах “ ?N “I” ?M
t crlf)
(modify ?w (task contra))
)
;; ЕСЛИ обнаружится противоречие между
;; текущим “ миром” в предположении о лживости
;; и ранее покинутым “миром”,
;; ТО подготовиться к выполнению отката в ранее
;; покинутый “мир”.
(defrule transworld-falsity
(declare (salience 80))
?W <- (world (tag ?N) (scope falsity) (task check))
(claim (content ?F ?X) (reason ?N))
(claim (content ?G&: (not (eq ?G ?F)) ?X)
(reason ?M&: (< ?M ?N)))
=>
(printout
t crlf
“TRANSWORLD CONTRADICTION: “ ?F ?X “ versus “
?G ?X “ in worlds “ ?N “I” ?M
;; МЕЖМИРОВОЕ ПРОТИВОРЕЧИЕ: “ ?F ?X “ противоречит “
;; ?G ?X “ в мирах “ ?N “I” ?M
t crlf)
(modify ?W (task contra) (prior ?M))
)
Обращаю ваше внимание на то, что вместе с фиксацией самого факта противоречия в последнем правиле фиксируется и идентификатор ранее покинутого «мира», с которым конфликтует текущий. Эта информация потребует для выполнения отката с помощью правил, которые будут представлены в следующем разделе.
Подготовка рабочей памяти к выполнению отката
При подготовке к откату нужно выполнить одну из двух возможных операций с рабочей памятью:
· если к противоречию привел выбор определенного дизъюнкта, нужно удалить контекст, созданный в результате этого выбора;
· если к противоречию привело предположение о правдивости персонажа, нужно удалить соответствующий контекст и проанализировать, к чему приведет противоположное предположение.
В любом случае из рабочей памяти нужно удалить объекты claim. Поскольку откат никогда не выполняется в противоречивом контексте, такое удаление не повлияет на полноту представления информации о задаче. Если потребуется вновь сформировать удаленный контекст при других предположениях, это можно будет выполнить, повторив вычисления с «чистого листа».
;; ЕСЛИ обнаружено противоречие с одним из
;; дизъюнктивных контекстов «мира»,
;; ТО удалить все утверждения (объекты claim)
;; этого контекста.
;; ПРИМЕЧАНИЕ: правило будет активизироваться повторно,
;; пока не будут удалены все ненужный объекты.
(defrule clean-context
(declare (salience 50))
(world (tag ?N) (task contra) (prior 0)
(context ?S&~0))
?F <- (claim (reason ?N) (context ?S))
=>
(retract ?F) )
)
;; ЕСЛИ противоречие обнаружено в текущем “мире” в
;; предположении о правдивости,
;; ТО повторить анализ, предположив лживость персонажа.
(defrule switch-context
(declare (salience 40))
;; Если больше нет правых дизъюнктов,
?W <- (world (tag ?N) (scope truth) (task contra)
(prior 0) (context ?S&~1))
=>
;; изменить предположение и сформировать новый контекст.
(modify ?W (scope falsity) (task check) (context 0))
)
;; Удалить все утверждения (объекты claim),
;; сформированные на основании предположения о
;; правдивости.
;; ПРИМЕЧАНИЕ: правило будет активизироваться повторно,
;; пока не будут удалены все ненужные объекты.
(defrule sweep-truth
(declare (salience 100))
(world (tag ?N) (scope falsity))
?F <- (claim (reason ?N) (scope truth))
=>
(retract ?F)
)
Последнее правило демонстрирует, как с помощью полей reason и scope можно отслеживать объекты claim. В данной программе используется тот же прием, что и в системах обработки правдоподобия, которые были рассмотрены в главе 19.
Теперь можно приступить к разработке правил, выполняющих откат.
Выполнение отката
Каждое отдельное высказывание в задачах рассматриваемого класса формирует свой «мир». Поскольку высказывания обрабатываются последовательно, возможна ситуация, когда «мир», который программа анализирует в текущий момент, вступает в конфликт с одним из «миров», обработанных ранее. Дальнейшие действия в такой ситуации зависят от того, на каких предположениях основаны конфликтующие «миры».
Если текущий «мир» был проанализирован только в предположении о правдивости соответствующего персонажа, то, очевидно, нужно повторить его анализ, но уже в предположении, что персонаж – лжец. Если и в этом случае конфликтная ситуация сохраняется, следовательно, мы исчерпали все возможности ее локального разрешения, поэтому нужно подумать о возврату к анализу ранее покинутого «мира» и повторить его анализ, но уже на основе других предположений.
Но возврат имеет смысл выполнять только в том случае, если в ранее покинутом «мире» не были проанализированы все возможные сочетания предположений и контекстов. Таким образом, одно из условий, при которых целесообразно выполнять откат, состоит в том, что покинутый «мир» был проанализирован только в предположении правдивости соответствующего персонажа и что есть еще возможность проанализировать следствия из противоположного предположения.
Правило undirected-falsity выполняет необходимые для этого подготовительные операции. Смысл слова undirected (ненаправленный) состоит в том, что это правило реализует откат в «хронологическом» порядке создания «миров». В механизме разрешения конфликтов в CLIPS реализовано «хронологическое предпочтение», которое обеспечивает откат к последнему из ранее сформированных «миров», удовлетворяющих заданным условиям. Но при этом не предпринимается никакой попытки локализовать в процессе выбор точки, которая стала причиной конфликта, например выбрать именно тот «мир», с которым конфликтует текущий.
;; Хронологический откат к тому “миру”, который был
;; покинут без выполнения анализа в предположении
;; о лживости (поле scope содержит значение truth,
;; а поле task – значение check).
(defrule undirected-falsity
(world (tag ?N) (scope falsity) (task contra))
?W <- (world (tag ?M&: (< ?M ?N))
(scope truth) (task check))
=>
(modify ?W (task back))
)
Альтернативный сценарий используется в ситуации, когда в ранее покинутом «мире» не были проанализированы все дизъюнкты составного утверждения. «Мир» был покинут, когда обнаружилось, что проанализированный дизъюнкт не противоречит предположению, поэтому прочие дизъюнкты просто не рассматривались. Теперь, когда обнаружилось противоречие с другим «миром», можно вновь вернуться к ранее незавершенному анализу и попробовать, не разрешится ли конфликт в результате исследования другого дизъюнкта.
Приведенное ниже правило undirected-disjunct выполняет подготовку к такому откату в хронологическом порядке.
;; Хронологический откат к тому «миру», который был
;; покинут без завершения анализа дизъюнктов.
(defrule undirected-disjunct
(world (tag ?N) (scope falsity) (task contra))
V <- (world (tag ?M&: (< ?M ?N)) (task check)
(context 1))
claim (content OR ?P ?X ?Q ?Y) (reason ?M)
(scope ?S))
=>
;; Дизъюнкт в ранее покинутом “мире”, анализ которого
;; не был выполнен.
assert (claim (content ?Q ?Y) (reason ?M) (scope ?S)
(context 2)))
;; Зафиксировать необходимость отката в этот “мир”.
Modify ?V (task back))
)
Хронологический откат является не единственной операцией такого рода. Ниже представлены «направленные» (directed) версии соответствующих правил, в которых используется информация о том, в каком именно «мире» имеется утверждение, ставшее причиной конфликта с текущим «миром». Эта информация содержится в слоте prior текущего объекта world.
;; Если обнаружено противоречие между
;; объектами world M и N
;; и объект M создан ранее объекта N,
;; причем анализ M в предположении о лживости
;; соответствующего высказывания не был выполнен,
;; ТО вернуться к анализу объекта M.
(defrule directed-falsity
(world (tag ?N) (scope falsity) (task contra)
(prior ?M&”0))
?W <- (world (tag ?M) (scope truth) (task check))
=>
modify ?W (task back))
)
;; Если обнаружено противоречие между
;; объектами M и N
;; и объект М создан ранее объекта N, причем
;; не был выполнен анализ всех дизъюнктов в M,
;; ТО вернуться к анализу объекта M.
(defrule directed-disjunct
(world (tag ?N) (scope falsity) (task contra)
(prior ?M&~0))
?V <- (world (tag ?M) (task check) (context 1))
(claim (content OR ?P ?X ?Q ?Y) (reason ?M)
(scope ?S))
=>
;; Дизъюнкт в ранее покинутом “мире”, анализ которого
;; не был выполнен.
(assert (claim (content ?Q ?Y) (reason ?M)
(scope ?S) (context 2)))
;; Зафиксировать необходимость отката в этот “мир”.
(modify ?V (task back))
)
Если вы думаете, что эти два правила позволяют справиться со всеми возможными ситуациями, в которых может возникнуть необходимость выполнить откат, то вы ошибаетесь. «Миры» W и V могут конфликтовать, хотя в обоих проанализированы все варианты предположений и все дизъюнкты. А источник конфликта при этом находится в некотором третьем «мире», в котором не был завершен анализ предположений или дизъюнктов. (см. пример 4).
Упражнение 4
Проанализируйте следующую головоломку, в которой участвуют персонажи А, В и С.
А: «В лжец».
В: «С лжец».
С: «В всегда говорит правду».
Как выполнить откат в процессе решения этой задачи. Отыщите «мир», в который нужно выполнить откат, и объясните, почему этот «мир» не удастся определить с помощью приведенных выше правил.
Фактически второе т третье высказывания в этой задаче несовместимы, а потому в ней не существует варианта непротиворечивого распределения ролей между персонажами.
Правила directed- и undirected- можно использовать в комбинации, но с первого взгляда трудно решить, как именно это сделать. Условные части правил undirected-falsity и directed-falsity одинаковы, а потому нам остается только манипулировать значением параметра salience. Обычно «направленные» варианты правил более эффективны, но в результате их применения может пострадать полнота исследования «миров» в особо хитроумных задачах. «Ненаправленные» варианты работают медленнее, но зато обеспечивают исчерпывающий просмотр всех имеющихся в задаче объектов world. Я предлагаю читателям самостоятельно поэкспериментировать с обоими вариантами при решении разных задач рассматриваемого класса. Мы же в дальнейшем будем использовать только «ненаправленные» варианты этих правил.
Восстановление контекста
При восстановлении контекста придется удалить из рабочей памяти все объекты world, созданные после того объекта, к анализу которого программа возвращается. Удаляются и все утверждения, сформированные на основании высказываний, связанных с удаляемыми объектами. Сами же высказывания (объекты statement) должны быть сохранены и при этом помечены признаком, указывающим, что их нужно в дальнейшем анализировать повторно.
;; Удаление объектов world.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8
