self.write_blog

It’s quiet in here…

jr.calzada.nospam@nospam.raine-tech.com (jr.calzada) — Thu, 28 May 2009 18:48:59 -0600

If you happen to be a regular visitor, then you might have noticed it has been almost a month since my last post. Although I had some interesting posts lined up for this month, everything got side-tracked once the date of the wedding approached. For those not in the know, I got married on May 16th and finally put an end to the very stressful and intense process of planning such an event. Everything was perfect and both me and my wife had the time of our lives. After the wedding we traveled to Spain, where we spent our honeymoon. I just got back yesterday and, realizing I had neglected the blog, thought it would be appropriate to post a small update.

As I mentioned in one of my first posts in this blog, I played a few songs at the wedding with the help of some friends. Unfortunately, I didn’t actually record the performance, so I can’t honestly say whether it sounded decent or not. Still, here’s a nice picture taken during the third song in the set: Oasis’s Live Forever.

I’ll try and post often these next few weeks. I still have some pending posts I’d promised before and I also wanted to mention some topics that caught my attention. I also need to get back on Twitter, since I haven’t posted an update in ages either. Until then, I’ll go back to enjoying the newly-wed life!

Genetic Algorithms in F# Part 1: Generations, Selection, Crossover, and Mutation

jr.calzada.nospam@nospam.raine-tech.com (jr.calzada) — Sun, 03 May 2009 03:33:35 -0600

Genetic algorithms are a technique in artificial intelligence used to find the answer to a problem we don’t really know how to solve. The solution process is stochastic in nature, employing several ideas based on the theory of evolution. The main hypothesis is that, given a randomly generated set of possible solutions to a problem and a way to measure how effective they are, we can find increasingly better solutions by selecting the best ones from our set, mixing them, and then making very small changes. This mirrors the basic evolutionary process where the fittest individuals of a certain species mate and, sometimes, their genes are mutated leading to new characteristics that might be beneficial or not.

There are two main questions we must ask ourselves when trying to approach a problem with a genetic algorithm:

How can I encode a possible solution?
How can I measure a solution’s effectiveness?

We usually call the encoded version of a solution a chromosome. There’s no definite rule as to how we should build our chromosome, but using bit arrays is a common approach. Whatever your choice, it is safe to assume that they will usually be a collection of values and all chromosomes should be the same size. Now we just need to find a way to translate a possible solution to our problem to our data structure. The second question leads us to our fitness function which is a function that measures how effective a certain ‘chromosome’ is at solving our problem. Depending on the problem you’re trying to solve, it might make sense to normalize the fitness or not. These two elements are completely domain-dependent. The evolutionary process, on the other hand, is mostly domain-independent, which means it can be coded in a generic way. I will delve deeper into these subjects in a later post.

In a way, selection, crossover, and mutation are the workhorses within a genetic algorithm. They are, after all, the ones that process the initial batch of solutions to generate new ones that might be more effective. Depending on our problem, different selection, crossover, and mutation strategies may be appropriate. Ideally, we would like to be able to choose which algorithm we’d like to use for each of these processes depending on our problem. I present one algorithm of each further below.

Generations

The way we represent a batch of solutions is with a generation, which is simply a collection of individuals. These individuals are our possible solutions to the problem at hand and contain a chromosome and a fitness, which determines how effective they are at solving the problem. The code to implement these data structures is very simple. I defined the Individual type to be a record and the Generation to be a class.

   1:  #light

   2:  namespace RaineTech.AI.GeneticAlgorithms

   3:      type 'a Individual =

   4:          {

   5:              Chromosome : 'a list

   6:              Fitness : double

   7:          }

8:

   9:      type 'a Generation(individuals : 'a Individual list) =

  10:          let orderedIndividuals = List.sort (fun a b -> (b.Fitness).CompareTo(a.Fitness)) individuals

  11:          let accumulatedFitness =

  12:              individuals

  13:              |> List.fold_left (fun accumulatedFitness individual -> accumulatedFitness + individual.Fitness) 0.0

14:

  15:          member x.GetFittest(number, copies) =

  16:              [for i in 0 .. number - 1 do

  17:                  for j in 0 .. copies - 1 do

  18:                      yield orderedIndividuals.[i]]

  19:          member x.Individuals with get() = individuals

  20:          member x.AccumulatedFitness with get() = accumulatedFitness

  21:          member x.FittestIndividual with get() = orderedIndividuals.Head

As you can see, the Individual record consists of the Chromosome, which is a list of values; and its fitness. A generation is built with a list of individuals and immediately does two things: Stores a sorted list of the individuals and calculates the accumulated fitness.

The sorted list is created in line 10 with a call to List.sort passing in a simple function that compares the individuals according to their fitness value. I’ll go explain how these individuals are created in a later post. The accumulated fitness is simply the sum of each individual’s fitness, which we accomplish with a call to List.fold_left. The function argument simply accumulates each individual’s fitness using 0.0 as the starting value.

The properties on lines 19 – 21 should be self-explanatory. The method on line 15, however, is a bit more interesting. Its purpose is to create a list that contains several copies of the fittest individuals. You’ll see the importance of this method in my next blog post on the subject when I talk about elitism. In terms of implementation, it’s a simple list expression that returns copies copies of the number fittest individuals.

With the basic data structures covered, we can move on to our selection, crossover, and mutation algorithms.

Selection: Roulette Wheel

The selection algorithm I implemented is called “Roulette Wheel Selection”. The concept is very simple: Imagine you have a pie chart representing the fitness of all chromosomes in the current generation. If you choose a random number between 0.0 and 1.0 and, afterwards, multiply it by the total accumulated fitness (The sum of the fitness of each solution in the current generation) you could use the resulting number to stochastically choose an individual from the generation, giving a larger probability to those individuals with a high fitness value. You can visualize it as if the pie chart were really a roulette and you were dropping a ball on it. Any individual might get chosen, but those with the highest fitness value have a better chance. This ensures that, overall, the fittest individuals survive but also prevents stagnation by giving other solutions with lower fitness a chance to go through. We can also specify how many individuals we would like to select from the current generation.

The code for this algorithm is rather simple, although not as functional as I would have liked it to be. I considered implementing it using several list transformations, but it traversed the list way too many times for my liking, which led to a more imperative solution. It still showcases some nice things about F#:

   1:  #light

   2:  module RaineTech.AI.GeneticAlgorithms.SelectionFunctions

   3:      open System

4:

   5:      let RouletteWheelSelection (generation : 'a Generation) (size : int) (randomGenerator : Random) =

   6:          let generationFitness = generation.AccumulatedFitness

   7:          let rec getIndividualAtRoulette (individual : 'a Individual) (restOfGeneration : 'a Individual list) roulettePosition accumulatedFitness =

   8:              if accumulatedFitness > roulettePosition then

   9:                  individual

  10:              else

  11:                  getIndividualAtRoulette restOfGeneration.Head restOfGeneration.Tail roulettePosition (accumulatedFitness + restOfGeneration.Head.Fitness)

  12:          [for i in 0 .. size - 1 do

  13:              let roulettePosition = randomGenerator.NextDouble() * generationFitness

  14:              yield getIndividualAtRoulette generation.Individuals.Head generation.Individuals.Tail roulettePosition generation.Individuals.Head.Fitness

  15:          ]

16:

The function receives the generation from which to select the individuals, the number of individuals to select, and a random number generator as parameters. We start by storing the generation’s accumulated fitness in line 6 and then we define a recursive function that is responsible for returning the individual at a certain position in our imaginary roulette. What we do is from the first solution in the generation, accumulate the fitness of the solutions until we obtain a value greater than the roulette position we received. Once this happens, we can return the individual that made us go over. In lines 8 – 9 we simply perform that check and return the individual. If we still haven’t gone over the roulette position value, then we call recursively in line 11 passing the next solution as the first parameter, the rest of the generation as the second, the same roulette position as the third, and the result of adding the current individual’s fitness to the running total as the fourth. You can visualize this process as follows:

Solution 1	Solution 2	Solution 3	Solution 4	Solution 5
31	15	29	42	5

individual	restOfGeneration	roulettePosition	accumulatedFitness
Solution 1	[Solution 2; Solution 3; Solution 4; Solution 5]	51 (random)	31
Solution 2	[Solution 3; Solution 4; Solution 5]	51	46
Solution 3	[Solution 4; Solution 5]	51	75 (Return Solution 3)

After defining the function responsible for getting the individual at a certain position, we use a list expression in lines 12 – 15 to select the number of individuals specified by the size parameter. Within the list expression we calculate the roulette’s position by retrieving a random double and multiplying it by the total fitness. Afterwards we just yield elements returned by making calls to the previously explained function. The resulting list contains the individuals that will be ‘mated’ with the crossover algorithm in order to produce a new generation.

Crossover: Single Point Crossover

The crossover function is responsible for taking two chromosomes and ‘mating’ them. This means producing a new chromosome based on the values included in each of the chromosomes passed in to the function. One of the simplest kinds of crossover is single point crossover, which picks a certain point within the chromosome at random, called the crossover point, and takes the values from the first chromosome up to that point, and the values from the second one after that. Consider the following example with a crossover point of 3:

Father	Mother	Son
[1; 2; 3; 4; 5]	[6; 7; 8; 9; 10]	[1; 2; 3; 9; 10]

Crossover functions must produce chromosomes that are the same length as their parents and the parents must be of equal lengths (A restriction that usually applies to all chromosomes handled by a genetic algorithm). The code is very simple, as you can see below:

   1:  #light

   2:  module RaineTech.AI.GeneticAlgorithms.CrossoverFunctions

   3:      open System

4:

   5:      let SinglePointCrossover(fatherChromosome : 'a list, motherChromosome : 'a list, crossoverRate : double, randomGenerator : Random) =

   6:          if randomGenerator.NextDouble() > crossoverRate then

   7:              fatherChromosome

   8:          else

   9:              let crossoverPoint = randomGenerator.Next(fatherChromosome.Length)

  10:              List.mapi2 (fun i a b -> if i < crossoverPoint then a else b) fatherChromosome motherChromosome

The first two parameters are the chromosomes to mate. The third one is the crossover rate, which is the probability that we will in fact mate these two chromosomes. You can see this in action in line 6 where we generate a random double. If this random double is greater than the crossover rate, then we don’t mate the chromosomes and simply return the father. One of the main tweaking points in genetic algorithms is finding the right rates for your particular problem. Crossover rates, however, tend to be quite high (Keep in mind it’s a probability, which means it must have a value between 0.0 and 1.0).

On line 9 we get a random integer that must be less than the length of the father chromosome and use it as the crossover point. Afterwards we simply use the List.mapi2 higher-order function which allows us to apply a given transformation to two lists at the same time. Our function simply checks if the index is less than the crossover point. If so, then it returns the value from the first list, otherwise it returns the value from the second list.

Mutation: Insertion Mutation

After we have mated our chromosomes and generated a new population, we pass them through a mutation process. Mutation functions act on one chromosome and are responsible for making very small changes on it. Whether a mutation will be performed or not depends on the mutation rate, which is usually a very small value. Once again, it is important to tweak this rate to fit your particular problem.

Insertion mutation is one of the simplest mutation algorithms. It picks two points at random within the chromosome and then simply swaps the values in those positions. The code to pull this off is very simple, although since we are using immutable lists to represent our chromosomes it’s not quite as efficient as it could be if we were using a different data structure.

   1:  #light

   2:  module RaineTech.AI.GeneticAlgorithms.MutationFunctions

   3:      open System

4:

   5:      let InsertionMutation(chromosome : 'a list, mutationRate : double, randomGenerator : Random) =

   6:          if randomGenerator.NextDouble() > mutationRate then

   7:              chromosome

   8:          else

   9:              let sourcePosition = randomGenerator.Next(chromosome.Length)

  10:              let targetPosition = randomGenerator.Next(chromosome.Length)

  11:              chromosome |> List.mapi (fun index element ->

  12:                              match index with

  13:                              | x when x = sourcePosition -> chromosome.[targetPosition]

  14:                              | x when x = targetPosition -> chromosome.[sourcePosition]

  15:                              | _ -> element)

16:

As with the crossover function, we start by generating a random double to check against the mutation rate. In case it is decided a mutation will happen, we get two random numbers to act as the source and target of the swap. Both these numbers must be less than the chromosome’s length. Once we have those numbers we use the List.mapi to generate the resulting chromosome. The match expression returns the element at the target position if the index is equal to the source position and vice-versa. In all other cases it simply returns the current element in the map function.

Coming Up Next

Now that we have a small set of operators and data structures to work with, I will show how they all come together in the form of a genetic algorithm in the next blog post in the series. I will also mention some other selection, crossover, and mutation functions that might be more useful for certain types of problems.

Technorati Tags: F#,Genetic Algorithms,Artificial Intelligence

Parallel Quicksort in Erlang

jr.calzada.nospam@nospam.raine-tech.com (jr.calzada) — Fri, 01 May 2009 03:39:18 -0600

When I first read about processes in Erlang and how to program for concurrency within the language, I decided to write a simple parallel implementation of the well-known Quicksort algorithm as an exercise. The reason I chose this algorithm in particular is because it is, by nature, easily parallelizable. If it’s been a while since you last implemented Quicksort, here’s a short overview of what the algorithm does:

The function receives a list of elements
A pivot is chosen from this list (Usually the first element)
The original list is separated into two new lists: One that contains all elements that are less than the pivot and one that contains all elements that are greater than the pivot
The two new lists are sorted separately
The sorted lists are joined by placing the pivot between them

The step with the most potential for parallelization is the fourth one, since the the sorting of each of the two new lists is side-effect free and there is no need to share information. Because of this we should be able to simply sort the two lists concurrently, wait for both of them to finish, and then join them together as explained in the fifth step.

I’ve chosen to keep the implementation clear and make the parallelization process explicit, in an effort to make the algorithm as understandable as possible. Keep in mind, however, that it can be cleaned up significantly by delegating the process of sorting the two lists to an auxiliary function responsible for spawning the required processes, waiting for them to finish, and simply returning the results in the order expected (A parallel implementation of the well-known ‘map’ function, an example of which can be found in “Programming Erlang” by Joe Armstrong).

   1:  -module(parallel_sorting).

   2:  -export([quicksort/1]).

3:

   4:  quicksort([H|T]) ->

   5:      {Lesser, Greater} = separate(H, T, [], []),

   6:      Pid = self(),

   7:      LeftSortPid = spawn(fun() ->

   8:                              SortedList = quicksort(Lesser), Pid ! {self(), SortedList}

   9:                          end),

  10:      RightSortPid = spawn(fun() ->

  11:                              SortedList = quicksort(Greater), Pid ! {self(), SortedList}

  12:                          end),

  13:      receive

  14:          {LeftSortPid, LeftList} ->

  15:              receive

  16:                  {RightSortPid, RightList} ->

  17:                      LeftList ++ [H|RightList]

  18:              end;

  19:          {RightSortPid, RightList} ->

  20:              receive

  21:                  {LeftSortPid, LeftList} ->

  22:                      LeftList ++ [H|RightList]

  23:              end

  24:      end;

  25:  quicksort([]) ->

  26:      [].

27:

  28:  separate(E, [H|T], Lesser, Greater) ->

  29:      if H < E ->

  30:          separate(E, T, [H|Lesser], Greater);

  31:      true ->

  32:          separate(E, T, Lesser, [H|Greater])

  33:      end;

  34:  separate(_, [], Lesser, Greater) ->

  35:      {Lesser, Greater}.

You can see we match calls to the quicksort function against two cases: A list with elements and an empty list. In case of receiving an empty list we just return an empty list, there’s no sorting to be performed. If we receive a list with elements instead, we start by separating it into the two lists outlined in step three of the algorithm description. The head of the list is chosen as the pivot, which is the first argument to the separate function. The other three arguments are the remaining elements in the list and accumulators for what will eventually be the new lists. I will not explain the separate function since it should be fairly self-explanatory.

Once we have the lists, we spawn new processes that will take care of sorting them. We must first store the id of the current process, so that we can, eventually, send a message to it containing the sorted lists. The spawn function takes as its argument another function that will start by calling quicksort on one of the lists and then send a message to the parent process with the sorted list. We do the same thing for both the list with the lesser elements and the list with the greater elements.

Once these processes are spawned, the function needs to wait for the results, which happens between lines 13-24. This is the part of the code that could be cleaned up the most, but I believe it is easier to see what’s going on in its current form. We start a receive expression which will wait for messages to arrive. Since we cannot determine which of the two lists will be sorted first, we must consider both cases, which is what we specify when waiting for either a message from LeftSortPid or RightSortPid.

Once we receive either of the sorted sub-lists, we wait to receive the missing one. You can see this in lines 15-18 and 20-23. After receiving the other list we join them as mentioned in the fifth step of the algorithm outline above. This will be the result of the receive expression and, therefore, the result of the quicksort function.

On a final note, here is what the code would look like if we had an auxiliary parallel_map function:

   1:  quicksort([H|T]) ->

   2:      {Lesser, Greater} = separate(H, T, [], []),

   3:      [LesserSorted, GreaterSorted] = parallel_map(fun quicksort/1, [Lesser, Greater])

   4:      LesserSorted ++ [H] ++ GreaterSorted

   5:      end;

   6:  quicksort([]) ->

   7:      [].

Which goes to show the effect higher-order functions can have on your code.

Technorati Tags: Quicksort,Erlang,Concurrency

Scoping in Groovy Closures

jr.calzada.nospam@nospam.raine-tech.com (jr.calzada) — Mon, 27 Apr 2009 03:23:51 -0600

As I’ve been playing around with Groovy something that immediately caught my attention was the way scoping worked within closures. I came across a code example involving using closures within double quoted strings in “Programming Groovy” by Venkat Subramaniam that made it seem, for a moment, that closures actually had dynamic scoping. Dynamic scoping, in contrast to static or lexical scoping, means that the bindings in the scope of a block of code is determined not according to the source code, as is the case with most popular programming languages, but during evaluation. This pretty much means that you can have a function that uses a variable named ‘a’ and, even if you haven’t defined that variable in its enclosing lexical scope, you can call that function within another block of code that defines the aforementioned variable. The variable inside the function will actually refer to the one inside the block of code that made the call to the function.

Take a look at this Groovy code and you will see something similar happening:

   1:  def closure = {->

   2:      x

   3:  }

4:

   5:  def closure2 = {v ->

   6:      x = v

   7:      println closure()

   8:  }

9:

  10:  closure2(5)

If you execute this script you will get ‘5’ as an output, which might not be that surprising. Consider, however, that when the closure is defined in lines 1-3, it’s referring to a non-existent variable ‘x’. Lexical scoping would consider this an error, since there is no variable named ‘x’ in the code’s enclosing scope. Somehow, the closure is actually referencing the value assigned to x within ‘closure2’. One could take a look at this and think this is dynamic scoping in action, and that’s what I thought at first too… Then I started digging a bit more.

Turns out that if you delete line 6 and then rename the parameter to ‘closure2’ in line 5 from ‘v’ to ‘x’ the code doesn’t work. This makes it clear that it’s not really dynamic scoping what we’re dealing with here, since there’s still a variable named ‘x’ in the scope of the block of code that is making the call to the first closure. What’s really happening is one of the main characteristics of closures in Groovy.

Every closure in Groovy has three special members: ‘this’, ‘owner’, and ‘delegate’. The ‘this’ member is set to the object in which the closure was defined and the ‘owner’ and ‘delegate’ members are set to either a surrounding closure, if the closure is defined within another closure, or the same as the ‘this’ member. When referring to a variable inside the closure, Groovy will first look for the variable in the closure’s lexical scope, which is typical static scoping at its finest. If it doesn’t find the variable, however, it will look for it in the three members I just mentioned. In my current Groovy Console session it shows that ‘ConsoleScript50@c21095’ is the value of all three members. We already determined the closure isn’t really getting the value of ‘x’ from the scope of the call, since changing the closure’s parameter name from ‘v’ to ‘x’ doesn’t work. You might also be thinking that there is no ‘x’ variable defined in the global scope either. So, what’s going on?

It turns out that the assignment in line 6 is actually creating the ‘x’ variable in the global scope. When we assign to ‘x’ Groovy apparently looks for the symbol in the ‘this’ member which happens to be the script environment, which pretty much always allows defining new variables. So, the statement in line 6 actually creates the variable ‘x’ in the global scope and assigns to it the value passed in to the closure. You can verify this by adding a ‘println x’ statement after line 10 and you’ll see the number ‘5’ printed a second time. When the first closure is finally executed it eventually looks for the variable ‘x’ in its ‘this’ member, which is the ‘ConsoleScript50@c21095’ object, where the previous call just created a variable named ‘x’. This will allow the closure to find the symbol and get its value, which explains why this code works as it does.

The first time I came across this it struck me as somewhat obscure, but once you know what’s going on things start making sense and you realize this is actually a nifty feature. It’s also, in a way, the backbone of several meta-programming strategies in Groovy. But that’ll be a topic for another day.

Technorati Tags: Groovy

Pass by reference… It’s really not that hard, people!

jr.calzada.nospam@nospam.raine-tech.com (jr.calzada) — Fri, 24 Apr 2009 03:38:54 -0600

So, I was checking my RSS feeds and came across this post that explains, in very simple code, how Ruby and Java don’t really pass method arguments by reference, but do it by value, in contrast to what you can do in C++ by defining parameters as ‘pass by reference’.

The post is clear and well written, so I never really expected the surprisingly huge amount of crap I found in the comments section. I mean, really, this is not rocket science!

What’s happening in Java and Ruby is actually pretty simple: Let’s say you have a reference to a shiny object. This reference is, for all intents and purposes, a pointer to the actual instance that was allocated in the heap. When you pass this reference to a method, you are actually creating a copy of the reference, which is the argument the method receives. Yes, the method is still receiving a reference, but it’s not the original reference, it’s a copy. Therefore, the reference was passed by value. It’s the same thing that happens with all primitive types: You pass them to a method and the method receives a copy because they were passed by value. The only difference is that you’re creating a copy of a reference, so if you make any modifications to the object within the method those changes will affect the original object. This is because even though you’re acting on a copy of the original reference, they’re both still references to the same real object that lives somewhere in the heap. The point is that a copy of the argument is being made.

With C++’s pass by reference things are different. When you pass by reference in C++ you are not creating a copy of the reference, but you are actually passing that same reference to the method. No copy of the reference is being created. If a reference is a pointer to an object, then what the method is really receiving as an argument is a pointer to the reference (A pointer to a pointer). This is, of course, hidden from the programmer by the reference’s particular syntax, which is probably why so many programmers struggle with them and never fully understand them. But still, with an explanation as clear as the one in the post mentioned at the beginning, I just can’t believe how many people kept trying to spin it around in some misguided attempt to be right. This is not some great, new discovery, it’s been widely explored in the existing literature and is something anyone with a firm grasp on programming languages should get.

By the way, C# actually supports both. By using the ‘ref’ keyword you can actually pass a parameter by reference, which is why any assignments made to a ‘ref’ parameter affect the original value, which means the swap function implemented in the original post would actually work as intended. One way to look at is that references are really value types (I’m referring to the reference itself, not the object to which it points), so when you use a ‘ref’ parameter you are just passing a reference to the reference, just as you would with an int or any other primitive.

So, now that I have that off my chest, I’ll go back to doing something a bit more productive.

Technorati Tags: C#,C++,Ruby,Java

Wave File Information Decoder in Erlang

jr.calzada.nospam@nospam.raine-tech.com (jr.calzada) — Mon, 20 Apr 2009 07:15:48 -0600

One of the features of Erlang that immediately caught my attention was the bit manipulation syntax. Despite whatever gripes I may have with other parts of the language’s syntax, this stands out as a gem. So, as en exercise to myself I decided to write a set of functions that would allow me to extract some information from a wave file. I wanted the function to return a record that contained the file’s size followed by a list of the RIFF chunks the file contains (If you don’t know what a chunk refers to, it’s how wave files are organized. You can read more here). The chunks would be represented by a tuple that contained the chunk’s ID, its size and its data. The only exception would be the format chunk, which would be represented by a record that nicely held all its relevant values.

Since the chunks in wave files are nicely structured, Erlang’s bit manipulation syntax was a perfect fit for the task, allowing me to easily specify which bits made up which values. Here’s the source code:

   1:  -module(wave_tools).

   2:  -export([decode_wave_file/1]).

3:

   4:  -record(wave_file, {fileSize, chunks}).

   5:  -record(fmt_chunk, {id = "fmt ", size, compression_code, channels, sample_rate, bytes_per_second, block_align, significant_bits_per_sample, extra_format_bytes}).

6:

   7:  decode_wave_file(<<"RIFF", Size:32/little, "WAVE", Data/binary>>) ->

   8:    Chunks = extract_chunks(Data),

   9:    #wave_file{fileSize = Size + 8, chunks = Chunks}.

10:

  11:  extract_chunks(<<ID:4/binary, Size:32/little, ChunkData:Size/binary, Rest/binary>>) ->

  12:    Chunk = build_chunk(ID, Size, ChunkData),

  13:    if

  14:      Size rem 2 =:= 0 ->

  15:        [Chunk|extract_chunks(Rest)];

  16:      true ->

  17:        <<_:1/binary, Rest2/binary>> = Rest,

  18:        [Chunk|extract_chunks(Rest2)]

  19:    end;

  20:  extract_chunks(<<>>) ->

  21:    [].

22:

  23:  build_chunk(ID, Size, Data) ->

  24:    case ID of

  25:      <<"fmt ">> ->

  26:        extract_fmt_chunk(Size, Data);

  27:      _ ->

  28:        {ID, Size, Data}

  29:    end.

30:

  31:  extract_fmt_chunk(Size, <<CompressionCode:16/little,

  32:                            Channels:16/little,

  33:                            SampleRate:32/little,

  34:                            BytesPerSecond:32/little,

  35:                            BlockAlign:16/little,

  36:                            SignificantBitsPerSample:16/little,

  37:                            Rest/binary>>) ->

  38:    ExtraFormatBytes = case Rest of

  39:                         <<NumberExtraFormatBytes:16/little, EFB:NumberExtraFormatBytes/binary>> ->

  40:                           EFB;

  41:                         _ ->

  42:                           <<>>

  43:                        end,

  44:    #fmt_chunk{size = Size, compression_code = CompressionCode, channels = Channels,

  45:              sample_rate = SampleRate, bytes_per_second = BytesPerSecond, block_align = BlockAlign,

  46:              significant_bits_per_sample = SignificantBitsPerSample, extra_format_bytes = ExtraFormatBytes}.

The first few lines are very simple, the only interesting parts being the record definitions. The only function being exported is ‘decode_wavefile’ which relies on the other functions to correctly decode the data passed in. You can see the function argument is matched against a bit pattern which specifies that the data must contain the letters “RIFF” followed by four bytes that represent the file size (minus eight). After the file size we expect the letters “WAVE” and we wrap up by binding the ‘Rest’ variable to the rest of the data. Once this is done the function calls the ‘extract_chunks’ function and then fills out the ‘wave_file’ record.

The ‘extract_chunks’ function that starts in line 11 is a bit more interesting. We use some more matching to extract the chunk’s ID, its size, the data, and whatever’s left. We want to capture the size as an integer in order to use it cleanly when specifying how many bytes to match for the chunk’s data. Wave files are stored in little-endian order, so we specify that to retrieve the correct result. With this data extracted we call the build_chunk function and then check whether the chunk’s size is even. Since chunks in a wave file have to be word-aligned, whenever a chunk’s size is odd we need to skip a byte that is used as padding after the data. After figuring that out we just build a cons cell that contains the retrieved chunk and whatever chunks can be extracted from the rest of the data. This could be turned into a tail-recursive call by using an accumulator argument, but I think this is a bit more readable. We must also take into account that eventually there will be no more data from which to extract a chunk, in which case we return the empty list.

The ‘build_chunk’ function simply checks whether the ID matches “fmt “ or not. If it doesn’t then we just build a tuple containing the ID, the size, and the data; if it does then we call the ‘extract_fmt_chunk’ function which performs a pretty long, though straightforward, match against the data. We start by extracting the compression code, the number of channels, the sample rate, the average bytes per second, the block alignment, the number of significant bits per sample, and whatever information is left. Format chunks can sometimes hold additional format bytes, but this field is entirely optional. Because of this, we match ‘Rest’ to either 2 bytes that specify a size followed by the adequate number of bytes which would be the extra format bytes, or against nothing in which case there are no extra format bytes. Once that’s done we’ve extracted all of the information in the chunk and simply proceed to filling out the record.

As you can see, most of the code is rather straightforward if you’re familiar with the syntax. The bit manipulation syntax seems to be extremely powerful and impressive, making tasks that would be daunting or tedious in other programming languages entirely trivial. I’ll keep playing around with Erlang a bit more, maybe if I come across enough stuff that’s as good as this I’ll get over some not-so-nice aspects of its syntax.

Technorati Tags: Erlang

Wedding Invitations Are Here!

jr.calzada.nospam@nospam.raine-tech.com (jr.calzada) — Sun, 19 Apr 2009 01:23:00 -0600

Things have been a bit busy lately and I also have been feeling a bit under the weather so I haven’t been able to post as often as I would’ve liked. Aside from that, things have been progressing smoothly and hopefully will continue to do so for the next couple of months.

The wedding is now less than a month away and am pretty excited. We finally received the wedding invitations, after a slight delay, and they should be going out in the next couple of days which means people will stop asking me why I didn’t invite them. They came out pretty great and it’s fair to say the delay was worth it.

On a more blog-related note, I do have a few blog posts waiting to be finished and published. I’m working on a post about formal methods and how we can include certain aspects of them into our typical development workflows in a way that we can reap many of their benefits, yet without having to go to extremes. I’m also working on a blog post that talks about F#’s asynchronous workflows, which is a wonderful feature when working with asynchronous methods in .NET.

Hopefully I’ll be able to get those two posts finished before the end of next week. I’ve been trying to do at least eight posts per month, but it looks like I’m not gonna make it this time. Hopefully I’ll get some time next month to make up for that.

WPF Dispatcher Decorator in IronPython

jr.calzada.nospam@nospam.raine-tech.com (jr.calzada) — Wed, 08 Apr 2009 14:32:46 -0600

Lately I’ve been working on an application hosting environment that dynamically loads applications written in IronPython and provides them with certain infrastructure. Windows Presentation Foundation is being used throughout and hosted applications are required to provide, at least, two classes: An application controller and a user interface. The application controller class will receive an instance of the application’s UI from the hosting environment and from that instance it can decide which events to handle and call methods on the UI that perform certain modifications. In one of the applications I’m working on, most of the actions taken by the controller are in response to asynchronous communications through a network, which means that the code will actually be executing on a different thread (The callbacks passed to the BeginSomething methods in the .NET framework execute in another thread to avoid blocking the main thread, something essential in UI applications).

If you have some experience with WPF, you may know that only the UI thread can make modifications to the UI and that if you want to make changes from another thread, then you need to use a Dispatcher object to which you pass a delegate containing the code to execute. This code will, eventually, execute in the UI thread. There are no surprises when doing this from IronPython, fortunately, but I thought it would be nice to have a way to take care of this issue without adding unnecessary code to my methods. That’s where decorators come in.

What I wanted was a decorator that replaced functions with equivalents wrapped in a Dispatcher. To pull this off we need to define a delegate since the Dispatcher.Invoke call receives an instance of System.Delegate. We need to make this delegate available to IronPython, which means adding a reference to whatever assembly owns it and then importing it from its namespace. I named my delegate DispatcherDelegate and will, from now on, infer its available when showing the code. In my case, the dispatcher object itself was also being made available by the hosting environment in a variable named “__uiDispatcher__”. Your best bet is to store the dispatcher in the global scope inside the module that needs to use the decorator.

The first logical version of the decorator code is probably as follows:

def uiModifier(function):
  def dispatchedFunction(*args):
    __uiDispatcher__.Invoke(DispatcherPriority.Render, DispatcherDelegate(function), *args)
  return dispatchedFunction

If you do this, however, IronPython will choke with a ParameterMiscount exception. For some reason the multiple arguments are not extended correctly when passing them in place of the ‘params’ parameter. The solution is simply to use another internal function that invokes the function passed in by closing over the parameters and then use the dispatcher to invoke this additional internal function that takes no parameters. The result is the following:

def uiModifier(function):
  def dispatchedFunction(*args):
    def inner():
      function(*args)
    __uiDispatcher__.Invoke(DispatcherPriority.Render, DispatcherDelegate(inner))
  return dispatchedFunction

This solves the problem wonderfully and allows me to simply write “@uiModifier” over any function that needs to work on the UI from a different thread. This little function can be easily extended to allow the decorator to take the DispatcherPriority as an argument, but I’ll leave that one out for now. In the case of my project, this significantly improves the development experience from the hosted applications’ point of view. I hated those few extra lines that had nothing to do with what I wanted to do and was delighted to find them reduced to a simple line at the top of the relevant functions. I hope you’ll find this useful as well.

Technorati Tags: IronPython,WPF

Memoization… And an example in IronPython

jr.calzada.nospam@nospam.raine-tech.com (jr.calzada) — Mon, 06 Apr 2009 03:59:20 -0600

Memoization is one of those programming techniques that make an awful lot of sense in theory yet I almost never see in practice. For those not familiar with the term, memoization refers to maintaining a store of function results so that when a function is invoked several times with the same arguments the result can just be retrieved from the store instead of being computed every single time.

This technique can have huge performance implications for doubly recursive functions, like the typical Fibonacci implementation. You can find a typical and naïve Fibonacci implementation in Python below:

def fibonacci(n):
  print "Calculating Fibonacci"
  if n <= 2:
    return 1
  return fibonacci(n - 1) + fibonacci(n - 2)

The print statement is there so you can see the result of invoking this function on large numbers. The number of times “Calculating Fibonacci” is printed increases from 3 for n = 3 to 41 for n = 8. This means that when calculating the eight fibonacci number the function is executed a total of 41 times. Try calculating the 30th fibonacci number and you’ll see why the constant re-computation of values is not feasible. Memoization is an elegant solution to this problem (Although for our current example you could just implement the algorithm iteratively, but a high computation cost can come from many different places). Below is a solution that applies this technique:

fibonacciValues = dict()
def fibonacciMemoized(n):
  print "Calculating Fibonacci"
  if n <= 2:
    return 1
  elif fibonacciValues.has_key(n):
    return fibonacciValues[n]
  else:
    result = fibonacciMemoized(n - 1) + fibonacciMemoized(n - 2)
    fibonacciValues[n] = result
    return result

This version only prints “Calculating Fibonacci” 13 times compared to the 41 times of the previous version for the eighth fibonacci number. It also has the nice feature that the second time we request the eighth fibonacci number or any other number that was calculated previously there is no computation required. The code has several drawbacks, however. First amongst them is that the function requires an external dictionary to store the results. One can also see that the memoization code makes the function quite a bit less understandable than our original version. We are also mixing code with two different purposes, one of which is a simple optimization detail. It turns out there is a very easy way to do away with these problems and that is by using a function that is responsible for generating a memoized function.

def memoize(function):
  results = dict()
  def callFunction(*args):
    if results.has_key(args):
      return results[args]
    result = function(*args)
    results[args] = result
    return result
  return callFunction

This function builds an internal dictionary which is then closed over by the internal function. The internal function is defined to take a variable number of arguments which are used as the key to the previously created dictionary in order to store the values (Notice that when using the arguments as a key we use them in their tuple form and only expand them when using them to call the function). If there is no result for a particular set of arguments in the dictionary then the function is called and its return value stored. The internal function is returned so that it can be used. Here’s how you would use it:

memoizedFibonacci = memoize(fibonacci)
memoizedFibonacci(8)

If you do this, you might be surprised to find “Calculating Fibonacci” printed 41 times again. Weren’t we supposed to use memoization to avoid computing a certain value so many times? The reason this happened is that the memoize function has no control over the function that is passed in and if that function makes additional calls to itself then these additional calls are not going through our memoization mechanism. This means that, effectively, we are only applying memoization to the top-level call. The good news is that if you execute that last line of code again, you’ll get an immediate result with no computation, which means it is still kind of working.

What we need to get a perfect version is to re-bind the function’s name to the memoized version, making sure that each and every call to that function goes through the memoization mechanism. Turns out there is a very nice way to do this in Python which also makes enabling the memoization technique on any function a breeze. The trick is to use decorators and make sure that the wrapping function used as the decorator performs the memoization. Let´s re-define the fibonacci function to use the decorator.

@memoize
def fibonacci(n):
  print "Calculating Fibonacci"
  if n <= 2:
    return 1
  return fibonacci(n - 1) + fibonacci(n - 2)

If you execute this version with 8 as an argument as before, you might be surprised to find this one performs even better than the first memoized fibonacci we implemented (The previous version never performed any memoization when 1 or 2 were passed in as arguments). It also takes care of any issues regarding readability since the only modification we have to do is to add the decorator. This is still, of course, a relatively rough implementation. It could be improved by providing mechanisms to control in some way the stored values so that we could clear them when appropriate. This can be done by returning objects of custom callable classes that implement the desired methods instead of functions from the decorator function, but this post is already a bit on the long side so I’ll let you figure that one out.

Although it’s true that memoization is not always applicable (And downright dangerous when applied to functions with significant side-effects) it can be a nice way to reduce computation of redundant values and, best of all, can be implemented rather elegantly. Hopefully you’ll find some use for it in your programming endeavors.

Technorati Tags: Memoization,IronPython,Python

The joys of sharing the world with trolls

jr.calzada.nospam@nospam.raine-tech.com (jr.calzada) — Wed, 25 Mar 2009 19:52:29 -0600

There’s one thing I can’t seem to wrap my head around, no matter how hard I try: Senseless trolling. Do these people actually think that their hate-ridden, poorly written, fanatical diatribes actually matter or make much of an impact beyond giving like-minded so-called individuals an incentive to swim around in each other’s crap? It’s just a bunch of uninformed self-righteous crap that serves no purpose but to inflate the author’s ego while he and his buddies keep participating in this pathetically ridiculous circle-jerk.

Well, now that I have that off my chest, I’ll gladly apologize for the language in the previous paragraph. But it does infuriate me to come across such worthless arguments so often when all they do is reinforce certain stereotypes and brew hatred amongst what would otherwise be simply consumers. Yet, for some reason, some people find it necessary to use unfounded hyperbole in an effort to validate whatever choice they make regarding what software they install on their machines.

Sometimes it seems like the overall internet population never left and will never leave puberty…

BTW, go here for the actual facts.