txlyre
/
avram


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162
							<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html401/loose.dtd">
<html>
<!-- Created on December 10, 2012 by texi2html 1.82
texi2html was written by: 
            Lionel Cons <[email protected]> (original author)
            Karl Berry  <[email protected]>
            Olaf Bachmann <[email protected]>
            and many others.
Maintained by: Many creative people.
Send bugs and suggestions to <[email protected]>
-->
<head>
<title>avram - a virtual machine code interpreter: 2.7.13.4 Sort</title>

<meta name="description" content="avram - a virtual machine code interpreter: 2.7.13.4 Sort">
<meta name="keywords" content="avram - a virtual machine code interpreter: 2.7.13.4 Sort">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="texi2html 1.82">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
pre.display {font-family: serif}
pre.format {font-family: serif}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: serif; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: serif; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.roman {font-family:serif; font-weight:normal;}
span.sansserif {font-family:sans-serif; font-weight:normal;}
ul.toc {list-style: none}
-->
</style>


</head>

<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">

<a name="Sort"></a>
<table cellpadding="1" cellspacing="1" border="0">
<tr><td valign="middle" align="left">[<a href="Reduce.html#Reduce" title="Previous section in reading order"> &lt; </a>]</td>
<td valign="middle" align="left">[<a href="Transfer.html#Transfer" title="Next section in reading order"> &gt; </a>]</td>
<td valign="middle" align="left"> &nbsp; </td>
<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>
<td valign="middle" align="left">[<a href="List-Combinators.html#List-Combinators" title="Up section"> Up </a>]</td>
<td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Next chapter"> &gt;&gt; </a>]</td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
<td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
<td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
<td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
</tr></table>
<hr size="1">
<a name="Sort-1"></a>
<h4 class="subsubsection">2.7.13.4 Sort</h4>

<a name="index-sort"></a>
<p>Sorting is a frequently used operation that has the following standard
representation in virtual code.
</p>
<dl compact="compact">
<dt> <em>T25</em></dt>
<dd><p>[[<code>sort</code>]] <code><var>p</var></code> = <code>((nil,nil),((<var>p</var>,nil),(nil,nil)))</code>
</p></dd>
</dl>

<p>When an application in this form is evaluated with an operand
representing a list, the result is a sorted version of the list.
</p>
<p>The way a list is sorted depends on what order is of interest. For
example, numbers could be sorted in ascending or descending order,
character strings could be sorted lexically or by length, etc.. The
value of <code><var>p</var></code> is therefore needed in sorting applications to
specify the order. It contains the virtual code for a partial order
relational operator. This operator can be evaluated with any pair of
items selected from a list, and should have a value of true if the left
one should precede the right under the ordering. For example, if numbers
were to be sorted in ascending order, then <code><var>p</var></code> would compute
the &ldquo;less or equal&rdquo; relation, returning true if its operand were a
pair of numbers in which the left is less or equal to the right.
</p>
<p>The virtual code semantics for sorting applications is given by these
two properties, wherein <code><var>p</var></code> is a non-<code>nil</code> tree, and
<code>insert</code> is a <code>silly</code> mnemonic to be defined next.
<a name="index-insert"></a>
</p>
<dl compact="compact">
<dt> <em>P31</em></dt>
<dd><p>([[<code>sort</code>]] <code><var>p</var></code>) <code>nil</code> = <code>nil</code>
</p></dd>
<dt> <em>P32</em></dt>
<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>)
<code>(<var>x</var>,</code>([[<code>sort</code>]] <code><var>p</var></code>) <code><var>y</var>)</code>
</p></dd>
</dl>

<p>These properties say that the empty list is already sorted, and
a non-empty list is sorted if its tail is sorted and the head is then
inserted in the proper place. This specification of sorting has nothing
to do with the sorting algorithm that <code>avram</code> really uses.
</p>
<p>The meaning of insertion is convenient to specify in virtual code
itself. It should satisfy these three equations.
</p>
<dl compact="compact">
<dt> <em>E4</em></dt>
<dd><p>([[<code>insert</code>]] <code><var>p</var></code>) <code>(<var>x</var>,nil)</code> = <code>(<var>x</var>,nil)</code>
</p></dd>
<dt> <em>E5</em></dt>
<dd><p>([[<code>insert</code>]] <code><var>p</var></code>) <code>(<var>x</var>,(<var>y</var>,<var>z</var>))</code> =
<code>(<var>y</var>,</code>([[<code>insert</code>]] <code><var>p</var></code>) <code>(<var>x</var>,<var>z</var>))</code>
if <code><var>p</var>(<var>x</var>,<var>y</var>)</code> = <code>nil</code>
</p></dd>
<dt> <em>E6</em></dt>
<dd><p>([[<code>insert</code>]] <code><var>p</var></code>) <code>(<var>x</var>,(<var>y</var>,<var>z</var>)</code>) =
<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
</p></dd>
</dl>

<p>Intuitively, the right argument, whether <code>nil</code> or
<code>(<var>y</var>,<var>z</var>)</code>, represents a list that is already sorted. The
left argument <code><var>x</var></code> therefore only needs to be compared to the
head element, <code><var>y</var></code> to ascertain whether or not it belongs at
the beginning. If not, it should be inserted into the tail.
</p>
<p>A possible implementation of <code>insert</code> in <code>silly</code> is given in
<a href="Insert.html#Insert">Insert</a>.
</p>
<hr size="1">
<table cellpadding="1" cellspacing="1" border="0">
<tr><td valign="middle" align="left">[<a href="Reduce.html#Reduce" title="Previous section in reading order"> &lt; </a>]</td>
<td valign="middle" align="left">[<a href="Transfer.html#Transfer" title="Next section in reading order"> &gt; </a>]</td>
<td valign="middle" align="left"> &nbsp; </td>
<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>
<td valign="middle" align="left">[<a href="List-Combinators.html#List-Combinators" title="Up section"> Up </a>]</td>
<td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Next chapter"> &gt;&gt; </a>]</td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
<td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
<td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
<td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
</tr></table>
<p>
 <font size="-1">
  This document was generated on <i>December 10, 2012</i> using <a href="http://www.nongnu.org/texi2html/"><i>texi2html 1.82</i></a>.
 </font>
 <br>

</p>
</body>
</html>