Archive for the ‘math’ Category

math explained

December 2nd, 2012

I've always found it really painful to read math. Yet I've never really been able to pinpoint why. It feels like using a really horrible piece of software where it's ridiculously hard to figure out what is what and how to do what you want.

Then it hit me. Math notation is a dead ringer for the International Obfuscated C Code Contest. I've always had this unarticulated sensation that when I read math, be it a textbook, a proof, anything with formal notation, I constantly have to decrypt the horrible code into its meaning and store that in memory. Eventually the number of symbols and operators grows to a point where I encounter an out of memory error.

If you've ever looked at what javascript looks like when it comes out of a minifier, you've noticed that descriptive function names and variable names have all been turned into identifiers like "a", "b" etc. Sure, on the web the size of the payload matters. But are mathematicians too embroiled in some misguided quest for Huffman coding?

People criticize c++ because you can overload the operators to mean anything you want. But math is such a cognitive overload of operators that it's worse than any c++. And people who need math to explain something formally routinely redefine operators to mean whatever they want.

You know what else math doesn't have? Scope. It's fabulous reading a paper with that tingling of anxiety because you never know when a symbol defined 10 pages back is about to make a comeback.

So in the end it's all operators and single identifier names in a global namespace, in a word: delightful. Holy cow, I *wish* we had awful Hungarian notation practices, it would improve the code by levels of magnitude. In fact, so many of the tips in the seminal How to Write Unmaintainable Code would be a godsend for math writing.

classes of functions

May 24th, 2009

I decided to finally blog this since I can never frickin remember which is which. Maybe if I write this and draw the diagram it'll finally stick. If not, I'll have something to come back to. To make it more accessible I'll be using a running example: the bike allocation problem. Given a group of people and a set of bikes, who gets which bike?

Partial functions

function_properties_partialPartial functions are pretty self explanatory. All you have to remember is which side the partiality concerns. In our example a partial function means that not every person has been assigned a bike. Some persons do not have bikes, so lookup_bike(person) will not work on all inputs.

Partial functions are common in code: reading from files that don't exist, and of course the ever lurking NullPointerException -- following a pointer to an object that is not live. In haskell, this is where the Maybe monad appears.

Total functions

function_properties_totalNot surprisingly, total functions are the counterpart to partial functions. A total function has a value for every possible input, so that means every person has been assigned a bike. But it doesn't tell you anything about how the bikes are distributed over the persons; whether it's one-to-one, all persons sharing the same bike etc.

Clearly, total functions are more desirable than partial ones -- it means the caller can call the function with any value without having to check it first. Partial functions often masquerade as total ones, by returning a value outside the expected range (which explains the existence of a null value in just about every programming language and data format). In python the value 0, None and any empty sequence (string, list, tuple, dict) all represent null, which makes writing total functions easy.

Bijective/isomorphic functions (forall one-to-one)

function_properties_bijectiveA bijective function (also called isomorphic) is a one-to-one mapping between the persons and the bikes (between the domain and codomain). It means that if you find a bike, you can trace it back to exactly one person, and that if you have a person you can trace it to exactly one bike. In other words it means the inverse function works, that is both lookup_bike(person) and lookup_person(bike) work for all inputs.

Isomorphic functions are found in all kinds of translations; storing objects in a database, compressing files etc. The name literally means "the same shape", so any format that can reproduce the same structure can represent the same data.

Injective functions (one-to-one)

function_properties_injectiveAn injective function returns a distinct value for every input. That is, no bike is assigned to more than one person. If the function is total, then what prevents it from being bijective is the unequal cardinality of the domain and codomain (ie. more bikes than persons).

Another way to understand it is to think of something small being stored in (embedded in) something big. In order to maintain unique output values, the codomain must be at least as big as the domain. GUIDs are an example of this. A GUID generator guarantees a globally unique identifier by picking values from a sufficiently large space. Given a GUID that has been issued, you can trace it back to exactly one object, but you cannot take just any value in the GUID space, because most of them have never (and will never) be issued to anyone.

Surjective functions (many-to-one)

function_properties_surjectiveA surjective function is one where all values in the codomain are used (ie. all bikes are assigned). In a way it is the inverse property of a total function (where all persons have a bike).

Surjective functions are often undesirable in practice, meaning that you have too few resources at your disposal, which forces sharing (threads on a cpu) or rejection (streaming server can only accept so many clients).

The way to think of injections and surjections is not as opposites, but as complementary properties. A function can be both injective (all persons have a unique bike) and surjective (all bikes are used). If so, it is bijective.