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"> < </a>]</td>
- <td valign="middle" align="left">[<a href="Blocking.html#Blocking" 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="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"> >> </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="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> </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 “deconstructed” 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> </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"> < </a>]</td>
- <td valign="middle" align="left">[<a href="Blocking.html#Blocking" 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="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"> >> </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>
|