Программирование на языке CLIPS

(defrule sweep-truth

(declare (salience 100))

(world (tag ?N) (scope falsity))

?F

(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

(modify ?W (task back))

)

Альтернативный сценарий используется в ситуации, когда в ранее

покинутом «мире» не были проанализированы все дизъюнкты составного

утверждения. «Мир» был покинут, когда обнаружилось, что проанализированный

дизъюнкт не противоречит предположению, поэтому прочие дизъюнкты просто не

рассматривались. Теперь, когда обнаружилось противоречие с другим «миром»,

можно вновь вернуться к ранее незавершенному анализу и попробовать, не

разрешится ли конфликт в результате исследования другого дизъюнкта.

Приведенное ниже правило undirected-disjunct выполняет подготовку к

такому откату в хронологическом порядке.

;; Хронологический откат к тому «миру», который был

;; покинут без завершения анализа дизъюнктов.

(defrule undirected-disjunct

(world (tag ?N) (scope falsity) (task contra))

V

;; Дизъюнкт в ранее покинутом “мире”, анализ которого

;; не был выполнен.

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

modify ?W (task back))

)

;; Если обнаружено противоречие между

;; объектами M и N

;; и объект М создан ранее объекта N, причем

;; не был выполнен анализ всех дизъюнктов в M,

;; ТО вернуться к анализу объекта M.

(defrule directed-disjunct

(world (tag ?N) (scope falsity) (task contra)

(prior ?M&~0))

?V

;; Дизъюнкт в ранее покинутом “мире”, анализ которого

;; не был выполнен.

(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.

;; ЕСЛИ выполняется откат к объекту М,

;; ТО удалить все объекты world,

;; имеющие идентификатор, больший М.

;; ПРИМЕЧАНИЕ: правило может активизироваться

;; несколько раз.

(defrule undo-world

(declare (salience 40))

(world (tag ?M) (task back))

?W ?N ?M)))

?S

(retract ?W)

(modify ?S (done 0))

)

;; Удаление объектов claim.

;; ЕСЛИ выполняется откат к объекту world M,

;; ТО удалить все объекты claim,

;; связанные с удаленными объектами world.

(defrule unclaim

(declare (salience 30))

(world (tag ?M) (task back))

?F ?N ?M)))

=>

(retract ?F)

)

;; Возобновление процесса вычислений

;; начиная с точки возврата.

;; ЕСЛИ все объекты world, созданные

;; после объекта М, удалены,

;; ТО повторно сформировать объект М,

;; предположив лживость высказывания.

(defrule restart

(declare (salience 20) )

?W

(retract ?W)

(modify ?W (scope falsity) (task check) (context 0))

)

Последнее из приведенных выше правил вновь запускает процесс анализа

того объекта world, к которому выполнен откат. Обратите внимание на то, что

это правило имеет самый низкий приоритет. В результате правила,

уничтожающие ненужные объекты, будут активизированы в первую очередь.

Организация процесса вычислений на основе этих правил позволяет

программе продолжать вычисления до тех пор, пока имеются не до конца

проанализированные «миры». При использовании «ненаправленных» правил отката

программа всегда сможет вернуться к последнему объекту world, предлагающему

альтернативный вариант предположения, или к такому объекту, в котором

имеются еще не проанализированные дизъюнкты составного утверждения.

Упражнение 5

Проанализируйте следующую головоломку.

Р7. Встретились два человека, А и В, которые заявляют следующее.

А: «В утверждает, что он правдолюбец.»

В: « А утверждает, что он лжец.»

К какой категории следует отнести каждый персонаж? Как следует

модифицировать нашу программу, чтобы она могла решать задачи такого вида?

Ниже будут высказаны некоторые соображения, которые подскажут вам, как

модифицировать модель для таких задач.

В существующей программе мы прежде всего анализировали

непротиворечивость каждого из «миров», т.е. внутреннюю непротиворечивость

каждого отдельного высказывания. После этого мы анализировали

непротиворечивость одного «мира» другому (или другим).

Включение в постановку задачи высказывания о высказывании (назовем

его метавысказыванием) несколько усложняет положение дел. В такой

постановке высказывание образует «мир», в котором другое высказывание, а не

утверждение, может быть истинным или ложным. Это второе, внутреннее,

высказывание должно также формировать собственный «мир».

Рассмотрим высказывание

А: «В утверждает, что он правдолюбец.»

Предположив, что А говорит правду, мы сформируем «мир», в котором В

действительно утверждает, что он правдолюбец, но внутри этого «мира»

существует и другой, в котором В действительно является правдолюбцем.

Отслеживать подобного рода связи между внешним высказыванием и «внедренным»

в него внутренним высказыванием – одна из новых задач механизма обработки

правдоподобия.

А что можно сказать о «мире», в котором А лжет? Мы должны показать,

что заявление В о том, что он лжец, приведет к противоречию.

А.4.6. Обработка метавысказываний

Имеяв свом распоряжении программу, снабжённую механизмом реализации

откатов, попробуем адаптировать её к работе с метавысказываниями, т.е.

высказываниями о высказываниях. Это позволит нам решать задачи, подобные

Р7, которая приведена в упр. 5.

Рассмотрим высказывание:

А: «В утверждает, что он правдолюбец».

Мы должны сформировать «мир», в котором В утверждает, что он

правдолюбец, а внутри этого «мира» другой, в котором В действительно

является правдолюбцем. Также внедренные «миры» образуют отдельное множество

зависимостей, которое придётся отслеживать с помощью механизма обработки

правдоподобия. Начнём с того, что модифицируем шаблон объекта world и

внесём в него информацию о том, является ли данный объект внешним или

внутренним, а если внутренним, то какой объект world является для него

внешним.

В более сложных сцинариях работы с «мирами» нам потребуется также

отслеживать, был ли данный объект world проанализирован полностью. Это

упростит выполнение отката.

;; Объект world представляет множество утверждений,

;; сформированных при определённом предположении

;; о правдивости или лживости высказывания,

;; принадлежащего некоторому персонажу.

;; Объект имеет уникальный идентификатор

;; в поле tag, который соответствует

;; тегу высказываний.

;; Смысл допущения – истинность или лживость –

;; фиксируется в поле scope.

;; Поле TASK содержит одно из перечисленных

;; ниже значений:

;; CHECK – анализ предположений о

;; правдивости или лживости высказываний;

;; CONTRA – анализ обнаруженного противоречия;

;; CLEAN – удаляет все утверждения, созданные

;; в противоречивом «мире»;

;; BACK – откат в точку возврата;

;; QUIT – прекращение процесса.

;; Поле prior может содержать идентификатор

;; объекта world, созданного перед тем,

;; как был создан данный объект, и с которым данный

;; объект может потенциально конфликтовать.

;; Поле upper содержит идентификатор другого объекта

;; world, в который внедрён данный объект, если

;; соответствующее высказывание содержит другое

;; высказывание.

;; Например, А говорит, что В сказал, что А – лжец.

;; В поле context сохраняется текущий контекст

;; анализируемого операнда дизъюнкции.

;; Поле done содержит информацию о том, обработано ли

;; уже высказывание, на основании которого создан этот

;; объект.

(deftemplate world

(field tag (type INTEGER) (default 1))

(field scope (type SYMBOL) (default truth))

(field task (type SYMBOL) (default check))

(field prior (type INTEGER) (default (0))

(field upper (type INTEGER) (default 0))

(field context (type INTEGER) (default 0))

(field done (type INTEGER) (default 0))

)

;; Объект statement (высказывание) связан с определённым

;; персонажем (поле speaker).

;; Высказывание содержит утверждение (поле claim).

;; Высказывание имеет основание – причину (поле reason)

;; Если данный объект не является производным от другого

;; объекта statement, в поле reason устанавливается

;; значение 0.

;; В поле tag устанавливается уникальный числовой

;; идентификатор объекта – число, большее 0.

;; В поле DONE устанавливается одно из

;; следующих значений:

;; 0 означает, что объект ещё не обрабатывался;

;; 1 означает, что объект обрабатывался в предположении

;; о правдивости высказывания;

;; 2 означает, что объект обрабатывался в предположении

;; о лживости высказывания.

(deftemplate statement

(field speaker (type SYMBOL))

(multifield claim (type SYMBOL))

(field scope (type SYMBOL) (default truth))

(multifield reason (type INTEGER) (default 0))

(field tag (type INTEGER) (default 0))

(field done (type INTEGER) (default 0))

)

Теперь разработаем правило, которое будет «распаковывать»

высказывание о высказывании.

;; ЕСЛИ объект world базируется на предположении о

;; правдивости метавысказывания,

;; ТО прредположить, что персонаж говорит правду и что

;; высказывание истинно.

(defrule unwrap-true-state

?W

(printout

t crlf

“Assuming “ T ?X “ and “ ?Z “ says “ $?Y

“ in world “ ?N

;; “Предполагается “ Т ?Х “ и “ ? Z “ говорит “ $?Y

;; “ в мире “ ?N

t crlf

)

;; Зафиксировать, что высказывание было распаковано

;; в предложении о его правдивости.

(modify ?S (tag ?N) (done 1))

;; Предположим, что персонаж в текущем «мире» является

;; правдолюбцем.

(assert (claim (content T ?X) (reason ?N)

(scope truth)))

;; Зафиксировать в объекте world для внедрённого

;; высказывания и зафиксировать, что этот объект

;; является внутренним по отношению к объекту ?N.

(assert (world (tag (+ ?N 1)) (scope truth) (upper ?N)))

;; Зафиксировать внедрённое высказывание в новом

;; объекте world.

(assert (statement (speaker ?Z) (claim $?Y)

(reason ?N)))

)

;; ЕСЛИ объект world базируется на предположении о

;; лживости метавысказывания,

Страницы: 1, 2, 3, 4, 5, 6, 7, 8