Правило ancestor/2 (рекурсивно через parent/2):
parent(alice,bob).
parent(bob,charlie).
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).
Пример запроса:
?- ancestor(alice,charlie). % ответ — true
Ключевые моменты и сравнение
- Механизм Prolog: при запросе Prolog выполняет обратный поиск (top‑down, SLD‑резолюция) — пытается доказать цель, рекурсивно подбирая факты и правила, с возвратом (backtracking) при неудаче. Это поиск на дереве доказательств, управляемый системой.
- Дедукция vs императивное вычисление:
- Дедукция (логическое программирование) описывает отношения (что верно), а система сама строит доказательства (как получить ответ). Подход декларативен: программа — набор логических предикатов.
- Императивное вычисление описывает пошагово алгоритм (как вычислять), с явным контролем потока, состоянием и побочными эффектами.
- В дедуктивном подходе контроль выполнения скрыт в интерпретаторе (поисковая стратегия, unification, backtracking). В императивном — программист явно управляет циклами, ветвлениями и памятью.
- Последствия различий:
- Преимущества логического подхода: компактное, читабельное описание связей; удобство работы с недетерминистичностью и генерацией всех решений; естественная интеграция с символьными данными и правилами.
- Ограничения: стандартный Prolog использует глубинный поиск слева‑направо, что может вести к зацикливанию или неэффективному перебору; сложнее контролировать порядок и ресурсопотребление без приёмов (cut, тернарное программирование, ограничения).
- Можно улучшать: табличная дедукция (tabling/SLG) избавляет от повторных вычислений и устраняет многие зацикливания, превращая сложность из экспоненциальной в полиномиальную в ряде случаев.
- Сложность (оценочно):
- В худшем случае при наивном backtracking — экспоненциальный рост поискового пространства, примерно $O(b^d)$ (где $b$ — степень разветвления, $d$ — глубина).
- С табличной дедукцией или в ориентированных графовых задачах можно получить линейную сложность по числу узлов/ребёр, примерно $O(n+m)$.
Когда логическое программирование эффективно
- Хорошо подходит для: выводных систем, экспертных систем, правил принятия решений, задач с интенсивной работой с отношениями (родословные, графы, базы фактов), обработки и анализа синтаксических деревьев, прототипирования логики, задач с недетерминизмом и поиском, а также когда удобно задавать ограничения (CLP).
- Менее эффективно для: тяжёлых численных расчётов и низкоуровневой оптимизации, где требуется контроль памяти и высокая производительность; для задач, где нужен детерминированный поток управления и явная эффективная итерация — императивный подход часто проще и быстрее.
Короткая рекомендация: используйте логическое программирование, когда хотите декларативно задать отношения и дозволить системе искать решения; при проблемах с производительностью добавляйте ограничения, таблинг или комбинируйте с императивным кодом.