User-Defined Constraints

The fd.pl library defines a set of low-level predicates which allow the user to process domain variables and their domains, modify them and write new constraint predicates.

The fd Attribute

A domain variable is a metaterm. The fd.pl library defines a metaterm attribute

fd with [domain:D, min:Mi, max:Ma, any:A]

which stores the domain information together with several suspension lists. The attribute arguments have the following meaning:

• domain - the representation of the domain itself. Domains are treated as abstract data types, the users should not access them directly, but only using access and modification predicates listed below.

• min - a suspension list that should be woken when the minimum of the domain is updated

• max - a suspension list that should be woken when the maximum of the domain is updated

• any - a suspension list that should be woken when the domain is reduced no matter how.

The suspension list names can be used in the predicate suspend/3 to denote an appropriate waking condition.

The attribute of a domain variable can be accessed with the predicate dvar_attribute/2 or by unification in a matching clause:

get_attribute(_{fd:Attr}, A) :-
    -?->
    Attr = A.

Note however, that this matching clause succeeds even if the first argument is a metaterm but its fd attribute is empty. To succeed only for domain variables, the clause must be

get_attribute(_{fd:Attr}, A) :-
    -?->
    nonvar(Attr),
    Attr = A.

or to access directly attribute arguments, e.g. the domain

get_domain(_{fd:fd with domain:D}, Dom) :-
    -?->
    D = Dom.

The dvar_attribute/2 has the advantage that it returns an attribute-like structure even if its argument is already instantiated, which is quite useful when coding fd constraints.

The attribute arguments can be accessed by macros from the structures.pl library, if e.g. Attr is the attribute of a domain variable, the max list can be obtained as

arg(max of fd, Attr, Max)

or, using a unification

Attr = fd with max:Max

Domain Access

The domains are represented as abstract data types, the users are not supposed to access them directly, instead a number of predicates and macros are available to allow operations on domains.

dom_check_in(+Element, +Dom)

Succeed if the integer Element is in the domain Dom.

dom_compare(?Res, +Dom1, +Dom2)

Works like compare/3 for terms. Res is unified with

• = iff Dom1 is equal to Dom2,

• < iff Dom1 is a proper subset of Dom2,

• > iff Dom2 is a proper subset of Dom1.

Fails if neither domain is a subset of the other one.

dom_member(?Element, +Dom)

Successively instantiate Element to the values in the domain Dom (similar to indomain/1).

dom_range(+Dom, ?Min, ?Max)

Return the minimum and maximum value in the integer domain Dom. Fails if Dom is a domain containing non-integer elements. This predicate can also be used to test if a given domain is integer or not.

dom_size(+Dom, ?Size)

Size is the number of elements in the domain Dom.

Domain Operations

The following predicates operate on domains alone, without modifying domain variables. Most of them return the size of the resulting domain which can be used to test if any modification was done.

dom_copy(+Dom1, -Dom2)

Dom2 is a copy of the domain Dom1. Since the updates are done in-place, two domain variables must not share the same physical domain and so when defining a new variable with an existing domain, the domain has to be copied first.

dom_difference(+Dom1, +Dom2, -DomDiff, ?Size)

The domain DomDifference is Dom1 \ Dom2 and Size is the number of its elements. Fails if Dom1 is a subset of Dom2.

dom_intersection(+Dom1, +Dom2, -DomInt, ?Size)

The domain DomInt is the intersection of domains Dom1 and Dom2 and Size is the number of its elements. Fails if the intersection is empty.

dom_union(+Dom1, +Dom2, -DomUnion, ?Size)

The domain DomUnion is the union of domains Dom1 and Dom2 and Size is the number of its elements. Note that the main use of the predicate is to yield the most specific generalisation of two domains, in the usual cases the domains become smaller, not bigger.

list_to_dom(+List, -Dom)

Convert a list of ground terms and integer intervals into a domain Dom. It does not have to be sorted and integers and intervals may overlap.

integer_list_to_dom(+List, -Dom)

Similar to list_to_dom/2 , but the input list should contain only integers and integer intervals and it should be sorted. This predicate will merge adjacent integers and intervals into larger intervals whenever possible. typically, this predicate should be used to convert a sorted list of integers into a finite domain. If the list is known to already contain proper intervals, sorted_list_to_dom/2 could be used instead.

sorted_list_to_dom(+List, -Dom)

Similar to list_to_dom/2, but the input list is assumed to be already in the correct format, i.e. sorted and with correct integer and interval values. No checking on the list contents is performed.

Accessing Domain Variables

The following predicates perform various operations:

dvar_attribute(+DVar, -Attrib)

Attrib is the attribute of the domain variable DVar. If DVar is instantiated, Attrib is bound to an attribute with a singleton domain and empty suspension lists.

dvar_domain(+DVar, -Dom)

Dom is the domain of the domain variable DVar. If DVar is instantiated, Dom is bound to a singleton domain.

var_fd(?Var, +Dom)

If Var is a free variable, it becomes a domain variable with the domain Dom and with empty suspension lists. The domain Dom is copied to make in-place updates logically sound. If Var is already a domain variable, its domain is intersected with the domain Dom. Fails if Var is not a variable.

dvar_msg(+DVar1, +DVar2, -MsgDVar)

MsgVar is a domain variable which is the most specific generalisation of domain variables or ground values Var1 and Var2.

Modifying Domain Variables

When the domain of a domain variable is reduced, some suspension lists stored in the attribute have to be scheduled and woken.

NOTE: In the fd.pl library the suspension lists are woken precisely when the event associated with the list occurs. Thus e.g. the min list is woken if and only if the minimum value of the variable's domain is changed, but it is not woken when the variable is instantiated to this minimum or when another element from the domain is removed. In this way, user-defined constraints can rely on the fact that when they are executed, the domain was updated in the expected way. On the other hand, user-defined constraints should also comply with this rule and they should take care not to wake lists when their waking condition did not occur. Most predicates in this section actually do all the work themselves so that the user predicates may ignore scheduling and waking completely.

dvar_remove_element(+DVar, +El)

The element El is removed from the domain of DVar and all concerned lists are woken. If the resulting domain is empty, this predicate fails. If it is a singleton, DVar is instantiated. If the domain does not contain the element, no updates are made.

dvar_remove_smaller(+DVar, +El)

Remove all elements in the domain of DVar which are smaller than the integer El and wake all concerned lists. If the resulting domain is empty, this predicate fails; if it is a singleton, DVar is instantiated.

dvar_remove_greater(+DVar, +El)

Remove all elements in the domain of DVar which are greater than the integer El and wake all concerned lists. If the resulting domain is empty, this predicate fails; if it is a singleton, DVar is instantiated.

dvar_update(+DVar, +NewDom)

If the size of the domain NewDom is 0, the predicate fails. If it is 1, the domain variable DVar is instantiated to the value in the domain. Otherwise, if the size of the new domain is smaller than the size of the domain variable's domain, the domain of DVar is replaced by NewDom, the appropriate suspension lists in its attribute are passed to the waking scheduler and so is the constrained list in the suspend attribute of the domain variable. If the size of the new domain is equal to the old one, no updates and no waking is done, i.e. this predicate does not check an explicit equality of both domains. If the size of the new domain is greater than the old one, an error is raised.

dvar_replace(+DVar, +NewDom)

This predicate is similar to dvar_update/2, but it does not propagate the changes, i.e. no waking is done. If the size of the new domain is 1, DVar is not instantiated, but it is given this singleton domain. This predicate is useful for local consistency checks.