# Writing min function, part 1: The rise of Concepts

May 20, 2014

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*[1], 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 [2]

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 try to 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*[3].

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 [4].

## First Attempt

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

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

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:

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*[6]. A relation is a binary *Predicate*[6].

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*[6], 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 [6].*

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

: 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 Non-Strict Partial Ordering): A relation is a Reflexive Partial Ordering if it is*Reflexive Partial Ordering**transitive*,*reflexive*[6] and*antisymmetric*[6].(or Non-Reflexive Partial Ordering): A relation is a Strict Partial Ordering if it is*Strict Partial Ordering**transitive*and*ireflexive*[6] (it is also*asymmetric*[6], 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:

The 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 Non-Strict Total Ordering): A relation is a Reflexive Total Ordering if it is transitive, antisymmetric and*Reflexive Total Ordering**total*[6]. (it is also reflexive, but is implied by totally)[6] (or Non-Reflexive Total Ordering): A relation is a Strict Total Ordering if it is*Strict Total Ordering**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:

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 API provided by some 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

Part 5: Stabilizing the algorithm

## References

[1] Original definition of “Generic Programming”:

David R. Musser and Alexander A. Stepanov: Generic Programming. ISSAC 1988, pages 13-25. http://www.stepanovpapers.com/genprog.pdf

[2] Elements of Programming of Alexander Stepanov and Paul McJones:

http://www.elementsofprogramming.com

Buy it at Amazon

[3] Concept definition: Stepanov and McJones [2009, page 10]

[4] SGI’s STL using Concepts in Documentation: https://www.sgi.com/tech/stl/min.html

[5] Object definition:

The definition used in this article has nothing to do with an OOP-like definition of object [7].

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.

[6] See Appendix A

[7] 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 \\
\qquad HomogeneousPredicate(\texttt{Op}) \\
\quad \land \texttt{ Arity(Op) = 2}$$
```

```
$$HomogeneousPredicate(\texttt{P}) \triangleq \\
\qquad Predicate(\texttt{P}) \\
\quad \land HomogeneousFunction(\texttt{P})$$
```

```
$$Predicate(\texttt{P}) \triangleq \\
\qquad FunctionalProcedure(\texttt{P}) \\
\quad \land \texttt{Codomain(P) = bool}$$
```

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

```
$$\textbf{property}\text{(R : Relation)} \\
\text{refexive : R} \\
\quad r \mapsto (\forall a \in \texttt{Domain(R)}) (r(a, a))$$
```

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

```
$$\textbf{property}\text{(R : Relation)} \\
\text{irreflexive : R} \\
\quad r \mapsto (\forall a \in \texttt{Domain(R)}) (\lnot r(a, a))$$
```

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

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

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

```
$$TotallyOrdered(\texttt{T}) \triangleq \\
\qquad \texttt{Regular(T)} \\
\quad \land <\texttt{: T x T} \rightarrow \text{bool} \\
\quad \land total\_ordering(<)$$
```

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

Share