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 1s and 0s, 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)))

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