Reduce.html 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205
  1. <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html401/loose.dtd">
  2. <html>
  3. <!-- Created on November 8, 2012 by texi2html 1.82
  4. texi2html was written by:
  5. Lionel Cons <[email protected]> (original author)
  6. Karl Berry <[email protected]>
  7. Olaf Bachmann <[email protected]>
  8. and many others.
  9. Maintained by: Many creative people.
  10. Send bugs and suggestions to <[email protected]>
  11. -->
  12. <head>
  13. <title>avram - a virtual machine code interpreter: 2.7.13.3 Reduce</title>
  14. <meta name="description" content="avram - a virtual machine code interpreter: 2.7.13.3 Reduce">
  15. <meta name="keywords" content="avram - a virtual machine code interpreter: 2.7.13.3 Reduce">
  16. <meta name="resource-type" content="document">
  17. <meta name="distribution" content="global">
  18. <meta name="Generator" content="texi2html 1.82">
  19. <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
  20. <style type="text/css">
  21. <!--
  22. a.summary-letter {text-decoration: none}
  23. blockquote.smallquotation {font-size: smaller}
  24. pre.display {font-family: serif}
  25. pre.format {font-family: serif}
  26. pre.menu-comment {font-family: serif}
  27. pre.menu-preformatted {font-family: serif}
  28. pre.smalldisplay {font-family: serif; font-size: smaller}
  29. pre.smallexample {font-size: smaller}
  30. pre.smallformat {font-family: serif; font-size: smaller}
  31. pre.smalllisp {font-size: smaller}
  32. span.roman {font-family:serif; font-weight:normal;}
  33. span.sansserif {font-family:sans-serif; font-weight:normal;}
  34. ul.toc {list-style: none}
  35. -->
  36. </style>
  37. </head>
  38. <body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
  39. <a name="Reduce"></a>
  40. <table cellpadding="1" cellspacing="1" border="0">
  41. <tr><td valign="middle" align="left">[<a href="Filter.html#Filter" title="Previous section in reading order"> &lt; </a>]</td>
  42. <td valign="middle" align="left">[<a href="Sort.html#Sort" title="Next section in reading order"> &gt; </a>]</td>
  43. <td valign="middle" align="left"> &nbsp; </td>
  44. <td valign="middle" align="left">[<a href="Virtual-Machine-Specification.html#Virtual-Machine-Specification" title="Beginning of this chapter or previous chapter"> &lt;&lt; </a>]</td>
  45. <td valign="middle" align="left">[<a href="List-Combinators.html#List-Combinators" title="Up section"> Up </a>]</td>
  46. <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Next chapter"> &gt;&gt; </a>]</td>
  47. <td valign="middle" align="left"> &nbsp; </td>
  48. <td valign="middle" align="left"> &nbsp; </td>
  49. <td valign="middle" align="left"> &nbsp; </td>
  50. <td valign="middle" align="left"> &nbsp; </td>
  51. <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
  52. <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
  53. <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
  54. <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
  55. </tr></table>
  56. <hr size="1">
  57. <a name="Reduce-1"></a>
  58. <h4 class="subsubsection">2.7.13.3 Reduce</h4>
  59. <a name="index-reduce"></a>
  60. <p>In the virtual code fragment shown below, <code><var>f</var></code> should be
  61. regarded as the virtual code for a binary operator, and <code><var>k</var></code>
  62. is a constant.
  63. </p>
  64. <dl compact="compact">
  65. <dt> <em>T24</em></dt>
  66. <dd><p>[[<code>reduce</code>]] <code>(<var>f</var>,<var>k</var>)</code> = <code>((nil,nil),((<var>f</var>,<var>k</var>),nil))</code>
  67. </p></dd>
  68. </dl>
  69. <p>By constructing a tree in the form shown, the <code>silly</code>
  70. mnemonic <code>reduce</code> effectively constructs the code for a function
  71. operating on lists in a particular way.
  72. </p>
  73. <p>The effect of evaluating an application in this form with an argument
  74. representing a list can be broken down into several cases.
  75. </p>
  76. <ul>
  77. <li> If the list is empty, then the value of <code><var>k</var></code> is the
  78. result.
  79. </li><li> If the list has only one item, then that item is the result.
  80. </li><li> if the list has exactly two items, the first being <code><var>x</var></code> and the
  81. second being <code><var>y</var></code>, then the result is <code><var>f</var>
  82. (<var>x</var>,<var>y</var>)</code>.
  83. </li><li> If the list has more than two items and an even number of them, the
  84. result is that of evaluating the application with the list of values
  85. obtained by partitioning the list into pairs of adjacent items, and
  86. evaluating <code><var>f</var></code> with each pair.
  87. </li><li> If the list has more than two items and an odd number of them, the
  88. result is that of evaluating the application with the list of values
  89. obtained by partitioning the list into pairs of adjacent items excluding
  90. the last one, evaluating <code><var>f</var></code> with each pair, and then
  91. appending the last item to the list of values.
  92. </li></ul>
  93. <p>In the last two cases, evaluation of the application is not necessarily
  94. finished after just one traversal of the list, because it has to carry
  95. on until the list is reduced to a single item.
  96. </p>
  97. <p>Some care has been taken to describe this operation in detail because it
  98. differs from comparable operations common to functional programming
  99. <a name="index-fold"></a>
  100. languages, variously known as fold or reduce. All of these operations
  101. could be used, for example, to compute the summation of a list of
  102. numbers. The crucial differences are as follows.
  103. </p>
  104. <ul>
  105. <li> Whereas a fold or a reduce is conventionally either of the left or
  106. right variety, this <code>reduce</code> is neither.
  107. </li><li> The vacuous case result <code><var>k</var></code> is never used at all unless
  108. the argument is the empty list.
  109. </li><li> This <code>reduce</code> is not very useful if the operator
  110. <code><var>f</var></code> is not associative.
  111. </li></ul>
  112. <p>The reason for defining the semantics of <code>reduce</code> in this way
  113. instead of the normal way is that a distributed implementation of this
  114. <a name="index-distributed-implementation-1"></a>
  115. one could work in logarithmic time, so it&rsquo;s worth making it easy for a
  116. language processor to detect the pattern in case the virtual code is
  117. ever going to be targeted to such an implementation. Of course, nothing
  118. prevents the conventional left or right reduction semantics from being
  119. translated to virtual code by explicit recursion.
  120. <a name="index-recursion-2"></a>
  121. </p>
  122. <p>The precise semantics of this operation are as follows, where
  123. <code><var>f</var></code> is not <code>nil</code>, <code><var>k</var></code> is unconstrained, and
  124. <code>pairwise</code> represents a function to be explained presently.
  125. <a name="index-iterate-1"></a>
  126. <a name="index-pairwise"></a>
  127. <a name="index-bu-1"></a>
  128. <a name="index-right-2"></a>
  129. </p>
  130. <dl compact="compact">
  131. <dt> <em>P29</em></dt>
  132. <dd><p>([[<code>reduce</code>]] <code>(<var>f</var>,<var>k</var>)</code>) <code>nil</code> = <code><var>k</var></code>
  133. </p></dd>
  134. <dt> <em>P30</em></dt>
  135. <dd><p>([[<code>reduce</code>]] <code>(<var>f</var>,<var>k</var>)</code>) <code>(<var>x</var>,<var>y</var>)</code> = <br>
  136. [[<code>left</code>]] ([[<code>bu(iterate,right)</code>]] [[<code>pairwise</code>]] <code><var>f</var></code>) <code>(<var>x</var>,<var>y</var>)</code>
  137. </p></dd>
  138. </dl>
  139. <p>The latter property leverages off some virtual machine features and
  140. <code>silly</code> code that has been defined already. The function
  141. implemented by [[<code>pairwise</code>]] <code><var>f</var></code> is the one that
  142. partitions its argument into pairs and evaluates <code><var>f</var></code> with
  143. each pair as described above. The combination of that with
  144. <code>bu(iterate,right)</code> results in an application that repeatedly
  145. performs [[<code>pairwise</code>]] <code><var>f</var></code> while the resulting list
  146. still has a tail (i.e., a <code>right</code> side), and stops when the list
  147. has only a single item (i.e., when <code>right</code> is false). The
  148. <code>left</code> operation then extracts the item.
  149. </p>
  150. <p>For the sake of completeness, it is tedious but straightforward to
  151. give an exact definition for <code>pairwise</code>. The short version is that
  152. it can be anything that satisfies these three equations.
  153. </p>
  154. <dl compact="compact">
  155. <dt> <em>E1</em></dt>
  156. <dd><p>([[<code>pairwise</code>]] <code><var>f</var></code>) <code>nil</code> = <code>nil</code>
  157. </p></dd>
  158. <dt> <em>E2</em></dt>
  159. <dd><p>([[<code>pairwise</code>]] <code><var>f</var></code>) <code>(<var>x</var>,nil)</code> = <code>(<var>x</var>,nil)</code>
  160. </p></dd>
  161. <dt> <em>E3</em></dt>
  162. <dd><p>([[<code>pairwise</code>]] <code><var>f</var></code>) <code>(<var>x</var>,(<var>y</var>,<var>z</var>))</code> =
  163. <code>(<var>f</var> (<var>x</var>,<var>y</var>),</code>([[<code>pairwise</code>]] <code><var>f</var></code>) <code><var>z</var>)</code>
  164. </p></dd>
  165. </dl>
  166. <p>For the long version, see <a href="Pairwise.html#Pairwise">Pairwise</a>.
  167. </p>
  168. <hr size="1">
  169. <table cellpadding="1" cellspacing="1" border="0">
  170. <tr><td valign="middle" align="left">[<a href="Filter.html#Filter" title="Previous section in reading order"> &lt; </a>]</td>
  171. <td valign="middle" align="left">[<a href="Sort.html#Sort" title="Next section in reading order"> &gt; </a>]</td>
  172. <td valign="middle" align="left"> &nbsp; </td>
  173. <td valign="middle" align="left">[<a href="Virtual-Machine-Specification.html#Virtual-Machine-Specification" title="Beginning of this chapter or previous chapter"> &lt;&lt; </a>]</td>
  174. <td valign="middle" align="left">[<a href="List-Combinators.html#List-Combinators" title="Up section"> Up </a>]</td>
  175. <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Next chapter"> &gt;&gt; </a>]</td>
  176. <td valign="middle" align="left"> &nbsp; </td>
  177. <td valign="middle" align="left"> &nbsp; </td>
  178. <td valign="middle" align="left"> &nbsp; </td>
  179. <td valign="middle" align="left"> &nbsp; </td>
  180. <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
  181. <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
  182. <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
  183. <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
  184. </tr></table>
  185. <p>
  186. <font size="-1">
  187. This document was generated on <i>November 8, 2012</i> using <a href="http://www.nongnu.org/texi2html/"><i>texi2html 1.82</i></a>.
  188. </font>
  189. <br>
  190. </p>
  191. </body>
  192. </html>