1<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
2<!-- BEGIN LICENSE BLOCK
3   - Version: CMPL 1.1
4   -
5   - The contents of this file are subject to the Cisco-style Mozilla Public
6   - License Version 1.1 (the "License"); you may not use this file except
7   - in compliance with the License.  You may obtain a copy of the License
8   - at www.eclipse-clp.org/license.
9   - 
10   - Software distributed under the License is distributed on an "AS IS"
11   - basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
12   - the License for the specific language governing rights and limitations
13   - under the License. 
14   - 
15   - The Original Code is  The ECLiPSe Constraint Logic Programming System. 
16   - The Initial Developer of the Original Code is  Cisco Systems, Inc. 
17   - Portions created by the Initial Developer are
18   - Copyright (C) 2006 Cisco Systems, Inc.  All Rights Reserved.
19   - 
20   - Contributor(s): 
21   - 
22   - END LICENSE BLOCK -->
23<html>
24<head>
25   <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
26   <meta name="Author" content="Joachim Schimpf">
27   <meta name="GENERATOR" content="Mozilla/4.76 [en] (X11; U; SunOS 5.7 sun4u) [Netscape]">
28</head>
29<body>
30
31<h1>
32Topic: Cyclic (and deeply nested) terms</h1>
33Involved: Joachim, Warwick
34<br>&nbsp;
35<h2>
36Problem</h2>
37Eclipse up to 5.2 at least contains a number of C routines that recurse
38over Prolog terms. E.g.
39<ul>
40<li>
41groundness test</li>
42
43<li>
44term_variables</li>
45
46<li>
47compare_terms</li>
48
49<li>
50occurs test</li>
51
52<li>
53copy term</li>
54
55<li>
56copy to heap</li>
57
58<li>
59term write operations</li>
60</ul>
61Most of them have "last subterm optimization" implemented, i.e. they don't
62build up a call stack when traversing right-balanced structures and in
63particular lists. However, for deep non-right-balanced structures, and
64for cyclic structures, we get overflows of the C call stack, which cannot
65be caught easily (they manifest themselves as segfaults or the like).
66<br>&nbsp;
67<h2>
68Solutions</h2>
69
70<h3>
71Catch overflows</h3>
72Use a PDL (push down list) as in the emulator unification/difference routine
73or in the garbage collector marking. This PDL is built in the local stack,
74so overflow can be properly detected and caught.
75<p>Other possibility: introduce a global "nesting depth limit", count depth
76in all the critical routines, and report error on exceeding the limit.
77<h3>
78Detect cycles</h3>
79There are rather obvious ways to detect cycles by destructively marking
80the visited parts of the term.
81<p>But here is a cheap, non-destructive algorithm for cycle detection:
82<ul>
83<li>
84Maintain one address within the term that has already been visited (call
85it <b>crumb</b>).</li>
86
87<li>
88Maintain a <b>step counter</b> that counts steps since leaving the crumb.</li>
89
90<li>
91have a <b>step counter limit</b>, initialized to an arbitrary value (e.g.
922 or more)</li>
93
94<li>
95When encoutering crumb<b> </b>again during term traversal, we have a cycle
96and stop.</li>
97
98<li>
99When step counter exceeds step counter limit before having encountered
100crumb:</li>
101
102<ol>
103<li>
104set crumb to current address</li>
105
106<li>
107reset step counter to zero</li>
108
109<li>
110double step counter limit</li>
111</ol>
112</ul>
113This will eventually (but possibly quite late) detect a cycle if one exists.
114Why? Assume the traversal has entered a cycle. When step counter reaches
115step counter limit before encountering crumb, that means:
116<ul>
117<li>
118either crumb is outside the cycle. Therefore we set crumb to the current
119address, so it will be in the cycle from now on.</li>
120
121<li>
122or the cycle is longer than the step limit. Therefore we double the step
123limit, so it will eventually be long enough to detect the cycle.</li>
124</ul>
125
126</body>
127</html>
128