\chapter{Special Variables and Coroutining}	\label{sec:extvar}

This chapter deals with extensions primarily designed to support
constraint logic programming (CLP). The low-level attributed variable
interface defined in \secref{attvar} is not intended for the typical
Prolog programmer. Instead, the typical Prolog programmer should use the
coroutining predicates and the various constraint solvers built on top
of attributed variables. CHR (\chapref{chr}) provides a general purpose
constraint handling language.

As a rule of thumb, constraint programming reduces the search space by
reordering goals and joining goals based on domain knowledge. A typical
example is constraint reasoning over integer domains. Plain Prolog has
no efficient means to deal with (integer) $X > 0$ and $X < 3$. At best
it could translate $X > 0$ with uninstantiated X 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. Instead, a constraint system will \jargon{delay}
an uninstantiated goal to $X > 0$. If, later, it finds a value for
\arg{X} it will execute the test. If it finds $X < 3$ it will combine
this knowledge to infer that X is in 1..2 (see below). If it never finds a
concrete value for \arg{X} it can be asked to \jargon{label} \arg{X} and
produce 1 and 2 on backtracking. See \secref{clpfd}.

\begin{code}
1 ?- [library(clpfd)].
...
true.

2 ?- X #> 0, X #< 3.
X in 1..2.
\end{code}

Using constraints generally makes your program more
\jargon{declarative}. There are some caveats though:

\begin{itemize}
    \item Constraints and cuts do not merge well.  A cut after a goal
    that is delayed prunes the search space before the condition
    is true.
    \item Term-copying operations (assert/1, retract/2, 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.
\end{itemize}


\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 \url[CHR
page]{http://people.cs.kuleuven.be/~tom.schrijvers/CHR/}).

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, 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/3 is used to translate remaining attributes to
user-readable goals that, when executed, reinstate these attributes.

\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 a representation 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.
Normally this predicate fails to veto binding the variable to
\arg{VarValue}, forcing backtracking to undo the binding.  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.

    \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.  New infrastructure
dealing with communicating attribute values must be based on
copy_term/3 and its hook attribute_goals//1.

    \dcg{attribute_goals}{1}{+Var}
This nonterminal, if it is defined in a module, is used by copy_term/3
to project attributes of that module to residual goals. It is also
used by the top level to obtain residual goals after executing a query.

    \predicate{project_attributes}{+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.
\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 maplist(call,\arg{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.

    \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 deals with having Prolog goals scheduled for execution as
soon as some conditions are fulfilled.  In Prolog the most commonly
used condition is the instantiation (binding) of a variable. Scheduling
a goal to execute immediately after a variable is bound can
be used to avoid instantiation errors for some built-in predicates
(e.g.\ arithmetic), do work \jargon{lazy}, prevent the binding of
a variable to a particular value, etc.  Using freeze/2 for example
we can define a variable that can only be assigned an even number:

\begin{code}
?- freeze(X, X mod 2 =:= 0), X = 3

No
\end{code}

\begin{description}
    \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}.
Use \exam{frozen(Var, Goal)} to find out whether
and which goals are delayed on \arg{Var}.

    \predicate{frozen}{2}{@{Var}, -Goal}
Unify \arg{Goal} with the goal or conjunction of goals delayed on
\arg{Var}.  If no goals are frozen on \arg{Var}, \arg{Goal} is unified
to \const{true}.

    \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{dif}{2}{@{A}, @{B}}
The dif/2 predicate provides a constraint stating that \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, and finally, if \arg{A} and \arg{B} can unify,
goals are delayed that prevent \arg{A} and \arg{B} to become equal. The
dif/2 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 defined in the autoload library
\pllib{dif}.

    \predicate{call_residue_vars}{2}{:Goal, -Vars}
Find residual attributed variables left by \arg{Goal}. This predicate is
intended for debugging programs using coroutining or constraints.
Consider a program that poses contradicting constraints on a variable.
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 attribute
variables 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}


\section{Global variables}			\label{sec:gvar}

Global variables are associations between names (atoms) and terms.
They differ in various ways from storing information using assert/1
or recorda/3.

\begin{itemize}
    \item The value lives on the Prolog (global) stack.  This implies
          that lookup time is independent of the size of the term.
	  This is particularly interesting for large data structures
	  such as parsed XML documents or the CHR global constraint
	  store.

    \item They support both global assignment using nb_setval/2 and
          backtrackable assignment using b_setval/2.

    \item Only one value (which can be an arbitrary complex Prolog
	  term) can be associated to a variable at a time.

    \item Their value cannot be shared among threads.  Each thread
          has its own namespace and values for global variables.

    \item Currently global variables are scoped globally.  We may
          consider module scoping in future versions.
\end{itemize}

Both b_setval/2 and nb_setval/2 implicitly create a variable if the
referenced name does not already refer to a variable.

Global variables may be initialised from directives to make them
available during the program lifetime, but some considerations are
necessary for saved states and threads. Saved states do not store global
variables, which implies they have to be declared with initialization/1
to recreate them after loading the saved state.  Each thread has
its own set of global variables, starting with an empty set.  Using
thread_initialization/1 to define a global variable it will be
defined, restored after reloading a saved state and created in all
threads that are created \emph{after} the registration.  Finally,
global variables can be initialised using the exception hook
exception/3.  The latter technique is used by CHR (see \chapref{chr}).


\begin{description}
    \predicate{b_setval}{2}{+Name, +Value}
Associate the term \arg{Value} with the atom \arg{Name} or replace
the currently associated value with \arg{Value}.  If \arg{Name} does
not refer to an existing global variable, a variable with initial value
\const{[]} is created (the empty list).  On backtracking the
assignment is reversed.

    \predicate{b_getval}{2}{+Name, -Value}
Get the value associated with the global variable \arg{Name} and unify
it with \arg{Value}. Note that this unification may further instantiate
the value of the global variable. If this is undesirable the normal
precautions (double negation or copy_term/2) must be taken. The
b_getval/2 predicate generates errors if \arg{Name} is not an atom or
the requested variable does not exist.
\end{description}

\begin{description}
    \predicate{nb_setval}{2}{+Name, +Value}
Associates a copy of \arg{Value} created with duplicate_term/2
with the atom \arg{Name}.  Note that this can be used to set an
initial value other than \const{[]} prior to backtrackable assignment.

    \predicate{nb_getval}{2}{+Name, -Value}
The nb_getval/2 predicate is a synonym for b_getval/2, introduced for
compatibility and symmetry.  As most scenarios will use a particular
global variable using either non-backtrackable or backtrackable
assignment, using nb_getval/2 can be used to document that the
variable is non-backtrackable. Raises \term{existence_error}{variable,
Name} if the variable does not exist.

    \predicate{nb_linkval}{2}{+Name, +Value}
Associates the term \arg{Value} with the atom \arg{Name} without copying
it. This is a fast special-purpose variation of nb_setval/2 intended for
expert users only because the semantics on backtracking to a point
before creating the link are poorly defined for compound terms. The
principal term is always left untouched, but backtracking behaviour on
arguments is undone if the original assignment was \jargon{trailed} and
left alone otherwise, which implies that the history that created the
term affects the behaviour on backtracking. Consider the
following example:

\begin{code}
demo_nb_linkval :-
	T = nice(N),
	(   N = world,
	    nb_linkval(myvar, T),
	    fail
	;   nb_getval(myvar, V),
	    writeln(V)
	).
\end{code}

    \predicate{nb_current}{2}{?Name, ?Value}
Enumerate all defined variables with their value. The order of
enumeration is undefined. Note that nb_current/2 can be used as an
alternative for nb_getval/2 to request the value of a variable and fail
silently if the variable does not exists.

    \predicate{nb_delete}{1}{+Name}
Delete the named global variable.  Succeeds also if the named variable
does not exist.
\end{description}


\subsection{Compatibility of SWI-Prolog Global Variables}
\label{sec:gvars-compat}

Global variables have been introduced by various Prolog implementations
recently.  The implementation of them in SWI-Prolog is based on hProlog
by Bart Demoen. In discussion with Bart it was decided that the
semantics of hProlog nb_setval/2, which is equivalent to nb_linkval/2,
is not acceptable for normal Prolog users as the behaviour is influenced
by how built-in predicates that construct terms (read/1, =../2, etc.) are
implemented.

GNU-Prolog provides a rich set of global variables, including arrays.
Arrays can be implemented easily in SWI-Prolog using functor/3 and
setarg/3 due to the unrestricted arity of compound terms.