Кратко — причины и приёмы устранения зацикливания в Prolog (с примерами реструктуризации).
Причины зацикливания
- Отсутствие или неправильная база рекурсии. Пример плохо: `p :- p.` — всегда зацикливание.
- Неправильный порядок целей: рекурсивный вызов стоит раньше тестов/ограничений, которые могли бы отсечь ветвь.
- Леворекурсивные правила в топ‑down поиске (например, грамматика с left‑recursion) приводят к бесконечной рекурсии.
- Рекурсия, которая строит всё более «большие» термы (рост аргумента) вместо уменьшения; или нет монотонно убывающей меры.
- Слишком большая недетерминированность (множество альтернатив / разветвлённый поиск) без отсечения, вследствие чего DFS уходит в бесконечный путь.
- Использование отрицания по незафиксированным переменным (\+ с вар), флаундинг или создание циклических термов при отсутствии occurs‑check (маскирует ошибки).
- Повторные вычисления одних и тех же подцелей (без memoization/tabling) приводят к бесконечным чередующимся вызовам.
Как реструктурировать и контролировать поиск
- Вводить корректную базу и обеспечивать уменьшение меры: для некоторой функции меры $\mu$ требовать $\mu ({\text{args}}_{n+1})<\mu ({\text{args}}_n)$. Пример для натуральных чисел: мера $\mu (N)=N$, в рекурсии должно выполняться $\mu (N-1)<\mu (N)$.
- Поменять порядок целей: ставить детерминирующие/ограничивающие тесты (например `ground/1`, сравнения, `\+`) перед рекурсивным вызовом, чтобы отсекать ветви раньше.
- Устранить левую рекурсию: переписать правила в правую рекурсию или использовать эквивалентную итеративную форму. Пример (DCG): заменить `expr --> expr, [+], term` на форму с накопителем или правой рекурсией.
- Сделать рекурсию хвостовой (tail recursion) с аккумулятором, чтобы уменьшить глубину стека и упростить анализ завершения.
- Ограничивать глубину/ширину поиска: глубинная граница, итеративное углубление (iterative deepening), или явно проверять пределы (например счётчик глубины).
- Применять таблирование (tabling, SLG): сохраняет результаты подцелей и гарантирует завершение для множества программ, где топ‑down DFS зацикливается. В SWI‑Prolog: `:- table pred/arity.`
- Использовать pruning: cut (`!`), `once/1`, `->/2 ; /2` — с осторожностью (меняет семантику). Применять только когда вариант действительно ненужен.
- Переключаться на CLP/ограничения: уравнения/СЛП(граничные) часто дают заключения о невозможности решения и отсекают ветви раньше.
- Включать occurs‑check при отладке, чтобы обнаружить неожиданные циклические термы.
- Анализ аргументов/мод (mode analysis): проектировать предикаты так, чтобы некоторые аргументы были input (заданы) — это снижает недетерминированность и улучшает индексацию.
Короткие примеры
- Плохой порядок:
- Плохо: `p(X) :- q(X), p(X).`
- Лучше: `p(X) :- q(X), some_test(X), p1(X).` — поместить тест `some_test/1` перед рекурсией или изменить логику так, чтобы рекурсивный вызов получал «меньший» аргумент.
- Рекурсия с уменьшением:
- Корректно: `fact(0,1). fact(N,F) :- N>0, N1 is N-1, fact(N1,F1), F is N * F1.` — мера $\mu (N)=N$ убывает.
Вывод: определить, какая из причин применяется в вашей программе (провести трассировку), затем применить соответствующий приём: переставить цели, ввести базу/меру, переписать левую рекурсию, добавить табуляцию или ограничение глубины.