Creating recursive types (typelist etc.)

From: Hamish Mackenzie (boost_at_[hidden])
Date: 2001-11-27 16:53:56

Just thought I would try to write a summary of the issues involved with
the different approaches.  I am not going to get into the details of
what recursive types we should create as it looks like that is going to
be a very complicated question. Instead I want to concentrate on how
they can be created.

----------------  How To Create a Recursive Type  ----------------

1) Write it out in full
t< a, t< b, t< c, tail > > >
You can see how this format quickly becomes awkward and unreadable.

2) Macros
#define RECURSIVE_3_T( Traits, Item0, Item1, Item2, Tail ) \
  Traits::node< Item0, \
  Traits::node< Item1, \
  Traits::node< Item2, Tail > > >
#define RECURSIVE_3( Traits, Item0, Item1, Item2 ) \
  RECURSIVE_3_T( Traits, Item0, Item1, Item2, Traits::nil )

Macros cannot have a variable number of arguments this means
* The number of arguments must be hashed into the name of the macro.
* There must be a fixed limit to the number of arguments (although we
can nest the macros to get around this limit)
Macros do not obey namespace rules and as such can result in problems.

3) make_recursive_type< a, b, c >::result
Defining a class with a large number of default arguments be used to
construct the appropriate recursive result.
Like the macros this has the drawback that there must be an upper limit
on the number of items.  This can be over come using an append template.

The drawback is that it cannot be used in specialization.
template< class RecursiveType > class foo;
template<> class foo< make_recursive_type< a, b, c >::result > {}

4) type< a, b, c >
By dispensing with the recursive type (at least in the interface) and
using a type with a large number of default arguments we avoid the
specialization problem. This limits the number of items and
unfortunately now it is further complicated by the fact that....

append< type< a, b >, type< c > >::result
should be the same type as type< a, b, c >

But what is append< X, Y >::result if it has more items than the maximum
number of arguments for type?

If this does not fail it will have to return some other type. This would
be possible but complicated. The following steps would have to take
place:

a. Convert to a recursive type
b. Perform operation
c. Convert back if possible
(this is more complicated than it might sound)

After all that users would have to create there algorithms (for use in
step b) in terms of the recursive type so they would still have to write
things out the long way during specialization.

What have I missed?

--------------------  How we could patch C++ --------------------

My preference now is for macros with expectation that they would be
replaced with a suitable extension to the C++ language at some point in
the future. At that time existing code would not need to be updated just
the macros would change.

The macros would be of the form RECURSIVE_NN( Traits, ... ) and
RECURSIVE_NN_T( Traits, ..., Tail ) where NN is the number of arguments
represented by ...

Traits::node must be a template class taking two parameters.  The first
parameter would be the head item. The second would be the tail and must
be a class or typename template argument.

Traits::nil must be a class or typedef representing the empty type.

Tail must be a recursive type also based on Traits.

The _NN version will create a recursive type with NN components.

The _NN_T will create a similar type but with Tail added to the end.

Example #defines
In the case where NN = 0 the macros will be as follows
#define RECURSIVE_0( Traits ) Traits::nil
#define RECURSIVE_0_T( Traits, Tail ) Tail

In the case where NN = 3 
#define RECURSIVE_3_T( Traits, Item0, Item1, Item2, Tail ) \
  Traits::node< Item0, \
  Traits::node< Item1, \
  Traits::node< Item2, Tail > > >
#define RECURSIVE_3( Traits, Item0, Item1, Item2 ) \
  RECURSIVE_3_T( Traits, Item0, Item1, Item2, Traits::nil )

Is this a daft idea?
Could it be worked into existing code?
Would it help if submitted a header file?

--------------------  How we could fix C++  --------------------

Finally here is a possible extension to the language would be to make a
reserved word say boost::recursive behave almost exactly like the
macros.

RECURSIVE_NN( Traits, ... ) becomes
  boost::recursive< Traits, ... >
RECURSIVE_NN_T( Traits, ..., Tail ) becomes
  boost::recursive< Traits, ... | Tail >

So...
BOOST_STATIC_ASSERT( is_same<
  boost::recursive< Traits, a, b, c >,
  RECURSIVE_3( Traits, a, b, c ) >::value )

BOOST_STATIC_ASSERT( is_same<
  boost::recursive< Traits, a, b, c | Tail >,
  RECURSIVE_3_T( Traits, a, b, c, Tail ) >::value )

Where Traits and Tail are as described in the previous section

Is this idea even more daft?

Hamish