Invariants

For writing sophisticated search algorithms it is useful to be able not only to detect conflicts caused by tentative value changes, but also to compute consequences of these changes. For example, it is possible to repair certain constraints automatically by (re)computing one or more of their variable's tentative values based on the others (e.g. a sum constraint can be repaired by updating the tentative value of the sum variable whenever the tentative value of one of the other variables changes). We provide two predicates for this purpose:

-Result tent_is +Expression

This is similar to the normal arithmetic is/2 predicate, but evaluates the expression based on the tentative assignment of its variables. The result is delivered as (an update to) the tentative value of the Result variable. Once initiated, tent_is will stay active and keep updating Result's tentative value eagerly whenever the tentative assignment of any variable in Expression changes.

tent_call(In, Out, Goal)

This is a completely general meta-predicate to support computations with tentative values. Goal is a general goal, and In and Out are lists (or other terms) containing subsets of Goal's variables. A copy of Goal is called, with the In-variables replaced by their tentative values and the Out-variables replaced by fresh variables. Goal is expected to return values for the Out variables. These values are then used to update the tentative values of the original Out variables. This process repeats whenever the tentative value of any In-variable changes.

Waking on Tentative Assignment Change

The predicates tent_is/2 and tent_call/3 are implemented using the ga_chg suspension list which is attached to every repair variable. The programmer has therefore all the tools to write specialised, efficient versions of tent_call/3. Follow the following pattern:

my_invariant(In, Out) :-
        In tent_get TentIn,
        ... compute TentOut from TentIn ...
        suspend(my_invariant(In,Out,Susp), 3, [In->ga_chg]),
        Out tent_set TentOut.

This can be made more efficient by using a demon (demon/1).