I want to fix programming

(The SB series, part 1 of 7)

Programming is broken. Completely broken. The very way we write code today is just so broken that it makes you want to puke. I’ve been saying for years that I hate programming. I am and have been a fulltime developer for over 20 years, I don’t regret it, and I still love what you can do with programming. Still, I hate programming.

The way code is written is just braindead. At each step of the process, you can crash the program, be it by filling up all available memory, accessing a stray pointer or reference, or entering an infinite loop. No doubt programming feels like walking barefeet in a floor filled with broken glass. One tiny inch out of the right place, and bang, you nearly lose one of your toes.

Every step of the way, in every statement, line of code, function call or sequence-point, if you want to write good code, you need to think about all the different possible states of the whole program. This is invisible and impossible to define. Provably. Always. In all existing languages. That’s the reason 100% code-coverage unit-testing doesn’t guarantee bug-free code, and it never will. This is also the reason bad programmers don’t become good: they just can’t think about all those possible cases in a structured way.

(By the way, this only gets about a thousand times worse with multithreaded code – so it’s not getting better, it’s getting worse.)

The problem is that the fundamental way that code is written is wrong. It’s just wrong. You write a bunch of instructions, step by step, which supposedly result in a given wanted state. But each step is separate from all others, it is only understood by the compiler/interpreter separately, and it’s almost easier to screw things up than to get them right.

I thought for a long time that functional programming could be the solution, and studied it in detail. Lisp. Haskell. The Lambda calculus. The functional approach brings indeed several improvements over regular imperative or object-oriented programming. But still it’s not the solution. It is still composed of many discrete simple steps that excruciatingly calculate the output.

What is the key thing that is wrong with code? The fact that you don’t express what you want. You express what steps have to be taken. Imagine telling your pal to grab you a beer from the fridge, step by step, with each step being robotically-rigid and with very little regard for context.  It would be excruciating. And prone to catastrophic failure. Exactly like code is.

Libraries help with this phenomenon, but they are only shortcuts for higher-legoal-specific needs. They don’t really fix it.

There was recently a very interesting post by John Carmack about static code checking, where he cited a great tweet by Dave Revell on code checking:

“The more I push code through static analysis, the more I’m amazed that computers boot at all.”

A vision

So, how should code look? Let’s take a simple example: sorting a list. Say you have an input list, let’s call it, ahem, input. Assume it has several elements. And now we want to compute a new list, called output, containing the same elements that the input has, but sorted in ascending order. How should we do it?

Traditional methods include bubble sort, quick-sort, shell-sort, insertion sort, etc… these are all algorithms that allow us to sort a list in a way that provably works. For example, bubble sort:

Straightforward enough. But if you write the code to do the sort, you may still make a mistake! What if you forget to set the “swapped” parameter to true when you exchange two elements? Or more typical than that, what if you make an off-by-one mistake with the loop counts?

This is why I say that programming is broken: sorting is a simple concept to grasp and describe, and still, the code to do this is convoluted, and full of traps where you can crash the program or generate wrong output. It’s nuts!

Someone could come up with a functional version of one of the algorithms above, but it would still be very similar: no side effects, but many steps to do all the tasks needed. Recursion may be more elegant than iteration (ahem), but it isn’t fundamentally better.

So, how should the code to sort a list really look like? After many years, I’ve come to the conclusion that it must be something like this (pardon the pseudo-code for a style of programming that doesn’t really exist yet):

Let me try to explain it: the first line of the sort definition says that there exists a one-to-one set of “relations” between elements in the input and output sequences. We will see later how the one_to_one_equal definition achieves this. But this ensures that the input and output list contain the same elements. It defines the space of possible answers.

Second, the key thing, the next line specifies that for each pair of elements in the output sequence, when the first index is lower than the second index in the pair, then the value of the element is less or equal. Which basically states that the output list is sorted. It defines which of the possible answers is the solution.

And it’s that simple. The sort function only specifies WHAT sorting is. Not HOW it is done. It shows the properties of the output and the input, related, and it leaves as an exercise for the compiler to figure out how to get there.

Undoubtedly, there are two key questions here:

  • First, how can the compiler process this? Is it actually possible? In future articles, I will try to show that yes, it is indeed possible, and that the compiler could even be able to figure out the algorithms to get this result.
  • And the second key question is, how applicable is this to more complex problems? I will also try to show that it is indeed applicable to any fully-general programming or computation task, and that such a way of programming can be much simpler, more efficient, and much closer to being failproof!

I had been meaning to save this knowledge to set up a company in the future, but several circumstances have made me rethink this plan. I’d rather share this knowledge now, and see where things go. Watch out for the next articles in the series.

Afternote

We’ll get deeper into this later in the series, but here is a small bite. This one_to_one_equal function would be a “standard library function” in this idealized language, but here it is more or less how it would look, so that you can see the underlying logic:

Let me try to explain it: the first line of the definition says that there exists a one-to-one set of “relations” between elements in the input and output sequences.

The second and third lines state that there is a single relation in “c” that pertains to each element in the input and output lists, thus ensuring the relation is one-to-one. Finally, the last line states that the two elements in each relation are of equal value, ensuring the two lists are the same, just reordered.

My current day job involves Mouinpress (a system to turn WordPress sites into native iPhone, Android, Blackberry and J2ME mobile apps), and ViEmu (a vi/vim emulator for Visual Studio, Word & Outlook, and SQL Server). If you want to help me with my project to fix programming, I’ll be grateful if you have a look, evaluate, and maybe buy or promote either of them’products. Or, since I’m looking for investors, maybe you can help with that!

I’m available at http://twitter.com/jonbho