extra/lazy-lists/old-doc.html

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