Часть 8.

moves([State, _, Depth, _, _], Rest_open_pg, Closed_set,

[Next, State, New_D, H, S] , Goal) :-

move(State, Next),

not(unsafe(Next)), %определяется с учетом задачи

not(member_pq([Next, _, _, _, _], Rest_open_pq)), not(member_set([Next, _, _, _, _], Closed_set)),

New_D is Depth + 1,

heuristic(Next, Goal, H), %определяется с учетом задачи

S is New_D + H.

И, наконец, команда printsolution выводит путь решения. Она рекурсивно нахо­дит пары [State, Parent] путем проверки соответствия первых двух элементов в описании состояния первым двум элементам пятиэлементных списков, составляющих множество Closed_set. Родителем начального состояния является указатель nil.

printsolution([State, nil, _, _,_],_) :-

write(State), nl.

printsolution([State, Parent, _, _, _], Closed_set) :-

member_set([Parent, Grandparent, _, _, _], Closed_set),

printsolution([Parent, Grandparent, _, _, _], Closed_set),

write(State), nl.

14.5. Реализация планировщика на языке PROLOG

В разделе 5.4 был описан алгоритм планирования на основе теории предикатов. В нем логика предикатов использовалась как для представления состояний мира плани­рования, так и для описания правил изменения таких состояний. В этом разделе будет разработана реализация этого алгоритма на языке PROLOG.

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

start = [handempty, ontable(b), ontable(c), on(a, b), clear(c),

clear(a)]

goal = [handempty, ontable(a), ontable(b), on(c, b), clear(a),

clear(c)]

Эти состояния наряду с фрагментом пространства поиска показаны на рис. 14.3 и 14.4.

Переходы в этом "мире блоков" описываются с помощью списков добавления и удаления, как в разделе 7.4. Предикаты move зависят от трех аргументов. Первый - имя преди­ката move с его параметрами. Второй аргумент - это список предусловий, т.е. перечень предикатов, которые должны быть истинны в описании состояния мира, чтобы данное пра­вило перехода было применимо к этому состоянию. Третий аргумент - это список добав­ления и удаления или перечень предикатов, которые добавляются к состоянию мира или удаляются из него для создания нового состояния в результате применения правила пере­хода. Заметим, что в данном случае полезно использовать абстрактные типы данных и опе­рации над множествами, в том числе объединение, пересечение, разность и т.д. Их удобно применять для управления предусловиями, а также добавления и удаления списков.

Четыре перехода в этом мире можно описать следующим образом.

move(pickup(X), [handempty, clear(X), on(X, Y) ] ,

[del(handempty), del(clear(X)), del(on(X,Y)),

add(clear(Y)), add(holding(X))]).

636 Часть VI. Языки и технологии программирования для искусственного интеллекта

move(pickup(X), [handempty, clear(X), ontable(X)],

[del(handempty), del(clear(X)), del(ontable(X))

add(holding(X))]). move(putdown(X), [holding(X)] ,

[del(holding(X)), add(ontable(X)),

add(clear(X)), add(handempty)]). move(stack(X, Y), [holding(X), clear(Y)],

[del(holding(X)), del(clear(Y)), add(handempty)

add(on(X, Y)), add(clear(X))]).

Рис. 14.4. Начальные уровни пространства состояний для мира блоков

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

Глава 14. Введение в PROLOG

637

Находим отношение для предиката move.

С помощью операции получения подмножества проверяем, выполняются ли предусловия Preconditions для данного состояния.

Предикат change_state генерирует новое состояние Child_state с исполь­зованием списка добавления и удаления.

С помощью предиката member_stack проверяем, не содержится ли новое со­стояние в списке уже пройденных.

Оператор stack добавляет новое состояние Child_state в стек

New_move_stack.

Оператор stack добавляет исходное состояние name в стек New_been_stack.

С помощью рекурсивного вызова предиката plan на основе дочернего состояния

Child_state и обновленных стеков New_move_stack и Been_stack находится новое состояние.

Для реализации алгоритма требуются дополнительные утилиты, описанные при рассмотрении абстрактных типов данных (стека и множества) в подразделах 14.2.1 и 14.2.4. Естественно, поиск реализуется на основе стеков с помощью алгоритма поиска в глубину с возвратами и завершается после нахождения первого пути к цели. Алгоритмы планиро­вания на основе поиска в ширину и "жадного" алгоритма поиска читателю предлагается реализовать самостоятельно в качестве упражнений.

plan(State, Goal, _, Move_stack) :-

equal_set(State, Goal),

write('переходы'), nl,

reverse_print_stack(Move_stack).

plan(State, Goal, Been_stack, Move_stack) :-

move(Name, Preconditions, Actions),

conditions_met(Preconditions, State),

change_state(State, Actions, Child_state),

not(member_stack(Child_state, Been_stack)),

stack(Name, Been_stack, New_been_stack) ,

stack(Child_state, Move_stack, New_move_stack),

plan(Child_state, Goal, New_been_stack, New_move_stack), !.

plan(_, _, _) :- write(чПри таких переходах план невозможен!').

conditions_met(P, S) :-

subset(P, S),

change_state(S, [ ], S) . change_state(S, [add(P)|T], S_new) :-

change_state(S, T, S2),

add_if_not_in_set(P, S2, S_new), !.

change_state(S, [del(P)|T], S_new) :-

change_state(S, T, S2),

delete_if_in_set(P, S2, S_new), !.

reverse_print_stack(S) :-

empty_stack(S). reverse_print_stack(S) :-

stack(E, Rest, S),

reverse_print_stack(Rest) ,

write(E), nl.

638 Часть VI. Языки и технологии программирования для искусственного интеллекта

И, наконец, выпишем предикат до для инициализации аргументов предиката plan, а так­же предикат test для демонстрации простого метода запуска системы планирования.

go(Start, Goal) :-

empty_stack(Move_stack) ,

empty_stack(Been_stack),

stack(Start, Been_stack, New_been_stack),

plan(Start, Goal, New_been_stack, Move_stack). test :-

go([handempty, ontable(b), ontable(c), on(a, b) , clear(c),

clear(a)],

[handempty, ontable(a), ontable(b), on(c, b), clear(a), clear(c)]).

14.6. Метапредикаты, типы и подстановки унификации

в языке PROLOG

14.6.1. Металогические предикаты

Металогические конструкции позволяют повысить выразительность программирования в любой среде. Такие конструкции будем называть метапредикатами (meta-predicate), поскольку они предназначены для проверки соответствия, формирования за­просов и управления другими предикатами, составляющими спецификацию предметной области задачи. Их можно использовать для рассуждения о предикатах в PROLOG, а не для обозначения термов или объектов, что свойственно обычным предикатам. Метапре­дикаты в языке PROLOG служат для реализации (как минимум) пяти целей.

Определение "типа" выражения.

Добавление ограничений "типа" в логические приложения.

Построение, разделение и оценка структур PROLOG.

Сравнение значений выражений.

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

Выше было описано, как в программу на языке PROLOG можно ввести глобальные структуры, т.е. данные, доступные во всем множестве дизъюнктов. К текущему набору дизъюнкт С можно добавить с помощью команды assert (С).

Использование команд assert и retract связано с некоторой опасностью. По­скольку эти команды создают и удаляют глобальные структуры, они приводят к по­бочным эффектам, которые могут вызвать другие проблемы, присущие плохо структурированным программам. Однако глобальные структуры иногда необходимо исполь­зовать. Это требуется при создании в среде PROLOG семантических сетей (semantic net) и фреймов (frame). Глобальные структуры также можно использовать для описа­ния новых результатов, получаемых с помощью основанной на правилах оболочки. Эта информация должна быть глобальной, чтобы к ней могли получить доступ другие предикаты или правила.

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

Глава 14. Введение в PROLOG 639

var (X) принимает значение "истина" только в том случае, если X - несвязанная

переменная.

nonvar(X) принимает значение "истина" только в том случае, если переменная

X связана с постоянным термом.

= . . создает список из терма предиката.

Например, foo (a, b, c) = .. Y унифицирует Y со списком [ foo, а, Ь, с]. Голова списка Y - это имя функции, а хвост содержит аргументы этой функции. Метапредикат =. . можно также использовать для выполнения обратного действия. Так, если выражение Х=. . [foo, a, b, с] истинно, то значением X является foo(a, b, с).

• functor (A, В, С) принимает значение "истина", если аргумент А - это терм,

главный функтор которого имеет имя В и арность С.

Например, выражение functor (foo (a, b), X, Y) истинно для значений пере­менных X=foo и Y=2. Если один из аргументов метапредаката functor (A, В, С) является связанной переменной, то можно получить значения других переменных, в частности, все термы с заданным именем и/или арностью.

• clause (А, В) унифицирует В с телом дизъюнкта, голова которого унифициро­

вана с аргументом А.

Если в базе данных существует предикат р (X) : - q (X), то clause (p (a) , Y) истинно для Y=q (а). Этот метапредикат полезно использовать для связывания управляющих правил в интерпретаторе.

• any_predicate (..., X, ...) :-Х выполняет предикат X, являющийся

аргументом произвольного предиката.

Так, некоторый предикат X можно передавать в качестве параметра и выполнять в любое удобное время. Предикат call (X), где X - дизъюнкт, тоже завершается успеш­но при выполнении предиката X. Этот краткий список металогических предикатов очень полезен при построении и интерпретации структур данных искусственного интеллекта, описанных в предыдущих главах. Поскольку PROLOG позволяет легко управлять собственными структурами, то несложно реализовать интерпретаторы, модифицирующие се­мантику языка PROLOG. Это и будет сделано ниже.

14.6.2. Типы данных в языке PROLOG

Во многих приложениях неограниченное использование подстановок унификации может привести к возникновению ошибок. PROLOG - это нетипизированный язык. В процессе унификации просто проверяется соответствие шаблонам без всякой их при­вязки к типам данных. Например, значение выражения append (nil, б, 6) выво­дится из определения предиката append. На примере строго типизированных языков наподобие Pascal можно удостовериться в том, что проверка соответствия типов помогает программистам избежать многих проблем. Многие исследователи предлагают ввести понятие типов данных (type) и в язык PROLOG [Neves и др., 1986],

[Mycroft и O'Keefe, 1984].

Типизированные данные особенно полезны для использования в реляционных базах данных [Neves и др., 1986], [Malpas, 1987]. Логические правила можно применять в качест­ве ограничений для этих правил и типизировать их, чтобы обеспечить согласованность и

640

осмысленную интерпретацию запросов. Допустим, в базе данных универмага содержатся отношения inventory (каталог), suppliers (поставщики), supplier_inventory (товар-поставщик) и т.п. Определим базу данных как множество отношений с именованными полями, которые можно рассматривать как наборы кортежей. Например, отношение inventory может состоять из четырехэлементных кортежей, где

6 inventory

только в том случае, если Supplier- это имя поставщика товара с номером Pnumber, именем Pname и весом Weight. Допустим также, что

G suppliers

только в том случае, если Supplier- это имя поставщика с порядковым номером Snumber, статусом Status из города Location, a

e supplier_inventory

только в том случае, если Supplier - это имя поставщика партии с номером Pnumber, стоимостью Cost в отдел Department.

В языке PROLOG можно определить правила, реализующие различные запросы и выполняющие проверку соответствия типов для этих отношений. Например, запрос "располагаются ли поставщики партии товаров № 1 в Лондоне" на языке PROLOG можно представить так.

?- getsuppliers(Supplier, I, london). Правило

getsuppliers(Supplier, Pnumber, City) :-cktype(City, suppliers, city), suppliers(Supplier, _, _,City), cktype(Pnumber, inventory, number), supplier_inventory(Supplier, Pnumber, _, _), cktype(Supplier, inventory, name).

реализует этот запрос и накладывает ограничение на кортежи базы данных. Первые переменные Pnumber и City связываются, если запрос унифицируется с головой правила. Предикат cktype выполняет проверку принадлежности элемента Supplier множеству suppliers, проверку легитимности 1 как инвентарного номера и проверку того, что london - это возможное местоположение поставщика.

Пусть предикат cktype зависит от трех аргументов: значения, имени отношения и имени поля. Допустим, он проверяет соответствие каждого значения типу отношения. Например, можно определить списки допустимых значений для переменных Supplier, Pnumber и City и реализовать типизацию данных с помощью запросов проверки принадлежности предлагаемых значений этим спискам. Кроме того, можно определить логические ограничения на возможные значения в рамках одного типа. Например, можно потребовать, чтобы инвентарные номера не превышали 1000.

Необходимо понимать различия в реализации проверки соответствия типов между стандартными языками наподобие Pascal и языком PROLOG. Для отношения suppliers в языке Pascal можно определить следующий тип данных.

type supplier = record sname: string;

Глава 14. Введение в PROLOG 641

snumber: integer; status: boolean; location: string end

Программист на языке Pascal определяет новые типы (в данном случае supplier) в терминах уже существующих, таких как boolean и integer. Если программист использует переменные этого типа, то компилятор автоматически выполняет проверку соответствия типов.

В PROLOG отношение supplier можно представить в виде

supplier(sname(Supplier), snumber(Snumber), status(Status), location(Location)).

Проверка соответствия типов осуществляется с помощью таких правил, как getsup-pliers и cktype. Различие проверки соответствия типов между языками Pascal и PROLOG очевидно. При объявлении типа в языке Pascal компилятору передается тип данных как всей структуры (record), так и ее отдельных компонентов (boolean, integer, string). При объявлении переменной указывается ее тип (record), а затем создаются процедуры для доступа к этим типизированным структурам.

procedure changestatus (X: supplier); begin

if X.status then. . . .

Поскольку PROLOG - это не процедурный язык, в нем объявление не отделяется от использования типов данных, а проверка соответствия типов осуществляется в процессе выполнения программы. Рассмотрим правило

supplier_name(supplier(sname(Supplier), snumber(Snumber),

status(true), location (london))) :-integer(Snumber), write(Supplier).

Предикат supplier_name получает в качестве аргументов экземпляр предиката Supplier и записывает имя данного поставщика. Однако это правило успешно реализуется только в том случае, если номер поставщика - это целое число, переменная статуса принимает значение true, и поставщик располагается в Лондоне. Важной особенностью проверки соответствия типов является ее реализация с помощью алгоритма унификации (true, london) и встроенного системного предиката integer. Можно ввести ограничение на выбор значений из определенного списка. Например, можно потребовать, чтобы значение переменной Snumber выбиралось из списка номеров поставщиков. Ограничения на запросы к базе данных определяются с помощью правил типа cktype и supplier_name и реализуют проверку соответствия типов в процессе выполнения программы.

Таким образом, мы рассмотрели три способа типизации данных в языке PROLOG. Первый и наиболее мощный состоит в использовании унификации для ограничения возможных значений переменных. Второй способ - применение встроенных предикатов PROLOG для ограниченной проверки соответствия типов. Примерами его реализации являются метапредикаты var(X), clause (X, У) и integer (X). Третий способ - ограниченное использование типизации в рассмотренном примере, где проверка соответствия типов выполняется с помощью правил, определяющих принадлежность значений Supplier, Pnumber и City к заданным спискам.

642 Часть VI. Языки и технологии программирования для искусственного интеллекта

Четвертый, более радикальный, подход - это полная проверка соответствия типов данных и предикатов, предложенная в [Mycroft и O'Keefe, 1984]. В этой работе все имена предикатов связываются с определенным типом и фиксированной арностью. Более того, типизируются и сами имена переменных. Преимущество этого подхода состоит в том, что ограничения на вложенные предикаты и переменные в программе на языке PROLOG определяются самой программой. Несмотря на то что выполнение программы при этом замедляется, такой подход обеспечивает очень высокий уровень безопасности типов.

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

Программист не должен постоянно заботиться о строгой типизации. Он может пи

сать программы, работающие для любых типов объектов. Например, предикат

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

мо от типа элементов списка.

Гибкость типизации помогает разрабатывать программы в новых областях знаний.

Программисты могут абстрагироваться от проверки соответствия типов на ранних

стадиях разработки программы и ввести ее для выявления ошибок при более глу

боком понимании задачи.

Представления данных в области искусственного интеллекта плохо согласуются со

встроенными типами данных таких языков, как Pascal, C++ или Java. PROLOG по

зволяет определять типы с использованием всей мощи логики предикатов. Эта

гибкость хорошо видна на примере с базой данных.

Поскольку проверка соответствия типов осуществляется в процессе выполнения

программы, а не во время компиляции, то программист сам определяет, когда ее

следует начинать. Это позволяет отложить проверку соответствия типов до момен

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

Контроль проверки соответствия типов во время исполнения позволяет писать

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

использовать, например, в программах обучения.

14.6.3. Унификация, механизм проверки соответствия предикатов и оценка

Важная особенность программирования на языке PROLOG состоит в том, что интерпретатор ведет себя как система доказательства теорем на основе резолюции (см. раздел 12.3). Как система доказательства теорем PROLOG выполняет последовательность разрешающих процедур над элементами базы данных, а не оценивает операторы и выражения подобно компиляторам традиционных языков. Это приводит к важному результату: переменные связываются (инстанцируются, принимают значения) с помощью подстановки унификации, а не за счет оценки, если, конечно, оно не требуется явно. Такая парадигма программирования приводит к своеобразным последствиям.

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

Глава 14. Введение в PROLOG 643

части. В разделе 14.9 подстановка унификации также будет рассмотрена как механизм проверки соответствия и обработки ограничений при грамматическом разборе и генерации предложений.

Унификация - это мощное средство экспертных систем, основанных на правилах и фреймах. Разновидность такой проверки соответствия должна присутствовать во всех продукционных системах. Поэтому при написании таких систем на универсальных языках программирования алгоритм унификации зачастую приходится реализовывать вручную (реализация алгоритма унификации на языке LISP приводится в разделе 15.6).

Важное различие между вычислениями на основе унификации и применением более традиционных языков состоит в том, что процедуры унификации выполняют синтаксическую проверку соответствия структур данных (с соответствующими параметрами подстановки). Они не оценивают выражения. Например, предположим, что требуется создать предикат successor, успешно выполняющийся, если его второй аргумент на единицу больше первого. Не понимая сущности унификации, такой предикат можно определить следующим образом.

successor(X, Y):- Y = X + 1.

Он не будет работать, поскольку оператор = не оценивает свои аргументы, а лишь пытается унифицировать выражения в левой и правой части. Этот предикат будет успешно выполнен, если Y можно унифицировать со структурой Х+1. Поскольку 4 не унифицируется с 3 + 1, то вызов successor (3 , 4) завершится неудачно. С другой стороны, с помощью оператора = можно проверять эквивалентность (определяемую путем унификации) любых двух выражений.

Чтобы корректно определить предикат successor и другие арифметические предикаты, необходимо оценивать значения арифметических выражений. В языке PROLOG для этого существует оператор is. Он оценивает выражение в правой части и пытается унифицировать результат с объектом из левой части. Так, в выражении

X is Y + Z

осуществляется унификация объекта X со значением суммы Y и Z. Поскольку при этом выполняются арифметические вычисления, это приводит к таким последствиям.

Если переменные Y и Z не имеют значений (не связаны во время выполнения), то

реализация оператора is приводит к ошибке времени выполнения.

Аналогично, если X и Z - связанные переменные, то с помощью выражения X is Y

+ Z нельзя получить значение Y (как в декларативных языках программирования).

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

жащих арифметические операции +,-,*,/ и mod.

И, наконец, как и в логике предикатов, переменные в языке PROLOG могут иметь одно и только одно связывание. Если в процессе локального присваивания или унификации переменная получила некоторое значение, то она не сможет принять новое значение за исключением случаев возврата в пространстве поиска. Следовательно, is - это не функция, подобная традиционному оператору присваивания. Выражение X is X + 1 всегда ложно.

С помощью оператора is можно корректно определить предикат successor (X, Y). А именно,

successor (X, Y) :-Y is X + 1.

644 Часть VI. Языки и технологии программирования для искусственного интеллекта

Он будет корректно выполняться, если переменная X связана с числовым значением. Его можно использовать либо для вычисления значения Y на основе X, либо для проверки значений X и Y.

?- successor (3, X).

X = 4

yes

?- successor (3, 4).

yes

?- successor (4, 2).

no

?- successor (Y, 4).

failure, error in arithmetic expression

Как следует из этого обсуждения, интерпретатор PROLOG не оценивает выражения подобно тому, как это делается при использовании традиционных языков программирования. Программист должен явно реализовать оценивание с помощью оператора is. Явное управление оценкой, как и в LISP, упрощает обработку выражений (в том числе данных, передаваемых в качестве параметров), а также их создание и модификацию в рамках программы.

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

В завершение обсуждения преимуществ вычислений на основе унификации приведем пример, в котором объединение строк выполняется с помощью разностных списков (difference list). В качестве альтернативы традиционному обозначению списка в PROLOG его можно представить в виде разности двух списков. Например, список [а, Ь] эквивалентен списку [а, b | []]-[] или [а, Ь, с] - [с]. Такое представление имеет несколько преимуществ по сравнению с традиционным синтаксисом списков. Если список [а, Ь] представлен в виде разности [а, Ъ | Y] - Y, то он на самом деле описывает потенциально бесконечный класс всех списков, первыми двумя элементами которых являются а и Ь. Такое представление обладает интересным свойством сложения.

X-Z=X-Y+Y-Z

Это свойство можно использовать для определения следующей однострочной логической программы, в которой X-Y - первый список, Y-Z - второй, a X-Z - результат их конкатенации.

catenate(X -Y, Y-Z, X-Z).

Эта операция объединяет два списка произвольной длины за постоянное время за счет унификации списочных структур, а не за счет повторного присваивания, основанного на длине списков (как при использовании предиката append). Вызов предиката catenate дает следующие результаты.

?- catenate ([a, b|Y]-Y, [1, 2, 3] - [ ], W).

Y = [1, 2, 3]

W = [а, Ь, 1, 2, 3] - [ ]

Как показано на рис. 14.5, значение (поддерево) Y во втором параметре унифицируется с обоими вхождениями Y в первом параметре конкатенации. В этом проявляется сила унификации, которая не сводится к простой подстановке значений переменных. В про-

Глава 14. Введение в PROLOG 645

цессе унификации выполняется проверка соответствия общих структур: все вхождения Y должны принимать значение целого поддерева. Этот пример также иллюстрирует преимущество корректного представления. Таким образом, разностные списки представляют целый класс списков, включая возможные результаты конкатенации.

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

Рис. 14.5. Древовидные диаграммы конкатенации на основе разностных списков

14.7. Метаинтерпретаторы в языке PROLOG

14.7.1. Введение в метаинтерпретаторы: PROLOG в языке PROLOG

Как на Lisp, так и на PROLOG, можно писать программы для работы с выражениями, написанными в рамках синтаксических соглашений языка. Такие программы будем называть метаинтерпретаторами (meta-interpreter). Например, оболочка экспертной системы интерпретирует набор правил и фактов, описывающих конкретную задачу. И хотя правила для задачи описываются с помощью синтаксиса применяемого языка, метаинтерпретатор может переопределять их семантику.

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

solve(true) :- ! .

solve(not A) :- not(solve(A)).

solve((A, B)) :-!, solve(A), solve(B).

solve(A) :- clause(A, B), solve(B).

Допустим, существует следующий простой набор суждений.

р(Х, Y) :- q(X), r(Y).

q(X) :- s(X).

r(X) :- t(X).

s(a) .

646 Часть VI. Языки и технологии программирования для искусственного интеллекта

t(b) .

t(c) .

Тогда предикат solve будет вести себя как интерпретатор PROLOG.

?- solve(р(а, Ь)).

yes

?- solve(p(X, У)).

X = а, У = Ь;

X = а, У = с;

по

?- solve(p(f, g) ) .

по

Предикат solve реализует тот же поиск в глубину слева направо на основе цели, что и интерпретатор PROLOG.

Возможность написания метаинтерпретаторов для языка имеет несколько теоретических преимуществ. Например, в [McCarthy, 1960] описан простой метаинтерпретатор для LISP, представляющий собой часть доказательства того факта, что этот язык является полным (по Тьюрингу). С более практической точки зрения метаинтерпретаторы можно использовать для расширения или модификации семантики базового языка для обеспечения его более полного соответствия специфике приложения. Такая методология программирования получила название металингвистической абстракции (meta-linguistic abstraction), подразумевающей создание высокоуровневого языка для решения конкретных задач.

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

solve(A) :- askuser(A). askuser(A) :- write(A),

write(r? Введите значение true, если целевое утверждение истинно, и false в противном случае'), nl,

read(true).

Поскольку это определение добавляется в конец списка других правил solve, оно вызывается только в том случае, если остальные правила не срабатывают. Предикат solve запускает предикат askuser для передачи пользователю запроса о значении целевого утверждения А. Команда askuser выводит целевое утверждение и инструкции пользователю. Предикат read (true) пытается унифицировать введенное пользователем значение с термом true. Если пользователь ввел значение false (или значение, которое нельзя унифицировать со значением true), то эта попытка завершится неудачей. Таким образом, мы расширили семантику предиката solve и изменили поведение языка PROLOG. Приведем пример использования определенной выше простой базы знаний, иллюстрирующий поведение дополненного предиката solve.

?- solve(p(f, g)).

s(f)? Введите значение true, если целевое утверждение истинно,

и false в противном случае true. t(g)? Введите значение true, если целевое утверждение истинно,

и false в противном случае true.

yes

Глава 14. Введение в PROLOG 647

Следующее расширение метаинтерпретатора позволяет ему отвечать на вопросы "Почему?". Если интерпретатор задает пользователю вопрос, то пользователь может ответить ему встречным вопросом why (почему). Ответом на этот запрос должно служить текущее правило, которое пытается разрешить программа. Это реализуется за счет хранения стека правил в текущей строке рассуждений в качестве второго параметра предиката solve. При каждом вызове команды clause для обратной связи с целевым утверждением предикат solve помещает выбранное правило в стек. Тогда в стеке будет записана вся цепочка правил, начиная от цели наивысшего уровня и заканчивая текущей подцелью.

Поскольку пользователь теперь может вводить два корректных ответа на запрос, предикат askuser вызывает предикат respond, который либо завершается успешно при вводе пользователем значения true (как было описано выше), либо записывает последнее правило в стек, если пользователь вводит ответ why. Предикаты respond и askuser являются взаимно рекурсивными, поскольку после вывода ответа на запрос why предикат respond вызывает askuser для вывода следующего запроса пользователю о значении целевого утверждения. Заметим, однако, что на этот раз при вызове askuser его параметром является хвост стека правил. Таким образом, последовательность запросов why просто приводит к последовательному извлечению правил из стека до его опорожнения. Это позволяет пользователю отследить всю цепочку рассуждений.

solve(true, _) :-!.

solve(not(A), Rules) :- not(solve(A, Rules)).

solve((A, B), Rules) :- !, solve(A, Rules), solve(B, Rules).

solve(A, Rules) :- clause(A, B), solve(B, [(A :- B)|Rules]).

solve(A, Rules) :- askuser(A, Rules).

askuser(A, Rules) :- write(A),

write("? Введите значение true, если целевое утверждение истинно, и false в противном случае'), nl,

read(Answer), respond(Answer, A, Rules). respond(true, _, _). respond(why, A, [Rule|Rules]) :- write(Rule), nl,

askuser(A, Rules). respond(why, A, [ ]) :- askuser(A, [ ]).

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

?- solve(p(f, g), [ ]).

s(f)? Введите значение true, если целевое утверждение истинно,

и false в противном случае why.

q(f) :- S(f) s(f)? Введите значение true, если целевое утверждение истинно,

и false в противном случае why.

p(f, g) :- (q(f), r(g)) s(f)? Введите значение true, если целевое утверждение истинно,

и false в противном случае true. t(g)? Введите значение true, если целевое утверждение истинно,

и false в противном случае true, yes

648 Часть VI. Языки и технологии программирования для искусственного интеллекта

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

Обычный интерпретатор PROLOG можно модифицировать за счет рекурсивного построения дерева доказательства для целевого утверждения в случае успешного разрешения цели. В следующем определении дерево доказательства возвращается в качестве второго параметра предиката solve. Доказательством атомарного утверждения true является само это утверждение. Такое свойство приводит к построению рекурсии. При разрешении цели А с помощью правила А : -В можно построить доказательство В и возвратить структуру (А : - Proof В). При разрешении конъюнкции целей А и В можно просто объединить деревья доказательств для обеих целей: (Proof A, Proof В).

Определение метаинтерпретатора, обеспечивающего построение деревьев доказательств, имеет следующий вид.

solve(true, true) :-!.

solve(not(A), not ProofA) :- not(solve(A, ProofA)).

solve((A, B),(ProofA, ProofB)) :- solve(A, ProofA), solve(B,

ProofB).

solve(A, (A :- ProofB)) :- clause(A, B), solve(B, ProofB).

solve(A, (A :- given)) :- askuser(A).

askuser(A, Proof) :- write(A),

write('Введите значение true, если целевое утверждение истинно, и false в противном случае'), read(true).

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

?- solve(p(a, b), Proof). Proof = p(a, b) :-((q(a) :-s(a) :-

true)), (r(b) :-

(t(b) :-

true)))

В следующем разделе эти приемы используются для реализации оболочки экспертной системы exshell. В ней база знаний используется в форме правил решения задачи. Система запрашивает у пользователя необходимую информацию, записывает специфические данные, отвечает на запросы how и why и реализует механизм неточных рассуждений на основе фактора уверенности из главы 8. И хотя система exshell гораздо сложнее описанных выше метаинтерпретаторов PROLOG, она является лишь расширением этой методологии. Ее ядром служит предикат solve, реализующий обратный поиск цепочек правил и фактов.

14.7.2. Оболочка для экспертной системы на основе правил

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

Глава 14. Введение в PROLOG 649

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

База знаний оболочки exshell состоит из правил и спецификаций запросов к пользователю. Правила представляются с помощью предиката rule вида rule(R, CF). Первый параметр - это утверждение для базы знаний, записанное с помощью стандартного синтаксиса PROLOG. Утверждения могут представлять собой правила PROLOG вида (G : - Р), где G - это голова правила, а Р - конъюнктивный шаблон, при котором правило G истинно. Первый параметр предиката rule может также являться фактом PROLOG. Параметр CF характеризует степень доверия разработчика заключению правила. Система exshell реализует механизм неточных рассуждений на основе фактора уверенности, предложенный для системы MYCIN, описанной в главе 8. Параметр CF может изменяться в диапазоне от 100 (если факт заведомо истинный) до -100 (для заведомо ложных фактов). Если значение параметра CF близко к нулю, значит, степень уверенности для данного факта неизвестна. Приведем типичное правило из базы знаний для диагностики неисправностей автомобилей.

rule((bad_component(starter) :- (bad_system(starter_system),

lights(come_on))), 50). rule(fix(starter, 'замените стартер'), 100).

Первое правило утверждает следующее. Если "неисправной" оказалась система стартера, и фары включаются, значит, плохим компонентом является стартер с фактором уверенности 50. Второе утверждение означает, что починить неисправный стартер можно путем его замены (с уверенностью 100). В оболочке exshell предикат rule используется для извлечения правил, дающих заключение для указанной цели, подобно тому, как в более простой версии предиката solve используется встроенный предикат clause для извлечения правил из глобальной базы данных PROLOG.

Система exshell поддерживает запросы к пользователям о неизвестных данных. Однако, поскольку интерпретатор не должен задавать вопросы для каждой неразрешенной цели, программист может явно указать, какую информацию следует получить. Это можно сделать с помощью предиката askable.

askable(car_starts).

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

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

Ядром метаинтерпретатора exshell является предикат solve, зависящий от четырех аргументов. Первый аргумент - это целевое утверждение, которое требуется разрешить. При успешном разрешении цели оболочка exshell связывает второй аргумент со степенью уверенности, вычисляемой на основе базы знаний. Третий аргумент - это стек правил, применяемый для ответов на запросы why, а четвертый - порог отсечения для метода неточных рассуждений на основе фактора уверенности. Такой подход позволяет ограничивать пространство поиска, если значение фактора уверенности (степень достоверности) опускается ниже заданного порога.

650 Часть VI. Языки и технологии программирования для искусственного интеллекта

При разрешении цели G предикат solve сначала пытается выявить соответствие цели G любому факту, уже полученному от пользователя. Известные факты представляются с помощью предиката known (A, CF). Например, known (car_starts, 85) означает, что пользователь уже сообщил о том, что автомобиль запускается со степенью достоверности 85. Если значение целевого утверждения неизвестно, предикат solve пытается разрешить его с помощью базы знаний. Он обрабатывает отрицание цели, разрешая ее и умножая достоверность этой цели на -1. При этом разрешение конъюнктивных целей производится слева направо. Если G - это положительный литерал, то предикат solve проверяет все правила, голова которых соответствует G. В случае неудачного завершения этой операции solve передает запрос пользователю. При получении от пользователя значения достоверности цели предикат solve добавляет эту информацию в базу данных с помощью предиката known.

% Ситуация 1: истинное значение целевого утверждения уже известно solve(Goal, CF, _, Threshold) :-

known(Goal, CF), ! ,

above_threshold(CF, Threshold). %Проверка порога достоверности % Ситуация 2: отрицание цели solve(not(Goal), CF, Rules, Threshold) :-!,

invert_threshold(Threshold, New_threshold),

solve(Goal, CF_goal, Rules, New_threshold),

negate_cf(CF_goal, CF). % Ситуация З: конъюнктивные цели solve((Goal_l, Goal_2), CF, Rules, Threshold) :- !,

solve(Goal_l, CF_1, Rules, Threshold),

above_threshold(CF_l, Threshold),

solve(Goal_2, CF_2, Rules, Threshold),

above_threshold(CF_2, Threshold),

and_cf (CF_1, CF_2, CF) . %Вычисление CF для конъюнкции целей % Ситуация 4: обратная связь с правилом в базе знаний solve(Goal, CF, Rules, Threshold) :-

rule((Goal :- (Premise)), CF_rule),

solve(Premise, CF_premise, [rule((Goal :- Premise), CF_rule) |Rules], Threshold) ,

rule_cf(CF_rule, CF_premise, CF),

above_threshold(CF, Threshold). % Ситуация 5: добавлени факта в базу знаний solve(Goal, CF, _, Threshold) :-

rule(Goal, CF),

above_threshold(CF, Threshold). % Ситуация 6: запрос к пользователю solve(Goal, CF, Rules, Threshold) :-

askable(Goal),

askuser(Goal, CF, Rules), !,

assert(known(Goal, CF)) ,

above_threshold(CF, Threshold).

Консультации с пользователем начинаются с помощью версии предиката solve с двумя параметрами. Первый аргумент - это цель верхнего уровня в базе знаний, а второй - переменная, которая будет связана с фактором уверенности в цели после анализа базы знаний. Этот предикат выводит набор инструкций пользователю, вызывает команду retractall (known (_, _) ) для очистки любой остаточной информации от преды-

Глава 14. Введение в PROLOG 651

дущих запусков оболочки exshell, а затем вызывает предикат solve с соответствующими значениями четырех параметров.

solve(Goal, CF) :-print_instructions, retractall(known(_, _)), solve(Goal, CF, [ ], 20), %Порог 20

Команда print_instructions сообщает пользователю список допустимых ответов на запрос exshell.

print_instructions :-

nl, write("Возможные ответы: '),

nl, write('Фактор уверенности в истинности запроса. '),

nl, write(' Число от -100 до 100. '),

nl, write(ч why. '),

nl, write(' how(X), где X - это целевое утверждение'), nl.

Следующий набор предикатов позволяет вычислить коэффициенты достоверности. (В оболочке exshell используется разновидность метода неточных рассуждений на основе фактора уверенности, представленного в подразделе 8.2.1.) Фактор уверенности для конъюнкции двух целей - это минимум среди факторов уверенности каждой из целей. Фактор уверенности для отрицания факта вычисляется путем умножения фактора уверенности этого факта на -1. Степень уверенности в гипотезе, полученной с помощью правила, равна произведению факторов уверенности предпосылок и самого этого правила. Предикат above_threshold определяет, превышает ли значение фактора уверенности заданный порог. В системе exshell пороговое значение используется для отсечения цели, если уверенность в ней слишком низка. Заметим, что предикат above_threshold отдельно определяется для отрицательных и положительных значений порога. При положительном значении порога отсечение выполняется в том случае, если фактор уверенности не превышает этого порога. Отрицательное значение порога означает, что мы пытаемся доказать ложность цели. Поэтому для отрицательных целей поиск прерывается, если значение фактора уверенности цели превышает заданный порог. Команда invert_threshold вызывается для умножения значения порога на -1.

and_cf(A, В, А) :-

А = < В. and_cf(A, В, В) :-

В < А. negate_cf(CF, Negated_CF) :-

Negated_CF is - 1 * CF. rule_cf(CF_rule, CF_premise, CF) :-

CF is (CF_rule * CF_premise/100). above_threshold(CF, T) :-

T >= 0, CF >= T. above_threshold(CF, T) :-

T < 0, CF =< T. invert_threshold(Threshold, New_threshold) :-

New_threshold is -1 * Threshold.

Предикат askuser выводит запрос и считывает ответ пользователя. Предикаты respond выполняют действия, соответствующие введенной пользователем информации.

652 Часть VI. Языки и технологии программирования для искусственного интеллекта

askuser(Goal, CF, Rules) :- %3апрашивает ответ пользователя

в отношении цели

nl, write(* Запрос к пользователю: '),

write(Goal), nl, write(>?'),

read(Answer) ,

respond(Answer, Goal, CF, Rules). %Обрабатывает ответ

В качестве ответа на запрос пользователь может ввести значение параметра CF из диапазона от -100 до 100, отражающее степень его доверия истинности цели, запрос why или how (X).

Ответом на запрос why является правило, расположенное в данный момент в верхушке стека. Как и в предыдущей реализации, успешная обработка запросов why приводит к последовательному извлечению правил из стека. Это позволяет восстановить всю цепочку рассуждений. Если ответ пользователя соответствует шаблону how(X), то предикат respond вызывает команду build_proof для построения дерева доказательства для X и команду write_proof для вывода этого доказательства в удобной для восприятия форме. Все неизвестные входные значения "отлавливаются" предикатом respond.

% Ситуация 1: пользователь вводит корректный фактор уверенности respond(CF, _, CF, _) :-

number(CF),

CF =< 100, CF >= -100.

% Ситуация 2: пользователь вводит запрос why respond(why. Goal, CF, [Rule|Rules]) :-

write_rule(Rule),

askuser(Goal, CF, Rules), respond(why, Goal, CF, [ ]) :-

write(* Перейти к вершине стека правил. '),

askuser(Goal, CF, [ ]).

% Ситуация 3: Пользователь вводит запрос how. % Строится и выводится доказательство respond(how(X), Goal, CF, Rules) :-

build_proof(X, CF_X, Proof), !,

write(X), write('заключение получено с уверенностью '),

write(CF_X),nl, nl,

write('Доказательство '), nl, nl,

write_proof(Proof, 0), nl, nl,

askuser(Goal, CF, Rules).

% пользователь вводит запрос how, доказательство построить нельзя respond(how(X), Goal, CF, Rules) :-

write('Истинность '), write(X), nl,

write(*еще неизвестна. '), nl,

askuser(Goal, CF, Rules). % Ситуация 4: неизвестный ввод respond(_, Goal, CF, Rules) :-

write('Неизвестный отклик.'), nl,

askuser(Goal, CF, Rules).

Определение предиката build_proof почти полностью соответствует определению предиката solve с четырьмя параметрами. Однако build_proof не спрашивает пользователя о неизвестных фактах, поскольку они уже сохранены среди данных, соответствующих определенным ситуациям. Предикат build_proof строит дерево доказательства цели.

Глава 14. Введение в PROLOG 653

build_proof(Goal, CF, (Goal, CF :- given)) :-

known(Goal, CF), !. build_proof(not Goal, CF, not Proof) :-

!, build_proof(Goal, CF_goal, Proof), negate_cf(CF_goal, CF). build_proof((Goal_l, Goal_2), CF, (Proof_l, Proof_2)) :-

!, build_proof(Goal_l, CF_1, Proof_l),

build_proof(Goal_2, CF_2, Proof_2), and_cf(CF_l, CF_2, CF). build_proof(Goal, CF, (Goal, CF :- Proof)) :-

rule((Goal :- Premise), CF_rule),

build_proof(Premise, CF_premise, Proof),

rule_cf(CF_rule, CF_premise, CF),

build_proof(Goal, CF, (Goal, CF :- fact)) :-

rule(Goal, CF).

И, наконец, создадим предикаты, определяющие простой интерфейс пользователя. Как правило, для его написания требуются огромные объемы кода. Сначала определим предикат вывода правила в удобном для восприятия формате.

write_rule(rule((Goal :- (Premise)), CF)) :-

write(Goal), write(':-'), nl,

write_premise(Premise), nl,

write("CF = '), write(CF), nl. write_rule(rule(Goal, CF)) :-

write(Goal), nl,

write(4CF = '), write(CF), nl.

Тогда предикат write_premise записывает конъюнкты из предусловий правила.

write_premise((Premise_l, Premise_2)) :-

!, write_premise(Premise_l),

write_premise(Premise_2). write_premise(not Premise)

!, write(v '), write(not), write(' '), write(Premise), nl. write_premise(Premise) :-

write(% '), write(Premise), nl.

Команда write_proof выводит доказательство с отображением структуры дерева.

write_proof((Goal, CF :- given), Level) :- %Выводит дерево

%доказательства

indent(Level), write(Goal), %c указанием уровней

write(' CF= '), write(CF),

write(* получено от пользователя'), nl, !. write_proof((Goal, CF :- fact). Level) :-

indent(Level), write(Goal), write(v CF = '), write(CF),

write(ч факт из базы знаний'), nl, !. write_proof((Goal, CF :- Proof), Level) :-

indent(Level), write(Goal), write(" CF = '), write(CF),

write(' : - ') ,

nl, New_level is Level + 1, write_proof(Proof, New_level), !. write_proof(not Proof, Level) :-

indent(Level), write((not)), nl,

New_level is Level + 1, write_proof(Proof, New_level), !. write_proof((Proof_1, Proof_2), Level) :-

write_proof(Proof_1, Level), write_proof(Proof_2, Level), !. indent(0).

654 Часть VI. Языки и технологии программирования для искусственного интеллекта

indent(1) : -

write!1 '), l_new is 1-1, indent(l_new).

Для иллюстрации работы оболочки exshell рассмотрим следующую простую базу знаний для диагностики неисправностей автомобилей. Целью верхнего уровня является утверждение fix, зависящее от одного параметра. С помощью базы знаний решение задачи разбивается на поиск неисправной системы, поиск неисправного компонента в рамках этой системы и построение совета по решению проблемы на основе поставленного диагноза. Заметим, что база знаний является неполной, т.е. существует множество симптомов, которые невозможно диагностировать. В этом случае программа exshell попросту не работает. Расширение базы знаний на некоторые из этих случаев и добавление правил, срабатывающих при неприменимости остальных правил, - это интересная задача, которую читатель может решить в качестве упражнения.

rule((fix(Advice) :- %3апрос верхнего уровня

(bad_component(X), fix(X,Advice))), 100). rule((bad_component(starter) : -

(bad_system(starter_system), lights(come_on))), 50). rule((bad_component(battery) :-

(bad_system(starter_system), not lights(come_on))), 90). rule((bad_component(timing) :-

(bad_system(ignition_system), not tuned_recently)), 80). rule((bad_component(plugs) :-

(bad_system(ignition_system), plugs(dirty))), 90). rule((bad_component(ignition_wires) :-

(bad_system(ignition_system), not plugs(dirty), tuned_recently)), 80). rule((bad_system(starter_system) :-

(not car_starts, not turns_over)), 90). rule((bad_system(ignition_system) :-

(not car_starts, turns_over, gas_in_carb)), 80). rule((bad_system(ignition_system) :-

(runs(rough), gas_in_carb)), 80). rule((bad_system(ignition_system) :-

(car_starts, runs(dies), gas_in_carb)), 60). rule(fix(starter, 'заменить стартер'), 100).

%Совет по устранению проблемы

rule(fix(battery, 'заменить или зарядить аккумулятор'), 100). rule(fix(timing, "настроить временные параметры'), 100). rule(fix(plugs, 'заменить свечи зажигания'), 100). rule(fix(ignition_wires, "проверить провода в системе зажигания'),

100) .

askable(car_starts). %Можно спросить пользователя о цели

askable(turns_over). askable(lights(_)). askable(runs(_)). askable(gas_in_carb). askable(tuned_recently) . askable(plugs(_)).

Глава 14. Введение в PROLOG 655

Теперь воспользуемся этой базой знаний в работе системы exshell. На рис. 14.6 показано пространство поиска. Сплошной линией обозначены пройденные участки, пунктирной - непройденные, а жирной - решения.

Рис. 14.6. Граф поиска для системы диагностики неисправностей автомобилей. Пунктирные линии обозначают непройденные ветви, а жирные - окончательное решение

?- solve(fix(X), CF). Возможные ответы:

Фактор уверенности в истинности запроса. Число от -100 до 100.

why.

how(X), где X - это целевое утверждение Запрос к пользователю:car_starts ? -100.

Запрос к пользователю:turns_over ? 85.

Запрос к пользователю:gas_in_carb ? 75.

Запрос к пользователю:tuned_recently ? -90.

X = 'настроить временные параметры' CF = 48.0

Теперь рассмотрим ситуацию, при которой в этой же задаче используются запросы how и why. Сравните ответы с соответствующими поддеревьями и путями, показанными на рис. 14.6.

?- solve(fix(X), CF).

Возможные ответы:

Фактор уверенности в истинности запроса.

Число от -100 до 100. why.

656 Часть VI. Языки и технологии программирования для искусственного интеллекта