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-12 12:47:22

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

> I feel hesitancy with anything you have yet to design. Also, I
> personally think your earlier work items are already more than plenty
> for a GSoC which really is not very long. GSoC uses a US summer
> schedule, we here in Europe get much longer summer holidays (equally,
> the Chinese get less than the US).

Alright, I removed those two tasks.

> > - Make std::tuple, MPL sequences and Fusion sequences valid MPL11
> >   sequences, so they can be used in MPL11 algorithms.
>
> Very nice. You're getting me very excited about MPL11 now.

Since it is not too daunting, I made this a non-optional task.

> Superb Louis. With Joel as prospective mentor, this is exactly the
> kind of GSoC we look for at Boost. Knock the above list into a
> proposal according to Google's proposal template, send it here and I
> think not long after you're ready to submit.

My full proposal follows the Boost template available here:
https://svn.boost.org/trac/boost/wiki/SoCSubmissionTemplate

Here we go. It's rather long, sorry if you meant that I should only
post a link to it.

------------------------------------------------------------------------------

Background information
======================
I am an undergraduate in mathematics with a passion for programming.
My educational and programming backgrounds are summarized on my resume [1].
I could write those here, but that would be redundant.

My main programming interests are metaprogramming and functional programming
in C++ or other languages (Haskell, Python). I usually love it when there
are some abstract mathematics hidden somewhere, so I search for that. I am
interested in contributing to Boost because of the quality of what gets in
there. One of my primary goals at this (early) stage of my life is to get
better. Hence, having to satisfy very high standards is a good thing.

The project I am proposing aims to provide a high quality C++11-enabled TMP
library. I have been thinking about that for about two years, and I have been
working actively on a potential successor to the MPL named MPL11 [2] for about
9 months. I have looked extensively at other libraries with a similar purpose
to make sure I was constantly aware of the state of the art.

But why would Boost want a C++11-enabled TMP library? First, we can improve
the compile-time performance of some algorithms by using variadic templates
and/or constexpr wisely. Also, a C++11 TMP library could be much lighter to
include; as an example, including all the MPL11 is ~35x faster than including
all the MPL, yet they provide similar functionality. However, compilation time
is not the only improvement in C++11; several constructs become easier to use
(say goodbye to vectorN and friends) and errors become easier to decipher
because we do not need to emulate variadic templates.

Project proposal
================
Concretely, here is a 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).

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

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

What follow is a list of optional tasks I would like to complete if I have
the time. Again, each task implies full unit testing and documentation.

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

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

Proposed milestones and schedule
================================
April 22: Start working (part time) on the benchmark suite. A lot of
          subsequent work will depend on it, so it should be done first.

May 18: Begin working full-time. Start implementing the compile-time map
        and set. Use the benchmark suite to help determine the best
        implementation techniques.

June 8: Start implementing numeric metafunctions. Again, use the benchmark
        suite to make sure I'm not doing de-optimization.

June 23: Submit midterm evaluations to Google

July 1: Setup a Boost-compatible build system. This should not be too long.
        Right after, start making MPL and Fusion compatible with MPL11.

July 15: Finish non-optional tasks if that's not done. Otherwise start
         working on optional tasks. Which optional tasks I start with
         could depend on what the community wants the most.

August 11: Pencils down date. Last-minute polishing.

August 18: Submit final evaluation to Google.

Personal details
================
- Name: Louis Dionne
- University: Laval University (Québec, Canada)
- Major: Mathematics
- Degree program: B.Sc.
- Email: ldionne.2_at_[hidden]
- Homepage: ldionne.com
- Availability:
  I can start working a couple hours per week right now (I already do).
  However, full-time work should wait before the end of C++Now, which
  is May, 18. As for the stop date, I would go with the suggested date,
  which is August, 11.

  I can work full-time during the whole summer, i.e. more or less 40hrs per
  week, as the project requires it.

  The only factor limiting my availability is that I would like to take a
  vacation of perhaps one week or so during the summer. However, if I am
  not required to be super-available between the "pencils down" date and
  the final results announcement, then I can take my vacation at that time.

- Knowledge of (from 0 to 5):
    + C++: 3.5
    + C++ Standard Library: 3.5
    + Boost: 3.5
    + Subversion: 1     (I'm sold to git!)
    + Doxygen: 3.5
    + Quickbook: 1
    + CMake: 3.5

  I use the SublimeText editor on OS X and compile on the command line.
  I use GCC 4.9.0 and Clang 3.5.

[1]: http://ldionne.com/resume.pdf
[2]: http://github.com/ldionne/mpl11

------------------------------------------------------------------------------

As always, comments are welcome!

Regards,

Louis