Язык логического программирования Visual Prolog
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
нается с вершины программы.
Пытаясь согласовать первую подцель, Visual Prolog (начиная с вершины) производит сопоставление с каждым фактом или заголовком правила, встреченным в программе.
Он обнаруживает соответствие с запросом у первого же факта, представляющего отношение food. Таким образом, переменная X связывается со значением brussels_sprouts. Поскольку существует более чем один возможный ответ на обращение food(X), Visual Prolog ставит точку возврата (маркер) возле факта food(brussels_sprouts). Эта точка поиска с возвратом указывает на то место, откуда Пролог начнет поиск следующего возможного соответствия для food(X).
Когда установление соответствия обращения завершается успешно, говорят, что обращение возвращается, и может быть испытана очередная подцель.
Поскольку переменная X связана с brussels_sprouts, следующее обращение будет выполняться так:
tastes(brussels_sprouts, good)
и Visual Prolog вновь начнет поиск с вершины программы, пытаясь согласовать это вращение. Поскольку соответствующих предложений не обнаруживается, обращение завершается неудачно, и теперь Visual Prolog запускает механизм возврата. Начиная поиск с возвратом, Пролог отступает к последней позиции, где была уставлена точка отката. В данном случае Пролог возвращается к факту
food(brussels_sprouts).
Единственным способом освободить переменную, однажды связанную в предложении, является откат при поиске с возвратом.
Когда Пролог отступает к точке поиска с возвратом, он освобождает все переменные, связанные после этой точки, и будет искать другое решение для исходного обращения.
Обращение было food(X), так что связанность brussels_sprouts с X отменена. Теперь Пролог пытается заново произвести решение для этого обращения. Он обнаруживает соответствие с фактом food (pizza); на этот раз переменная X связывается со значением pizza.
Пролог переходит к следующей подцели в правиле, имея при этом новую связанную переменную. Производится новое обращение, tastes (pizza, good), и начинается поиск (опять от вершины программы). На этот раз соответствие найдено, и целевое утверждение успешно выполняется.
Поскольку переменная what в целевом утверждении унифицирована с переменной X в правиле likes, а переменная X связана со значением pizza, переменная What отныне связана со значением pizza и Visual Prolog сообщает решение:
What=pizza
1 Solution
3. Управление поиском решений
Встроенный механизм поиска с возвратом в Прологе может привести к поиску ненужных решений, в результате чего теряется эффективность, например, когда желательно найти только одно решение. В других случаях может оказаться необходимым продолжать поиск дополнительных решений, даже если целевое утверждение уже согласовано.
Visual Prolog обеспечивает два инструментальных средства, которые дают возможность управлять механизмом поиска с возвратом: предикат fail, который используется для инициализации поиска с возвратом, и cut или отсечение (обозначается !) для запрета возможности возврата.
Использование предиката fail
Visual Prolog начинает поиск с возвратом, когда вызов завершается неудачно. В определенных ситуациях бывает необходимо инициализировать выполнение поиска с возвратом, чтобы найти другие решения. Visual Prolog поддерживает специальный предикат fail, вызывающий неуспешное завершение, и, следовательно, инициализирует возврат. Действие предиката fail равносильно эффекту от сравнения 2=3 или другой невозможной подцели. Программа ch04e06.pro (рис. 3) иллюстрирует использование этого специального предиката.
domains
name = symbol
predicates
father(name, name)
everybody
clauses
father(leonard,katherine).
father (carl, jason).
father (carl,marilyn)
everybody:-
father (X,Y),
write(X," is ",Y,"s father\n"), fail.
- Программа ch04e06.pro
Пусть необходимо найти все решения цели father (X,Y). Используя утилиту Test Goal, можно записать цель как
goal
father(X,Y).
Test Goal найдет все решения цели father (X,Y) и отобразит значения всех переменных следующим образом:
X=leonard, Y=katherine
X=carl, Y=jason
X=carl, Y=marilyn
3 Solutions
Но если вы скомпилируете эту программу и запустите ее, то Visual Prolog найдет только первое подходящее решение для father (X,Y). После того как целевое утверждение, определенное в разделе goal, выполнено впервые, ничто не говорит Прологу о необходимости продолжения поиска с возвратом. Поэтому обращение к father приведет только к одному решению. Как же найти все возможные решения? Предикат everybody в программе ch04e06.pro использует fail для поддержки поиска с возвратом.
Задача предиката everybody найти все решения для father и выдать полный ответ. Сравните предыдущие ответы утилиты Test Goal с целью father(X,Y) и ответы на выполнение следующей цели:
goal
everybody.
отображенные сгенерированной программой:
leonard is katherine s father
carl is Jasons father
carl is marilyns father
Предикат everybody использует поиск с возвратом с тем, чтобы получить все решения для father (X, Y), заставляя Пролог выполнять поиск с возвратом сквозь тело правила everybody:
father (X, Y),
mite(X," is ",Y, "s father\n"),
fail.
fail не может быть согласован (он всегда неуспешен), поэтому Visual Prolog вынужден повторять поиск с возвратом. При поиске с возвратом он возвращается к последнему обращению, которое может произвести множественные решения. Такое обращение называют недетерминированным. Недетерминированное обращение является противоположностью детерминированному обращению, которое может произвести только одно решение.
Предикат write не может быть вновь согласован (он не может предложить новых решений), поэтому Visual Pr