basis/lists/lazy/old-doc.html

   1 <!DOCTYPE html>
   2 <html>
   3   <head>
   4     <title>Lazy Evaluation</title>
   5     <link rel="stylesheet" type="text/css" href="style.css">
   6       </head>
   7   <body>
   8     <h1>Lazy Evaluation</h1>
   9 <p>The 'lazy' vocabulary adds lazy lists to Factor. This provides the
  10     ability to describe infinite structures, and to delay execution of
  11     expressions until they are actually used.</p>
  12 <p>Lazy lists, like normal lists, are composed of a head and tail. In
  13     a lazy list the head and tail are something called a 'promise'.
  14     To convert a
  15     'promise' into its actual value a word called 'force' is used. To
  16     convert a value into a 'promise' the word to use is 'delay'.</p>
  17 <table border="1">
  18 <tr><td><a href="#delay">delay</a></td></tr>
  19 <tr><td><a href="#force">force</a></td></tr>
  20 </table>
  21
  22 <p>Many of the lazy list words are named similar to the standard list
  23     words but with an 'l' prefixed to it. Here are the commonly used
  24     words and their equivalent list operation:</p>
  25 <table border="1">
  26 <tr><th>Lazy List</th><th>Normal List</th></tr>
  27 <tr><td><a href="#lnil">lnil</a></td><td>[ ]</td></tr>
  28 <tr><td><a href="#lnilp">lnil?</a></td><td>Test for nil value</td></tr>
  29 <tr><td><a href="#lcons">lcons</a></td><td>cons</td></tr>
  30 <tr><td><a href="#lunit">lunit</a></td><td>unit</td></tr>
  31 <tr><td><a href="#lcar">lcar</a></td><td>car</td></tr>
  32 <tr><td><a href="#lcdr">lcdr</a></td><td>cdr</td></tr>
  33 <tr><td><a href="#lnth">lnth</a></td><td>nth</td></tr>
  34 <tr><td><a href="#luncons">luncons</a></td><td>uncons</td></tr>
  35 <tr><td><a href="#lmap">lmap</a></td><td>map</td></tr>
  36 <tr><td><a href="#lsubset">lsubset</a></td><td>subset</td></tr>
  37 <tr><td><a href="#leach">leach</a></td><td>each</td></tr>
  38 <tr><td><a href="#lappend">lappend</a></td><td>append</td></tr>
  39 </table>
  40 <p>A few additional words specific to lazy lists are:</p>
  41 <table border="1">
  42 <tr><td><a href="#ltake">ltake</a></td><td>Returns a normal list containing a specified
  43 number of items from the lazy list.</td></tr>
  44 <tr><td><a href="#lappendstar">lappend*</a></td><td>Given a lazy list of lazy lists,
  45 concatenate them together in a lazy manner, returning a single lazy
  46 list.</td></tr>
  47 <tr><td><a href="#list>llist">list>llist</a></td><td>Given a normal list, return a lazy list
  48 that contains the same elements as the normal list.</td></tr>
  49 </table>
  50 <h2>Reference</h2>
  51 <!-- delay description -->
  52 <a name="delay">
  53 <h3>delay ( quot -- &lt;promise&gt; )</h3>
  54 <p>'delay' is used to convert a value or expression into a promise.
  55    The word 'force' is used to convert that promise back to its
  56    value, or to force evaluation of the expression to return a value.
  57 </p>
  58 <p>The value on the stack that 'delay' expects must be quoted. This is
  59    a requirement to prevent it from being evaluated.
  60 </p>
  61 <pre class="code">
  62   ( 1 ) [ 42 ] <a href="#delay">delay</a> dup .
  63        => &lt;&lt; promise [ ] [ 42 ] [ ] [ ] &gt;&gt;
  64   ( 2 ) <a href="#force">force</a> .
  65        => 42
  66 </pre>
  67
  68 <!-- force description -->
  69 <a name="force">
  70 <h3>force ( &lt;promise&gt; -- value )</h3>
  71 <p>'force' will evaluate a promises original expression
  72    and leave the value of that expression on the stack.
  73 </p>
  74 <p>A promise can be forced multiple times but the expression
  75    is only evaluated once. Future calls of 'force' on the promise
  76    will returned the cached value of the original force. If the
  77    expression contains side effects, such as i/o, then that i/o
  78    will only occur on the first 'force'. See below for an example
  79    (steps 3-5).
  80 </p>
  81 <p>If a promise is itself delayed, a force will evaluate all promises
  82    until a value is returned. Due to this behaviour it is generally not
  83    possible to delay a promise. The example below shows what happens
  84    in this case.
  85 </p>
  86 <pre class="code">
  87   ( 1 ) [ 42 ] <a href="#delay">delay</a> dup .
  88        => &lt;&lt; promise [ ] [ 42 ] [ ] [ ] &gt;&gt;
  89   ( 2 ) <a href="#force">force</a> .
  90        => 42
  91
  92         #! Multiple forces on a promise returns cached value
  93   ( 3 ) [ "hello" print 42 ] <a href="#delay">delay</a> dup .
  94        => << promise [ ] [ "hello" print 42 ] [ ] [ ] >>
  95   ( 4 ) dup <a href="#force">force</a> .
  96        => hello
  97           42
  98   ( 5 ) <a href="#force">force</a> .
  99        => 42
 100
 101         #! Forcing a delayed promise cascades up to return
 102         #! original value, rather than the promise.
 103   ( 6 ) [ [ 42 ] <a href="#delay">delay</a> ] <a href="#delay">delay</a> dup .
 104        => << promise [ ] [ [ 42 ] delay ] [ ] [ ] >>
 105   ( 7 ) <a href="#force">force</a> .
 106        => 42
 107 </pre>
 108
 109 <!-- lnil description -->
 110 <a name="lnil">
 111 <h3>lnil ( -- lcons )</h3>
 112 <p>Returns a value representing the empty lazy list.</p>
 113 <pre class="code">
 114   ( 1 ) <a href="#lnil">lnil</a> .
 115        => << promise [ ] [ [ ] ] t [ ] >>
 116 </pre>
 117
 118 <!-- lnil description -->
 119 <a name="lnilp">
 120 <h3>lnil? ( lcons -- bool )</h3>
 121 <p>Returns true if the given lazy cons is the value representing
 122    the empty lazy list.</p>
 123 <pre class="code">
 124   ( 1 ) <a href="#lnil">lnil</a> <a href="#lnilp">lnil?</a> .
 125        => t
 126   ( 2 ) [ 1 ] <a href="#list2llist">list&gt;llist</a> dup <a href="#lnilp">lnil?</a> .
 127        => [ ]
 128   ( 3 ) <a href="#lcdr">lcdr</a> <a href="#lnilp">lnil?</a> .
 129        => t
 130 </pre>
 131
 132 <!-- lcons description -->
 133 <a name="lcons">
 134 <h3>lcons ( car-promise cdr-promise -- lcons )</h3>
 135 <p>Provides the same effect as 'cons' does for normal lists.
 136    Both values provided must be promises (ie. expressions that have
 137    had <a href="#delay">delay</a> called on them).
 138 </p>
 139 <p>As the car and cdr passed on the stack are promises, they are not
 140    evaluated until <a href="#lcar">lcar</a> or <a href="#lcdr">lcdr</a>
 141    are called on the lazy cons.</p>
 142 <pre class="code">
 143   ( 1 ) [ "car" ] <a href="#delay">delay</a> [ "cdr" ] <a href="#delay">delay</a> <a href="#lcons">lcons</a> dup .
 144        => &lt;&lt; promise ... &gt;&gt;
 145   ( 2 ) dup <a href="#lcar">lcar</a> .
 146        => "car"
 147   ( 3 ) dup <a href="#lcdr">lcdr</a> .
 148        => "cdr"
 149 </pre>
 150
 151 <!-- lunit description -->
 152 <a name="lunit">
 153 <h3>lunit ( value-promise -- llist )</h3>
 154 <p>Provides the same effect as 'unit' does for normal lists. It
 155 creates a lazy list where the first element is the value given.</p>
 156 <p>Like <a href="#lcons">lcons</a>, the value on the stack must be
 157    a promise and is not evaluated until the <a href="#lcar">lcar</a>
 158    of the list is requested.</a>
 159 <pre class="code">
 160   ( 1 ) [ 42 ] <a href="#delay">delay</a> <a href="#lunit">lunit</a> dup .
 161        => &lt;&lt; promise ... &gt;&gt;
 162   ( 2 ) dup <a href="#lcar">lcar</a> .
 163        => 42
 164   ( 3 ) dup <a href="#lcdr">lcdr</a> <a href="#lnilp">lnil?</a> .
 165        => t
 166   ( 4 ) [ . ] <a href="#leach">leach</a>
 167        => 42
 168 </pre>
 169
 170 <!-- lcar description -->
 171 <a name="lcar">
 172 <h3>lcar ( lcons -- value )</h3>
 173 <p>Provides the same effect as 'car' does for normal lists. It
 174 returns the first element in a lazy cons cell. This will force
 175 the evaluation of that element.</p>
 176 <pre class="code">
 177   ( 1 ) [ 42 ] <a href="#delay">delay</a> <a href="#lunit">lunit</a> dup .
 178        => &lt;&lt; promise ... &gt;&gt;
 179   ( 2 ) <a href="#lcar">lcar</a> .
 180        => 42
 181 </pre>
 182
 183 <!-- lcdr description -->
 184 <a name="lcdr">
 185 <h3>lcdr ( lcons -- value )</h3>
 186 <p>Provides the same effect as 'cdr' does for normal lists. It
 187 returns the second element in a lazy cons cell and forces it. This
 188 causes that element to be evaluated immediately.</p>
 189 <pre class="code">
 190   ( 1 ) [ 1 ] <a href="#delay">delay</a> [ 5 6 + ] <a href="#delay">delay</a> <a href="#lcons">lcons</a> dup .
 191        => &lt;&lt; promise ... &gt;&gt;
 192   ( 2 ) <a href="#lcdr">lcdr</a> .
 193        => 11
 194 </pre>
 195
 196 <pre class="code">
 197   ( 1 ) 5 <a href="#lfrom">lfrom</a> dup .
 198        => &lt;&lt; promise ... &gt;&gt;
 199   ( 2 ) <a href="#lcdr">lcdr</a> dup <a href="#lcar">lcar</a> .
 200        => 6
 201   ( 3 ) <a href="#lcdr">lcdr</a> dup <a href="#lcar">lcar</a> .
 202        => 7
 203   ( 4 ) <a href="#lcdr">lcdr</a> dup <a href="#lcar">lcar</a> .
 204        => 8
 205 </pre>
 206
 207 <!-- lnth description -->
 208 <a name="lnth">
 209 <h3>lnth ( n llist -- value )</h3>
 210 <p>Provides the same effect as 'nth' does for normal lists. It
 211 returns the nth value in the lazy list. It causes all the values up to
 212 'n' to be evaluated.</p>
 213 <pre class="code">
 214   ( 1 ) 1 <a href="#lfrom">lfrom</a> dup .
 215        => &lt;&lt; promise ... &gt;&gt;
 216   ( 2 ) 5 swap <a href="#lnth">lnth</a> .
 217        => 6
 218 </pre>
 219
 220 <!-- luncons description -->
 221 <a name="luncons">
 222 <h3>luncons ( lcons -- car cdr )</h3>
 223 <p>Provides the same effect as 'uncons' does for normal lists. It
 224 returns the car and cdr of the lazy list.</p>
 225 <pre class="code">
 226   ( 1 ) [ 5 ] <a href="#delay">delay</a> [ 6 ] <a  href="#delay">delay</a> <a href="#lcons">lcons</a> dup .
 227        => &lt;&lt; promise ... &gt;&gt;
 228   ( 2 ) <a href="#luncons">luncons</a> . .
 229        => 6
 230           5
 231 </pre>
 232
 233 <!-- lmap description -->
 234 <a name="lmap">
 235 <h3>lmap ( llist quot -- llist )</h3>
 236 <p>Lazily maps over a lazy list applying the quotation to each element.
 237 A new lazy list is returned which contains the results of the
 238 quotation.</p>
 239 <p>When intially called nothing in the original lazy list is
 240 evaluated. Only when <a href="#lcar">lcar</a> is called will the item
 241 in the list be evaluated and applied to the quotation. Ditto with <a
 242 href="#lcdr">lcdr</a>, thus allowing infinite lists to be mapped over.</p>
 243 <pre class="code">
 244   ( 1 ) 1 <a href="#lfrom">lfrom</a>
 245        => < infinite list of incrementing numbers >
 246   ( 2 ) [ 2 * ] <a href="#lmap">lmap</a>
 247        => < infinite list of numbers incrementing by 2 >
 248   ( 3 ) 5 swap <a href="#ltake">ltake</a> <a  href="#llist2list">llist&gt;list</a> .
 249        => [ 2 4 6 8 10 ]
 250 </pre>
 251
 252 <!-- lsubset description -->
 253 <a name="lsubset">
 254 <h3>lsubset ( llist pred -- llist )</h3>
 255 <p>Provides the same effect as 'subset' does for normal lists. It
 256 lazily iterates over a lazy list applying the predicate quotation to each
 257 element. If that quotation returns true, the element will be included
 258 in the resulting lazy list. If it is false, the element will be skipped.
 259 A new lazy list is returned which contains  all elements where the
 260 predicate returned true.</p>
 261 <p>Like <a href="#lmap">lmap</a>, when initially called no evaluation
 262 will occur. A lazy list is returned that when values are retrieved
 263 from in then items are evaluated and checked against the predicate.</p>
 264 <pre class="code">
 265   ( 1 ) 1 <a href="#lfrom">lfrom</a>
 266        => < infinite list of incrementing numbers >
 267   ( 2 ) [ <a href="#primep">prime?</a> ] <a href="#lsubset">lsubset</a>
 268        => < infinite list of prime numbers >
 269   ( 3 ) 5 swap <a href="#ltake">ltake</a> <a  href="#llist2list">llist&gt;list</a> .
 270        => [ 2 3 5 7 11 ]
 271 </pre>
 272
 273 <!-- leach description -->
 274 <a name="leach">
 275 <h3>leach ( llist quot --  )</h3>
 276 <p>Provides the same effect as 'each' does for normal lists. It
 277 lazily iterates over a lazy list applying the quotation to each
 278 element. If this operation is applied to an infinite list it will
 279 never return unless the quotation escapes out by calling a continuation.</p>
 280 <pre class="code">
 281   ( 1 ) 1 <a href="#lfrom">lfrom</a>
 282        => < infinite list of incrementing numbers >
 283   ( 2 ) [ 2 mod 1 = ] <a href="#lsubset">lsubset</a>
 284        => < infinite list of odd numbers >
 285   ( 3 ) [ . ] <a href="#leach">leach</a>
 286        => 1
 287           3
 288           5
 289           7
 290           ... for ever ...
 291 </pre>
 292
 293 <!-- ltake description -->
 294 <a name="ltake">
 295 <h3>ltake ( n llist -- llist )</h3>
 296 <p>Iterates over the lazy list 'n' times, appending each element to a
 297 lazy list. This provides a convenient way of getting elements out of
 298 an infinite lazy list.</p>
 299 <pre class="code">
 300   ( 1 ) : ones [ 1 ] delay [ ones ] delay <a href="#lcons">lcons</a> ;
 301   ( 2 ) 5 ones <a href="#ltake">ltake</a> <a  href="#llist2list">llist&gt;list</a> .
 302        => [ 1 1 1 1 1  ]
 303 </pre>
 304
 305 <!-- lappend description -->
 306 <a name="lappend">
 307 <h3>lappend ( llist1 llist2 -- llist )</h3>
 308 <p>Lazily appends two lists together. The actual appending is done
 309 lazily on iteration rather than immediately so it works very fast no
 310 matter how large the list.</p>
 311 <pre class="code">
 312   ( 1 ) [ 1 2 3 ] <a href="#list2llist">list&gt;llist</a> [ 4 5 6 ] <a href="#list2llist">list&gt;llist</a> <a href="#lappend">lappend</a>
 313   ( 2 ) [ . ] <a href="#leach">leach</a>
 314        => 1
 315           2
 316           3
 317           4
 318           5
 319           6
 320 </pre>
 321
 322 <!-- lappend* description -->
 323 <a name="lappendstar">
 324 <h3>lappend* ( llists -- llist )</h3>
 325 <p>Given a lazy list of lazy lists, concatenate them together in a
 326 lazy fashion. The actual appending is done lazily on iteration rather
 327 than immediately so it works very fast no matter how large the lists.</p>
 328 <pre class="code">
 329   ( 1 ) [ 1 2 3 ] <a href="#list2>llist">list&gt;llist</a>
 330   ( 2 ) [ 4 5 6 ] <a href="#list2llist">list&gt;llist</a>
 331   ( 3 ) [ 7 8 9 ] <a href="#list2llist">list&gt;llist</a>
 332   ( 4 ) 3list <a href="#list2llist">list&gt;llist</a> <a href="#lappendstar">lappend*</a>
 333   ( 5 ) [ . ] <a href="#leach">leach</a>
 334        => 1
 335           2
 336           3
 337           4
 338           5
 339           6
 340           7
 341           8
 342           9
 343 </pre>
 344
 345 <!-- list>llist description -->
 346 <a name="list2llist">
 347 <h3>list&gt;llist ( list  -- llist )</h3>
 348 <p>Converts a normal list into a lazy list. This is done lazily so the
 349 initial list is not iterated through immediately.</p>
 350 <pre class="code">
 351   ( 1 ) [ 1 2 3 ] <a href="#list2llist">list&gt;llist</a>
 352   ( 2 ) [ . ] <a href="#leach">leach</a>
 353        => 1
 354           2
 355           3
 356 </pre>
 357
 358 <p class="footer">
 359 News and updates to this software can be obtained from the authors
 360 weblog: <a href="http://radio.weblogs.com/0102385">Chris Double</a>.</p>
 361 <p id="copyright">Copyright (c) 2004, Chris Double. All Rights Reserved.</p>
 362 </body> </html>