PREPROCESSOR data structures

From: Vesa Karvonen (vesa.karvonen_at_[hidden])
Date: 2001-12-17 15:27:15

/* This message can be preprocessed! :) */

#include <boost/preprocessor.hpp>

/*
  I recently discovered a technique for representing "general
  purpose" recursive data structures such as lists and trees using
  the preprocessor.

  Consider the following list constructor macros:
*/

#define BOOST_PREPROCESSOR_LIST_NIL\
  (_,_,0)
#define BOOST_PREPROCESSOR_LIST_CONS(H,T)\
  (H,T,1)

/*
  The simple trick is that the last element of the tuple indicates
  whether the node is a NIL node or a CONS node. This kind of
  representation makes it possible to define algorithms for lists
  without having to know what kind of elements are stored in the
  list.
*/

/* A simple list would look like this: */

#define TEST_LIST\
  BOOST_PREPROCESSOR_LIST_CONS(1,\
  BOOST_PREPROCESSOR_LIST_CONS(2,\
  BOOST_PREPROCESSOR_LIST_CONS(3,\
  BOOST_PREPROCESSOR_LIST_CONS(4,\
  BOOST_PREPROCESSOR_LIST_CONS(5,\
  BOOST_PREPROCESSOR_LIST_NIL)))))

list: TEST_LIST

/* The following are the other elementary operations on lists: */

#define BOOST_PREPROCESSOR_LIST_IS_CONS(L)\
  BOOST_PREPROCESSOR_TUPLE_ELEM(3,2,L)
#define BOOST_PREPROCESSOR_LIST_IS_NIL(L)\
  BOOST_PREPROCESSOR_NOT(BOOST_PREPROCESSOR_TUPLE_ELEM(3,2,L))
#define BOOST_PREPROCESSOR_LIST_HEAD(L)\
  BOOST_PREPROCESSOR_TUPLE_ELEM(3,0,L)
#define BOOST_PREPROCESSOR_LIST_TAIL(L)\
  BOOST_PREPROCESSOR_TUPLE_ELEM(3,1,L)

/* The following macros can be used to compute the length of a list: */

#define BOOST_PREPROCESSOR_LIST_SIZE(L)\
  BOOST_PREPROCESSOR_LIST_SIZE_I(0,L)
#define BOOST_PREPROCESSOR_LIST_SIZE_I(I,L)\
  BOOST_PREPROCESSOR_TUPLE_ELEM\
  ( 2\
  , 0\
  , BOOST_PREPROCESSOR_WHILE##I\
    ( BOOST_PREPROCESSOR_LIST_SIZE_C\
    , BOOST_PREPROCESSOR_LIST_SIZE_F\
    , (0,L)\
    )\
  )
#define BOOST_PREPROCESSOR_LIST_SIZE_C(I,X)\
  BOOST_PREPROCESSOR_LIST_IS_CONS(BOOST_PREPROCESSOR_TUPLE_ELEM(2,1,X))
#define BOOST_PREPROCESSOR_LIST_SIZE_F(I,X)\
  ( BOOST_PREPROCESSOR_INC(BOOST_PREPROCESSOR_TUPLE_ELEM(2,0,X))\
  , BOOST_PREPROCESSOR_LIST_TAIL(BOOST_PREPROCESSOR_TUPLE_ELEM(2,1,X))\
  )

/* For example: */

size: BOOST_PREPROCESSOR_LIST_SIZE(TEST_LIST)

/* The following implements a well known higher order function: */

#define BOOST_PREPROCESSOR_LIST_FOLD_LEFT_I(I,F,R,L)\
  BOOST_PREPROCESSOR_TUPLE_ELEM\
  ( 3\
  , 1\
  , BOOST_PREPROCESSOR_WHILE##I\
    ( BOOST_PREPROCESSOR_LIST_FOLD_LEFT_C\
    , BOOST_PREPROCESSOR_LIST_FOLD_LEFT_F\
    , (F,R,L)\
    )\
  )
#define BOOST_PREPROCESSOR_LIST_FOLD_LEFT_C(I,X)\
  BOOST_PREPROCESSOR_LIST_IS_CONS(BOOST_PREPROCESSOR_TUPLE_ELEM(3,2,X))
#define BOOST_PREPROCESSOR_LIST_FOLD_LEFT_F(I,X)\
  ( BOOST_PREPROCESSOR_TUPLE_ELEM(3,0,X)\
  , BOOST_PREPROCESSOR_TUPLE_ELEM(3,0,X)\
    ( BOOST_PREPROCESSOR_INC(I)\
    , BOOST_PREPROCESSOR_TUPLE_ELEM(3,1,X)\
    , BOOST_PREPROCESSOR_LIST_HEAD(BOOST_PREPROCESSOR_TUPLE_ELEM(3,2,X)))\
    , BOOST_PREPROCESSOR_LIST_TAIL(BOOST_PREPROCESSOR_TUPLE_ELEM(3,2,X))\
  )

/* And here is an example of how to use it: */

fold:
BOOST_PREPROCESSOR_LIST_FOLD_LEFT_I(0,BOOST_PREPROCESSOR_SUB_I,20,TEST_LIST)

/*
  The following is list reversal implemented using the previously
  defined higher order function:
*/

#define BOOST_PREPROCESSOR_LIST_REV_I(I,L)\
  BOOST_PREPROCESSOR_LIST_FOLD_LEFT_I\
  ( I\
  , BOOST_PREPROCESSOR_LIST_REV_F\
  , BOOST_PREPROCESSOR_LIST_NIL\
  , L\
  )
#define BOOST_PREPROCESSOR_LIST_REV_F(I,R,H)\
  BOOST_PREPROCESSOR_LIST_CONS(H,R)

/* For example: */

rev: BOOST_PREPROCESSOR_LIST_REV_I(0,TEST_LIST)

/* Finally, here is another well known higher order function: */

#define BOOST_PREPROCESSOR_LIST_MAP_I(I,F,S,L)\
  BOOST_PREPROCESSOR_LIST_REV_I\
  ( I\
  , BOOST_PREPROCESSOR_TUPLE_ELEM\
    ( 3\
    , 2\
    , BOOST_PREPROCESSOR_LIST_FOLD_LEFT_I\
      ( I\
      , BOOST_PREPROCESSOR_LIST_MAP_F\
      , (F,S,BOOST_PREPROCESSOR_LIST_NIL)\
      , L\
      )\
    )\
  )
#define BOOST_PREPROCESSOR_LIST_MAP_F(I,R,H)\
  ( BOOST_PREPROCESSOR_TUPLE_ELEM(3,0,R)\
  , BOOST_PREPROCESSOR_TUPLE_ELEM(3,1,R)\
  , BOOST_PREPROCESSOR_LIST_CONS\
    ( BOOST_PREPROCESSOR_TUPLE_ELEM(3,0,R)\
      ( I\
      , BOOST_PREPROCESSOR_TUPLE_ELEM(3,1,R)\
      , H\
      )\
    , BOOST_PREPROCESSOR_TUPLE_ELEM(3,2,R))\
  )

/* And an example: */

#define BOOST_PREPROCESSOR_INC_I(I,_,X) BOOST_PREPROCESSOR_INC(X)
map: BOOST_PREPROCESSOR_LIST_MAP_I(0,BOOST_PREPROCESSOR_INC_I,_,TEST_LIST)

/*
  The question is: Should this functionality be added to
  the preprocessor library?

  Personally, I have no idea of how useful this stuff would be.
  I'd like to know if anyone has ideas on how to use the
  functionality or is otherwise interested.
*/