Efficient annotated terms
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.
|Programming Environments (acm D.2.6), DATA STRUCTURES (acm E.1), DATA STORAGE REPRESENTATIONS (acm E.2), CODING AND INFORMATION THEORY (acm E.4)|
|Software (theme 1)|
|Organisation||Software Analysis and Transformation|
van den Brand, M.G.J, de Jong, H.A, Klint, P, & Olivier, P.A. (2000). Efficient annotated terms. CWI.