<!-- 95% W3C COMPLIANT, 95% CSS FREE, RAW HTML -->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=ISO-8859-1">
<title>BiglooA ``practical Scheme compiler''User manual for version 3.2bJune 2009</title>
<style type="text/css">
<!--
pre { font-family: monospace }
tt { font-family: monospace }
code { font-family: monospace }
p.flushright { text-align: right }
p.flushleft { text-align: left }
span.sc { font-variant: small-caps }
span.sf { font-family: sans-serif }
span.skribetitle { font-family: sans-serif; font-weight: bolder; font-size: x-large; }
span.refscreen { }
span.refprint { display: none; }
-->
</style>
</head>
<body class="chapter" bgcolor="#ffffff">
<table width="100%" class="skribetitle" cellspacing="0" cellpadding="0"><tbody>
<tr><td align="center" bgcolor="#8381de"><div class="skribetitle"><strong><big><big><big>7. Bigloo<br/>A ``practical Scheme compiler''<br/>User manual for version 3.2b<br/>June 2009 -- Pattern Matching</big></big></big></strong></div><center>
</center>
</td></tr></tbody></table>
<table cellpadding="3" cellspacing="0" width="100%" class="skribe-margins"><tr>
<td align="left" valign="top" class="skribe-left-margin" width="20%" bgcolor="#dedeff"><div class="skribe-left-margin">
<br/><center id='center27345'
><table width="97%" border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse;" frame="box" rules="none"><tbody>
<tr bgcolor="#8381de"><th id="tc27335" align="center" colspan="1"><font color="#ffffff"><strong id='bold27333'
>main page</strong></font></th></tr>
<tr bgcolor="#ffffff"><td id="tc27342" align="center" colspan="1"><table width="100%" border="0" style="border-collapse: collapse;" frame="void" rules="none"><tbody>
<tr><td id="tc27338" align="left" valign="top" colspan="1"><strong id='bold27337'
>top:</strong></td><td id="tc27339" align="right" valign="top" colspan="1"><a href="bigloo.html#Bigloo-A-``practical-Scheme-compiler''-User-manual-for-version-3.2b-June-2009" class="inbound">Bigloo<br/>A ``practical Scheme compiler''<br/>User manual for version 3.2b<br/>June 2009</a></td></tr>
</tbody></table>
</td></tr>
</tbody></table>
</center>
<br/><br/><center id='center27355'
><table width="97%" border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse;" frame="box" rules="none"><tbody>
<tr bgcolor="#8381de"><th id="tc27349" align="center" colspan="1"><font color="#ffffff"><strong id='bold27347'
>Pattern Matching</strong></font></th></tr>
<tr bgcolor="#ffffff"><td id="tc27352" align="center" colspan="1"><table cellspacing="1" cellpadding="1" width="100%" class="toc">
<tbody>
<tr><td valign="top" align="left">7.1</td><td colspan="4" width="100%"><a href="bigloo-8.html#Bigloo-pattern-matching-facilities">Bigloo pattern matching facilities</a></td></tr>
<tr><td valign="top" align="left">7.2</td><td colspan="4" width="100%"><a href="bigloo-8.html#The-pattern-language">The pattern language</a></td></tr>
</tbody>
</table>
</td></tr>
</tbody></table>
</center>
<br/><br/><center id='center27365'
><table width="97%" border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse;" frame="box" rules="none"><tbody>
<tr bgcolor="#8381de"><th id="tc27359" align="center" colspan="1"><font color="#ffffff"><strong id='bold27357'
>Chapters</strong></font></th></tr>
<tr bgcolor="#ffffff"><td id="tc27362" align="center" colspan="1"><table cellspacing="1" cellpadding="1" width="100%" class="toc">
<tbody>
<tr><td valign="top" align="left"></td><td colspan="4" width="100%"><a href="bigloo-1.html#Acknowledgements">Acknowledgements</a></td></tr>
<tr><td valign="top" align="left">1</td><td colspan="4" width="100%"><a href="bigloo-2.html#Table-of-contents">Table of contents</a></td></tr>
<tr><td valign="top" align="left">2</td><td colspan="4" width="100%"><a href="bigloo-3.html#Overview-of-Bigloo">Overview of Bigloo</a></td></tr>
<tr><td valign="top" align="left">3</td><td colspan="4" width="100%"><a href="bigloo-4.html#Modules">Modules</a></td></tr>
<tr><td valign="top" align="left">4</td><td colspan="4" width="100%"><a href="bigloo-5.html#Core-Language">Core Language</a></td></tr>
<tr><td valign="top" align="left">5</td><td colspan="4" width="100%"><a href="bigloo-6.html#DSSSL-support">DSSSL support</a></td></tr>
<tr><td valign="top" align="left">6</td><td colspan="4" width="100%"><a href="bigloo-7.html#Standard-Library">Standard Library</a></td></tr>
<tr><td valign="top" align="left">7</td><td colspan="4" width="100%"><a href="bigloo-8.html#Pattern-Matching">Pattern Matching</a></td></tr>
<tr><td valign="top" align="left">8</td><td colspan="4" width="100%"><a href="bigloo-9.html#Fast-search">Fast search</a></td></tr>
<tr><td valign="top" align="left">9</td><td colspan="4" width="100%"><a href="bigloo-10.html#Structures-and-Records">Structures and Records</a></td></tr>
<tr><td valign="top" align="left">10</td><td colspan="4" width="100%"><a href="bigloo-11.html#Object-System">Object System</a></td></tr>
<tr><td valign="top" align="left">11</td><td colspan="4" width="100%"><a href="bigloo-12.html#Regular-parsing">Regular parsing</a></td></tr>
<tr><td valign="top" align="left">12</td><td colspan="4" width="100%"><a href="bigloo-13.html#Lalr(1)-parsing">Lalr(1) parsing</a></td></tr>
<tr><td valign="top" align="left">13</td><td colspan="4" width="100%"><a href="bigloo-14.html#Posix-Regular-Expressions">Posix Regular Expressions</a></td></tr>
<tr><td valign="top" align="left">14</td><td colspan="4" width="100%"><a href="bigloo-15.html#Command-Line-Parsing">Command Line Parsing</a></td></tr>
<tr><td valign="top" align="left">15</td><td colspan="4" width="100%"><a href="bigloo-16.html#Cryptography">Cryptography</a></td></tr>
<tr><td valign="top" align="left">16</td><td colspan="4" width="100%"><a href="bigloo-17.html#Errors-Assertions-and-Traces">Errors, Assertions, and Traces</a></td></tr>
<tr><td valign="top" align="left">17</td><td colspan="4" width="100%"><a href="bigloo-18.html#Threads">Threads</a></td></tr>
<tr><td valign="top" align="left">18</td><td colspan="4" width="100%"><a href="bigloo-19.html#Database-library">Database library</a></td></tr>
<tr><td valign="top" align="left">19</td><td colspan="4" width="100%"><a href="bigloo-20.html#Multimedia-library">Multimedia library</a></td></tr>
<tr><td valign="top" align="left">20</td><td colspan="4" width="100%"><a href="bigloo-21.html#Mail-library">Mail library</a></td></tr>
<tr><td valign="top" align="left">21</td><td colspan="4" width="100%"><a href="bigloo-22.html#Eval-and-code-interpretation">Eval and code interpretation</a></td></tr>
<tr><td valign="top" align="left">22</td><td colspan="4" width="100%"><a href="bigloo-23.html#Macro-expansion">Macro expansion</a></td></tr>
<tr><td valign="top" align="left">23</td><td colspan="4" width="100%"><a href="bigloo-24.html#Parameters">Parameters</a></td></tr>
<tr><td valign="top" align="left">24</td><td colspan="4" width="100%"><a href="bigloo-25.html#Explicit-typing">Explicit typing</a></td></tr>
<tr><td valign="top" align="left">25</td><td colspan="4" width="100%"><a href="bigloo-26.html#The-C-interface">The C interface</a></td></tr>
<tr><td valign="top" align="left">26</td><td colspan="4" width="100%"><a href="bigloo-27.html#The-Java-interface">The Java interface</a></td></tr>
<tr><td valign="top" align="left">27</td><td colspan="4" width="100%"><a href="bigloo-28.html#Bigloo-Libraries">Bigloo Libraries</a></td></tr>
<tr><td valign="top" align="left">28</td><td colspan="4" width="100%"><a href="bigloo-29.html#Extending-the-Runtime-System">Extending the Runtime System</a></td></tr>
<tr><td valign="top" align="left">29</td><td colspan="4" width="100%"><a href="bigloo-30.html#SRFIs">SRFIs</a></td></tr>
<tr><td valign="top" align="left">30</td><td colspan="4" width="100%"><a href="bigloo-31.html#Compiler-description">Compiler description</a></td></tr>
<tr><td valign="top" align="left">31</td><td colspan="4" width="100%"><a href="bigloo-32.html#User-Extensions">User Extensions</a></td></tr>
<tr><td valign="top" align="left">32</td><td colspan="4" width="100%"><a href="bigloo-33.html#Bigloo-Development-Environment">Bigloo Development Environment</a></td></tr>
<tr><td valign="top" align="left">33</td><td colspan="4" width="100%"><a href="bigloo-34.html#Global-Index">Global Index</a></td></tr>
<tr><td valign="top" align="left">34</td><td colspan="4" width="100%"><a href="bigloo-35.html#Library-Index">Library Index</a></td></tr>
<tr><td valign="top" align="left"></td><td colspan="4" width="100%"><a href="bigloo-36.html#Bibliography">Bibliography</a></td></tr>
</tbody>
</table>
</td></tr>
</tbody></table>
</center>
</div></td>
<td align="left" valign="top" class="skribe-body"><div class="skribe-body">
<a name="Pattern-Matching" class="mark"></a><a name="g14016" class="mark"></a>
Pattern matching is a key feature of most modern functional programming
languages since it allows clean and secure code to be
written. Internally, ``pattern-matching forms'' should be translated
(compiled) into cascades of ``elementary tests'' where code is made as
efficient as possible, avoiding redundant tests; Bigloo's ``pattern
matching compiler'' provides this. The technique used is described in
details in [QueinnecGeffroy92], and the code generated can be considered
optimal <a href="#footnote-footnote14018"><sup><small>1</small></sup></a> due to the way this ``pattern
compiler'' was obtained.<br/><br/>The ``pattern language'' allows the expression of a wide variety of patterns,
including:<br/><br/><ul class="itemize" id='itemize14030'
><li>Non-linear patterns: pattern variables can appear more than
once, allowing comparison of subparts of the datum (through <code id='code14021'
>eq?</code>)<br/><br/></li>
<li>Recursive patterns on lists: for example, checking that the
datum is a list of zero or more <code id='code14024'
>a</code>s followed by zero or more
<code id='code14025'
>b</code>s.<br/><br/></li>
<li>Pattern matching on lists as well as on vectors and structures,
and record types.<br/><br/></li>
</ul>
<br/><br/><!-- Bigloo pattern matching facilities -->
<a name="Bigloo-pattern-matching-facilities"></a>
<div class="section-atitle"><table width="100%"><tr><td bgcolor="#dedeff"><h3><font color="black">7.1 Bigloo pattern matching facilities</font>
</h3></td></tr></table>
</div><div class="section">
<a name="Bigloo-Pattern-Matching-Facilities" class="mark"></a>
Only two special forms are provided for this in Bigloo: <code id='code14032'
>match-case</code>
and <code id='code14033'
>match-lambda</code>.<br/><br/><table cellspacing="0" class="frame" cellpadding="10" border="1" width="100%"><tbody>
<tr><td><a name="g14036" class="mark"></a><a name="match-case" class="mark"></a><table width="100%" style="border-collapse: collapse;" frame="void" rules="none"><tbody>
<tr><td id="tc14040" align="left" colspan="1"><strong id='bold14038'
>match-case</strong><em id='it14039'
> key clause...</em></td><td id="tc14041" align="right" colspan="1">bigloo syntax</td></tr>
</tbody></table>
The argument <code id='code14045'
><em id='it14044'
>key</em></code> may be any expression and each <code id='code14047'
><em id='it14046'
>clause</em></code> has the form<br/><br/><center id='center14055'
><table cellspacing="0" class="color" cellpadding="0" width="95%"><tbody>
<tr><td bgcolor="#ffffcc"><pre class="prog" id='prog14053'
>(<code id='code14050'
><em id='it14049'
>pattern</em></code> <code id='code14052'
><em id='it14051'
>s-expression</em></code>...)
</pre>
</td></tr>
</tbody></table></center>
<em id='emph14056'
>Semantics: </em> A <code id='code14057'
>match-case</code> expression is evaluated as
follows. <code id='code14059'
><em id='it14058'
>key</em></code> is evaluated and the result is compared with each
successive pattern. If the pattern in some <code id='code14061'
><em id='it14060'
>clause</em></code> yields a match, then
the expressions in that <code id='code14063'
><em id='it14062'
>clause</em></code> are evaluated from left to right in an
environment where the pattern variables are bound to the corresponding
subparts of the datum, and the result of the last expression in that
<code id='code14065'
><em id='it14064'
>clause</em></code> is returned as the result of the <code id='code14066'
>match-case</code> expression.
If no <code id='code14068'
><em id='it14067'
>pattern</em></code> in any <code id='code14070'
><em id='it14069'
>clause</em></code> matches the datum, then, if there is an
<code id='code14071'
>else</code> clause, its expressions are evaluated and the result of the last
is the result of the whole <code id='code14072'
>match-case</code> expression; otherwise the result
of the <code id='code14073'
>match-case</code> expression is unspecified.<br/><br/>The equality predicate used is <code id='code14075'
>eq?</code>.<br/><br/><center id='center14080'
><table cellspacing="0" class="color" cellpadding="0" width="95%"><tbody>
<tr><td bgcolor="#ffffcc"><pre class="prog" id='prog14078'
>(<strong id='bold27366'
>match-case</strong> '(a b a)
((?x ?x) 'foo)
((?x ?- ?x) 'bar))
=> bar
</pre>
</td></tr>
</tbody></table></center>
</td></tr>
</tbody></table><br/>
The following syntax is also available:<br/><br/><table cellspacing="0" class="frame" cellpadding="10" border="1" width="100%"><tbody>
<tr><td><a name="g14085" class="mark"></a><a name="match-lambda" class="mark"></a><table width="100%" style="border-collapse: collapse;" frame="void" rules="none"><tbody>
<tr><td id="tc14089" align="left" colspan="1"><strong id='bold14087'
>match-lambda</strong><em id='it14088'
> clause...</em></td><td id="tc14090" align="right" colspan="1">bigloo syntax</td></tr>
</tbody></table>
It expands into a lambda-expression expecting an argument which, once
applied to an expression, behaves exactly like a <code id='code14093'
>match-case</code>
expression.<br/><br/><center id='center14098'
><table cellspacing="0" class="color" cellpadding="0" width="95%"><tbody>
<tr><td bgcolor="#ffffcc"><pre class="prog" id='prog14096'
>((<strong id='bold27367'
>match-lambda</strong>
((?x ?x) 'foo)
((?x ?- ?x) 'bar))
'(a b a))
=> bar
</pre>
</td></tr>
</tbody></table></center>
</td></tr>
</tbody></table><br/>
</div><br>
<!-- The pattern language -->
<a name="The-pattern-language"></a>
<div class="section-atitle"><table width="100%"><tr><td bgcolor="#dedeff"><h3><font color="black">7.2 The pattern language</font>
</h3></td></tr></table>
</div><div class="section">
<a name="The-Pattern-Language" class="mark"></a><a name="g14101" class="mark"></a>
The syntax for <pattern> is:<br/><br/><center id='center14131'
><table cellspacing="0" class="color" cellpadding="0" width="95%"><tbody>
<tr><td bgcolor="#ccccff"><pre class="prog" id='prog14129'
><pattern> ==> <em id='emph14104'
>Matches:</em><br/><br/> <atom> the <atom>.
| (<code id='code14106'
>kwote</code> <atom>) any expression <code id='code14107'
>eq?</code> to <code id='code14108'
><atom></code>.
| (<code id='code14109'
>and</code> <pat1> ... <patn>) if all of <code id='code14112'
><pat<code id='code14111'
><em id='it14110'
>i</em></code>></code> match.
| (<code id='code14113'
>or</code> <pat1> ... ...<patn>) if any of <code id='code14114'
><pat1></code> through <code id='code14115'
><patn></code> matches.
| (<code id='code14116'
>not</code> <pat>) if <code id='code14117'
><pat></code> doesn't match.
| (<code id='code14118'
>?</code> <predicate>) if <code id='code14119'
><predicate></code> is true.
| (<pat1> ... <patn>) a list of n elements. Here, <code id='code14120'
>...</code> is a
meta-character denoting a finite repetition
of patterns.
| <pat> ... a (possibly empty) repetition
of <code id='code14121'
><pat></code> in a list.
| #(<pat> ... <patn>) a vector of <code id='code14123'
><em id='it14122'
>n</em></code> elements.
| #{<struct> <pat> ... } a structure.
| <code id='code14124'
>?</code><id> anything, and binds <code id='code14125'
>id</code> as a variable.
| <code id='code14126'
>?-</code> anything.
| <code id='code14127'
>??-</code> any (possibly empty) repetition of anything
in a list.
| <code id='code14128'
>???-</code> any end of list.
</pre>
</td></tr>
</tbody></table></center>
<em id='emph14132'
>Remark: </em> <code id='code14133'
>and, or, not, check</code> and <code id='code14134'
>kwote</code> must be
quoted in order to be treated as literals. This is the only justification
for having the <code id='code14135'
>kwote</code> pattern since, by convention, any atom which is
not a keyword is quoted.<br/><br/><!-- Explanations through examples -->
<a name="Explanations-through-examples"></a>
<div class="subsubsection-atitle"><h4><font color="#8381de">Explanations through examples</font>
</h4></div><div class="subsubsection">
<ul class="itemize" id='itemize14186'
><li><code id='code14137'
>?-</code> matches any s-expr
</li>
<li><code id='code14139'
>a</code> matches the atom <code id='code14140'
>'a</code>.
</li>
<li><code id='code14142'
>?a</code> matches any expression, and binds the variable <code id='code14143'
>a</code> to
this expression.<br/><br/></li>
<li><code id='code14146'
>(? integer?)</code> matches any integer
</li>
<li><code id='code14148'
>(a (a b))</code> matches the only list <code id='code14149'
>'(a (a b))</code>.
</li>
<li><code id='code14151'
>???-</code> can only appear at the end of a list, and always succeeds.
For instance, <code id='code14152'
>(a ???-)</code> is equivalent to <code id='code14153'
>(a . ?-)</code>.<br/><br/></li>
<li>when occurring in a list, <code id='code14156'
>??-</code> matches any sequence of anything:
<code id='code14157'
>(a ??- b)</code> matches any list whose <code id='code14158'
>car</code> is <code id='code14159'
>a</code> and last
<code id='code14160'
>car</code> is <code id='code14161'
>b</code>. <br/><br/></li>
<li><code id='code14164'
>(a ...)</code> matches any list of <code id='code14165'
>a</code>'s, possibly empty.
</li>
<li><code id='code14167'
>(?x ?x)</code> matches any list of length 2 whose <code id='code14168'
>car</code> is
<em id='emph14169'
>eq</em> to its <code id='code14170'
>cadr</code><br/><br/></li>
<li><code id='code14173'
>((and (not a) ?x) ?x)</code> matches any list of length 2 whose
<code id='code14174'
>car</code> is not <em id='emph14175'
>eq</em> to <code id='code14176'
>'a</code> but is <em id='emph14177'
>eq</em> to its <code id='code14178'
>cadr</code><br/><br/></li>
<li><code id='code14181'
>#(?- ?- ???-)</code> matches any vector whose length is at least 2.
</li>
<li><code id='code14183'
>#{foo (?- . ?-) (? integer?)}</code> matches any structure or
record <code id='code14184'
>foo</code> whose first and second fields are respectively a pair and an
integer. You can provide only the fields you want to test. The order is not
relevant.
</li>
</ul>
<em id='emph14187'
>Remark: </em> <code id='code14188'
>??-</code> and <code id='code14189'
>...</code> patterns can not appear
inside a vector, where you should use <code id='code14190'
>???-</code>: For example,
<code id='code14191'
>#(a ??- b)</code> or <code id='code14192'
>#(a...)</code> are invalid patterns, whereas
<code id='code14193'
>#(a ???-)</code> is valid and matches any vector whose first element
is the atom <code id='code14194'
>a</code>.
</div>
</div><br>
<div class="footnote"><br><br>
<hr width='20%' size='2' align='left'>
<a name="footnote-footnote14018"><sup><small>1</small></sup></a>: In the cases of pattern matching in lists and vectors,
not in structures for the moment.
<br>
<div></div></td>
</tr></table><div class="skribe-ending">
<hr>
<p class="ending" id='paragraph27373'
><font size="-1">
This <span class="sc">Html</span> page has been produced by
<a href="http://www.inria.fr/mimosa/fp/Skribe" class="http">Skribe</a>.
<br/>
Last update <em id='it27371'
>Tue Jun 2 11:43:27 2009</em>.</font></p></div>
</body>
</html>
distrib
>
Fedora
>
13
>
i386
>
media
>
os
>
by-pkgid
>
52a37fb77746ef557a2ec666070d732e
>
files
>
47
