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><</span><span class=keyword>typename </span><span class=identifier>ScannerT</span><span class=special>> 35 </span><span class=keyword>typename </span><span class=identifier>parser_result</span><span class=special><</span><span class=identifier>self_t</span><span class=special>, </span><span class=identifier>ScannerT</span><span class=special>>::</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>& </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="https://www.boost.org/sgi/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><</span><span class=keyword>double</span><span class=special>>(), 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><</span><span class=keyword>double</span><span class=special>>(), </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 "currying", 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 -> C)</tt> 91 and <tt>(A -> (B -> C))</tt> are isomorphic, where <tt>"x"</tt> 92 is cartesian product and <tt>"->"</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>>> </span><span class=special>*( </span><span class=special>(</span><span class=literal>'+' </span><span class=special>>> </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><</span><span class=keyword>long</span><span class=special>>(), </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>>> </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><</span><span class=keyword>long</span><span class=special>>(), </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>(&</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>>> </span><span class=special>*( </span><span class=literal>',' 161 </span><span class=special>>> </span><span class=identifier>real_p 162 </span><span class=special>[ 163 </span><span class=identifier>bind</span><span class=special>(&</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><</span><span class=keyword>double</span><span class=special>> </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<double>. 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="https://people.cs.umass.edu/~yannis/fc++/">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>>> </span><span class=special>*( </span><span class=special>(</span><span class=literal>'+' </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>]) 210 </span><span class=special>| </span><span class=special>(</span><span class=literal>'-' </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>]) 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>>> </span><span class=special>*( </span><span class=special>(</span><span class=literal>'*' </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>]) 217 </span><span class=special>| </span><span class=special>(</span><span class=literal>'/' </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>]) 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>>> </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>>> </span><span class=literal>')' 224 </span><span class=special>| </span><span class=special>(</span><span class=literal>'-' </span><span class=special>>> </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>>> </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 © 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"> </p> 264</body> 265</html> 266
