[ < ] | [ > ] |  | [ << ] | [ Up ] | [ >> ] |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

### 2.2.1 Bit String Encoding

The conversion from trees to bit strings might have been done in several 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.

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 none that takes advantage of this possibility, it is better to plan ahead than to be faced with backward compatibility problems later.

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 first-in first-out order. Intuitively, the algorithm works by traversing the tree in level order. To print a tree `T` as a string of `1`s and `0`s, it performs the following steps.

    Initialize the queue to contain only T
    while the queue is not empty do
       if the front element of the queue is nil then
          print 0
       else if the front element of the queue is of the form cons(x,y) then
          print 1
          append x to the back of the queue
          append y to the back of the queue
       end if
       remove the front element of the queue
    end while

This algorithm presupposes that any given tree `cons(x,y)` can be “deconstructed” to obtain `x` and `y`. The computability of such an operation is assured in theory by the uniqueness property of the `cons` 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.

As an example, running the following tree through the above algorithm results in the bit string `111111101011110010001001100010100010100100100`.

    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)))

[ < ] | [ > ] |  | [ << ] | [ Up ] | [ >> ] |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

This document was generated on November 8, 2012 using texi2html 1.82.