Adtpp: lightweight efficient safe polymorphic algebraic data types for C

Lee Naish, Peter Schachte and Aleck MacNally

Adtpp is an open-source tool that adds support for algebraic data types (ADTs) to the C programming language. ADTs allow more precise description of program types and more robust handling of data structures than is directly supported by C. ADT definitions and other declarations are put in a file that is preprocessed by adtpp to produce a C header (".h") file which can be included in C source files. The generated header file contains C type definitions, macros, and inline functions that support type-safe construction, deconstruction, and pattern matching of ADT values, while avoiding unsafe operations such as casts, and avoiding the risk of errors such as dereferencing NULL pointers and accessing inappropriate fields of unions. Values are represented efficiently, using techniques from the implementation of declarative languages. For many simple data types, the representation is identical to a direct implementation in C, with no loss of efficiency. For more complex types, the adtpp representation is more efficient than common C representations, while preserving type safety and convenience. As an example, we present a new variation of 234-trees which is very compact. Adtpp also supports parametric polymorphism such as defining a type "list of t", where t can be any ADT, and generic functions such as length. However, compared to typical declarative languages, polymorphic code is somewhat more verbose, due to our reliance on the limited type checking available in C.

A version of this paper with minor changes is to appear in Software Practice and Exerience.

Keywords: Algebraic data types, C language extension, generics, polymorphism, safety, static checking, open-source