Выполнение запроса и механизм поиска
- Правила программы:
parent(alice,bob).
parent(bob,carol).
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).
- При запросе ancestor(alice,carol) Prolog использует поиск в глубину, слева-направо (SLD): он берёт сначала первый клаузул для ancestor и пытается доказать его тело, затем — если не получится — переходит ко второму клаузулу.
1. Пробует первый клаузул ancestor(X,Y) :- parent(X,Y). Сопоставляет $X=alice,Y=carol$ и проверяет parent(alice,carol) — это не факт, попытка неудачна.
2. Переходит ко второму клаузулу ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y). Сопоставляет $X=alice,Y=carol$ и пытается доказать первый литерал parent(alice,Z). Он успешен с $Z=bob$.
3. Теперь нужно доказать ancestor(bob,carol). Для этого сначала проверяется parent(bob,carol) — факт есть, значит ancestor(bob,carol) истинно и следовательно ancestor(alice,carol) успешно доказывается.
- Особенность механизма: Prolog создаёт точки выбора (choice points) при наличии нескольких подходящих клаузул или нескольких совпадающих фактов; при необходимости он откатывается (backtracking) к последней точке выбора и пробует альтернативы. Поиск детерминирован слева-направо и глубинный — это влияет на порядок и время нахождения решений и на то, какие решения будут найдены первыми.
Влияние оператора cut (!) — примечания
- Cut (!) коммитит (фиксирует) выборы, сделанные до него в текущем вызове предиката, и удаляет соответствующие точки выбора. Это влияет на корректность (может изменять набор найденных решений) и на производительность (может уменьшить поиск).
Примеры вставки cut и их эффект
1) Cut в первом клаузуле:
ancestor(X,Y) :- parent(X,Y), !.
- Для ancestor(alice,carol): первый клаузул не сработал (parent(alice,carol) ложен), cut не достигнут — поведение не меняется.
- Для ancestor(bob,carol): parent(bob,carol) истинно, cut сработает и запретит пробовать другие клаузулы для ancestor — это может улучшить производительность и предотвратить дублирование альтернатив. Это «зелёный» cut, если он только устраняет лишние альтернативы, но может стать «красным», если вторичный путь давал другие решения.
2) Cut после parent(X,Z) во втором клаузуле:
ancestor(X,Y) :- parent(X,Z), !, ancestor(Z,Y).
- Для ancestor(alice,carol): parent(alice,Z) даёт Z=bob, cut фиксирует этот Z и запрещает откатываться к другим возможным Z; затем доказывается ancestor(bob,carol) и успех. При текущих фактх результат тот же, но:
- если у alice было несколько детей, cut запретит проверять других детей после первого найденного — некоторые решения будут потеряны;
- если ancestor(Z,Y) впоследствии не удастся, cut помешает попробовать другой Z, что может превратить возможный успех в неудачу. Это часто «красный» cut (меняет смысл).
3) Cut после рекурсивного вызова (в конце второго клаузула):
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y), !.
- Cut выполняется только если ancestor(Z,Y) успешно доказано; затем он убирает альтернативы, которые появились до него (включая другие варианты Z или другие клаузулы ancestor). Это может ускорить, предотвращая дальнейший поиск после первого найденного доказательства, но также может убрать дополнительные корректные решения.
Короткие выводы
- Без cut Prolog даёт все логически вытекающие решения (с откатом), но может тратить время на альтернативы.
- Cut может значительно улучшить производительность, убирая ненужные ветви поиска, но легко изменить логическое поведение программы и потерять решения (особенно если cut стоит перед моментом, где ещё могли бы появиться альтернативы).
- Практика: использовать cut осторожно; предпочитать «зелёные» cut (только оптимизация) и документировать, когда cut меняет Semantics (красные).