Duncan C. White, d.white@imperial.ac.uk
7th September 2018

datadec - ANSI C Inductive (or Recursive) Data Type Generator

Datadec takes inductive data types modelled on those found in functional languages (Hope, Miranda, Haskell etc) and generates ANSI C code to implement them.

An Example of Datadec in Action

To give you a feel for what datadec can do, you could write: 

intlist = nil
        | cons( int first, intlist next )
        ;

illist  = nil
        | cons( intlist first, illist next )
        ;

idtree  = leaf( string id, illist l )
        | node( idtree left, idtree right )
        ;

What does this mean? The first rule declares that an intlist can take two basic "shapes" - it is either empty, nil, or of the form cons(int,intlist). nil and cons() are called constructors, and define different "shapes" that objects of the type can take. However, because the second argument of a cons() constructor is itself an intlist, this type is said to be recursively defined. Functional programmers will recognise nil or cons() as the standard way of defining a list, so more intuitively, intlist is simply a list of integers!

Reading on, an illist is declared as a list of intlists, and an idtree is declared as a binary tree where each leaf node contains a (string, illist) pair.

Given this input, datadec can automatically construct an ANSI C module which implements all the data types, a constructor function for each constructor, deconstructor functions to help you to take objects apart again and printing functions to help you with debugging.

New feature in 1.3: -m mode

New in 1.3 (Summer 2018) - I've added a new metadata mode (the -m flag) which displays a standardised form of the types, constructors, and parameter types contained in a Datadec input file, to enable an ecosystem of support tools around Datadec to grow up. The first such support tool (not included in Datadec 1.3) is a C+Pattern Matching to C translator called CPM, which gives an experimental client-side Pattern Matching syntax for clients of datadec. See my https://www.doc.ic.ac.uk/~dcw/PSD/article11/ for a description of the development of CPM - you can download the final version of CPM from there as well.

In addition, I took the opportunity to fully convert Datadec to use stdbool.h internally, which is long overdue.

New feature in 1.2: free_TYPE() functions

New in 1.2 (Summer 2014) - experimental free functions (run datadec with new -f option to generate them). Read the man page carefully, there are still issues with shared pointers (as there often are in C). You can mark individual parameters in shapes as "-" - do not attempt to free this parameter.

Building and Packaging datadec

See the INSTALL file for building and packaging instructions. Hope you enjoy datadec.