Naive transformations

Let us begin with the naive way of translating the following example:

let f a b = a + b

The simplest way of converting the function f is showed in the C++ code below.

template<int a, int b>
struct f
{
  enum { res = a + b };
};

Let us now consider the following MetaGene lines :

let g = f 1

template <int b>
struct g : public f <1, b>
{};

Translating this code would lead us to complex processing : specializing f is not an easy task since it is not homogeneous. Moreover this transformation is not context-free: it depends on the complete type of f.

Compare with

let f a b c = a + b + c
let g = f 1

which would be translated to

template <int b, int c>
struct g : public f <1, b, c>
{};

ECHEC !

Functional model

CAML functions

The CAML language offers n-ary functions. Following the lambda calculus model, an n-ary function is in fact interpreted as n unary functions.

For example,

let f a b c = a + b +c

let f = function a -> (function b -> (function c = a + b +c))

We can easily guess that the kind of problems we had before are related to the fact that we were not as near as necessary of this formalism. Let's try to get closer to it.

Metagene functions as C++ nested template structs

Our beloved MetaGene function can also be translated as nested C++ template structs.

let f a b = a + b
let g = f 1

template <int a>
struct f {
  template <int b>
  struct res {
    enum { res = a + b };
  };
};

G can then systematically be expressed in a more satisfactory way.

template<int b>
struct g : public f <1>::res<b>
{};

This construct depends less on the context. Now, the definition of g still works with the a ternary function f :

let f a b c = a + b + c

This is nice, since we now manipulate unary functions only, and res can be fetched at any nesting level :

let f2 = f 1
let f3 = f 1 2
let f4 = f 1 2 3

f2 is represented by f<1>::res
f3 is represented by f<1>::res<2>
f3 is represented by f<1>::res<2>::res<3>

Limitations

This translating scheme is very nice but ....

... the resulting code does not compile !!

Our pleasant standard compliant C++ compiler says : declaration of a member with the same name as its class. (see MetaGeneHorrorShow for more details and a possible but ugly workaround)

Moreover, MetaGene does not aim at being restricted to integer types. For example, list types should be in the language. According to our previous design attempts, this could be a problem :

val f  : 'a list -> 'a list
val g : int -> int

We can expect that the translation of those function could look like :

template < typename L >
struct f {
[...]
typedef [ ... ] res;
[...]
};

template < int a >
struct f {
[...]
enum { [ ... ] } res;
[...]
};

This forbids a systematic generation process: we have to know the data types in order to choose the good C++ implementation.

Ca rate !!

Boxes

A basic box

The problem stated just before can be solved by static encapsulation of types :

template <int i>
struct Int
{
  enum { value = i };
};

This way,

let f a b = a + b
in f 50 1

becomes :

template <typename a>
struct f
{
  template <typename b>
  struct res {
  typedef Int < (a :: value + b :: value) > res;
  }; 
};

This way, we can manipulate all integral types equally. This can be pushed further, by encapsulating functions too.

Think about a bogus mapping function :

let dummy_map f x = f x

Back in C++, we can have

template <template <typename> typename f>
struct dummy_map
{
  template <typename x>
  struct res
  {
    typedef f<x>::res res;
  }
};

but we would prefer :

template <typename f>
struct dummy_map
{
  [...]
};

This is made possible by the Fun box concept.

The Fun box

We generalize the trick used for Int to functions by encapsulating them in a Fun struct.

template <template <typename> typename f>
struct Fun
{
  template <class x>
  struct value : public f<x>
  {};
};

This way, dummy_map can now be translated as follows:

Function implementation:

template <typename f>
struct dummy_map_ 
{
  template <typename x>
  struct res_ // (dummy_map f) implementation
  {
    typedef f::value<x>::res res;
  };
  typedef Fun <res_> res // (dummy_map f) as value
};

Function as value: a c++ concrete type.

typedef Fun <dummy_map_> dummy_map; 

The Fun struct allows us to typedef our template structs (ie: to manipulate functions as variables of our meta language). Thus we treat functions and variables in a uniform fashion, exactly as in the functional model.

Limitations

In the implementation of a recursive function, we need to access to its function as value. Resolving these dependencies can be done via predeclaring our templates. This quickly becomes very verbose.

Final paradigm

Implicit Fun box

Fortunately, the previous code can easily be simplified. Let us imagine that we use a Fun box without saying it explicitly.

struct dummy_map {         // (dummy_map) as value
  template <typename f>
  struct value {           // (dummy_map) implementation
    struct res {           // (dummy_map f) as value
      template<typename x>
      struct value {       // (dummy_map f) implementation
        typedef f::value<x>::res res; 
      };
    };
  };
};

This code is used exactly the same way as the previous one. But this new way of generating is much cleaner. Moreover it allows simple recursive functions without any predeclaration. This is not the case of mutual recursive functions, which cannot be generated without heavy predeclaration code.

A full example

let compose a b x = a (b x) 
and afunc = compose (( + ) 1) (( * ) 2)
in afunc 25

is translated as:

struct temp1 {
  struct compose {
    template<typename a>
    struct value {
      struct res {
        template<typename b>
        struct value {
          struct res {
            template<typename x>
            struct value {
              typedef a::value< b::value< x >::res >::res       res;
            };
          };
        };
      };
    };
  };
  typedef compose::value< mtg::plus::value< mtg::Int <1> >::res>::
          res::value< mtg::times::value< mtg::Int <2> >::res>
          ::res    afunc;
  typedef afunc::value< mtg::Int <25> >::res    res;
};
typedef temp1::res res;

And now?

Thanks to our generation paradigm we are able to translate Metagene functionnal core: variables, functions (that can be recursive) and application (partial and total). We did neither talk about variant types nor about pattern matching. Moreover we need to integrate C++ concepts into this functionnal core: C++ types and C++ code seen as values. See Metagene translation process for a listing of how we solved these problems.

-- FrancisMaes^?, NicolasTisserand^? - 19 Nov 2003

MetaGeneZone

• Metagene, Metagene main page.
• Introduction, An introduction to the Metagene project.
• History: preliminary examples, Some examples showing the equivalence between C++ meta-programming and functionnal programming.
• History: generation paradigm, The generation paradigm and its history.
• Metagene translation process, From functionnal expressions to class templates.
• Related work, Some related work.
• Download Metagene, Download the latest release of Metagene.
• Paper and Slides, A paper introduicing the Metagene project with corresponding slides.
• Possible extensions, Possible extensions to Metagene.
• Horror Show, The museum of C++ horrors.