Generation of abstract programming interfaces from syntax definitions

Tree Manipulation; Using the ATerm-Library to represent tree-like data structures has become a popular activity, especially amongst developers of e.g. lexical scanners, parsers, rewrite engines and model checkers. Practical experience with the ATerm-Library in the ASF+SDF Meta-Environment has shown that the development and maintenance of tools that access ATerms using handcrafted code is involved and very error prone. Both the make and match paradigm and the direct manipulation of ATerms suffer from the fact that the programmer uses knowledge about the underlying structure (a.k.a. the signature) of the ATerm that represents the data type being accessed. Hard-wiring this knowledge in various tools makes it difficult to maintain the tools with respect to changes in the data structure. By lifting the data definition and its mapping to an ATerm representation away from the level of tool implementation, it becomes possible to generate a library of access functions on the data type, which can be used by all the tools that need access to it. The tools no longer directly manipulate the ATerm representation, but rather invoke methods described by the API of the library, thus abstracting from the fact that ATerms are used for the implementation of the data type. This paper describes how an API and its implementation can be generated from a syntax definition of the data type. In particular we describe how a grammar (in SDF) can be used to generate a library of access functions that manipulate the parse trees of terms over this syntax. Application of this technique in the ASF+SDF Meta-Environment has resulted in a spectacular elimination of 47 of the handwritten code, thus greatly improving both maintainability of the tools and their flexibility with respect to changes in the parse tree format