Tuesday, July 21, 2009

Five orders of ignorance

The five orders of ignorance, published in a short article in the 2000 issue of the Communications of the ACM, states that "software is not a product, but rather a medium for the storage of knowledge". It then goes on to recognize five levels of ignorance:

  • 0th Order Ignorance (0OI)—Lack of Ignorance.You know, you have the answer.
  • 1st Order Ignorance (1OI)—Lack of Knowledge.You know what you don't know, you have the question.
  • 2nd Order Ignorance (2OI)—Lack of Awareness. You don't know what you don't know.
  • 3rd Order Ignorance (3OI)—Lack of Process.You have no means, or process, for resolving your lack of knowledge.
  • 4th Order Ignorance (4OI)—Meta Ignorance. Not aware of these 5 levels.
Obviously, level 4 is bliss, but reality might come and kick you in the teeth. Level 3 represents agony. Level 2 is bliss and level 1 is just hard work, but at least you can apply the processes from level 3. So we have seen many efforts at level 3, processes and methodologies for resolving your lack of knowledge. One of the methodologies for acquiring knowledge that I have not seen highlighted very much is formal analysis. It's about as rigorous as it gets, highly structured and rather unforgiving.

As an example, I was reading the following article http://www.switchonthecode.com/tutorials/csharp-tutorial-the-lambda-operator . In essence:

public delegate int FoldIntDelegate(int a, int b);

public int Fold(FoldIntDelegate fid, params int[] list){ int result = 1; foreach (int i in list) result = fid(result, i); return result;}

int val = Fold((a, b) => a * b, 1, 3, 5, 7, 9);

A nice, solid, article. I wondered however why the Fold method was not recursive. That's kind of what I would expect when using functions/lambda's, since you have no foreach loops in pure functional programming languages. Obviously, C# is not a pure functional programming language, but you can toy around with it. So writing a recursive version requires you to think about proof by induction. Ah, by going through the formal process of induction you rather quickly figure out that the Fold function above assumes that 1 is the unity for the operation you are applying. Which is true for multiplication, but for

int val = Fold((a, b) => a + b, 1, 3, 5, 7, 9);

that's certainly not true. Fold does not force you to only use multiplication as the operation being applied, since we are passing the operation through the lambda expression. In fact, Fold((a, b) => a + b, 1, 3, 5, 7, 9); will always be incorrect with the above implementation. So you can't just assume that 1 is the unity. Nor can you assume that when not enough arguments are passed for a binary operator, 1 is a correct answer.

Why care? Fold is a public method. Somebody will sooner or later think you can use Fold on operations other than multiplication and before you know it, people wonder why the software developers can't even add a list of integers correctly.

So when you remove the two mentioned assumptions from Fold, the code becomes a little more complicated. Since Fold definitely only applies in it's current form to binary operations (because of the signature required for the lambda expression), you would have to require that at least two parameters are passed to Fold.

Finishing this up, it could look like:

public int Fold(Func aFid, params int[] list)
if (list.Length > 2)
return aFid(list.First(), Fold(aFid, list.Skip(1).ToArray()));
if (list.Length < 2) { throw new Exception("Binary operation requires at least 2 arguments.");
} else { return aFid(list[0], list[1]); }

Ofcourse this could be even rewritten to the point where it's actually required to have at least two parameters of type int and then call a private version of Fold that takes just a list of parameters (with the value of the two parameters of type int concatenated to the front of the list). That would be cleaner since the public contract of Fold then requires you to at least pass two parameters.

An other assumption that Fold makes that might not be clear at first glance is that of an associative operator. The assumption is that (2*3)* 5 == 2*(3*5). For lambda x=> x-y, Fold would give us 6 - ( 3 - 2) = 5. Question is, would you expect fold to return (6-3)-2 = 1 instead?

Obviously, I am taking a small, and excellent, sample of the use of lambda's somewhat over the top, but hopefully the point is clear: (semi- , since I didn't actually write any formal derivations) formal analysis has it's uses.

No comments:

Post a Comment