Raw-Material.html 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207
  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.1 Raw Material</title>
  14. <meta name="description" content="avram - a virtual machine code interpreter: 2.1 Raw Material">
  15. <meta name="keywords" content="avram - a virtual machine code interpreter: 2.1 Raw Material">
  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="Raw-Material"></a>
  40. <table cellpadding="1" cellspacing="1" border="0">
  41. <tr><td valign="middle" align="left">[<a href="Virtual-Machine-Specification.html#Virtual-Machine-Specification" title="Previous section in reading order"> &lt; </a>]</td>
  42. <td valign="middle" align="left">[<a href="Concrete-Syntax.html#Concrete-Syntax" 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="Virtual-Machine-Specification.html#Virtual-Machine-Specification" 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="Raw-Material-1"></a>
  58. <h2 class="section">2.1 Raw Material</h2>
  59. <p>The purpose of this section is to instill some basic concepts about the
  60. way information is stored or communicated by the virtual machine, which
  61. may be necessary for an understanding of subsequent sections.
  62. </p>
  63. <p>The virtual machine represents both programs and data as members of a
  64. semantic domain that is straightforward to describe. Lisp users and
  65. functional programmers may recognize familiar concepts of atoms and
  66. <a name="index-lists"></a>
  67. lists in this description. However, these terms are avoided for the
  68. moment, in order to keep this presentation self contained and to prevent
  69. knowledgeable readers from inferring any unintended meanings.
  70. </p>
  71. <p>As a rule, it is preferable to avoid overspecifying any theoretical
  72. artifact. In this spirit, the set of entities with which the virtual
  73. machine is concerned can be defined purely in terms of the properties we
  74. need it to have.
  75. </p>
  76. <dl compact="compact">
  77. <dt> <em>A distinguished element</em></dt>
  78. <dd><p>A particular element of the set is designated, arbitrarily or otherwise,
  79. as a distinguished element. Given any element of the set, it is
  80. always possible to decide whether or not it is the distinguished
  81. element. The set is non-empty and such an element exists.
  82. </p></dd>
  83. <dt> <em>A binary operator</em></dt>
  84. <dd><p>A map from pairs of elements of the set to elements of the set exists
  85. and meets these conditions.
  86. </p>
  87. <ul>
  88. <li> It associates a <em>unique</em> element of the set with any given
  89. ordered pair of elements from the set.
  90. </li><li> It does not associate the distinguished element with any pair of elements.
  91. </li></ul>
  92. </dd>
  93. </dl>
  94. <p>For the sake of concreteness, an additional constraint is needed:
  95. <em>the set has no proper subset satisfying the above conditions</em>. Any
  96. number of constructions remain within these criteria, but there is no
  97. need to restrict them further, because they are all equivalent for our
  98. purposes.
  99. </p>
  100. <p>To see that these properties provide all the structure we need for
  101. general purpose computation, we may suppose some given set <code>S</code> and
  102. an operator <code>cons</code> having them are fixed, and infer the following
  103. points.
  104. </p>
  105. <ul>
  106. <li> <code>S</code> contains at least one element, the distinguished
  107. element. Call it <code>nil</code>.
  108. <a name="index-nil"></a>
  109. </li><li> The pair <code>(nil,nil)</code> is a pair of
  110. elements of <code>S</code>, so there must be an element of <code>S</code> that
  111. <code>cons</code> associates with it. We can denote this element
  112. <code>cons(nil,nil)</code>.
  113. <a name="index-cons"></a>
  114. </li><li> As no pair of elements is associated with the
  115. distinguished element, <code>cons(nil,nil)</code> must differ from <code>nil</code>, so
  116. <code>S</code> contains at least two distinct elements.
  117. </li><li> The pair <code>(nil,cons(nil,nil))</code> therefore differs from <code>(nil,nil)</code>,
  118. but because it is yet another pair of elements from <code>S</code>, there
  119. must be an element associated with it by the operator. We can denote
  120. this element as <code>cons(nil,cons(nil,nil))</code>.
  121. </li><li> Inasmuch as the operator
  122. associates every pair of elements with a <em>unique</em> element,
  123. <code>cons(nil,cons(nil,nil))</code> must differ from the element associated
  124. with any other pair of elements, so it must differ from
  125. <code>cons(nil,nil)</code>, and we conclude that <code>nil</code>,
  126. <code>cons(nil,nil)</code> and <code>cons(nil,cons(nil,nil))</code> constitute three
  127. distinct elements of the set <code>S</code>.
  128. </li><li> By defining <code>cons(cons(nil,nil),nil)</code>
  129. and <code>cons(cons(nil,nil),cons(nil,nil))</code> analogously and following a
  130. similar line of reasoning, one may establish the existence of two more
  131. distinct elements of <code>S</code>.
  132. </li></ul>
  133. <p>It is not difficult to see that an argument in more general terms could
  134. show that the inclusion of infinitely many elements in <code>S</code> is
  135. mandated by the properties of the <code>cons</code> operator. Furthermore,
  136. every element of <code>S</code> other than <code>nil</code> owes its inclusion to
  137. being associated with some other pair of elements by <code>cons</code>,
  138. because if it were not, its exclusion would permit a proper subset of
  139. <code>S</code> to meet all of the above conditions. We can conclude that
  140. <code>S</code> contains exactly <code>nil</code> and the countable infinitude of
  141. elements of the form <code>cons(x,y)</code>, where <code>x</code> and <code>y</code> are
  142. either <code>nil</code> or something of the form <code>cons(&hellip;)</code> themselves.
  143. </p>
  144. <p>Some specific examples of sets and operators that have the required
  145. properties are as follows.
  146. </p>
  147. <ul>
  148. <li> the set of natural numbers, with <code>0</code> as the distinguished element,
  149. and the <code>cons</code> operator defined by <code>cons(<var>x</var>,<var>y</var>) =
  150. ((<var>x</var>+<var>y</var>)(<var>x</var>+<var>y</var>+1))/2 + <var>y</var> + 1</code>
  151. </li><li> a set of balanced strings of parentheses, with <code>()</code> as the
  152. distinguished element, and <code>cons</code> defined as string concatenation
  153. followed by enclosure in parentheses
  154. </li><li> a set of ordered binary trees, with the empty tree as the distinguished
  155. element, and the <code>cons</code> operator as that which takes an ordered
  156. pair of trees to the tree having them as its descendents
  157. </li><li> a set containing only its own Cartesian product and an arbitrary
  158. but fixed element <code>nil</code>, with <code>cons</code> being the identity
  159. function
  160. </li></ul>
  161. <p>Each of these models may suggest a different implementation, some of which
  162. are more practical than others. The remainder of this document is
  163. phrased somewhat imprecisely in terms of a combination of the latter
  164. two. The nature of the set in question is not considered further, and
  165. elements of the set are described as &ldquo;trees&rdquo; or &ldquo;lists&rdquo;. The
  166. <a name="index-trees"></a>
  167. <a name="index-lists-1"></a>
  168. distinguished element is denoted by <code>nil</code> and the operator by
  169. <code>cons</code>. Where no ambiguity results, <code>cons(x,y)</code> may be written
  170. simply as <code>(x,y)</code>. These terms should not be seen as constraints
  171. on the implementation.
  172. </p>
  173. <hr size="1">
  174. <table cellpadding="1" cellspacing="1" border="0">
  175. <tr><td valign="middle" align="left">[<a href="Virtual-Machine-Specification.html#Virtual-Machine-Specification" title="Previous section in reading order"> &lt; </a>]</td>
  176. <td valign="middle" align="left">[<a href="Concrete-Syntax.html#Concrete-Syntax" title="Next section in reading order"> &gt; </a>]</td>
  177. <td valign="middle" align="left"> &nbsp; </td>
  178. <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>
  179. <td valign="middle" align="left">[<a href="Virtual-Machine-Specification.html#Virtual-Machine-Specification" title="Up section"> Up </a>]</td>
  180. <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Next chapter"> &gt;&gt; </a>]</td>
  181. <td valign="middle" align="left"> &nbsp; </td>
  182. <td valign="middle" align="left"> &nbsp; </td>
  183. <td valign="middle" align="left"> &nbsp; </td>
  184. <td valign="middle" align="left"> &nbsp; </td>
  185. <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
  186. <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
  187. <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
  188. <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
  189. </tr></table>
  190. <p>
  191. <font size="-1">
  192. This document was generated on <i>November 8, 2012</i> using <a href="http://www.nongnu.org/texi2html/"><i>texi2html 1.82</i></a>.
  193. </font>
  194. <br>
  195. </p>
  196. </body>
  197. </html>