<!-- 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>8. Bigloo<br/>A ``practical Scheme compiler''<br/>User manual for version 3.2b<br/>June 2009 -- Fast search</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='center27387' ><table width="97%" border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse;" frame="box" rules="none"><tbody> <tr bgcolor="#8381de"><th id="tc27377" align="center" colspan="1"><font color="#ffffff"><strong id='bold27375' >main page</strong></font></th></tr> <tr bgcolor="#ffffff"><td id="tc27384" align="center" colspan="1"><table width="100%" border="0" style="border-collapse: collapse;" frame="void" rules="none"><tbody> <tr><td id="tc27380" align="left" valign="top" colspan="1"><strong id='bold27379' >top:</strong></td><td id="tc27381" 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='center27397' ><table width="97%" border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse;" frame="box" rules="none"><tbody> <tr bgcolor="#8381de"><th id="tc27391" align="center" colspan="1"><font color="#ffffff"><strong id='bold27389' >Fast search</strong></font></th></tr> <tr bgcolor="#ffffff"><td id="tc27394" align="center" colspan="1"><table cellspacing="1" cellpadding="1" width="100%" class="toc"> <tbody> <tr><td valign="top" align="left">8.1</td><td colspan="4" width="100%"><a href="bigloo-9.html#Knuth-Morris-and-Pratt">Knuth, Morris, and Pratt</a></td></tr> </tbody> </table> </td></tr> </tbody></table> </center> <br/><br/><center id='center27407' ><table width="97%" border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse;" frame="box" rules="none"><tbody> <tr bgcolor="#8381de"><th id="tc27401" align="center" colspan="1"><font color="#ffffff"><strong id='bold27399' >Chapters</strong></font></th></tr> <tr bgcolor="#ffffff"><td id="tc27404" 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="Fast-search" class="mark"></a><a name="g14195" class="mark"></a> This chapters details the Bigloo's API for fast string search algorithms.<br/><br/><br/><br/><!-- Knuth, Morris, and Pratt --> <a name="Knuth-Morris-and-Pratt"></a> <div class="section-atitle"><table width="100%"><tr><td bgcolor="#dedeff"><h3><font color="black">8.1 Knuth, Morris, and Pratt</font> </h3></td></tr></table> </div><div class="section"> <a name="Knuth---Morris---Pratt" class="mark"></a><a name="g14199" class="mark"></a> Bigloo supports an implementation of the <em id='emph14201' >Knuth, Morris, and Pratt</em> algorithm on strings and memory mapped area, See <a href="bigloo-7.html#Memory-mapped-area" class="inbound">Memory mapped area</a>.<br/><br/><table cellspacing="0" class="frame" cellpadding="10" border="1" width="100%"><tbody> <tr><td><a name="g14204" class="mark"></a><a name="kmp-table" class="mark"></a><table width="100%" style="border-collapse: collapse;" frame="void" rules="none"><tbody> <tr><td id="tc14208" align="left" colspan="1"><strong id='bold14206' >kmp-table</strong><em id='it14207' > pattern</em></td><td id="tc14209" align="right" colspan="1">bigloo procedure</td></tr> </tbody></table> This function creates a <em id='emph14212' >kmp</em>-table used for fast search. </td></tr> </tbody></table><br/> <table cellspacing="0" class="frame" cellpadding="10" border="1" width="100%"><tbody> <tr><td><a name="g14216" class="mark"></a><a name="kmp-mmap" class="mark"></a><table width="100%" style="border-collapse: collapse;" frame="void" rules="none"><tbody> <tr><td id="tc14220" align="left" colspan="1"><strong id='bold14218' >kmp-mmap</strong><em id='it14219' > kmp-table mmap offset</em></td><td id="tc14221" align="right" colspan="1">bigloo procedure</td></tr> </tbody></table> <a name="g14225" class="mark"></a><a name="kmp-string" class="mark"></a><table width="100%" style="border-collapse: collapse;" frame="void" rules="none"><tbody> <tr><td id="tc14229" align="left" colspan="1"><strong id='bold14227' >kmp-string</strong><em id='it14228' > kmp-table string offset</em></td><td id="tc14230" align="right" colspan="1">bigloo procedure</td></tr> </tbody></table> This function searches the <code id='code14234' ><em id='it14233' >pattern</em></code> described by <code id='code14236' ><em id='it14235' >kmp-table</em></code> in the memory mapped area <code id='code14238' ><em id='it14237' >mmap</em></code> (respec. in the <code id='code14240' ><em id='it14239' >string</em></code>). The search starts at <code id='code14242' ><em id='it14241' >offset</em></code>. If an occurrence is found, its position in the <code id='code14244' ><em id='it14243' >mmap</em></code> is returned. Otherwise <code id='code14245' >-1</code> is returned.<br/><br/>For the sake of the example, here is a prototypal implementation of the Usenix command <code id='code14247' >grep</code>:<br/><br/><center id='center14271' ><table cellspacing="0" class="color" cellpadding="0" width="95%"><tbody> <tr><td bgcolor="#ffffcc"><pre class="prog" id='prog14269' >(<font color="#6959cf"><strong id='bold27408' >define</strong></font> (<font color="#6959cf"><strong id='bold27410' >main</strong></font> args) (<strong id='bold27412' >cond</strong> ((null? (cdr args)) (fprintf (current-error-port) <font color="red">"Usage: grep STRING [FILE]..."</font>) (exit 0)) (else (<strong id='bold27414' >let</strong> ((t (kmp-table (cadr args)))) (for-each (<strong id='bold27415' >lambda</strong> (f) (grep-file t f)) (cddr args))))))<br/><br/>(<font color="#6959cf"><strong id='bold27416' >define</strong></font> (<font color="#6959cf"><strong id='bold27418' >grep-file</strong></font> t file) (<strong id='bold27420' >let*</strong> ((mm (open-mmap file read: #t write: #f)) (ls (mmap-length mm))) (<strong id='bold27421' >let</strong> loop ((o 0)) (unless (>=fx o ls) (<strong id='bold27422' >let</strong> ((n (kmp-mmap t mm o))) (when (>fx n 0) (print file <font color="red">":"</font> (mmap-line mm ls n)) (loop (+fx n 1)))))) (close-mmap mm)))<br/><br/>(<font color="#6959cf"><strong id='bold27424' >define</strong></font> (<font color="#6959cf"><strong id='bold27426' >mmap-line</strong></font> mm ls n) (<strong id='bold27428' >let</strong> ((b 0) (e (elong->fixnum ls))) <font color="#ffa600"><em id='it27429' >;; beginning</em></font> (<strong id='bold27431' >let</strong> loop ((i n)) (when (>fx i 0) (<strong id='bold27432' >if</strong> (char=? (mmap-ref mm i) #\Newline) (<strong id='bold27433' >set!</strong> b (+fx i 1)) (loop (-fx i 1))))) <font color="#ffa600"><em id='it27434' >;; end</em></font> (<strong id='bold27436' >let</strong> loop ((i n)) (when (<fx i ls) (<strong id='bold27437' >if</strong> (char=? (mmap-ref mm i) #\Newline) (<strong id='bold27438' >set!</strong> e i) (loop (+fx i 1))))) (mmap-substring mm b (- e b)))) </pre> </td></tr> </tbody></table></center> </td></tr> </tbody></table><br/><br/><br/><br/><br/> </div><br> </div></td> </tr></table><div class="skribe-ending"> <hr> <p class="ending" id='paragraph27444' ><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='it27442' >Tue Jun 2 11:43:27 2009</em>.</font></p></div> </body> </html>