/usr/share/mozart/doc/cpitut/node5.html is in mozart-doc 1.4.0-8ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>1.4 Imposing Propagators</TITLE><LINK href="ozdoc.css" rel="stylesheet" type="text/css"></HEAD><BODY><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node4.html#u_replacing"><< Prev</A></TD><TD><A href="node1.html">- Up -</A></TD><TD><A href="node6.html#u_vectors">Next >></A></TD></TR></TABLE><DIV id="u_nesting"><H2><A name="u_nesting">1.4 Imposing Propagators</A></H2><P>The C<SPAN class="allcaps">PI</SPAN> provides a generic way to implement different schemes for imposing propagators. This section discusses the following issues:</P><P></P><UL><LI><P>How to implement a nestable propagator. </P><P> It is explained how to make the addition propagator of <A href="node3.html#u_getting_started">Section 1.2</A> nestable. </P></LI><LI><P>How to extend the class <CODE>OZ_Expect</CODE> to cope with structured parameters. </P></LI></UL><P></P><P>The answers to these questions will be used in later sections, for example, when we come to implement propagators imposed on more than just single variables. </P><DIV id="u_nesting.basic"><H3><A name="u_nesting.basic">1.4.1 Basic Concepts</A></H3><P>A propagator is imposed by a C/C++ function, a so-called <EM>header function</EM>, that is connected to an Oz abstraction. The application of such an abstraction results in calling the corresponding header function and finally in imposing the propagator. </P><DIV class="apropos"><P class="margin">C<SPAN class="allcaps">PI</SPAN> class <CODE>OZ_Expect</CODE></P><P> The class <CODE>OZ_Expect</CODE> provides the functionality to fulfill the tasks mentioned above. It provides member functions to control the imposition of a propagator and to determine the constraints which have to be present in the store before a propagator is imposed. </P></DIV><P>The class <CODE>OZ_Expect</CODE> provides a group of member functions to examine the constraints of a propagator's parameters. The names of these member functions begin with <CODE>expect</CODE>. The basic idea is to define for each parameter a constraint <IMG alt="\phi" src="latex11.png"> (expected to be present in the store) in terms of <CODE>expect</CODE> member functions and to decide whether <IMG alt="\phi" src="latex11.png"> is entailed resp. disentailed by the store (by evaluating the return value of the <CODE>expect</CODE> function expressing the constraint <IMG alt="\phi" src="latex11.png">). If entailment of <IMG alt="\phi" src="latex11.png"> for a parameter cannot be decided yet then the constraint in the store for this parameter is <EM>insufficient</EM>. </P><P>The type of the return value allows to handle structured parameters. The definition of the return type is as follows. </P><P><CODE> struct OZ_expect_t { int size<SPAN class="keyword">,</SPAN> accepted; } </CODE> </P><P>The meaning of the fields <CODE>size</CODE> and <CODE>accepted</CODE> is explained by the following examples. </P><P></P><DL><DT>Example 1.</DT><DD><P>Assume a parameter is expected to be an integer, then the field <CODE>size</CODE> of the returned value is 1. In case this parameter is currently a variable then the field <CODE>accepted</CODE> is 0. An inconsistent constraint, like for instance a literal, would be indicated by -1. The value 1 in the field <CODE>accepted</CODE> for our example means that the examined parameter is an integer. </P></DD><DT>Example 2.</DT><DD><P>Let us suppose we expect a parameter to be a vector with <IMG alt="n" src="latex6.png"> integer fields, where a vector is either a closed record, a tuple, or a list. First the parameter is expected to be a vector (which is one constraint expected to be found in the store) and then all its <IMG alt="n" src="latex6.png"> elements are to be integers, which determines the field <CODE>size</CODE> of the return value to be <IMG alt="n+1" src="latex37.png">. If the field <CODE>accepted</CODE> is also <IMG alt="n+1" src="latex37.png">, then all expected constraints are present. Otherwise appropriate action has to be taken, for example, suspending the execution of the header function. The implementation to check for a vector of finite domain variable is discussed in <A href="node5.html#u_nesting.basic">Section 1.4.1</A>. </P></DD></DL><P> </P><P>An instance of the class <CODE>OZ_Expect</CODE> maintains two sets, namely <IMG alt="A" src="latex38.png"> and <IMG alt="B" src="latex39.png">. In the course of checking parameters <CODE>expect</CODE> member functions collect variables in either of these two sets. Variables which are constrained according to the corresponding <CODE>expect</CODE> function are added to set <IMG alt="A" src="latex38.png">. All the other variables are added to set <IMG alt="B" src="latex39.png">. The <CODE>expect</CODE> function for finite domain variables has an extra argument to determine the event which resumes the propagator, for example only narrowing of the bounds of the domain. This information is maintained in the sets too. </P><P>Leaving a header function by calling the member function <CODE>suspend</CODE> (see <A href="../cpiref/node2.html#expect.control">Section 1.2.5 of ``The Mozart Constraint Extensions Reference''</A>) causes the header function to be resumed if variables collected in set <IMG alt="B" src="latex39.png"> are further constrained. </P><P>Calling <CODE>OZ_Expect<SPAN class="keyword">::</SPAN>impose()</CODE> introduces the propagator which is passed as argument to the runtime system and makes the propagator resume if at least one variable of both sets is constrained in a way defined by the corresponding <CODE>expect</CODE> function. Additionally, variables in set <IMG alt="B" src="latex39.png"> are constrained to be finite domain variables. This will be used for the implementation of nestable propagators. </P><P></P></DIV><DIV id="u_nesting.impose"><H3><A name="u_nesting.impose">1.4.2 Imposing Nestable Propagators</A></H3><P>In <A href="node3.html#u_getting_started.creating">Section ``Creating a Propagator''</A> not too much attention was paid to propagator imposition. Now more details will be given by the example of a nestable propagator. Let us consider the following Oz code. </P><P><CODE> {FD<SPAN class="keyword">.</SPAN>times {FD<SPAN class="keyword">.</SPAN>plus U V} {FD<SPAN class="keyword">.</SPAN>plus X Y} Z} </CODE> </P><P>The propagator <CODE>FD<SPAN class="keyword">.</SPAN>plus</CODE> is required to be <EM>nestable</EM>, since one of its parameters is syntactically not accessible and cannot be constrained to a finite domain variable by explicit Oz code. The expansion of the above code makes it clear. </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">local</SPAN> A1 A2 <SPAN class="keyword">in</SPAN> <BR> {FD<SPAN class="keyword">.</SPAN>plus U V A1}<BR> {FD<SPAN class="keyword">.</SPAN>plus X Y A2}<BR> {FD<SPAN class="keyword">.</SPAN>times A1 A2 Z}<BR><SPAN class="keyword">end</SPAN></PRE></BLOCKQUOTE><P> </P><P>Due to lexical scoping the implicit variables <CODE>A1</CODE> and <CODE>A2</CODE> are inaccessible to outside code. Therefore the two <CODE>FD<SPAN class="keyword">.</SPAN>plus</CODE> propagators must constrain <CODE>A1</CODE> and <CODE>A2</CODE> to finite domain variables before they are imposed. To simplify the implementation of header functions for propagators, the C<SPAN class="allcaps">PI</SPAN> provides three macros. </P><P></P><DL><DT><CODE>OZ_EXPECTED_TYPE(S)</CODE> </DT><DD><P>defines a C/C++ string <CODE>S</CODE> typically consisting of a number of substrings separated by commas which describe the constraint expected at the corresponding argument position. The first substring corresponds to the first argument with index 0, the second one to the second argument with index 1 and so on. The substrings are used to generate meaningful messages in case an inconsistent constraint is detected. There are predefined macros (starting with <CODE>OZ_EM_</CODE> defining strings for the possible constraints to be expected. For details see <A href="../cpiref/node2.html#expect.macros">Section 1.2.6 of ``The Mozart Constraint Extensions Reference''</A>. The macro <CODE>OZ_EXPECTED_TYPE</CODE> is required by <CODE>OZ_EXPECT</CODE> and <CODE>OZ_EXPECT_SUSPEND</CODE>. </P></DD><DT><CODE>OZ_EXPECT(O<SPAN class="keyword">,</SPAN> P<SPAN class="keyword">,</SPAN> F)</CODE></DT><DD><P>checks if the argument at position <CODE>P</CODE> (<CODE>P</CODE> is a C integer with a value starting from 0) is constrained according to the semantics of <CODE>F</CODE> (which is an <CODE>expect</CODE> member function of class <CODE>O</CODE>). The type of <CODE>F</CODE> has to be <CODE>OZ_Expect_t O<SPAN class="keyword">::</SPAN>F(OZ_Term)</CODE>. The value of <CODE>O</CODE> has to be an instance of the class <CODE>OZ_Expect</CODE> or a class inheriting from it. In case an inconsistent or insufficient constraint is detected, the appropriate action is taken <A href="node5.html#label2"><SUP>1</SUP></A> and the C/C++ function is left by a <CODE>return</CODE> statement. Otherwise, the execution proceeds to the next statement in the header function. </P></DD><DT><CODE>OZ_EXPECT_SUSPEND(O<SPAN class="keyword">,</SPAN> P<SPAN class="keyword">,</SPAN> F<SPAN class="keyword">,</SPAN> SC)</CODE></DT><DD><P>is similar to <CODE>OZ_EXPECT</CODE> except for the case that the constraint defined by <CODE>F</CODE> is currently not yet entailed. Then it increments the value of <CODE>SC</CODE> which is expect to be of type <CODE>int</CODE> and proceeds to the next statement in the header function. </P></DD></DL><P> </P><P>In <A href="node3.html#u_getting_started.creating">Section ``Creating a Propagator''</A> the macro <CODE>OZ_EXPECT</CODE> was already used for the non-nestable addition propagator. The macro <CODE>OZ_EXPECT_SUSPEND</CODE> is provided to implement nestable propagators. Insufficient constraints for a parameter cause it to increment its argument <CODE>SC</CODE>. Allowing exactly one argument to be insufficiently constrained implements a nestable propagator. </P><P>Therefore the header function has to suspend in case more than one parameter is insufficiently constrained. The class <CODE>OZ_Expect</CODE> therefore provides the member function <CODE>suspend()</CODE> which expects a value of type <CODE>OZ_Thread</CODE>. Details on how to create a thread for a C/C++ function can be found in <A href="../foreign/node17.html#section.threads">Section 7.10 of ``Interfacing to C and C++''</A>. </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="functionname">OZ_BI_define</SPAN>(fd_add_nestable, 3, 0)<BR>{<BR> OZ_EXPECTED_TYPE(OZ_EM_FD<SPAN class="string">","</SPAN>OZ_EM_FD<SPAN class="string">","</SPAN>OZ_EM_FD);<BR> <BR> <SPAN class="type">OZ_Expect</SPAN> <SPAN class="variablename">pe</SPAN>;<BR> <SPAN class="type">int</SPAN> <SPAN class="variablename">susp_count</SPAN> = 0;<BR> <BR> OZ_EXPECT_SUSPEND(pe,0,expectIntVar,susp_count);<BR> OZ_EXPECT_SUSPEND(pe,1,expectIntVar,susp_count);<BR> OZ_EXPECT_SUSPEND(pe,2,expectIntVar,susp_count);<BR> <BR> <SPAN class="keyword">if</SPAN> (susp_count > 1) <BR> <SPAN class="keyword">return</SPAN> pe.suspend();<BR> <BR> <SPAN class="keyword">return</SPAN> pe.impose(<SPAN class="keyword">new</SPAN> <SPAN class="type">AddProp</SPAN>(OZ_in(0),<BR> OZ_in(1),<BR> OZ_in(2)));<BR>}<BR>OZ_BI_end<BR> <BR></PRE></BLOCKQUOTE><P> </P><P>The variable <CODE>susp_count</CODE> is passed to the <CODE>OZ_EXPECT_SUSPEND</CODE> macros and if it is greater than 1 the function <CODE>fd_add_nestable()</CODE> is suspended. Otherwise the propagator is imposed. </P></DIV><DIV id="u_nesting.customize"><H3><A name="u_nesting.customize">1.4.3 Customizing <CODE>OZ_Expect</CODE></A></H3><P>The propagators implemented so far are imposed on single finite domain variables. The propagators will be resumed whenever an arbitrary element of a domain of its parameters is removed. But more elaborate propagators may have more demanding requirements concerning their resumption resp.parameter structure. Therefore the following frequently occurring requirements will be discussed in this section. </P><P></P><UL><LI><P>Often it is <EM>not</EM> desirable to resume a propagator as soon as any arbitrary element is removed from the domain of one of its parameters. For instance, one might want to suspend resumption until a domain becomes a singleton domain. </P></LI><LI><P>One wants to pass structured parameters to a propagator. In <A href="node6.html#u_vectors">Section 1.5</A> a propagator will be implemented that expects a vector of finite domain variables. </P></LI></UL><P> </P><P>The <CODE>expect</CODE> member functions are used to define new <CODE>expect</CODE> functions which specify the constraints for each parameter of a propagator which have to be entailed by the store to enable the imposition of the propagator. To conform with the macros <CODE>OZ_EXPECT</CODE> and <CODE>OZ_EXPECT_SUSPEND</CODE> the type of the resulting <CODE>expect</CODE> function has to be <CODE>OZ_expect_t (O<SPAN class="keyword">::*</SPAN>)(OZ_Term)</CODE>, where <CODE>O</CODE> is either <CODE>OZ_Expect</CODE> or a class inheriting from it. </P><P>The new member function <CODE>expectIntVarSingl()</CODE> is implemented as member function of class <CODE>ExtendedExpect</CODE> inheriting from <CODE>OZ_Expect</CODE>. The definition of the member function <CODE>expectIntVarSingl()</CODE> which causes a propagator to be resumed when a variable is constrained to an integer, uses </P><P></P><BLOCKQUOTE class="code"><CODE> <BR>OZ_Expect<SPAN class="keyword">::</SPAN>expectIntVar(OZ_Term t<SPAN class="keyword">,</SPAN> <BR> OZ_FDPropState ps);</CODE></BLOCKQUOTE><P> </P><P>provided by the C<SPAN class="allcaps">PI</SPAN> . The second argument <CODE>ps</CODE> determines the event for resuming the propagator. For details on the values determining the resumption event see <A href="../cpiref/node2.html#expect.types">Section 1.2.1 of ``The Mozart Constraint Extensions Reference''</A>.</P><P>The following code defines the class <CODE>ExtendedExpect</CODE> with the member function <CODE>expectIntVarSingl()</CODE>. </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">class</SPAN> <SPAN class="type">ExtendedExpect</SPAN> : <SPAN class="keyword">public</SPAN> <SPAN class="type">OZ_Expect</SPAN> {<BR><SPAN class="keyword">public</SPAN>:<BR> <SPAN class="type">OZ_expect_t</SPAN> <SPAN class="functionname">expectIntVarSingl</SPAN>(<SPAN class="type">OZ_Term</SPAN> <SPAN class="variablename">t</SPAN>) {<BR> <SPAN class="keyword">return</SPAN> expectIntVar(t, fd_prop_singl);<BR> }<BR></PRE></BLOCKQUOTE><P> </P><P>The definition of an <CODE>expect</CODE> function for vectors is similar. The C<SPAN class="allcaps">PI</SPAN> provides for the function </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">typedef</SPAN> <SPAN class="type">OZ_expect_t</SPAN> (<SPAN class="reference">O</SPAN>::*<SPAN class="type">OZ_ExpectMeth</SPAN>)(OZ_Term);<BR><SPAN class="type">OZ_expect_t</SPAN> <SPAN class="reference">OZ_Expect</SPAN>::<SPAN class="functionname">expectVector</SPAN>(<SPAN class="type">OZ_Term</SPAN> <SPAN class="variablename">v</SPAN>,<BR> <SPAN class="type">OZ_ExpectMeth</SPAN> <SPAN class="variablename">f</SPAN>);<BR></PRE></BLOCKQUOTE><P> </P><P>which can be used to define a new instance of <CODE>expectVector</CODE> with the required signature <CODE>OZ_expect_t (O<SPAN class="keyword">::*</SPAN>)(OZ_Term)</CODE>. The semantics of <CODE>expectVector</CODE> defines that <CODE>v</CODE> is a vector and all elements of the vector are constrained according to <CODE>f</CODE>, which is an <CODE>expect</CODE> function too. </P><P>Note that for a member function passed to <CODE>expectVector</CODE>, defined in a class inheriting from <CODE>OZ_Expect</CODE>, the cast <CODE>OZ_ExpectMeth</CODE> is necessary, since the type system of C/C++ cannot figure out by itself that the type of the function passed is admissible. </P><P>The following code is part of the definition of class <CODE>ExtendedExpect</CODE>. </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">private</SPAN>:<BR> <SPAN class="type">OZ_expect_t</SPAN> <SPAN class="functionname">_expectIntVarAny</SPAN>(<SPAN class="type">OZ_Term</SPAN> <SPAN class="variablename">t</SPAN>) {<BR> <SPAN class="keyword">return</SPAN> expectIntVar(t, fd_prop_any);<BR> }<BR><SPAN class="keyword">public</SPAN>:<BR> <SPAN class="type">OZ_expect_t</SPAN> <SPAN class="functionname">expectVectorIntVarAny</SPAN>(<SPAN class="type">OZ_Term</SPAN> <SPAN class="variablename">t</SPAN>) {<BR> <SPAN class="keyword">return</SPAN> expectVector(t, <BR> (OZ_ExpectMeth) &_expectIntVarAny);<BR> }<BR> <SPAN class="type">OZ_expect_t</SPAN> <SPAN class="functionname">expectVectorIntVarSingl</SPAN>(<SPAN class="type">OZ_Term</SPAN> <SPAN class="variablename">t</SPAN>) {<BR> <SPAN class="keyword">return</SPAN> expectVector(t, <BR> (OZ_ExpectMeth) &expectIntVarSingl);<BR> }<BR></PRE></BLOCKQUOTE><P> </P><P>The implementation of the propagators discussed in the next sections assumes the existence of the class <CODE>ExtendedExpect</CODE>. </P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node4.html#u_replacing"><< Prev</A></TD><TD><A href="node1.html">- Up -</A></TD><TD><A href="node6.html#u_vectors">Next >></A></TD></TR></TABLE><HR align="left" width="30%"><DIV class="footnote"><A name="label2">1. </A>For example, in case of a detected inconsistency an error message is emitted and the header function returns <CODE>OZ_FAILED</CODE> to the runtime system. </DIV><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~tmueller/">Tobias Müller</A><BR><SPAN class="version">Version 1.4.0 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|