Writing min function, part 2: Understanding Concepts

This is the second article of the series called “Writing min function”.

I want complete the min function and fix the mistakes mentioned in the previous post. But first, we have to understand Concepts, so let’s review the last version of the function with its requirements.

// Requires:
//  The type of a is equal to the type of b, and it is called T,
//  and T is TotallyOrdered
min(a, b) {
	if (a < b) return a
	return b

Here we specify that:

  • the formal parameters a and b are of the same type, and we called this type: T.
  • T models the concept called TotallyOrdered.

“A type models a concept, if the requirements expressed by the concept are satisfied for this type”

So, let’s review the formal definition of the TotallyOrdered concept:

TotallyOrdered(\texttt{T}) \triangleq \hspace{37mm}\texttt{//line1} \\  \hspace*{13mm} \texttt{Regular(T)} \hspace{50mm}\texttt{//line2} \\  \hspace*{7mm} \land <\texttt{: T x T} \rightarrow \textnormal{bool} \hspace{30mm}\texttt{//line3} \\  \hspace*{5mm} \land total\_ordering(<) \hspace{36mm}\texttt{//line4}

This reads as:

  • line1: A type T models the TotallyOrdered concept if:
  • line2: The type T also has to model the Regular[1] concept. This means that TotallyOrdered is defined in terms of Regular.
  • line3: A procedure less-than-operator (<) with the signature: T x T -> bool, must exist. This is the syntactic rule that allows us to write things like: a < b
  • line4: This is a semantic requirement, meaning that the less-than-operator procedure has to be a Total Ordering relation.

But… remember that there are two kinds of TotalOrdering.
Do we mean Reflexive or Strict TotalOrdering? Because it would be one or the other.

Let’s review the difference with examples:

  • An example of Reflexive Total Ordering is the \leq relation on the Natural numbers set, or in other words, (\mathbb{N} , \leq ) is a Reflexive Totally Ordered Set.
    That is, for all a, b and c in \mathbb{N} , the following must hold:
    Transitivity: if a \leq b and b \leq c then a \leq c
    Antisymmetry: if a \leq b and b \leq a then a = b
    Totality: a \leq b or b \leq a

    (\mathbb{N} , \geq ) is another example of a Reflexive Totally Ordered Set.

  • An example of Strict Total Ordering is the \textless relation on the Natural numbers set, or in other words, (\mathbb{N} , \textless ) is a Strict Totally Ordered Set.
    That is, for all a, b and c in \mathbb{N} , the following must hold:
    Transitivity: if a \textless b and b \textless c then a \textless c
    Trichotomy: only one of the following holds, a \textless b, b \textless a or a = b

    (\mathbb{N} , > ) is another example of a Strict Totally Ordered Set.

Exercise 1: Prove that
a. \leq is a Transitive relation
b. \leq is an Antisymmetric relation
c. \leq is a Total relation
on \mathbb{N}
Exercise 2: Prove that
a. \textless is a Transitive relation
b. \textless obeys the Trichotomy law
on \mathbb{N}

So, we have four options with which the TotallyOrdered concept could be defined: \textless , \leq , > , or, \geq . Whatever we choose is a right decision, but we have to choose.

Exercise 3: Do you know why any of the four options is a right choice?

I’m lying, actually we will not choose anything, the TotallyOrdered concept is defined using \textless , but here I will show the thinking behind the choice.

We have two choices to make:

  1. Less… vs. Greater…: \textless or \leq vs. > or \geq
  2. Reflexive vs. Strict: \leq or \geq vs. \textless or >

As we know, for 1, Alex has chosen Less…. The rationale for his decision is simple: Counting!
\textless is the natural order of natural numbers. Why? Usually we count in ascending order, it is the natural way of counting.

Having chosen Less… then, we have to chose between Reflexive (\leq ) and Strict (\textless ).
Alex has chosen Strict (\textless ) and his reasoning is: “It is one character less” (len(‘<‘) < len(‘<=’))
But maybe you could think: “This is not a good reason”.
The Alex’s answer is: “Well, we can choose either because they are equivalents!, then, you could use any decision procedure, such as, fewer typing”
Finally, another fundament: “Mathematicians consistently use \textless in their books as the primary ordering, when they talk about, for example, Totally Ordered Fields they write all the axioms in terms of \textless

Summarizing, the choice is to use LessThan that is Strict, so we use \textless .

Well, now we understand what we mean when we use the TotallyOrdered concept, but  this post is ended and we haven’t written any new code.
You must be thinking: “Anyone knows how to write the min function without having any knowledge about abstract algebra”.
The Alex’s answer is: “Yes, they may know how to write it, but they implemented it incorrectly time and time again. How I know that? Because I was one of them.”

And this is mine: “Remembering some mathematics doesn’t do any harm”

In the next post I will write some code. Be patient 🙂


The Series


[1] Regular is another concept, maybe the most important one, I will cover it later, but for the moment we will ignore it. If you want to see its definition, see http://www.elementsofprogramming.com/eop-concepts.pdf [page 1]



Writing min function, part 1: The rise of Concepts

This is the first in a series of articles in which I want to transmit what I learned (or what I think I learned) from the books, papers and lectures of Alexander Stepanov.

These are the lessons that Alex gives us, and I want to show them in this series:

  • Specify our algorithms correctly
  • Programming must be based on a solid mathematical foundation
  • Designing our API’s consistently
  • Not always the library implementations provided by the programming languages we use are correct, even though they are designed by “experts”.
  • The concept of Stability
  • Generic programming, of course!

And… the following lesson is mine:

  • Please don’t blindly accept what it is expressed on this blog. In
    case of doubt you should go to the source, the Elements of Programming
    book [1] 🙂

In this article I want to avoid using any programming language, I want to focus on the algorithms and the specifications. In subsequent articles, I will implement what we learned using several mainstream programming languages.

Writing min

I will try to write the function min, that is, a function that returns the minimum of two things.

At this time you may be wondering, this guy is writing an entire blog post about a two-line function, is this serious?
The answer is yes. As Alex says, “Simple things are beautiful”, and believe it or not, we can learn a lot in the process of writing min.

The objective is to learn to correctly determine what are the requirements that a function must impose on types used in it.

“It is better to design our Components (algorithms and data structures) not in terms of concrete types, but in terms of requirements on types expressed as syntactic and semantic properties”

Alex calls a collection of requirements a Concept[2].

Despite having no support for Concepts in programming languages, he has been using them for decades, not in code, but in his mind and in the documentation of the components developed by him [3].

First Attempt

Well, let’s start writing the specification and then, the code:

Spec: Given two objects[4], a and b, return the smaller of both.

//Note: Naive min function in pseudo-code. Warning: contains errors.
min(a, b) {
	if (a < b) return a
	return b

The above function is written in pseudo-code (which looks like a mix between C and Python), it has some flaws, but we will see them later.

The most important question is… What are the requirements of min function must impose to the arguments a and b? That is… Which are the Concepts?

For some programmers, especially those advocates of duck-typing, imposing requirements to arguments may be something uninteresting. They simply use the arguments in the function body, and they hope to at least get a runtime error.

I strongly disagree!

“Even if we do not have Concepts in the language, they should exists in our mind. You have to learn to think in terms of Concepts whichever language you use.”

Forget for a while about programming languages, let’s see what the requirements are. The problem arises from this code snippet

a < b

What does this mean?

Someone could say that the requirement is that arguments a and b must be compared using the less-than-operator.

But this is just a syntactic requirement, we have to go further in order to correctly specify our function. We need to include semantics in our type requirements! But… how to do it?

Mathematics to the rescue!

What is the less-than-operator?

It is a way for comparing two objects, returning a boolean value.
Is this enough for defining min function?

No, and to ilustrate that, see what happened if the less-than-operator is defined this way:

//Pseudo-code for less-than-operator
less_than_operator(a, b) {
	if ( is_even(system_time().seconds) ) return true
	return false

This function returns true if the number of seconds of the system time is even, otherwise returns false. With this code I want to emphasize that the less_than_operator could be defined using a random behaviour, but we need to define an specific behaviour.

Mathematically the less-than-operator is a Relation [5]. A relation is a binary Predicate[5].

That is, a predicate that takes two parameters of the same type.
“If you look of two things, is either true or false. The relation holds, or not.”
The difference between the code above and a relation is that the relation is considered a FunctionalProcedure[5], that is, a function in which by replacing its inputs with equal objects results in equal output objects.

But the relation concept is too weak, we need a stronger concept: Ordering.

“What is an ordering? What do mathematicians call ordering?

The only absolute rule for ordering is the requirement of transitivity[5].
A relation is transitive if, whenever it holds between a and b, and between b and c, it holds between a and c.
A transitive relation is the most basic notion of ordering, but it is still too weak for our needs.”

Let’s review what kinds of Ordering Relations exist:

  • Partial Ordering: A Partial Ordering is an ordering relation in which not every pair of elements need to be related.
    “The canonical example of Partial Ordering is the Subset Relation
    Subset are ordered, one subset could be a Subset of another subset, for example, the subset {2, 4} Is a Subset Of the subset {1, 2, 3, 4}.
    But it also happens that there are subsets which you could said nothing about, for example, given {2, 4} and {3, 5}.
    Which one is greater? Which one includes the other?
    It is not defined!
    We have two kinds of Partial Ordering:
    Reflexive Partial Ordering (or Non-Strict Partial Ordering): A relation is a Reflexive Partial Ordering if it is transitive, reflexive[5] and antisymmetric[5].
    Strict Partial Ordering (or Non-Reflexive Partial Ordering): A relation is a Strict Partial Ordering if it is transitive and ireflexive[5] (it is also asymmetric[5], but this axiom is implied by irreflexivity and transitivity)
  • Total Ordering: a Total Ordering is an Ordering Relation in which any pair of elements in the set of the relation are comparable under the relation. Total Ordering is a specialization of Partial Ordering.
    Real numbers ordered by the less-than relation (<) (also Rational, Integers and Natural numbers)
    – The letters of the alphabet ordered by the natural dictionary order.
    We have two kinds of Total Ordering:
    Reflexive Total Ordering (or Non-Strict Total Ordering): A relation is a Reflexive Total Ordering if it is transitive, antisymmetric and total[5]. (it is also reflexive, but is implied by totally)
    Strict Total Ordering[5] (or Non-Reflexive Total Ordering): A relation is a Strict Total Ordering if it is transitive and obeys the trichotomy law, whereby for every pair of elements, exactly one of the following holds: the relation, its converse, or equality. (It is also irreflexive, but this axiom is implied by the trichotomy law)

(Note: There are more ordering relations, but we will see them later)

Writing min using Concepts

Well, now we know about ordering relations, let’s look at how we can use them to specify the min function.

But first, what should we use? Partial or Total Ordering?

“If our relation is the Subset relation on a set, then, min and max of two sets doesn’t make sense.”

Then, Partial Ordering is too weak, because the relation doesn’t hold for every pair of elements of the set.

We need to use Total Ordering for define the requirements of min, let’s do it:

// Requires:
//  The type of a is equal to the type of b, and it is called T,
//  and T is TotallyOrdered[5]
min(a, b) {
	if (a < b) return a
	return b
// Note: the implementations still has errors.

Note that the requirements were expressed as code comments. Later we will see what the programming languages provide us to express them as code.

Well, this is enough for a single post.

In the next articles of the series, we will:

  • complete and fix the errors of the implementation of min
  • write the max function
  • refine the requirements of min and max
  • implement them in real programming languages
  • analyze the functions provided by popular (and not so popular) programming languages.

Stay tuned!



Thanks in particular to the following for their feedback to improve this article: Mario Dal Lago, Andrzej Krzemienski, Dean Michael Berris, Javier Centurión, Alejandro Santos, Ezequiel Reyno.


The Series


[1] Elements of Programming of Alexander Stepanov and Paul McJones, http://www.elementsofprogramming.com
[2] Concept definition: Stepanov and McJones [2009, page 10]
[3] SGI’s STL using Concepts in Documentation: https://www.sgi.com/tech/stl/min.html
[4] Object definition:
The definition used in this article has nothing to do with an OOP-like definition of object [6].
The definition used here is a practical definition of what an object is:
“Object is a sequence of bits in memory” or
“Object is a value residing in memory”
See Stepanov and McJones [2009, page 4] for a complete definition.
[5] See Appendix A
[6] Object-Oriented Software Construction (2nd Ed) by Bertrand Meyer [1997, page 1198]


Appendix A: Definitions

Some of the definitions presented here are based on: http://www.elementsofprogramming.com/eop-concepts.pdf

Relation(\texttt{Op}) \triangleq \\  \hspace*{13mm} HomogeneousPredicate(\texttt{Op}) \\  \hspace*{5mm} \land \texttt{Arity(Op) = 2}


HomogeneousPredicate(\texttt{P}) \triangleq \\  \hspace*{13mm} Predicate(\texttt{P}) \\  \hspace*{5mm} \land HomogeneousFunction(\texttt{P})


Predicate(\texttt{P}) \triangleq \\  \hspace*{13mm} FunctionalProcedure(\texttt{P}) \\  \hspace*{5mm} \land \texttt{Codomain(P) = bool}


property(R : Relation)
transitive : R
r \mapsto (\forall a, b, c \in \texttt{Domain(R)}) (r(a, b) \land r(b, c) \Rightarrow r(a, c))

property(R : Relation)
refexive : R
r \mapsto (\forall a \in \texttt{Domain(R)}) (r(a, a))

property(R : Relation)
antisymmetric : R
r \mapsto (\forall a, b \in \texttt{Domain(R)}) (r(a, b) \land r(b, a) \Rightarrow a = b)

property(R : Relation)
irreflexive : R
r \mapsto (\forall a \in \texttt{Domain(R)}) (\lnot r(a, a))

property(R : Relation)
asymmetric : R
r \mapsto (\forall a, b \in \texttt{Domain(R)}) (r(a, b) \Rightarrow \lnot r(b, a))

property(R : Relation)
total : R
r \mapsto (\forall a, b \in \texttt{Domain(R)}) (r(a, b) \lor r(b, a))

property(R : Relation)
total_ordering : R
\textnormal{r} \mapsto \textnormal{transitive(r) } \land
\textnormal{ (} \forall \textnormal{ a, b} \in \texttt{Domain(R)} \textnormal{) exactly one of the following holds: r(a, b), r(b, a), or a = b}

TotallyOrdered(\texttt{T}) \triangleq \\  \hspace*{13mm} \texttt{Regular(T)} \\  \hspace*{7mm} \land <\texttt{: T x T} \rightarrow \textnormal{bool} \\  \hspace*{5mm} \land total\_ordering(<)


For definitions of: HomogeneousFunction, FunctionalProcedure, and Regular, see http://www.elementsofprogramming.com/eop-concepts.pdf [page 1]