Topic: Cyclic (and deeply nested) terms

Involved: Joachim, Warwick

Problem

Eclipse up to 5.2 at least contains a number of C routines that recurse over Prolog terms. E.g.

groundness test
term_variables
compare_terms
occurs test
copy term
copy to heap
term write operations

Most of them have "last subterm optimization" implemented, i.e. they don't build up a call stack when traversing right-balanced structures and in particular lists. However, for deep non-right-balanced structures, and for cyclic structures, we get overflows of the C call stack, which cannot be caught easily (they manifest themselves as segfaults or the like).

Solutions

Catch overflows

Use a PDL (push down list) as in the emulator unification/difference routine or in the garbage collector marking. This PDL is built in the local stack, so overflow can be properly detected and caught.

Other possibility: introduce a global "nesting depth limit", count depth in all the critical routines, and report error on exceeding the limit.

Detect cycles

There are rather obvious ways to detect cycles by destructively marking the visited parts of the term.

But here is a cheap, non-destructive algorithm for cycle detection:

Maintain one address within the term that has already been visited (call it crumb).
Maintain a step counter that counts steps since leaving the crumb.
have a step counter limit, initialized to an arbitrary value (e.g. 2 or more)
When encoutering crumb again during term traversal, we have a cycle and stop.
When step counter exceeds step counter limit before having encountered crumb:

set crumb to current address
reset step counter to zero
double step counter limit

This will eventually (but possibly quite late) detect a cycle if one exists. Why? Assume the traversal has entered a cycle. When step counter reaches step counter limit before encountering crumb, that means:

either crumb is outside the cycle. Therefore we set crumb to the current address, so it will be in the cycle from now on.
or the cycle is longer than the step limit. Therefore we double the step limit, so it will eventually be long enough to detect the cycle.