Roadmap

[Manu343726]

Here's the roadmap I have been discussing with @ericjavier for a true functional language for C++ metaprogramming:

1. Language Level
   • Algebraic datatypes
   • Typeclasses
   • Bindable/curryable first class metafunctions
2. Middleware level
   • Sequences, typelists
   • Simple functionality for sequence manipulation
3. Library level
   • High order algorithms
   • Port of Haskell prelude?

Let's discuss the "hows" here. Please for an in depth discussion of any of that points, open a new issue on the topic.

[ericjavier]

Let me mention some features I would like to see in the first issue you mention above:

About Typeclasses:

• Once created a type, it should be assignable to a class without modifying it. For example, in your post you place the fmap functionality inside the list type. Maybe we can exploit some C++ features (like template specialization) to accomplish a more liberal approach to this issue. This will allow us to insert already created types in different classes. Also I would like to have the possibility to create my own classes.

About curryable metafunctions:

• Should be representable as simple types (no template< template < class... > class > arguments). This allow to take functions inside desired classes too (see bellow). Also I would like the possibility to adapt already created templates to first class citizen metafunctions in an easy way, something like:

  using f = make_metafunction< std::is_same >; // note that f is not an instance of the functor class ... using f2 = f::ret< int >; // ... note that f2 should be an instance of the functor class.

• Currying. A metafunction (I am going to use a general syntax) F(a, b, c) can perform as F(a)(b)(c), that is, its 'type' is like F:A->B->C so F(a) gives a function that take 2 arguments and so on... Also should be possible to call F with all the arguments at the same time (F(a,b,c)). I propose here to use my ideas from yaml.
• Client friendly syntax. I chose the syntax 'my_function::ret< A, B >' because it looks like a normal funtion application 'my_function(A,B)', that is, 'my_function::ret< A, B > ~ my_function(A,B)'. But I recognize that a great debate should be here.
• True composition. There must be an operation called 'composition' (Comp) that given two metafunction f:a->b, g:b->c, Comp(g,f) gets a first class citizen metafunction h:a->c with the required semantics, being Comp a first class citizen metafunction it self. At this point I got stuck in yaml, because I wanted to condense 2 curryed metafuncions, with 2 different currying states into only one representation, I think that this is not a trivial class and a deep formalization is needed.

[Manu343726]

• Maybe it's still too early to be talking about typeclasses. I'm agree with the fact that the metatype system should be plugeable in a way existing/external features can be added to the system instead of writting everything from scratch. The "intrusive" approach proposed on the post was only an exploration I was doing on the topic, maybe we should think about other alternatives. But note I prefer to not rely on specialization since it pollutes the code a lot. Maybe internal specialization, like what I described with metafunction classes.

• I'm agree, if (meta)functions will be first class citizens then we should avoid templates in favor of metafunction classes I think. Of course we can write a simple adaptor to deal with templates:

  template<template<typename...> class F>
  struct function_from_template
  {
      template<typename... Args>
      struct apply
      {
          using type = $(F, Args...);
      };
  };

• I'm still thinking on the best way to handle this. It's a killer feature, but your implementation is too complex I think. What about closures?

  struct f
  {
    template<typename... Head>
    struct apply
    {
        struct type
        {
            template<typename... Tail>
            using apply = f::apply<Head...,Tail...>;
        };
    };
  
    template<typename A, typename B, typename C>
    struct apply<A, B, C>
    {
        using type = C;
    };
  };
  
  using a = $(f, int); // a is a closure
  using b = $(a, char); // b is a closure
  using c = $(b, bool); // calling b we pass the third param so the non-closure matches, 
                      // so c is bool

• Note the $() alias I did for tml::eval. Still debatable...
• Completely agree. There should be a global metafunction to apply composition.

[Manu343726]

Today I also have been working on a prototype for algebraic datatypes. Look at main.cpp . Note that there are type traits to do pattern matching on those datatypes, seem to work quite well.

[Manu343726]

About composition, I forgot I introduced a very questionable specialization on tml::eval to handle function composition using pointer to function syntax:

using result = $(f(*)g);

[ericjavier]

Some thoughts.

I believe that when an user will create a function should not be thinking and worrying about many conventions established by our library. He should just take into account creating a template with a defined type that has the name 'type'.

For example, should not be writing:

struct f
{
    template<typename... Head>
    struct apply
    {
        struct type
        {
            template<typename... Tail>
            using apply = f::apply<Head...,Tail...>;
        };
    };

    template<typename A, typename B, typename C>
    struct apply<A, B, C>
    {
        using type = C;
    };
};

should only write something like:

template<typename A, typename B, typename C> struct f {
  using type = C;
};

and then trust that the type:

using my_func = function_from_template<f>;

is already a first-class citizen with all requirements of the library.

I think the meta-function to compose other functions should be called 'compose' or 'composition', no fancy notation, kept as simple and understandable as possible, or at least have several options.

A question: Are you aware of the work of Abel Sinkovics (@sabel83) ?

I'm still not quite sure how your eval works for delayed evaluations, I think (by the way, which branch should I use with Turbo ?), but let me ask another question:

When you do:

using a = $(f, int); // a is a closure
using b = $(a, char); // b is a closure

you can still pass them as parameters to other functions, in short: Are 'x' and 'y' first-class citizens functions in the library ?

[Manu343726]

I believe that when an user will create a function should not be thinking and worrying about many conventions established by our library. He should just take into account creating a template with a defined type that has the name 'type'.

That's right, there should be a way to provide all that features out of the box as adapters for classic metafunctions. I have played both with eager metafunctions (like what Eric Niebler's Meta does) and lazy ones (i.e. metafunction classes), and I think that the library should use lazy evaluation by default. Also metafunction classes are easier to play with since they are directly first-class citizens (types) instead of templates. Thankfully writing an adapter to translate metafunctions into metafunction classes is easy:

template<template<typename...> class F>
struct from_metafunction
{
    template<typename... Args>
    struct apply
    {
        using type = $(F<Args...>);
    };
};

One of the problems I'm facing with the adapter approach is: How to handle currying on variadic metafunctions? We can use SFINAE to check if a given instantiation is valid and has a ::type member and then evaluate the metafunction, else returning the closure to continue with currying. But it's possible to check if a template is a variadic template and then disable currying?

I have been playing a bit on the topic: http://coliru.stacked-crooked.com/a/52719bb784a98b13 GCC rejects the code, the second static_assert() fails, meaning it considers a template<typename, typename, typename> to be instantiable with just one int param only. http://coliru.stacked-crooked.com/a/b5abd3d81341e8e2

If this thing finally works is the right way to go I think. Note that curry adapter also raises templates into metafunction classes, solving both problems with one adapter only.

A question: Are you aware of the work of Abel Sinkovics (@sabel83)

Yes, I'm. It's a cool project with almost the same goals as ours, but I find the macro based interface a bit tricky.

I'm still not quite sure how your eval works for delayed evaluations, I think (by the way, which branch should I use with Turbo ?)

eval is just a thing that "parses" expressions (templates) expanding its arguments first prior to evaluation. That was intended for easy metafunction composition riding over the typename ::type pattern. But it evolved a lot from that, and now it's really an evaluation trigger for any expression (Value, metafunction, metafunction class, type ctor, etc) the library can deal with. For lazyness it does not do anything special, if you need lazy computations use metafunction classes instead of metafunctions.

About the branch, I'm sorry I usually experiment directly in the master branch. All other branches are currently outdated, maybe we should clean up the repo and start a git flow workflow or something like that.

... you can still pass them as parameters to other functions, in short: Are 'x' and 'y' first-class citizens functions in the library ?

x y?

[ldionne]

Looking at this discussion going on, I think you might be interested in my previous work on the MPL11. It's basically a port of the Haskell prelude to TMP. Also, it uses lazy evaluation and it has proper type classes. So far, I fail to see how what you are trying to achieve is different, but I might be being thick.

[Manu343726]

I fail to see how what you are trying to achieve is different, but I might be being thick.

@ldionne maybe that's because we are trying to achieve almost the same thing? ;) What I'm trying here is to compile (no pun intended...) all my ideas about tmp and see how the final result looks like. MPL11 is certainly very similar to our goal, but reviewing your guide and implementation I think we will achieve it in a different way.

It would be great to compare results in the future

[ldionne]

Ok, well then I'm eager to see the solutions you come up with!

[Manu343726]

Ok, well then I'm eager to see the solutions you come up with!

@ldionne don't worry, I will continue spamming Twitterverse with screen captures and metaprogramming blog posts on the topic

[Manu343726]

I didn't remember this, the void_t issue is a well known GCC bug.

[ericjavier]

...'the types 'a' and 'b', sorry

[Manu343726]

Look at the implementation of the curry adapter (From the coliru links above):

template<template<typename...> class Function>
struct curry
{
    template<typename... Args>
    struct apply
    {
        using f = just_t<Function, Args...>;

        template<typename F, bool is_function = has_type<F>::value>
        struct call
        {
            using type = typename F::type;
        };

        template<typename F>
        struct call<F, false>
        {
            struct type
            {
                template<typename... Tail>
                struct apply
                {
                    using type = eval_mc<curry, Args..., Tail...>;
                };
            };
        };

        using type = typename call<f>::type;
    };
};

As you can see, this translates any metafunction (i.e. any template with a type member) into a metafunction class. When evaluating the resulting lifted metafunction (following MPL11 terminology), it just evaluates the original template when possible, or returns a closure instead.
The magic occurs at the closure!

struct type
{
    template<typename... Tail>
    struct apply
    {
        using type = eval_mc<curry, Args..., Tail...>;
    };
};

The type there, the "value" the lifted metafunction is returning, is a metafunction class too. Is not that results from partial applications behave like functions, is that those are true functions.
Note what that closure returns: It just calls the lifted metafunction again, but adding the captured arguments first.

[ericjavier]

Yes, the problem with variadic meta-functions is controversial, there could be the following template:

template<typename A, typename... Cry> struct foo { using type = A; };

... and the corresponding wrapper

using foo_func = make_func<foo>;

... then if we say

using a = foo_func<int> // or eval<foo_func, int<

... then we have an ambiguous situation, we can get 'int', or let's say: an infinite amount of functions that eventually can give 'int' at some point.

We can take by convention that when a type is available we should get it, i think that this approach is pretty reasonable.

The approach I followed with 'yaml' is the following: when a template instance is well formed then I should evaluate it (I mean maybe we don't need to know when a template is variadic or not), note:

/// \brief SFINAE usage to detect when a set of arguments fits a given template.
/// \!NOTE: only fitting lenght.
template<template<class...> class T, typename... Args>
std::true_type test_fitting(const T<Args...>*);

/// \brief FAILURE OVERLOAD
template<template<class...> class T, typename... Args>
std::false_type test_fitting(...);

/// \brief Helper to know when a set of arguments fits a given template.
template<template<class...> class T, typename... Args>
using fitting_t = decltype(test_fitting<T, Args...>(0));

... then when I get the asserts:

 static_assert(!fitting_t<curryable_function, int>::value, "Instantiable?");
 static_assert(!fitting_t<curryable_function, int, int>::value, "Instantiable?");
 static_assert(fitting_t<curryable_function, int, int, int>::value, "Not instantiable?");

... it works as expected. I use the same approach with variadic templates.

About Sinkovics works:

Yes, I'm. It's a cool project with almost the same goals as ours, but I find the macro based interface >a bit tricky.

yeah, I was not referencing code at all, but his papers and thesis, I think we should have this very close looking to the future.

[ericjavier]

you can see the test I added here with name: "fitting_for_manu, first"

[Manu343726]

yeah, I was not referencing code at all, but his papers and thesis, I think we should have this very close looking to the future.

Thanks, just pinned the document ;)

We can take by convention that when a type is available we should get it, i think that this approach is pretty reasonable. The approach I followed with 'yaml' is the following: when a template instance is well formed then I should evaluate it [...]

That's exactly the same reasoning I'm playing with (See the coliru examples). I'm glad we are agree. I was thinking on a tag to explicitly ask for continuing with currying. Something like:

using is_constructible = curry<std::is_constructible>;
using is_vector_constructible = $(is_constructible, std::vector<int>, Continue);

static_assert($(is_vector_constructible, std::size_t, int)::value, "???");

[ericjavier]

Ok, it seems good to me. A 'continue' tag could help with variadic templates. One question: you also handle placeholders with your closures?

[Manu343726]

Currently not. But, instead you give me one implementation that handles them in a simple manner, I will not add that functionality (with a potential noticeable overhead) to a feature that will be the basis of our language/library.