<html>
<head>
<title>Closures</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>Closures</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="functional.html"><img src="theme/l_arr.gif" border="0"></a></td>
<td width="20"><a href="escape_char_parser.html"><img src="theme/r_arr.gif" border="0"></a></td>
</tr>
</table>
<p>Closures provide an environment, a stack frame, for local variables to reside.
Most importantly, the closure variables are acessible from the EBNF grammar
specification and can be used to pass parser information upstream or downstream
from the topmost rule down to the terminals in a top-down recursive descent.
For one, closures provide a parser with the ability to have inherited and synthetic
attributes, more or less analogous to return values and function arguments.
</p>
<p>When a parser is enclosed in a closure, the closure's local variables are created
prior to entering the parse function and destructed after exiting the parse
function. These local variables are true local variables that exist on the hardware
stack. </p>
<h2>Nested Functions</h2>
<p>To fully understand the importance of closures, it is best to look at a language
such as Pascal which allows nested functions. Since we are dealing with C++,
lets us assume for the moment that C++ allows nested functions. Consider the
following <b><i>pseudo</i></b> C++ code:</p>
<pre><span class=identifier> </span><span class=keyword>void </span><span class=identifier>a</span><span class=special>()
</span><span class=special>{
</span><span class=keyword>int </span><span class=identifier>va</span><span class=special>;
</span><span class=keyword>void </span><span class=identifier>b</span><span class=special>()
</span><span class=special>{
</span><span class=keyword>int </span><span class=identifier>vb</span><span class=special>;
</span> <span class=keyword>void </span><span class=identifier>c</span><span class=special>()
</span><span class=special>{
</span><span class=keyword>int </span><span class=identifier>vc</span><span class=special>;
</span><span class=special>}
</span><span class=identifier>c</span><span class=special>()</span><span class=special>;
</span><span class=special>}
</span><span class=identifier>b</span><span class=special>();
</span><span class=special>}</span></pre>
<p>We have three functions <tt>a</tt>, <tt>b</tt> and <tt>c</tt> where <tt>c</tt>
is nested in <tt>b</tt> and <tt>b</tt> is nested in <tt>a</tt>. We also have
three variables <tt>va</tt>, <tt>vb</tt> and <tt>vc</tt>. The lifetime of each
of these local variables starts when the function where it is declared is entered
and ends when the function exits. The scope of a local variable spans all nested
functions inside the enclosing function where the variable is declared.</p>
<p>Going downstream from function <tt>a</tt> to function <tt>c</tt>, when function
a is entered, the variable <tt>va</tt> will be created in the stack. When function
<tt>b</tt> is entered (called by <tt>a</tt>), <tt>va</tt> is very well in scope
and is visble in <tt>b</tt>. At which point a fresh variable, <tt>vb</tt>, is
created on the stack. When function <tt>c</tt> is entered, both <tt>va</tt>
and <tt>vb</tt> are visibly in scope, and a fresh local variable <tt>vc</tt>
is created. </p>
<p>Going upstream, <tt>vc</tt> is not and cannot be visible outside the function
<tt>c</tt>. <tt>vc</tt>'s life has already expired once <tt>c</tt> exits. The
same is true with <tt>vb</tt>; vb is accessible in function <tt>c</tt> but not
in function <tt>a</tt>. </p>
<h2>Nested Mutually Recursive Rules</h2>
<p>Now consider that <tt>a</tt>, <tt>b</tt> and <tt>c</tt> are rules:</p>
<pre><span class=identifier> </span><span class=identifier>a </span><span class=special>= </span><span class=identifier>b </span><span class=special>>> </span><span class=special>*((</span><span class=literal>'+' </span><span class=special>>> </span><span class=identifier>b</span><span class=special>) </span><span class=special>| </span><span class=special>(</span><span class=literal>'-' </span><span class=special>>> </span><span class=identifier>b</span><span class=special>));
</span><span class=identifier>b </span><span class=special>= </span><span class=identifier>c </span><span class=special>>> </span><span class=special>*((</span><span class=literal>'*' </span><span class=special>>> </span><span class=identifier>c</span><span class=special>) </span><span class=special>| </span><span class=special>(</span><span class=literal>'/' </span><span class=special>>> </span><span class=identifier>c</span><span class=special>));
</span><span class=identifier>c </span><span class=special>= </span><span class=identifier>int_p </span><span class=special>| </span><span class=literal>'(' </span><span class=special>>> </span><span class=identifier>a </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>c</span><span class=special>) </span><span class=special>| </span><span class=special>(</span><span class=literal>'+' </span><span class=special>>> </span><span class=identifier>c</span><span class=special>);</span></pre>
<p>We can visualize <tt>a</tt>, <tt>b</tt> and <tt>c</tt> as mutually recursive
functions where <tt>a</tt> calls <tt>b</tt>, <tt>b</tt> calls <tt>c</tt> and
<tt>c</tt> recursively calls <tt>a</tt>. Now, imagine if <tt>a</tt>, <tt>b</tt>
and <tt>c</tt> each has a local variable named <tt>value</tt> that can be referred
to in our grammar by explicit qualification:</p>
<pre><span class=special> </span><span class=identifier>a</span><span class=special>.</span><span class=identifier>value </span><span class=comment>// refer to a's value local variable
</span><span class=identifier>b</span><span class=special>.</span><span class=identifier>value </span><span class=comment>// refer to b's value local variable
</span><span class=identifier>c</span><span class=special>.</span><span class=identifier>value </span><span class=comment>// refer to c's value local variable</span>
</pre>
<p>Like above, when <tt>a</tt> is entered, a local variable <tt>value</tt> is
created on the stack. This variable can be referred to by both <tt>b</tt> and
<tt>c</tt>. Again, when <tt>b</tt> is called by <tt>a</tt>, <tt>b</tt> creates
a local variable <tt>value</tt>. This variable is accessible by <tt>c</tt> but
not by <tt>a</tt>. </p>
<p>Here now is where the analogy with nested functions end: when <tt>c</tt> is
called, a fresh variable <tt>value</tt> is created which, as usual, lasts the
whole lifetime of <tt>c</tt>. Pay close attention however that <tt>c</tt> may
call <tt>a</tt> recursively. When this happens, <tt>a</tt> may now refer to
the local variable of <tt>c</tt>.</p>
<h2>What are Closures?</h2>
<p> Interestingly, nested functions demonstrate the flexibility of accessing a
local variable exixting in an outer scope. However, Spirit closures (inherited
from <a href="../../phoenix/index.html">Phoenix</a>) are more powerful than
what the nested function example suggests. </p>
<p>The closure as an object that <span class="quotes">"closes"</span>
over the local variables of a function making them visible and accessible outside
the function. What is more interesting is that the closure actually packages
a local context (stack frame where some variables reside) and make them available
outside the scope in which they actually exist. The information is essentially
<span class="quotes">"captured"</span> by the closure allowing it
to be referred to anywhere and anytime, even prior to the actual creation of
the variables. </p>
<p>The following diagram depicts the situation where a function <tt>A</tt> (or
rule) exposes its closure and another function <tt>B</tt> references <tt>A</tt>'s
variables through its closure.</p>
<table width="40%" border="0" align="center">
<tr>
<td><img src="theme/closure1.png"></td>
</tr>
<tr>
<td>
<div align="center"><b><font face="Geneva, Arial, Helvetica, san-serif" size="+1" color="#003399">The
closure as an object that <i>"closes"</i> over the local variables
of a function making them visible and accessible outside the function</font></b></div>
</td>
</tr>
</table>
<p>Of course, function <tt>A</tt> should be active when <tt>A.x</tt> is referenced.
What this means is that function <tt>B</tt> is reliant on function <tt>A</tt>
(If <tt>B</tt> is a nested function of <tt>A</tt>, this will always be the case).
The free form nature of Spirit rules allows access to a closure variable anytime,
anywhere. Acessing <tt>A.x</tt> is equivalent to referring to the topmost stack
variable <tt>x</tt> of function <tt>A</tt>. If function <tt>A</tt> is not active
when <tt>A.x</tt> is referenced, a runtime exception will be thrown.</p>
<h2>free_closure</h2>
<p> The free_closure class can be wrap any parser. Doing so will give a parser
its own closure. As an example, let us provide a parser with a closure with
two local variables:<tt> double x</tt> and <tt>int y</tt>.</p>
<p> First, we need to declare our closure:</p>
<pre>
<code><span class=keyword>struct </span><span class=identifier>my_closure </span><span class=special>: </span><span class=identifier>free_closure</span><span class=special><</span><span class=identifier>my_closure3</span><span class=special>, </span><span class=keyword>double</span><span class=special>, </span><span class=keyword>int</span><span class=special>>
</span><span class=special>{
</span><span class=identifier>member1 </span><span class=identifier>x</span><span class=special>;
</span><span class=identifier>member2 </span><span class=identifier>y</span><span class=special>;
</span><span class=special>};</span></code></pre>
<p> We subclass a user defined closure struct, <tt>my_closure</tt>, from free_closure.
The parameters to free_closure from left to right are:</p>
<p>1. The user defined my_closure.<br>
2. The type of the first closure member: double.<br>
3. The type of the second closure member: int.</p>
<p> <tt>member1</tt> and <tt>member2</tt> are indirect links to the actual closure
variables. Their indirect types correspond to double and int, respectively.</p>
<p> Now that it's declared, we can instantiate and use it:</p>
<pre>
<code><span class=identifier>rule</span><span class=special><> </span><span class=identifier>a</span><span class=special>, </span><span class=identifier>b</span><span class=special>, </span><span class=identifier>c</span><span class=special>;
</span><span class=identifier>my_closure </span><span class=identifier>clos</span><span class=special>;
</span><span class=identifier>a </span><span class=special>= </span><span class=identifier>clos</span><span class=special>[</span><span class=identifier>b </span><span class=special>>> </span><span class=identifier>c</span><span class=special>];</span></code></pre>
<p> <tt>clos</tt> provides a closure for the parser expression <tt>b >>
c</tt>. The closure variables <tt>x</tt> and <tt>y</tt> are accessible as <tt>clos.x</tt>
and <tt>clos.y</tt>:</p>
<pre>
<code><span class=identifier>c </span><span class=special>= </span><span class=identifier>real_p</span><span class=special>[</span><span class=identifier>clos</span><span class=special>.</span><span class=identifier>x </span><span class=special>= </span><span class=identifier>arg1</span><span class=special>];</span></code></pre>
<p> Using <a href="../../phoenix/index.html">Phoenix</a>, the result of real_p
is assigned to clos's closure member x.</p>
<p> The closure member1 is the closure's return value. This return value, like
the one returned by real_p, for example, can be used to propagate data up the
parser hierarchy or passed to semantic actions.</p>
<h2>closure</h2>
<p> In most cases, we want our closures to provide local variables for our rules
and grammars. To illustrate, consider a rule that parses even palindromes: A
parser that can recognize textual mirror images such as "abcddcba".
Without closures, this can be achieved by setting up a stack, pushing the first
parsed character into the stack, then recursively calling itself. Upon exit,
from the recursion, the pushed character from the stack is popped and used to
recognize the next parsed character to match. Tedious.</p>
<p> Using closures:</p>
<pre>
<code><span class=keyword>struct </span><span class=identifier>my_closure </span><span class=special>: </span><span class=identifier>spirit</span><span class=special>::</span><span class=identifier>closure</span><span class=special><</span><span class=identifier>my_closure</span><span class=special>, </span><span class=keyword>char</span><span class=special>>
</span><span class=special>{
</span><span class=identifier>member1 </span><span class=identifier>ch</span><span class=special>;
</span><span class=special>};
</span><span class=identifier>rule</span><span class=special><</span><span class=identifier>scanner</span><span class=special><>, </span><span class=identifier>my_closure</span><span class=special>::</span><span class=identifier>context_t</span><span class=special>> </span><span class=identifier>rev</span><span class=special>;
</span><span class=identifier>rev </span><span class=special>= </span><span class=identifier>anychar_p</span><span class=special>[</span><span class=identifier>rev</span><span class=special>.</span><span class=identifier>ch </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>rev </span><span class=special>>> </span><span class=identifier>fch_p</span><span class=special>(</span><span class=identifier>rev</span><span class=special>.</span><span class=identifier>ch</span><span class=special>);</span></code></pre>
<p> As before, we declare our closure first. This time, we need only one closure
member, a char. Take note that since we are providing a closure to a rule, we
subclass my_closure from closure rather than from free_closure.</p>
<p> Remember rule and grammar contexts? This is the closure's means to hook into
the grammar and rule. The closure has a special parser context that may be used
to enable rule and grammar closures.</p>
<pre>
<code><span class=identifier>rule</span><span class=special><</span><span class=identifier>scanner</span><span class=special><>, </span><span class=identifier>my_closure</span><span class=special>::</span><span class=identifier>context_t</span><span class=special>> </span><span class=identifier>rev</span><span class=special>;</span></code></pre>
<p> Declares a rule <tt>rev</tt> with our closure.</p>
<pre>
<code><span class=identifier>rev </span><span class=special>= </span><span class=identifier>anychar_p</span><span class=special>[</span><span class=identifier>rev</span><span class=special>.</span><span class=identifier>ch </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>rev </span><span class=special>>> </span><span class=identifier>fch_p</span><span class=special>(</span><span class=identifier>rev</span><span class=special>.</span><span class=identifier>ch</span><span class=special>);</span></code></pre>
<p> Defines our even palindrome parser. anychar_p parses any character and assigns
it to rev's sole closure member <tt>rev.ch</tt>. <tt>>> !rev</tt> recursively
calls itself. <tt>fch_p(rev.ch)</tt> attempts to recognize <tt>rev.ch</tt>.
<tt>fch_p</tt> is very similar to ch_p but accepts functors such as closure
member accesses (see <a href="parametric_parsers.html">Parametric Parsers</a>).</p>
<p> The same can be applied to grammars. Example:</p>
<pre>
<code><span class=keyword>struct </span><span class=identifier>my_grammar </span><span class=special>: </span><span class=keyword>public </span><span class=identifier>grammar</span><span class=special><</span><span class=identifier>my_grammar</span><span class=special>, </span><span class=identifier>my_closure</span><span class=special>::</span><span class=identifier>context_t</span><span class=special>>
</span><span class=special>{
</span><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>struct </span><span class=identifier>definition
</span><span class=special>{
</span><span class=identifier>definition</span><span class=special>(</span><span class=identifier>my_grammar </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>self</span><span class=special>)
</span><span class=special>{
</span><span class=comment>/*...*/
</span><span class=special>}
</span><span class=special>};
</span><span class=comment>/*...*/
</span><span class=special>};</span></code></pre>
<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="functional.html"><img src="theme/l_arr.gif" border="0"></a></td>
<td width="20"><a href="escape_char_parser.html"><img src="theme/r_arr.gif" border="0"></a></td>
</tr>
</table>
<br>
<hr size="1">
<p class="copyright">Copyright © 1998-2002 Joel de Guzman<br>
<br>
<font size="2">Permission to copy, use, modify, sell and distribute this document
is granted provided this copyright notice appears in all copies. This document
is provided "as is" without express or implied warranty, and with
no claim as to its suitability for any purpose. </font> </p>
</body>
</html>
