Reduce.html 7.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133
  1. <html lang="en">
  2. <head>
  3. <title>Reduce - avram - a virtual machine code interpreter</title>
  4. <meta http-equiv="Content-Type" content="text/html">
  5. <meta name="description" content="avram - a virtual machine code interpreter">
  6. <meta name="generator" content="makeinfo 4.13">
  7. <link title="Top" rel="start" href="index.html#Top">
  8. <link rel="up" href="List-Combinators.html#List-Combinators" title="List Combinators">
  9. <link rel="prev" href="Filter.html#Filter" title="Filter">
  10. <link rel="next" href="Sort.html#Sort" title="Sort">
  11. <link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
  12. <meta http-equiv="Content-Style-Type" content="text/css">
  13. <style type="text/css"><!--
  14. pre.display { font-family:inherit }
  15. pre.format { font-family:inherit }
  16. pre.smalldisplay { font-family:inherit; font-size:smaller }
  17. pre.smallformat { font-family:inherit; font-size:smaller }
  18. pre.smallexample { font-size:smaller }
  19. pre.smalllisp { font-size:smaller }
  20. span.sc { font-variant:small-caps }
  21. span.roman { font-family:serif; font-weight:normal; }
  22. span.sansserif { font-family:sans-serif; font-weight:normal; }
  23. --></style>
  24. </head>
  25. <body>
  26. <div class="node">
  27. <a name="Reduce"></a>
  28. <p>
  29. Next:&nbsp;<a rel="next" accesskey="n" href="Sort.html#Sort">Sort</a>,
  30. Previous:&nbsp;<a rel="previous" accesskey="p" href="Filter.html#Filter">Filter</a>,
  31. Up:&nbsp;<a rel="up" accesskey="u" href="List-Combinators.html#List-Combinators">List Combinators</a>
  32. <hr>
  33. </div>
  34. <h5 class="subsubsection">2.7.13.3 Reduce</h5>
  35. <p><a name="index-g_t_0040code_007breduce_007d-321"></a>In the virtual code fragment shown below, <var>f</var> should be
  36. regarded as the virtual code for a binary operator, and <var>k</var>
  37. is a constant.
  38. <dl>
  39. <dt><em>T24</em><dd>[[<code>reduce</code>]] <code>(</code><var>f</var><code>,</code><var>k</var><code>)</code> = <code>((nil,nil),((</code><var>f</var><code>,</code><var>k</var><code>),nil))</code>
  40. </dl>
  41. <p class="noindent">By constructing a tree in the form shown, the <code>silly</code>
  42. mnemonic <code>reduce</code> effectively constructs the code for a function
  43. operating on lists in a particular way.
  44. <p>The effect of evaluating an application in this form with an argument
  45. representing a list can be broken down into several cases.
  46. <ul>
  47. <li>If the list is empty, then the value of <var>k</var> is the
  48. result.
  49. <li>If the list has only one item, then that item is the result.
  50. <li>if the list has exactly two items, the first being <var>x</var> and the
  51. second being <var>y</var>, then the result is <var>f</var><code>
  52. (</code><var>x</var><code>,</code><var>y</var><code>)</code>.
  53. <li>If the list has more than two items and an even number of them, the
  54. result is that of evaluating the application with the list of values
  55. obtained by partitioning the list into pairs of adjacent items, and
  56. evaluating <var>f</var> with each pair.
  57. <li>If the list has more than two items and an odd number of them, the
  58. result is that of evaluating the application with the list of values
  59. obtained by partitioning the list into pairs of adjacent items excluding
  60. the last one, evaluating <var>f</var> with each pair, and then
  61. appending the last item to the list of values.
  62. </ul>
  63. <p class="noindent">In the last two cases, evaluation of the application is not necessarily
  64. finished after just one traversal of the list, because it has to carry
  65. on until the list is reduced to a single item.
  66. <p>Some care has been taken to describe this operation in detail because it
  67. differs from comparable operations common to functional programming
  68. <a name="index-fold-322"></a>languages, variously known as fold or reduce. All of these operations
  69. could be used, for example, to compute the summation of a list of
  70. numbers. The crucial differences are as follows.
  71. <ul>
  72. <li>Whereas a fold or a reduce is conventionally either of the left or
  73. right variety, this <code>reduce</code> is neither.
  74. <li>The vacuous case result <var>k</var> is never used at all unless
  75. the argument is the empty list.
  76. <li>This <code>reduce</code> is not very useful if the operator
  77. <var>f</var> is not associative.
  78. </ul>
  79. <p>The reason for defining the semantics of <code>reduce</code> in this way
  80. instead of the normal way is that a distributed implementation of this
  81. <a name="index-distributed-implementation-323"></a>one could work in logarithmic time, so it's worth making it easy for a
  82. language processor to detect the pattern in case the virtual code is
  83. ever going to be targeted to such an implementation. Of course, nothing
  84. prevents the conventional left or right reduction semantics from being
  85. translated to virtual code by explicit recursion.
  86. <a name="index-recursion-324"></a>
  87. The precise semantics of this operation are as follows, where
  88. <var>f</var> is not <code>nil</code>, <var>k</var> is unconstrained, and
  89. <code>pairwise</code> represents a function to be explained presently.
  90. <a name="index-g_t_0040code_007biterate_007d-325"></a><a name="index-g_t_0040code_007bpairwise_007d-326"></a><a name="index-g_t_0040code_007bbu_007d-327"></a><a name="index-g_t_0040code_007bright_007d-328"></a>
  91. <dl>
  92. <dt><em>P29</em><dd>([[<code>reduce</code>]] <code>(</code><var>f</var><code>,</code><var>k</var><code>)</code>) <code>nil</code> = <var>k</var>
  93. <br><dt><em>P30</em><dd>([[<code>reduce</code>]] <code>(</code><var>f</var><code>,</code><var>k</var><code>)</code>) <code>(</code><var>x</var><code>,</code><var>y</var><code>)</code> = <br>
  94. &nbsp;<!-- /@w -->&nbsp;<!-- /@w -->&nbsp;<!-- /@w -->
  95. [[<code>left</code>]] ([[<code>bu(iterate,right)</code>]] [[<code>pairwise</code>]] <var>f</var>) <code>(</code><var>x</var><code>,</code><var>y</var><code>)</code>
  96. </dl>
  97. <p class="noindent">The latter property leverages off some virtual machine features and
  98. <code>silly</code> code that has been defined already. The function
  99. implemented by [[<code>pairwise</code>]] <var>f</var> is the one that
  100. partitions its argument into pairs and evaluates <var>f</var> with
  101. each pair as described above. The combination of that with
  102. <code>bu(iterate,right)</code> results in an application that repeatedly
  103. performs [[<code>pairwise</code>]] <var>f</var> while the resulting list
  104. still has a tail (i.e., a <code>right</code> side), and stops when the list
  105. has only a single item (i.e., when <code>right</code> is false). The
  106. <code>left</code> operation then extracts the item.
  107. <p>For the sake of completeness, it is tedious but straightforward to
  108. give an exact definition for <code>pairwise</code>. The short version is that
  109. it can be anything that satisfies these three equations.
  110. <dl>
  111. <dt><em>E1</em><dd>([[<code>pairwise</code>]] <var>f</var>) <code>nil</code> = <code>nil</code>
  112. <br><dt><em>E2</em><dd>([[<code>pairwise</code>]] <var>f</var>) <code>(</code><var>x</var><code>,nil)</code> = <code>(</code><var>x</var><code>,nil)</code>
  113. <br><dt><em>E3</em><dd>([[<code>pairwise</code>]] <var>f</var>) <code>(</code><var>x</var><code>,(</code><var>y</var><code>,</code><var>z</var><code>))</code> =
  114. <code>(</code><var>f</var><code> (</code><var>x</var><code>,</code><var>y</var><code>),</code>([[<code>pairwise</code>]] <var>f</var>) <var>z</var><code>)</code>
  115. </dl>
  116. <p class="noindent">For the long version, see <a href="Pairwise.html#Pairwise">Pairwise</a>.
  117. </body></html>