Writing min function, part 3: Weakening the ordering

This is the third article of the series called “Writing min function”:

Now we understand what Concepts are (do we?), I will try to complete the min function.

What do I mean with “complete”?

Well, we need to see how to use our min function, but first, let’s write the min function in a real programming language.

From now on I will write code in C++. Why C++?, it is a topic for another article. But don’t worry, I will try to analyze all the algorithms in several programming languages in the following articles.

Here is the code of the min function from part 2:

//Note 1: this code is Concept-enabled C++.
//        Later we will see how to use it.
//Note 2: Still has errors!
template <TotallyOrdered T>
T const& min(T const& a, T const& b) {
    if (a < b) return a;
    return b;
}

(We will see how to define the TotallyOrdered concept in C++ later. For now, think in the mathematical definition presented before)

And we use it in this way:

void usage_with_builtin_types_simple() {
    int a = 12;
    int b = 34;

    //using variables
    cout << min(a, b); //print the result on standard output

    //using integer-literals (base10)
    cout << min(1, 2);

    //using variables and literals
    cout << min(a, 2);

    //assigning the result (copy)
    int m1 = min(a, b);
    int m2 = min(1, 2);
}

These are very simple examples using the int builtin type, but our min function is supposed to be Generic, so it has to operate with all types that satisfy the TotallyOrdered concept. So let’s see a little more complicated example.

Suppose we maintain the employee database of a company and we want to take two employees and know which is the minimum of the two. Let’s see it on code. Here a simplified Employee class written in C++:

struct employee { string name; float salary; };

And now we use the min function with Employees:

void usage_with_employees() {
    employee e1 {"John", 5000.0f};
    employee e2 {"Peter", 6000.0f};
    employee e3 {"George", 4500.0f};
    employee e4 {"Frank", 5000.0f};

    employee m = min(e1, e2); // ???
}

What happend at line 7?

Well, we should get a compile-time error saying that the employee type doesn’t satisfy the TotallyOrdered concept.

Why?

First, syntactically there is no way of comparing two employees using the less-than-operator required by the TotallyOrdered concept.
If we use C++ templates without Concepts (or duck-typing templates) we will get a compile-time error pointing to the min function, saying that a < b could not be done. Instead, if we use a dynamic duck-typing language, like Python, we will get a similar error but at runtime.
The compiler (or interpreter) doesn’t know how to do a < b for employees, so this is the reason why we get the error.

So, how to make my Employee type to satisfy the TotallyOrdered concept?

Let’s start satisfying the requirements imposed by the concept:

  1. Employee must satisfy the Regular concept.
  2. We have to provide an operator< with the signature: Employee x Employee -> bool
  3. The operator< must be a total ordering relation.

For now I want to skip the points 1 and 3, we will see them in another article. So let’s concentrate on point 2, which is a syntactic requirement, that specify that we have to provide the operator<, so let’s do it:

bool operator<(employee const& a, employee const& b) {
    return ???????;
}

This is the canonical way on C++ for implementing a less-than-operator, but … What should I put on line 2?

Actually, I don’t know. That answer should be given by the designer of the Employee class. Well…, that’s me (?).

First, remember, total ordering, is, roughly speaking, some kind of Natural Ordering. So we need to know what is the natural ordering of Employees.
Maybe the natural ordering of employees is by name, maybe by salary, … I don’t know. This depends on the domain of the application. In a company, I think, employees have a unique identification number, maybe that is a good candidate to implement total ordering. So, let’s modify our Employee class:

struct employee { int id; string name; float salary; };

Now, let’s finalize our less-than-operator:

bool operator<(employee const& a, employee const& b) {
    return a.id < b.id;
}

Now, we have an Employee class with a natural ordering, by id, that satisfies the TotallyOrdered concept (remember, we are ignoring the points 1 and 3).

But, what if we want to know who is the lowest paid employee, and then raise his salary. Should we modify the less-than-operator to compare by salary?

bool operator<(employee const& a, employee const& b) {
    return a.salary < b.salary;
}

Is it OK?
No, we are imposing a default un-natural ordering to employee’s, it is not the right way to do it.

Changing the Employee’s natural ordering is not an option, so, we need another min function, one that takes a relation as parameter.
Let’s do it in the old-unconstrained-way (wrong way?), that is, without Concepts:

//Note: It compiles, but is incorrect, still, be patient!
template <typename T, typename Comparator>
T const& min(T const& a, T const& b, Comparator cmp) {
    if (cmp(a, b)) return a;
    return b;
}

Now we can write code like the following:

struct salary_comparator {
    bool operator()(employee const& a, employee const& b) const {
        return a.salary < b.salary;
    }
};

void usage_with_employees() {
    employee e1 {1, "John", 5000.0f};
    employee e2 {2, "Peter", 6000.0f};
    employee e3 {3, "George", 4500.0f};
    employee e4 {4, "Frank", 5000.0f};

    // using natural employee ordering (by id)
    employee m = min(e1, e2);

    // using another (unnatural) ordering
    employee m2 = min(e1, e2, salary_comparator{});

    // using another (unnatural) ordering, with lambdas   
    employee m3 = min(e1, e2, [](employee const& a, employee const& b){
              return a.name < b.name; } );
}

But so far, I have not mentioned anything that an experienced programmer does not know, the use of predicates (comparators) is a common thing in practically all programming languages.
What most programmers (and existing implementations) forget is to specify the semantics of the predicate.

So, what are the semantic requirements?
What is Comparator?

Comparator is a Relation, that is, a binary Predicate. What kind of relation?
It is an ordering. What kind of ordering?
Is it a total ordering relation? Well, let’s check it:

Remember, a Relation r is a Strict Total Ordering if: For all a, b and c in the domain of the r, the following must hold:
Transitivity: if r(a, b) and r(b, c) then r(a, c)
Trichotomy: only one of the following holds, r(a, b), r(b, a) or a = b
 

It’s easy to prove that the transitivity axiom holds so I will skip it; but, what about trichotomy? Let’s prove it with an example. Given our previous defined employees:

employee e1 { 1, "John", 5000.0f };
employee e2 { 2, "Peter", 6000.0f };
employee e3 { 3, "George", 4500.0f };
employee e4 { 4, "Frank", 5000.0f };

And our salary_comparator, here called r in order to abbreviate it:

  • Take e1 and e2: According to trichotomy: only one of the following holds, r(e1, e2), r(e2, e1) or e1 = e2
    What is the result of r(e1, e2)? r(e1, e2) means e1.salary < e2.salary, which means: 5000 < 6000, so it holds. The other two propositions are false (intentionally omitted), so trichotomy holds in that case.
  • Take e1 and e3: Following the same analysis,  r(e1, e3) means e1.salary < e3.salary, which means: 5000 < 4500, so it doesn’t hold. But r(e3, e1) means … 4500 < 5000 which is true, and the last proposition is false (again, intentionally omitted), so trichotomy holds.
  • Now, take e1 and e4: Following the same analysis, r(e1, e4) and r(e4, e1) are both false, so, the proposition e1 = e4 have to be true if we want trichotomy holds.
    Is e1 = e4 true?
    No! because e1 is not equal to e4, they are differents employees, they are not the same.

Then, the trichotomy axiom does not hold, that is, the salary_comparator relation is not a Total Ordering on the Employee Set. This means that Total Ordering is too restrictive.

So, what kind of ordering relation should be our Comparator?

Partial Ordering? No, we saw in Part1 that Partial Ordering is too weak to define min.
We need something in between Partial and Total Ordering: what we need is called Weak Ordering[1].

Roughly speaking, weak ordering says that if r(a, b) and r(b, a) are false, then, a and b are equivalents.

So, let’s modify the min function to introduce weak ordering:

//Note: yes! you guess it, it is incorrect, still!
template <typename T, StrictWeakOrdering Cmp>
   requires SameType<ArgumentType<Cmp>, T>
T const& min(T const& a, T const& b, Cmp cmp) {
    if (cmp(a, b)) return a;
    return b;
}

The code above means that we have a function called min, that takes two formal parameters, a and b, both of the same type, called T.
The funcion has a third formal parameter, cmp, that models the concept called StrictWeakOrdering. The “requires” clause means that T (the type of a and b) and the argument type of the Comparator (Cmp) must be the same.

Well, in this article I explained what Weak Ordering means and why it is important, I want to end it with a quote from Alex:
“Mathematicians are happy with Total and Partial ordering. But most of them don’t know what is Weak Ordering. It is not a common term in mathematics but it is essential in computer science, because when we want to order things, we want to order by something. For example by social security number, by name, by age”.

In the next article, finally, I will tell you what are the mistakes that remain to be addressed.

You can get the complete source code on my Github repository.


References

[1] For a formal definition of Weak Ordering see:
http://www.elementsofprogramming.com/eop-concepts.pdf

About these ads

2 thoughts on “Writing min function, part 3: Weakening the ordering

  1. I hope you introduce projections next to show how to reuse std::less with id and salary. It would be also nice if you cold mention variadic versions of min: min(a,b,c, std::less(), proj).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s