ceph/src/boost/libs/spirit/classic/doc/functional.html

   1 <html>
   2 <head>
   3 <title>Functional</title>
   4 <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
   5 <link rel="stylesheet" href="theme/style.css" type="text/css">
   6 </head>
   7
   8 <body>
   9 <table width="100%" border="0" background="theme/bkd2.gif" cellspacing="2">
  10   <tr>
  11     <td width="10">
  12     </td>
  13     <td width="85%"> <font size="6" face="Verdana, Arial, Helvetica, sans-serif"><b>Functional</b></font>
  14     </td>
  15     <td width="112"><a href="http://spirit.sf.net"><img src="theme/spirit.gif" width="112" height="48" align="right" border="0"></a></td>
  16   </tr>
  17 </table>
  18 <br>
  19 <table border="0">
  20   <tr>
  21     <td width="10"></td>
  22     <td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td>
  23     <td width="30"><a href="parametric_parsers.html"><img src="theme/l_arr.gif" border="0"></a></td>
  24     <td width="30"><a href="phoenix.html"><img src="theme/r_arr.gif" border="0"></a></td>
  25   </tr>
  26 </table>
  27 <p>If you look more closely, you'll notice that Spirit is all about composition
  28   of <i>parser functions</i>. A parser is just a function that accepts a scanner
  29   and returns a match. Parser <i>functions</i> are composed to form increasingly
  30   complex <i>higher order forms</i>. Notice too that the parser, albeit an object,
  31   is immutable and constant. All primitive and composite parser objects are <tt>const</tt>.
  32   The parse member function is even declared as <tt>const</tt>:</p>
  33 <pre>
  34     <code><span class=keyword>template </span><span class=special>&lt;</span><span class=keyword>typename </span><span class=identifier>ScannerT</span><span class=special>&gt;
  35     </span><span class=keyword>typename </span><span class=identifier>parser_result</span><span class=special>&lt;</span><span class=identifier>self_t</span><span class=special>, </span><span class=identifier>ScannerT</span><span class=special>&gt;::</span><span class=identifier>type
  36     </span><span class=identifier>parse</span><span class=special>(</span><span class=identifier>ScannerT </span><span class=keyword>const</span><span class=special>&amp; </span><span class=identifier>scan</span><span class=special>) </span><span class=keyword>const</span><span class=special>;</span></code></pre>
  37 <p> In all accounts, this looks and feels a lot like <b>Functional Programming</b>.
  38   And indeed it is. Spirit is by all means an application of Functional programming
  39   in the imperative C++ domain. In Haskell, for example, there is what are called
  40   <a href="references.html#combinators">parser combinators</a> which are strikingly
  41   similar to the approach taken by Spirit- parser functions which are composed
  42   using various operators to create higher order parser functions that model a
  43   top-down recursive descent parser. Those smart Haskell folks have been doing
  44   this way before Spirit.</p>
  45 <p> Functional style programming (or FP) libraries are gaining momentum in the
  46   C++ community. Certainly, we'll see more of FP in Spirit now and in the future.
  47   Actually, if one looks more closely, even the C++ standard library has an FP
  48   flavor. Stealthily beneath the core of the standard C++ library, a closer look
  49   into STL gives us a glimpse of a truly FP paradigm already in place. It is obvious
  50   that the authors of STL know and practice FP.</p>
  51
  52 <h2>Semantic Actions in the FP Perspective</h2>
  53
  54 <h3>STL style FP</h3>
  55 <p> A more obvious application of STL-style FP in Spirit is the semantic action.
  56   What is STL-style FP? It is primarily the use of functors that can be composed
  57   to form higher order functors.</p>
  58 <table width="80%" border="0" align="center">
  59   <tr>
  60     <td class="note_box"> <img src="theme/note.gif" width="16" height="16"> <strong>Functors</strong><br>
  61       <br>
  62       A Function Object, or Functor is simply any object that can be called as
  63       if it is a function. An ordinary function is a function object, and so is
  64       a function pointer; more generally, so is an object of a class that defines
  65       operator(). </td>
  66   </tr>
  67 </table>
  68 <p> This STL-style FP can be seen everywhere these days. The following example
  69   is taken from <a href="http://www.sgi.com/tech/stl/">SGI's Standard Template
  70   Library Programmer's Guide</a>:</p>
  71 <pre>
  72     <code><span class=comment>//  Computes sin(x)/(x + DBL_MIN) for each element of a range.
  73
  74     </span><span class=identifier>transform</span><span class=special>(</span><span class=identifier>first</span><span class=special>, </span><span class=identifier>last</span><span class=special>, </span><span class=identifier>first</span><span class=special>,
  75               </span><span class=identifier>compose2</span><span class=special>(</span><span class=identifier>divides</span><span class=special>&lt;</span><span class=keyword>double</span><span class=special>&gt;(),
  76                        </span><span class=identifier>ptr_fun</span><span class=special>(</span><span class=identifier>sin</span><span class=special>),
  77                        </span><span class=identifier>bind2nd</span><span class=special>(</span><span class=identifier>plus</span><span class=special>&lt;</span><span class=keyword>double</span><span class=special>&gt;(), </span><span class=identifier>DBL_MIN</span><span class=special>)));</span></code></pre>
  78 <p align="left"> Really, this is just <i>currying</i> in FP terminology.</p>
  79 <table width="80%" border="0" align="center">
  80   <tr>
  81     <td class="note_box"> <img src="theme/lens.gif" width="15" height="16"> <strong>Currying</strong><br>
  82       <br>
  83       What is &quot;currying&quot;, and where does it come from?<br>
  84       <br>
  85       Currying has its origins in the mathematical study of functions. It was
  86       observed by Frege in 1893 that it suffices to restrict attention to functions
  87       of a single argument. For example, for any two parameter function <tt>f(x,y)</tt>,
  88       there is a one parameter function <tt>f'</tt> such that <tt>f'(x)</tt> is
  89       a function that can be applied to y to give <tt>(f'(x))(y) = f (x,y)</tt>.
  90       This corresponds to the well known fact that the sets <tt>(AxB -&gt; C)</tt>
  91       and <tt>(A -&gt; (B -&gt; C))</tt> are isomorphic, where <tt>&quot;x&quot;</tt>
  92       is cartesian product and <tt>&quot;-&gt;&quot;</tt> is function space. In
  93       functional programming, function application is denoted by juxtaposition,
  94       and assumed to associate to the left, so that the equation above becomes
  95       <tt>f' x y = f(x,y)</tt>. </td>
  96   </tr>
  97 </table>
  98 <p> In the context of Spirit, the same FP style functor composition may be applied
  99   to semantic actions. <a href="../example/fundamental/full_calc.cpp">full_calc.cpp</a> is a good example. Here's a snippet from that sample:</p>
 100 <pre>
 101     <code><span class=identifier>expression </span><span class=special>=
 102         </span><span class=identifier>term
 103         </span><span class=special>&gt;&gt; </span><span class=special>*(   </span><span class=special>(</span><span class=literal>'+' </span><span class=special>&gt;&gt; </span><span class=identifier>term</span><span class=special>)[</span><span class=identifier>make_op</span><span class=special>(</span><span class=identifier>plus</span><span class=special>&lt;</span><span class=keyword>long</span><span class=special>&gt;(), </span><span class=identifier>self</span><span class=special>.</span><span class=identifier>eval</span><span class=special>)]
 104             </span><span class=special>|   </span><span class=special>(</span><span class=literal>'-' </span><span class=special>&gt;&gt; </span><span class=identifier>term</span><span class=special>)[</span><span class=identifier>make_op</span><span class=special>(</span><span class=identifier>minus</span><span class=special>&lt;</span><span class=keyword>long</span><span class=special>&gt;(), </span><span class=identifier>self</span><span class=special>.</span><span class=identifier>eval</span><span class=special>)]
 105             </span><span class=special>)
 106             </span><span class=special>;</span></code></pre>
 107
 108 <p> <img height="16" width="15" src="theme/lens.gif"> The full source code can be <a href="../example/fundamental/full_calc.cpp">viewed here</a>. This is part of the Spirit distribution.</p>
 109 <h3>Boost style FP</h3>
 110 <p> Boost takes the FP paradigm further. There are libraries in boost that focus
 111   specifically on Function objects and higher-order programming.</p>
 112 <table width="90%" border="0" align="center">
 113   <tr>
 114     <td class="table_title" colspan="14"> Boost FP libraries </td>
 115   </tr>
 116   <tr>
 117     <td class="table_cells"><a href="http://www.boost.org/libs/bind/bind.html">bind</a>
 118       and <a href="http://www.boost.org/libs/bind/mem_fn.html">mem_fn</a></td>
 119     <td class="table_cells">Generalized binders for function/object/pointers and
 120       member functions, from Peter Dimov</td>
 121   </tr>
 122   <td class="table_cells"><a href="http://www.boost.org/libs/function/index.html">function</a></td>
 123   <td class="table_cells">Function object wrappers for deferred calls or callbacks,
 124     from Doug Gregor</td>
 125   </tr>
 126   <td class="table_cells"><a href="http://www.boost.org/libs/functional/index.html">functional</a></td>
 127   <td class="table_cells">Enhanced function object adaptors, from Mark Rodgers</td>
 128   </tr>
 129   <td class="table_cells"><a href="http://www.boost.org/libs/lambda/index.html">lambda</a></td>
 130   <td class="table_cells">Define small unnamed function objects at the actual
 131     call site, and more, from Jaakko Järvi and Gary Powell</td>
 132   </tr>
 133   <td class="table_cells"><a href="http://www.boost.org/libs/bind/ref.html">ref</a></td>
 134   <td class="table_cells">A utility library for passing references to generic
 135     functions, from Jaako Järvi, Peter Dimov, Doug Gregor, and Dave Abrahams</td>
 136   </tr>
 137 </table>
 138 <p> The following is an example that uses boost <strong>Bind</strong> to use a
 139   member function as a Spirit semantic action. You can see this example in full
 140   in the file<a href="../example/fundamental/bind.cpp"> bind.cpp</a>.</p>
 141 <pre>
 142     <code><span class=keyword>class </span><span class=identifier>list_parser
 143     </span><span class=special>{
 144     </span><span class=keyword>public</span><span class=special>:
 145
 146         </span><span class=keyword>typedef </span><span class=identifier>list_parser </span><span class=identifier>self_t</span><span class=special>;
 147
 148         </span><span class=keyword>bool
 149         </span><span class=identifier>parse</span><span class=special>(</span><span class=keyword>char </span><span class=keyword>const</span><span class=special>* </span><span class=identifier>str</span><span class=special>)
 150         </span><span class=special>{
 151             </span><span class=keyword>return </span><span class=identifier>spirit</span><span class=special>::</span><span class=identifier>parse</span><span class=special>(</span><span class=identifier>str</span><span class=special>,
 152
 153                 </span><span class=comment>//  Begin grammar
 154                 </span><span class=special>(
 155                     </span><span class=identifier>real_p
 156                     </span><span class=special>[
 157                         </span><span class=identifier>bind</span><span class=special>(&amp;</span><span class=identifier>self_t</span><span class=special>::</span><span class=identifier>add</span><span class=special>, </span><span class=keyword>this</span><span class=special>, </span><span class=identifier>_1</span><span class=special>)
 158                     </span><span class=special>]
 159
 160                     </span><span class=special>&gt;&gt; </span><span class=special>*(   </span><span class=literal>','
 161                             </span><span class=special>&gt;&gt;  </span><span class=identifier>real_p
 162                                 </span><span class=special>[
 163                                     </span><span class=identifier>bind</span><span class=special>(&amp;</span><span class=identifier>self_t</span><span class=special>::</span><span class=identifier>add</span><span class=special>, </span><span class=keyword>this</span><span class=special>, </span><span class=identifier>_1</span><span class=special>)
 164                                 </span><span class=special>]
 165                         </span><span class=special>)
 166                 </span><span class=special>)
 167                 </span><span class=special>,
 168                 </span><span class=comment>//  End grammar
 169
 170                 </span><span class=identifier>space_p</span><span class=special>).</span><span class=identifier>full</span><span class=special>;
 171         </span><span class=special>}
 172
 173         </span><span class=keyword>void
 174         </span><span class=identifier>add</span><span class=special>(</span><span class=keyword>double </span><span class=identifier>n</span><span class=special>)
 175         </span><span class=special>{
 176             </span><span class=identifier>v</span><span class=special>.</span><span class=identifier>push_back</span><span class=special>(</span><span class=identifier>n</span><span class=special>);
 177         </span><span class=special>}
 178
 179         </span><span class=identifier>vector</span><span class=special>&lt;</span><span class=keyword>double</span><span class=special>&gt; </span><span class=identifier>v</span><span class=special>;
 180     </span><span class=special>};
 181 </span></code></pre>
 182 <p>   <img height="16" width="15" src="theme/lens.gif"> The full source code can be <a href="../example/fundamental/bind.cpp">viewed here</a>. This is part of the Spirit distribution.</p>
 183 <p>This parser parses a comma separated list of real numbers and stores them
 184   in a vector&lt;double&gt;. Boost.bind creates a Spirit conforming semantic action
 185   from the <tt>list_parser</tt>'s member function <tt>add</tt>.</p>
 186 <h3>Lambda and Phoenix</h3>
 187 <p> There's a library, authored by yours truly, named <a href="../phoenix/index.html">Phoenix</a>.
 188   While this is not officially part of the Spirit distribution, this library has
 189   been used extensively to experiment on advanced FP techniques in C++. This library
 190   is highly influenced by <a href="http://www.cc.gatech.edu/%7Eyannis/fc%2B%2B/">FC++</a>
 191   and boost Lambda (<a href="http://www.boost.org/libs/lambda/index.html">BLL</a>).</p>
 192 <table width="80%" border="0" align="center">
 193   <tr>
 194     <td class="note_box"> <b><img src="theme/lens.gif" width="15" height="16">
 195       BLL</b><br>
 196       <br>
 197       In as much as Phoenix is influenced by boost Lambda (<a href="http://www.boost.org/libs/lambda/index.html">BLL</a>),
 198       Phoenix innovations such as local variables, local functions and adaptable
 199       closures, in turn influenced BLL. Currently, BLL is very similar to Phoenix.
 200       Most importantly, BLL incorporated Phoenix's adaptable closures. In the
 201       future, Spirit will fully support BLL. </td>
 202   </tr>
 203 </table>
 204 <p> Phoenix allows one to write semantic actions inline in C++ through lambda
 205   (an unnamed function) expressions. Here's a snippet from the <a href="../example/fundamental/phoenix_calc.cpp">phoenix_calc.cpp</a>  example:</p>
 206 <pre>
 207     <code><span class=identifier>expression
 208         </span><span class=special>=   </span><span class=identifier>term</span><span class=special>[</span><span class=identifier>expression</span><span class=special>.</span><span class=identifier>val </span><span class=special>= </span><span class=identifier>arg1</span><span class=special>]
 209             </span><span class=special>&gt;&gt; </span><span class=special>*(   </span><span class=special>(</span><span class=literal>'+' </span><span class=special>&gt;&gt; </span><span class=identifier>term</span><span class=special>[</span><span class=identifier>expression</span><span class=special>.</span><span class=identifier>val </span><span class=special>+= </span><span class=identifier>arg1</span><span class=special>])
 210                 </span><span class=special>|   </span><span class=special>(</span><span class=literal>'-' </span><span class=special>&gt;&gt; </span><span class=identifier>term</span><span class=special>[</span><span class=identifier>expression</span><span class=special>.</span><span class=identifier>val </span><span class=special>-= </span><span class=identifier>arg1</span><span class=special>])
 211                 </span><span class=special>)
 212         </span><span class=special>;
 213
 214     </span><span class=identifier>term
 215         </span><span class=special>=   </span><span class=identifier>factor</span><span class=special>[</span><span class=identifier>term</span><span class=special>.</span><span class=identifier>val </span><span class=special>= </span><span class=identifier>arg1</span><span class=special>]
 216             </span><span class=special>&gt;&gt; </span><span class=special>*(   </span><span class=special>(</span><span class=literal>'*' </span><span class=special>&gt;&gt; </span><span class=identifier>factor</span><span class=special>[</span><span class=identifier>term</span><span class=special>.</span><span class=identifier>val </span><span class=special>*= </span><span class=identifier>arg1</span><span class=special>])
 217                 </span><span class=special>|   </span><span class=special>(</span><span class=literal>'/' </span><span class=special>&gt;&gt; </span><span class=identifier>factor</span><span class=special>[</span><span class=identifier>term</span><span class=special>.</span><span class=identifier>val </span><span class=special>/= </span><span class=identifier>arg1</span><span class=special>])
 218                 </span><span class=special>)
 219         </span><span class=special>;
 220
 221     </span><span class=identifier>factor
 222         </span><span class=special>=   </span><span class=identifier>ureal_p</span><span class=special>[</span><span class=identifier>factor</span><span class=special>.</span><span class=identifier>val </span><span class=special>= </span><span class=identifier>arg1</span><span class=special>]
 223         </span><span class=special>|   </span><span class=literal>'(' </span><span class=special>&gt;&gt; </span><span class=identifier>expression</span><span class=special>[</span><span class=identifier>factor</span><span class=special>.</span><span class=identifier>val </span><span class=special>= </span><span class=identifier>arg1</span><span class=special>] </span><span class=special>&gt;&gt; </span><span class=literal>')'
 224         </span><span class=special>|   </span><span class=special>(</span><span class=literal>'-' </span><span class=special>&gt;&gt; </span><span class=identifier>factor</span><span class=special>[</span><span class=identifier>factor</span><span class=special>.</span><span class=identifier>val </span><span class=special>= </span><span class=special>-</span><span class=identifier>arg1</span><span class=special>])
 225         </span><span class=special>|   </span><span class=special>(</span><span class=literal>'+' </span><span class=special>&gt;&gt; </span><span class=identifier>factor</span><span class=special>[</span><span class=identifier>factor</span><span class=special>.</span><span class=identifier>val </span><span class=special>= </span><span class=identifier>arg1</span><span class=special>])
 226         </span><span class=special>;</span></code></pre>
 227 <p>  <img height="16" width="15" src="theme/lens.gif"> The full source code can be <a href="../example/fundamental/phoenix_calc.cpp">viewed here</a>. This is part of the Spirit distribution.</p>
 228 <p>You do not have to worry about the details for now. There is a lot going on here that needs to be explained. The succeeding chapters will be enlightening.</p>
 229 <p>Notice the use of lambda expressions such as:</p>
 230 <pre>
 231     <code><span class=identifier>expression</span><span class=special>.</span><span class=identifier>val </span><span class=special>+= </span><span class=identifier>arg1</span></code></pre>
 232 <table width="80%" border="0" align="center">
 233   <tr>
 234     <td class="note_box"> <b><img src="theme/lens.gif" width="15" height="16">
 235         <a name="lambda"></a>Lambda Expressions?</b><br>
 236         <br>
 237       Lambda expressions are actually unnamed partially applied functions where
 238       placeholders (e.g. arg1, arg2) are provided in place of some of the arguments.
 239       The reason this is called a lambda expression is that traditionally, such
 240     placeholders are written using the Greek letter lambda <img src="theme/lambda.png" width="15" height="22">.</td>
 241   </tr>
 242 </table>
 243 <p>where <tt>expression.val</tt> is a closure variable of the expression rule
 244   (see <a href="closures.html">Closures</a>). <code><span class=identifier><tt>arg1</tt></span></code>
 245   is a placeholder for the first argument that the semantic action will receive
 246   (see <a href="../phoenix/doc/place_holders.html">Phoenix Place-holders</a>).
 247   In Boost.Lambda (BLL), this corresponds to <tt>_1</tt>. </p>
 248 <table border="0">
 249   <tr>
 250     <td width="10"></td>
 251     <td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td>
 252     <td width="30"><a href="parametric_parsers.html"><img src="theme/l_arr.gif" border="0"></a></td>
 253     <td width="30"><a href="phoenix.html"><img src="theme/r_arr.gif" border="0"></a></td>
 254   </tr>
 255 </table>
 256 <br>
 257 <hr size="1">
 258 <p class="copyright">Copyright &copy; 1998-2003 Joel de Guzman<br>
 259   <br>
 260 <font size="2">Use, modification and distribution is subject to the Boost Software
 261     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
 262     http://www.boost.org/LICENSE_1_0.txt)</font></p>
 263 <p class="copyright">&nbsp;</p>
 264 </body>
 265 </html>