Compression of Labeled Spine Trees.

Recent developments in the implementation of functional programming languages rely on a specific form of labeled tree to represent the call hierarchy of functions. Such trees, that we refer to as spine trees, or simply spines for short, possess a very regular structure that makes them suitable for high compression, i.e. a reduction in the space needed to represent them internally. The discovery of an efficient method of compression for spines would directly impact to the implementation of functional programming languages that rely on them. In this work, we set out to investigate the possibilities of compression of labeled spine trees. Since we hypothesize spines to occur anywhere within a larger, possibly unstructured labeled tree, their “shape” needs to be recognized by an algorithmic procedure. We start therefore by addressing the problem of spine detection, proposing asymptotically efficient methods, both in time and in space. We then progress to the problem of their storage, namely the way in which they can be stored within or apart the tree they were originally embedded in, and finally turn to the problem of their own compression. The study of spine compression is done by applying already established results from the subfield of information theory known as data compression. Rather than devise a new compression algorithm from scratch, we try to understand which, among the already available ones, is fit to our own interests. In studying the compression of spine trees, we try in particular to determine when a so-called logarithmic compression, namely a reduction of the size of the spine to the logarithm of its original size, can be achieved. We first introduce a theoretical criterion for classifying the adequacy of our solutions, and then progress incrementally to our findings, until we reach a solution that is very promising both in the capacity of achieving logarithmic compression and in the computational resources needed to obtain this storage reduction.