Filter a list of values at compile time with gnu++11 and no stdlib (Arduino environment)

Question

I'm working on an Arduino project, which means the C++ dialect is currently the gnu++11 superset of C++11, and stdlib is not available (no tuples, no arrays, no nothing; namespace std is just empty!).

For optimization reasons (the CPU has 16K of FLASH, 2K of RAM and this particular low-voltage version runs at 8MHz) I want the compiler to pre-compute as much as possible to provide runtime code, especially the interrupt service routines, with "friendly" data.

Now what I would like to do is the following:

given a list of (unique) integers, I want to extract the values that match an arbitrary filter. Then I want to build an index table that will allow to reach the filtered elements through their initial indices

For instance 2,10,4,7,9,3 with the filter value < 8 could yield the filtered list 2,4,7,3 and the index table 0,-1,1,2,-1,3.
The order of the elements in the filtered array does not matter as long as the index table remains consistent.

I insist on the fact that I want constant arrays. Producing these data dynamically would be trivial, but I want the compiler to do the job, without executing a single instruction at runtime.

The initial list would be given by a plain #define, and the results would be in constant arrays, e.g:

#define my_list 2,10,4,7,9,3

constexpr bool filter (int value) { return value < 8; }

const int    filtered_list [] = filter_list <filter>(my_list);
const size_t filtered_index[] = filter_index<filter>(my_list);

The question is, how to implement these filter_list and filter_index templates with barebone C++11 and no stdlib, if at all feasible?

I'm not interested in error handling, the abnormal cases like empty lists or duplicate values are already taken care of. I'd rather like to see the simplest possible implementation, even if some assumptions are made about data validity.

The exact form of the templates, filter or the initial list do not matter either. All that matters is to get the arrays from an unique list definition.
For instance I would not mind a syntax where each element of the list is declared separately (though I can't really imagine how that could work).

I would prefer to have a self-contained C++ source. On the other hand, if what Python could achieve in a couple dozen lines requires pages of cryptic templates, including the rewriting of std::array and std::tuple, I'd rather write some external preprocessor.

Answer 1

There is a way to avoid most of the boilerplate using function templates instead of full classes. The last class template is needed because there is no return type deduction for functions in c++11. int is used instead of typename T to skip unimportant template parameters. The code could be slimmed further when atmel updates their toolchain to gcc5 or newer with c++14 support.

#define LIST  2,10,4,7,9,3
constexpr bool less8(int v) { return v < 8; }

typedef bool(*predicate)(int);

template<int... values>
struct seq {};

template<int N>
struct array {
      const int   data[N];
};

template<int... values>
constexpr array<sizeof...(values)> to_array(seq<values...>) { return {{ values... }}; }

template<typename trueType, typename falseType>
constexpr falseType select(seq<0>, trueType, falseType) { return {}; }

template<typename trueType, typename falseType>
constexpr trueType select(seq<1>, trueType, falseType) { return {}; }

template<int... first, int... second>
constexpr seq<first..., second...> append(seq<first...>, seq<second...>) { return {}; }

template<predicate p, typename N, typename V>
struct filter_impl;

template<predicate p, int next>
struct filter_impl<p, seq<next>, seq<>> {
      using type = seq<>;
};

template<predicate p, int next, int first, int... rest>
struct filter_impl<p, seq<next>, seq<first, rest...>> {
      using type = decltype(
            append(
                  select(seq<p(first)>{}, seq<next>{}, seq<-1>{}),
                  typename filter_impl<p, decltype(select(seq<p(first)>{}, seq<next+1>{}, seq<next>{})), seq<rest...>>::type{}
            )
      );
};

extern constexpr auto  const_indices = to_array(filter_impl<less8, seq<0>, seq<LIST>>::type{});

Answer 2

My own answer just to put things together from a mundane point of view.

It is heavily based on Daniel Schepler's solution. I certainly would still be stuck on this problem without his help. Rewriting my own version was more like a learning exercise.

//////////////////////////////////////////////////////////////////////////////
// should allow to compile outside Arduino environment without std includes
typedef unsigned char uint8_t;
typedef unsigned size_t;

//////////////////////////////////////////////////////////////////////////////
// pseudo-stl

// barebone std::array
template <typename T, size_t N> struct array {
    T elem[N];
    constexpr size_t size() { return N; }
    constexpr T operator[](size_t i) { return elem[i]; }
};

// barebone std::integer_sequence
template <typename T, T... Values> struct integer_sequence
{
    typedef T value_type;
};

//////////////////////////////////////////////////////////////////////////////
// sequence filtering

// predicate functions prototype (means the sequence type must be convertible to int)
typedef bool(*predicate)(int);

// LISP-like 'if' (selects a parameter according to a boolean value)
template <bool Check, typename IfTrue, typename IfFalse> struct s_if;
template <typename IfTrue, typename IfFalse> struct s_if<true , IfTrue, IfFalse> {using type = IfTrue ;};
template <typename IfTrue, typename IfFalse> struct s_if<false, IfTrue, IfFalse> {using type = IfFalse;};
template <bool Check, typename IfTrue, typename IfFalse>
using f_if = typename s_if<Check, IfTrue, IfFalse>::type;

// LISP-like 'cons' for integer_sequence
template <typename T, T Car, typename Cdr> struct s_integer_sequence_cons;
template <typename T, T Car, T... Cdr> struct s_integer_sequence_cons<T, Car, integer_sequence<T, Cdr...>>
{ using type = integer_sequence<T, Car, Cdr...>; };
template <typename T, T Car, typename Cdr>
using f_cons = typename s_integer_sequence_cons<T, Car, Cdr>::type;

// LISP-like 'append' for integer_sequence
template <typename T, typename S1, typename S2> struct s_integer_sequence_append;
template <typename T, T... S1, T... S2> struct s_integer_sequence_append<T, integer_sequence<T, S1...>, integer_sequence<T, S2...>>
{ using type = integer_sequence<T, S1..., S2...>; };
template <typename S1, typename S2>
using f_append = typename s_integer_sequence_append<S1::value_type, S1, S2>::type;

// filter an integer_sequence according to a predicate
template <typename Sequence, predicate pred> struct s_filter;
template <typename T, predicate pred> struct s_filter<integer_sequence<T>, pred>
{
    using type = integer_sequence<T>; // termination condition
};
template <typename T, T Car, T...Cdr, predicate pred> struct s_filter<integer_sequence<T, Car, Cdr...>, pred>
{
    using tail = typename s_filter<integer_sequence<T, Cdr...>, pred>::type; // forward recursion on the sequence tail
    using type = f_if<pred(Car),            // if current element satisfies the predicate
                      f_cons<T, Car, tail>, // add it to the list
                      tail>;                // else skip it
};
template <typename Sequence, predicate pred>
using f_filter = typename s_filter<Sequence, pred>::type;

//////////////////////////////////////////////////////////////////////////////
// now for the indexation...

// returns the index of a value in a list of values, or -1 if not found
template <int I  , typename T> constexpr T find_index (T elem) { return -1; }
template <int I=0, typename T, typename... List> constexpr T find_index (T elem, T val, List... rest)
{ return elem == val ? I : find_index<I+1>(elem, rest...); }

// builds an index list allowing to reach each value final position from their initial position
template <typename Target, typename Origin> struct s_index_list;
template <typename T, typename Origin> struct s_index_list<integer_sequence<T>, Origin>
{ 
    using type = integer_sequence<T>; // termination of the Target list
};
template <typename T, T Car, T... Cdr, T...Origin> struct s_index_list<integer_sequence<T, Car, Cdr...>, integer_sequence<T, Origin...>>
{
    // as usual, the only way to loop is to recurse...
    using tail = typename s_index_list<integer_sequence<T, Cdr...>, integer_sequence<T, Origin...>>::type;
    using type = f_cons<T, find_index(Car, Origin...), tail>;
};
template <typename Target, typename Origin>
using f_index = typename s_index_list<Target, Origin>::type;

//////////////////////////////////////////////////////////////////////////////
// implementing sequences as arrays

// turn an integer_sequence into a (constant) array
template <typename T, T... x> constexpr array<T, sizeof...(x)> integer_sequence_to_array(integer_sequence<T, x...>)
{ return array<T, sizeof...(x)> { x... }; }

//////////////////////////////////////////////////////////////////////////////
// Putting all this marvelous piece of engineering to use
//

// our initial list
#define input_list 2,10,4,7,9,3

// convert the list into a sequence
typedef integer_sequence<uint8_t, input_list> input_sequence;

// define filtering predicates
constexpr bool test_group_1(int n) { return (n >> 3) == 0; } // values from 0 to 7
constexpr bool test_group_2(int n) { return (n >> 3) == 1; } // values from 8 to 15

// compute the two split sequences
typedef f_filter<input_sequence, test_group_1> sequence_1; // <unsigned char, 2u, 4u, 7u, 3u>
typedef f_filter<input_sequence, test_group_2> sequence_2; // <unsigned char, 10u, 9u>

// append them
typedef f_append<sequence_1, sequence_2> output_sequence; // <unsigned char, 2u, 4u, 7u, 3u, 10u, 9u>

// compute indexes
typedef f_index<output_sequence, input_sequence> output_indexes; // <unsigned char, 0u, 2u, 3u, 5u, 1u, 4u>

// turn the results into arrays
constexpr auto const_values  = integer_sequence_to_array(output_sequence{}); // [2, 4, 7, 3,10, 9]
constexpr auto const_indexes = integer_sequence_to_array(output_indexes {}); // [0, 2, 3, 5, 1, 4]

A few afterthoughts

The purpose of this code is to generate a couple of integer arrays at compile time. This could easily be done with 20 lines of any language able to handle text files (Python, PHP, Perl, awk, you name it...), doing the trivial filtering and indexing in a couple of loops and replacing the line

#define my_list 2,10,4,7,9,3

with

const int    filtered_list [] = {2,4,7,3};
const size_t filtered_index[] = {0,-1,1,2,-1,3};

before passing the modified source to the actual C++ compiler.

The only reason I wanted a self-contained C++ program is the Arduino environment. It is meant to be very simple, and as such is considerably restrictive. You can't really ask a casual Arduino programmer to tweak makefiles or use external code generation tools, so if you want to provide an "Arduino-friendly" module you're basically stuck with this stdlib-less gnu++11 compiler.

Now since the C++ preprocessor is clearly not up to that kind of job, the only choice left is template metaprogramming.

I can't say I really understand how it works, I just used it as a last resort. I'm an embedded software programmer, and my functional programming skills are certainly nothing to write home about.

Still I tried to put my rusty LISP notions to good use, but basic tools like cons, append or if were apparently nowhere to be found, and re-writing them from scratch felt largely like trying to reinvent the wheel. Having to coax the pattern-matching engine into recursion to implement simple loops was also rather painful and made for pretty eye-watering code. Hopefully there's a few useful tricks I missed there.

All this being said, and to my surprise, the lack of stdlib was not really a problem. You can whip up the bare minimum in a few lines of code, provided you throw caution to the wind and kiss the syntactic sugar goodbye.

I finally came up with something that actually does the job in a bit less than 100 lines of very obfuscated code.

I'm not looking for efficiency here, my lists will hardly hold more than a dozen values, but I sure would be happy to watch and learn a way to achieve the same result with less source code. Any takers?

Answer 3

Here is a small implementation of compile-time filtering, reproducing small parts of the standard library in a minimalist way. It includes an example of usage at the end. (It probably isn't possible to implement the filtering as a function, since C++ doesn't allow the result type of a function to depend on the values of the arguments. So, you would have to have the result type have enough storage for the case where the predicate always returns true which seems like it would be a show-stopper for your use case. That is why the approach here is to do the filtering using template metaprogramming first, and then convert the results to an array wrapper object.)

#include <sys/types.h>

template <typename T, size_t N>
struct array {
    T elem[N];
    constexpr size_t size() const { return N; }
    constexpr T operator[](size_t i) const { return elem[i]; }
    T* begin() { return elem; }
    const T* begin() const { return elem; }
    T* end() { return elem + N; }
    const T* end() const { return elem; }
};
template <typename T>
struct array<T, 0> {
    constexpr size_t size() const { return 0; }
    T* begin() { return nullptr; }
    const T* begin() const { return nullptr; }
    T* end() { return nullptr; }
    const T* end() const { return nullptr; }
};

template <typename T, T... x>
struct static_sequence { };

template <bool p, typename TrueT, typename FalseT>
struct conditional;
template <typename TrueT, typename FalseT>
struct conditional<true, TrueT, FalseT> {
    using type = TrueT;
};
template <typename TrueT, typename FalseT>
struct conditional<false, TrueT, FalseT> {
    using type = FalseT;
};
template <bool p, typename TrueT, typename FalseT>
using conditional_t = typename conditional<p, TrueT, FalseT>::type;

template <typename T, T x, typename S>
struct static_sequence_cons;
template <typename T, T x, T... Ss>
struct static_sequence_cons<T, x, static_sequence<T, Ss...>> {
    using type = static_sequence<T, x, Ss...>;
};
template <typename T, T x, typename S>
using static_sequence_cons_t = typename static_sequence_cons<T, x, S>::type;

template <typename T, bool(*pred)(T), T... N>
struct filter;
template <typename T, bool(*pred)(T)>
struct filter<T, pred> {
    using type = static_sequence<T>;
};
template <typename T, bool(*pred)(T), T hd, T... tl>
struct filter<T, pred, hd, tl...> {
private:
    using filter_tl = typename filter<T, pred, tl...>::type;
public:
    using type = conditional_t<pred(hd),
                               static_sequence_cons_t<T, hd, filter_tl>,
                               filter_tl>;
};
template <typename T, bool(*pred)(T), T... N>
using filter_t = typename filter<T, pred, N...>::type;

template <ssize_t curr_index, typename T, bool(*pred)(T), T... N>
struct filter_index;
template <ssize_t curr_index, typename T, bool(*pred)(T)>
struct filter_index<curr_index, T, pred> {
    using type = static_sequence<ssize_t>;
};
template <ssize_t curr_index, typename T, bool(*pred)(T), T hd, T... tl>
struct filter_index<curr_index, T, pred, hd, tl...> {
    using type = conditional_t<pred(hd),
        static_sequence_cons_t<ssize_t, curr_index, typename filter_index<curr_index + 1, T, pred, tl...>::type>,
        static_sequence_cons_t<ssize_t, -1, typename filter_index<curr_index, T, pred, tl...>::type>>;
};
template <typename T, bool(*pred)(T), T... N>
using filter_index_t = typename filter_index<0, T, pred, N...>::type;

template <typename T, T... x>
constexpr array<T, sizeof...(x)> static_sequence_to_array(
    static_sequence<T, x...>) {
    return array<T, sizeof...(x)> { x... };
}


//
// EXAMPLE USAGE
//
constexpr bool even(int n) {
    return n % 2 == 0;
}
constexpr auto x = static_sequence_to_array(
    filter_t<int, even, 0, 1, 2, 3, 4>{});
constexpr auto i = static_sequence_to_array(
    filter_index_t<int, even, 0, 1, 2, 3, 4>{});

static_assert(x.size() == 3, "Bad filter");
static_assert(x[0] == 0, "Bad filter");
static_assert(x[1] == 2, "Bad filter");
static_assert(x[2] == 4, "Bad filter");
static_assert(i.size() == 5, "Bad filter_index");
static_assert(i[0] == 0, "Bad filter_index");
static_assert(i[1] == -1, "Bad filter_index");
static_assert(i[2] == 1, "Bad filter_index");
static_assert(i[3] == -1, "Bad filter_index");
static_assert(i[4] == 2, "Bad filter_index");