contact
----------------------------

Blog <-

Archive for the ‘programming’ Category

RSS   RSS feed for this category

Subversion svn:ignore propery doesn't (seem) to work? [FIXED]

Say you're trying to set the "ignore" property on something in a subversion checkout like this:

svn propset svn:ignore "foo.pyc" .

Next you do a svn status:

M       foo.pyc

It seems it isn't working. In order to fix this, you must remember to first:

  • Remove the file from subversion and commit
  • svn update all the checkouts of that repository so that the file is gone everywhere!
  • Set the svn:ignore propery
  • Now commit the property change, or svn status will still show it (even in the local checkout)!
  • svn update all the checkouts of the repository

So:

host1$ svn rm foo.pyc && svn commit -m "Remove compiled python code"
host2$ svn update
host1$ svn propset svn:ignore "foo.pyc" .
host1$ svn commit -m "Ignore compiled python code"
host2$ svn update

If you get conflicts because you didn't follow these steps exactly:

host2$ svn update
   C foo.pyc
host2$ svn resolve --accept working foo.pyc
host2$ svn rm foo.pyc
host2$ svn update
At revision 123

That should solve it.

If you want all your subversion problems solved, try this.

Input, state and their relationship to bugs

Why are there so many programmers who don't know what state is, much less the impact it has on programming? Recently I was having a discussion online and some programmers kept misinterpreting everything being said by me and other programmers because they had no or little grasp of the concept of state. This is not the first time I've noticed that, for such an important concept, there are a surprising number of programmers who don't understand the concept and implications of state.

The meaning of state

From Wikipedia:

the state of a digital logic circuit or computer program is a technical term for all the stored information, at a given point in time, which the circuit or program has access to. The output of a digital circuit or computer program at any time is completely determined by its current inputs and its state.

Just to be clear, "all the stored information" includes the instruction pointer, CPU registers/caches and so forth. So if at any given point in time your program is in a while loop or conditional branch, that is also part of the state.

"The output of a digital circuit or computer program at any time is completely determined by its current inputs and its state."… Think about that for a moment, because it is important. Everything that happens from that moment on in a computer program is determined by the current inputs and its state. That means, as long as there is no other input, the output of the program is completely predictable at any time. That's a lot (or rather, exactly) like the pseudo-random number generator in most programming languages. If you know the seed, you can predict every random number that will be produced. Each number the pseudo-RNG returns is the result of its input and its current state.

If programs are that predictable, how come there are still so many bugs in them? Well, for one thing, programs are not that predictable at all.

On the Origin of Bugs

Look at the following example:

a = 5
b = 10
c = a + b

Tell me, how many bugs does the program have? If we assume that the syntax is correct and that each variable can hold an integer number, this program contains zero bugs. Now tell me, how many bugs does this program have?

a = int(file('in', 'r').readline())
b = 10;
c = a + b;

How many bugs? One? Three? Do you know? Because I sure don't. Here's a few I can come up with from the top of my head:

  • The file "in" may not exist
  • The file "in" may not be readable
  • The file "in" may disappear between opening and reading
  • The file "in" may be empty
  • The file "in" may not contain something that can be cast to an integer
  • The system may not be able to allocate more file handles
  • The system may not be able to allocate enough memory to read a line from the file

I could go on, but the point should be clear. We changed only one line in our program, and now there are who-knows how many bugs in our program. Why is that? Because in our first example, the state of the program could never be influenced from outside the program at any time, since there was no input! (Yes, the memory might get corrupt from a random flipped bit or the universe might decide to suspend the laws of physics, but again: let's not get pedantic).

When we write a piece of code, we write that code with certain assumptions. If I write:

while (i < 10) { /* ... */ };

I'm assuming variable 'i' contains some kind of number, which at the start of the loop is smaller than 10, and which during the loop will not suddenly change into, say, an open file pointer. Now if I'm not a total idiot, and I write my code properly, that last thing will never happen. Given a piece of code, it's generally not difficult to make correct assumptions about that code. But making assumptions about input into that code (in this case the contents of variable 'i'), regardless of where it came from (interactive input, the network, the filesystem, passed in as a argument into a function, whatever) is much more difficult and dangerous.

I'm going to make a sweeping generalization: Given that "the output of a digital circuit or computer program at any time is completely determined by its current inputs and its state", and given that a program's current state is determined by its starting state and all the input, and that we can thus disregard the "and its state" part of the first statement... I'm going to claim that

All bugs in a program are a result of the input into that program.

Of course, like I said, that statement is sweeping, and therefor false. But for now, assume it's true and think about the implication of it for a moment, while I correct my previous statement.

Predictable state

Of course, not all bugs in a program are a result of input into that program. Sometimes us programmers screw up, and make mistakes. This is another source of bugs in our programs. Sometimes we're tired, and we make mistakes in the syntax of our programs. Sometimes we don't pay attention, and a certain library works differently than we thought. Such bugs are easily solved. In fact, many can be automatically detected by compilers or asserts or whatever.

Another class of bugs is the one where we make assumptions about the current state of a part of our program, and write new code in accordance with those assumptions. Those assumptions could be correct, resulting in working code, or they may be incorrect, resulting in bugs.

A coworker of mine once had to write some code for an ATM. Since ATMs are reasonably sensitive, he wasn't allowed to dynamically allocate memory. That is, he could not use malloc and was only allowed to use what memory was statically allocated by the compiler. Not allowing dynamically allocated memory gets rid of entire range of problems, all of which are directly related to unpredictable state. Buffer overflows, out-of-bounds array referencing, bugs in string copying, reading input... all those problems are greatly mitigated by not having dynamically allocated memory.

You always want the state of your program to be predictable. Input makes the state unpredictable. As soon as we get input into our program, we can only hope that that input adheres to the assumptions the code makes. The current state may be valid (though unpredictable), however we cannot make any claims about future states. Only after we have sufficiently validated and sanitized any input in such a way that it adheres to the code's assumptions can we speak about a predictable state again.

This is why unclear code is such a problem. Unclear code makes it hard to reason about code, thus hard to determine whether code might lead to unpredictable states. Basically, we want to make the assumptions of code as transparent as possible.

I hope everything I've said so far makes absolutely basic sense. I hope that at this point in the article you're thinking "Well, duh", because from what I've seen of many programmers.. they don't have a clue about the relation between input, state and bugs.

"So what?"

It is important to grasp this basic concept of state because it helps you to reason about why and when certain programming techniques are a good or bad idea.

  • Functions are a good idea because they make it easier for the programmer to reason about input and its effect on state within that function. Easier reasoning about state equals better assumptions about code, resulting in less bugs.

  • Object Oriented Programming is a good idea because it groups together data and the logic that operates on that data, and therefor it allows the programmer to encapsulates state in such a way that it is harder to disrupt that state with outside influences.

  • Using global variables is a bad idea because it screws up all the assumptions code makes about that global variable. Wherever you use a global variable, you cannot reason about the state of your program, since the value of the global variable can change at any time.

  • Allowing publicly settable properties in objects (that includes setter methods, for you Java developers out there) is a bad idea because now any assumptions methods in that object make about the state of those properties can be invalid. Conversely, making the constructor the only part of the object that is allowed to have input is a good idea (even if it's not always practical)

  • goto is considered evil because it makes allows for random changing of the state of a program, and therefor can make it incredibly hard for developers to reason about the current state of the program at any point.

  • functional programming is a good idea because it avoids mutable data as much as possible, and therefor it is hard to bring the program into an undefined state.

  • Multi-threaded programs where threads write to the same memory are a bad idea because writes are non-deterministic which cause unpredictable state. This can be avoided using locking, which in itself is incredibly hard to do properly, leading to state which is difficult to reason about.

  • Smaller functions are a good idea because, again, it makes it easier to reason about the state and the changes in that state within the function.

  • ...

I could go on, but I hope you get the point. Please note that these point have to be considered in context. Don't take these as absolutes, because that would go entirely against what I'm trying to say. Goto can most certainly be used to create state that is more predictable and easier to reason about. In general however, it is considered detrimental to predictable state.

Back to input

Lets jump back to input for a moment. The age-old adage goes: "Validate your input!" What does that mean? Quick question.. Given this function:

def foo(a, b):
    c = a / b
    return c

How many bugs are in that function? We can immediately spot a potential division by zero bug and an overflow bug. There are others, but the point is you don't know! The input into this function is not validated. We're making assumptions about the calling code which may or may not be true. The key here is that the concept of "input" doesn't just apply to what you read from they keyboard, a file or the network. It applies to every line of code. Programmers who do not realize this are what I like to call Pavlovian Programmers... Sure, you can teach them a trick (goto is bad!), but they'll never understand the reasoning behind that trick, and they won't be able to apply it to new concept. This is why programmers are jumping on the Event-driven programming bandwagon, despite what an insanely bad idea it is. Basically event-driven programming (the kind that binds anonymous functions as callbacks to events. Yes, javascript et al) is a kind of goto, except for being harder to debug.

Ideally, every function and every constructor would validate its input arguments. (Contracts, anyone?) The stricter you validate input arguments, the less chance there is of winding up in an unpredictable state. Of course I say "ideally", because it is not practical to validate each and every bit of input. A decent compromise would be to validate the input of all constructors that are part of library code. Then again, 99% of your code should be library code. But that's a discussion for another time.

Conclusions

The conclusions of this article are simple:

  • Prevent bugs
  • Write clear code

I'm not trying to be funny here. The conclusions are the same as what you've already heard a thousand times. I just hope that you now view them in a bit of a different light. I believe we can accomplish the above and create much better code if everybody would just realize a few basic concepts:

  • It is vitally important to protect the state at all times.
  • Minimize "outside" influences on the state. This includes input from files, the network, other threads that are running, global variables, etc.
  • The State in a program is unpredictable all the time. Whenever we read input, whenever a function returns or throws an error, our program is in an unpredictable state. The system should, at all times, move from unpredictable and potentially invalid states to a predictable and valid state. This can be accomplished by validating and sanitizing any input into the program.

I leave you with this quote, which I think I once read somewhere else, but cannot find again, so I will attribute to myself:

Programming is the messy art of constantly bringing a program back to a predictable state after receiving a tiny bit of input.

python-libtorrent program doesn't exit

(TL;DR: To the solution)

I was mucking about with the Python bindings for libtorrent, and made something like this:

import libtorrent
 
fname = 'test.torrent'
ses = libtorrent.session()
ses.listen_on(6881, 6891)
 
info = libtorrent.torrent_info(fname)
h = ses.add_torrent({'ti': info, 'save_path': session_dir})
prev_progress = -1
while (not h.is_seed()):
    status = h.status()
    progress = int(round(status.progress * 100))
    if progress != prev_progress:
        print 'Torrenting %s: %i%% done' % (h.name(), progress)
        prev_progress = progress
    time.sleep(1)
 
print "Done torrenting %s" % (h.name())
# ... more code

After running it a few times, I noticed the program would not always terminate. You'd immediately suspect a problem in the while loop condition, but in all cases "Done torrenting Foo" would be printed and then the program would hang.

In celebration of one of the rare occasions that I don't spot a hanging problem in such a simple piece of code right away, I fired up PDB, the Python debugger, which told me:

$ pdb ./tvt 
> /home/fboender/Development/tvtgrab/trunk/src/tvt(9)()
-> import sys
(Pdb) cont
Torrenting Example Torrent v1.0: 100% done
Done torrenting Example Torrent v1.0
The program finished and will be restarted

after which it promptly hung. That last line, "The program finished and will be restarted", that's PDB telling us execution of the program finished. Yet it still hung.

At this point, I was suspecting threads. Since libtorrent is a C++ program, and as the main loop in my code doesn't actually really do anything, it seems libtorrent is doing its thing in the background, and not properly shutting down every now and then. (Although it's more likely I just don't understand what it's doing) It's quite normal for torrent clients to take a while before closing down, especially if there are still peers connected. Most of the time, if I waited long enough, the program would terminate normally. However, sometimes it wouldn't terminate even after an hour, even if no peers were at any point connected to any torrents (the original code does not always load torrents into a session).

Digging through the documentation, I couldn't easily find a method of shutting down the session. I did notice the following:

~session()

The destructor of session will notify all trackers that our torrents have been shut down. If some trackers are down, they will time out. All this before the destructor of session returns. So, it's advised that any kind of interface (such as windows) are closed before destructing the session object. Because it can take a few second for it to finish. The timeout can be set with set_settings().


Seems like libtorrent uses destructors to shut down the session. Adding the following to the end of the code fixed the problem of the script not exiting:

del ses

The del statement in Python calls any destructors (if you're lucky) on that class. Having nearly zero C++ knowledge, I suspect C++ calls destructors automatically at program exit. Python doesn't do that though, so we have to call it manually.

Update: Calling the destructor does not definitively solve the problem. I am still experiencing problems with hangs when calling the session destructor. I will investigate further and update when a solution has been found.

Update II: Well, I've not been able to solve the problem any other way than upgrading to the latest version of libtorrent. So I guess that'll have to do.

Conque: Terminal emulators in Vim buffers

For the longest time, I've searched for a way to run terminal emulators in Vim buffers.

As a kind of work-around, I created Bexec, which allows you to run the current contents of a buffer through an external program. It then captures the output and inserts/appends it to another buffer.

Although Bexec works reasonable, and still has it's uses, it's not a true terminal emulator in Vim. Today I finally found a Vim plugin that let's you actually run interactive commands / terminals in Vim buffers: Conque.

It requires Vim with Python support built in. Installation is straight-forward if you've got the requirements.

Download the .vmb file, edit it in vim, and issue:

:so %

It will then be installed. Quit vim, restart it, and you can now run start using it:

:ConqueTerm bash

Very awesome.

Read less

A programmer once built a vast database containing all the literature, facts, figures, and data in the world. Then he built an advanced querying system that linked that knowledge together, allowing him to wander through the database at will. Satisfied and pleased, he sat down before his computer to enjoy the fruits of his labor.

After three minutes, the programmer had a headache. After three hours, the programmer felt ill. After three days, the programmer destroyed his database. When asked why, he replied: “That system put the world at my fingertips. I could go anywhere, see anything. Because I was no longer limited by external conditions, I had no excuse for not knowing everything there is to know. I could neither sleep nor eat. All I could do was wander through the database. Now I can rest.”

— Geoffrey James, Computer Parables: Enlightenment in the Information Age

I was a major content consumer on the Internet. My Google Reader had over 120 feeds in it. It produced more than a 1000 new items every couple of hours. I religiously read Hacker News, Reddit and a variety of other high-volume sources of content. I have directories full of theoretical science papers, articles on a wide range of topics and many, many tech books. I scoured the web for interesting articles to save to my tablet for later reading. I was interested in everything. Programming, Computer Science, Biology, Theoretical Particle Physics, Psychology, rage-comics, and everything else. I could get lost for hours on Wikipedia, jumping from article to article, somehow, without noticing it, ending up at articles titled "Gross–Pitaevskii equation" or "Grand Duchy of Moscow", when all I needed to know was what the abbreviation "SCPD" stood for. (Which, by the way, Wikipedia doesn't have an article for, and means "Service Control Point Definition")

I want to make it clear I wasn't suffering from Information Overload by any definition. I was learning things. I knew things about technology which I hadn't even ever used myself. I can tell you some of the ins and outs of iPhone development. I don't even own an iPhone. I can talk about Distributed Computing, Transactional Memory and why it is and isn't a good idea, without having written more than a simple producer/consumer routine. I'm even vehemently against writing to shared memory in any situation! I can tell you shit about node.js and certain NoSQL databases without even ever having installed – much less dived into – them. Hell, I don't even like Javascript!

The things is: even though I was learning about stuff, it was superficial knowledge without context and the kind of basic information that allows you to draw these conclusions you're reading about for yourself, without the help of some article. I didn't pause to think about conclusions drawn in an article, or to let the information sink in. I read article after article. I wasn't putting the acquired knowledge into practice. The Learning Pyramid may have been discredited, but I'm convinced that we learn more from doing than we do from reading about something.

So what makes reading so attractive that we'd rather read about things than actually doing them? And I know for a fact that I'm not alone in having this problem. I think – and this might be entirely personal – it's because of a couple of reasons.

One is that it's much easier to read about something than to actually figure things out yourself. I want to experiment with sharding in NoSQL databases? I have to set up virtual machines, set up the software, write scripts to generate testing data, think about how to perform some experiments, and actually run them. Naturally I'd want to collect some data from those experiments; maybe reach a couple of conclusions even. That's a lot of work. It's much easier to just read about it. It's infinitely easier to stumble upon and read an article on "How to Really Get Things Done Using GettingThingsDone2.0 and Reverse Todo Lists" than it is to actually get something done.

The second reason, at least for me, is that it gives me the feeling that I'm learning more about things. In the time it takes me to set up all the stuff above, I could have read who-knows-how-many articles. And it's true in a sense. The information isn't useless per se. I'm learning more shallow knowledge about a lot of different things, versus in-depth knowledge about a few things. It gives me all kinds of cool ideas, things to do, stuff to try out. But I never get around to those things, because I'm always busy reading about something else!

So I have taken drastic measures.

I have removed close to 95% of my feeds from Google Reader. I've blocked access to Reddit and HackerNews so I'm not tempted to read the comments there. I check hackurls.com (an aggregator for Hacker News, Reddit's /r/programming and some other stuff) at most once a day. Anything interesting I see, I send to my tablet (at most two articles a day), which I only read on the train (where I don't have anything better to do anyway). I avoid Wikipedia like the plague.

I distinctly remember being without an Internet connection for about a month almost four years ago. It was the most productive time of my life since the Internet came around. I want to return to the times when the Internet was a resource for solving problems and doing research, not an interactive TV shoveling useless information into my head.

Now if you'll excuse me, I have an algorithm to write and a website to finish.

Read the POSIX standard

Stop reading your local manual pages when programming/scripting stuff, and use the POSIX standard instead:

Online POSIX 2008 (EEE Std 1003.1-2008) standard

There are four main parts:

Some Do's and Dont's:

Finally, read Bash Pitfalls to learn why your shell scripting sucks.

Python UnitTest: AssertRaises pitfall

I ran into a little pitfall with Python's UnitTest module. I was trying to unit test some failure cases where the code I called should raise an exception.

Here's what I did:

def test_file_error(self):
    self.assertRaises(IOError, file('/foo', 'r'))

I mistakenly thought this would work, in that assertRaises would notice the IOError exception and mark the test as passed. Naturally, it doesn't:

ERROR: test_file_error (__main__.SomeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "./test.py", line 10, in test_file_error
    self.assertRaises(IOError, file('/foo', 'r'))
IOError: [Errno 2] No such file or directory: '/foo'

The problem is that I'm a dumbass and I didn't read the documentation carefully enough:


assertRaises(exception, callable, *args, **kwds)
Test that an exception is raised when callable is called with any positional or keyword arguments that are also passed to assertRaises().

If you look carefully, you'll notice that I did not pass in a callable. Instead, I passed in the result of a callable! Here's the correct code:

def test_file_error(self):
    self.assertRaises(IOError, file, '/foo', 'r')

The difference is that this time I pass a callable (file) and the arguments ('/foo' and 'r') that the test case should pass to that callable. self.AssertRaises will then call it for me with the specified arguments and catch the IOError. In the first scenario (the wrong code), the call is made before the unit test is actually watching out for it.

Programmer's Block: Analysis Paralysis

I'm in the process of writing a tiny tool. What it does is not important, only that it's nothing big. I've almost finished writing it, and it currently weighs in at about 260 lines of code. The bizarre thing is that it took me three days to write. By my estimates, it shouldn't have taken me longer than perhaps a day. So why did it take so long?

Like always, whenever I start writing a program, I begin with the absolute heart of the problem I want to solve. I then write the rest of the program around that. I never really design anything up-front, especially when it's such as small project. As normally happens, I run into some potential problems. The solution is almost always obvious. Part of the program might block on a non-responsive network resource? Fine, build some threading around it. External tools may need to access internals of the program? Alright, let's build in a simple RPC server to communicate with the process. Functionality should be extensible by system administrators or other programmers? Cool, just write some plugin architecture with a tightly defined API. In short, everything just flows.

"Flow" is, to me at least, exceptionally important. Problems and solutions present themselves almost instantaneously when I'm writing code. More often than not I need to refactor almost constantly during the development process. Some might see that as a problem; I don't. It's just the way I work. It's part of my flow. I can't design an entire program up front on paper or in diagrams [1]. I'm one of those "Solve the problem at hand and nothing else" kind of developers. I always gruesomely over-design things, scared of ending up with a design that is not extensible or flexible enough, which leads to Feature Creep. Usually, halfway through the implementation I will encounter something non-optimal in the design and feel bad for either following or not following the design. Following design breaks my flow, and it demotivates me. So I don't fully design up-front, although I usually have a rough outline in my head.

This time however, my flow was interrupted by something completely different. It was such a small and ridiculous thing that I'm almost ashamed of talking about it. You see, I needed to return some results from a method call, and I couldn't see the right way to proceed. My normal minimalist approach would have been to simply return the results as a list/array of values. My "Upcoming Problem" alarm bells started ringing however, as I anticipated that a simple list wouldn't do. The calling code would need to do various things with the results, which really weren't the responsibility of the calling code at all. So should I create a new object to hold the results, accompanied with some methods to perform operations on those results? Again it didn't feel like the optimum solution. It would mean tightly coupling that object with other code. I considered some other options, but it was beginning to feel obvious: my flow was broken.

So I did what I usually do when my flow is broken: I go and do something else. Let my subconscious think about it a bit. A solution is bound to jump to the top of my mind, and I can get back to work, right? Well, it didn't. Then I did what I almost never do: I let the problem fester in my mind. In the next two days I intermittently returned to my (still open) editor, looked at the code a bit, and went to do something else again.

After two days I suddenly realized I was having Programmer's Block over something completely idiotic! This was such a minor problem that I almost couldn't believe I wasted two days on it. My lack of progress wasn't because the problem was too hard, or that the solution was sub-optimal. That happens all the time, and I either keep on tinkering until I've solved the problem, even if it means the solution is sub-optimal. The problem was that I had multiple possible solutions in my head and all were equally sub-optimal, and I couldn't choose between them. I was over-thinking the implications of my choice; suffering from Analysis Paralysis. The very thing I try to avoid by not designing too much up-front.

In the end I just went with a random sub-optimal solution to the problem. I still don't know of a better one. Perhaps one will come around later on in the development, or during my final refactoring round. It's really not important, which is why it bugs me that I got stuck on such a minor problem in the first place. In any case, my flow is back and the program is almost finished [2].

So, the lessons learned?

  • Sometimes you just have to put your perfectionism aside.
  • Sometimes, all you have are bad choices. Making a bad choice is better than making no choice.
  • "Go and do something else" can sometimes actually be more harmful then just persevering in solving the problem, even if it is sub-optimal. Remember, it's just code. You can always throw it away if it doesn't live up to expectations. I was afraid of wasting time by making the wrong choice, but in the meantime I wasn't working on the problem at all, so the time was wasted anyway.

[1] Actually, I can design up-front. I just have to keep it very minimal. Some diagrams on the architecture of multi-tier projects. A couple of doodles of how the major components will interact. A small list of data that needs to be stored. But if I actually start making class diagrams, the flood-gates open and I end up with a beast of a design.

[2] Experience tells me the program isn't nearly finished. The "programming" bit of a project usually only accounts for about 40% of the total project I have to do. The rest goes to the final refactoring round, writing documentation, testing, packaging, release management, etc

Evolutionary Algorithm: Evolving "Hello, World!"

Note: The latest version of this article is always available from the Writings page in HTML, PDF, ePub and AsciiDoc (source) format.

My interest in Evolutionary Algorithms started when I read On the Origin of Circuits over at DamnInteresting.com. I always wanted to try something like that out for myself, but never really found the time. Now I have, and I think I've found some interesting results.

Disclaimer: I know next to nothing about Evolutionary Algorithms. Everything you read in here is the product of my own imagination and tests. I may use the wrong algorithms, nomenclature, methodology and might just be getting very bad results. They are, however, interesting to me, and I do know something about evolution, so here it is anyway.

How Evolution Works

So, how does an Evolutionary Algorithm work? Why, the same as normal biological evolution, mostly! Very (very) simply said, organism consist of DNA, which determine their characteristics. When organisms reproduce, there is a chance their offspring's DNA contains a mutation, which can lead to difference in characteristics. Sufficiently negative changes in offspring make that offspring less fit to survive, causing it, and the mutation, to die out eventually. Positive changes are passed on to future offspring. So through evolution an set of DNA naturally tends to grow towards its "goal", which is ultimate fitness for its environment. Now this is not an entirely correct description, but for our purposes it is good enough.

A simple evolutionary algorithm

There is nothing stopping us from using the same technique to evolve things towards goals set by a programmer. As can be seen from the Antenna example in the DamnInteresting article, this can sometimes even produce better things than engineers can come up with. In this post, I'm going to evolve the string "Hello, World!" from random garbage. The first example won't be very interesting, but it demonstrates the concept rather well.

First, lets define our starting point and end goal:

source = "jiKnp4bqpmAbp"
target = "Hello, World!"

Our evolutionary algorithm will start with "jiKnp4bqpmAbp", which we can view as the DNA of our "organism". It will then randomly mutate some of the DNA, and judge the new mutated string's fitness. But how do we determine fitness? This is probably the most difficult part of any evolutionary algorithm.

Lucky for us, there's an easy way to do this with strings. All we have to do is take the value of each character in the mutated string, and see how much it differs from the same character in the target string. This is called the distance between two characters. We then add all those differences, which leads us to a single value which is the fitness of that string. A fitness of 0 is perfect, and means that both strings are exactly the same. A fitness of 1 means one of the characters is off by one. For instance, the strings "Hfllo" and "Hdllo" both have a fitness of one. The higher the fitness number, the less fit it actually is!

Here's the fitness function.

def fitness(source, target):
   fitval = 0
   for i in range(0, len(source)):
      fitval += (ord(target[i]) - ord(source[i])) ** 2
   return(fitval)

If you look closely, you'll notice that for each character, I square the difference. This is to convert any negative numbers to positive ones, and to put extra emphasis on larger differences. If we don't do this, the string "Hannp" would have a fitness of 0. You see, the difference between 'e' and 'a' is -5, between 'l' and 'n' is +2 (which we have twice) and between 'o' and 'p' is +1. Adding these up yields a fitness of 0, but it's not the string we want at all. If we square the differences, they become 25, 4, 4 and 1, which yields a fitness of 34. Effectively, we square each difference so that they can't cancel each other out.

Edit: In the mutation algorithm below, I only mutate one character by one value at a time. It has been pointed out that, unless I actually allow for larger mutations, squaring the distance is largely pointless, since new mutations will always only differ by one value. At the time I wrote this fitness function, I had no idea how the rest of the algorithm would look like. It seemed like a good idea.

Now we need to introduce mutations into our string. This is rather easy. We simply pick a random character in the string, and either increment or decrease it by one, or leave it alone:

def mutate(source):
   charpos = random.randint(0, len(source) - 1)
   parts = list(source)
   parts[charpos] = chr(ord(parts[charpos]) + random.randint(-1,1))
   return(''.join(parts))

Time to tie the whole shabang together!

fitval = fitness(source, target)
i = 0
while True:
   i += 1
   m = mutate(source)
   fitval_m = fitness(m, target)
   if fitval_m < fitval:
      fitval = fitval_m
      source = m
      print "%5i %5i %14s" % (i, fitval_m, m)
   if fitval == 0:
      break

This should be easy enough to understand. For each iteration of the While-loop, we mutate the string and then calculate its fitness. If it is fitter then the original string (the parent), we make the child the new string. Otherwise, we throw it away. If the fitness is 0, we're done!

Lets look at some output. I'm snipping out some intermediary output cause it's not terribly interesting.

At generation 1, we have a fitness of 15491, and the string looks nothing like "Hello, World!". The same for generation 20, 40, 60, etc.

    1 15491  jjKnp4bqpmAbp
   20 15400  jiKnp3bppoAbp
   40 15377  jiKlo2bpooAdp
   60 15130  iiKlo2aoooAdp

Not much progress so far. At generation 500 it's still a load of nonsense:

  500  9986  \eTlo,YaorNdf

Generation 1200, we start to see something that looks like "Hello, World!":

 1200  4186  Heglo,LWorhdP

Generation 1500, we're getting very close!

 1500  3370  Hello,GWorldL

It still takes a good 1500 generations more before we're finally there:

 3078     2  Hello, Vorld"
 3079     2  Hfllo, World"
 3080     2  Hfllo, World"
 3081     0  Hello, World!

There it is!

A better, more interesting, algorithm

Okay, so that worked. But... it was kinda lame. Nothing interesting to see, really, was there? That's because our algorithm was a little too simplistic. Only one "organism" in the gene pool, only one character mutated at any time. We can do better than that, so let's modify the program to make it more interesting.

We're not going to touch our fitness function, since that works rather well. Instead, lets introduce a gene pool. Instead of having only one string, why not have a whole bunch or randomly generated strings and let them duke it out among themselves. That sounds a bit more real-life, doesn't it?

GENSIZE = 20
genepool = []
for i in range(0, GENSIZE):
   dna = [random.choice(string.printable[:-5]) for j in range(0, len(target))]
   fitness = calc_fitness(dna, target)
   candidate = {'dna': dna, 'fitness': fitness }
   genepool.append(candidate)

This little snippet generates a gene pool with 20 random strings and their fitnesses. In an official implementation, the gene pool would be called the population. (Thanks, reddit!)

Now, lets modify our mutation function. Instead of mutating one single character, we feed it two parents, picked at random from the genepool, and it will mix their DNA together a bit. This is called crossover. It will also randomly mutate one character in the resulting DNA. It then returns the newly fabricated child, including its fitness.

def mutate(parent1, parent2):
   child_dna = parent1['dna'][:]

   # Mix both DNAs
   start = random.randint(0, len(parent2['dna']) - 1)
   stop = random.randint(0, len(parent2['dna']) - 1)
   if start > stop:
      stop, start = start, stop
   child_dna[start:stop] = parent2['dna'][start:stop]

   # Mutate one position
   charpos = random.randint(0, len(child_dna) - 1)
   child_dna[charpos] = chr(ord(child_dna[charpos]) + random.randint(-1,1))
   child_fitness = calc_fitness(child_dna, target)
   return({'dna': child_dna, 'fitness': child_fitness})

We also need a routine to pick two random parents from the genepool. Now, we could just pick them completely random, but what you really want is for parents with a good fitness to have a better chance of offspring. This is called elitism If we sort the genepool list by fitness, we can use a uniform product distribution to make sure that parents with better fitness get chosen more often.

Now you might ask, what the hell is a uniform product distribution? When you randomly pick a number between, say, one and ten, each number has the same chance of being picked. This is called a "uniform distribution". But when you pick two random numbers, and you multiply them, there's a much bigger chance of getting a bigger number than a smaller number. Hence the name "uniform product distribution". Here's how that looks:

So our random parent picker will do just that. We select two random real numbers between 0 and 1, multiple those two random numbers and then scale the result up to our poolsize by multiplying the result with the size of the pool. We return that parent from the pool.

def random_parent(genepool):
   wRndNr = random.random() * random.random() * (GENSIZE - 1)
   wRndNr = int(wRndNr)
   return(genepool[wRndNr])

There! Now it's time for our main loop

while True:
   genepool.sort(key=lambda candidate: candidate['fitness'])

   if genepool[0]['fitness'] == 0:
      # Target reached
      break

   parent1 = random_parent(genepool)
   parent2 = random_parent(genepool)

   child = mutate(parent1, parent2)
   if child['fitness'] < genepool[-1]['fitness']:
      genepool[-1] = child

For each iteration of the While True loop, we first sort the genepool by fitness so that the most fit parents are at the top. We check to see if the fittest happens to be the target string we're looking for. If so, we stop the loop.

Then we select two parents from the genepool using the uniform product distribution so that fitter parents are chosen more often. We create a bastard mutated child that will mix both parents' DNA together and introduce a little mutation. If the new child is more fit than the worst in the genepool, it will replace that degenerate one in the genepool. In the next iteration, the pool is sorted again on fitness so that the new child takes its rightful place.

Results

Now it's time to run this puppy and see what it does. Again, I snip out some of the less interesting stuff.

Here's the genepool in the beginning. The first number is the generation (the number of times the While-loop has run), the second number the fitness and the third column is the DNA for that entry in the genepool.

     1   7617   'iSx{$,K`u~(B
     1   9284   SQf`1N#UdrPlT
     1  12837   sYIu<E"Fq'^_.
     1  15531   DC8Dg1I$*mUs-
     1  16064   L~*}JBVdF7bu2
     1  16533   1,XU%)5$q[YuO
     1  16588   ff],ceW<0fud&
     1  17316   [V3@2'VgY\{KV
     1  17356   kWw#v/P<#apG9
     1  17581   <Lrh(1hN_Bd)3
     1  18777   TM]_]TbtxFY:q
     1  19656   $zS+EI?BS>%z(
     1  19841   =S;B~((W8 D,6
     1  20398   P_A$D|NPJPio/
     1  21957   J&f=O:g\8'{S2
     1  22543   5*T2c"pMZ80L'
     1  24954   A&lZ#A_}MxI"P
     1  25186   &9MrI|0&x)q,N
     1  28110   OlXT/Q{y3{"LR
     1  29656   8WB99hx%0]}h[

One big random jumbled mess. Note the ones I've emphasized. These are the parents that were selected for the new child in the next generation. Lets see how it looks after one generation:

     2   7617   'iSx{$,K`u~(B
     2   8742   SQf`1N#UdfumT
     2   9284   SQf`1N#UdrPlT
     2  12837   sYIu<E"Fq'^_.
     2  15531   DC8Dg1I$*mUs-
     2  16064   L~*}JBVdF7bu2
     2  16533   1,XU%)5$q[YuO
     2  16588   ff],ceW<0fud&
     2  17316   [V3@2'VgY\{KV
     2  17356   kWw#v/P>#apG9
     2  17581   <Lrh(1hN_Bd)3
     2  18777   TM]_]TbtxFY:q
     2  19656   $zS+EI?BS>%z(
     2  19841   =S;B~((W8 D,6
     2  20398   P_A$D|NPJPio/
     2  21957   J&f=O:g\8'{S2
     2  22543   5*T2c"pMZ80L'
     2  24954   A&lZ#A_}MxI"P
     2  25186   &9MrI|0&x)q,N
     2  28110   OlXT/Q{y3{"LR

Two random parents from the previous generation have their DNA mixed, and have generated an offspring (the bold one) which is better then both of them. It comes in second with a fitness of 8742, while its parents only had fitness of 9284 and 16588. Lets skip ahead a bit and look at the 6th generation:

     6   7617   'iSx{$,K`u~(B
     6   8742   SQf`1N#UdfumT
     6   9284   SQf`1N#UdrPlT
     6  10198   SQfD1N#UdfumT
     6  12837   sYIu<E"Fq'^_.
     6  15531   DC8Dg1I$*mUs-
     6  16064   L~*}JBVdF7bu2
     6  16387   SQf`1N"MZ80LT
     6  16533   1,XU%)5$q[YuO
     6  16588   ff],ceW<0fud&
     6  17316   [V3@2'VgY\{KV
     6  17356   kWw#v/P>#apG9
     6  17356   kWw#v/P>#apG9
     6  17581   <Lrh(1hN_Bd)3
     6  18777   TM]_]TbtxFY:q
     6  19656   $zS+EI?BS>%z(
     6  19841   =S;B~((W8 D,6
     6  20287   fe],1eW<0fud&
     6  20398   P_A$D|NPJPio/
     6  21957   J&f=O:g\8'{S2

As you can see, the "SQf" has reproduced again with success, and there are now four variants of it in the genepool. We also note the "kWw#", which there are two identical ones of. This can happen when the entire DNA of one parent is copied and no mutation occurs. In our mutate function, we use the first parent's DNA as a base and then randomly overlay some of the seconds parent's DNA. This can anything from the entire second parent's DNA, or nothing at all. But generally, the chance is higher that the first parent's DNA survives largely in tact.

The next interesting generation is 13:

    13   4204   RQf`{$,KdfumT
    13   7617   'iSx{$,K`u~(B
    13   7617   'iSx{$,K`u~(B
    13   8742   SQf`1N#UdfumT
    13   8742   SQf`1N#UdfumT
    13   9284   SQf`1N#UdrPlT
    13   9284   SQf`1N#UdrPlT
    13  10198   SQfD1N#UdfumT
    13  12837   sYIu<E"Fq'^_.
    13  15531   DC8Dg1I$*mUs-
    13  15838   L~*xJBVdG7bu2
    13  15856   $zS+<E"Fq(^_(
    13  15883   L~*xJCVdG7bu2
    13  16064   L~*}JBVdF7bu2
    13  16387   SQf`1N"MZ80LT
    13  16533   1,XU%)5$q[YuO
    13  16588   ff],ceW<0fud&
    13  17316   [V3@2'VgY\{KV
    13  17356   kWw#v/P>#apG9
    13  17356   kWw#v/P>#apG9

Wow! "SQf" has been really busy and now almost rules the genepool. "iSx" is second and third, but has lost its number one position to the "RQf" variant of "SQf". "RQf" was introduced in the 12th generation as a child of an "iSx" and "SQf" variant. We see that "kWv" has been knocked almost to the end of the list by more fit candidates. It is very obvious that this pool is no longer random. Patterns are starting to emerge all over it.

By the time we reach generation 40:

    40   3306   RQSw{$-KcfumB
    40   4204   RQf`{$,KdfumT
    40   4229   RQf`|$,KdfumT
    40   4242   RQe`|$,KdfumT
    40   4795   RQSw{$-KdfumT
    40   4971   RQSwz$*K`uSnT
    40   4973   RQSwz$+K`uSmT
    40   4992   RQSwz$+K`uSnT
    40   5017   SQSxz$+K`uSmT
    40   5017   SQSxz$+K`uSmT
    40   5951   (QSxz$+KdfSmT
    40   5985   'QSxz$+K`uSmT
    40   6421   SQfx{$+K`u~(B
    40   6444   TQf`{$+K`u~(B
    40   6489   SQfx{$+KdfS(B
    40   6492   TQf`{$-K`u~(B
    40   7034   SQSxy$+KdfS(B
    40   7617   'iSx{$,K`u~(B
    40   7617   'iSx{$,K`u~(B
    40   7625   'iS`{$,Kdg~(B

The genepool is now almost entirely dominated by the "RQf" variants. Forms of its original parents "SQf" and "iSx" can still be found here and there, although "iSx" is almost entire gone from the pool. An interesting thing is that we can see combinations of letters (bold) that keep reappearing. These are almost like actual genes! Combinations of DNA that work well together and therefor stay in the genepool in that combination. It takes lots of generations to make variants of these genes that are more fit then previous versions.

The next milestone is found in the 67th generation:

    67   3138   RQSw{$+KdfukA
    67   3161   RQSw{$+KcfukA
    67   3176   RQSw{$,KdfulA
    67   3176   RQSw{$+KcfulA
    67   3218   RQSw{$-LcfumA
    67   3222   RQSw{%,KefumB
    67   3237   RQSw{$-LcfvmA
    67   3241   RQSw{$-KcfumA
    67   3241   RQSw{$-KcfumA
    67   3266   RQSw{$-KceumA
    67   3266   RQSw{$-KceumA
    67   3267   RRSw{$-KcfumB
    67   3289   RQSw{%,KefumC
    67   3306   RQSw{$-KcfumB
    67   3306   RQSw{$-KcfumB
    67   3323   RQSw{#-KcfumB
    67   3324   RPSw{$-KdfumB
    67   3331   RQSw{$-KbfumB
    67   3348   RQSw{#-KbfumB
    67   3489   RQSw{$+KdfumA

This marks the first generation where there are no other variations then the RQS one. But immediately, we see the next generation in which a new number one is found:

    68   3119   QQSw{$+KdfukA
    68   3138   RQSw{$+KdfukA
    68   3161   RQSw{$+KcfukA

By the 96th generation, QQS has taken over the top:

    96   3060   QQSw{%+KdhukA
    96   3065   QRSw{%+KdfukA
    96   3081   QQSw{%+KdgukA
    96   3081   QQSw{%+KdgukA
    96   3081   QQSw{%+KdgukA
    96   3096   QQSw{$+KdgukA
    96   3104   QQSw{%+KdfukA
    96   3119   QQSw{$+KdfukA
    96   3119   QQSw{$+KdfukA
    96   3119   QQSw{$+KdfukA
    96   3137   RRSw{$,KdfulA
    96   3137   RRSw{$,KdfulA
    96   3138   RQSw{$+KdfukA
    96   3138   RQSw{$+KdfukA
    96   3138   RQSw{$+KdfukA
    96   3138   RQSw{$+KdfukA
    96   3138   RQSw{$+KdfukA
    96   3142   QQSw{$,KdfukA
    96   3142   QQSw{$+KcfukA
    96   3144   QQSw|$+KdfukA

This is where the race gets boring. Every now and then a new, better, mutation will arise and take over the genepool. Change is slow though, and no big surprised are left. The candidates slowly but surely mutate until the reach something resembling the "Hello, World!" we are looking for in generation 1600:

  1600     19   Hdllo+ Worle%
  1600     20   Hdklo+ Worle%
  1600     20   Hdklo+ Worle%
  1600     20   Hdklo+ Worle%
  1600     20   Hdklo+ Worle%
  1600     20   Hdklo+ Workd%

It takes almost another half-thousand generation to get to the final target:

  1904      0   Hello, World!
  1904      1   Hello, World"
  1904      1   Hello, World"
  1904      2   Hello, Wprld"
  1904      2   Helmo, World"
  1904      2   Helmo, World"
  1904      2   Hdllo, World"
  1904      2   Hello, Worle"

Here are the program so you can download them and play with it a bit (ignore the SSL warning; it's a self-signed certificate):

Interesting (if you're boring like me and you like this kind of stuff) facts:

  • It usually takes anywhere between 2500 and 4000 generations to evolve the target.
  • On average, it takes approximately 3100 generations to evolve the target.
  • If we remove the parent DNA mixing and rely solely on mutations, it takes on average 3650 generations to evolve the target.
  • The parent DNA mixing is only really useful in the beginning. In the first generations, it can quickly propel a new mix of DNA to the top of the list, but later on random mutations instead of mixing DNA becomes the main driving force between the evolution. (this doesn't have to be the case in real life evolution, naturally)
  • Sometimes "beneficial" mutations disappear. For instance, the word "World" already appeared in mutation 1469, but was overtaken by other mutations quickly. It was pushed out of the genepool at generation 1486, only to reappear in generation 1659. From then on, it quickly rose to the top and dominated the top 5 positions of the genepool within 10 generations.

Update: It has rightly been pointed out that are much more efficient methods of this algorithm. Please keep in mind that I had absolutely no idea what I was doing. :-D I'm surprised I got so close to how one would properly implement an Evolutionary Algorithm.

Also, here are some more interesting statistics. I modified the mutation function a number of times, and these are the results:

  • One char, -1, 0 or +1 ascii-value: 3100 generations
  • Two chars, -1, 0 or +1 assii-value: 1924 generations
  • Three chars, -1, 0 or +1 ascii-values: 1734 generations
  • Four chars, -1, 0 or +1 ascii-values: 1706 generations
  • One char, between -4 and +4 ascii-values: 1459 generations
  • two chars: between -4 and +4 ascii-values: 2122 generations
  • Three chars, between -4 and +4 ascii-values: 4490 generations

You can also read the
Reddit discussion and the Hacker News discussion for some nice insights. One of the most interesting comments mentions:

FWIW, for this problem, at least the way the OP set it up, the "naive" algorithm is actually a very good way to go - when I increase the population size to 20, and set the mutation/selection/crossover policies OP used, I find that the average number of fitness checks required to hit "Hello, World" (about 3510) is actually higher than the number in the naive version (in the neighborhood of 3k, usually a bit under). Also, the real time taken is larger. Which means that adding "genetic" to the algorithm has actually hurt us...
In fact, even with my full GA codebase in hand (not a substantial one, I wrote it in response to this post, but it's more flexible than the OP's), I couldn't find any situation where having a population size more than a few members helped - single member mutation (which is accepted/rejected if better/worse) always won. This is a good indication that this type of problem is vastly better suited to gradient descent than it is to a genetic algorithm.

Cool stuff.

PyWebkitGTK: 'module' object has no attribute 'WebView'

If you're working with PyWebkitGTK, and you get the following error:

Traceback (most recent call last):
  File "./webkit.py", line 7, in 
    import webkit
  File "/home/todsah/webkit.py", line 18, in 
    class BrowserPage(webkit.WebView):
AttributeError: 'module' object has no attribute 'WebView'

… make sure you haven't named your script 'webkit.py', and there is no other script with the same name in that directory. Also delete any webkit.pyc pic files. Do'h!