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.