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 onlyT
while the queue is not empty do if the front element of the queue isnil
then print0
else if the front element of the queue is of the formcons(x,y)
then print1
appendx
to the back of the queue appendy
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)))