Кратко о механизме поиска (SLD‑резолюция)
- Prolog использует SLD‑резолюцию: выбирается текущая цель (обычно самый левый атом), подбирается к ней клауза из базы, производится унификация её головы с целью, образуется новый резолвент (замена цели на её тела с подстановками). Процесс повторяется рекурсивно; при неудаче происходит откат (backtracking) к последней точке выбора (choice point) и пробуется следующая клауза/альтернатива.
- Стратегия поиска в классическом Prolog: глубинный поиск в глубину с левым порядком выбора (depth‑first, left‑to‑right). Результаты — вычисленные подстановки (computed answer substitutions).
Где возникают проблемы с производительностью/терминируемостью
- Комбинаторный взрыв: при ветвлении $b$ и глубине $d$ число ветвей может расти экспоненциально, примерно $O(b^d)$.
- Повторные вычисления одинаковых подцелей приводят к экспоненциальному удвоению (типично в рекурсивных графах без табуляции).
- Неподходящий порядок целей: если дорогостоящая/ограничивающая проверка стоит в конце, Prolog может перебрать много неудачных ветвей прежде, чем обнаружить провал.
- Лево-рекурсия (рекурсивный вызов стоит в начале тела): приводит к зацикливанию (неконвергентности) в глубинном поиске. Пример: `p :- p, q.` — попытки раскрыть `p` будут бесконечны.
- Много точек выбора: частые неоднозначные предикаты (большое число клауз) создают много choice points и нагрузку на откат.
Как менять поведение через порядок правил и целей
- Порядок клауз: Prolog пробует клаузы сверху вниз — поместите более специфичные/быстро отбрасывающие случаи раньше, общие — позже.
- Порядок целей в теле: используйте сначала узкие/быстрые фильтры (арность, арифметику, простые проверки, `var/1`/`nonvar/1`), затем дорогие/генерирующие вызовы. Это раннее отсечение плохих ветвей.
Пример: вместо
```
complicated_search(X), check(X).
```
лучше
```
check(X), complicated_search(X).
```
- Рекурсия: если рекурсивный вызов делает левое расширение, попробуйте переписать так, чтобы рекурсивный вызов был правее (или использовать хвостовую рекурсию), либо использовать аккумулирующие аргументы для преобразования в хвостовую рекурсию.
Использование отсечения (!) (cut) для управления поиском
- `!` удаляет все choice points, созданные внутри текущего предиката с момента входа в него; после выполнения `!` откат к ранее удалённым вариантам невозможен. Это способствует эффективности, но меняет семантику программы.
- Зеленый cut (без изменения логического значения): применяется после того, как предикат уже гарантированно определил уникальное логическое поведение; он лишь убирает ненужные альтернативы и не меняет множество моделей. Пример:
```
max(X,Y,X) :- X >= Y, !.
max(_,Y,Y).
```
Если `X >= Y` истинно, мы фиксируем выбор и не пробуем вторую клаузу.
- Красный cut (изменяющий семантику): используется для управления поиском и сокращения вычислений, но может скрыть корректные решения, поэтому требует осторожности.
- Варианты: `once/1` (взять только первое решение), конструкция `(Cond -> Then ; Else)` (если Cond ставит `!` неявно при успехе в Then для того, чтобы не рассматривать Else), явные `!` в теле для прекращения дальнейшего перебора.
Рекомендации по улучшению производительности
- Переставляйте цели: быстрые тесты и фильтры первыми.
- Ставьте более специфичные клаузы раньше.
- Избегайте лево‑рекурсии — делайте рекурсивный вызов правее или применяйте хвостовую рекурсию с аккумуляторами.
- Используйте табуляцию (memoization, напр. `:- table` в XSB/SWI с `library(tabling)`) для избежания повторных вычислений.
- Пользуйтесь индексированием: организуйте сигнатуры так, чтобы первый аргумент различал большинство клауз (Prolog индексирует обычно по первому аргументу).
- Применяйте `cut` осторожно: предпочитайте зеленый cut; для простого «взять первое решение» используйте `once/1`.
- Профилируйте и тестируйте: локализуйте медленные предикаты и экспериментируйте с порядком целей и клауз.
Короткий пример (порядок целей и cut)
```
% плохой вариант: expensive генерирует много вариантов, check отбрасывает их поздно
p(X) :- expensive(X), check(X).
% лучший порядок: сначала фильтр
p(X) :- check(X), expensive(X).
% использование cut для детерминированного случая
p(X) :- special_case(X), !, handle_special(X).
p(X) :- general_case(X).
```
Это основные принципы: SLD — глубинный левосторонний поиск с откатом; проблемы — экспоненциальный рост, лево‑рекурсия и повторные вычисления; управление — перестановка клауз/целей, хвостовая рекурсия, табуляция и аккуратное применение `!`.