Bit-String-Encoding.html 7.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154
  1. <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html401/loose.dtd">
  2. <html>
  3. <!-- Created on December 10, 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.2.1 Bit String Encoding</title>
  14. <meta name="description" content="avram - a virtual machine code interpreter: 2.2.1 Bit String Encoding">
  15. <meta name="keywords" content="avram - a virtual machine code interpreter: 2.2.1 Bit String Encoding">
  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="Bit-String-Encoding"></a>
  40. <table cellpadding="1" cellspacing="1" border="0">
  41. <tr><td valign="middle" align="left">[<a href="Concrete-Syntax.html#Concrete-Syntax" title="Previous section in reading order"> &lt; </a>]</td>
  42. <td valign="middle" align="left">[<a href="Blocking.html#Blocking" 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="Concrete-Syntax.html#Concrete-Syntax" 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="Bit-String-Encoding-1"></a>
  58. <h3 class="subsection">2.2.1 Bit String Encoding</h3>
  59. <p>The conversion from trees to bit strings might have been done in several
  60. <a name="index-trees-1"></a>
  61. ways, perhaps the most obvious being based on a preorder traversal with
  62. each vertex printed as it is traversed. By this method, the entire
  63. encoding of the left descendent would precede that of the right in the
  64. bit string. This alternative is therefore rejected because it imposes
  65. unnecessary serialization on communication.
  66. </p>
  67. <p>It is preferable for the encodings of both descendents of a tree to be
  68. interleaved to allow concurrent transmission. Although there is
  69. presently no distributed implementation of the virtual machine and hence
  70. <a name="index-distributed-implementation"></a>
  71. none that takes advantage of this possibility, it is better to plan
  72. ahead than to be faced with backward compatibility problems later.
  73. </p>
  74. <p>The preferred algorithm for encoding a tree as a bit string employs a
  75. queue. The queue contains trees and allows them to be processed in a
  76. <a name="index-queues"></a>
  77. first-in first-out order. Intuitively, the algorithm works by traversing
  78. <a name="index-printing-algorithm"></a>
  79. the tree in level order. To print a tree <code>T</code> as a string of
  80. <code>1</code>s and <code>0</code>s, it performs the following steps.
  81. </p><table><tr><td>&nbsp;</td><td><pre class="display">
  82. Initialize the queue to contain only <code>T</code>
  83. while the queue is not empty do
  84. if the front element of the queue is <code>nil</code> then
  85. print <code>0</code>
  86. else if the front element of the queue is of the form <code>cons(x,y)</code> then
  87. print <code>1</code>
  88. append <code>x</code> to the back of the queue
  89. append <code>y</code> to the back of the queue
  90. end if
  91. remove the front element of the queue
  92. end while
  93. </pre></td></tr></table>
  94. <p>This algorithm presupposes that any given tree
  95. <a name="index-deconstruction"></a>
  96. <code>cons(x,y)</code> can be &ldquo;deconstructed&rdquo; to obtain <code>x</code> and
  97. <code>y</code>. The computability of such an operation is assured in theory by
  98. the uniqueness property of the <code>cons</code> operator, regardless of the
  99. representation chosen. If the trees are implemented with pointers in the
  100. obvious way, their deconstruction is a trivial constant time operation.
  101. </p>
  102. <p>As an example, running the following tree through the above algorithm
  103. results in the bit string <code>111111101011110010001001100010100010100100100</code>.
  104. </p>
  105. <table><tr><td>&nbsp;</td><td><pre class="example">
  106. cons(
  107. cons(
  108. cons(nil,cons(nil,cons(nil,nil))),
  109. cons(nil,cons(nil,nil))),
  110. cons(
  111. cons(
  112. cons(nil,cons(nil,cons(nil,cons(nil,nil)))),
  113. cons(nil,nil)),
  114. cons(
  115. cons(
  116. cons(nil,cons(nil,cons(cons(nil,cons(nil,nil)),nil))),
  117. cons(nil,nil)),
  118. nil)))
  119. </pre></td></tr></table>
  120. <hr size="1">
  121. <table cellpadding="1" cellspacing="1" border="0">
  122. <tr><td valign="middle" align="left">[<a href="Concrete-Syntax.html#Concrete-Syntax" title="Previous section in reading order"> &lt; </a>]</td>
  123. <td valign="middle" align="left">[<a href="Blocking.html#Blocking" title="Next section in reading order"> &gt; </a>]</td>
  124. <td valign="middle" align="left"> &nbsp; </td>
  125. <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>
  126. <td valign="middle" align="left">[<a href="Concrete-Syntax.html#Concrete-Syntax" title="Up section"> Up </a>]</td>
  127. <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Next chapter"> &gt;&gt; </a>]</td>
  128. <td valign="middle" align="left"> &nbsp; </td>
  129. <td valign="middle" align="left"> &nbsp; </td>
  130. <td valign="middle" align="left"> &nbsp; </td>
  131. <td valign="middle" align="left"> &nbsp; </td>
  132. <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
  133. <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
  134. <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
  135. <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
  136. </tr></table>
  137. <p>
  138. <font size="-1">
  139. This document was generated on <i>December 10, 2012</i> using <a href="http://www.nongnu.org/texi2html/"><i>texi2html 1.82</i></a>.
  140. </font>
  141. <br>
  142. </p>
  143. </body>
  144. </html>