23.02.99: At the seminar Component-Based Programming under Different Paradigms in Dagstuhl, Germany, 21.02.--26.02.1999, I have presented the C++ program flatten.C. It makes use of partial template specialization, which is not implemented in every C++ compiler by now. It is known to run with Cygnus egcs-2.90.29 980515 (egcs-1.0.3 release).
At the previous day a generic function flatten was used as an example for polytypic programming in functional languages. It raised the question whether a similar program could be written using templates in C++. Besides that the meta-information for the self-inspection of user-defined types must be given explicitly, it can be written, see flatten.C.
The function flatten traverses a DAG (directed acyclic graph) depth-first from left to right and collect all items of type I in a list. The implementation given here is a template meta-program that creates a recursive traversal function for each type involved in the definition of the DAG data structure. The type annotation used for self-inspection of the types is encoded in the class template T<type,int>. Note that this program does not exactly solve the original problem, where flatten collected all items of type I in a parametric data structure parameterized with I as well. If int is chosen for I the functional programming flatten still collects only all occurences of I even if there are other int values in the DAG. The program flatten.C presented here will collect all int values. However, with another format for the meta-information it can be easily adapted to this case.
The output of this program is supposed to be "1 2 3 2 3\n1\n".
) 10.01.2000