Коротко о правилах и целях
Дан фрагмент:
parent(alice, bob).
parent(bob, carol).
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

В Prolog строки вида parent(...) — факты, а ancestor(...) — два правила. Правило читается как: "X — предок Y, если X — родитель Y" и "X — предок Y, если X — родитель Z и Z — предок Y".

Механизм поиска и отката (backtracking) — пошагово на примере запроса
1) Запрос: ?- ancestor(alice, carol).

Prolog пытается доказать цель ancestor(alice,carol). По умолчанию он перебирает правила сверху вниз и для тела правила — слева направо.

Шаг 1: пробует первое правило ancestor(X,Y) :- parent(X,Y).

Подставляет X=alice, Y=carol и ставит подцель parent(alice,carol).Ищет факт parent(alice,carol) — нет. Подцель неудачна → возникает точка отката (choice point): есть ещё правило ancestor, значит вернуться и попробовать следующее правило.

Шаг 2: пробует второе правило ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).

Подставляет X=alice, Y=carol; появляется подцель parent(alice,Z).parent(alice,Z) унифицируется с фактом parent(alice,bob) → Z=bob. Теперь остаётся доказать ancestor(bob,carol).

Для доказательства ancestor(bob,carol) Prolog рекурсивно повторяет тот же алгоритм:

Сначала пробует первый вариант ancestor(bob,carol) :- parent(bob,carol).
parent(bob,carol) есть факт → успех. Значит ancestor(bob,carol) успешно доказан.Возвращается вверх: раз ancestor(bob,carol) истинно и Z=bob, то исходная цель ancestor(alice,carol) истинна. Отдаётся ответ true (и при интерактивном режиме — возможная подстановка Z=bob, хотя пользователь обычно интересуется Y).

Если запрос ?- ancestor(alice, Y). — Prolog вернёт сначала Y=bob (из первого правила ancestor :- parent), затем при запросе "ещё" он откатится и найдёт Y=carol через второй (рекурсивный) путь. Откат работает так: когда достигнут успешный ответ, Prolog сохраняет точки выбора (альтернативные правила или альтернативы унификации). При требовании дополнительных решений он возвращается к последнему выбору и пробует следующую альтернативу, при этом откатывает (отменяет) связки переменных до того состояния, в котором был этот выбор.

Важно: поиск — глубинный (depth-first), слева направо. Это эффективно по памяти, но может зациклиться на леворекурсивных правилах или при бесконечных ветвях.

Где именно появляются точки выбора (choice points)

при выборе между несколькими клаузулами с тем же именем/арностью;при унификации с фактом/шаблоном, если фактов несколько;при использовании предикатов, которые сами дают несколько решений (например, перебор списков и т. п.).

При откате Prolog восстанавливает старые значения логических переменных (undo bindings) и пробует следующую альтернативу.

Сравнение с рекурсией в функциональных языках

Контроль исполнения:
В функциональном языке рекурсия — это детерминированный способ вычисления значения. Вы явно пишете последовательность вызовов, результатом — единственное значение или ленивый список значений. Управление порядком перебора/генерации обычно явно кодируется (например, через списки, монады, комбинаторы).В Prolog рекурсия сочетается с не детерминизмом: одно правило может выдавать множество решений, Prolog автоматически ищет их через backtracking. Вам не надо вручную управлять генерацией всех вариантов.Переменные и унификация:
Функц. языки имеют неизменяемые переменные (значения). В Prolog переменные — логические: они могут быть частично определены и затем унифицироваться (заполняться) в процессе поиска.Декларативность:
В Prolog вы описываете отношения (что верно), а не пошаговый алгоритм. В функциональном вы описываете преобразования данных.Поиск и контроль:
Prolog implicit search (DFS) + backtracking. В функциональном вам нужна структура данных (например, список возможных вариантов) и явно написанный перебор или использование монады nondet/logic.Производительность и предсказуемость:
Функциональный код часто предсказуемее по сложности; Prolog может быть удобен для компактного описания, но требует понимания порядка правил (чтобы избежать зацикливания).

Пример задачи, где логический подход предпочтительнее императивного
Классические примеры — задачи с ограничениями и комбинированием: судоку, раскраска карт, расписание экзаменов, конфигурация оборудования, логические головоломки (Zebra puzzle), синтаксический разбор предложений и т. п.

Почему Prolog/логическое программирование удобнее:

Вы можете описать ограничения декларативно (например, "в одной строке все числа различны", "сумма ряда равна ...", "каждый студент имеет ровно один экзамен в один слот"), а система сделает поиск по вариантам за вас.Современный Prolog с CLP(FD) (Constraint Logic Programming over Finite Domains) дополнительно использует дедуктивную фильтрацию (constraint propagation), что значительно уменьшает обход пространства вариантов и делает код коротким и выразительным.

Пример (в двух словах): судоку

В Prolog декларативно задают 9×9 массива переменных, домены 1..9, и ограничения "в каждой строке/столбце/квадрате все значения различны". Затем запуск решателя вернёт заполнение — вы не пишете вложенные циклы и backtracking вручную, Prolog/CLP делает это эффективнее, чем простая императивная реализация с ручным откатом.

Короткое замечание об ограничениях

Преимущество логического подхода — компактность и возможность неявного поиска. Недостатки — контроль над порядком поиска, возможные зацикливания, менее эффективен для численных вычислений по сравнению с низкоуровневым императивным кодом. Для трудных задач часто комбинируют: используют Prolog/CLP для спецификации и C/императив для «тяжёлых» вычислений.

Если хочется, могу:

показать полный пошаговый трассинг поиска для запроса ancestor(alice, Y) с указанием всех точек выбора,или привести пример кода Prolog для судоку с CLP(FD).