Attributed variables provide a technique for extending the Prolog unification algorithm Holzbaur, 1992 by hooking the binding of attributed variables. There is no consensus in the Prolog community on the exact definition and interface to attributed variables. The SWI-Prolog interface is identical to the one realised by Bart Demoen for hProlog Demoen, 2002. This interface is simple and available on all Prolog systems that can run the Leuven CHR system (see chapter 9 and the Leuven CHR page).
Binding an attributed variable schedules a goal to be executed at the first possible opportunity. In the current implementation the hooks are executed immediately after a successful unification of the clause-head or successful completion of a foreign language (built-in) predicate. Each attribute is associated to a module, and the hook (attr_unify_hook/2) is executed in this module. The example below realises a very simple and incomplete finite domain reasoner:
:- module(domain,
[ domain/2 % Var, ?Domain
]).
:- use_module(library(ordsets)).
domain(X, Dom) :-
var(Dom), !,
get_attr(X, domain, Dom).
domain(X, List) :-
list_to_ord_set(List, Domain),
put_attr(Y, domain, Domain),
X = Y.
% An attributed variable with attribute value Domain has been
% assigned the value Y
attr_unify_hook(Domain, Y) :-
( get_attr(Y, domain, Dom2)
-> ord_intersection(Domain, Dom2, NewDomain),
( NewDomain == []
-> fail
; NewDomain = [Value]
-> Y = Value
; put_attr(Y, domain, NewDomain)
)
; var(Y)
-> put_attr( Y, domain, Domain )
; ord_memberchk(Y, Domain)
).
% Translate attributes from this module to residual goals
attribute_goals(X) -->
{ get_attr(X, domain, List) },
[domain(X, List)].
Before explaining the code we give some example queries:
?- domain(X, [a,b]), X = cfail ?- domain(X, [a,b]), domain(X, [a,c]).X = a ?- domain(X, [a,b,c]), domain(X, [a,c]).domain(X, [a, c])
The predicate domain/2 fetches (first clause) or assigns (second clause) the variable a domain, a set of values the variable can be unified with. In the second clause, domain/2 first associates the domain with a fresh variable (Y) and then unifies X to this variable to deal with the possibility that X already has a domain. The predicate attr_unify_hook/2 (see below) is a hook called after a variable with a domain is assigned a value. In the simple case where the variable is bound to a concrete value, we simply check whether this value is in the domain. Otherwise we take the intersection of the domains and either fail if the intersection is empty (first example), assign the value if there is only one value in the intersection (second example), or assign the intersection as the new domain of the variable (third example). The nonterminal attribute_goals//1 is used to translate remaining attributes to user-readable goals that, when called, reinstate these attributes or attributes that correspond to equivalent constraints.
Implementing constraint solvers (chapter 8) is the most common, but not the only use case for attributed variables: If you implement algorithms that require efficient destructive modifications, then using attributed variables is often a more convenient and somewhat more declarative alternative for setarg/3 and related predicates whose sharing semantics are harder to understand. In particular, attributed variables make it easy to express graph networks and graph-oriented algorithms, since each variable can store pointers to further variables in its attributes. In such cases, the use of attributed variables should be confined within a module that exposes its functionality via more declarative interface predicates.
Attribute names are linked to modules. This means that certain operations on attributed variables cause hooks to be called in the module whose name matches the attribute name.
//
The latter property ensures that users can reason about residual goals, and see for themselves whether a constraint library behaves correctly. It is this property that makes it possible to thoroughly test constraint solvers by contrasting obtained residual goals with expected answers.
This nonterminal is used by copy_term/3, on which the Prolog top level relies to ensure the basic invariant of pure Prolog programs: The answer is declaratively equivalent to the query.
The copy_term/3 primitive uses attribute_goals//1 inside a findall/3 call. This implies that attribute_goals//1 can unify variables and modify attributes, for example, to tell other hooks that some attribute has already been taken care of. This nonterminal is also used by frozen/2 which does not create a copy. Ideally attribute_goals//1 should not modify anything to allow direct application in frozen/2. In the current implementation frozen/2 backtracks over attribute_goals//1 to tolerate the current behavior. This work-around harms the performance of frozen/2. New implementations of attribute_goals//1 should avoid relying on backtracking when feasible. Future versions of frozen/2 and copy_term/3 may require attribute_goals//1 not to modify any variables or attributes.
Note that instead of defaulty representations, a Prolog list is used to represent residual goals. This simplifies processing and reasoning about residual goals throughout all programs that need this functionality.
attributes(portray) is in effect. If the hook succeeds the
attribute is considered printed. Otherwise Module = ... is
printed to indicate the existence of a variable. This predicate is
deprecated because it cannot work with pure interface predicates like
copy_term/3.
Use attribute_goals//1 instead to map attributes to residual goals.
maplist(call, Gs)
recreates the attributes for Copy. The nonterminal
attribute_goals//1, as defined in the modules the attributes stem from,
is used to convert attributes to lists of goals.
This building block is used by the top level to report pending attributes in a portable and understandable fashion. This predicate is the preferred way to reason about and communicate terms with constraints.
The form copy_term(Term, Term, Gs) can be used to reason
about the constraints in which Term is involved.
term_attvars(Term,[]) in an efficient test that Term
has
no attributes; scanning the term is aborted after the first
attributed variable is found.
Normal user code should deal with put_attr/3, get_attr/3 and del_attr/2. The routines in this section fetch or set the entire attribute list of a variable. Use of these predicates is anticipated to be restricted to printing and other special purpose operations.
att(Module, Value, MoreAttributes), where MoreAttributes
is
[]