ATerm
An ATerm (Annotated Term) is both an abstract data type designed for the representation and manipulation of tree-like data structures and a set of formats for exchanging this data between distributed applications.
An ATerm can be:
an integer literal, such as 1 and -28;
a real literal, such as 1.414 and 1E+10;
a string literal, such as "x" and "Hello World!";
a list of zero or more ATerms, such as [1, 0.2, "a"] and [ ];
or a function application, such as Plus(Var("x"),Int(1)), and True;
and optionally followed by one or more annotations ATerms, such as, Mult(1,4){Type(Int)}, or Sym("x"){Line(14),Col(5)}.
An ATerm is immutable once created, and is in general represented internally as a Direct Acyclic Graph (DAG), which saves both space and time by avoiding unnecessary duplications. The primary implementation of the ATerm library is in the C language, but there are implementations of the library in the Java and Haskell languages also. ATerm library was adapted to into the Python language.
For more information see:
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.