Impossible

From APIDesign

Revision as of 20:04, 19 October 2014

Explaining something is impossible, is well, impossible. Or at least almost impossible as following few stories show.

You Are the Expert!

Following viral video demonstrates the principle:

You are the expert! Can you do it? And don't tell us it is impossible, as that can only be explained as your own incapability.

Finite-state Machine

This story requires you to understand what a Finite-state automaton is and how it differs in capabilities from a pushdown automaton or at least from Turing machine - e.g. classical computer. This kind of knowledge should be approachable to every expert who studied computer science, or who studied lingustics and knows who Chomsky and his hierarchy is. I heard the story when I was studying MatFyz by Michal Chytil, who at the time was not only computer scientist, but also partner of Anderson Consulting in our country and his stories about business vs. science relation were absolutely revealing.

Imagine your are an expert in the area of Finite-state automatons. Your great reputation lead another potential customer to you and you are being asked to create a new Finite-state automaton that will:

Recognize words composed from 0 and 1 alphabet letters.
Accept words that start with some number of 0 and are followed by the same number of 1.
Reject all other words.

Your new automaton should then accept word like "01" or "000000000111111111" and reject words like "10" or "00010" or "001". What should you say to such customer?

The right answer is to say: "It's impossible!" Enough to read description of pushdown automaton to understand why, but of course, your customer is clueless and won't bother. Even if you try to explain what the problem is, you are only going to be seen as incapable. Moreover there is another company specialized in construction of Finite-state automatons and when your customer visits them, they (as good business men) say: "Of course, we'll build the automaton!"

Customer gets his machine and is happy. Competing company is happy too. Only your expert reputation is being damaged. But you know the automaton cannot work! So you visit the customer and ask for permission to use his automaton for a while and yes, after a little bit of time you find a word that is accepted, even it should not be. It is not a simple word, it has tens of zeros at beginning and even more ones at the end. But you'd done it! Satisfied you run to the customer to tell him, it is all a fake.

Customer is a bit worried and contacts the supplier of the machine, who sticks to the business note and admits there is a bug in his automaton which he is going to fix. In a few weeks a new automaton, ten times bigger than the old one, is being deployed to the customer and it fixes the so called bug: the incorrectly accepted word is not being rejected. Happiness all over. Except in your camp: you know it is just another bigger fake. It is impossible to create such finite automaton!

Hurrying to save your reputation, you ask the customer again for a permission to inspect the automaton. You study it for weeks and after that you finally find another incorrectly accepted word: this time is starts with thousands of zeros followed by even more ones. Exhausted, but happy you visit the customer. He finally listens to you and is ready to accept that the competing company is a gang of ignorants. But he still may not get it:

"OK, now I see the other company can't create the finite-state automaton properly. Can you please build it for us?"

Your expert credit is back. But the fact that something is impossible is somehow not getting through. What will be your answer this time?

NetBeans Threading

Once upon a time, probably slightly after year 2000, NetBeans had enormous problems with deadlocks. Not surprisingly. Swing is single-threaded, but we were running a lot of tasks on background and they were competing for resources (like the Swing dispatch thread, or their own locks, etc.). My boss asked me to fix this.

Yes, I was the expert - I knew about deadlock conditions and was aware that it is enough to make sure just one of them is not true and we will have a deadlock-free system. Yet I also remembers my lectures from MatFyz where we were informed that there is no coherent theory to drive development of deadlock-free system. Especially if you have a system composed from independent modules, they may be deadlock-free themselves, but when you assemble them together a deadlock can still appear.

I did what experts do. I said: "It's impossible!" and explained my reasoning. Looking back and reminding myself of the finite-state automaton story, it was no surprise my boss didn't listen. I lost my credibility as an expert and he selected somebody else to make NetBeans deadlock free!

As a result we got a detailed write up describing the state of locking at that time (it was really bad) and suggestions to modify state under write-lock and deliver events under read-lock. For a while it worked OK (when the code was new), but then it turned out this style is actually a source of major hard to solve deadlocks and long pauses when rendering the UI. Again I acted as experts do, I seeked for a way to eliminate deadlocks - but not due to a master plan, but through a hard work. I learned how to simulate any deadlock in a unit test and only then fix it. As a result the number of deadlocks started to decrease. Previously we fixed something, without even having a reproducible case and then the deadlock could reappear. With a test, we could be sure we prevent such kind of deadlock for once and ever.

TBD