Sophie

Sophie

distrib > Fedora > 13 > i386 > media > os > by-pkgid > 52a37fb77746ef557a2ec666070d732e > files > 48

bigloo-doc-3.2b-3.fc12.i686.rpm

<!-- 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">&quot;Usage: grep STRING [FILE]...&quot;</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 (&gt;=fx o ls)
	    (<strong id='bold27422'
>let</strong> ((n (kmp-mmap t mm o)))
	       (when (&gt;fx n 0)
		  (print file <font color="red">&quot;:&quot;</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-&gt;fixnum ls)))
      <font color="#ffa600"><em id='it27429'
>;; beginning</em></font>
      (<strong id='bold27431'
>let</strong> loop ((i n))
	 (when (&gt;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 (&lt;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>

Perl :: Catalyst :: PostgreSQL :: RPM Valid HTML 4.01 Transitional