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

Российской Федерации

Кубанский Государственный Технологический Университет

Курсовая работа на тему:

ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ CLIPS

Работу выполнил

студент группы 01-КТ-22 факультета КТАС Мариненко А. А.

Краснодар 2001

СОДЕРАЖНИЕ

· А.1. Краткая история CLIPS                                                                    3

· А.2. Правила и функции в CLIPS                                                                3

· А.3. Обектно-ориентированные средства в CLIPS                                    10

· А.4. Задача «Правдолюбцы и лжецы»                                                      15

· А.5 Стиль программирования на языке CLIPS                                    66

А.1. КРАТКАЯ ИСТОРИЯ CLIPS

Название языка CLIPS – аббревиатура от C Language Integrated Production System. Язык был разработан в центре космических исследований  NASA

{NASA’s Johnson Space Center} в середине 1980-х годов и во многом сходен с языками, созданными на базе LIPS, в частности OPS5 и ART. Использование C в качестве языка реализации объясняется тем, что компилятор LISP не поддерживается частью распространенных платформ, а также сложностью интеграции LISP-кода в приложения, которые используют отличный от LIPS язык программирования. Хотя в то время на рынке уже появились программные средства для задач искусственного интеллекта, разработанные на языке C, специалисты из NASA решили создать такой продукт самостоятельно. Разработанная ими система в настоящее время доступна во всем мире, и нужно сказать, что по своим возможностям она не уступает множеству гораздо более дорогих коммерческих продуктов.

Первая версия представляет собой, по сути, интерпретатор порождающих правил. Процедурный язык и объективно-ориентированное расширение CLIPS Object-Oriented Language {COOL} были включены в этот программный продукт только в 1990-х годах. Существующая в настоящее время версия может эксплуатироваться на платформах UNIX, DOS, Windows и Macintosh. Она является хорошо документированным общедоступным программным продуктом и доступна по сети FTR с множества университетских сайтов. Исходный код программного пакета CLIPS распространяется совершенно свободно и его можно установить на любой платформе, поддерживающей стандартный компилятор языка C. Однако я бы рекомендовал пользоваться официальной версией для определенной платформы, поскольку такие версии оснащены пользовательским интерфейсом, включающим меню команд и встроенный редактор.

Это Приложение организовано следующим образом. В разделе А.2. рассмотрены основные функции языка, описание правил и процедурного языка. В разделе А.3. представлены методы работы с объектами и показано, как использовать их в сочетании с правилами и процедурами. В разделе А.4. описан пример, демонстрирующий некоторые приемы программирования правил, а в разделе А.5. резюмируются характеристики этого программного продукта и предлагаются темы для более углубленного изучения.

 

А.2. ПРАВИЛА И ФУНКЦИИ В CLIPS

CLIPS включает в язык представления порождающих правил и язык описания процедур. В этом разделе мы рассмотрим оба этих модуля, сопровождая описание отдельных функций примерами.

Основными компонентами языка описания правил являются база фактов (fact base) и база правил (rule base). На них возлагаются следующие функции:

- база фактов представляет собой исходное состояние проблемы;

- база правил содержит операторы, которые преобразуют состояние проблемы, приводя его к решению.

 

Машина логического вывода CLIPS сопоставляет эти факты и правила и выясняет, какие из правил можно активизировать. Это выполняется циклически, причем каждый цикл состоит из трех шагов:

(1) сопоставление фактов и правил;

(2) выбор правила, подлежащего активизации;

(3) выполнение действий, предписанных правилом.

 

Такой трехшаговый циклический процесс иногда называют «циклом распознование – действие»

 

А.2.1. Факты

 

Сразу после запуска CLIPS-приложения на выполнение на экране появится приглашение, извещающее пользователя, что он работает с интерпретатором.

CLIPS>

В режиме интерпретатора пользователь может использовать множество команд. Факты можно включить в базу фактов прямо из командной строки с помощью команды assert, например:

CLIPS> (assert (today is Sunday))

<Fact-0>

CLIPS> (assert (weather is warm))

<Fact-0>

Для лучшего восприятия теста Приложения мы в дальнейшем будем выделять текст, вводимый пользователем, полужирным щрифтом, а запросы и ответы интерпретатора – обычным моноширинным шрифтом.

Для вывода списка фактов, имеющихся в базе, используется команда facts:

 

CLIPS>(facts)

f-1 (today is Sunday)

f-2 (weather is warm)

В последних версиях CLIPS, в частности, в той, которая работает в операционной среде Windows, такие команды как facts, можно вызвать с помощью меню.

Для удаления фактов из базы используется команда retract.

CLIPS> (retract 1)

CLIPS> (facts)

f-0 (today is Sunday)

 

Эти же команды, assert и retract, используются в выполняемой части правил (заключении правила) и с их помощью выполняется программное изменение базы фактов. Часто приходится пользоваться и другой командой интерпретатора, clear, которая очищает базу фактов (как правило, эта команда доступна в одном из выпадающих меню).

 

CLIPS> (clear)

CLIPS> (facts)

В тексте программы факты можно включать в базу не по одиночке, а целым массивом. Для этого в CLIPS имеется команда deffacts.

(deffacts today

(today is Sunday)

(weather is warm)

)

Выражение deffacts имеет формат, аналогичный выражениям в языке LISP. Выражение начинается с команды deffacts, затем приводится имя списка фактов, который программисти собирается определить (в нашем примере – today), а за ним следуют элементы списка, причем их количество не ограничивается. Этот массив фактов можно затем удалить из базы командой undeffacts.

CLIPS> (undeffacts today)

Выражение deffacts можно вводить и в командную строку интерпретатора, но лучше записать его в текстовый файл с помощью редактора CLIPS или любого другого текстового редактора. Загрузить этот файл в дальнейшем можно с помощью команды в меню File либо из командной строки.

CLIPS> (load “my file”)

Однако после загрузки файла факты не передаются сразу же в базу фактов CLIPS. Команда deffacts просто указывает интерпретатору, что существует массив today, который содержит множество фактов. Собственно загрузка выполняется командой reset.

CLIPS> (reset)

Команда reset сначала очищает базу фактов, а затем включает в неё факты из всех раннее загруженных массивов. Она также добавляет в базу единственный системно определенный факт:

f-0 (initial-fact)

Это делается по умолчанию, поскольку иногда имеет смысл включить в программу правило start rule, которое может быть сопоставлено с этим фактом и позволит выполнить какие-либо нестандартные инициализирующие операции. Однако включать такое правило в программу или нет – дело программиста.

Можно проследить, как выполняется команда reset, если перед выполнением приведенных выше команд установить режим слежения среды разработки. Для этого нужно вызвать команду Watch из меню Execution и установить в ней флажок Facts.

 

А.2.2. Правила

 

В языке CLIPS правила имеют следующий формат:

(defrule <имя правила>

    < необязательный комментарий >

    < необязательное объявление >

    < предпосылка_1 >

     ……………….

   < предпосылка_m >

=>

   < действие_1 >

    ………………..

   < предпосылка_n >

)

Например:

(defrule chores

        “Things to do on Sunday”

        (salience 10)

        (today is Sunday)

        (weather is warm)

=>

       (assert (wash car))

       (assert (chop wood)

)

 

В этом примере Chores – произвольно выбранное имя правила. Предпосылки в условной части правила

(today is Sunday)

(weather is warm)

сопоставляются затем интерпретатором с базой фактов, а действия, перечисленные в выполняемой части правила (она начинается после пары символов =>), вставят в базу два факта

(wash car)

(chop wood)

в случае, если правило будет активизировано. Приведенный в тексте правила комментарий

“Things to do on Sunday”

“Что делать в воскресенье”

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

(salience 10)

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

(defrule fun

      “Better things to do on Sunday”

      (salience 100)

      (today is Sunday)

      (weather is warm)

=>

     (assert (drink beer))

     (assert (play guitar))

)

 

Поскольку предпосылки обоих правил одинаковы, то при выполнении оговоренных условий они будут «конкурировать» за внимание интерпретатора. Предпочтение будет отдано правилу, у которого параметр salience имеет более высокое значение, в данном случае – правилу fun. Параметру salience может быть присвоено любое целочисленное значение в диапазоне [-10000, 10000]. Если параметр salience в определении правила опущен, ему по умолчанию присваивается значение 0.

Обычно в определении правила присутствуют и переменные. Если, например, правило

(defrule pick-a-chore

        “Allocating chores to days”

        (today is?day)

        (chore is?job)

=>

        (assert (do?job on?day))

)

будет сопоставлено с фактами

(today is Sunday)

(chore is carwash)

то в случае активизации оно включит в базу новый факт

(do carwash on Sunday).

 

Аналогично, правило

(defrule drop-a-chore

        “Allocating chores to days”

        (today is?day)

       ?chore <- (do?job on?day)

=>

       (retract?chore)

)

отменит выполнение работ по дому (a chore). Обратите внимание на то, что оба экземпляра переменной?day должны получить одно и то же значение. Переменная?chore в результате сопоставления должна получить ссылку на факт, который мы собираемся исключить из базы. Таким образом, если это правило будет сопоставлено с базой фактов, в которой содержатся

(today is Sunday)

(do carwash on Sunday)

то при активизации правила из базы будет удален факт

(do carwash on Sunday)

С подробностями выполнения процесса сосоставления в интерпретаторе CLIPS вы сможете познакомиться в Руководстве пользователя, а здесь только отметим, что факт

(do carwash on Sunday)

будет сопоставлен с любым из представленных ниже образцов

(do?? Sunday)

(do? on?)

(do? on?when)

(do $?)

(do $? Sunday)

(do?chore $?when)

 

Учтите, что префикс $? является признаком сегментной переменной, которая будет связана с сегментом списка. Например, в приведенном выше примере переменная $?when будет связана с

(on Sunday)

Если за префиксами? и $? не следует имя переменой, они рассматриваются как универсальные символы подстановки, которым соответственно может быть сопоставлен любой элемент или сегмент списка.

 

А.4.1. Анализ проблемы

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

Предложенные головоломки можно решить, систематически анализируя, что случится, если персонаж, произносящий реплику, является правдолюбцем, а что, если он – лжец. Обозначим через Т(А) факт, что А говорит правду, и следовательно, является правдолюбцем, а через F(А) – факт, что А лжет и, следовательно, является лжецом.

Рассмотрим сначала головоломку Р1. Предположим, что А говорит правду. Тогда из его реплики следует, что либо А лжец, либо В правдолюбец. Формально это можно представить в следующем виде:

Т(А) =>F(А) v Т(В)

Поскольку А не может одновременно быть и лжецом, и правдолюбцем, то отсюда следует

Т(А) =>Т(В)

Аналогично можно записать и другой вариант. Предположим, что А лжет:

F(A)=>-(F(A) v Т(В)).

Упростим это выражение:

F(A)=>-F(A) ^-Т(В) или F(A)=> Т(А)^F(B).

Сравнивая оба варианта, нетрудно прийти к выводу, что толко последний правильный, поскольку в первом варианте мы пришли к выводу, противоречащему условиям (не могут быть правдолюбцами одновременно А и В).

Таким образом, рассматриваемая проблема относится к типу таких, решение которых находится в результате анализа выводов, следующих из определенных предположений, и поиска в них противоречий (или отсутствия таковых). Мы предполагаем, что определенный персонаж говорит правду, а затем смотрим, можно ли в этом случае так распределить «роли» остальных персонажей, что не будут нарушены условия, сформулированные в репликах. На жаргоне, принятом в математическое логике, предположение о правдивости или лживости множества высказываний называется интерпретацией, а вариант непротиворечивого присвоения значений истинности элементам множества – моделью.

Однако наши головоломки включают и нечто, выходящее за рамки типовых проблем математической логики, поскольку реплики в них может произносить не один персонаж (как в головоломке Р2), а на реплику одного персонажа может последовать ответная реплика другого (как в головоломке Р3). В исходной версии программы, которую мы рассмотрим ниже, это усложнение отсутствует, но в окончательной оно должно быть учтено. Мы покажем, что постепенное усложнение программы довольно хорошо согласуется с использованием правил.

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

Р0. А заявляет: «Я лжец». Кто же в действительности А – лжец или правдолюбец?

Мы только что фактически процитировали хорошо известный Парадокс Лгуна. Если А лжец, то, значит, он врет, т.е. в действительности он правдолюбец. Но тогда мы приходим к противоречию. Если же А правдолюбец, т.е. говорит правду, то в действительности он лжец, а это опять противоречие. Таким образом, в этой головоломке не существует непротиворечивого варианта «распределения ролей», т.е. не существует модели в том смысле, который придается ей в математической логике.

Есть много достоинств в выборе для прототипа программы варианта головоломки Р0.

· В головоломке присутствует только один персонаж.

· Выражение не содержит логических связок, таких как И или ИЛИ, или кванторов, вроде квантора общности (все) и прочих.

· Отсутствует ответная реплика.

 

В то же время существенные черты проблемы в этом варианте присутствуют. Мы по-прежнему должны попытаться отыскать непротиворечивую интерпретацию высказывания А, т.е. должны реализовать две задачи, присутствующие в любых вариантах подобной головоломки:

· формировать альтернативные интерпретации высказываниям;

· анализировать наличие противоречий.

 

Вы увидите, что для выполнения этих двух задач потребуется использовать механизм, очень близкий к тем, которые мы рассматривали при описании систем обработки правдоподобия в главах 17 и 19.

 

А.4.3. Разработка правил

 

В этом разделе мы рассмотрим набор правил, который помогает справиться с вырожденной формулировкой Р0 задачи о лжецах и правдолюбцах. Первые два правила, unwrap-true и unwrap-false, извлекают содержимое высказывания в предположении, что персонаж, которому принадлежит высказывание, является соответственно правдолюбцем или лжецом, и на этом основании формируют объект claim.

 

;; Извлечение содержимого высказывания.

(defrule unwrap-true

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

    (statement (speaker?X) (claim $?Y) (tag?N))

=>

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

                    (scope truth)))

    (assert (claim (content $?Y) (reason?M)

                    (scope truth)))

)

(defrule unwrap-false

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

    (statement (speaker?X) (claim $?Y) (tag?N))

=>

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

           (scope falsity)))

    (assert (claim (content NOT $?Y) (reason?N)

            (scope falsity))

)

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

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

 

;; Правила отрицания

(defrule not1

  ?F <- (claim (content NOT T?P))

=>

   (modify?F (content F?P))

)

(defrule not2

  ?F <- (claim (conteny NOT F?P))

=>

   (modify?F (content T?P))

)

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

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

(defrule contra-truth

    (declare (salience 10))

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

   ?S <- (statement (speaker?Y) (tag?N))

   ?P <- (claim (content T?X) (reason?N) (scope truth))

   ?Q <- (claim (content F?X) (reason?N) (scope truth))

=>

    (printout t crlf

             “Statement is inconsistent if “?Y “ is a knight.”

;; “Высказывание противоречиво, если “?Y “ правдолюбец.”

  t crlf)

(retract?Q)

(retract?P)

(modify?W (scope falsity))

)

Если предположить, что исходное высказывание было правдивым, то в дальнейшем обнаруживается противоречивая пара утверждений, которые затем удаляются из рабочей памяти, а значение «правдивости» предположения в объекте world изменяется на falsity (лживость). Если же после этого также будет обнаружено противоречие, то мы приходим к выводу о глобальной несовместимости условий задачи, т.е. в данной постановке мы имеем дело с логическим парадоксом.

 

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

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

(defrule contra-falsity

   (declare (salience 10))

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

  ?S <- (statement (speaker?Y) (tag?N))

  ?P <- (claim (content F?X) (reason?N) (scope falsity))

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

=>

 (printout t crlf

“Statement is inconsistent if “?Y “ is a knave.”

;; “Высказывание противоречиво, если “?Y “ лжец.”

t crlf)

(modify?W (scope contra))

)

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

 

;; Удалить из базы фактов все утверждения,

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

(defrule sweep

(declare (salience 20))

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

?F <- (claim (reason?N) (scope truth))

=>

(retract?F)

)

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

Если теперь запустить на выполнение программу, представив ей исходный набор фактов, соответствующих условию задачи Р0, то программа обнаружит, что оба контекста противоречивы. Другими словами, независимо от того, предполагаем ли мы, что А говорит правду или лжет, программа обнаружит противоречие в контексте world. Трассировка программы в этом случае представлена в листинге А.1. Строки, выведенные курсивом, - сообщения основной программы, а прочие – сообщения программы трассировки. Для удобства строки, указывающие на активизацию правил, представлены полужирным шрифтом.

 

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

CLIPS> (reset)

= => f-0 (initial-fact)

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

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

CLIPS> (run)

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))

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))

Упражнение 1

 

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

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

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

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

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

 

Упражнение 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) Возобновить вычисления начиная с точки возврата.

 

Рассмотрим подробнее каждую из этих операций.

· Каждый объект world имеет уникальный числовой идентификатор, который хранится в поле tag. Эта информация практически не используется при решении задач с единственным высказыванием, поскольку мы всегда имеем дело с одним и тем же объектом world, связанным с этим высказыванием. Но при решении задач, оперирующих с несколькими высказываниями, нам придется различать утверждения, которые порождены разными высказываниями в разных «мирах». По мере того, как мы будем переходить от анализа одних высказываний к другим, будут формироваться и новые объекты world. Прежние объекты world нужно оставлять в таком состоянии, чтобы при необходимости к ним можно было еще раз вернуться. Это означает, что вектор world, с которым прекращены операции (возможно, временно), содержал всю информацию, которая потребуется программе для возобновления работы с ним. При этом именно та точка, в которой процесс вычислений «переключился» на новый объект world, и будет, потенциальной точкой возврата. Информация, сохраняемая в объекте, включает знание о том, какое предположение о правдивости или лживости персонажа было сделано в этом «мире» и какие дизъюнкты (операнды составного дизъюнктивного выражения) в утверждении, содержащемся в высказывании персонажа, уже проанализированы.

· Поскольку каждый объект world имеет свой уникальный идентификатор и каждое утверждение (объект claim) индексировано определенным объектом world, можно довольно просто выяснить, существует ли противоречие между разными «мирами» (т.е. между утверждениями, связанными с разными объектами world). Остается единственный вопрос – нужно ли возвращаться в ранее покинутый «мир», если в текущем «мире» обнаружено противоречие с ним. Мы будем применять стратегию поиска в глубину, которая состоит в том, что откат нужно выполнять только в том случае, если противоречие сохраняется после полного завершения анализа текущего «мира».

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

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

Начнем модификацию нашей программы с того, что в шаблон объекта world включим слот, в котором будет храниться идентификатор ранее покинутого «мира» (объекта), с которым данный объект конфликтует. Это нужно сделать по двум причинам.

(1) Нам потребуется различать случаи, в которых противоречия возникают в пределах одного и того же «мира», от конфликтов между «мирами». Если текущее высказывание само по себе прот