I missed a weekend, sorry guys! I was busy babysitting a five year old and contemplating the LambdaConf situation. To make it up I have a totally fresh and new topic to talk about: genetic programming. I do not want to design a bidding systems, I want to make the best one possible, and for that I intend to use genetic programming. The idea of genetic programming is that instead of typing a program, we create it (also called synthesizing).

A quite simple example is the following:

We have a method that returns a string:

function helloFSharpLovers() {
   return "123";
}

Yeah I know this is JavaScript and not F# but I am preparing for an F# conference 🙂 It is JavaScript so I can embed an example later and you and see it in action!

The string we want to return is “HELLO FSHARP LOVERS” So, we can type this, but why? That is so tiring… I want the machines to work for me, using some principles from evolution.

In order to mimic evolution, we need two things: the ability to create new versions of programs (mutation) and knowing which of your children is most likely to succeed (fitness)

Mutation

I can define a number of transformations that mutate my program, like replacing a letter or adding one:

function mutate(input)
{
   var operation = Math.floor(Math.random() * 2);

   var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";
   randChar = chars.charAt(Math.floor(Math.random() * chars.length));

   if (operation == 0){
      //get a random location
      var location = Math.floor(Math.random() * input.length);
	
      var firstPart = input.substring(0,location);	
      var secondPart = input.substring(location+1, input.length);
	
      return firstPart + randChar + secondPart;
   }

   if (operation == 1){
      return input + randChar;
   }
}

Survival of the fittests 

Now, when are we going the ‘right way’? For this problem, we could use string distance (Levenshtein distance). So, we mutate the function into returning a slightly different string, and if we are closer to the result, we keep it, if not, we discard it:

function runGenetics(){
   while (code != goal)){
      var mutatedVersion = mutate(code);
      if (levenshteinDistance(mutatedVersion, goal) <= levenshteinDistance(code,goal))
      {
         code = mutatedVersion;			
         editor.setValue(code);
       }
   }
}

Look, mommy, no hands (were hurt writing this code)

In the iframe below you see my code in action. Adapt the program manually and ‘Run current code’ to execute the function in the Ace editor or click ‘Make it so!’ to have the program generated for you!

Cool heh? Next week I will talk about how this works together with a DSL! How to eval() you own code? And what fitness function to use for a bridge bidding machine? Stay tuned!