Why Gödels incompleteness theorem should be software engineering 101
I am a developer. That’s why I know how us folk think. We want clean and nice solutions for problems, because that’s what we do best: provide elegant programs that solve actual everyday problems. We also tend to overrate elegancy. Especially in web development -my field of expertise-, when projects and programs are relatively small for relatively small budgets and always with end results that have a short life span, we think about reusability and tend towards abstract and generic solutions that provide more than a solution, it provides a way of life, progression for the industry as a whole, a solution to even more problems the client nor project manager ever thought of or could even imagine they would ever encounter. We are smart, we know what problems they will face eventually so we prepare them for this. Even more so, we prepare our solution for this, so ultimately the only thing we have to do is flick a switch from now on, and everything is working for everything and we never have to write one line of code again. From now on all we have to do is configure. Which isn’t like coding. At all. You know the feeling, right?
The cake is a lie
In practice, the solution for those problems is never enough, neither to satisfy our bloodlust, nor to satisfy the need for a mother of all solutions. What if another client comes and would like more or less the same thing, but just slightly different? Should we introduce an extra configuration parameter? Should we abstract the different behaviors into different trees of inheritance in our object model? Should we try out new language features, such as mix-ins, functional programming, event models, …? Wait, what if another client walks in and wants a tool that can manage such configuration? Should we make that tool, so that next time we only have to push a button and another slightly modified reincarnation of the same application will roll out? I heard something about DSL’s, that might be cool! Well do it with a JSON REST service and we’ll become our own SAAS provider...
Yes. But also, not really. And also: no. Repeat like a mantra: KISS and YAGNI.
The system is incomplete
Every broader solution introduces new problems. We cannot figure out all problems that will come on our path. We simply can’t. We can have a hunch, and for experienced developers this hunch usually is pretty close to the outcome, but we don’t really know. And Gödel proves this in his first incompleteness theorem.
Wait, what? A guy from the early previous century knew this already and no one told us?! Yes. I’ll try to clarify it as simple as I can. Let’s start with what problem it tries to point out. The outcome of the theorem basically is that if you say “We have a set of rules, and this set of rules is complete for every problem it tries to solve”, it contradicts itself, and if it contradicts itself it cannot be true.
Hm, that seems an assumption, doesn’t it? Fair enough. Let’s state it like this: say, there can not be a set of rules that is complete. If that is true, then we’re done. If that’s not true, then it must be true that there is a set of rules that is complete. But that one rule, the one that says that it’s complete, is not part of the set of rules. Right? OK, let’s make it part of the set of rules, that would help. So we state: there can be a set of rules that is complete, but it needs this one tiny amendment rule to say it is complete. Oh, wait. We’re back at inconsistent again….. Because in fact it states that it isn’t complete …. crap ...
Are you with me yet? Just for the sake of clarity: let’s say we know that 1 = 1. We introduce an operation on this, and if we repeat this number twice and count the sum, we call it 2. So 1 + 1 = 2. We would also agree on 1 + 1 + 1 = 3. It can be very easily deduced that now 1 + 2 = 3, and 2 + 1 = 3. Based on this principle, we can describe and agree on all kinds of rules. For example, multiplication is repeated addition: 3 * 4 = 12, because 3 + 3 + 3 + 3 = 12 (did you count the number of 3’s there?). Same goes for exponentiation, 3 to the power of 4 = 81, because 3 * 3 * 3 * 3 = 81. And so forth and so on.
We have now built a set of rules in which we can operate. We do all kinds of crazy stuff with these (and a few other) axioms. Pretty much everything that has anything to do with computing, which is realistically nearly 100% of our economies, is based on this. So it works. It works because it’s consistent. We can go back from any kind of arithmetic problem and reduce it ultimately to 1 + 1 = 2. But it is incomplete. 1 + 1 = 2 because we say so, not because theres no way around it. We agree on this, because it works, but we do not agree on it because there’s anything to validate it.
Think about it.
There really isn’t.
Either inconsistent, or incomplete. This means that we will always need some kind of outside factor to validate any system of rules. And this goes for all systems and any system. Because that’s what systems are: sets of rules to operate in.
Provability of any rule isn’t necessarily what makes the rule worth anything. There is no fundamental problem in defining some axioms, as long as we can all agree that these are, in fact, just that, axioms: there is no point in discussing them. We all simply agree on them being true. That’s, according to wikipedia (I did my research1), what the word axiom in ancient Greek actually translates best to: “something we all agree on to be evident”. Remember we previously agreed on the truth of the statement that 1 = 1? That is an axiom. It is evident that we can agree on that. There needs to be no discussion. But we can’t prove it. In other words, you either incorporate a new rule in your system to make it more complete, or you accept it as being inconsistent.
101
How would this apply to program design? It is simple. You should accept the axioms of any system as the axioms, and not dig deeper to find out whether the axioms are actually derived from other axioms. For example: if one of the axioms is that a client should get a website that has some content, it does not necessarily mean that they would need a CMS to manage that content. That’s not part of the problem domain, and therefore not part of the solution. This case is pretty obvious and of course a scenario you would discuss with your client. But the deeper you will dig to find out what the scope of your problem is, the more you should think about the fact whether it would contribute to solving the problem rather than introducing new ones. Moreover, you will encounter possible problems that you would not discuss with your client per se, because they might not understand or oversee what the consequences might be. Being an artisan of the modern world, you’re out to give the client the best possible solution which means you have thought of solutions for things they have never thought of. So, we tend to widen the scope.
Let me give you an example. Say, we have a product web site. People need to be able to gather products, and ask for a quotation. These products come in different forms, or product types. We know that there are only three types of products. It will come in handy that all of these three types have different behaviors in different situations. For example: the price of one product is calculated based on different properties than another. In an object oriented model this could translate to a base class Product and two subclasses implementing the getEffectivePrice() method differently. We will use a relational database to store the products in. Where and how will we store this type of product in the database? Normalization would suggest that a different entity “product type” should be stored, and all products would have a many to one relation to these product types. Let’s use a table for this, and put a class name (an OO representation of the product) in the table, so we can differentiate what class should be instantiated for each of the rows in the product table, and that way we can alter their behaviors per instance. If we think about it properly, the calculation rules should in fact be a separate entity, so each product type can use their own set of rules and at the same time reuse others. This way, the system does not have to change to add more product types. All we have to do is make sure there are CRUD interfaces for these, and we probably use an admin generator for our entities anyway. So, we decide not to use an inheritance model, but use one Product class, which has a getEffectivePrice() method, which will in turn use all associated calculation rules from the product type and calculate the price. The calculation rules in turn are defined in the database as a simple DSL, e.g. a formula.
Seems like a decent solution, right? It might a bit overdone, but it is decent and future proof. So we started with a fixed set of axioms. One is that there are only 3 product types in the world, and these product types have their own price calculation rules. What we decided was that it is feasible to assume that there will be more product types and that all we need to make the system more generic and thus flexible is a data model around the axiom that there could be any number of product types and any number of calculation rules. We diverted from our axioms. This widening of scope went from an implementation of about 15 lines of code:
#!java
class Product
{
/**
* Returns the effective price the customer should ultimately pay
*/
public int getEffectivePrice() {
switch (type) {
case TYPE_FOO: // the shipping costs for type “foo” is included based on their weight.
return weight * SHIPPING_COST * (1 + TAX_PERCENTAGE/100) * price;
case TYPE_BAR:
return price * (1 + TAX_PERCENTAGE/100);
case TYPE_QUX: // type “qux” is tax free
return price;
}
throw new ProductConfigurationException(“The product has an invalid (unknown) type \”” + type + “\””);
}
}
To a solution where we would need:
- A separate Type entity
- CRUD interface for that
- A separate CalculationRule entity
- CRUD interface for that
- A DSL to calculate the prices, including a parser/compiler or interpreter.
So that went from the 15 lines of code that are testable in no more than 4 test cases, to a whole set of test cases, classes and libraries that will cost about a gazillion times the money.
Where did it go wrong? We wanted the elegant solution, because a switch statement in an OO environment usually triggers the idea of polymorphism. You do not need the switch if you can abstract common behavior in a the class in separate types. This causes the system to be more complete, as it makes it more generic.
"But... complete and generic and reusable is... cool..." snif
Don't strive for completeness. There is no such thing. Accept inconsistencies as part of the system. Completeness does not validate the system. It's axioms do. As long as we all agree on the axioms, the system is fine.
Kurt2 would agree.