M. G. J. van den Brand, H. A. de Jong, P. Klint, and P. A. Olivier. Efficient Annotated Terms.
Software - Practice & Experience, 30:259-291, 2000.
Abstract
How do distributed applications exchange tree-like data structures?
We introduce the abstract data type of
Annotated Terms
(
ATerms) and discuss their design, implementation and
application. A comprehensive procedural interface enables
creation and manipulation of ATerms in C or Java.
The ATerm implementation is based on maximal subterm
sharing and automatic garbage collection.
A binary exchange format for the
concise representation of ATerms (sharing preserved) allows the
fast exchange of ATerms between applications. In a typical
application--parse trees which contain considerable redundant
information--less than 2
bytes are needed to represent
a node in memory,
and less than 2
bits are needed to represent it in binary format.
The implementation of ATerms scales up to the manipulation
of ATerms in the giga-byte range.
Available:
See also
CategoryPaper