 |
Предотвращение поиска с возвратом к предыдущей подцели в правиле
|
|
|
|
r1:- а,b,
!,
c.
Такая запись является способом сообщить Visual Prolog о том, что вас удовлетворит первое решение, найденное им для подцелей а и b. Имея возможность найти множественные решения при обращении к с путем поиска с возвратом, Пролог при этом не может произвести откат (поиск с возвратом) через отсечение и найти альтернативное решение для обращений а и b. Он также не может возвратиться к другому предложению, определяющему предикат rl.
В качестве конкретного примера рассмотрим программу ch04e07.pro (рис. 4).
predicates
buy_car(symbol,symbol)
car (symbol,symbol,integer)
colors(symbol,symbol)
clauses
buy_car(Model,Color):-
car(Model,Color,Price),
colors(Color,sexy),
!,
Price < 25000.
car(maserati,green,25000).
car(corvette,black,24000).
car(corvette,red,26000).
car(porsche,red,24000).
colors(red,sexy).
colors(black,mean).
colors(green,preppy).
goal
buy_car(corvette,Y).
Рис. 4. Рис. 4. Программа ch04e07.pro
В данном примере поставлена цель: найти corvette (Корвет) приятного цвета, подходящий по стоимости. Отсечение в правиле buy_car означает, что поскольку в базе данных содержится только один "Корвет" приятного цвета, хоть и со слишком высокой ценой, то нет нужды искать другую машину. Получив целевое утверждение
buy_car(corvette, Y)
программа отработает следующие шаги:
1. Visual Prolog обращается к саг, первой подцели для предиката buy_car.
2. Выполняет проверку для первой машины, maserati, которая завершается неудачно.
3. Затем проверяет следующее предложение саг и находит соответствие, связывая переменную Color со значением black.
4. Переходит к следующему обращению и проверяет, имеет ли выбранная машина приятный цвет. Черный цвет не является приятным в данной программе, таким образом, проверка завершается неудачно.
5. Выполняет поиск с возвратом к обращению саг и снова ищет corvette, удовлетворяющий этому критерию.
|
|
|
6. Находит соответствие и снова проверяет цвет. На этот раз цвет оказывается приятным, и Visual Prolog переходит к следующей подцели в правиле: к отсечению. Отсечение немедленно выполняется, "замораживая" все переменные, ранее связанные в этом предложении.
7. Переходит к следующей (и последней) подцели в правиле, к сравнению
Price < 25000.
8. Проверка завершается неудачно, и Visual Prolog пытается совершить поиск с возвратом с целью найти другую машину для проверки. Отсечение предотвращает попытку решить последнюю подцель, и наше целевое утверждение завершается неудачно.
Предотвращение поиска с возвратом к следующему предложению
Отсечение может быть использовано, как способ сообщить Visual Prolog, что он выбрал верное предложение для определенного предиката. Например, рассмотрим следующий фрагмент:
r(1):-
!,
а, b, с.
r(2):-
!,
d.
r(3):-
!,
с.
r(_):-
write("This is a catchall clause.").
Использование отсечения делает предикат r детерминированным. В данном случае Visual Prolog выполняет обращение к r с единственным целым аргументом. Предположим, что произведено обращение r(l). Visual Prolog просматривает программу в поисках соответствия для обращения; он находит его с первым предложением, определяющим r. Поскольку имеется более чем одно возможное решение для данного обращения, Visual Prolog проставляет точку возврата около этого предложения.
Теперь Visual Prolog начинает обработку тела правила, проходит через отсечение и исключает возможность возвращения к другому предложению r. Это отменяет точки поиска с возвратом, повышая эффективность выполнения программы, а также гарантирует, что отлавливающее ошибки предложение будет выполнено лишь в том случае, если ни одно из условий не будет соответствовать обращению к r.
Обратите внимание, что конструкция такого типа весьма похожа на конструкцию case в других языках программирования; условие проверки записывается в заголовке правил. По возможности, всегда следует помещать проверочное условие именно в заголовок правила, — это повышает эффективность программы и упрощает ее чтение.
|
|
|
Детерминизм и отсечение
Если бы предикат r, определенный в предыдущей программе, не содержал отсечений, то это был бы недетерминированный предикат (способный производить множественные решения при помощи поиска с возвратом). В предыдущих реализациях Пролога программисты должны были обращать особое внимание на недетерминированные предложения из-за сопутствующих им дополнительных требований к ресурсам памяти. Теперь Visual Prolog сам выполняет проверку на недетерминированные предложения, облегчая вашу работу.
В Прологе существует директива компилятора check_determ. Если вставить эту директиву в самое начало программы, то Visual Prolog будет выдавать предупреждение в случае обнаружения недетерминированных предложений в процессе компиляции.
Можно превратить недетерминированные предложения в детерминированные, вставляя отсечения в тело правил, определяющих данный предикат.
Предикат not
Следующая программа ch04el0.pro (рис. 5.) демонстрирует, как вы можете использовать предикат not для того, чтобы выявить успевающего студента: студента, у которого средний балл (GPA) не менее 3.5 и у которого в настоящее время не продолжается испытательный срок.
domains
name = symbol
gpa = real
predicates
honor_student(name)
student(name, gра)
probation(name)
clauses
honor_student (Name):-
student(Name, GPA),
GPA>=3.5,
not(probation(Name)).
student ("Betty Blue", 3.5).
student ("David Smith", 2.0).
student ("John Johnson", 3.7).
probation ("Betty Blue").
probation ("David Smith").
goal
honor_student (X).
Рис. 5. Программа ch04e10.pro
При использовании предиката not необходимо иметь в виду следующее:
Предикат not будет успешным, если не может быть доказана истинность данной подцели.
Это приводит к предотвращению связывания внутри not несвязанных переменных. При вызове изнутри not подцели со свободными переменными, Visual Prolog возвратит сообщение об ошибке: "Free variables not allowed in not or retractall" (Свободные переменные не разрешены в not или retract). Это происходит вследствие того, что для связывания свободных переменных в подцели, подцель должна унифицироваться с каким-либо другим предложением и выполняться. Правильным способом управления несвязанными переменными подцели внутри not является использование анонимных переменных.
|
|
|
Первый пример работает правильно:
likes (bill, Anyone):-% Anyone — выходной аргумент
likes(sue, Anyone),
not(hates(bill, Anyone).
В этом примере Anyone связывается посредством likes (sue, Anyone) до того, как Visual Prolog делает вывод, что hates (bill, Anyone) не является истиной. Данное предложение работает корректно.
Если пример изменить таким образом, что обращение к not будет выполняться первым, то получите сообщение об ошибке: "Free variable are not allowed in not" (Свободные переменные в not не разрешены).
likes(bill, Anyone):-% Это не будет работать правильно
not(hates(bill, Anyone)),
likes(sue, Anyone).
Даже если вы замените в not (hates (bill, Anyone)) Anyone на анонимную переменную, и предложение, таким образом, не будет возвращать ошибку, все равно получите неправильный результат.
likes(bill, Anyone):- % Это не будет работать правильно
not(hates(bill, _)),
likes(sue, Anyone).
Это предложение утверждает, что Биллу нравится кто угодно, если неизвестно ничего о том, кого Билл ненавидит, и если этот "кто-то" нравится Сью. Подлинное предложение утверждало, что Биллу нравится тот, кто нравится Сью, и при этом Билл не испытывает к этому человеку ненависти.
Неверное использование предиката not приведет к сообщению об ошибке или к ошибкам в логике вашей программы.Простые и составные объекты
До сих пор мы работали только основными видами объектов данных Visual Prolog, таких как числа, идентификаторы и строки. Visual Prolog может создавать не только простые, но и составные типы.
Простые объекты данных
Простой объект данных — это переменная или константа. Не путайте это значение слова "константа" с символьными константами, которые вы определяете в разделе constants программы. То, что мы здесь называем константой, это нечто, идентифицирующее объект, который нельзя изменять: символ (char), число (integer или real) или атом (symbol или string).
Константы включают числа, символы и атомы. Числа и символы были рассмотрены ранее.
Атомы имеют тип идентификатор (symbol) или строка (string). Отличие между ними — главным образом вопрос машинного представления и реализации, и, в основном, оно синтаксически не заметно. Когда атом передается в качестве аргумента при вызове предиката, то к какому домену принадлежит атом — symbol или string -определяется по тому, как описан этот аргумент в декларации предиката.
|
|
|
Visual Prolog автоматически преобразует типы между доменами string и symbol, поэтому вы можете использовать атомы symbol в доменах string и наоборот. Однако принято считать, что объект в двойных кавычках принадлежит домену string, а объект, не нуждающийся в кавычках, домену symbol. Атомы типа symbol — это имена, начинающиеся со строчной буквы и содержащие только буквы, цифры и знак подчеркивания.
Атомы типа string выделяются двойными кавычками и могут содержать любую комбинацию литер, кроме ASCII-нуля (0, бинарный нуль), который обозначает конец строки атома.
Примеры строк и идентификаторов приведены в табл. 1.
Таблица 2. Строки и идентификаторы
| Атомы-идентификаторы | Атомы-строки |
| food | "Jesse James" |
| rick_Jones_2nd | "123 Pike street" |
| fred_Flintstone_1000_Bс_Bedrock | "jon" |
| a | "a" |
| new_york | "New York" |
| pdcProlog | "Visual Prolog, by Prolog Development Center" |
Так как string/symbol взаимозаменяемы, их отличие не существенно. Однако имена предикатов и функторы для составных объектов должны соответствовать синтаксическим соглашениям домена symbol.
|
|
|
