A-Hierarchy-of-Sets.html 7.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125
  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.15.1 A Hierarchy of Sets</title>
  14. <meta name="description" content="avram - a virtual machine code interpreter: 2.7.15.1 A Hierarchy of Sets">
  15. <meta name="keywords" content="avram - a virtual machine code interpreter: 2.7.15.1 A Hierarchy of Sets">
  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="A-Hierarchy-of-Sets"></a>
  40. <table cellpadding="1" cellspacing="1" border="0">
  41. <tr><td valign="middle" align="left">[<a href="Exception-Handling.html#Exception-Handling" title="Previous section in reading order"> &lt; </a>]</td>
  42. <td valign="middle" align="left">[<a href="Operator-Generalization.html#Operator-Generalization" 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="Exception-Handling.html#Exception-Handling" 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="A-Hierarchy-of-Sets-1"></a>
  58. <h4 class="subsubsection">2.7.15.1 A Hierarchy of Sets</h4>
  59. <p>As indicated already, the virtual machine represents all functions and
  60. data as members of a set satisfying the properties in <a href="Raw-Material.html#Raw-Material">Raw Material</a>,
  61. namely a <code>nil</code> element and a <code>cons</code> operator for constructing
  62. trees or nested pairs of <code>nil</code>. However, it will be necessary to
  63. distinguish the results of computations that go wrong for exceptional
  64. reasons from normal results. Because any tree in the set could conceivably
  65. represent a normal result, we need to go outside the set to find an
  66. unambiguous representation of exceptional results.
  67. </p>
  68. <p>Because there may be many possible exceptional conditions, it will be helpful
  69. to have a large set of possible ways to encode them, and in fact there
  70. is no need to refrain from choosing a countably infinite
  71. set. Furthermore, it will be useful to distinguish between different
  72. levels of severity among exceptional conditions, so for this purpose a
  73. countably infinite hierarchy of mutually disjoint sets is used.
  74. </p>
  75. <p>In order to build on the theory already developed, the set that has been
  76. used up to this point will form the bottom level of the hierarchy, and
  77. its members will represent normal computational results. The members of
  78. sets on the higher levels in the hierarchy represent exceptional
  79. results. To avoid ambiguity, the term &ldquo;trees&rdquo; is reserved for members
  80. <a name="index-trees-3"></a>
  81. of the bottom set, as in &ldquo;for any tree <code><var>x</var></code> &hellip;&rdquo;.
  82. Unless otherwise stated, variables like <code><var>x</var></code> and
  83. <code><var>y</var></code> are universally quantified over the bottom set only.
  84. <a name="index-universal-quantification-1"></a>
  85. </p>
  86. <p>Because each set in the hierarchy is countably infinite, it is
  87. isomorphic to the bottom set. With respect to an arbitrary but fixed
  88. bijection between them, let <code><var>x</var>_<var>n</var></code> denote the image in
  89. the <code><var>n</var></code>th level set of a tree <code><var>x</var></code> in the bottom
  90. set. The level numbers in this notation start with zero, and we take
  91. <code><var>x</var>_0</code> to be synonymous with <code><var>x</var></code>. For good measure,
  92. let <code>(<var>x</var>_<var>n</var>)_<var>m</var></code> = <code><var>x</var>_(<var>n</var>+<var>m</var>)</code>.
  93. </p>
  94. <hr size="1">
  95. <table cellpadding="1" cellspacing="1" border="0">
  96. <tr><td valign="middle" align="left">[<a href="Exception-Handling.html#Exception-Handling" title="Previous section in reading order"> &lt; </a>]</td>
  97. <td valign="middle" align="left">[<a href="Operator-Generalization.html#Operator-Generalization" title="Next section in reading order"> &gt; </a>]</td>
  98. <td valign="middle" align="left"> &nbsp; </td>
  99. <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>
  100. <td valign="middle" align="left">[<a href="Exception-Handling.html#Exception-Handling" title="Up section"> Up </a>]</td>
  101. <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Next chapter"> &gt;&gt; </a>]</td>
  102. <td valign="middle" align="left"> &nbsp; </td>
  103. <td valign="middle" align="left"> &nbsp; </td>
  104. <td valign="middle" align="left"> &nbsp; </td>
  105. <td valign="middle" align="left"> &nbsp; </td>
  106. <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
  107. <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
  108. <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
  109. <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
  110. </tr></table>
  111. <p>
  112. <font size="-1">
  113. This document was generated on <i>November 8, 2012</i> using <a href="http://www.nongnu.org/texi2html/"><i>texi2html 1.82</i></a>.
  114. </font>
  115. <br>
  116. </p>
  117. </body>
  118. </html>