Sunday, October 20, 2013

Curried type traits

Partial meta function application is critically useful. For example, if you want to test a list of types whether they are implicitly convertible to a known type T, basically you need to “bind” T to is_convertible. With Boost.MPL, it would be:

using F = std::is_convertible<mpl::_1, T>;

_1 is a meta placeholder[1], which is conceptually same as that to std::bind, but works with meta functions. However, while the result of std::bind still supports operator(), now the F above can only be called with mpl::apply<F, Arg>. Such a calling convention change also affects meta algorithms’ implementation. Although Boost handles it very well, it can hardly be a cross-library solution.

Here is a simple thought: use currying[2] instead of partial application. Currying starts with a simple interpretation of a multi-argument function:

f(a, b, c, ...) => f(a)(b)(c)...

In the world of currying, there are only unary functions, and a multi-argument function is just a function returning another unary function, and applying such a function, in effect, is to bind an argument. Mapping these to C++, I get:

is_constructible<T1, T2, T3> =>
curried<is_constructible, 3>::call<T1>::call<T2>::call<T3>

The second argument of curried is the number of arguments you want to curry; defaults to 2. There we have the construct to make any argument “free to bind”, and the next step is to make an argument at any position “ready to bind”:

flipped<curried<F, 3>, 3>:call<T3>::call<T1>::call<T2>

flipped switches the Nth argument of a curried function to the next call position; N defaults to 2 (you may have noticed that these two functions are just generalized curry and flip in Haskell). Now we are able to bind any argument, any where.

The last issue is that a meta algorithm might expect normal multi-argument functions, not curried ones. Basically, we need uncurry. Here is the shining part: wherever useful, there is an ::apply typedef in addition to ::call to give you the “automatically” uncurried meta function:

flipped<curried<F, 3>, 3>:call<T3>::apply<T1, T2>

Now the advantage of this system is quite clear: the calling convention is not changed — after done processing the meta function, ::apply or ::call is just the processed meta function. For the example at the beginning, it would be

using F = flipped<curried<std::is_convertible>>::call<T>;

, then drop F::call to wherever need a template. If you want to know more, here is a tiny meta programming library[3] I wrote based on this system.

Links:

[1] Handling Placeholders, from “A Deeper Look at Metafunctions”. http://www.artima.com/cppsource/metafunctions2.html

[2] Currying. https://en.wikipedia.org/wiki/Currying

[3] C++ traits adaptors. https://github.com/lichray/traits_adaptors

Sunday, September 15, 2013

xrange for C++

Python does not have a traditional C-like for loop or a Pascal-like counted for loop; the “Pythonic” solution is to use the iterator-based for-in loop with an xrange (renamed into range in Python 3) iterator:

>>> for i in xrange(1, 6):
...     print i,
... 
1 2 3 4 5

Like in C++, it gives a half-open range.

I think this is a good approach, since it offers a higher abstraction compared to a handmade for loop in C; you don’t need to run a state machine in head to know where the loop stops because there is no states at all.

C++11 range-based for[1] can also make use of iterators, so it’s fairly easy to write a factory to generate an underlying object which gives you those iterators:

for (auto i : xrange(1, 6))
	std::cout << i << ' ';

You can find more examples at https://github.com/lichray/xrangexx/blob/master/example.cc .

Different from the one in Python, my version does not have the step argument, because range-for only uses != to compare the iterators even they support random access (as a result, looping across a range [a, b) where a > b results in an undefined behavior). There is nothing wrong from the point of view of genericity, and practically it’s easier to get things right when using an adjacent input range and multiplying each value with a factor inside the loop.

The header file also includes a utility, rxrange, to generate a reversed xrange, providing the same argument — exactly as same as what you get with reversed(xrange(a, b)) in Python. C++17 is probably going to have the Range[2] concept and some range adaptors, but I think it’s still worth to have a shorter spelling, like rbegin(…) vs. reverse_iterator<T>(begin(…)).

Links:

[1] Range-based for loop (since C++11) http://en.cppreference.com/w/cpp/language/range-for

[2] SG9, Ranges http://isocpp.org/std/the-committee

Saturday, April 27, 2013

Explicit type conversion makes no sense

One of the most criticized “feature” in C++ is that, a constructor which may accept one argument IS an implicit conversion function from the argument type T to the class type U. For example:

struct A {
	A(int, int = 4) {}
};

void f(A) {
}

f(3);  // f(A) is called

Such a “feature” is terribly bad. It looks like something designed to disable the compilers’ type checking and to mess up the overloading set. But, all the criticisms are targeting the “implicit” aspect of this feature. I haven’t seen an argument to criticize the “conversion” part.

My argument is, for short,

  1. Implicit conversion makes sense.
  2. Explicit conversion makes no sense.

Let’s define a type as a set of all the possible values and a set of all the possible operations which deal with the values. Now, say if we have two types, int and list<long>, is that possible to convert an int n to a list<long>? Oh, maybe a list of n zeros. But wait, why zeros? And, what if I expect a {n}? See? If we allow one possible value set to be converted to an arbitrary possible value set, the semantics of the conversions are arbitrary and multiple, but the explicit conversion can only carry one semantics.

So that’s why I say explicit conversion makes no sense. To express the meaning of an arbitrary conversion, the conversion function has to be named in some way to connect the two types involved, like list<long>::from_size(n), while an explicit conversion function is only named in a meaningless way (list<long>(n)).

But in one situation, a conversion is not arbitrary, and it can be safely and implicitly established from type T to U, if the possible value set of T is a subset of U's. Actually, C++ understands this theory, and that is why C++ allows an object of a derived class to be implicitly converted to an object of the base class, since an object of a derived class is supposed to be able to be used anywhere in place of an object of the base class.[1]

As you can see, the problem is not caused by “implicit”; the problem is caused by “conversion” — mixing the conversion semantics into the constructors is a design error in C++.

So here are my suggestions:

  1. Use implicit conversion for its well-defined semantics;
  2. Prefer named functions/factories[2] over constructors.

Notes:

[1] Unfortunately, such a mechanism is broken if the derived class has a different representation, which results in a type punning, which simply breaks the type safety. However, pointer conversions and pointer to member conversions work.

[2] Like make_shared, and “named constructor”: https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Named_Constructor

Tuesday, January 1, 2013

Use array as a tuple

After variadic template being supported by VC++ Nov 2012 CTP, the feature which will blow away most of our old code is supported by all of the major C++ compilers, and the next topic is how we use it well. A frequently raised question is that, how to expand a pack of arguments, like an std::tuple, to a function. Like, instead of writing

std::lock(l1, l2);

we want

std::tuple<std::mutex, std::mutex> t;
vlock(t);

Now we already know the solution: the “indices trick”[1] — to expand a variadic indices, not the arguments.

template <size_t... I>
struct indices {};

template <size_t N, size_t... I>
struct build_indices : build_indices<N - 1, N - 1, I...> {};
 
template <size_t... I>
struct build_indices<0, I...> : indices<I...> {};

template <typename Tuple>
using tuple_indices = build_indices<std::tuple_size<Tuple>::value>;

template <typename Tuple>
using tuple_indices = build_indices<std::tuple_size<Tuple>::value>;

template <typename Tuple, size_t... I>
void _vlock(Tuple&& t, indices<I...>) {
	std::lock(std::get<I>(std::forward<Tuple>(t))...);
}

template <typename Tuple>
void vlock(Tuple& t) {
	_vlock(t, tuple_indices<Tuple>());
}

The best thing with the implementation I referred is that, it works with any type supporting the “tuple-like” protocol, e.g., std::pair, std::tuple, and std::array. The last one is very interesting since it provides both the tuple-like access and the STL container interfaces.

However, std::array has a tiny problem: its size template parameter has to be explicitly specified:

std::array<std::mutex, 2> t {};

So how about to use a native array instead? A trivial and evil approach is to specialize std::get, std::tuple_size and std::tuple_element before the definition of _vlock:

// unused specializations are omitted
namespace std {
template <size_t I, typename T, size_t N>
auto get(T (&a)[N]) -> T& {
	static_assert(I < N, "out of range");
	return a[I];
}

template <typename T, size_t N>
class tuple_size<T[N]> : public integral_constant<size_t, N> {};
}

std::mutex t[] = { {}, {} };  // bad example...
vlock(t);

However, to open the std namespace is not permitted by the standard. If you consider these specializations to be helpful, maybe you can submit a proposal to LWG.[2]

Links:

[1] The indices trick http://loungecpp.wikidot.com/tips-and-tricks%3Aindices

[2] How To Submit a Proposal http://isocpp.org/std/submit-a-proposal

Wednesday, November 21, 2012

Fix unpaired perfect forwarding

To enable perfect forwarding in C++11, you need a template parameter T paired with a function template parameter T&&. Scott Meyers calls it `Universal Reference’[1] because, by combining the special deduction rule (14.8.2.1/3) and the reference collapsing rule (8.3.2/6), you will get a lvalue reference or an rvalue reference corresponding to the expression category of the actually argument of the call. However, a problem was raised on comp.lang.c++:[2]

template<typename T> void foo(T&&, T&&); 

A first impression is that, T&& is still a `universal reference’. But, the call foo(1, a) fails since T con’t be deduced to both int and int&. So this is the problem of our faked `universal reference’: in C++03, there is no way to have a cv-qualified or reference type deduced for T, but now, a lvalue reference is allowed, while the type comparison rule is unchanged.

We can simulate the rule by hand:

template <typename T1, typename T2> void foo(T1&&, T2&&,
    typename std::enable_if<std::is_same<
    typename std::remove_reference<T1>::type,
    typename std::remove_reference<T2>::type>::value>::type* = 0)
{}

However, despite of its cryptic verbose grammar, the big problem is: what if we add more parameters, like T3? A new SFINAE template is needed:

template <typename...>
struct common_deduced_type;

template <typename T>
struct common_deduced_type<T, T> { typedef T type; };

template <typename T>
struct common_deduced_type<T&, T> { typedef T type; };

template <typename T>
struct common_deduced_type<T, T&> { typedef T type; };

template <typename T>
struct common_deduced_type<T&, T&> { typedef T type; };

template <typename T1, typename... T2>
struct common_deduced_type<T1, T2...> {
	typedef typename common_deduced_type<T1,
	    typename common_deduced_type<T2...>::type>::type type;
};

Similar to std::common_type, but without implicit conversion, just removing the lvalue reference then to compare. The trick fix the unpaired prefect forwarding pretty well,

template <typename T1, typename T2, typename T3, typename T4>
void foo(T1&&, T2&&, T3&&, T4&&,
    typename common_deduced_type<T1, T2, T3, T4>::type* = 0)
{}

but a modified type comparison matching the new deduction rule can be more straightforward.

Links:

[1] Universal References in C++11—Scott Meyers http://isocpp.org/blog/2012/11/universal-references-in-c11-scott-meyers

[2] Template argument as rvalue reference https://groups.google.com/forum/#!topic/comp.lang.c++/8YUIqp300ME/discussion