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:

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.

Posted in Development | Tagged , | Leave a comment

Building OpenGL SDK: compile error “X11/extensions/XInput.h”

If you get this error:

src/freeglut_internal.h:111:39: fatal error: X11/extensions/XInput.h: No such file or directory

This might save you some time searching for the correct dev packages to install. The package it is in in the Debian repositories is called x11proto-input-dev, but it contains the file XI.h which contains the correct headers freeglut is including. Symlink the file and you’re good to go.

cd /usr/include/X11/extensions && sudo ln -s XI.h XInput.h

HTH :)

Posted in Development, Linux & BSD | Tagged , | 2 Comments

Composer local package mirroring: Press the pedal to the metal.

In my previous blog post, I told you about hosting local package repositories for composer. Me, or to be honest, my colleagues, weren’t too excited about the performance gains. So I decided to dig in a bit deeper.

Read More »

Posted in Development | Tagged , , , , | 8 Comments

Composer: create a local package repository to improve speed

When you’re developing a lot of symfony projects with a relatively large set of dependencies, sooner or later you’ll get annoyed by performance issues. By default, composer uses packagist.org to get package metadata (what versions are available and where to get them from). All packages are part of packagist.org by default, but 9 times out of 10, you’ll only need a fraction of that.

So, to gain performance, I decided to generate a local package repository which only contains the package info for the libraries I regulary use. Read More »

Posted in Development | Tagged , , | 1 Comment

Flow charts in code: enter graphviz and the “dot” language

If you’re like me, you like gui’s as long as they don’t push you in a direction other than your train of thought. Whenever the tool tends to distract you from the task you are performing, you get annoyed. Stuff like “why am I searching for such an over-obvious functionality”, or “why didn’t they think of making the clickable area a bit bigger”, or simply “aaaarggghhh, it crashed on me again”.

Read More »

Posted in Development, Linux & BSD | Tagged , , | Leave a comment

PHP: We are getting slow and sluggish, and we’re lazy and arrogant about it.

In my most recent blog, I wrote about how I feel that too much of the world’s logic is coming onto the shoulders of PHP, these days. Today, I’m will be showing you why and how PHP’s powers could be harnessed better and more. We, as PHP web developers, should be absolutely fully aware that we’re allowing insane amounts of processing power to do too much work when it’s absolutely unnecessary to do so dynamically.

Read More »

Posted in Development | Tagged , | 15 Comments

PHP in the web development world: are we doing it all wrong?

Some thoughts and ponderings on how “the frameworks out there” might not do it just as right as they should.

The UNIX principle applied?

Something that is currently overlooked in a large part of the PHP community is that not all design patterns are necessarily implemented in PHP code. Your webserver can be considered the front controller of your application too. Routes can be defined using your filesystem and webserver configuration. Not everything has to be Object Oriented to be well organised and well structured. To gain perspective, here are some ideas to think outside the box, and not have OO patterns drive you beyond reason.

Read More »

Posted in Development | Tagged , , , | 2 Comments

Tetris in HTML and Javascript

First, I saw the documentary Ecstacy of Order. Then I thought of great things, like building 3D Tetris in HTML5 canvas. I started it, just typing away, of course only Vanilla JS. But after a few hours, having the simple Tetris basics covered, I got bored and stopped.

But wait, there’s still hope! I thought I could write a post about me thinking of awesome stuff, getting the basics working and then never finishing it. So I started typing this post, but halfway through, I decided that the basics are good enough. And that the basics are worth posting too.

Sorry if I disappointed you. Have fun reading the code ;) The gameplay is not that interesting.


  1. The controls are A & Z for rotating, < and > for moving. You can also use your cursor keys if you use Firefox. Didn’t test it in IE, btw. 

Posted in Development | Tagged , | Leave a comment

Symfony2: A two piece puzzle.

If you’re getting started with Symfony2, you’ll get something running pretty quickly. The AcmeBundle contains some of the basic features you’ll need when writing a Symfony2 app. The basics lie in the MVC paradigm, so there is some model (Doctrine ORM), some view (Twig templates) and some controllers.

However, none of that is the real core of Symfony2. The most interesting part lies in two main components of the framework. First, the HttpFoundation component and second, the Service container.

Read More »

Posted in Development | Tagged , , | Leave a comment

Using a .pfx to install an SSL certificate

Got a .pfx file and need to install an SSL certificate with this? Here’s how I did it. You’ll need to extract the signed public certificate (public key) and the private key without passphrase.

Read More »

Posted in Linux & BSD | Tagged , , | 2 Comments