123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125 |
- <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html401/loose.dtd">
- <html>
- <!-- Created on November 8, 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.15.1 A Hierarchy of Sets</title>
- <meta name="description" content="avram - a virtual machine code interpreter: 2.7.15.1 A Hierarchy of Sets">
- <meta name="keywords" content="avram - a virtual machine code interpreter: 2.7.15.1 A Hierarchy of Sets">
- <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="A-Hierarchy-of-Sets"></a>
- <table cellpadding="1" cellspacing="1" border="0">
- <tr><td valign="middle" align="left">[<a href="Exception-Handling.html#Exception-Handling" title="Previous section in reading order"> < </a>]</td>
- <td valign="middle" align="left">[<a href="Operator-Generalization.html#Operator-Generalization" title="Next section in reading order"> > </a>]</td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left">[<a href="Virtual-Machine-Specification.html#Virtual-Machine-Specification" title="Beginning of this chapter or previous chapter"> << </a>]</td>
- <td valign="middle" align="left">[<a href="Exception-Handling.html#Exception-Handling" title="Up section"> Up </a>]</td>
- <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Next chapter"> >> </a>]</td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left"> </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="A-Hierarchy-of-Sets-1"></a>
- <h4 class="subsubsection">2.7.15.1 A Hierarchy of Sets</h4>
- <p>As indicated already, the virtual machine represents all functions and
- data as members of a set satisfying the properties in <a href="Raw-Material.html#Raw-Material">Raw Material</a>,
- namely a <code>nil</code> element and a <code>cons</code> operator for constructing
- trees or nested pairs of <code>nil</code>. However, it will be necessary to
- distinguish the results of computations that go wrong for exceptional
- reasons from normal results. Because any tree in the set could conceivably
- represent a normal result, we need to go outside the set to find an
- unambiguous representation of exceptional results.
- </p>
- <p>Because there may be many possible exceptional conditions, it will be helpful
- to have a large set of possible ways to encode them, and in fact there
- is no need to refrain from choosing a countably infinite
- set. Furthermore, it will be useful to distinguish between different
- levels of severity among exceptional conditions, so for this purpose a
- countably infinite hierarchy of mutually disjoint sets is used.
- </p>
- <p>In order to build on the theory already developed, the set that has been
- used up to this point will form the bottom level of the hierarchy, and
- its members will represent normal computational results. The members of
- sets on the higher levels in the hierarchy represent exceptional
- results. To avoid ambiguity, the term “trees” is reserved for members
- <a name="index-trees-3"></a>
- of the bottom set, as in “for any tree <code><var>x</var></code> …”.
- Unless otherwise stated, variables like <code><var>x</var></code> and
- <code><var>y</var></code> are universally quantified over the bottom set only.
- <a name="index-universal-quantification-1"></a>
- </p>
- <p>Because each set in the hierarchy is countably infinite, it is
- isomorphic to the bottom set. With respect to an arbitrary but fixed
- bijection between them, let <code><var>x</var>_<var>n</var></code> denote the image in
- the <code><var>n</var></code>th level set of a tree <code><var>x</var></code> in the bottom
- set. The level numbers in this notation start with zero, and we take
- <code><var>x</var>_0</code> to be synonymous with <code><var>x</var></code>. For good measure,
- let <code>(<var>x</var>_<var>n</var>)_<var>m</var></code> = <code><var>x</var>_(<var>n</var>+<var>m</var>)</code>.
- </p>
- <hr size="1">
- <table cellpadding="1" cellspacing="1" border="0">
- <tr><td valign="middle" align="left">[<a href="Exception-Handling.html#Exception-Handling" title="Previous section in reading order"> < </a>]</td>
- <td valign="middle" align="left">[<a href="Operator-Generalization.html#Operator-Generalization" title="Next section in reading order"> > </a>]</td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left">[<a href="Virtual-Machine-Specification.html#Virtual-Machine-Specification" title="Beginning of this chapter or previous chapter"> << </a>]</td>
- <td valign="middle" align="left">[<a href="Exception-Handling.html#Exception-Handling" title="Up section"> Up </a>]</td>
- <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Next chapter"> >> </a>]</td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left"> </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>November 8, 2012</i> using <a href="http://www.nongnu.org/texi2html/"><i>texi2html 1.82</i></a>.
- </font>
- <br>
- </p>
- </body>
- </html>
|