Привожу разбор пошагово и короткие рекомендации.
1) Программа (в KaTeX):
$parent(alice,bob).$
$parent(bob,charlie).$
$ancestor(X,Y):-parent(X,Y).$
$ancestor(X,Y):-parent(X,Z),ancestor(Z,Y).$
2) Механизм резолюции (SLD‑резолюция) и унификация — по шагам на запросе
$?-ancestor(alice,charlie).$
- Процедура выбирает левую (leftmost) цель: $ancestor(alice,charlie)$.
- Сначала пытается унифицировать с первым правилом (базовый случай)
$ancestor(X,Y):-parent(X,Y)$. Унификация даёт подстановку $X=alice,Y=charlie$.
Нужно доказать цель $parent(alice,charlie)$ — она не соответствует фактам, попытка завершается неудачей.
- Происходит откат (backtracking) к альтернативному правилу:
$ancestor(X,Y):-parent(X,Z),ancestor(Z,Y)$. Унификация даёт $X=alice,Y=charlie$.
Становится набор целей: $parent(alice,Z),ancestor(Z,charlie)$.
- Левый цель $parent(alice,Z)$ унифицируется с фактом $parent(alice,bob)$, даёт $Z=bob$.
Остаётся цель $ancestor(bob,charlie)$.
- Для $ancestor(bob,charlie)$ сначала проверяется базовый случай $parent(bob,charlie)$ — он истинный, значит исходный запрос успешен (подстановка $X=alice,Y=charlie$).
- Если есть другие варианты для $parent(alice,Z)$ или другие совпадающие правилa, при возврате Prolog будет откатываться и пробовать их.
3) Откат (backtracking)
- При неудаче Prolog возвращается к последней точке выбора (правило или факт) и пробует следующую альтернативу.
- Откат применяется также для поиска дополнительных ответов после успеха.
4) Когда порядок правил/предикатов влияет
- Prolog делает глубинный поиск (depth‑first) с выбором левого предиката. Поэтому:
- Порядок правил влияет на то, какой путь будет исследован первым (влияет на время до первого ответа и на возможность найти ответ вообще).
- Порядок предикатов в теле влияет на частоту привязки переменных и на возможность раннего отсечения ветвей. Часто выгодно ставить детерминистические/узкие тесты первыми (например, проверку ground/1 или сравнения), чтобы сократить ветвление.
- Важный класс проблем — леворекурсивные определения: если рекурсивный вызов стоит левее немедленного уменьшителя размера, поиск может нырять в бесконечную рекурсию и никогда не дойти до базового случая даже если решение существует.
Пример плохой (леворекурсивной) версии:
$ancestor(X,Y):-ancestor(X,Z),parent(Z,Y).$ Запрос $?-ancestor(alice,charlie).$ будет пытаться сначала доказать $ancestor(alice,Z)$ рекурсивно снова и снова — возможная бесконечная петля.
5) Как избегать бесконечных рекурсий и улучшить производительность
- Писать базовый (не рекурсивный) случай первым: в примере это уже так.
- Переставлять цели в теле так, чтобы рекурсивный вызов шёл после предикатов, которые сильно ограничивают переменные (пример: сначала найти конкретного $Z$ через parent, затем рекурсивно).
- Использовать накопители / явный список посещённых узлов, чтобы предотвратить циклы:
$ancestor(X,Y):-ancestor\_vis(X,Y,[]).$
$ancestor\_vis(X,Y,Visited):-parent(X,Y),\neg member(Y,Visited).$
$ancestor\_vis(X,Y,Visited):-parent(X,Z),\neg member(Z,Visited),ancestor\_vis(Z,Y,[Z|Visited]).$ (Идея: не возвращаться в уже посещённые вершины.)
- Использовать табуляцию (tabling, memoization) в реализациях Prolog (например, SWI/XSB): директива $:-tableancestor/2.$ обеспечивает SLG‑резолюцию и часто предотвращает зацикливание и повторные вычисления.
- Применять cut (!) и once/1 аккуратно, когда нужно отбросить ненужные альтернативы (влияет на полноту).
- Обеспечить убывающую меру рекурсии (например, длина пути уменьшается) — классический способ для доказуемости завершения.
- Ограничения глубины или итеративное углубление (если нужно гарантировать завершение при большом пространстве).
Короткие практические правила:
- Базовые факты и детерминистические проверки — первыми.
- Рекурсивный вызов — после предикатов, которые конкретизируют аргументы.
- Для графов/циклов — хранить visited или использовать табулирование.
- Профилировать: порядок влияет на скорость; ставьте самые вероятные/узкие правила первыми.
Если нужно, могу показать конкретные варианты кода с visited или пример использования tabling в SWI‑Prolog.