Реферат: Программирование на языке CLIPS
· когда обнаружится конфликт между текущим «миром» и ранее существовавшим, причем в ранее существовавшем «мире» предполагается истинность высказывания, но не была проанализирована его лживость;
· когда обнаружится конфликт между текущим «миром» и ранее существовавшим, причем в ранее существовавшем «мире» был проанализирован только один операнд в составном дизъюнктивном утверждении.
Чтобы смысл этих формулировок стал более понятным, рассмотрим следующий пример.
Р6. Встречаются два человека, А и В, которые заявляют следующее.
А: «Хотя бы один из нас говорит правду».
В: «Хотя бы один из нас лжец».
К какой категории следует отнести каждый из персонажей?
Высказывания персонажей представим в следующем виде:
А: T(A) v T(B)
B: F(A) v F(B)
Начнем с заявления персонажа В
T(B)=>F(A) v F(B)
И проанализируем левый операнд дизъюнкции. В результате будет сформирована корректная непротиворечивая интерпретация: В – правдолюбец, А – лжец.
Получив непротиворечивую интерпретацию высказывания персонажа В, перейдем к анализу высказывания персонажа А:
T(A)=> FALSE
Поскольку правдивость А противоречит сформированной ранее интерпретации высказывания персонажа В. Предположим, что А – лжец. Тогда:
F(A)=> -(T(A) v T(B))=> F(A) ^ F(B)=> FALSE.
Таким образом, оказывается, что это предположение также не работает, поскольку противоречит выбранной ранее интерпретации высказывания персонажа В, из которой следует, что В говорит правду.
Но анализ высказывания персонажа В нельзя считать законченным, поскольку не был выполнен анализ правого операнда дизъюнкции
T(B)=> F(A) v F(B)
И не было проанализировано предположение, что В лжец. До тех пор, пока это не будет выполнено, мы не имеем права делать вывод, что высказывания в формулировке задачи противоречат друг другу.
Поэтому придется вернуться назад в ту точку процесса логического анализа, где было сделано предположение об истинности левого операнда в дизъюнкции, и проанализировать вместо него правый операнд F(B). При этом сразу же будет обнаружено противоречие между истинностью F(B) и ранее высказанным предположением о правдивости персонажа В, но, не вернувшись назад и не выполнив этот анализ, мы не смогли бы обнаружить это противоречие. Теперь остается проанализировать следствие из предположения, что В – лжец.
F(B)=> -(F(A) v F(B))=> T(A) ^ T(B)=> FALSE
Только теперь можно с чистой совестью утверждать, что не существует непротиворечивой интерпретации высказываний, приведенных в условии задачи. Предположение о правдивости персонажа В приводит к конфликту с высказыванием персонажа А, а предположение о лживости В противоречит его же словам.
Чтобы в системе, использующей правила в качестве основного программного компонента, реализовать откат (обратное прослеживание), нужно в первую очередь иметь возможность восстановить тот контекст, который существовал в момент, когда было сформулировано предположение, приведшее к не удовлетворяющему нас результату. Как было показано в главе 5, одно из достоинств продукционных систем, подобных CLIPS, состоит в том, что они способны выполнить такой откат, не сохраняя прежнего состояния процесса вычислений, что коренным образом отличает их от фундаментально рекурсивных языков программирования, таких как LISP и PROLOG. При возникновении необходимости выполнить откат продукционные системы последовательно отменяют в обратном порядке все операции, связанные с добавлением данных в рабочую память, которые были выполнены, начиная с точки возврата, в которую нужно вернуться, вплоть до текущего этапа вычислений. Но таким способом можно реализовать возврат, только предполагая, что в ходе выполнения операций, следующих за точкой возврата, из рабочей память не было удалено ничего существенного, а все действия, модифицирующие состояние рабочей памяти, носили исключительно аддитивный характер.
Примеры, подобные задаче Р6, существенно усложняют жизнь, поскольку для их решения программа должна выполнять некоторые дополнительные операции, в которых не было необходимости при решении задач с единственным высказыванием.
(1) Сохранять информацию о возможных точках возврата.
(2) При обнаружении противоречия принимать решение, выполнять или не выполнять откат, а если выполнять, то в какую именно точку.
(3) Отменить все изменения, внесенные в состояние рабочей памяти после «прохождения» выбранной точки возврата.
(4) Возобновить вычисления начиная с точки возврата.
Рассмотрим подробнее каждую из этих операций.
· Каждый объект world имеет уникальный числовой идентификатор, который хранится в поле tag. Эта информация практически не используется при решении задач с единственным высказыванием, поскольку мы всегда имеем дело с одним и тем же объектом world, связанным с этим высказыванием. Но при решении задач, оперирующих с несколькими высказываниями, нам придется различать утверждения, которые порождены разными высказываниями в разных «мирах». По мере того, как мы будем переходить от анализа одних высказываний к другим, будут формироваться и новые объекты world. Прежние объекты world нужно оставлять в таком состоянии, чтобы при необходимости к ним можно было еще раз вернуться. Это означает, что вектор world, с которым прекращены операции (возможно, временно), содержал всю информацию, которая потребуется программе для возобновления работы с ним. При этом именно та точка, в которой процесс вычислений «переключился» на новый объект world, и будет, потенциальной точкой возврата. Информация, сохраняемая в объекте, включает знание о том, какое предположение о правдивости или лживости персонажа было сделано в этом «мире» и какие дизъюнкты (операнды составного дизъюнктивного выражения) в утверждении, содержащемся в высказывании персонажа, уже проанализированы.
· Поскольку каждый объект world имеет свой уникальный идентификатор и каждое утверждение (объект claim) индексировано определенным объектом world , можно довольно просто выяснить, существует ли противоречие между разными «мирами» (т.е. между утверждениями, связанными с разными объектами world). Остается единственный вопрос – нужно ли возвращаться в ранее покинутый «мир», если в текущем «мире» обнаружено противоречие с ним. Мы будем применять стратегию поиска в глубину, которая состоит в том, что откат нужно выполнять только в том случае, если противоречие сохраняется после полного завершения анализа текущего «мира».
· Если объекты world нумеруются последовательно, по мере их формирования, то потребуется разработать правило, которое при возвращении в покинутый ранее «мир» уничтожит как текущий объект world, так и все промежуточные объекты такого типа, которые при необходимости затем могут быть воссозданы.
· Если прежний объект world содержит полную информацию о том, в каком состоянии был покинут «мир», и утверждения в этом «мире» не противоречат этому состоянию, то ничто не мешает нам продолжить вычисления из точки возврата.
Начнем модификацию нашей программы с того, что в шаблон объекта world включим слот, в котором будет храниться идентификатор ранее покинутого «мира» (объекта), с которым данный объект конфликтует. Это нужно сделать по двум причинам.
(1) Нам потребуется различать случаи, в которых противоречия возникают в пределах одного и того же «мира», от конфликтов между «мирами». Если текущее высказывание само по себе противоречиво (т.е. является парадоксом), нет смысла выполнять откат в прежний мир и искать в нем разрешения противоречия.
(2) Наличие такого слота позволит разработать правило, которое будет выполнять откат прямо в этот покинутый ранее «мир».
Ниже будет показано, что для решения проблемы можно обойтись без реализации правила, упомянутого в п.2., хотя это и не так легко сделать, но соображения, высказанные в п.1., в любом случае остаются в силе.
;; Объект world представляет контекст,
;; сформированный определенными предположениями
;; о правдивости или лживости высказывания,
;; принадлежащего некоторому персонажу.
;; Объект имеет уникальный идентификатор в поле tag,
;; а смысл допущения – истинность или лживость –
;; фиксируется в поле scope.
;; Поле prior может содержать идентификатор
;; объекта world, обработанного перед тем,
;; как был создан данный объект, и с которым данный
;; объект может потенциально конфликтовать.
;; В поле context сохраняется текущий контекст
;; анализируемого операнда дизъюнкции.
(deftemplate world
(field tag (type INTEGER) (default 1))
(field scope (type SYMBOL) (default truth))
(field prior (type INTEGER) (default 0))
(field context (type INTEGER) (default 0)
)
Помимо модификации структуры объекта, для выполнения отката потребуется разработать правила для выполнения некоторых ключевых операций. Эти операции перечислены ниже вместе с ключевыми словами, ассоциированными с каждой из них.
· CHECK. Эта операция реализует нормальный режим выполнения вычислений при анализе предположений о правдивости или лживости.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14