prolog-backtracking

Prolog backtracking uses depth-first search to traverse facts and rules, creating choice points at alternative branches. When a goal fails, execution rewinds to the most recent untried choice point to continue searching the proof space.

Choice points store untried alternative clauses during goal evaluation. When Prolog backtracks, it navigates to these stored points, unbinds variables on the trail, and evaluates the next alternative to enumerate subsequent solutions.

Left recursion in logic programming causes infinite loops because the recursive call appears before the base case in the rule body. This prevents Prolog from establishing a terminating choice point, leading to non-exhaustive depth-first search.

Variable unbinding on the trail resets bindings when backtracking occurs. Determinism categories dictate whether a predicate yields single or multiple solutions, directly affecting how the trail unwinds and whether choice points remain active.

Prolog backtracking concepts bridge to related programming paradigms like RxJS and Go. The execution model of navigating choice points translates to understanding reactive streams and concurrency patterns in these languages.

Prolog queries fail when depth-first search exhausts all choice points without satisfying goals, or encounters infinite loops from left recursion. The execution model reports failure, triggering chronological backtracking to explore alternative branches.