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> 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> 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