Sophie

Sophie

distrib > Mandriva > 2010.0 > i586 > media > contrib-release > by-pkgid > bd5c3d824c3db63ffd9226c15941e6ad > files > 1189

mozart-1.4.0-1mdv2010.0.i586.rpm

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>3.4 New Primitives</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="node16.html#section.problem.explorer">&lt;&lt; Prev</A></TD><TD><A href="node13.html">- Up -</A></TD><TD><A href="node18.html#section.problem.watching">Next &gt;&gt;</A></TD></TR></TABLE><DIV id="section.problem.primitives"><H2><A name="section.problem.primitives">3.4 New Primitives</A></H2><P> This section gives you an idea of the new Oz primitives needed to express search engines and finite domain scripts. </P><P>The new primitives come in two orthogonal groups. The first group provides the ability to create and distribute spaces and to explore search trees. This ability is essential for the implementation of search engines based on the propagate and distribute paradigm. As was mentioned before, this paradigm is general and applies also to constraints other than finite domain constraints. </P><P>The second group of primitives provides the ability to create finite domain propagators and to tell domain constraints to the constraint store. It also provides the ability to access the domain of a variable in the current constraint store, an expressivity needed for programming distribution strategies. </P><P class="margin">first-class spaces</P><P> Oz provides spaces as first-class citizens that can be created, distributed, and killed, among other things. A <A name="label50"></A><EM>first-class space</EM> is almost like Oz's unique top-level space, where regular computation takes place. Like the top-level space, first-class spaces have a constraint store, a procedure store, and a cell store and can host any number of threads. One important difference between the top-level and first-class spaces is the treatment of failure, which is considered an error at the top level and a regular event in first-class spaces (<EM>this space has no solution</EM>). </P><P class="margin">attributes of global objects cannot be assigned</P><P> The <A name="label51"></A><EM>parent</EM> of a first-class space is the space that created it. The constraint and the procedure store of a first-class space inherit all constraints and procedures in the respective stores of the parent space. However, a first-class space has no write access to the cell store of its parent space. Consequently, it is impossible to assign in a first-class space attributes of objects that belong to an ancestor space. On the other hand, a first-class space can create its own objects and apply them freely. </P><P>The details of first-class spaces need only concern programmers who want to implement new search engines. For finite domain problems, the necessary search engines are already available as predefined functionality (e.g., <CODE>SearchOne</CODE> and <CODE>SearchAll</CODE>). </P><P>All functionality related to finite domain constraints is provided through the procedures of the module <CODE>FD</CODE>. We have already seen <CODE>FD<SPAN class="keyword">.</SPAN>distinct</CODE> (creates a propagator) and <CODE>FD<SPAN class="keyword">.</SPAN>distribute</CODE> (creates a distributor) in the script for the Send More Money Puzzle (see <A href="node15.html#section.problem.money">Section&nbsp;3.2</A>). </P><P class="margin">infix notations</P><P> For some of the procedures of the module <CODE>FD</CODE>, Oz provides special infix notations governed by the following operators: </P><BLOCKQUOTE class="code"><CODE>&nbsp;&nbsp;&nbsp;<SPAN class="keyword">::</SPAN>&nbsp;&nbsp;&nbsp;&nbsp;<SPAN class="keyword">:::</SPAN>&nbsp;&nbsp;&nbsp;&nbsp;<SPAN class="keyword">=:</SPAN>&nbsp;&nbsp;&nbsp;&nbsp;<SPAN class="keyword">\=:</SPAN>&nbsp;&nbsp;&nbsp;&nbsp;<SPAN class="keyword">&lt;:</SPAN>&nbsp;&nbsp;&nbsp;&nbsp;<SPAN class="keyword">&gt;:</SPAN>&nbsp;&nbsp;&nbsp;&nbsp;<SPAN class="keyword">=&lt;:</SPAN>&nbsp;&nbsp;&nbsp;&nbsp;<SPAN class="keyword">&gt;=:</SPAN></CODE></BLOCKQUOTE><P> You have already seen examples of the use of <CODE><SPAN class="keyword">:::</SPAN></CODE>, <CODE><SPAN class="keyword">\=:</SPAN></CODE>, and <CODE><SPAN class="keyword">=:</SPAN></CODE> in the script <CODE>Money</CODE>. An equivalent version of Money not using these notational conveniences appears in <A href="node17.html#progmoneynogadgets">Figure&nbsp;3.4</A> </P><P></P><DIV class="figure" id="progmoneynogadgets"><HR><P><A name="progmoneynogadgets"></A></P></DIV><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename">&nbsp;</SPAN>{<SPAN class="functionname">Money</SPAN>&nbsp;Root}<BR>&nbsp;&nbsp;&nbsp;S&nbsp;E&nbsp;N&nbsp;D&nbsp;M&nbsp;O&nbsp;R&nbsp;Y<BR><SPAN class="keyword">in</SPAN>&nbsp;<BR>&nbsp;&nbsp;&nbsp;Root&nbsp;=&nbsp;sol(s:S&nbsp;e:E&nbsp;n:N&nbsp;d:D&nbsp;m:M&nbsp;o:O&nbsp;r:R&nbsp;y:Y)<BR>&nbsp;&nbsp;&nbsp;{FD<SPAN class="keyword">.</SPAN>dom&nbsp;0<SPAN class="keyword">#</SPAN>9&nbsp;Root}<BR>&nbsp;&nbsp;&nbsp;{FD<SPAN class="keyword">.</SPAN>distinct&nbsp;Root}<BR>&nbsp;&nbsp;&nbsp;{FD<SPAN class="keyword">.</SPAN>sum&nbsp;[S]&nbsp;<SPAN class="string">'\\=:'</SPAN>&nbsp;0}<BR>&nbsp;&nbsp;&nbsp;{FD<SPAN class="keyword">.</SPAN>sum&nbsp;[M]&nbsp;<SPAN class="string">'\\=:'</SPAN>&nbsp;0}<BR>&nbsp;&nbsp;&nbsp;{FD<SPAN class="keyword">.</SPAN>sumC<BR>&nbsp;&nbsp;&nbsp;&nbsp;[1000&nbsp;&nbsp;100&nbsp;&nbsp;&nbsp;10&nbsp;&nbsp;1&nbsp;&nbsp;1000&nbsp;&nbsp;100&nbsp;&nbsp;10&nbsp;&nbsp;1&nbsp;&nbsp;<SPAN class="keyword">~</SPAN>10000&nbsp;&nbsp;<SPAN class="keyword">~</SPAN>1000&nbsp;&nbsp;<SPAN class="keyword">~</SPAN>100&nbsp;&nbsp;<SPAN class="keyword">~</SPAN>10&nbsp;&nbsp;<SPAN class="keyword">~</SPAN>1]<BR>&nbsp;&nbsp;&nbsp;&nbsp;[&nbsp;&nbsp;&nbsp;S&nbsp;&nbsp;&nbsp;&nbsp;E&nbsp;&nbsp;&nbsp;&nbsp;N&nbsp;&nbsp;D&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;M&nbsp;&nbsp;&nbsp;&nbsp;O&nbsp;&nbsp;&nbsp;R&nbsp;&nbsp;E&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;M&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;O&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;N&nbsp;&nbsp;&nbsp;&nbsp;E&nbsp;&nbsp;&nbsp;Y]<BR>&nbsp;&nbsp;&nbsp;&nbsp;<SPAN class="string">'=:'</SPAN>&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;0}<BR>&nbsp;&nbsp;&nbsp;{FD<SPAN class="keyword">.</SPAN>distribute&nbsp;ff&nbsp;Root}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><DIV class="figure"><P class="caption"><STRONG>Figure&nbsp;3.4:</STRONG> A script for Money that does not use the infix notations <CODE><SPAN class="keyword">=:</SPAN></CODE> and <CODE><SPAN class="keyword">\=:</SPAN></CODE>.</P><HR></DIV><P></P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node16.html#section.problem.explorer">&lt;&lt; Prev</A></TD><TD><A href="node13.html">- Up -</A></TD><TD><A href="node18.html#section.problem.watching">Next &gt;&gt;</A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~schulte/">Christian&nbsp;Schulte</A> and&nbsp;<A href="http://www.ps.uni-sb.de/~smolka/">Gert&nbsp;Smolka</A><BR><SPAN class="version">Version 1.4.0 (20090610)</SPAN></ADDRESS></BODY></HTML>