Author: Mark
Date: April 2003
Revision history: Apr 2003 (original)
Contents:
    Global Structure
    ECLiPSe Code
 

Global Structure

File

Module

All the repair code is within a single module repair

Imported Modules

lib(linearize) used to linearize arithmetic expressions in tent_is calls
lib(hash) used to select a named conflict set from the repair state
 

Debugging

For the developers and maintainers of repair, a specific debugging  (tracing) facility is supported through the "'ASSERT'" predicate.  This is switched on by commenting out the other clause in its definition.

For users repair statistics are provided via the exported predicate  repair_stat/1.

ECLiPSe Code

The repair library supports tentative values, conflict detection and invariants (label propagation of tentative values).  Unnamed conflict sets are retained for legacy reasons.
 

Attribute

Repair variables have the following attribute:

:- export struct(repair(
                                        tent,  % tentative value
                                        mon,  % set element with suspension of monitor_tenable goal
                                       ga_chg  % suspensions to wake on global assignment changes
                          )).
The value of the mon attribute has a special structure which allows constant time set membership testing and update (see below).  monitor_tenable is suspended on constrained, and uses not_unify to check if the variable is tenable.  If the variable has just become untenable, it wakes the ga_chg suspension list.
 

Global Repair State

:- current_array(repair_state, _) -> true ; local reference(repair_state).

:- local struct(repair_state(
                                              conflict_vars,
                                              conflict_hash_constraints,
                                              conflict_constraints
                        )).
All information about conflict constraints and variables is held in this local reference.
The attribute conflict_hash_constraints records, for each conflict set, its conflict constraints.  The conflict sets are held in a hash table.  The third attribute, conflict_constraints, is a global (unnamed) conflict set, kept for legacy reasons.
 

Detecting Conflicts

The predicate monitor_conflict is the heart of the repair library.

:- local struct(monitor_conflict(constraint,annotation,conflict,prop,module)).

This internal structure maintains the information necessary to monitor conflicts for a repair constraint.
The annotation is the information returned by the system when listing conflicts.
The conflict is a (constant time set membership) structure which both records whether the constraint is in conflict, and holds the suspension which keeps this information up to date.
The prop attribute records whether the constraint should also be propagated.

monitor_conflict is a demon suspended on the constrained and ga_chg lists of all variables in the constraint, it instantiates the variables to their tentative values (if they have one), and runs the constraint using not not to avoid any side-effects.  If the check fails, the conflict is recorded, and if the propagation flag is set (to 0) the constraint is invoked.

Numerical Constraints and Invariants

If a repair constraint (annotated with r_conflict or r_conflict_prop) is arithmetic, then it involves two expressions Expr1 and Expr2 which are compared (using =,>,< etc.).  Such a constraint is handled using tent_is to compute the tentative value of each expression and unify_to_tent_if_ground_args to instantiate the result in case the expression is ground.
All other repair constraints are handled using monitor_conflict.

Invariants allow tentative values to be propagated through a function (functional constraint) from its inputs to its outputs.
In essence this is achieved by making a copy of the constraint, replacing the input variables by their tentative values.  This copy of the constraint is then invoked, thereby instantiating its outputs.  Finally the output values from the copied constraint are used to update the tentative values of the output variables of the original constraint.

For mathematical invariants (with the form Var tent_is Expr) the expression is first linearized, creating a sum expression of the form C1*V1+C2*V2+...+Cn*Vn  together with none or more nonlinear constraints of the form V=NonLin.
The sum expression allows the invariant to be computed in a way that is independent of the number of terms n.
Specifically if the tentative value of one term changes, the difference between its old and new value is computed, and the tentative value of the whole sum is changed by that amount.  This is done by a demon sum_update.
A separate invariant is created to handle each nonlinear subexpression V=NonLin using tent_call.

All other (non-arithmetic) invariants are handled using tent_call, which is implemented by making a copy of the constraint, as described above.
 

Constant Time Set Membership

A special structure is used for the mon attribute of repair variables, and for the conflict argument of the monitor_conflict predicate.  This structure allows set membership checking and updating in constant time.
The structure of a set element is: elem(Term,InSet,OnList,Set).
Term is the actual element held in the set.
InSet is a 0/1 flag, indicating whether Term is currently in the set.
Set is a structure of the form s(List), where List is a list of elements in the form elem/4.
OnList is another 0/1 flag, indicating whether elem(Term,InSet,OnList,s(List)) is currently in the list List.
Term belongs to the set s(List) if and only if elem(Term,1,1,s(List)) is in the list List.  Consequently this representation employs a cyclic data structure.
Given the structure elem(Term,InSet,OnList,s(List)), checking for membership requires constant time (by just checking the flag InSet), and updating is constant time by either just changing the flag InSet or, if necessary, updating the flag OnList and adding this structure to the head of the list.
The set can be "flushed" when necessary by removing all the elements from the list whose InSet flag is off, and by also setting their OnList flag off.

The constant time set of conflict variables, containing the mon attributes of the repair variables, is in the conflict_vars attribute of the repair_state.
The constant time set of conflict constraints, containing the conflict argument of the monitor_conflict predicates, is in the conflict_hash_constraints (or conflict_constraints) attribute of the repair_state.

Priorities

The priorities of the variable and constraint conflict monitors, and of the invariants, are hard-wired.  They are as follows:
Demon                  Priority
monitor_conflict     8
monitor_tenable     6
sum_update             2
tent_call                  2
The predicate unify_to_tent_if_ground_args has priority 3.