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)
CWI
Software Analysis and Transformation

van den Brand, M.G.J, de Jong, H.A, Klint, P, & Olivier, P.A. (2000). Efficient annotated terms. CWI.