skip to content

When a containment query's first matching clause leads to a dead end, what does the inference engine do next?

level: middleimportance: should knowfreq 41%

answer

  1. failure is ordinary, not an error
  2. the engine kept somewhere to return to
  3. bindings roll back with the branch
  4. resume at the most recent alternative
  5. a further answer restarts the same search

basics

~10 s

It backtracks: the engine returns to the most recent choice point, undoes every variable binding made since, and tries the next matching clause - repeating until a branch succeeds or the alternatives run out.

solid answer

~40 s

The engine is running a depth-first search you did not write. It takes the leftmost unsolved goal, finds the first clause whose head unifies with it, and - if other clauses could also have matched - records a **choice point** before continuing. A dead end is not an error; it is just failure of that branch, so the engine unwinds to the last choice point, **undoes the bindings** made after it, and tries the next alternative. That undo is the part people forget: a variable bound on a failed branch is open again on the next one. This machinery is **SLD resolution**, and the same machinery answers 'give me another solution' - the engine deliberately fails the current success and resumes the search where it left off.

code

pseudocode · 13 lines
pseudocode
fact contains("cabinet", "fan")
fact contains("cabinet", "tray")
fact contains("tray", "bolt")

# goal: partOf("cabinet", "bolt")
#
#   clause 1: contains("cabinet", "bolt")      -> no such fact, fail
#   clause 2: contains("cabinet", Middle)
#       Middle = "fan"      <- choice point recorded ("tray" untried)
#       partOf("fan", "bolt")                  -> fail
#   backtrack: undo Middle, take the next alternative
#       Middle = "tray"
#       partOf("tray", "bolt")                 -> succeeds

go deeper

for a junior

Know that failure is a normal outcome in this model: the engine goes back to the last point where another clause could have matched and tries that one instead.

for a middle

Describe the loop - leftmost goal, first matching clause, choice point when alternatives remain - and be explicit that backtracking undoes the bindings made since.

for a senior

Reason about cost: choice points are retained state, clause and fact order decide what is explored, and side-effecting goals are not rolled back when a branch is abandoned.

for a principal

Weigh the bargain the paradigm offers - the engine owns control, so your levers are ordering and pruning, and pruning costs you the purely logical reading of the program.

## The engine runs a search you did not write In an imperative program, the control flow on the page is the control flow at run time. In a logic program it is not: the clauses state what is true, and the engine supplies a fixed search strategy over them. Understanding a logic program operationally means understanding that search, because it is where both the answers and the costs come from. ## The loop, in operational terms For a goal list, the engine repeats: 1. Take the **leftmost** unsolved goal. 2. Scan the clauses whose head could match it, in program order, and unify with the first that fits. 3. If other clauses remain that could also have matched, record a **choice point**: the goal list as it stands, the bindings as they stand, and a pointer to the next untried clause. 4. Replace the goal with that clause's body goals and continue. 5. If the goal matches nothing, the branch **fails** - unwind to the most recent choice point, undo everything done since it was created, and resume from the next untried clause there. 6. If no choice point remains, the query has no (further) answers. When the goal list empties, the current bindings are an answer. This procedure is **SLD resolution**: selection of a goal, linear derivation, definite clauses. ## What backtracking undoes, and what it does not This is the distinction worth being precise about: - **Variable bindings are undone.** Anything bound after the choice point becomes unbound again. The alternative branch starts from exactly the state that existed before the abandoned one. - **Work already done is not remembered.** Having derived a subgoal on the failed branch does not make it cheaper on the next one, unless the engine memoises goals - and engines differ on whether they do. - **Anything outside the knowledge base is not undone.** A goal that printed, wrote, or asserted a new fact has already had its effect, and backtracking past it does not take it back. Mixing such goals into a search is how logic programs become hard to reason about. ## A worked trace With facts `contains(cabinet, fan)`, `contains(cabinet, tray)`, `contains(tray, bolt)` and the usual two-clause `partOf`, the goal `partOf(cabinet, bolt)` goes like this: - The direct clause tries `contains(cabinet, bolt)` - no such fact, fail. - The recursive clause tries `contains(cabinet, Middle)`. The first matching fact binds `Middle = fan`, and because `tray` could also match, a **choice point** is recorded. - The subgoal `partOf(fan, bolt)` finds nothing at all and fails. - The engine unwinds to the choice point, **unbinds** `Middle`, and takes the next alternative: `Middle = tray`. - Now `partOf(tray, bolt)` succeeds through the direct clause, and the query succeeds. Nothing in the clause text mentions fans, retries, or order. The failed excursion into `fan` exists only in the engine's search. ## Why the search behaviour is your problem anyway | symptom | what it means operationally | |---|---| | a query that takes far longer than the answer's size suggests | the search is exploring large subtrees that fail late | | answers arriving in an order that surprises you | clause order and fact order decide enumeration order | | a second answer that is identical to the first | two distinct branches derive the same binding | | memory growing during a single query | choice points accumulate; nothing has been discarded | The last row is worth stressing. Every choice point is retained state, so a query that leaves millions of them behind consumes memory even though your program contains no data structure at all. Engines therefore offer a pruning construct that discards the choice points created since the current goal began, committing to the choices already made. It is the sharpest tool in this paradigm and the easiest to misuse: pruning changes which answers are found, so a program that reads as pure logic no longer means what its clauses say. That is the practical face of the trade this paradigm makes - you write the logic, the engine owns the control, and when the control is wrong your only levers are the order of your clauses and goals, and a construct that cuts the search short.

  • What is a choice point holding, in practice?
    The state needed to resume: the outstanding goals, the bindings as they stood, and a pointer to the next untried clause for the goal being solved. It is retained until the engine either exhausts those alternatives or prunes them, which is why a long-running query can grow in memory without your program allocating anything.
  • Why is mixing side effects into a logic program's goals risky?
    Backtracking undoes bindings but not effects. A goal that printed or wrote has already acted, and the branch that caused it may be abandoned a moment later, so the effects you observe reflect the engine's search path rather than the program's logical reading.

saying these in an interview costs you the question

  • Treats a failed goal as an error the query reports
  • Thinks bindings made on a failed branch survive backtracking
  • Assumes work done on a failed branch is remembered and reused
  • Believes asking for the next answer restarts the query from the beginning
  • Ignores that choice points are retained memory during one query