\chapter{Constraint Logic Programming}	\label{sec:clp}
\index{CLP}
\index{constraint programming}

This chapter describes the extensions primarily designed to support
\textbf{constraint logic programming}~(CLP), an important declarative
programming paradigm with countless practical applications.

CLP($X$) stands for constraint logic programming over the domain~$X$.
Plain Prolog can be regarded as~CLP($H$), where $H$ stands for
\textit{Herbrand~terms}\index{Herbrand term}. Over this domain,
\predref{=}{2} and dif/2 are the most important constraints that
express, respectively, equality and disequality of~terms. Plain Prolog
can thus be regarded as a special~case of~CLP.

There are dedicated constraint solvers for several important domains:

\begin{itemize}
\item CLP(FD) for \textbf{integers} (\secref{clpfd})
\item CLP(B) for \textbf{Boolean} variables (\secref{clpb})
\item CLP(Q) for \textbf{rational} numbers (\secref{lib:clpqr})
\item CLP(R) for \textbf{floating point} numbers (\secref{lib:clpqr}).
\end{itemize}

In addition, CHR (\chapref{chr}) provides a general purpose constraint
handling language to reason over user-defined constraints.

Constraints blend in naturally into Prolog programs, and behave
exactly like plain Prolog predicates in those cases that can also be
expressed without constraints. However, there are two key differences
between constraints and plain Prolog predicates:

\begin{itemize}
\item Constraints can \textit{delay} checks until their truth can be
  safely decided. This feature can significantly increase the
  \textit{generality} of your programs, and preserves their relational
  nature.

\item Constraints can take into account everything you state about the
  entities you reason about, independent of the order in which you
  state it, both \textit{before} and also \textit{during} any search
  for concrete solutions. Using available information to prune parts
  of the search space is called constraint
  \jargon{propagation}\index{propagation}, and it is performed
  automatically by the available constraint solvers for their
  respective domains. This feature can significantly increase the
  \textit{performance} of your programs.
\end{itemize}

Due to these two key advantages over plain Prolog, CLP has become an
extremely important declarative programming paradigm in practice.

Among its most important and typical instances is CLP(FD), constraint
logic programming over~\textit{integers}. For example, using
constraints, you can state in the most general way that a
variable~\arg{X} is an integer greater than~0. If, later, \arg{X} is
bound to a concrete integer, the constraint solver automatically
ensures this. If you in addition constrain~\arg{X} to integers less
than~3, the constraint solver combines the existing knowledge to infer
that \arg{X} is either 1 or~2 (see below). To obtain concrete values
for~\arg{X}, you can ask the solver to \jargon{label}~\arg{X} and
produce 1 and 2 on backtracking. See~\secref{clpfd}.

\begin{code}
?- use_module(library(clpfd)).
...
true.

?- X #> 0, X #< 3.
X in 1..2.

?- X #> 0, X #< 3, indomain(X).
X = 1 ;
X = 2.
\end{code}

Contrast this with plain Prolog, which has no efficient means to deal
with (integer) $X > 0$ and $X < 3$. At best it could translate $X > 0$
to \term{between}{1, infinite, X} and a similar primitive for $X <
3$. If the two are combined it has no choice but to generate and test
over this infinite two-dimensional space.

Using constraints therefore makes your program more
\jargon{declarative}\index{declarative} in that it frees you from some
procedural aspects and limitations of Prolog.

When working with constraints, keep in mind the following:

\begin{itemize}
    \item As with plain Prolog, \predref{!}{0} also destroys the
    declarative semantics of constraints.  A cut after a goal that is
    delayed may prematurely prune the search space, because the truth
    of delayed goals is not yet established. There are several ways to
    avoid cuts in constraint logic programs, retaining both generality
    and determinism of your programs.  See for example zcompare/3.
    \item Term-copying operations (assertz/1, retract/1, findall/3,
    copy_term/2, etc.) generally also copy constraints.  The effect
    varies from ok, silent copying of huge constraint networks
    to violations of the internal consistency of constraint
    networks.  As a rule of thumb, copying terms holding attributes
    must be deprecated. If you need to reason about a term that is
    involved in constraints, use copy_term/3 to obtain the constraints
    as Prolog goals, and use these goals for further processing.
\end{itemize}

All of the mentioned constraint solvers are implemented using the
attributed variables interface described in~\secref{attvar}. These are
lower-level predicates that are mainly intended for library authors,
not for typical Prolog programmers.

\section{Attributed variables}			\label{sec:attvar}

\jargon{Attributed variables} provide a technique for extending the
Prolog unification algorithm \cite{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 \cite{Demoen:CW350}. This interface is simple and available on
all Prolog systems that can run the Leuven CHR system (see \chapref{chr}
and the Leuven \href{https://dtai.cs.kuleuven.be/CHR/}{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:

\begin{code}
:- 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)].
\end{code}


Before explaining the code we give some example queries:

\begin{quote}
\begin{tabular}{ll}
\tt ?- domain(X, [a,b]), X = c		     & fail \\
\tt ?- domain(X, [a,b]), domain(X, [a,c]).   & X = a \\
\tt ?- domain(X, [a,b,c]), domain(X, [a,c]). & domain(X, [a, c]) \\
\end{tabular}
\end{quote}

The predicate \nopredref{domain}{2} fetches (first clause) or assigns
(second clause) the variable a \emph{domain}, a set of values the
variable can be unified with. In the second clause,
\nopredref{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 (\chapref{clp}) 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.

\subsection{Attribute manipulation predicates}
\label{sec:attvar-predicates}

\begin{description}
    \predicate{attvar}{1}{{@}Term}
Succeeds if \arg{Term} is an attributed variable. Note that var/1 also
succeeds on attributed variables.  Attributed variables are created with
put_attr/3.

    \predicate{put_attr}{3}{+Var, +Module, +Value}
If \arg{Var} is a variable or attributed variable, set the value for the
attribute named \arg{Module} to \arg{Value}. If an attribute with this
name is already associated with \var{Var}, the old value is replaced.
Backtracking will restore the old value (i.e., an attribute is a mutable
term; see also setarg/3). This predicate raises an uninstantiation error if
\arg{Var} is not a variable, and a type error if \arg{Module} is not an atom.

    \predicate{get_attr}{3}{+Var, +Module, -Value}
Request the current \arg{value} for the attribute named \arg{Module}.  If
\arg{Var} is not an attributed variable or the named attribute is not
associated to \arg{Var} this predicate fails silently.  If \arg{Module}
is not an atom, a type error is raised.

    \predicate{del_attr}{2}{+Var, +Module}
Delete the named attribute.  If \arg{Var} loses its last attribute it
is transformed back into a traditional Prolog variable.  If \arg{Module}
is not an atom, a type error is raised. In all other cases this
predicate succeeds regardless of whether or not the named attribute is
present.
\end{description}


\subsection{Attributed variable hooks}
\label{sec:attvar-hooks}

Attribute names are linked to modules. This means that certain
operations on attributed variables cause \jargon{hooks} to be called in
the module whose name matches the attribute name.

\begin{description}
    \predicate{attr_unify_hook}{2}{+AttValue, +VarValue}
A hook that must be defined in the module to which an attributed variable
refers. It is called \emph{after} the attributed variable has been
unified with a non-var term, possibly another attributed variable.
\arg{AttValue} is the attribute that was associated to the variable
in this module and \arg{VarValue} is the new value of the variable.
If this predicate fails, the unification fails. If \arg{VarValue} is
another attributed variable the hook often combines the two attributes
and associates the combined attribute with \arg{VarValue} using
put_attr/3.

\begin{tags}
    \tag{To be done}
The way in which this hook currently works makes the implementation of
important classes of constraint solvers impossible or at least
extremely impractical. For increased generality and convenience,
simultaneous unifications as in \exam{[X,Y]=[0,1]} should be processed
sequentially by the Prolog engine, or a more general hook should be
provided in the future. See \cite{clpb:Triska2016} for more
information.
\end{tags}

    \dcg{attribute_goals}{1}{+Var}
This nonterminal is the main mechanism in which residual constraints
are obtained. It is called in every module where it is defined, and
\arg{Var} has an attribute. Its argument is that variable. In each
module, attribute_goals//1 must describe a list of Prolog goals that
are declaratively equivalent to the goals that caused the attributes
of that module to be present and in their current state. It is always
possible to do this (since these attributes stem from such goals), and
it is the responsibility of constraint library authors to provide this
mapping without exposing any library internals. Ideally and typically,
remaining relevant attributes are mapped to \jargon{pure} and
potentially simplified Prolog goals that satisfy both of the
following:

\begin{itemize}
\item They are declaratively equivalent to the constraints that were
originally posted.

\item They use only predicates that are themselves exported and
documented in the modules they stem from.
\end{itemize}

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 \textit{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 \emph{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 \jargon{defaulty} representations, a Prolog
\textit{list} is used to represent residual goals. This simplifies
processing and reasoning about residual goals throughout all programs
that need this functionality.

    \predicate{project_attributes}{2}{+QueryVars, +ResidualVars}
A hook that can be defined in each module to project constraints on
newly introduced variables back to the query variables.
\arg{QueryVars} is the list of variables occurring in the query and
\arg{ResidualVars} is a list of variables that have attributes
attached. There may be variables that occur in both lists.
If possible, project_attributes/2 should change the attributes so that
all constraints are expressed as residual goals that refer only to
\arg{QueryVars}, while other variables are existentially quantified.

    \predicate[deprecated]{attr_portray_hook}{2}{+AttValue, +Var}
Called by write_term/2 and friends for each attribute if the option
\term{attributes}{portray} is in effect.  If the hook succeeds the
attribute is considered printed.  Otherwise \exam{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.
\end{description}

\subsection{Operations on terms with attributed variables}
\label{sec:terms-with-attvars}

\begin{description}
    \predicate{copy_term}{3}{+Term, -Copy, -Gs}
Create a regular term \arg{Copy} as a copy of \arg{Term} (without
any attributes), and a list \arg{Gs} of goals that represents the attributes.
The goal \texttt{maplist(call, Gs)} recreates the attributes for \arg{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 \texttt{copy_term(Term, Term, Gs)} can be used to reason
about the constraints in which \texttt{Term} is involved.

    \predicate{copy_term_nat}{2}{+Term, -Copy}
As copy_term/2.  Attributes, however, are \emph{not} copied but replaced
by fresh variables.

    \predicate{term_attvars}{2}{+Term, -AttVars}
\arg{AttVars} is a list of all attributed variables in \arg{Term} and
its attributes. That is, term_attvars/2 works recursively through
attributes. This predicate is cycle-safe. The goal
\term{term_attvars}{Term, []} in an efficient test that \arg{Term} has
\emph{no} attributes; scanning the term is aborted after the first
attributed variable is found.
\end{description}


\subsection{Special purpose predicates for attributes}
\label{sec:attvar-low-level-preds}

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.

\begin{description}
    \predicate{get_attrs}{2}{+Var, -Attributes}
Get all attributes of \arg{Var}. \arg{Attributes} is a term of the form
\term{att}{Module, Value, MoreAttributes}, where \arg{MoreAttributes} is
\const{[]} for the last attribute.

    \predicate{put_attrs}{2}{+Var, -Attributes}
Set all attributes of \arg{Var}.  See get_attrs/2 for a description of
\arg{Attributes}.

    \predicate{del_attrs}{1}{+Var}
If \arg{Var} is an attributed variable, delete \emph{all} its
attributes.  In all other cases, this predicate succeeds without
side-effects.
\end{description}


\section{Coroutining}				\label{sec:coroutining}

Coroutining allows us to delay the execution of Prolog goals until
their truth can be safely decided.

Among the most important coroutining predicates is dif/2, which
expresses \textit{disequality} of terms in a sound way. The actual
test is delayed until the terms are sufficiently different, or have
become identical. For example:

\begin{code}
?- dif(X, Y), X = a, Y = b.
X = a,
Y = b.

?- dif(X, Y), X = a, Y = a.
false.
\end{code}

There are also lower-level coroutining predicates that are intended as
building blocks for higher-level constraints. For example, we can use
freeze/2 to define a variable that can only be assigned an atom:

\begin{code}
?- freeze(X, atom(X)), X = a.
X = a.
\end{code}

In this case, calling atom/1 earlier causes the whole query to fail:

\begin{code}
?- atom(X), X = a.
false.
\end{code}

If available, domain-specific constraints should be used in such
cases.  For example, to state that a variable can only assume even
integers, use the CLP(FD) constraint \predref{#=}{2}:

\begin{code}
?- X mod 2 #= 0.
X mod 2#=0.
\end{code}

Importantly, domain-specific constraints can apply stronger
propagation by exploiting logical properties of their respective
domains. For example:

\begin{code}
?- X mod 2 #= 0, X in 1..3.
X = 2.
\end{code}

Remaining constraints, such as \exam{X mod 2\#=0} in the example above,
are called \jargon{residual}\index{residual} goals. They are said to
\jargon{flounder}\index{flounder}, because their truth is not yet
decided. Declaratively, the query is only true if all residual goals
are satisfiable. Use call_residue_vars/2 to collect all variables that
are involved in constraints.

\begin{description}
    \predicate{dif}{2}{@{A}, @{B}}
The dif/2 predicate is a \textit{constraint} that is true if and only
if \arg{A} and \arg{B} are different terms. If \arg{A} and \arg{B} can
never unify, dif/2 succeeds deterministically. If \arg{A} and \arg{B}
are identical, it fails immediately. Finally, if \arg{A} and \arg{B}
can unify, goals are delayed that prevent \arg{A} and \arg{B} to
become equal. It is this last property that makes dif/2 a more general
and more declarative alternative for \predref{\=}{2} and related
predicates.

This predicate behaves as if defined by
\verb$dif(X, Y) :- when(?=(X,Y), X \== Y)$.
See also \predref{?=}{2}.  The implementation can deal
with cyclic terms.

The dif/2 predicate is realised using attributed variables associated
with the module \const{dif}.  It is an autoloaded predicate that is
defined in the library \pllib{dif}.

    \predicate{freeze}{2}{+Var, :Goal}
Delay the execution of \arg{Goal} until \arg{Var} is bound (i.e., is
not a variable or attributed variable).	 If \arg{Var} is bound on entry
freeze/2 is equivalent to call/1.  The freeze/2 predicate is realised
using an attributed variable associated with the module \const{freeze}.
See also frozen/2.

    \predicate[det]{frozen}{2}{@{Term}, -Goal}
Unify \arg{Goal} with the goal or conjunction of goals delayed on
some attributed variable in \arg{Term}. If \arg{Term} is free of
attributed variables, \arg{Goal} is unified to \const{true}. Note that
frozen/2 reports all delayed goals, not only those delayed due to
freeze/2. The goals are extracted using copy_term/3.\footnote{Versions
prior to 8.3.7 only report goals delayed using freeze/2 on a plain
variable. The new behaviour is compatible with SICStus.}  See also
term_attvars/2 and call_residue_vars/2.

    \predicate{when}{2}{@{Condition}, :Goal}
Execute \arg{Goal} when \arg{Condition} becomes true.  \arg{Condition}
is one of \term{?=}{X, Y}, \term{nonvar}{X}, \term{ground}{X},
\term{,}{Cond1, Cond2} or \term{;}{Cond1, Cond2}.  See also freeze/2
and dif/2.  The implementation can deal with cyclic terms in \arg{X} and \arg{Y}.

The when/2 predicate is realised using attributed variables associated
with the module \const{when}.  It is defined in the autoload library
\pllib{when}.

    \predicate{call_residue_vars}{2}{:Goal, -Vars}
Find residual attributed variables left by \arg{Goal}. This predicate
is intended for reasoning about and debugging programs that use
coroutining or constraints.  To see why this predicate is necessary,
consider a predicate that poses contradicting constraints on a
variable, and where that variable does not appear in any argument of
the predicate and hence does not yield any residual goals on the
toplevel when the predicate is invoked.  Such programs should fail,
but sometimes succeed because the constraint solver is too weak to
detect the contradiction. Ideally, delayed goals and constraints are
all executed at the end of the computation. The meta predicate
call_residue_vars/2 finds variables that are given attributes
or whose attributes are modified by \arg{Goal}, regardless of whether
or not these variables are reachable from the arguments of
\arg{Goal}.\footnote{The implementation of call_residue_vars/2 is
completely redone in version 7.3.2 (7.2.1) after discussion with Bart
Demoen. The current implementation no longer performs full scans of the
stacks. The overhead is proportional to the number of attributed
variables on the stack, dead or alive.}.
\end{description}