<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>A Traps and Pitfalls</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="node46.html#chapter.scheduling"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="node53.html#appendix.golden-rules">Next >></A></TD></TR></TABLE><DIV id="appendix.traps"><H1><A name="appendix.traps">A Traps and Pitfalls</A></H1><P>This section lists traps and pitfalls that beginners typically fall into when writing their first finite domain problem scripts in Oz. </P><DIV class="unnumbered"><H2><A name="label163">Ordinary Arithmetic Blocks</A></H2><P>There is a big difference between the statement </P><BLOCKQUOTE class="code"><CODE>X<SPAN class="keyword">+</SPAN>Y <SPAN class="keyword">=:</SPAN> Z</CODE></BLOCKQUOTE><P> and the statement </P><BLOCKQUOTE class="code"><CODE>X<SPAN class="keyword">+</SPAN>Y = Z</CODE></BLOCKQUOTE><P> The first statement creates a concurrent finite domain propagator and never blocks. The second statement creates an addition task that blocks until its arguments <CODE>X</CODE> and <CODE>Y</CODE> are known. Blocking means that the statements following the addition statement will not be executed. </P><P>This pitfall can be particulary malicious if the infix expressions <CODE>(X <SPAN class="keyword">mod</SPAN> Y)</CODE> or <CODE>(X <SPAN class="keyword">div</SPAN> Y)</CODE> are used. For instance, </P><BLOCKQUOTE class="code"><CODE>X <SPAN class="keyword">mod</SPAN> Y <SPAN class="keyword">=:</SPAN> Z</CODE></BLOCKQUOTE><P> is equivalent to </P><BLOCKQUOTE class="code"><CODE><SPAN class="keyword">local</SPAN> A <SPAN class="keyword">in</SPAN> <BR> X <SPAN class="keyword">mod</SPAN> Y = A<BR> A <SPAN class="keyword">=:</SPAN> Z <BR><SPAN class="keyword">end</SPAN></CODE></BLOCKQUOTE><P> and will thus block until <CODE>X</CODE> and <CODE>Y</CODE> are determined. In contrast, a statement like </P><BLOCKQUOTE class="code"><CODE>U <SPAN class="keyword">+</SPAN> X<SPAN class="keyword">*</SPAN>(Y<SPAN class="keyword">-</SPAN>Z) <SPAN class="keyword">=:</SPAN> <SPAN class="keyword">~</SPAN>Y</CODE></BLOCKQUOTE><P> is fine since the operations <CODE><SPAN class="keyword">+</SPAN></CODE>, <CODE><SPAN class="keyword">*</SPAN></CODE>, <CODE><SPAN class="keyword">-</SPAN></CODE>, and <CODE><SPAN class="keyword">~</SPAN></CODE> are implemented by the created propagator. The general rule behind this is simple: The infix operators <CODE><SPAN class="keyword">=:</SPAN></CODE>, <CODE><SPAN class="keyword">\=:</SPAN></CODE> </P><BLOCKQUOTE class="code"><CODE>:</CODE></BLOCKQUOTE><P>, <CODE><SPAN class="keyword">>:</SPAN></CODE>, <CODE><SPAN class="keyword">=<:</SPAN></CODE>, and <CODE><SPAN class="keyword">>=:</SPAN></CODE> absorp the arithmetic operators <CODE><SPAN class="keyword">+</SPAN></CODE>, <CODE><SPAN class="keyword">-</SPAN></CODE>, <CODE><SPAN class="keyword">*</SPAN></CODE>, and <CODE><SPAN class="keyword">~</SPAN></CODE>, and no others. </P><P>Incidentally, interval and domain propagators for the modulo constraint can be created with the procedures <CODE>{FD<SPAN class="keyword">.</SPAN>modI X Y Z}</CODE> and <CODE>{FD<SPAN class="keyword">.</SPAN>modD X Y Z}</CODE>, respectively (see <A href="node6.html#section.constraints.intdom">Section 2.4</A>). </P><P>There is an easy way to check whether a statement in a script blocks: Just insert as last statement </P><BLOCKQUOTE class="code"><CODE>{Browse <SPAN class="string">'End of script reached'</SPAN>}</CODE></BLOCKQUOTE><P> and check in the Browser. If <CODE><SPAN class="string">'End of script reached'</SPAN></CODE> appears in the Browser when you execute the script (e.g. with the Explorer), no statement in the script can have blocked, except for those that have been explicitly parallelized with <CODE><SPAN class="keyword">thread</SPAN> <SPAN class="keyword">...</SPAN> <SPAN class="keyword">end</SPAN></CODE>.</P></DIV><DIV class="unnumbered"><H2><A name="label164">Delay of Propagators</A></H2><P>Almost all propagators start their work only after all variables occurring in the implemented constraint are constrained to finite domains in the constraint store. For instance, the propagator created by </P><BLOCKQUOTE class="code"><CODE>X<SPAN class="keyword">*</SPAN>47 <SPAN class="keyword">=:</SPAN> _</CODE></BLOCKQUOTE><P> will never start propagation since it will wait forever that the anonymous variable created by the wildcard symbol <CODE>_</CODE> is constrained to a finite domain. This problem can easily be avoided by writing </P><BLOCKQUOTE class="code"><CODE>X<SPAN class="keyword">*</SPAN>47 <SPAN class="keyword">=:</SPAN> {FD<SPAN class="keyword">.</SPAN>decl}</CODE></BLOCKQUOTE><P> The procedure <CODE>{FD<SPAN class="keyword">.</SPAN>decl X}</CODE> constrains its argument to the largest finite domain possible (i. e. <CODE>0<SPAN class="keyword">#</SPAN>sup</CODE>).</P></DIV><DIV class="unnumbered"><H2><A name="label165">The Operators <CODE><SPAN class="keyword">=:</SPAN></CODE> and <CODE><SPAN class="keyword">::</SPAN></CODE> don't Introduce Pattern Variables</A></H2><P>The statement </P><BLOCKQUOTE class="code"><CODE><SPAN class="keyword">local</SPAN> X <SPAN class="keyword">=:</SPAN> Y<SPAN class="keyword">+</SPAN>Z <SPAN class="keyword">in</SPAN> </CODE>...<CODE> <SPAN class="keyword">end</SPAN></CODE></BLOCKQUOTE><P> does not declare <CODE>X</CODE> as local variable, which is in contrast to the statement </P><BLOCKQUOTE class="code"><CODE><SPAN class="keyword">local</SPAN> X = Y<SPAN class="keyword">+</SPAN>Z <SPAN class="keyword">in</SPAN> </CODE>...<CODE> <SPAN class="keyword">end</SPAN></CODE></BLOCKQUOTE><P> which however does not create a propagator. The desired effect can be obtained by writing </P><BLOCKQUOTE class="code"><CODE><SPAN class="keyword">local</SPAN> X = {FD<SPAN class="keyword">.</SPAN>decl} <SPAN class="keyword">in</SPAN> X <SPAN class="keyword">=:</SPAN> Y<SPAN class="keyword">+</SPAN>Z </CODE>...<CODE> <SPAN class="keyword">end</SPAN></CODE></BLOCKQUOTE><P> A related pitfall is the wrong assumtion that a statement </P><BLOCKQUOTE class="code"><CODE><SPAN class="keyword">local</SPAN> X <SPAN class="keyword">::</SPAN> 4<SPAN class="keyword">#</SPAN>5 <SPAN class="keyword">in</SPAN> </CODE>...<CODE> <SPAN class="keyword">end</SPAN></CODE></BLOCKQUOTE><P> declares <CODE>X</CODE> as local variable. This is not the case. To obtain the desired effect, you can write </P><BLOCKQUOTE class="code"><CODE><SPAN class="keyword">local</SPAN> X = {FD<SPAN class="keyword">.</SPAN>int 4<SPAN class="keyword">#</SPAN>5} <SPAN class="keyword">in</SPAN> </CODE>...<CODE> <SPAN class="keyword">end</SPAN></CODE></BLOCKQUOTE><P></P></DIV><DIV class="unnumbered"><H2><A name="label166">Delay of Domain Specifications</A></H2><P>A domain specification like <CODE>X<SPAN class="keyword">::</SPAN>L<SPAN class="keyword">#</SPAN>U</CODE> constrains <CODE>X</CODE> only after both <CODE>L</CODE> and <CODE>U</CODE> are determined. Thus </P><BLOCKQUOTE class="code"><CODE>L <SPAN class="keyword">::</SPAN> 5<SPAN class="keyword">#</SPAN>13 <BR>U <SPAN class="keyword">::</SPAN> 14<SPAN class="keyword">#</SPAN>33<BR>X <SPAN class="keyword">::</SPAN> L<SPAN class="keyword">#</SPAN>U</CODE></BLOCKQUOTE><P> will constrain <CODE>X</CODE> only after both <CODE>L</CODE> and <CODE>U</CODE> have been determined.</P></DIV><DIV class="unnumbered"><H2><A name="label167">Coreferences are not Always Realized</A></H2><P>The propagator created by </P><BLOCKQUOTE class="code"><CODE>A<SPAN class="keyword">*</SPAN>A <SPAN class="keyword">+</SPAN> B<SPAN class="keyword">*</SPAN>B <SPAN class="keyword">=:</SPAN> C<SPAN class="keyword">*</SPAN>C</CODE></BLOCKQUOTE><P> provides much less propagation than the four propagators created by </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>times A A} <SPAN class="keyword">+</SPAN> {FD<SPAN class="keyword">.</SPAN>times B B} <SPAN class="keyword">=:</SPAN> {FD<SPAN class="keyword">.</SPAN>times C C}</CODE></BLOCKQUOTE><P> The reason is that the first propagator does not realize the coreferences in the constraint it implements, that is, it treats the two occurrences of <CODE>A</CODE>, say, as if they were independent variables. On the other hand, the propagator created by <CODE>{FD<SPAN class="keyword">.</SPAN>times A A $}</CODE> exploits this coreference to provide better propagation. The Pythagoras Puzzle (see <A href="node32.html#section.propagators.pythagoras">Section 7.2</A>) is a problem, where exploiting coreferences is essential).</P></DIV><DIV class="unnumbered"><H2><A name="label168">Large Numbers</A></H2><P>There is an implementation-dependent upper bound for the integers that can occur in a finite domain stored in the constraint store. This upper bound is available as the value of <CODE>FD<SPAN class="keyword">.</SPAN>sup</CODE>. In Mozart, <CODE>FD<SPAN class="keyword">.</SPAN>sup</CODE> is <IMG alt="134\,\,217\,\,726" src="latex351.png"> on Linux and Sparc platforms.</P><P>The same restriction applies to constants appearing in propagators. For instance, the creation of a propagator </P><BLOCKQUOTE class="code"><CODE>X<SPAN class="keyword">*</SPAN>Y <SPAN class="keyword"><:</SPAN> 900<SPAN class="keyword">*</SPAN>1000<SPAN class="keyword">*</SPAN>1000</CODE></BLOCKQUOTE><P> will result in a run-time error since the constant <IMG alt="900\,\,000\,\,000" src="latex352.png"> computed by the compiler is larger than <CODE>FD<SPAN class="keyword">.</SPAN>sup</CODE>. There is a trick that solves the problem for some cases. The trick consists in giving a large number as a product involving an auxiliary variable: </P><BLOCKQUOTE class="code"><CODE><SPAN class="keyword">local</SPAN> A = 900 <SPAN class="keyword">in</SPAN> <BR> X<SPAN class="keyword">*</SPAN>Y <SPAN class="keyword"><:</SPAN> A<SPAN class="keyword">*</SPAN>1000<SPAN class="keyword">*</SPAN>1000<BR><SPAN class="keyword">end</SPAN></CODE></BLOCKQUOTE><P> The trick exploits that propagators can compute internally with integers larger than <CODE>FD<SPAN class="keyword">.</SPAN>sup</CODE>, and that the compiler does not eliminate the auxiliary variable. The Grocery Puzzle in <A href="node21.html#section.elimination.grocery">Section 4.1</A> uses this trick.</P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node46.html#chapter.scheduling"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="node53.html#appendix.golden-rules">Next >></A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~schulte/">Christian Schulte</A> and <A href="http://www.ps.uni-sb.de/~smolka/">Gert Smolka</A><BR><SPAN class="version">Version 1.4.0 (20090610)</SPAN></ADDRESS></BODY></HTML>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
bd5c3d824c3db63ffd9226c15941e6ad
>
files
>
1228
