Mathematical Properties and Programming

In school part of the maths education involved memorizing the definitions for words like “commutative” or “transitive”.  I always did terrible with those memorizations [1], however I’m pretty sure the cause behind my performance was a lack of context.  Trying to investigate maths on my own, I reencountered these words.  My first thought was something along the lines of, “hey these are those words I always missed points on with exams.”  However, I wanted to understand certain maths [2], so I trudged on.  I’m rather glad I did because an important realization struck me once I had finally memorized enough of these definitions:  If you create a programming construct [3] that does not obey a property that it should intuitively have, then when you (or someone else) uses the construct in the intuitive fashion it may malfunction in surprising or hidden ways.

The example that first comes to mind is floating point numbers in most programming languages.  Typically we imagine addition to be associative.  That is to say that a + (b + c) is equal to (a + b) + c.  However, this is not necessarily true for the floating point representation of a number [4].  The effect is that apparently valid looking code that uses floating point numbers may be incorrect, and apparently innocent looking code changes to code that uses floating point numbers may result in correct code becoming invalid.

Of course this doesn’t just apply to programming constructs that are baked into your programming language as a base feature.  It also applies to pretty much any class, object, inheritance chain, function definition, etc that you might end up creating in order to accomplish your goal. 

So far I’ve compiled a list of properties that look like that are important to keep in mind when you’re implementing solutions:

Reflexive

Symmetric

Transitive

Equality Relation (reflexive + symmetric + transitive)

Antisymmetric 

Partial Order (reflexive + antisymmetric + transitive)

Unary / Binary Idempotence 

Total

Injective

Surjective

Bijective

Commutative

Associative

Continuous (in the topological sense)

Monotonic (in the domain theory sense)

Continuous (in the domain theory sense)

Sound (in the type theory sense)

Referential Transparency

Not all of these properties are going to be required (or even a good idea) for every construct you come up with.  But when you’re using a construct like it has one of these properties it better have that property.

[1] - Actually I tend to *do* terrible with all memorizations, but that’s a different story.

[2] - Type theory and category theory (mostly because of Haskell).

[3] - It’s so much worse than just programming constructs though.  It also applies to reasoned arguments, personal philosophies, business procedures, school policies, and the list goes on.

[4] - http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems