Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/spirit/doc/functional.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 16 years ago

updated boost from 1_33_1 to 1_34_1
File size: 21.1 KB
Line 
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/compose/index.htm">compose</a></td>
123  <td class="table_cells">Functional composition adapters for the STL, from Nicolai
124    Josuttis</td>
125  </tr>
126  <td class="table_cells"><a href="http://www.boost.org/libs/function/index.html">function</a></td>
127  <td class="table_cells">Function object wrappers for deferred calls or callbacks,
128    from Doug Gregor</td>
129  </tr>
130  <td class="table_cells"><a href="http://www.boost.org/libs/functional/index.html">functional</a></td>
131  <td class="table_cells">Enhanced function object adaptors, from Mark Rodgers</td>
132  </tr>
133  <td class="table_cells"><a href="http://www.boost.org/libs/lambda/index.html">lambda</a></td>
134  <td class="table_cells">Define small unnamed function objects at the actual
135    call site, and more, from Jaakko Järvi and Gary Powell</td>
136  </tr>
137  <td class="table_cells"><a href="http://www.boost.org/libs/bind/ref.html">ref</a></td>
138  <td class="table_cells">A utility library for passing references to generic
139    functions, from Jaako Järvi, Peter Dimov, Doug Gregor, and Dave Abrahams</td>
140  </tr>
141</table>
142<p> The following is an example that uses boost <strong>Bind</strong> to use a
143  member function as a Spirit semantic action. You can see this example in full
144  in the file<a href="../example/fundamental/bind.cpp"> bind.cpp</a>.</p>
145<pre>
146    <code><span class=keyword>class </span><span class=identifier>list_parser
147    </span><span class=special>{
148    </span><span class=keyword>public</span><span class=special>:
149
150        </span><span class=keyword>typedef </span><span class=identifier>list_parser </span><span class=identifier>self_t</span><span class=special>;
151
152        </span><span class=keyword>bool
153        </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>)
154        </span><span class=special>{
155            </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>,
156
157                </span><span class=comment>//  Begin grammar
158                </span><span class=special>(
159                    </span><span class=identifier>real_p
160                    </span><span class=special>[
161                        </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>)
162                    </span><span class=special>]
163
164                    </span><span class=special>&gt;&gt; </span><span class=special>*(   </span><span class=literal>','
165                            </span><span class=special>&gt;&gt;  </span><span class=identifier>real_p
166                                </span><span class=special>[
167                                    </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>)
168                                </span><span class=special>]
169                        </span><span class=special>)
170                </span><span class=special>)
171                </span><span class=special>,
172                </span><span class=comment>//  End grammar
173
174                </span><span class=identifier>space_p</span><span class=special>).</span><span class=identifier>full</span><span class=special>;
175        </span><span class=special>}
176
177        </span><span class=keyword>void
178        </span><span class=identifier>add</span><span class=special>(</span><span class=keyword>double </span><span class=identifier>n</span><span class=special>)
179        </span><span class=special>{
180            </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>);
181        </span><span class=special>}
182
183        </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>;
184    </span><span class=special>};
185</span></code></pre>
186<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>
187<p>This parser parses a comma separated list of real numbers and stores them
188  in a vector&lt;double&gt;. Boost.bind creates a Spirit conforming semantic action
189  from the <tt>list_parser</tt>'s member function <tt>add</tt>.</p>
190<h3>Lambda and Phoenix</h3>
191<p> There's a library, authored by yours truly, named <a href="../phoenix/index.html">Phoenix</a>.
192  While this is not officially part of the Spirit distribution, this library has
193  been used extensively to experiment on advanced FP techniques in C++. This library
194  is highly influenced by <a href="http://www.cc.gatech.edu/%7Eyannis/fc%2B%2B/">FC++</a> 
195  and boost Lambda (<a href="http://www.boost.org/libs/lambda/index.html">BLL</a>).</p>
196<table width="80%" border="0" align="center">
197  <tr> 
198    <td class="note_box"> <b><img src="theme/lens.gif" width="15" height="16"> 
199      BLL</b><br>
200      <br>
201      In as much as Phoenix is influenced by boost Lambda (<a href="http://www.boost.org/libs/lambda/index.html">BLL</a>),
202      Phoenix innovations such as local variables, local functions and adaptable
203      closures, in turn influenced BLL. Currently, BLL is very similar to Phoenix.
204      Most importantly, BLL incorporated Phoenix's adaptable closures. In the
205      future, Spirit will fully support BLL. </td>
206  </tr>
207</table>
208<p> Phoenix allows one to write semantic actions inline in C++ through lambda
209  (an unnamed function) expressions. Here's a snippet from the <a href="../example/fundamental/phoenix_calc.cpp">phoenix_calc.cpp</a>  example:</p>
210<pre>
211    <code><span class=identifier>expression
212        </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>]
213            </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>])
214                </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>])
215                </span><span class=special>)
216        </span><span class=special>;
217
218    </span><span class=identifier>term
219        </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>]
220            </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>])
221                </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>])
222                </span><span class=special>)
223        </span><span class=special>;
224
225    </span><span class=identifier>factor
226        </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>]
227        </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>')'
228        </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>])
229        </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>])
230        </span><span class=special>;</span></code></pre>
231<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>
232<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>
233<p>Notice the use of lambda expressions such as:</p>
234<pre>
235    <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>
236<table width="80%" border="0" align="center">
237  <tr> 
238    <td class="note_box"> <b><img src="theme/lens.gif" width="15" height="16"> 
239        <a name="lambda"></a>Lambda Expressions?</b><br> 
240        <br>
241      Lambda expressions are actually unnamed partially applied functions where
242      placeholders (e.g. arg1, arg2) are provided in place of some of the arguments.
243      The reason this is called a lambda expression is that traditionally, such
244    placeholders are written using the Greek letter lambda <img src="theme/lambda.png" width="15" height="22">.</td>
245  </tr>
246</table>
247<p>where <tt>expression.val</tt> is a closure variable of the expression rule
248  (see <a href="closures.html">Closures</a>). <code><span class=identifier><tt>arg1</tt></span></code> 
249  is a placeholder for the first argument that the semantic action will receive
250  (see <a href="../phoenix/doc/place_holders.html">Phoenix Place-holders</a>).
251  In Boost.Lambda (BLL), this corresponds to <tt>_1</tt>. </p>
252<table border="0">
253  <tr> 
254    <td width="10"></td>
255    <td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td>
256    <td width="30"><a href="parametric_parsers.html"><img src="theme/l_arr.gif" border="0"></a></td>
257    <td width="30"><a href="phoenix.html"><img src="theme/r_arr.gif" border="0"></a></td>
258  </tr>
259</table>
260<br>
261<hr size="1">
262<p class="copyright">Copyright &copy; 1998-2003 Joel de Guzman<br>
263  <br>
264<font size="2">Use, modification and distribution is subject to the Boost Software
265    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
266    http://www.boost.org/LICENSE_1_0.txt)</font></p>
267<p class="copyright">&nbsp;</p>
268</body>
269</html>
Note: See TracBrowser for help on using the repository browser.