Predicates are functions that return a boolean value. Unary predicates take a single parameter to decide the return value [drdobbs] [cppref]. They are useful in many higher order functions e.g. ‘_if’ algorithms in standard library such as find_if or remove_if, partition etc. With increase in functional style programming and libraries within C++, predicates are going to be used more often.
This blog post shows cute, little unary predicates that save some keystrokes and work together well. We will walk through the implementation that begins with thinking generic and towards the end embarks on an often used metaprogramming pattern. Let’s have a look at what these predicates look like in the first place and observe their behavior.
Example-1: Relational operators with logical
Example-2: Multiple elements and element selection
Now, let us see an interesting real world example.
Example-3: A unit circle at origin
We begin with a simple implementation of relational operators. A relational predicate, like equals or greater than, takes a reference value initially. Each time the predicate is called with a parameter, it compares the parameter value with the reference value and returns a boolean. Since, the reference type and parameter type are not some fixed type, we express it with generic programming as follows.
The parameter type of the function call operator overload is not required to be same as the type of reference (Ref). However, it is necessary that comparing the values of two types with
== is semantically valid. This is because templates follow Duck typing.
Similarly, we can have Gt and Lt classes for greater than and less than, respectively.
Till now there is no logical operator to connect the different predicate classes. We know that the behavior of a logical operator is same for all the predicates. It implies we should not be writing operator overloads for logical operators separately in each predicate. Let us first try to frame a generic logical operator.
Notice that the And class itself is a predicate (returns boolean on function call) which is what we expect it to be. The class implementation simply says that it can be instantiated with any two predicates and each time the instantiated object will be called with a parameter, it will return the conjunction of the results of the two predicates for that parameter. The templates let us express this in a generic way with only duck-typing rules to follow. The
forward are there to express that the template predicate types can be either lvalue or rvalue and in either case predicate values will not be copied to the class members. In former case the member predicates (_pred1 and _pred2) reference to the constructor parameters (p1 and p2) while in latter case the constructor parameters are moved to the members. A simple way to understand lvalue and rvalue is that lvalue is held by a declared variable while an rvalue is a temporary that is not assigned to any variable. E.g. In the
a && !eq(1) expression of Example-1,
a is an lvalue while
eq(1) is an rvalue. Supporting predicates without copy is important since predicates by definition can be non-copiable like a lambda function.
Similarly, we can create a class for other two logical operators viz. or and not.
Now, let us create an umbrella class with all the logical operator overloads, so that we can reuse it to add logical operator overloads to any predicate.
We add similar operator overloads for
It is however not yet clear how these pieces especially the Logical_ops class will be used along with others. Let us tie these pieces together.
We know, inheritance gives a direct way of reusing the code. With public inheritance we can provide the public interface of logical operator overloads to the predicates. It looks like we need to inherit every relational operator class from Logical_ops class.
But, in the current form they don’t fit together. The operator overload method for a logical operator in a predicate class takes the first operand implicitly to be
this similar to any other method, while in current implementation of Logical_ops we have both the operands as parameter. The first implicit operand can vary in a restricted sense i.e. it is same as the predicate class that inherits from Logical_ops e.g. in Eq class the type of first operand will be Eq while the second operand can be any other predicate while in Gt the type of first operand would only be Gt. This smells like generic programming but has a wee bit more to it. Let us change the Logical_ops to have an implicit first operand of any generic template class type.
Finally, we need to change relational predicates to inherit from Logical_ops while passing the correct template types to it.
And, same for logical predicate classes so that we can continue chaining them with more logical operators.
The idea of passing itself as a template parameter for the base class sounds unusual and so does its name, CRTP (curiously recurring template pattern) which in general known as f-bounded polymorphism (even weird). It is a no overhead abstraction, since it enables static binding rather than dynamic dispatch of virtual functions.
We skipped over a couple of small details like overloading the logical operators for ltype and rtype separately, object generators, adding element selection to logical operators etc. These details can be found in the code here and examples can be found here. It is part of the easyLambda library for data processing. The predicates and examples can be used separately without any dependence on the easyLambda library. Don’t forget to check the library as well.
This is just one way out of many possible ways to implement such predicates. Please suggest improvements and how you would implement this.
I am not sure how much useful these predicates are in general but I have found them to be pretty useful for data processing. They appear in many examples in easyLambda. I have also found element selection quite useful in reusing the predicates. The technique defined for combining with logical operators can be applied to any general predicate. I believe that a library with geometrical predicates like
in_circle etc. would also be of use in various cases.