A-Minimal-Set-of-Properties.html 9.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166
  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.3 A Minimal Set of Properties</title>
  14. <meta name="description" content="avram - a virtual machine code interpreter: 2.7.3 A Minimal Set of Properties">
  15. <meta name="keywords" content="avram - a virtual machine code interpreter: 2.7.3 A Minimal Set of Properties">
  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-Minimal-Set-of-Properties"></a>
  40. <table cellpadding="1" cellspacing="1" border="0">
  41. <tr><td valign="middle" align="left">[<a href="On-Equality.html#On-Equality" title="Previous section in reading order"> &lt; </a>]</td>
  42. <td valign="middle" align="left">[<a href="A-Simple-Lisp-Like-Language.html#A-Simple-Lisp-Like-Language" 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-Code-Semantics.html#Virtual-Code-Semantics" 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-Minimal-Set-of-Properties-1"></a>
  58. <h3 class="subsection">2.7.3 A Minimal Set of Properties</h3>
  59. <p>For any trees <code><var>x</var></code>, <code><var>y</var></code>, and <code><var>k</var></code>, and any non-<code>nil</code>
  60. trees <code><var>p</var></code>, <code><var>f</var></code>, and <code><var>g</var></code>, the new invisible operator satisfies these
  61. conditions. In these expressions and hereafter, increasing abuse of
  62. notation is perpetrated by not writing the <code>cons</code> in expressions of the form
  63. <code>cons(<var>x</var>,<var>y</var>)</code>.
  64. </p>
  65. <dl compact="compact">
  66. <dt> <em>P0</em></dt>
  67. <dd><p><code>(nil,(nil,nil)) <var>x</var></code> = <code><var>x</var></code>
  68. </p></dd>
  69. <dt> <em>P1</em></dt>
  70. <dd><p><code>(nil,((nil,nil),nil)) (<var>x</var>,<var>y</var>)</code> = <code><var>x</var></code>
  71. </p></dd>
  72. <dt> <em>P2</em></dt>
  73. <dd><p><code>(nil,(nil,(nil,nil))) (<var>x</var>,<var>y</var>)</code> = <code><var>y</var></code>
  74. </p></dd>
  75. <dt> <em>P3</em></dt>
  76. <dd><p><code>((nil,<var>k</var>),nil) <var>x</var></code> = <code><var>k</var></code>
  77. </p></dd>
  78. <dt> <em>P4</em></dt>
  79. <dd><p><code>(((nil,(nil,nil)),nil),nil) (<var>f</var>,<var>x</var>)</code> = <code><var>f</var> (<var>f</var>,<var>x</var>)</code>
  80. </p></dd>
  81. <dt> <em>P5</em></dt>
  82. <dd><p><code>((<var>f</var>,<var>g</var>),nil) <var>x</var></code> = <code><var>f</var> <var>g</var> <var>x</var></code>
  83. </p></dd>
  84. <dt> <em>P6</em></dt>
  85. <dd><p><code>((<var>f</var>,nil),<var>g</var>) <var>x</var></code> = <code>(<var>f</var> <var>x</var>,<var>g</var> <var>x</var>)</code>
  86. </p></dd>
  87. <dt> <em>P7</em></dt>
  88. <dd><p><code>((<var>p</var>,<var>f</var>),<var>g</var>) <var>x</var></code> = <code><var>f</var> <var>x</var></code> if
  89. <code><var>p</var> <var>x</var></code> is a non-<code>nil</code> tree,
  90. but <code><var>g</var> <var>x</var></code> if <code><var>p</var> <var>x</var></code> = <code>nil</code>
  91. </p></dd>
  92. </dl>
  93. <a name="index-properties"></a>
  94. <a name="index-operator-properties"></a>
  95. <p>Although other properties remain to be described, it is worth pausing at
  96. this point because there is ample food for thought in the ones already
  97. given. An obvious question would be that of their origin. The short
  98. answer is that they have been chosen arbitrarily to be true by
  99. definition of the operator. At best, the completion of the construction
  100. may lead to a more satisfactory answer based on aesthetic or engineering
  101. grounds.
  102. </p>
  103. <p>A more important question would be that of the relevance of the mystery
  104. operator and its properties to the stated purpose of this section, which
  105. is to specify the virtual machine code semantics. The answer lies in
  106. that the operator induces a function for any given tree <code><var>t</var></code>,
  107. such that the value returned by the function when given an argument
  108. <var>x</var> is <code><var>t</var> <var>x</var></code>. This function is the one that is
  109. implemented by the virtual code <var>t</var>, which is to say the way an
  110. application will behave if we put <var>t</var> in its virtual code file. An
  111. equivalent way of looking at the situation is that the virtual machine
  112. does nothing but compute the result of this operator, taking the tree in
  113. the virtual code file as its left operand and the input data as the
  114. right operand. By knowing what the operator will do with a given pair of
  115. operands, we know what to put into the virtual code file to get the
  116. function we want.
  117. </p>
  118. <a name="index-universality"></a>
  119. <a name="index-Turing-equivalence"></a>
  120. <a name="index-exceptions-1"></a>
  121. <a name="index-lists-4"></a>
  122. <p>It is worthwhile to note that properties <em>P0</em> to <em>P7</em> are
  123. sufficient for universality in the sense of Turing equivalence. That
  124. means that any computable function could be implemented by the suitable
  125. choice of a tree <var>t</var> without recourse to any other properties of the
  126. operator. A compiler writer who finds this material boring could
  127. therefore stop reading at this point and carry out the task of targeting
  128. any general purpose programming language to the virtual machine based on
  129. the specifications already given. However, such an implementation would
  130. not take advantage of the features for list processing, exception
  131. handling, or profiling that are also built into the virtual
  132. machine and have yet to be described.
  133. </p>
  134. <hr size="1">
  135. <table cellpadding="1" cellspacing="1" border="0">
  136. <tr><td valign="middle" align="left">[<a href="On-Equality.html#On-Equality" title="Previous section in reading order"> &lt; </a>]</td>
  137. <td valign="middle" align="left">[<a href="A-Simple-Lisp-Like-Language.html#A-Simple-Lisp-Like-Language" title="Next section in reading order"> &gt; </a>]</td>
  138. <td valign="middle" align="left"> &nbsp; </td>
  139. <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>
  140. <td valign="middle" align="left">[<a href="Virtual-Code-Semantics.html#Virtual-Code-Semantics" title="Up section"> Up </a>]</td>
  141. <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Next chapter"> &gt;&gt; </a>]</td>
  142. <td valign="middle" align="left"> &nbsp; </td>
  143. <td valign="middle" align="left"> &nbsp; </td>
  144. <td valign="middle" align="left"> &nbsp; </td>
  145. <td valign="middle" align="left"> &nbsp; </td>
  146. <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
  147. <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
  148. <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
  149. <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
  150. </tr></table>
  151. <p>
  152. <font size="-1">
  153. This document was generated on <i>November 8, 2012</i> using <a href="http://www.nongnu.org/texi2html/"><i>texi2html 1.82</i></a>.
  154. </font>
  155. <br>
  156. </p>
  157. </body>
  158. </html>