Detection Idiom – A Stopgap for Concepts

Simon Brand from Simon Brand

Concepts is a proposed C++ feature which allows succinct, expressive, and powerful constraining of templates. They have been threatening to get in to C++ for a long time now, with the first proposal being rejected for C++11. They were finally merged in to C++20 a few months ago, which means we need to hold on for another few years before they’re in the official standard rather than a Technical Specification. In the mean time, there have been various attempts to implement parts of concepts as a library so that we can have access to some of the power of Concepts without waiting for the new standard. The detection idiom – designed by Walter Brown and part of the Library Fundamentals 2 Technical Specification – is one such solution. This post will outline the utility of it, and show the techniques which underlie its implementation.


A problem

We are developing a generic library. At some point on our library we need to calculate the foo factor for whatever types the user passes in.

template <class T>
int calculate_foo_factor (const T& t);

Some types will have specialized implementations of this function, but for types which don’t we’ll need some generic calculation.

struct has_special_support {
int get_foo() const;
};

struct will_need_generic_calculation {
// no get_foo member function
};

Using concepts we could write calculate_foo_factor like so:

template <class T>
concept bool SupportsFoo = requires (T t) {
{ t.get_foo() } -> int;
};

template <SupportsFoo T>
int calculate_foo_factor (const T& t) {
return t.get_foo();
}

template <class T>
int calculate_foo_factor (const T& t) {
// insert generic calculation here
return 42;
}

This is quite succinct and clear: SupportsFoo is a concept which checks that we can call get_foo on t with no arguments, and that the type of that expression is int. The first calculate_foo_factor will be selected by overload resolution for types which satisfy the SupportsFoo concept, and the second will be chosen for those which don’t.

Unfortunately, our library has to support C++14. We’ll need to try something different. I’ll demonstrate a bunch of possible solutions to this problem in the next section. Some of them may seem complex if you aren’t familiar with the metaprogramming techniques used, but for now, just note the differences in complexity and abstraction between them. The metaprogramming tricks will all be explained in the following section.

Solutions

Here’s a possible solution using expression SFINAE:

namespace detail {
template <class T>
auto calculate_foo_factor (const T& t, int)
-> decltype(t.get_foo()) {
return t.get_foo();
}

template <class T>
int calculate_foo_factor (const T& t, ...) {
// insert generic calculation here
return 42;
}
}

template <class T>
int calculate_foo_factor (const T& t) {
return detail::calculate_foo_factor(t, 0);
}

Well, it works, but it’s not exactly clear. What’s the int and ... there for? Why do we need an extra overload? The answers are not the important part here; what is important is that unless you’ve got a reasonable amount of metaprogramming experience, it’s unlikely you’ll be able to write this code offhand, or even copy-paste it without error.

The code could be improved by abstracting out the check for the presence of the member function into its own metafunction:

template <class... Ts>
using void_t = void;

template <class T, class=void>
struct supports_foo : std::false_type{};

template <class T>
struct supports_foo<T, void_t<decltype(std::declval<T>().get_foo())>>
: std::true_type{};

Again, some more expert-only template trickery which I’ll explain later. Using this trait, we can use std::enable_if to enable and disable the overloads as required:

template <class T, std::enable_if_t<supports_foo<T>::value>* = nullptr>
auto calculate_foo_factor (const T& t) {
return t.get_foo();
}

template <class T, std::enable_if_t<!supports_foo<T>::value>* = nullptr>
int calculate_foo_factor (const T& t) {
// insert generic calculation here
return 42;
}

This works, but you’d need to understand how to implement supports_foo, and you’d need to repeat all the boilerplate again if you needed to write a supports_bar trait. It would be better if we could completely abstract away the mechanism for detecting the member function and just focus on what we want to detect. This is what the detection idiom provides.

template <class T>
using foo_t = decltype(std::declval<T>().get_foo());

template <class T>
using supports_foo = is_detected<foo_t,T>;

is_detected here is part of the detection idiom. Read it as “is it valid to instantiate foo_t with T?” std::declval<T>() essentially means “pretend that I have a value of type T” (more on this later). This still requires some metaprogramming magic, but it’s a whole lot simpler than the previous examples. With this technique we can also easily check for the validity of arbitrary expressions:

template <class T, class U>
using equality_t = decltype(std::declval<T>() == std::declval<U>());

template <class T, class U>
using supports_equality = is_detected<equality_t, T, U>;

struct foo{};
struct bar{};
struct baz{};

bool operator== (foo, bar);

static_assert( supports_equality<foo,bar>::value, "wat");
static_assert(!supports_equality<foo,baz>::value, "wat");

We can also compose traits using std::conjunction:

template <class T>
using is_regular = std::conjunction<std::is_default_constructible<T>,
std::is_copy_constructible<T>,
supports_equality<T,T>,
supports_inequality<T,T>, //assume impl
supports_less_than<T,T>>; //ditto

If you want to use is_detected today, then you can check if your standard library supports std::experimental::is_detected. If not, you can use the implementation from cppreference or the one which we will go on to write in the next section. If you aren’t interested in how this is written, then turn back, for here be metaprogramming dragons.


Metaprogramming demystified

I’ll now work backwards through the metaprogramming techniques used, leading up to implementing is_detected.

Type traits and _v and _t suffixes

A type trait is some template which can be used to get information about characteristics of a type. For example, you can find out if some type is an arithmetic type using std::is_arithmetic:

template <class T>
void foo(T t) {
static_assert(std::is_arithmetic<T>::value, "Argument must be of an arithmetic type");
}

Type traits either “return” types with a ::type member alias, or values with a ::value alias. _t and _v suffixes are shorthand for these respectively. So std::is_arithmetic_v<T> is the same as std::is_arithmetic<T>::value, std::add_pointer_t<T> is the same as typename std::add_pointer<T>::type1.

decltype specifiers

decltype gives you access to the type of an entity or expression. For example, with int i;, decltype(i) is int.

std::declval trickery

std::declval is a template function which helps create values inside decltype specifiers. std::declval<foo>() essentially means “pretend I have some value of type foo”. This is needed because the types you want to inspect inside decltype specifiers may not be default-constructible. For example:

struct foo {
foo() = delete;
foo(int);
void do_something();
};

decltype(foo{}.do_something()) // invalid
decltype(std::declval<foo>().do_something()) // fine

SFINAE and std::enable_if

SFINAE stands for Substitution Failure Is Not An Error. Due to this rule, some constructs which are usually hard compiler errors just cause a function template to be ignored by overload resolution. std::enable_if is a way to gain easy access to this. It takes a boolean template argument and either contains or does not contain a ::type member alias depending on the value of that boolean. This allows you to do things like this:

template <class T>
std::enable_if_t<std::is_integral_v<T>> foo(T t);

template <class T>
std::enable_if_t<std::is_floating_point_v<T>> foo(T t);

If T is integral, then the second overload will be SFINAEd out, so the first is the only candidate. If T is floating point, then the reverse is true.

Expression SFINAE

Expression SFINAE is a special form of SFINAE which applies to arbitrary expressions. This is what allowed this example from above to work:

namespace detail {
template <class T>
auto calculate_foo_factor (const T& t, int)
-> decltype(std::declval<T>().get_foo()) {
return t.get_foo();
}

template <class T>
int calculate_foo_factor (const T& t, ...) {
// insert generic calculation here
return 42;
}
}

int calculate_foo_factor (const T& t) {
return calculate_foo_factor(t, 0);
}

The first overload will be SFINAEd out if calling get_foo on an instance of T is invalid. The difficulty here is that both overloads will be valid if the get_foo call is valid. For this reason, we add some dummy parameters to the overloads (int and ...) to specify an order for overload resolution to follow2.

void_t magic

void_t is a C++17 feature (although it’s implementable in C++11) which makes writing traits and using expression SFINAE a bit easier. The implementation is deceptively simple3:

template <class... Ts>
using void_t = void;

You can see this used in this example which we used above:

template <class T, class=void>
struct supports_foo : std::false_type{};

template <class T>
struct supports_foo<T, void_t<decltype(std::declval<T>().get_foo())>>
: std::true_type{};

The relevant parts are the class=void and void_t<...>. If the expression inside void_t is invalid, then that specialization of supports_foo will be SFINAEd out, so the primary template will be used. Otherwise, the whole expression will be evaluated to void due to the void_t and this will match the =void default argument to the template. This gives a pretty succinct way to check arbitrary expressions.

That covers all of the ingredients we need to implement is_detected.

The implementation

For sake of simplicity I’ll just implement is_detected rather than all of the entities which the Lib Fundamentals 2 TS provides.

namespace detail {
template <template <class...> class Trait, class Enabler, class... Args>
struct is_detected : std::false_type{};

template <template <class...> class Trait, class... Args>
struct is_detected<Trait, void_t<Trait<Args...>>, Args...> : std::true_type{};
}

template <template <class...> class Trait, class... Args>
using is_detected = typename detail::is_detected<Trait, void, Args...>::type;

Let’s start with that last alias template. We take a variadic template template parameter (yes really) called Trait and any number of other type template arguments. We forward these to our detail::is_detected helper with an extra void argument which will act as the class=void construct from the previous section on void_t4. We then have a primary template which will “return” false as the result of the trait. The magic then happens in the following partial specialization. Trait<Args...>> is evaluated inside void_t. If instantiating Traits with Args... is invalid, then the partial specialization will be SFINAEd out, and if it’s valid, it’ll evaluate to void due to the void_t. This successfully abstracts away the implementation of the detection and allows us to focus on what we want to detect.


That covers it for the detection idiom. This is a handy utility for clearing up some hairy metaprogramming, and is even more useful since it can be implemented in old versions of the standard. Let me know if there are any other parts of the code you’d like explained down in the comments or on Twitter. If you want some more resources on the detection idiom, you might want to watch the conference talks given by Walter Brown5 6, Marshall Clow7 8, and Isabella Muerte9.


  1. See here for information on why the typename keyword is needed in some places. 

  2. Have a look here for a better way to do this. 

  3. Due to standards defect CWG1558, implementations needed an extra level of abstraction to work on some compilers. 

  4. The reason we can’t use the same trick is that parameter packs must appear at the end of the template parameter list, so we need to put the void in the middle. 

  5. CppCon 2014: Walter E. Brown “Modern Template Metaprogramming: A Compendium, Part I” 

  6. CppCon 2014: Walter E. Brown “Modern Template Metaprogramming: A Compendium, Part II” 

  7. ACCU 2017: The Detection Idiom - a simpler way to SFINAE - Marshall Clow 

  8. C++Now 2017: Marshall Clow “The ‘Detection idiom:’ A Better Way to SFINAE” 

  9. CppCon 2016: Isabella Muerte “No Concepts Beyond This Point: The Detection Idiom” 

Libc++ v5 PPA for Ubuntu now available

Anthony Williams from Just Software Solutions Blog

I am please to announce that I have made v5.0 of libc++ available for Ubuntu Linux via a PPA. Initially, the binaries are only available for Ubuntu 16.04 Xenial.

I was frustrated at the lack of an up-to-date build of libc++ for linux, especially with the v5.0 release of clang. Even though the LLVM project provide Ubuntu packages for clang, they don't provide one for libc++, and the version in the Ubuntu repositories is woefully out of date (v3.7). I therefore decided to package it myself, in this PPA.

This is especially good, since in combination with clang v5.0, it provides support for the Coroutines TS!

Enjoy!

Posted by Anthony Williams
[/ news /] permanent link
Tags: , , , ,

| Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

Follow me on Twitter

The book of five rings

Jon Jagger from less code, more software

is an excellent book by Miyamoto Musashi, translated by Thomas Cleary (isbn 1-57062-748-7). As usual I'm going to quote from a few pages:
Preface: In common parlance, to do something with a real sword means to do it with utmost earnestness… The Book of Five Rings… explicitly intended to symbolise processes of struggle and mastery in all concerns and walks of life.
The martial way of life practiced by warriors is based on excelling others in anything and everything.
Fourth is the way of the artisan. In terms of the way of the carpenter, this involves skilful construction of all sorts of tools, knowing how to use each tool skilfully, drawing up plans correctly by means of the square and the ruler, making a living by diligent practice of the craft… practice unremittingly.
You should observe reflectively, with overall awareness of the large picture a well as precise attention to small details.
Having attained a principle, one detaches from the principles; thus one has spontaneous independence in the science of martial arts and naturally attains marvels.
As human beings, it is essential for each of us to cultivate and polish our individual path.
Observation and perception are two separate things.
It is essential to be relaxed in body and mind.
If you get to feeling snarled up and are making no progress, you toss your mood away and think in your heart that you are starting everything anew.
In my military science, it is essential that the physical aspect and the mental state both be simple and direct.
Whether in large- or small-scale military science, there is no narrow focus of the vision. As I have already written, by finicky narrowness of focus, you forget about bigger things and get confused, thus letting certain victory escape you.
Things stick in your mind because of being in doubt.
The practice of all the arts is for the purpose of clearing away what is on your mind. In the beginning, you do not know anything, so paradoxically you do not have any questions on your mind. Then, when you get into studies, there is something on your mind and you are obstructed by that. This makes everything difficult to do.


Learning C++

Simon Brand from Simon Brand

C++ is one of the most powerful programming languages in the world. However, it can also be one of the most daunting for beginners. There is so much to learn, so many corner cases, so many little languages within the language itself, that mastering it can seem an insurmountable task. Fortunately, it’s not quite as impossible as it looks. This post outlines some resources and advice for learning C++ today. Some of these also will be useful for those who have used C++ in the past and want to get familiar with modern C++, which is like an entirely different language.

If you want to learn C++ from scratch, don’t rely on random online tutorials. Get a good book. One of these. I read the entirety of Accelerated C++ the day before the interview for my current job, and it was enough to get stuck in to real C++ development. It’s a bit outdated now, (i.e. it doesn’t cover C++11/14/17) but is easily the most important book in my career development. The Effective C++ series by Scott Meyers should be mandatory reading for C++ developers, particularly Effective Modern C++, which is the go-to introduction to C++11 and 14. If you prefer online resources, use reputable ones like Kate Gregory’s Pluralsight courses rather than whatever Google throws out. There are a lot of terrible C++ tutorials out there which will only harm you. A good rule of thumb: if you see #include <iostream.h>, run1.

However, no matter how much you read, you need to practice in order to improve. I find it helpful to have a mix of small, self-contained problems to try out new techniques, and larger applications to make sure you can use those ideas in a real-world context. Kind of like unit tests and integration tests for your programming skills; can you use these ideas in isolation, and can you fit them together into something comprehensible and maintainable.

Stack Overflow is a great source of skill unit tests. I learned most of my initial metaprogramming knowledge by answering Stack Overflow questions incorrectly and having people tell me why I was wrong. Unfortunately it can be an unforgiving community, and isn’t friendly to very simple questions. Be sure to read through the rules thoroughly before contributing, and feel free to send me an answer you were going to post to get feedback on it if you’re worried!

For skill integration tests, I’d recommend coming up with an application in a domain you’re interested in and trying to develop it from start to finish. If you haven’t done much of this kind of thing before, it can be a daunting task. The main piece of advice I have on this is to ensure your application has a strict scope so that you always know what you’re aiming towards and when you’re finished. Set a number of checkpoints or milestones so that you have explicit tasks to work on and don’t get lost. Some ideas for fun projects:

  • A compiler for a simple C subset
  • A mini text editor
  • Implement some simplified standard library classes, like std::vector
  • A clone of a simple video game like Snake
  • An ELF file manipulation tool

One of the most valuable knowledge sources is a good C++ community to be part of. Find out if your city or a nearby one has a User Group and go along to meet other developers. They might even have a mentorship program or advice channels for people learning the language. Definitely get on to the C++ Slack Channel and lurk, ask questions, join in discussions. Many of the foremost C++ experts in the world hang out there, and it’s also a very friendly and welcoming environment to those learning. There are even dedicated subchannels for those learning or having problems debugging C++.

Don’t be discouraged when you find things difficult, and, trust me, you will. C++ is hard, and even the experts get things wrong, or can’t even agree on what’s right.

If you do get good, pass on the knowledge. Start a blog, give advice, mentor those who need it, talk at conferences. You do not need to be an expert to do these things, and we need more speakers and writers from a diverse set of experience levels, as well as in background, race, gender, sexuality. The major C++ conferences all have codes of conduct and organisers who care about these issues. Many of them also have student or accessibility tickets available for those who need further assistance to attend. If in doubt, just ask the organisers, or drop me a message and I can get in touch with the relevant people.

Finally, find some good, regular blogs to learn from. Here are some I would recommend:

I hope that this post helps you in your journey to learn C++. It’s a long, but very rewarding path, with a lot of wonderful people to meet, work with, and debate metaprogramming techniques with along the way.


  1. iostream.h rather than just iostream the name for the header before C++ was standardised. People are still writing tutorials which teach using this form and ancient compilers. 

Unit Testing with Mocha, a local instance of dynamoDB & Promises

Pete Barber from C#, C++, Windows &amp; other ramblings

I'm writing the backend for my current iOS App in Javascript using node.js, AWS Lambda along with DynamoDB.

My AWS Lambda code is mostly AWS Lambda agnostic except for the initial handler methods, this makes them fairly testable outside of AWS. However, they depend on the DynamoDB. It's quite easy to write Unit Tests that run against a live version of DynamoDB but I wanted to run against a local instance, ideally an in-memory instance so that it would be quick (not that running against a real instance is that slow) and so that I could have a clean dB each time.

NOTES

  • As these tests are running against a dB it might be more accurate to call them Integration Tests implemented using a Unit Testing framework but I'll refer to them as Unit Tests (UTs).
  • This is running on MacOS
  • I don't Unit Test the actual AWS Lambda function. Instead I export the underlying functions & objects that the AWS Lambda uses and Unit Test these.
  • I'm a JavaScript, Node, AWS n00b so this if you spot something wrong or that'd bad please comment.
  • I don't like the callback pyramid so I use Promises where I can. I would use async and await but the latest version of Node that AWS Lambda supports doesn't support them :-(

In order to run this locally you'll need:
My goal was to have a clean dB for each individual Unit Test. The simplest way to achieve this I thought was to create an in-memory of dynamoDB and destroy it after each Unit Test.


This uses the child_process npm package to create an instance before each test, store the handle to the process in local-ish variable and following the tasks just kill it. The important points here are that the '-inMemory' option is used meaning that when the dB instance is killed and another re-started everything is effectively wiped without having to do everything.

The problem I had with this approach is that in addition to creating the dB each time I also needed to create a table. Whilst the documentation for local dynamoDB says that one of the differences between the AWS hosted & the local versions is that CreateTable completes immediately it seems that the function does indeed complete immediately the table isn't immediately available. This meant the UT using the table often failed with:

1) awsLambdaToTest The querying an empty db for a user Returns{}:
     ResourceNotFoundException: Cannot do operations on a non-existent table

I'm going to jump ahead and show the completed Unit Test file and explain the various things I had to do in order to get it working. This shows the tests.


before()/after() - creating/destroying dynamoDB


Rather than attempting to create & destroy the dB for each Unit Test I settled with creating it once per  Unit Test file. This is handled in the begin() & after() functions. Here the local instance of dynamoDB is spawned using the child_process package and reference to the process retained. This is then used to kill it afterwards. The important point to note here is the use of the sleep package & function.

I found when I had multiple test files, each with their own begin() & after() functions that did the same as these, even though kill had purported to have killed the processed (I checked the killed flag) it seemed the process hadn't died immediately. This meant that the before() function in the next set of tests would succesfully connect to the dying instance of dynamoDB. Then later when any operation was performed it would just hang until Mocha timed-out the Unit Test/before handler. I tried various ways to detect that the process was really dead but none worked so settled for a sleep.

beforeEach()/afterEach() - creating/destroying the table

Where possible I use Promises. Mocha handles promises quite simply for both hooks (the before*/after* functions) and Unit Tests. The key is to make sure to return the final promise (or pass in the done parameter & call it - though I don't use this mechanism).

Looking at the beforeEach() function createTable() is called which returns a promise (from the AWS.Request type that aws-sdk.DynamoDB.createTable() returns. This promise is then chained too by the synchronous waitFor method. This polls the dB for state of the table. The returned promise will not complete until the table has been created and waitFor has completed.

I am not convinced that waitFor is needed. According to the AWS vs Local DynamoDB guide for local instances tables are created immediately. I added this check as occasionally I was getting resources errors like the one earlier. However, I think the cause for that was because I forgot the return statement before the call to createTable() meaning no Promise was returned to Mocha so it thought the beforeEach() function had completed. I have removed this since in my real Unit Tests and they all seem to work.

Unit Tests

That's really it. The hard part wasn't writing the UTs but getting a local instance of DynamoDB running with the table that the functions to test used in the correct state. Again, due to the functions being tested usually returning promises themselves it is necessary to return Promise. The assertion(s) are made synchronously in a then continuation chained to Promise returned from the function being tested and Promise from the whole chain returned.

If an assertion returns false then even though it's within a continuation Mocha detects this and the test fails. If the function under test throws then Mocha also catches this and the test fails.

And finally

timeout

There's also the this.timeout(5000); at the top of the tests for this file. By default Mocha has 2 second timeout for all tests and hooks. By having the 1 second sleep for starting the dB it's possible for the hook to timeout then causing everything else to fail. The 5 second timeout protects against this.

localhost

When creating the local instance it uses the default port of 8000 and is accessible via the localhost hostname alias. This is used to access the dB when creating the reference to it in before(). A local aws.config is also constructed in each of the functions that access the dB in the actual code under test below.

The actual code being tested


The Best Laid Schemata – a.k.

a.k. from thus spake a.k.

We have seen how we can exploit a simple model of biological evolution, known as a genetic algorithm, to search for global maxima of functions, being those points at which they return their greatest values.
This model treated the function being optimised as a non-negative measure of the fitness of individuals to survive and reproduce, replacing negative results with zero, and represented their chromosomes with arrays of bits which were mapped onto its arguments by treating subsets of them as integers that were linearly mapped to floating point numbers with given lower and upper bounds. It simulated sexual reproduction by splitting pairs of the chromosomes of randomly chosen individuals at a randomly chosen position and swapping their bits from it to their ends, and mutations by flipping randomly chosen bits from the chromosomes of randomly chosen individuals. Finally, and most crucially, it set the probability that an individual would be copied into the next generation to its fitness as a proportion of the total fitness of the population, ensuring that that total fitness would tend to increase from generation to generation.
I concluded by noting that, whilst the resulting algorithm was reasonably effective, it had some problems that a theoretical analysis would reveal and that is what we shall look into in this post.