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
- 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.