Publication details

Saarland University Computer Science

Linearisation, Minimisation and Transformation of Data Graphs with Transients

Guido Tack

Diploma thesis, Programming Systems Lab, Universität des Saarlandes, Saarbrücken, May 2003

This thesis introduces data graphs as a formal model for the objects in a programming system's memory, and describes three services on such data graphs: linearisation, minimisation, and transformation.
The SEAM system offers an abstract store that provides a programming language's implementor with a platform- and language-independent abstraction layer, hiding the complex issues of memory management. This thesis aims at giving a formal description of this store and of the services mentioned above.
Data graphs are presented here as a formal model for the objects that reside in such a store. Starting from this model, an abstract store can be described by an abstract data type (ADT) that implements data graphs as imperative objects.
The linearisation service (also known as pickling) translates a data graph into a linear, external, platform-independent representation (a pickle) from which a copy of the original graph can be reconstructed. Pickles can be written to files for persistence, or distributed over a network, implementing inter-process communication. Linearisation and delinearisation are described formally in terms of the data graph, and the SEAM implementation of pickling and unpickling is discussed.
Minimisation applies graph minimisation techniques to data graphs, yielding a store service that eliminates redundancy in the graph. The formal background as well as implementation issues of this service are presented, and its applicability to data graphs is evaluated.
Finally, the store is extended by transients, a mechanism essential for an efficient implementation of futures, logic variables and lazy evaluation. Transients are applied to both minimisation and linearisation; for the latter, they allow for the implementation of a powerful transformation mechanism that translates between an internal and an external representation of data graphs during pickling and unpickling.

Download PDF        Show BibTeX               

Login to edit

Webmaster, Wed Sep 16 10:47:00 2009