txlyre
/
avram


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154
							<!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.2.1 Bit String Encoding</title>

<meta name="description" content="avram - a virtual machine code interpreter: 2.2.1 Bit String Encoding">
<meta name="keywords" content="avram - a virtual machine code interpreter: 2.2.1 Bit String Encoding">
<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="Bit-String-Encoding"></a>
<table cellpadding="1" cellspacing="1" border="0">
<tr><td valign="middle" align="left">[<a href="Concrete-Syntax.html#Concrete-Syntax" title="Previous section in reading order"> &lt; </a>]</td>
<td valign="middle" align="left">[<a href="Blocking.html#Blocking" title="Next section in reading order"> &gt; </a>]</td>
<td valign="middle" align="left"> &nbsp; </td>
<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>
<td valign="middle" align="left">[<a href="Concrete-Syntax.html#Concrete-Syntax" title="Up section"> Up </a>]</td>
<td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Next chapter"> &gt;&gt; </a>]</td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </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="Bit-String-Encoding-1"></a>
<h3 class="subsection">2.2.1 Bit String Encoding</h3>

<p>The conversion from trees to bit strings might have been done in several
<a name="index-trees-1"></a>
ways, perhaps the most obvious being based on a preorder traversal with
each vertex printed as it is traversed.  By this method, the entire
encoding of the left descendent would precede that of the right in the
bit string. This alternative is therefore rejected because it imposes
unnecessary serialization on communication.
</p>
<p>It is preferable for the encodings of both descendents of a tree to be
interleaved to allow concurrent transmission. Although there is
presently no distributed implementation of the virtual machine and hence
<a name="index-distributed-implementation"></a>
none that takes advantage of this possibility, it is better to plan
ahead than to be faced with backward compatibility problems later.
</p>
<p>The preferred algorithm for encoding a tree as a bit string employs a
queue. The queue contains trees and allows them to be processed in a
<a name="index-queues"></a>
first-in first-out order. Intuitively, the algorithm works by traversing
<a name="index-printing-algorithm"></a>
the tree in level order. To print a tree <code>T</code> as a string of
<code>1</code>s and <code>0</code>s, it performs the following steps.
</p><table><tr><td>&nbsp;</td><td><pre class="display">
Initialize the queue to contain only <code>T</code>
while the queue is not empty do
   if the front element of the queue is <code>nil</code> then
      print <code>0</code>
   else if the front element of the queue is of the form <code>cons(x,y)</code> then
      print <code>1</code>
      append <code>x</code> to the back of the queue
      append <code>y</code> to the back of the queue
   end if
   remove the front element of the queue
end while

</pre></td></tr></table>

<p>This algorithm presupposes that any given tree
<a name="index-deconstruction"></a>
<code>cons(x,y)</code> can be &ldquo;deconstructed&rdquo; to obtain <code>x</code> and
<code>y</code>. The computability of such an operation is assured in theory by
the uniqueness property of the <code>cons</code> operator, regardless of the
representation chosen. If the trees are implemented with pointers in the
obvious way, their deconstruction is a trivial constant time operation.
</p>
<p>As an example, running the following tree through the above algorithm
results in the bit string <code>111111101011110010001001100010100010100100100</code>.
</p>
<table><tr><td>&nbsp;</td><td><pre class="example">
cons(
   cons(
      cons(nil,cons(nil,cons(nil,nil))),
      cons(nil,cons(nil,nil))),
   cons(
      cons(
         cons(nil,cons(nil,cons(nil,cons(nil,nil)))),
         cons(nil,nil)),
      cons(
         cons(
            cons(nil,cons(nil,cons(cons(nil,cons(nil,nil)),nil))),
            cons(nil,nil)),
         nil)))
</pre></td></tr></table>

<hr size="1">
<table cellpadding="1" cellspacing="1" border="0">
<tr><td valign="middle" align="left">[<a href="Concrete-Syntax.html#Concrete-Syntax" title="Previous section in reading order"> &lt; </a>]</td>
<td valign="middle" align="left">[<a href="Blocking.html#Blocking" title="Next section in reading order"> &gt; </a>]</td>
<td valign="middle" align="left"> &nbsp; </td>
<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>
<td valign="middle" align="left">[<a href="Concrete-Syntax.html#Concrete-Syntax" title="Up section"> Up </a>]</td>
<td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Next chapter"> &gt;&gt; </a>]</td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </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>