Re: [boost] [GSoC] [RFC] Proposal: A C++11 enabled TMP library

Subject: Re: [boost] [GSoC] [RFC] Proposal: A C++11 enabled TMP library
From: Louis Dionne (ldionne.2_at_[hidden])
Date: 2014-03-11 23:11:42

Niall Douglas <s_sourceforge <at> nedprod.com> writes:

> It's very simple: If you weren't in GSoC this summer, I'd assume
> you'd spend your summer working on your TMP library anyway. So simply
> list what you hope to finish this summer, and propose the first half
> of that for GSoC as concrete items and the second half as optional
> "would like if have time" items. Post that here when you're done.

First, thank you for taking your time to help me.

Here is the list of MPL11-related tasks I plan to clear during the summer.
Note that full unit testing and documentation is implied for each task.

- Write a suite of benchmarks to compare the compilation time and memory
  usage of different TMP techniques. The benchmarks should run automatically
  on different input datasets and produce charts for easy comparison. This
  can be done with e.g. Ruby and a Ruby binding for Gnuplot.

- Implement a compile-time map and a compile-time set with variadic templates.
  Several implementation techniques should be tested and benchmarked to pick
  the best one. For the interface, I'm thinking about an something similar
  to Haskell's Data.Map.Strict for the map and to Data.Set for the set. Note
  that I will have to decide what kind of type equality to support: type
  identity or "deep" type equivalence?

- Write numeric metafunctions that can perform efficiently on homogeneous
  sequences of integral constants (using constexpr).

- Write a tutorial that does not only present the core concepts of the
  library, but really shows how to use it for concrete tasks.

- Setup a Boost-compatible build system; the library currently uses CMake.

- Design a cross-tag dispatching system for binary metafunctions (probably
  following N3351). This is a bit like the mixed-type numeric metafunctions
  of the MPL, except it should work with arbitrary (non-numeric) types and
  metafunctions.

- Design a small DSL to write inline metafunction classes. This is pretty
  much like lambda expressions in the MPL, but:
    - It should be possible to refer to arguments in an outer scope. This
      issue can be addressed either by let-expressions or De Bruijn indices.
    - It should be possible and easy to define custom placeholders.
    - It should be possible to have variadic placeholders, i.e. placeholders
      that are replaced by more than one argument. Note that this is tricky
      because the template in which the placeholder appears might not have
      the arity required to perform the substitution.

These are optional tasks I would like to complete if I have the time. Again,
each task implies full unit testing and documentation.

- Make std::tuple, MPL sequences and Fusion sequences valid MPL11 sequences,
  so they can be used in MPL11 algorithms.

- Implement pattern matching on template specializations, much like
  Proto's match<> but for arbitrary template specializations. Pattern
  modifiers should be provided. At the minimum:
  - or_<Patterns...> matches if any of the Patterns match.
  - and_<Patterns...> matches if all of the Patterns match.
  - not_<Pattern> matches if the Pattern does not match.
  - when<F> matches if apply<F, T>::type::value is true, where T is
    the expression being matched against.

- Implement a compile-time graph data structure. The graph should support
  an interface similar to Boost.Graph's adjacency_list. Some basic graph
  algorithms should also be provided. At the minimum:
  - depth-first search
  - breadth-first search
  - topological sort
  - transitive closure

  This is useful e.g. to order the execution of computations at compile-time.
  By creating a compile-time graph where nodes are computations and edges are
  dependencies between them, one can determine which computations can be
  parallelized and which ones must be linearized.

Comments welcome!

Regards,

Louis