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="GENERATOR" content="Mozilla/4.76 [en] (X11; U; SunOS 5.5.1 sun4u) [Netscape]"> 27</head> 28<body> 29Author: Mark 30<br>Date: April 2003 31<br>Revision history: Apr 2003 (original) 32<br>Contents: 33<br> Global Structure 34<br> ECLiPSe Code 35<br> 36<h1> 37Global Structure</h1> 38 39<h3> 40File</h3> 41 42<ul> 43<li> 44<b>repair.pl: </b>The repair solver is encoded within this one file</li> 45</ul> 46 47<h3> 48Module</h3> 49All the repair code is within a single module <b>repair</b> 50<h3> 51<b>Imported Modules</b></h3> 52lib(linearize) used to linearize arithmetic expressions in <b>tent_is</b> 53calls 54<br>lib(hash) used to select a named conflict set from the repair state 55<br> 56<h3> 57Debugging</h3> 58For the developers and maintainers of <b>repair,</b> a specific debugging 59(tracing) facility is supported through the "<b>'ASSERT'</b>" predicate. 60This is switched on by commenting out the other clause in its definition. 61<p>For users repair statistics are provided via the exported predicate 62<b>repair_stat/1</b>. 63<h1> 64ECLiPSe Code</h1> 65The repair library supports tentative values, conflict detection and invariants 66(label propagation of tentative values). Unnamed conflict sets are 67retained for legacy reasons. 68<br> 69<h3> 70Attribute</h3> 71Repair variables have the following attribute: 72<p>:- export struct(repair( 73<br> 74tent, % tentative value 75<br> 76mon, % set element with suspension of <b>monitor_tenable</b> goal 77<br> 78ga_chg % suspensions to wake on global assignment changes 79<br> 80)). 81<br>The value of the <i>mon</i> attribute has a special structure which 82allows constant time set membership testing and update (see below). 83<b>monitor_tenable </b>is suspended on <i>constrained,</i> and uses <b>not_unify</b> 84to check if the variable is tenable. If the variable has just become 85untenable, it wakes the <i>ga_chg </i>suspension list. 86<br> 87<h3> 88Global Repair State</h3> 89:- current_array(repair_state, _) -> true ; local reference(repair_state). 90<p>:- local struct(repair_state( 91<br> 92conflict_vars, 93<br> 94conflict_hash_constraints, 95<br> 96conflict_constraints 97<br> 98)). 99<br>All information about conflict constraints and variables is held in 100this local reference. 101<br>The attribute <i>conflict_hash_constraints </i>records, for each conflict 102set, its conflict constraints. The conflict sets are held in a hash 103table. The third attribute, <i>conflict_constraints</i>, is a global 104(unnamed) conflict set, kept for legacy reasons. 105<br> 106<h3> 107Detecting Conflicts</h3> 108The predicate <b>monitor_conflict</b> is the heart of the repair library. 109<p>:- local struct(monitor_conflict(constraint,annotation,conflict,prop,module)). 110<p>This internal structure maintains the information necessary to monitor 111conflicts for a repair constraint. 112<br>The <i>annotation</i> is the information returned by the system when 113listing conflicts. 114<br>The <i>conflict </i>is a (constant time set membership) structure which 115both records whether the constraint is in conflict, and holds the suspension 116which keeps this information up to date. 117<br>The <i>prop</i> attribute records whether the constraint should also 118be propagated. 119<p><b>monitor_conflict</b> is a demon suspended on the <i>constrained</i> 120and <i>ga_chg</i> lists of all variables in the constraint, it instantiates 121the variables to their tentative values (if they have one), and runs the 122constraint using <b>not not</b> to avoid any side-effects. If the 123check fails, the conflict is recorded, and if the propagation flag is set 124(to 0) the constraint is invoked. 125<h3> 126Numerical Constraints and Invariants</h3> 127If a repair constraint (annotated with <i>r_conflict</i> or <i>r_conflict_prop</i>) 128is arithmetic, then it involves two expressions Expr1 and Expr2 which are 129compared (using =,>,< etc.). Such a constraint is handled using 130<b>tent_is </b>to compute the tentative value of each expression and <b>unify_to_tent_if_ground_args</b> 131to instantiate the result in case the expression is ground. 132<br>All other repair constraints are handled using <b>monitor_conflict</b>. 133<p>Invariants allow tentative values to be propagated through a function 134(functional constraint) from its inputs to its outputs. 135<br>In essence this is achieved by making a copy of the constraint, replacing 136the input variables by their tentative values. This copy of the constraint 137is then invoked, thereby instantiating its outputs. Finally the output 138values from the copied constraint are used to update the tentative values 139of the output variables of the original constraint. 140<p>For mathematical invariants (with the form <i>Var </i><b>tent_is </b><i>Expr</i>) 141the expression is first linearized, creating a sum expression of the form 142<i>C1*V1+C2*V2+...+Cn*Vn</i> together with none or more nonlinear 143constraints of the form <i>V=NonLin</i>. 144<br>The sum expression allows the invariant to be computed in a way that 145is independent of the number of terms <i>n</i>. 146<br>Specifically if the tentative value of one term changes, the difference 147between its old and new value is computed, and the tentative value of the 148whole sum is changed by that amount. This is done by a demon <i>sum_update</i>. 149<br>A separate invariant is created to handle each nonlinear subexpression 150<i>V=NonLin</i> using <i>tent_call.</i><i></i> 151<p>All other (non-arithmetic) invariants are handled using <b>tent_call</b>, 152which is implemented by making a copy of the constraint, as described above. 153<br> 154<h3> 155Constant Time Set Membership</h3> 156A special structure is used for the <i>mon </i>attribute of repair variables, 157and for the <i>conflict</i> argument of the <b>monitor_conflict </b>predicate. 158This structure allows set membership checking and updating in constant 159time. 160<br>The structure of a set element is: <i>elem(Term,InSet,OnList,Set)</i>. 161<br><i>Term</i> is the actual element held in the set. 162<br><i>InSet</i> is a 0/1 flag, indicating whether <i>Term</i> is currently 163in the set. 164<br><i>Set</i> is a structure of the form <i>s(List)</i>, where <i>List</i> 165is a list of elements in the form <i>elem/4</i>. 166<br><i>OnList </i>is another 0/1 flag, indicating whether <i>elem(Term,InSet,OnList,s(List))</i> 167is currently in the list <i>List</i>. 168<br><i>Term </i>belongs to the set <i>s(List)</i> if and only if <i>elem(Term,1,1,s(List))</i> 169is in the list <i>List.</i> Consequently this representation employs 170a cyclic data structure. 171<br>Given the structure <i>elem(Term,InSet,OnList,s(List))</i>, checking 172for membership requires constant time (by just checking the flag <i>InSet</i>), 173and updating is constant time by either just changing the flag <i>InSet</i> 174or, if necessary, updating the flag <i>OnList</i> and adding this structure 175to the head of the list. 176<br>The set can be "flushed" when necessary by removing all the elements 177from the list whose <i>InSet</i> flag is off, and by also setting their 178<i>OnList</i> flag off. 179<p>The constant time set of conflict variables, containing the <i>mon</i> 180attributes of the repair variables, is in the <i>conflict_vars </i>attribute 181of the <i>repair_state</i>. 182<br>The constant time set of conflict constraints, containing the <i>conflict</i> 183argument of the <b>monitor_conflict </b>predicates, is in the <i>conflict_hash_constraints</i> 184(or <i>conflict_constraints</i>) attribute of the <i>repair_state</i>. 185<h3> 186Priorities</h3> 187The priorities of the variable and constraint conflict monitors, and of 188the invariants, are hard-wired. They are as follows: 189<br>Demon 190Priority 191<br><b>monitor_conflict </b> 8 192<br><b>monitor_tenable </b> 6 193<br><b>sum_update</b> 1942 195<br><b>tent_call </b> 1962 197<br>The predicate <b>unify_to_tent_if_ground_args</b> has priority 3. 198<br> 199<br> 200<br> 201<br> 202</body> 203</html> 204