Sort.html 8.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162
  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.4 Sort</title>
  14. <meta name="description" content="avram - a virtual machine code interpreter: 2.7.13.4 Sort">
  15. <meta name="keywords" content="avram - a virtual machine code interpreter: 2.7.13.4 Sort">
  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="Sort"></a>
  40. <table cellpadding="1" cellspacing="1" border="0">
  41. <tr><td valign="middle" align="left">[<a href="Reduce.html#Reduce" title="Previous section in reading order"> &lt; </a>]</td>
  42. <td valign="middle" align="left">[<a href="Transfer.html#Transfer" 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="Sort-1"></a>
  58. <h4 class="subsubsection">2.7.13.4 Sort</h4>
  59. <a name="index-sort"></a>
  60. <p>Sorting is a frequently used operation that has the following standard
  61. representation in virtual code.
  62. </p>
  63. <dl compact="compact">
  64. <dt> <em>T25</em></dt>
  65. <dd><p>[[<code>sort</code>]] <code><var>p</var></code> = <code>((nil,nil),((<var>p</var>,nil),(nil,nil)))</code>
  66. </p></dd>
  67. </dl>
  68. <p>When an application in this form is evaluated with an operand
  69. representing a list, the result is a sorted version of the list.
  70. </p>
  71. <p>The way a list is sorted depends on what order is of interest. For
  72. example, numbers could be sorted in ascending or descending order,
  73. character strings could be sorted lexically or by length, etc.. The
  74. value of <code><var>p</var></code> is therefore needed in sorting applications to
  75. specify the order. It contains the virtual code for a partial order
  76. relational operator. This operator can be evaluated with any pair of
  77. items selected from a list, and should have a value of true if the left
  78. one should precede the right under the ordering. For example, if numbers
  79. were to be sorted in ascending order, then <code><var>p</var></code> would compute
  80. the &ldquo;less or equal&rdquo; relation, returning true if its operand were a
  81. pair of numbers in which the left is less or equal to the right.
  82. </p>
  83. <p>The virtual code semantics for sorting applications is given by these
  84. two properties, wherein <code><var>p</var></code> is a non-<code>nil</code> tree, and
  85. <code>insert</code> is a <code>silly</code> mnemonic to be defined next.
  86. <a name="index-insert"></a>
  87. </p>
  88. <dl compact="compact">
  89. <dt> <em>P31</em></dt>
  90. <dd><p>([[<code>sort</code>]] <code><var>p</var></code>) <code>nil</code> = <code>nil</code>
  91. </p></dd>
  92. <dt> <em>P32</em></dt>
  93. <dd><p>([[<code>sort</code>]] <code><var>p</var></code>) <code>(<var>x</var>,<var>y</var>)</code> = ([[<code>insert</code>]] <code><var>p</var></code>)
  94. <code>(<var>x</var>,</code>([[<code>sort</code>]] <code><var>p</var></code>) <code><var>y</var>)</code>
  95. </p></dd>
  96. </dl>
  97. <p>These properties say that the empty list is already sorted, and
  98. a non-empty list is sorted if its tail is sorted and the head is then
  99. inserted in the proper place. This specification of sorting has nothing
  100. to do with the sorting algorithm that <code>avram</code> really uses.
  101. </p>
  102. <p>The meaning of insertion is convenient to specify in virtual code
  103. itself. It should satisfy these three equations.
  104. </p>
  105. <dl compact="compact">
  106. <dt> <em>E4</em></dt>
  107. <dd><p>([[<code>insert</code>]] <code><var>p</var></code>) <code>(<var>x</var>,nil)</code> = <code>(<var>x</var>,nil)</code>
  108. </p></dd>
  109. <dt> <em>E5</em></dt>
  110. <dd><p>([[<code>insert</code>]] <code><var>p</var></code>) <code>(<var>x</var>,(<var>y</var>,<var>z</var>))</code> =
  111. <code>(<var>y</var>,</code>([[<code>insert</code>]] <code><var>p</var></code>) <code>(<var>x</var>,<var>z</var>))</code>
  112. if <code><var>p</var>(<var>x</var>,<var>y</var>)</code> = <code>nil</code>
  113. </p></dd>
  114. <dt> <em>E6</em></dt>
  115. <dd><p>([[<code>insert</code>]] <code><var>p</var></code>) <code>(<var>x</var>,(<var>y</var>,<var>z</var>)</code>) =
  116. <code>(<var>x</var>,(<var>y</var>,<var>z</var>))</code> if <code><var>p</var>(<var>x</var>,<var>y</var>)</code> is a non-<code>nil</code> tree
  117. </p></dd>
  118. </dl>
  119. <p>Intuitively, the right argument, whether <code>nil</code> or
  120. <code>(<var>y</var>,<var>z</var>)</code>, represents a list that is already sorted. The
  121. left argument <code><var>x</var></code> therefore only needs to be compared to the
  122. head element, <code><var>y</var></code> to ascertain whether or not it belongs at
  123. the beginning. If not, it should be inserted into the tail.
  124. </p>
  125. <p>A possible implementation of <code>insert</code> in <code>silly</code> is given in
  126. <a href="Insert.html#Insert">Insert</a>.
  127. </p>
  128. <hr size="1">
  129. <table cellpadding="1" cellspacing="1" border="0">
  130. <tr><td valign="middle" align="left">[<a href="Reduce.html#Reduce" title="Previous section in reading order"> &lt; </a>]</td>
  131. <td valign="middle" align="left">[<a href="Transfer.html#Transfer" title="Next section in reading order"> &gt; </a>]</td>
  132. <td valign="middle" align="left"> &nbsp; </td>
  133. <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>
  134. <td valign="middle" align="left">[<a href="List-Combinators.html#List-Combinators" title="Up section"> Up </a>]</td>
  135. <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Next chapter"> &gt;&gt; </a>]</td>
  136. <td valign="middle" align="left"> &nbsp; </td>
  137. <td valign="middle" align="left"> &nbsp; </td>
  138. <td valign="middle" align="left"> &nbsp; </td>
  139. <td valign="middle" align="left"> &nbsp; </td>
  140. <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
  141. <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
  142. <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
  143. <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
  144. </tr></table>
  145. <p>
  146. <font size="-1">
  147. This document was generated on <i>November 8, 2012</i> using <a href="http://www.nongnu.org/texi2html/"><i>texi2html 1.82</i></a>.
  148. </font>
  149. <br>
  150. </p>
  151. </body>
  152. </html>