266 lines
21 KiB
HTML
266 lines
21 KiB
HTML
<html>
|
||
<head>
|
||
<title>Functional</title>
|
||
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
|
||
<link rel="stylesheet" href="theme/style.css" type="text/css">
|
||
</head>
|
||
|
||
<body>
|
||
<table width="100%" border="0" background="theme/bkd2.gif" cellspacing="2">
|
||
<tr>
|
||
<td width="10">
|
||
</td>
|
||
<td width="85%"> <font size="6" face="Verdana, Arial, Helvetica, sans-serif"><b>Functional</b></font>
|
||
</td>
|
||
<td width="112"><a href="http://spirit.sf.net"><img src="theme/spirit.gif" width="112" height="48" align="right" border="0"></a></td>
|
||
</tr>
|
||
</table>
|
||
<br>
|
||
<table border="0">
|
||
<tr>
|
||
<td width="10"></td>
|
||
<td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td>
|
||
<td width="30"><a href="parametric_parsers.html"><img src="theme/l_arr.gif" border="0"></a></td>
|
||
<td width="30"><a href="phoenix.html"><img src="theme/r_arr.gif" border="0"></a></td>
|
||
</tr>
|
||
</table>
|
||
<p>If you look more closely, you'll notice that Spirit is all about composition
|
||
of <i>parser functions</i>. A parser is just a function that accepts a scanner
|
||
and returns a match. Parser <i>functions</i> are composed to form increasingly
|
||
complex <i>higher order forms</i>. Notice too that the parser, albeit an object,
|
||
is immutable and constant. All primitive and composite parser objects are <tt>const</tt>.
|
||
The parse member function is even declared as <tt>const</tt>:</p>
|
||
<pre>
|
||
<code><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>ScannerT</span><span class=special>>
|
||
</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
|
||
</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>
|
||
<p> In all accounts, this looks and feels a lot like <b>Functional Programming</b>.
|
||
And indeed it is. Spirit is by all means an application of Functional programming
|
||
in the imperative C++ domain. In Haskell, for example, there is what are called
|
||
<a href="references.html#combinators">parser combinators</a> which are strikingly
|
||
similar to the approach taken by Spirit- parser functions which are composed
|
||
using various operators to create higher order parser functions that model a
|
||
top-down recursive descent parser. Those smart Haskell folks have been doing
|
||
this way before Spirit.</p>
|
||
<p> Functional style programming (or FP) libraries are gaining momentum in the
|
||
C++ community. Certainly, we'll see more of FP in Spirit now and in the future.
|
||
Actually, if one looks more closely, even the C++ standard library has an FP
|
||
flavor. Stealthily beneath the core of the standard C++ library, a closer look
|
||
into STL gives us a glimpse of a truly FP paradigm already in place. It is obvious
|
||
that the authors of STL know and practice FP.</p>
|
||
|
||
<h2>Semantic Actions in the FP Perspective</h2>
|
||
|
||
<h3>STL style FP</h3>
|
||
<p> A more obvious application of STL-style FP in Spirit is the semantic action.
|
||
What is STL-style FP? It is primarily the use of functors that can be composed
|
||
to form higher order functors.</p>
|
||
<table width="80%" border="0" align="center">
|
||
<tr>
|
||
<td class="note_box"> <img src="theme/note.gif" width="16" height="16"> <strong>Functors</strong><br>
|
||
<br>
|
||
A Function Object, or Functor is simply any object that can be called as
|
||
if it is a function. An ordinary function is a function object, and so is
|
||
a function pointer; more generally, so is an object of a class that defines
|
||
operator(). </td>
|
||
</tr>
|
||
</table>
|
||
<p> This STL-style FP can be seen everywhere these days. The following example
|
||
is taken from <a href="https://www.boost.org/sgi/stl/">SGI's Standard Template
|
||
Library Programmer's Guide</a>:</p>
|
||
<pre>
|
||
<code><span class=comment>// Computes sin(x)/(x + DBL_MIN) for each element of a range.
|
||
|
||
</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>,
|
||
</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>>(),
|
||
</span><span class=identifier>ptr_fun</span><span class=special>(</span><span class=identifier>sin</span><span class=special>),
|
||
</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>
|
||
<p align="left"> Really, this is just <i>currying</i> in FP terminology.</p>
|
||
<table width="80%" border="0" align="center">
|
||
<tr>
|
||
<td class="note_box"> <img src="theme/lens.gif" width="15" height="16"> <strong>Currying</strong><br>
|
||
<br>
|
||
What is "currying", and where does it come from?<br>
|
||
<br>
|
||
Currying has its origins in the mathematical study of functions. It was
|
||
observed by Frege in 1893 that it suffices to restrict attention to functions
|
||
of a single argument. For example, for any two parameter function <tt>f(x,y)</tt>,
|
||
there is a one parameter function <tt>f'</tt> such that <tt>f'(x)</tt> is
|
||
a function that can be applied to y to give <tt>(f'(x))(y) = f (x,y)</tt>.
|
||
This corresponds to the well known fact that the sets <tt>(AxB -> C)</tt>
|
||
and <tt>(A -> (B -> C))</tt> are isomorphic, where <tt>"x"</tt>
|
||
is cartesian product and <tt>"->"</tt> is function space. In
|
||
functional programming, function application is denoted by juxtaposition,
|
||
and assumed to associate to the left, so that the equation above becomes
|
||
<tt>f' x y = f(x,y)</tt>. </td>
|
||
</tr>
|
||
</table>
|
||
<p> In the context of Spirit, the same FP style functor composition may be applied
|
||
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>
|
||
<pre>
|
||
<code><span class=identifier>expression </span><span class=special>=
|
||
</span><span class=identifier>term
|
||
</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>)]
|
||
</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>)]
|
||
</span><span class=special>)
|
||
</span><span class=special>;</span></code></pre>
|
||
|
||
<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>
|
||
<h3>Boost style FP</h3>
|
||
<p> Boost takes the FP paradigm further. There are libraries in boost that focus
|
||
specifically on Function objects and higher-order programming.</p>
|
||
<table width="90%" border="0" align="center">
|
||
<tr>
|
||
<td class="table_title" colspan="14"> Boost FP libraries </td>
|
||
</tr>
|
||
<tr>
|
||
<td class="table_cells"><a href="http://www.boost.org/libs/bind/bind.html">bind</a>
|
||
and <a href="http://www.boost.org/libs/bind/mem_fn.html">mem_fn</a></td>
|
||
<td class="table_cells">Generalized binders for function/object/pointers and
|
||
member functions, from Peter Dimov</td>
|
||
</tr>
|
||
<td class="table_cells"><a href="http://www.boost.org/libs/function/index.html">function</a></td>
|
||
<td class="table_cells">Function object wrappers for deferred calls or callbacks,
|
||
from Doug Gregor</td>
|
||
</tr>
|
||
<td class="table_cells"><a href="http://www.boost.org/libs/functional/index.html">functional</a></td>
|
||
<td class="table_cells">Enhanced function object adaptors, from Mark Rodgers</td>
|
||
</tr>
|
||
<td class="table_cells"><a href="http://www.boost.org/libs/lambda/index.html">lambda</a></td>
|
||
<td class="table_cells">Define small unnamed function objects at the actual
|
||
call site, and more, from Jaakko J<>rvi and Gary Powell</td>
|
||
</tr>
|
||
<td class="table_cells"><a href="http://www.boost.org/libs/bind/ref.html">ref</a></td>
|
||
<td class="table_cells">A utility library for passing references to generic
|
||
functions, from Jaako J<>rvi, Peter Dimov, Doug Gregor, and Dave Abrahams</td>
|
||
</tr>
|
||
</table>
|
||
<p> The following is an example that uses boost <strong>Bind</strong> to use a
|
||
member function as a Spirit semantic action. You can see this example in full
|
||
in the file<a href="../example/fundamental/bind.cpp"> bind.cpp</a>.</p>
|
||
<pre>
|
||
<code><span class=keyword>class </span><span class=identifier>list_parser
|
||
</span><span class=special>{
|
||
</span><span class=keyword>public</span><span class=special>:
|
||
|
||
</span><span class=keyword>typedef </span><span class=identifier>list_parser </span><span class=identifier>self_t</span><span class=special>;
|
||
|
||
</span><span class=keyword>bool
|
||
</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>)
|
||
</span><span class=special>{
|
||
</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>,
|
||
|
||
</span><span class=comment>// Begin grammar
|
||
</span><span class=special>(
|
||
</span><span class=identifier>real_p
|
||
</span><span class=special>[
|
||
</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>)
|
||
</span><span class=special>]
|
||
|
||
</span><span class=special>>> </span><span class=special>*( </span><span class=literal>','
|
||
</span><span class=special>>> </span><span class=identifier>real_p
|
||
</span><span class=special>[
|
||
</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>)
|
||
</span><span class=special>]
|
||
</span><span class=special>)
|
||
</span><span class=special>)
|
||
</span><span class=special>,
|
||
</span><span class=comment>// End grammar
|
||
|
||
</span><span class=identifier>space_p</span><span class=special>).</span><span class=identifier>full</span><span class=special>;
|
||
</span><span class=special>}
|
||
|
||
</span><span class=keyword>void
|
||
</span><span class=identifier>add</span><span class=special>(</span><span class=keyword>double </span><span class=identifier>n</span><span class=special>)
|
||
</span><span class=special>{
|
||
</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>);
|
||
</span><span class=special>}
|
||
|
||
</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>;
|
||
</span><span class=special>};
|
||
</span></code></pre>
|
||
<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>
|
||
<p>This parser parses a comma separated list of real numbers and stores them
|
||
in a vector<double>. Boost.bind creates a Spirit conforming semantic action
|
||
from the <tt>list_parser</tt>'s member function <tt>add</tt>.</p>
|
||
<h3>Lambda and Phoenix</h3>
|
||
<p> There's a library, authored by yours truly, named <a href="../phoenix/index.html">Phoenix</a>.
|
||
While this is not officially part of the Spirit distribution, this library has
|
||
been used extensively to experiment on advanced FP techniques in C++. This library
|
||
is highly influenced by <a href="https://people.cs.umass.edu/~yannis/fc++/">FC++</a>
|
||
and boost Lambda (<a href="http://www.boost.org/libs/lambda/index.html">BLL</a>).</p>
|
||
<table width="80%" border="0" align="center">
|
||
<tr>
|
||
<td class="note_box"> <b><img src="theme/lens.gif" width="15" height="16">
|
||
BLL</b><br>
|
||
<br>
|
||
In as much as Phoenix is influenced by boost Lambda (<a href="http://www.boost.org/libs/lambda/index.html">BLL</a>),
|
||
Phoenix innovations such as local variables, local functions and adaptable
|
||
closures, in turn influenced BLL. Currently, BLL is very similar to Phoenix.
|
||
Most importantly, BLL incorporated Phoenix's adaptable closures. In the
|
||
future, Spirit will fully support BLL. </td>
|
||
</tr>
|
||
</table>
|
||
<p> Phoenix allows one to write semantic actions inline in C++ through lambda
|
||
(an unnamed function) expressions. Here's a snippet from the <a href="../example/fundamental/phoenix_calc.cpp">phoenix_calc.cpp</a> example:</p>
|
||
<pre>
|
||
<code><span class=identifier>expression
|
||
</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>]
|
||
</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>])
|
||
</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>])
|
||
</span><span class=special>)
|
||
</span><span class=special>;
|
||
|
||
</span><span class=identifier>term
|
||
</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>]
|
||
</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>])
|
||
</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>])
|
||
</span><span class=special>)
|
||
</span><span class=special>;
|
||
|
||
</span><span class=identifier>factor
|
||
</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>]
|
||
</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>')'
|
||
</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>])
|
||
</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>])
|
||
</span><span class=special>;</span></code></pre>
|
||
<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>
|
||
<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>
|
||
<p>Notice the use of lambda expressions such as:</p>
|
||
<pre>
|
||
<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>
|
||
<table width="80%" border="0" align="center">
|
||
<tr>
|
||
<td class="note_box"> <b><img src="theme/lens.gif" width="15" height="16">
|
||
<a name="lambda"></a>Lambda Expressions?</b><br>
|
||
<br>
|
||
Lambda expressions are actually unnamed partially applied functions where
|
||
placeholders (e.g. arg1, arg2) are provided in place of some of the arguments.
|
||
The reason this is called a lambda expression is that traditionally, such
|
||
placeholders are written using the Greek letter lambda <img src="theme/lambda.png" width="15" height="22">.</td>
|
||
</tr>
|
||
</table>
|
||
<p>where <tt>expression.val</tt> is a closure variable of the expression rule
|
||
(see <a href="closures.html">Closures</a>). <code><span class=identifier><tt>arg1</tt></span></code>
|
||
is a placeholder for the first argument that the semantic action will receive
|
||
(see <a href="../phoenix/doc/place_holders.html">Phoenix Place-holders</a>).
|
||
In Boost.Lambda (BLL), this corresponds to <tt>_1</tt>. </p>
|
||
<table border="0">
|
||
<tr>
|
||
<td width="10"></td>
|
||
<td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td>
|
||
<td width="30"><a href="parametric_parsers.html"><img src="theme/l_arr.gif" border="0"></a></td>
|
||
<td width="30"><a href="phoenix.html"><img src="theme/r_arr.gif" border="0"></a></td>
|
||
</tr>
|
||
</table>
|
||
<br>
|
||
<hr size="1">
|
||
<p class="copyright">Copyright © 1998-2003 Joel de Guzman<br>
|
||
<br>
|
||
<font size="2">Use, modification and distribution is subject to the Boost Software
|
||
License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
|
||
http://www.boost.org/LICENSE_1_0.txt)</font></p>
|
||
<p class="copyright"> </p>
|
||
</body>
|
||
</html>
|