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.