Diagnosing Non‑Termination in Prolog Due to Missing Occurs‑Check

Recognizable condition

The program appears to hang, memory usage grows steadily, or it exceeds a time limit when a recursive predicate is invoked with a variable that could unify with a compound term containing itself. Typical symptoms are:

• The query never returns a solution.
• CPU usage stays at 100 % for the duration of the run.
• The process is killed by an external watchdog after exceeding a timeout.

Short cause / diagnostic table

Observed symptom	Likely cause	What to look for in a trace
Infinite loop, growing term depth	Missing occurs‑check in a recursive unification	Same predicate re‑entered with arguments that increase in size each call (e.g., f(X) → f(f(X)) → …)
Instantiation error after enabling occurs‑check	Occurs‑check now prevents the cyclic unification	Trace shows a single call that ends with ERROR: instantiation_error

Ordered checks

1. Confirm non‑termination

   Run the query with the default Prolog settings (occurs‑check disabled). Note whether it hangs or exceeds a time limit.

   % In SWI‑Prolog top‑level
   ?- time(( ancestor(A,B), fail )).
   

   Where to run: any Prolog console; no special permissions needed.
   Risk: the query may consume memory; interrupt with Ctrl‑C if it runs too long.

2. Enable the occurs‑check flag

   Turn on the flag that activates the occurs‑check (if your system provides it) and repeat the query.

   ?- set_prolog_flag(occurs_check,true).
   ?- time(( ancestor(A,B), fail )).
   

   Expected check: the call should now fail quickly with an instantiation_error instead of looping.

3. Use the built‑in tracer

   Activate tracing to see the call pattern.

   ?- trace.
   ?- ancestor(A,B).
   

   With occurs‑check disabled you will see repeated entries to ancestor/2 with ever‑larger arguments. After enabling the flag the tracer should show a single call that ends with an error.

Fixes tied to findings

• Enable occurs‑check for debugging or safety‑critical code

  If the program is intended to run with the occurs‑check (e.g., in a verified setting), keep the flag enabled:

  :- set_prolog_flag(occurs_check,true).
  

  Be aware that this can cause a noticeable slowdown in programs that do not need the check.

• Redesign the predicate to avoid cyclic unification

  Add an explicit check that prevents a variable from being unified with a term containing itself. In SWI‑Prolog you can use the built‑in acyclic_term/1 or unify_with_occurs_check/2:

  ancestor(X,Y) :- 
      parent(X,Y).
  ancestor(X,Y) :- 
      parent(X,Z),
      unify_with_occurs_check(X,Z), % prevents X = f(X) loops
      ancestor(Z,Y).
  

  Alternatively, restructure the recursion so that the recursive call does not share the same variable that could become cyclic.

• Use a cut only after confirming correctness

  A cut (!/0) can stop the loop but may hide the underlying occurs‑check problem and produce wrong results. Apply it only after you have verified that the program logic is sound.

Escalation criteria

If enabling the occurs‑check does not resolve the non‑termination, consider the following escalation steps:

1. Check for missing base cases or incorrect recursion ordering.
2. Look for other sources of infinite loops, such as mutually recursive predicates without a decreasing measure.
3. Consult the system’s documentation for additional flags (e.g., max_depth) that can help bound search during debugging.

Limitations and practical verification

The occurs‑check is a safety feature; turning it on may change the semantics of programs that deliberately rely on cyclic terms (e.g., constraint handling). Therefore:

• Verify that the program does not require cyclic terms before enabling the flag globally.
• After enabling the flag, run the full test suite to ensure no legitimate solutions are lost.
• If performance degradation is unacceptable, limit the occurs‑check to the specific module or predicate using local flag setting:

:- set_prolog_flag(occurs_check,true, local).

To confirm the fix, run the original non‑terminating query with the occurs‑check enabled and observe that it terminates with an error or a finite set of solutions within an expected time bound.