<Section id="u_basic_concepts">
<Title>Basic Concepts</Title>

<p>
This chapter explains the basic concepts of computation with finite
domain constraints in Oz. Further, it explains the implementation of
constraints by propagators. For more details see <Ptr.Extern
to="ozdoc:fdt">.

<SubSection id="u_basic_concepts.computation">
<Title/Computation with Constraints in Oz/
<p>
<para class=apropos><title/Basic Constraint/
A <Em/Basic Constraint/ 
takes the form <Math>x=n, x=y</Math> or
<Math>x \in D</Math>, where <Math>x</Math> and <Math>y</Math> are
variables, <Math>n</Math> is a non-negative integer and <Math>D</Math>
is a finite domain.  
<para class=apropos><title/Constraint Store/
The basic constraints reside in the
<Em/Constraint Store/. Oz provides efficient algorithms to decide
satisfiability and entailment for basic constraints.

<para class=apropos><title/Propagators/
For more expressive constraints, like <Math>x + y = z</Math>, deciding
their satisfiability is not computationally tractable. Such non-basic
constraints are not contained in the constraint store but are imposed by
<Em/propagators/. A propagator is a <Em/computational agent/ which is
<Em/imposed on/ the variables occurring in the corresponding
constraint. These variables are called the propagator's
<Em/parameters/. The propagator tries to narrow the domains of the
variables it is 
imposed on by amplifying the store with basic constraints. 

<para class=apropos><title/Constraint Propagation/
This
narrowing is called <Em/constraint propagation/. A propagator <Math/P/ 
amplifies the store <Math/S/ by writing a basic constraint <Math/\phi/
to it, if <Math/P \wedge S/ entails <Math/\phi/ but <Math/S/ on its
own does not. If <Math/P/ ceases to exist, it is either entailed by
the store <Math/S/, or <Math/P\wedge S/ is unsatisfiable. Note that
the amount of propagation depends on the operational semantics of the
propagator. 
<p>

As an example, assume a store containing <Math/x,y,z \in \{1,\ldots,10\}/.
The propagator for <Math/x+y<z/ narrows the domains to <Math/x,y \in
\{1,\ldots,8\}/ and <Math/z \in \{3,\ldots,10\}/ (since the other values
cannot satisfy the constraint). Adding the constraint <Math/z=5/ causes the
propagator to strengthen the store to <Math/x,y \in \{1,\ldots,3\}/ and
<Math/z=5/. Imposing <Math/x=3/ lets the propagator narrow the domain
of <Math/y/ to 
<Math/1/. We say that the propagator <Math/x+y<z/ <Em/constrains/ the
variables <Math/x,y/ and <Math/z/.
<p>
<para class=apropos><title/Computation Space/
Computation in Oz takes place in so-called
<Em/computation spaces/. For the purpose of the tutorial it is
sufficient to consider a computation space as consisting of the
<Em/constraint store/ and <Em/propagators/ connected to the store.

<SubSection id="u_basic_concepts.impprop">
<Title/Implementation of Propagators/

<p>
The computational model sketched in  <ptr
to="u_basic_concepts.computation"> is realised
by the Oz runtime system, which is implemented by an abstract
machine <ptr to="absmachine">, called the 
<Em/emulator/. In this section, the internal structure of propagators
and their interaction with the emulator is explained. 
<p>
A propagator exists in different execution states and has to be provided
with resources like computation time and heap memory by the
emulator. A propagator synchronises on the constraint store and may amplify
it with basic constraints.
<p>
A propagator <Em/reads/ the basic constraints of its parameters. In the
process of constraint propagation it <Em/writes/ basic constraints to
the store.
<p>
The emulator <Em/resumes/ a propagator when the store has been
amplified in a way the propagator is waiting for. For example, many
propagators will be resumed only in case the bounds of a domain have
been narrowed.

<Para><Title/Handling Propagators/
A propagator is created by the execution of an Oz program. To resume a
propagator if one of its parameters is further constrained, one has to
attach the propagator somehow to the parameters. To this end, a
reference to the propagator is added to so-called <Em/suspension lists/
of the propagator's parameters; we say, a propagator is
<Em/suspending/ on its parameters.

<p>
A resumed propagator returns a value of the predefined type
<<OZ_Return>>:
<p>
<<  enum OZ_Return {OZ_ENTAILED, OZ_FAILED, OZ_SLEEP}>>

<p>
In order to schedule propagators, the emulator maintains for each
propagator an execution state, namely
<<running>>, <<runnable>>, <<sleeping>>, <<entailed>>, and
<<failed>>.  The emulator's scheduler switches a
propagator between the execution states as shown in <ptr
to="propagatorstates">.
<p>
When a propagator is created, its state is
immediately set <<running>> and the scheduler allocates a time slice
for its first run. After every run, when the constraint propagation was
performed, the emulator evaluates the
propagator's return value.

<!-- have to find out how to move pictures automatically to -->
<!-- destination. -->
<figure id="propagatorstates">
<caption/Propagator states and the transitions between them/
<PICTURE.extern display to="propagatorstates.gif" id="propagatorstates.pic" type=GIF>
</figure>

The value <<OZ_FAILED>> is returned if the propagator
(according to its operational semantics) detects its inconsistency with
the store. The emulator sets the propagator's execution state to 
<<failed>> and the computation is aborted. The propagator will be
ignored by the emulator until it is eventually disposed by the next
garbage collection.  
<p>
The return value <<OZ_ENTAILED>> indicates that the
propagator has detected its entailment by the constrained store, 
&ie it cannot further amplify the constraint store. The emulator sets the
propagator's execution state to <<entailed>>.  It happens the same as
for a failed propagator: it will be ignored until it is disposed by
garbage collection.
<p>
If the propagator can neither detect inconsistency nor entailment, it
returns <<OZ_SLEEP>>. Because the propagator may amplify the
store in the future, it remains in the suspension lists. Its execution
state is set to <<sleeping>>.
<p>
A propagator is resumed when the domain of at least one of its parameters is
further narrowed.  In this case, the emulator scans the suspension list
of that variable and either deletes entries where the propagator's
execution state is <<failed>> &resp <<entailed>> 
or switches the execution state of the corresponding
propagator to <<runnable>>. This is indicated by transition (1) in
<ptr to=propagatorstates>. Now, the scheduler takes care of
the propagator and 
will schedule it later on (the transition (2) from <<runnable>> to
<<running>> is subject to the scheduler's policy and will be not
discussed here).
<p>
The parameters of a propagator are stored in its  state. Hence, reading
and writing of basic constraints is  
done by the propagator itself.  If a propagator constrains a
variable according to its operational semantics, it informs the emulator
that the corresponding suspension lists have to be scanned.
