/usr/share/mozart/doc/system/node26.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>5.12 Distribution</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="node25.html#section.fd.misc"><< Prev</A></TD><TD><A href="node14.html">- Up -</A></TD><TD><A href="node27.html#section.fd.assignment">Next >></A></TD></TR></TABLE><DIV id="section.fd.distribution"><H2><A name="section.fd.distribution">5.12 Distribution</A></H2><P>In this section it is shown how Oz supports distribution with constraints. The following procedure creates binary choice-points for variables. The choice is delayed until propagation has reached a fixed point. Assume <CODE>Dv</CODE> to be a vector of finite domain integers. The distribution differs in the order of the choice-points and in the constraint with which is distributed. Essentially, it works as follows </P><UL class="enum"><LI><P>Select an element <CODE>D</CODE> of <CODE>Dv</CODE> which is not determined.</P></LI><LI><P>Select a value or a domain specification <CODE>Spec</CODE> in the current domain of <CODE>D</CODE>. </P></LI><LI><P>Create a choice point for <CODE>X<SPAN class="keyword">::</SPAN>Spec</CODE> and <CODE>X<SPAN class="keyword">::</SPAN>compl(Spec)</CODE>. </P></LI><LI><P>If not all elements of <CODE>Dv</CODE> are determined, go to step 1.</P></LI></UL><P> The order of <CODE>Dv</CODE> is preserved. </P><DL><DT><A name="label274"></A> <CODE>distribute</CODE></DT><DD><BLOCKQUOTE class="synopsis"><P></P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>distribute </CODE><CODE>+<I>Dist</I></CODE><CODE> </CODE><CODE>+<I>Xv</I></CODE><CODE>}</CODE></BLOCKQUOTE><P></P></BLOCKQUOTE></DD><DD><P>The vector <CODE><I>Xv</I></CODE> is distributed according to the specification <CODE><I>Dist</I></CODE>. <CODE><I>Dist</I></CODE> may be either the atom <CODE>naive</CODE>, <CODE>ff</CODE> (for first-fail), <CODE>split</CODE> or a record with label <CODE>generic</CODE>: </P><UL><LI><P><CODE>naive</CODE>: <CODE><I>Xv</I></CODE> must be a vector of finite domain integers. Considers only non-determined elements of <CODE><I>Xv</I></CODE>. Chooses the leftmost variable <CODE>X</CODE> in <CODE><I>Xv</I></CODE>. Creates a choice point for <CODE>X=L</CODE> and <CODE>X<SPAN class="keyword">\=:</SPAN>L</CODE>, where <CODE>L</CODE> is the lower bound of the domain of <CODE>X</CODE>. </P></LI><LI><P><CODE>ff</CODE>: <CODE><I>Xv</I></CODE> must be a vector of finite domain integers. Considers only non-determined elements of <CODE><I>Xv</I></CODE>. Chooses the leftmost variable <CODE>X</CODE> in <CODE><I>Xv</I></CODE>, whose domain size is minimal. Creates a choice point for <CODE>X=L</CODE> and <CODE>X<SPAN class="keyword">\=:</SPAN>L</CODE>, where <CODE>L</CODE> is the lower bound of the domain of <CODE>X</CODE>. </P></LI><LI><P><CODE>split</CODE>: <CODE><I>Xv</I></CODE> must be a vector of finite domain integers. Considers only non-determined elements of <CODE><I>Xv</I></CODE>. Chooses the leftmost variable <CODE>X</CODE> in <CODE><I>Xv</I></CODE>, whose domain size is minimal. Creates a choice point for <CODE>X<SPAN class="keyword">=<:</SPAN>M</CODE> and <CODE>X<SPAN class="keyword">>:</SPAN>M</CODE>, where <CODE>M</CODE> is the middle of the domain of <CODE>X</CODE> (see <CODE>FD<SPAN class="keyword">.</SPAN>reflect<SPAN class="keyword">.</SPAN>mid</CODE>). </P></LI><LI><P></P><BLOCKQUOTE class="code"><CODE>generic(order: </CODE><CODE>+<I>Order</I></CODE><CODE> <SPAN class="keyword"><=</SPAN> size<BR> filter: </CODE><CODE>+<I>Filter</I></CODE><CODE> <SPAN class="keyword"><=</SPAN> undet<BR> select: </CODE><CODE>+<I>Select</I></CODE><CODE> <SPAN class="keyword"><=</SPAN> id<BR> value: </CODE><CODE>+<I>Value</I></CODE><CODE> <SPAN class="keyword"><=</SPAN> min<BR> procedure: </CODE><CODE>+<I>Proc</I></CODE><CODE> <SPAN class="keyword"><=</SPAN> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN>} <SPAN class="keyword">skip</SPAN> <SPAN class="keyword">end</SPAN>)</CODE></BLOCKQUOTE><P> Considers only those elements in <CODE><I>Xv</I></CODE>, for which <CODE><I>Filter</I></CODE> is true. Chooses the leftmost element, which is minimal with respect to <CODE><I>Order</I></CODE> and selects the corresponding variable <CODE>D</CODE> by <CODE><I>Select</I></CODE>. Creates a choice point for <CODE>D<SPAN class="keyword">::</SPAN>Spec</CODE> and <CODE>D<SPAN class="keyword">::</SPAN>compl(Spec)</CODE>, where <CODE>Spec</CODE> is selected by <CODE>Value</CODE>. </P><P>The values under the respective features must be as follows:</P><P></P><UL><LI><P><CODE><I>Order</I></CODE>: </P><UL><LI><P>Binary boolean function <CODE>P</CODE>: Selects the leftmost element in <CODE><I>Xv</I></CODE> which is minimal with respect to the order relation <CODE>P</CODE>. </P></LI><LI><P><CODE>naive</CODE>: Selects the leftmost variable. </P></LI><LI><P><CODE>size</CODE>: Selects the leftmost variable, whose domain is minimal. </P></LI><LI><P><CODE>min</CODE>: Selects the leftmost variable, whose lower bound is minimal. </P></LI><LI><P><CODE>max</CODE>: Selects the leftmost variable, whose upper bound is maximal. </P></LI><LI><P><CODE>nbSusps</CODE>: Selects the variable with the largest number of suspensions. If several variables suspend on the maximal number of constraints, the leftmost variable whose domain is minimal is selected. </P></LI></UL><P></P></LI><LI><P><CODE><I>Filter</I></CODE>: </P><UL><LI><P>Unary boolean function <CODE>P</CODE>: Considers only the elements <CODE>X</CODE> in <CODE><I>Xv</I></CODE>, for which <CODE>{P X}</CODE> yields <CODE><SPAN class="keyword">true</SPAN></CODE>. </P></LI><LI><P><CODE>undet</CODE>: Considers only undetermined variables.</P></LI></UL><P></P></LI><LI><P><CODE><I>Select</I></CODE>: </P><UL><LI><P>Unary function <CODE>P</CODE>: Selects the variable to enumerate from the selected element by <CODE><I>Order</I></CODE> and <CODE><I>Filter</I></CODE>. </P></LI><LI><P><CODE>id</CODE>: The variable to enumerate is the selected element.</P></LI></UL><P></P></LI><LI><P><CODE><I>Value</I></CODE>: </P><UL><LI><P>Binary procedure <CODE>P</CODE>: Takes a variable as first argument, and binds its second argument to a domain descriptor <CODE>D</CODE> to serve as the restriction on said variable to be used in a binary distribution step (<CODE>D</CODE> in one branch, <CODE>compl(D)</CODE> in the other). </P></LI><LI><P><CODE>min</CODE>: Selects the lower bound of the domain. </P></LI><LI><P><CODE>max</CODE>: Selects the upper bound of the domain. </P></LI><LI><P><CODE>mid</CODE>: Selects the element, which is closest to the middle of the domain (the arithmetical means between the lower and upper bound of the domain). In case of ties, the smaller element is selected. </P></LI><LI><P><CODE>splitMin</CODE>: Selects the interval from the lower bound to the middle of the domain (see <CODE>mid</CODE>). </P></LI><LI><P><CODE>splitMax</CODE>: Selects the interval from the element following the middle to the upper bound of the domain (see <CODE>mid</CODE>). </P></LI></UL><P></P></LI><LI><P><CODE><I>Proc</I></CODE>: Is applied when stability is reached. Since this application may cause instability, distribution is continued when stability is reached again. </P></LI></UL><P> Note, that in case <CODE><I>Det</I></CODE> is <CODE>det</CODE> or in case <CODE><I>Order</I></CODE> is <CODE>size</CODE>, <CODE>lower</CODE>, <CODE>upper</CODE>, or <CODE>nbSusps</CODE>, the elements of <CODE><I>Xv</I></CODE> must be finite domain integers. </P><P>For example, <CODE>{FD<SPAN class="keyword">.</SPAN>distribute ff Dv}</CODE> can be expressed as </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>distribute generic Dv}<SPAN class="keyword">,</SPAN></CODE></BLOCKQUOTE><P> <CODE>{FD<SPAN class="keyword">.</SPAN>distribute split Dv}</CODE> as </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>distribute generic(value: splitMin) Dv}<SPAN class="keyword">,</SPAN></CODE></BLOCKQUOTE><P> and <CODE>{FD<SPAN class="keyword">.</SPAN>distribute naive Dv}</CODE> as </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>distribute generic(order: naive) Dv}</CODE></BLOCKQUOTE><P></P></LI></UL><P> The naive distribution can also be defined as follows using the <CODE>value</CODE> feature. </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>distribute <BR>generic(value: <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> D}<BR> {FD<SPAN class="keyword">.</SPAN>reflect<SPAN class="keyword">.</SPAN>min D}<BR> <SPAN class="keyword">end</SPAN>) Ds}</CODE></BLOCKQUOTE><P> </P></DD><DT><A name="label276"></A> <CODE>choose</CODE></DT><DD><BLOCKQUOTE class="synopsis"><P></P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>choose </CODE><CODE>+<I>Dist</I></CODE><CODE> </CODE><CODE>+<I>Xv</I></CODE><CODE> </CODE><CODE>?<I>X</I></CODE><CODE> </CODE><CODE>?<I>Spec</I></CODE><CODE>}</CODE></BLOCKQUOTE><P></P></BLOCKQUOTE></DD><DD><P>Chooses the element <CODE><I>X</I></CODE> in <CODE><I>Xv</I></CODE> according to the description <CODE><I>Dist</I></CODE>. A specification <CODE><I>Spec</I></CODE> for the element <CODE><I>X</I></CODE> is returned according to the description <CODE><I>Dist</I></CODE>. The parameter <CODE><I>Dist</I></CODE> is defined in the same way as for <CODE>FD<SPAN class="keyword">.</SPAN>distribute</CODE> except for the value selection. If the feature <CODE>value</CODE> is used for generic distribution, the field must be constrained to a unary function <CODE>P</CODE> which selects a value from the domain of the selected variable (see below for an example). For example, </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>choose ff Xs E S}</CODE></BLOCKQUOTE><P> selects the element <CODE>E</CODE> in the list <CODE>Xs</CODE> according to the first-fail strategy and binds <CODE>S</CODE> to the current lower bound of <CODE>E</CODE>. </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>choose generic(value:splitMin) Xv E S}</CODE></BLOCKQUOTE><P> selects the element <CODE>E</CODE> in the list <CODE>Xs</CODE> according to the first-fail strategy and binds <CODE>S</CODE> to the pair <CODE>0<SPAN class="keyword">#</SPAN>M</CODE>, where <CODE>M</CODE> is the result of <CODE>{FD<SPAN class="keyword">.</SPAN>reflect<SPAN class="keyword">.</SPAN>mid E}</CODE>. For the naive distribution strategy, the following may be used. </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>choose generic(value: <SPAN class="keyword">fun</SPAN>{<SPAN class="functionname">$</SPAN> X}<BR> {FD<SPAN class="keyword">.</SPAN>reflect<SPAN class="keyword">.</SPAN>min X}<BR> <SPAN class="keyword">end</SPAN>)<BR> Xv E S}</CODE></BLOCKQUOTE><P></P></DD></DL><P></P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node25.html#section.fd.misc"><< Prev</A></TD><TD><A href="node14.html">- Up -</A></TD><TD><A href="node27.html#section.fd.assignment">Next >></A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~duchier/">Denys Duchier</A>, <A href="http://www.ps.uni-sb.de/~kornstae/">Leif Kornstaedt</A>, <A href="http://www.ps.uni-sb.de/~homik/">Martin Homik</A>, <A href="http://www.ps.uni-sb.de/~tmueller/">Tobias Müller</A>, <A href="http://www.ps.uni-sb.de/~schulte/">Christian Schulte</A> and <A href="http://www.info.ucl.ac.be/~pvr">Peter Van Roy</A><BR><SPAN class="version">Version 1.4.0 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|