Possible Design for a Machine Learning/Evolutionary Algorithm Library

My newest idea for a Machine Learning/Evolutionary Algorithm library in Haskell is to separate the problem into two levels.

The first is a level of plumbing to connect genetic operators, for example, that allows the user to store state, parameters to the algorithm, to write to a log, and, since these algorithm are stochastic, random number generation. This will be implemented as what I'm going to call the Stochastic Reader Writer State Monad (SRWS), which is just the RWS monad with another State keeping a seed for the random number generator. This provides the functionality one would expect for one of these algorithms, but I don't plan on enforcing any conditions on exactly what context, state, or log one actually keeps. These will have to be filled in for each algorithm, although I plan on writing some default ones for basic Genetic Algorithms and maybe Gene Expression Programming.

The burden is on the user to make sure that parameters that don't change are stored in some sort of context, that they have a data structure to hold their state, and that they insert writes to the log where they want. This is the weakness of this approach that I tried to avoid in my last attempt at writing a library like this. It seems like each algorithm will have to duplicate a lot of data and have its own, possibly large, data structures for things like generation count or probability of mutation, even if it is only a small extension of Genetic Algorithms. I think the way around this is to provide a separate specialization of the generic plumbing for each algorithm type, along with some classes like GenerationCount with functions like s -> Int with s the state, which says it has some generation count without specifying how to extract it. This is basically like a getter in OO, and I'm not sure that I'm not just regressing to my imperative thinking with that design. Perhaps there is something nicer out there? Lenses, maybe?

The second layer of this library would be some sort of mechanism for constructing these algorithms. I don't think that this layer has somehow capture the nature of the algorithm, or even be the most direct was of specifying it. Right now, my focus is just to give a single, coherent way to build bigger algorithms out of little pieces. If the ideas are simple and composable then I would be satisfied, even if I expect they will not be the most efficient. My current plan is to use this idea of composing machines to build the necessary operators. I'm not entirely sure what form the machines will take, but I've been playing around with several possibilities, and I hope to post about some of them soon.

To give a simple example of how the concept of little machine could be applied here, I'm going to describe how I envision building the usual GA. Assuming a bit vector representation for individuals, the bits would be (conceptually) little machines that, when provided a number between 0 and 1, would output a 0 or a 1, possibly changing some internal state. This internal state will probably be accessible, but with some of the schemes I've looked at it is not visible (see http://en.wikibooks.org/wiki/Haskell/StephensArrowTutorial). Selection will be a function that, given a population with fitnesses for the individuals, returns a machine that, given a number between 0 and 1, will return an individual. Repeating this process to get pairs of individuals, we would construct a machine that, given a number between 0 and the length of the individuals, would return a pair of crossed individuals. Notice that these machine are really just functions, but they store information about what actions they take along with their data. This is, again, somewhat like OOP. The advantage here is that it provides a single concept with which to express the operators, and it localizes the information about how they work, so that it may be easy to automate.

In addition to developing some of the ideas for how to define these ideas, I hope to make clear why I think this idea is useful at all (which I imagine isn't clear at first, even with (maybe because of?) this example). Just a simple look ahead- the result may end up just being the SRWS monad just like the outer layer, but perhaps with a little extra structure or another wrapping.

Haskell News Quotes

Some quotes from the quote of the week on #haskell, posted on Contemplating Code.

hpc: and when you want to get really ridiculous, agda has universe polymorphism, which is when you don't know how high up the tower of turtles you have managed to climb
RaptorRarr: Analogy puzzles are to intelligence as __________ is to elephants
[djahandarie] Group projects are stupid [shachaf] Try a semigroup project sometime. You need to lose your identity.
heatsink: Maybe, (), and Bool go to the Lone Star Bar. The bouncer stops Maybe and says, "we don't serve your kind here."
Jafet: Can oleg create a term so complicated that even he could not type-check it?
elliott: i'm here to prove theorems and compile code and I'm all out of code
kmc: my algorithm is O(1), but the constant factor grows quadratically as the problem size increases
luqui: Haskell is a DSL for writing monad tutorials.
spoolio: Haskell programmers know the cost of nothing, the type of everything, and might know the value of a few things later.
James Cook: I think Haskell questions on SO tend to the opposite extreme; no matter how poorly thought-out the question, the Haskell community will descend on it like a swarm of helpful piranhas.
djahandarie: Category theorists are morphisms for turning cofree theorems into free theorems.
monochrom: the road to haskell is paved with good abstractions
ddarius: Attempting to join #not-not-math sent me to #math. Freakin' Boole.
monochrom: @let germanize = concat . words

Forth Interpreters and the C Stack

I haven't been working on my Forth project for a while, but I'm coming back around to it recently, and there are some things I want to change. One of these things is to start using a variation on a technique I saw in the paper "Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine". In this paper they give a single line interpreter for their machine: "while (TRUE) { cont = (*cont)(); }" which simply calls the function pointer cont, and expects the function to return a new function pointer. This has the advantage of always cleaning the stack up after every function call, preventing it from overflowing or from having to throw it away occasionally.

The plan as of right now is that instead of always returning the next thing to call, the looping interpreter will simply do the action of "next"- it will copy the current IP (Instruction Pointer) onto the return stack, copy W into IP, increment IP, and call the function W points too. All functions will return nothing and the threading will be taken care of for them- they do not have to each have the code of "next" as I've done in the past.

I'm also going to change how the original dictionary is compiled. Before I was doing some pretty tedious manipulation of an array of cells (integers) for some reason. Instead of this, I will use a word struct of fixed length (the name will be a pointer to a character string rather then the string itself- this makes finding the xt of a word easier). I don't know why I didn't do this before, but it should be simpler and cleaner now.

I've been thinking about what I'm going to do for structures in this Forth. I don't want to use objects particularly, so I'm going to be thinking about how to do reasonable algebraic datatypes in Forth. It will probably involve runtime checking of types. I've devised a scheme for doing classes in the Haskell sense which I will post about, but its in the planning stage and I may abandon the idea at any moment.

I'm looking forward to cleaning up the implementation and getting it actually running so I can start exposing hardware functionality and adding threading, interrupts, etc.

McCarthy's 91 Function in Haskell

I've been reading a lot of articles on wikipedia on different topics of the theory of computation today, and I happened across one on the McCarthy 91 function. This function over the natural number is very simple- f(n) = n - 10 if n > 100 and f(n) = M(M(n + 11)) otherwise.

A proof that M(n) = 91 for all 0 >= n > 101 in Haskell is pretty concise:
m n | n > 100 = n - 10 | otherwise = m $ m $ n + 11
all ((91 ==) . m) [0..101]
Which evaluates to true.