Реферат: Программирование на языке CLIPS

FIRE 1 unwrap-true: f-1,f-2

Assumption:

          A is a knight, so (T A) is true.

= => f-3  (claim (content F A) (reason 1) (scope truth))

= => f-4  (claim (content T A) (reason 1) (scope truth))

FIRE 2 contra-truth: f-1, f-2, f-4, f-3

Statement is inconsistent if A is a knight.

<= = f-3  (claim (content F A) (reason 1) (scope truth))

<= = f-4  (claim (content T A) (reason 1) (scope truth))

<= = f-1  (world (tag 1) (scope truth))

= => f-5  (world (tag 1) (scope falsity))

FIRE 3 unwrap-false: f-5, f-2

Assumption

A is a knave, so (T A) is false.

= => f-6  (claim (content NOT F A) (reason 1) (scope falsity))

= => f-7  (claim (content F A) (reason 1) (scope falsity))

FIRE 4 not2: f-6

<= = f-6  (claim (content NOT F A) (reason 1) (scope falsity))

= => f-8  (claim (content T A) (reason 1) (scope falsity))

FIRE 5 contra-falsity: f-5, f-2, f-7, f-8

Statement is inconsistent if A is a knave.

<= = f-5  (world (tag 1) (scope falsity))

= => f-9  (world (tag 1) (scope contra))

Упражнение 1

Читателям, желающим самостоятельно проэкспериментировать с этой программой, я предлагаю рассмотреть другой вырожденный случай головоломок этого класса.

Предположим, что персонаж А утверждает : «Я всегда говорю правду». К какой категории следует отнести этот персонаж?

В такой постановке задача имеет неоднозначное решение. Предположение, что А правдолюбец, не приводит нас к противоречию. Но точно так же не приводит к противоречию и предположение, что А – лжец.

Ваша задача – модифицировать описанную выше программу таким образом, чтобы она давала заключение, что оба контекста непротиворечивы. Один из возможных вариантов модификации – ввести в состав программы правила consist-truth и consist-falsity, разработав их по образцу правил contra-truth и contra-falsity. Эти правила должны дать пользователю знать, что при данном положении противоречий не обнаружено, причем правила должны активизироваться в случае, когда нет больше правил, претендующих на внимание интерпретатора.

Обратите внимание на то, что в задачах этого класса недостаточно убедиться, что начальное предположение об истинности некоторого высказывания не приводит к противоречию. Необходимо еще и проверить, приведет ли к противоречию обратное предположение. Если окажется, что оно также непротиворечиво, значит, задача не имеет единственного решения.

А.4.4. Расширение набора правил – работа с составными высказываниями

Расширим тепрь возможности программы таким образом, чтобы она могла работать с составными высказываниями. Это даст возможность охватить в ней не только вырожденный случай, рассмотренный в предыдущем разделе, но и более сложные. За основу возьмем следующую головоломку.

Р4. Встречаются два персонажа, А и В, каждый из которых либо лжец, либо прадолюбец. Персонаж А говорит: «Мы оба лжецы.» К какой категории следует отнести каждого из них?

В этой задаче нам придется иметь дело с конъюнкцией, поскольку утверждение, высказанное персонажем А, моделируется выражением

F (A) ^ F (B)

Эту конъюнкцию нужно разделить на выражения-компоненты и проанализировать их непротиворечивость. Очевидно, что А не может быть правдолюбцем, поскольку это противоречит утверждению, которое содержится в его реплике. Но программа должна самостоятельно «распаковать» эту конъюнкцию для того, чтобы прийти к токому выводу.

Нам также понадобится снабдить программу и средствами обработки дизъюнкции, поскольку, если предположить, что А лжет, нужно будет оперировать с отрицанием этого утверждения, которое преобразует выражение

F (A) ^ F (B)

в

F (A) v F (B)

Таким образом, в программу нужно включить правило выполнения отрицания составных высказываний и правило, которое «понимало» бы, что дизъюнкции вроде Т (А) в действительности являются предположениями. Составное выражение T (A) v T (B) будем обрабатывать, предположив Т (А), и проанализируем, нет ли в нем противоречия. Если таковое не обнаружится, то можно предположить, что T (A) v T (B) совместимо с утверждением о том, что А лгун, т.е. F (A). Но если предположение Т (А) приведет к несовместимости, то нужно отказаться от него и предположить Т (В). Если и это предположение приведет к несовместимости, то это озаначает, что утверждение                 Т (А) v Т (В) несовместимо с предположением F (A). В противном случае Т (В) образует часть совместимоц интерпретации исходного высказывания.

В CLIPS составные высказывания проще всего представлять с помощью так называемой «польской» (или префиксной) нотации операций. Суть этого способа представления операций состоит в том, что символ операции предшествует символам операндов. Каждый оператор имеет фиксированное количество операндов, а потому всегда существует возможность однозначно установить область действия операций даже в случае, если операнды представляют собой вложенные выражения. Таким образом, выражение, представленное скобочной формой – (F (A)^T (B)), в польской записи будет иметь вид

NOT AND F A T B.

Легче всего восстановить исходный вид выражения, представленного в польской нотации, просматривая его справа налево. При этом операнды считываются до тех пор, пока не встретится объединяющий их оператор. Полученное выражение оказвается операндом следующего оператора. В представленном выше выражении В является операндом одноместного оператора Т, а пара операндов Т(В) и F(A) объединяется оператором AND.

Задавшись таким способом представления составных высказываний, сформируем правило выполнения отрицания дизъюнктивной и конъюнктивной форм, в котором будет использоваться функция flip, заменяющая “T” на “F” и наоборот.

(defrule not-or

       ?F <- (claim (content NOT OR ?P ?X ?Q ?Y))

=>

       (modify ?F (content AND (flip ?P)  ?X (flip ?Q)  ?Y))

)

(defrule not-and

        ?F <- (claim (content NOT AND ?P ?X ?Q ?Y))

 =>

        (modify ?F (content OR (flip ?P)  ?X  (flip ?Q)  ?Y))

)

Использование функции flip упрощает преобразование и позволяет перейти от выражения

NOT AND F A T B

Прямо к

           OR T A F B,

Минуя

          OR NOT F A NOT T B.

Функция flip определена следующим образом:

(deffunction flip (?P)

          (if (eq ?P T) then F else T)

)

Для упрощения мы ограничимся утверждениями в виде простых дизъюнкций или конъюнкций вида

T(A)vT(B)

Или

F(A)^T(B),

Но не будем использовать более сложные утверждения в форме

F(B)^(T(A)vT(B))

Или

-(F(A)vF(B))^(T(A)vT(B)),

поскольку для решения большинства интересных головоломок вполне достаточно простых выражений.

Наибольшие сложности при модификации нашей программы связаны с обработкой дизъюнктивных выражений, поскольку вывод о наличии противоречия может быть сделан только после завершения анализа всех членов операндов дизъюнкции. Напрмер, нет противоречия между F(A) и T(A)vF(B). Противоречие, которое обнаружится при обработке первого операнда дизъюнкции Т(А) в предположении F(A), будет локальным в контексте Т(А). Но если мы вернемся к исходной дизъюнкции и попробуем проанализировать контекст F(B), то никакого противоречия обнаружено не будет, и, следовательно, интерпретация найдена.

Реализовать такой анализ локальных и глобальных противоречий можно, добавив в шаблон объекта claim атрибут contest:

(deftemplate claim

         (multifield content (type SYMBOL))

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

         (field scope (type SYMBOL))

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

)

Значение 0 в поле context означает, что мы имеем дело с глобальным контекстом, значение 1 – с локальным контекстом левого операнда, а значение2 – с локальным контекстом правого операнда дизъюнкции. Пусть, например, анализируется дизъюнкция

    T(A)vF(B),

Причем Т(А) будет истинным в контексте 1, а F(B) – истинным в контексте 2. В этом случае все выражение будет истинным глобально, т.е. в контексте 0.

Структуру объекта world также нужно модифицировать – внести в нее поле context. Это позволит отслеживать ход вычислений. Пусть, например, объект world имеет вид

(world (tag 1)  (scope truth)  (context 2)).

Это означает, что данный «мир» создан следующей парой предположений:

·            истинно высказывание, имеющее идентификатор (tag), равный 1, и

·            правый операнд утверждения, которое содержится в этом высказывании, имеет значение «истина».

Новый вариант шаблона объекта world приведен ниже.

;; Объект world представляет контекст,

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

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

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

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

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

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

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

;; 0 означает глобальный контекст дизъюнкции,

;; 1 означает левый операнд,

;; 2 означает правый операнд.

(deftemplate world

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

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

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

)

Следующий шаг – разработка правил, манипулирующих контекстом. Приведенное ниже правило формирует контекст для левого операнда дизъюнкции.

(defrule left-or

        ?W <- (world (tag ?N)  (context 0))

        (claim (content OR ?P ?X ?Q ?Y)  (reason ?N)

                (scope ?V))

=>

        (modify ?W  (context 1))

        (assert  (claim

                 (content ?P ?X)  (reason ?N)  (scope ?V)          

                              (context 1)))

)

Это правило устанавливает значение 1 в поле context объекта world т формирует соответствующий объект claim.

По этому же принципу разработаем правило для формирования контекста правого операнда дизъюнкции.

(defrule right-or

        ?W <- (world (tag ?N)  (context 1))

        (claim (content OR ?P ?X ?Q ?Y)  (reason ?N)

               (scope ?V))

=>

        (modify ?W (context 2))

        (assert  (claim

                (content ?Q ?Y)  (reason ?N)  (scope ?V)

                (context 2))

)

Упражнение 2

Разработайте самостоятельно правило, которое оперировало бы с объектом claim содержим утверждение в конъюнктивной форме, как показано ниже.

(claim  (content AND T A F B ) (reason 1) (scope truth))

Это правило должно разделить такое утверждение на два: суть первого – утверждение, что А – правдолюбец, а второго – утверждение, что В – лжец. Новяе объекты claim должны существовать в текущем контексте, определенном в объекте world.

Далее разработаем правила, чувствительные к контексту, которые будут выявлять наличие противоречий в анализируемых утверждениях.

;; Выявление противоречия между предположением о

;; правдивости и следующими из него фактами

;; в разных контекстах одного и того же объекта world.

(defrule contra-truth-scope

         (declare (salience 10))

         (world (tag ?N) (scope truth) (context ?T))

         (claim

                  (content T ?X) (reason ?N) (scope truth)

                  (context ?S&: (< ?S ?T)))

         ?Q <- (claim (content P ?x) (reason ?N)

                   (scope truth) (context ?T))

=>

         (printout t “Disjunct “  ?T

                    “ is inconsistent with earlier truth context. “

;; “Дизъюнкт “ ?T

;; “ противоречит ранее установленному контексту правдивости. “

              crlf)

              (retract ?Q)

)

;; Выявление противоречия между предположением о

;; лживости и следующими из него фактами

;; в разных контекстах одного и того же объекта world.

(defrule contra-falsity-scope

        (declare (salience 10))

        ?W <- (world (tag ?N) (scope falsity) (context ?T))

        (claim

               (content F ?X) (reason ?N) (scope falsity)

               (context ?S&: (< ?S ?T)))

        ?Q <- (claim (content T ?X) (reason ?N)

               (scope falsity) (context ?T))

=>

        (printout t “Disjunct “ ?T

               “ is inconsistent with earlier falsity context. “

;; “Дизъюнкт” ?T

;; “ противоречит ранее установленному контексту лживости. “

               crlf)

   retract ?Q)

)

Нам потребуется модифицировать и прежний вариант правила contra-truth.

;; Выявление противоречия между предположением о

;; правдивости и следующими из него фактами

;; в одном и том же контексте оджного и того же объекта world.

(defrule contra-truth

       (declare (salience 10))

       ?W <- (world (tag ?N) (scope truth))

       ?P <-  (claim (content T ?X) (reason ?N) (context ?S)

               (scope truth))

       ?Q <- (claim (content F ?X) (reason ?N) (context ?S)

               (scope truth))

=>

       (printout t

               “Statement is inconsistent if “?X “ is a knight”

;; “Высказывание противоречиво, если “? X

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

           crlf)

    (retract ?Q)

    (retract ?P)

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

)

;; Выявление противоречия между предположением о

;; лживости и следующими из него фактами

;; в одном и том же контексте одного и того же объекта world.

(defrule contra-falsity

       (declare (salience 10))

       ?W <- (world (tag ?N) (scope falsity))

       ?P <- (claim (content F ?X) (reason ?N) (context ?S)

             (scope falsity))

       ?Q <- (claim (content T ?X) (reason ?N) (context ?S)

             (scope falsity))

=>

       (printout t

             “Statement is inconsistent whether “ ?X

                       “ is a knight or knave.”

;; “Высказывание противоречиво, независимо от того,”

;; “является ли “ ?X “ прадолюбцем или лжецом.”

             crlf)

    (modify ?W (scope contra)

)

Поскольку теперь постановка задачи усложнилась по сравнению с вырожденным случаем, имеет смысл включить в программу распечатку предположений о характеристиках персонажей, упомянутых в высказываниях.

(defrule consist-truth

        (declare (salience -10))

         ?W <- (world (tag ?N) (scope truth)

        (statement (speaker ?Y) (tag ?N))

=>

        (printout t

        “Statement is consistent:”

;; “Высказывание непротиворечиво:”

     crlf)

     (modify ?W (scope consist)

) 

(defrule consist-falsity

      (declare (salience -10))

      ?W <- (world (tag ?N) (scope falsity))

      (statement (speaker ?Y (tag ?N))

=>

      (printout t

             “Statement is consistent:”

;; “Высказывание непротиворечиво:”

             crlf)

      (modify ?W (scope consist)

)

(defrule true-knight

      (world (tag ?N) (scope consist))

      ?C <- (claim (content T ?X) reason ?N)

=>

      (printout t

      ?X “is a knight”

;;    ?X “ – правдолюбец”

               crlf)

          (retract ?C)

)

(defrule false-knave

        (world (tag ?M) (scope consist))

        ?C <- (claim (content F ?X) (reason ?N))

=>

        (printout t

               ?X “ is a knave”

;;      ?X “ – лжец”

                  crlf)

        (retract ?C)

)

Ниже приведенное правило разделения операции конюънкции, которое ранее мы предлагали вам разработать самостоятельно. Обратите внимание на то, что в нем также отслеживается контекст, хотя в данном случае без этого можно было бы и обойтись.

(defrule conj

       (world (tag ?N) (context ?S))

       (claim (content AND ?P ?X ?Q ?Y) (reason ?N)

                (scope ?V))

=>

       (assert (claim

                (content ?P ?X) (reason ?N) (scope ?V)

                (context ?S)))

       (assert  (claim

                (content ?Q ?Y) (reason ?N) (scope ?V)

                (context ?S)))

)

Прежде чем запустить программу на выполнение, сформируем исходные факты в соответствии с условиями задачи Р4:

(deffacts the-facts

        (world)

        (statement (speaker A) (claim AND F A F B ) (tag 1))

)

После запуска программы в режиме трассировки интерпретатор сформирует распечатку процесса ее выполнения, приведенную в листинге А.2.

Листинг А.2. Трассировка решения задачи Р4

 CLIPS> (reset)

= => f-0  (initial-fact)

= => f-1  (world (tag 1) (scope truth) (context 0))

= => f-2  (statement (speaker A) (claim OR F A T B) (reason 0) (tag 1))

CLIPS> (run)

FIRE 1 unwrap-true: f-1, f-2

Assumption

        F is a knight, so (OR F A T B) is true.

= => f-3  (claim (content OR F A T B) (reason 1) (scope truth) (context 0))

= => f-4  (claim (content T A) (reason 1) (scope truth) (context 0))

FIRE 2 left-or: f-1, f-3

= => f-5  (claim (content F A) (reason 1) (scope truth) (context 1))

<= = f-1  (world (tag 1) (scope truth) (context 0))

= => f-6  (world (tag1) (scope truth) (context 1))

FIRE 3 contra-truth-scope: f-6, f-4, f-5

Disjunct 1 is inconsistent with earlier truth context.

<= = = f-5  (claim (content F A) (reason 1) (scope truth) (context 1))

FIRE 4 right-or: f-6, f-3

= => f-7  (claim (content T B) (reason 1) (scope truth) (context 2))

<= = f-6  (world (tag 1) (scope truth) (context 1))

= => f-8  (world (tag 1) (scope truth) (context 2))

FIRE 5 consist-truth: f-8, f-2

Statement is consistent:

<= = f-8  (world (tag 1) (scope truth) (context 2))

= => f-9  (world (tag 1) (scope consist) (context 2))

FIRE 6 true-knight: f-9, f-7

B is a knight

<= = f-7  (claim (content T B) (reason 1) (scope truth) (context 2))

FIRE 7 true-knight: f-9, f-4

A is a knight

<= = f-4  (claim (content T A) (reason 1) (scope truth) (context 0))

CLIPS>

А.5. Обратное прослеживание и множество контекстов

Модифицируем программу таким образом, чтобы она могла справиться и с задачами этого класса в более сложной постановке. Речь идет о задачах, в которых несколько персонажей произносят реплики. Пример такого рода головоломки приведен ниже.

Упражнение 3

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

А: «Я говорю правду, либо В лжец».

В: «А говорит правду, либо я лжец».

К какой категории следует отнести каждый из персонажей? (Решите эту задачу самостоятельно вручную, используя ту же систему обозначений, которая применялась ранее в этом Приложении.)

Задача анализа высказываний нескольких персонажей потребует использования более сложной методики, которая получила наименование «обратное прослеживание на основе анализа зависимостей» (dependency-directed backtracking).

От программы потребуется выполнить обратное прослеживание (откат) в следующих ситуациях:

·            когда обнаружится конфликт между текущим «миром» и ранее существовавшим, причем в ранее существовавшем «мире» предполагается истинность высказывания, но не была проанализирована его лживость;

·            когда обнаружится конфликт между текущим «миром» и ранее существовавшим, причем в ранее существовавшем «мире» был проанализирован только один операнд в составном дизъюнктивном утверждении.

Чтобы смысл этих формулировок стал более понятным, рассмотрим следующий пример.

Р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, 5, 6