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 r*elation* 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 o*rdering* is the requirement of t*ransitivity*[5].

A relation is t*ransitive* 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:

: A*Partial Ordering**Partial Ordering*is an*ordering*relation in which not every pair of elements need to be related.Examples:

“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*:

(or*Reflexive Partial Ordering**Non-Strict Partial Ordering*): A relation is a*Reflexive Partial Ordering*if it is*transitive*,*reflexive*[5] and*antisymmetric*[5].

(or*Strict Partial Ordering**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*): a**Total Ordering***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*.Examples:

–*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*:

(or*Reflexive Total Ordering**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*)

[5] (or*Strict Total Ordering**Non-Reflexive Total Ordering*): A relation is a*Strict Total Ordering*if it is*transitive*and obeys the t*richotomy 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 o*rdering relations*, but we will see them later)

## Writing *min* using *Concepts*

Well, now we know about o*rdering 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!

## Acknowledgments

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

- Part 1: The rise of Concepts
- Part 2: Understanding Concepts
- Part 3: Weakening the ordering
- Part 4: Const-Correctness

## References

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.

## Appendix A: Definitions

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

**property**(R : Relation)

transitive : R

**property**(R : Relation)

refexive : R

**property**(R : Relation)

antisymmetric : R

**property**(R : Relation)

irreflexive : R

**property**(R : Relation)

asymmetric : R

**property**(R : Relation)

total : R

**property**(R : Relation)

total_ordering : R

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

## 2 thoughts on “Writing min function, part 1: The rise of Concepts”