Revisiting old concepts

In an old post I threw out the perspective that typeclasses & exokernels are similar ideas, but I explained it so pithily I think it was more or less incomprehensible. Honestly, even I had to sit & think for a minute to figure out what I meant over a year ago.

The idea wasn't really that profound, but did amuse me a little.

Let's say that you design a type class called Hardware, maybe even require that it be a monad or at least applicative, that includes all of the functionality you'd want from an exokernel, i.e. protection & raw handling of resources. You should also define a set of algebraic properties that you want all of these operations to satisfy in practice.

Any actual instance of this type class that satisfies all of our conditions is an implementation of an exokernel.

Then your libOS, the part that does all the nasty work of management of resources, can be polymorphic over the implementation and only work with the basic protection interface defined by the type class.

This whole business occurred to me a long time ago because of reading the original House paper and their discussion of the H monad. They don't quite take it in this direction, but I think that it seems feasible.

I'm being a little hand-wavy, though, because this isn't something I've
actually tried to make. It just seems like a compelling bit of imagery & possibly a good idea for organizing a kernel.

A serious problem

Hello,
I'm Creighton Hogg and I want to talk to you about typeclass abuse.

Like any form of substance abuse it may seem harmless at first, a way
to recapture the old feelings of modularity you had during your
object-oriented youth; however, you'll quickly find yourself twisting
and obfuscating your code to design the signatures of your typeclass
methods so that they can cover a wide swath of cases that are
fundamentally dissimilar.

Have you noticed signs of:
1. Obsession over reuse of the names of functions?
2. Attempts to use typeclasses to try and treat collections of
dissimilar objects as though they were the same?
3. A frequent need for typeclasses with two or more type
variables?

If so, you may be in grips of typeclass abuse. Please keep the
following in mind as you attempt to deal with your problem.

First, if you want to have a collection of objects that are treated
differently by functions, please consider using an Algebraic Data Type
instead. For more fine grained control over your data types, you may
want to look into GADTs.

Second, if you are needing a number of classes with two or more type
variables, consider that you may be attempting to use a language feature
designed to enable polymorphism to handle extremely specific and
dissimilar cases. You are working against the grain of the language,
and should probably simply accept that you can't overload a function
name to be 20 different functions that each do different things.

Lastly, if you're not actually sure if a typeclass would make your code
more convenient, why not just try writing your code without it? When
you've got a number of use cases down, then maybe you can decide on what
the proper abstraction is.

This message paid for by the Foundation To Get Creighton To Stop Abusing
His Code, a non-profit organization.

Brief updates

So two quick notes:

1. I've been working on my Haskell bindings to BlueZ and I can now detect my wiimote. I can't read anything from it or tell it to do anything, but I know it's there. I'm hoping to have some kind of actual release done next week.
2. Any political candidate who starts talking about how "great" our country is should be poked in the eyes, 3 Stooges style. We know you like the place or you wouldn't be running for office and if you keep talking about how great things are you look like you don't have ideas to make it better. Seriously.
   

A silly example and a brief history

So there's a few things I've thought about lately, and I wanted to bring back one of the first things I ever wrote in Haskell as a launch point.

I think I've made reference to this a few times, but in grad school I worked in experimental particle physics. I left with a Master's after three years when I realized that the field just wasn't going to be right for me. It was in particle physics that I got my first introduction to programming. I was exposed to C++ and Fortran 77 as my first languages. The funny thing is that back then I thought that programming was something difficult and scary, far more so than QFT or category theory.

I was utterly dumbfounded when I tried to read the source code of Pythia, the biggest event generator we used, and waded through the tens of thousands of lines of Fortran 77. I came away with the impression that even basic concepts such as Monte Carlo integration were far too difficult for me to understand. After working on a small emulator for detector logic in C++, my first real software project, I started to feel more comfortable with the idea that I could actually understand the Crazy Witchcraft that is programming. I also started wondering if there were other tools out there that were better than C++.

The first language that really intrigued me was Ruby, but while working through the Pickaxe book I then started wondering if it was possible to go beyond Ruby's blocks and start really passing functions to other functions. After spending a little time on The Google, I came across both Common Lisp and Haskell. Haskell seemed really neat, but was rather strange for someone who was entirely self-taught in Fortran and C++. One of the first semi-interesting code snippets I wrote in Haskell was the classic example of estimating pi Monte Carlo style.

> import System.Random
> import Control.Monad
> import System.Environment
>
> main' = do
>   [n] <- getArgs
>   let n' = read n 
>   ps <- replicateM n' generatePoint
>   print $ 4 * (fromIntegral . length . filter (\(x,y) -> x^2 + y^2 <= 1)) ps / (fromIntegral n')
>
> generatePoint :: IO (Double,Double)
> generatePoint = do
>   x <- randomRIO (-1,1)
>   y <- randomRIO (-1,1)
>   return (x,y)

Now, I'm not saying that this code was good, and I know I could do a lot better, but it does run and it was the first time I looked at code I had written and said oh, I guess that wasn't so hard. It had actually been really straight forward, far more straight forward to me than Fortran. It made more sense.

It felt more like math. Math makes sense to me. Abstract algebra, category theory, etc. feel comforting to my brain.

In the almost two years since I left grad school, I've done spurts of programming and studying CS and math. Until recently, I had pulled a bit of a Joel Reymont and switched which tools I used for projects on an all too frequent basis. For the past couple of months, I've really settled down on Haskell as my tool of choice. Why? Because it's the most math like programming language I've used. It makes more sense. It encourages abstraction in the math sense.

Huh? What's that supposed to mean?

Look at abstractions such as Functors, Monads, Applicative Functors, Arrows, etc. In programming, abstraction is normally about not having to repeat yourself or about making code more modular. Sure, the Monad typeclass does both of those things but it also encodes much more. It encodes algebraic information about programs, about how our programs behave under transformation and calculation. That's mathematical abstraction: reducing your problem to structures that are as general as possible, using only the most basic rules that you need to accomplish your proof.

So that's kind of my history and current thoughts on programming. I'm still learning a lot right now, but it's a lot more fun than I'd ever thought it'd be back when I was still in grad school. Haskell has proved to be a rather enjoyable intersection point between the pragmatic and the mathematic.

...at least until Epigram 2 is done.

Working through Genetic Programming

> import Random
> import Control.Monad
> import Control.Monad.Random
> import Data.Ratio
> import Data.List (sortBy)

So I really did accomplish my reading of the first three chapters of Koza's first book on Genetic Programming the week I said I would, but I sat on this post for a good bit afterwards. There wasn't a lot of meat in those initial chapters except for a few salient points:

1. Genetic programming can give you good answer if you're willing to accept that the answer is not 'correct', merely accurate and if you're willing to lay aside preconceived notions of beauty in your solutions.
   
2. Due to the schema theorem, a genetic recombination/fitness based search can effectively cover a large swath of the solution space with a small population.
   

The majority of Ch. 3 of the book is devoted to Old School genetic algorithms and the schema theorem. I'm not going to bother going through fully fledged examples of the schema theorem, but I think the point can be understood fairly intuitively: when you proportionally select the fittest specimen to be in the mating pool of each generation, you are making judgements about the fitness of patterns of genes and thus gather information about not just the specimen you have but all the possible specimen that have overlapping genetic structure.

What I want to do in the rest of this post is just write my own tiny, not terribly well-featured, genetic algorithm implementation. I'm hoping that this will provide not only more practice for me, but also be instructive to others. I base the implementation more upon the heuristic description that Koza gives than on anything else and make no claim that this is any kind of optimal construction.

First, since I hope to express my code at least somewhat generically between genetic algorithms and genetic programs, I'm going to define a typeclass to capture the basic behavior required of a "genetic" structure. Also, it is worth noting that in this post I'm going to make gratuitious use of the Control.Monad.Random library just because it feels somehow appropriate to be doing these calculations in a monad.

> class Genome a where
>     mutation :: MonadRandom m => a -> m a
>     recombination :: MonadRandom m => a -> a -> m (a,a)
>

Oddly enough, that didn't seem too terrible. We have no notion of how often something like mutation in the typeclass, because that should be controlled at the level of the actual implementation.

Now, though, we'll define an instance of this class for lists as that's probably the easiest thing to do. I do, however, make the implicit assumption that in a given simulation all the specimen are of the same length.

> 
> instance Random a => Genome [a] where
>     mutation xs = do
>                   i <- getRandomR (0,length xs - 1)
>                   x' <- getRandom
>                   return $ replaceAt i xs x'
>     recombination xs xs' = do
>                          i <- getRandomR (1,length xs - 2)
>                          let (xs1,xs2) = splitAt i xs
>                              (xs1',xs2') = splitAt i xs'
>                          return (xs1++xs2',xs1'++xs2)
> replaceAt i xs x = xs1++[x]++(drop 1 xs2)
>               where (xs1,xs2) = splitAt i xs

At this point we can start putting together the real framework for a genetic algorithm run. The first, and relatively easiest function to compute will be the one to choose the mating pool for the next generation given a fitness function and a list of specimen. I assume a constant population size for the course of the simulation, so the outgoing list will have just as many members as the in going list. We also do our selection based entirely upon the relative fitness between the specimen of the population, an idiom captured quite well in the fromList function in the Control.Monad.Random library.

> chooseMatingPool :: MonadRandom m => (a -> Integer) -> [a] -> m [a]
> chooseMatingPool eval pop = replicateM l $ fromList weighted
>     where weighted = map (\p -> (p, eval p % 1)) pop
>           l = length pop

Now I'll admit that I'm limiting the fitness function a little by requiring it to return Integer values, but I honestly feel like that's a generality that I'm willing to lose for the purposes of this post and for the convenience of using fromList.

Next will be the handler that sexually recombines the mating pool. I cheat a little here and presume that since the order of the mating pool was selected randomly that I don't need to shuffle them any more when I perform the selection and thus I can just take pairs of specimen, breed them, then put them back in the list. If there's an odd man out, or as I like to call him "Creighton in High School", then we don't breed him with anyone and just put him back in the pool.

The function to implement mutation in the population is also extremely trivial so I'll throw it in below without much ado.

> breed :: (MonadRandom m, Genome a) => [a] -> m [a]
> breed [] = return []
> breed (x:[]) = return [x]
> breed (x:y:xs) = do
>   (x',y') <- recombination x y
>   xs' <- breed xs
>   return $ x':y':xs'
>
> mutate :: (MonadRandom m, Genome a) => Double -> [a] -> m [a]
> mutate chance pop = mapM (mutate' chance) pop
>     where mutate' c a = do
>             result <- getRandomR (0,1)
>             if result < c then mutation a else return a 

Alright, so the next minor hurdle is going to be generating the initial population we need. Now, my cheating with lists has painted us into a slight corner where we can't be as generic as we'd like. The problem is that there are two conflicting imperatives at work here. First, that lists are a very convenient way to deal with sets of genes. Second, that the lists in a single simulation must all be of the same size. The result is that I can't write any generic instance such as

  instance (Random a) => Random [a] where
    ...

useful in all instances, since I want to be able to use different size lists, or arrays for that matter, for different simulations. What would be the slickest solution? Depedently typed arrays with the size as a part of the type. However, in a world without dependent types we can still write something that works even if the lack of clean semantics annoys me.

In any case we can now start wrapping the whole thing up a bit more into larger control structures. I think these are fairly straight forward, but the main function is runSimulation. It takes in the number of runs to execute, the performance threshold for declaring an early end, the probability of mutation, the evaluation function, and the initial population. That's a lot of parameters!

> randomList :: (Random a,MonadRandom m) => Int -> m [a]
> randomList i = liftM (take i) getRandoms
>
> initialListPopulation :: (Random a, MonadRandom m) => Int -> Int -> m [[a]]
> initialListPopulation s l = sequence $ replicate s $ randomList l
> 
> simulationStep :: (MonadRandom m, Genome a) => Double -> (a -> Integer) -> [a] -> m [a]
> simulationStep mut_chance eval pop = chooseMatingPool eval pop >>= breed >>= mutate mut_chance 
>   
> maxInPopulation :: (a -> Integer) -> [a] -> (a,Integer)
> maxInPopulation f = head . reverse . sortBy (\(_,w) (_,w') -> compare w w') . map (\p -> (p,f p))
>
> runSimulation :: (MonadRandom m, Genome a) => Int -> Integer -> Double -> (a -> Integer) -> [a] -> m a
> runSimulation 0 _ _ eval pop = return $ fst $ maxInPopulation eval pop
> runSimulation runs threshold mut_chance eval pop = do                               
>                    if snd (maxInPopulation eval pop) >= threshold 
>                       then return $ fst (maxInPopulation eval pop)
>                       else do
>                            newpop <- simulationStep mut_chance eval pop
>                            let finalpop = takeBest eval pop newpop
>                            runSimulation (runs-1) threshold mut_chance eval finalpop
>
> takeBest :: (a -> Integer) -> [a] -> [a] -> [a]
> takeBest eval xs xs' = take (length xs) . reverse . sortBy (\p p' -> compare (eval p) (eval p')) $ xs++xs'

Now we have enough framework in place that we can introduce an actual, executable, example. In accordance with a tutorial I saw once, we'll evolve the string of all 'True's as a quick test.

> evalOnes :: [Bool] -> Integer
> evalOnes = foldr (\b s -> let v=if b then 1 else 0 in v+s) 0
>
> main = do
>   p <- initialListPopulation 50 20
>   final <- runSimulation 200 20 0.01 evalOnes p
>   print final

I've done some preliminary testing and found that for this size of problem it still quite often finds the list of 20 Trues within the 200 generations. I'm sure if I played a bit more with how the population was chosen I could get it to be much more optimal, but I plan to worry more about that when I tweak my code to accommodate monotypic genetic programming instead of just fixed length genetic algorithms.

Random Thoughts and Idle Speculation

So first off, I found this code extremely easy to write. Now that I'm pretty much using Haskell for all of my personal projects and toys, I've come to appreciate just how effortless writing code starts to feel. It's just a language that stays out of my way when I'm trying to figure out a problem, and that's about the best compliment I think I can give a tool.

Also, as I've continued reading Koza's book I'm starting to wonder about what exactly makes genetic programming so much more powerful than straight up genetic algorithsm. I'm guessing it really comes down to the richness and varying size of the structure being evolved rather than the fact that you're evolving a parse tree. There's some ideas tickling at the back of my head about what about qualities a data structure, a functor, needs to satisify to be "evolvable". Hopefully I'll be able to clarify some thoughts about that as I continue reading the book.

Some first steps with Data.Reactive

I've had a pretty busy last week and I began to go down the path of neglecting my poor, tiny blog. Don't die on me, tiny blog! I will grant you the content you desire to make you happy!

Alright, so a friend of mine asked me about Data.Reactive a few days ago and I wanted to share a couple of small examples and even questions about the proper use of this library.

For those who haven't seen it, Conal Elliot has made a slightly brain-twisty new library for doing functional reactive programming, i.e. a way to make interactive programs with clean semantics. What follows is my attempt to make a simple chat server that uses Data.Reactive to handle logins and echoing text. I'm partly cribbing from a good example on haskell cafe and unabashedly borrow some of Mr. Stephen's function definitions. I'm not claiming this is a good example of using Data.Reactive, only that it merely works and this was my way of learning about the library. If anyone with more experience can comment as to my use/misuse of the Conal's work, it would be most appreciated.

> module Main where
>
> import Control.Concurrent
> import Control.Concurrent.STM
> import Control.Applicative
> import Control.Monad
> import Data.Reactive
> import Network
> import System.IO
>

The function socketServer is going to be our introduction to using Events in Data.Reactive. It returns an event source that we can use to grab handles as they are created by the acceptConnection function. An important point that I found embarrassingly confusing is that you don't need to do any plumbing between the event and sink. The sink is just a function of type a -> IO () that populates the event whenever it is called. acceptConnection is just a simple function that accepts the the connection then passes that into the sink that we created with mkEvent.

> socketServer :: IO (Event Handle)
> socketServer = withSocketsDo $ do
>                  (event,sink) <- mkEvent 
>                  socket <- listenOn (PortNumber 5000) 
>                  forkIO $ forever $ acceptConnection socket sink
>                  return event
>
> acceptConnection :: Socket -> (Handle -> IO ()) -> IO ThreadId
> acceptConnection s sink = do
>   (h,_,_) <- accept s 
>   hSetBuffering h NoBuffering
>   forkIO $ sink h

Now seeing these functions, you might be wondering what you need to do to get at the data in the event that's returned by this function. Well, we only have to take a look at the documentation for Data.Reactive on hackage to see that Event is an instance of Functor and that this functor instance allows us to lift a function of type a -> IO b to a function Event a -> Event (IO b). Looking at the documentation again, we find a wonderful little function called runE that has type Event (IO b) -> IO a so lets put these together into one tiny program.

> main' = do
>   e <- socketServer 
>   runE $ fmap (\h -> print h >> hClose h) e

This is a pretty braindead example, but it will print a line to stdout every time that a new connection is made to the server. Now lets go ahead and make it so that as new events occur we launch a connection handler that allows us to turn this into a real chat room. We'll also, just to be gratuitous, also use events to manage the incoming messages and their distribution.

> main = do
>        e <- socketServer 
>        (msgEvent,sink) <- mkEvent 
>        runE $ fmap (forkIO . (handleCloser $ handler msgEvent sink)) e
> handler :: Event String -> (String -> IO ())-> Handle -> IO ()
> handler e sink h = do
>   subscribe e (hPutStrLn h)
>   forever $ hGetLine h >>= sink
>
> handleCloser ::  (Handle -> IO ()) -> Handle -> IO ()
> handleCloser action h = catch (action h) (const $ hClose h)

Okay, so not really that much changed in this version. The big change is that we now have two sets of events, one that for the handles and one for the messages. We also use the subscribe function to launch the threads that display messages to everyone logged in, subscribe being a slightly misleadingly typed function that takes in an event and a consumer and spawns a new thread feeding the event data into the consumer. Now, all you boys and girls following along at home will probably notice a major oversight: at the moment, there's no real way to close down the chat server cleanly. Also, I cheat and don't properly handle logouts except for closing the handle when it hits an error.


I'm also working on another use of Data.Reactive with some of the SDL toys I've written. Maybe I should port my pong clone over to it, if I have copious free time.

One last thought on laziness

So while I'm working on a couple of other posts I want to put up over the next couple of days, I did want to throw out some last words on this whole lazy evaluation business & advice for learning Haskell.

I'm of the opinion that laziness is the single hardest thing to get used to in Haskell:  not warm fuzzy things, not higher order functions, not syntax.  The reason why it's taken me awhile, having used Haskell more off than on for small toys over the past couple of years, to really grasp how to use lazy evaluation is that it forces you to think about the combination of your functions and data much more carefully.

Let's take a really silly example such as 

head . map (+1)

because it's something that is easy & obvious.  If you apply this function to a list of numbers the evaluation can proceed something like the following:

head . map (+1) [1,2,..]
head $ ((+1) 1):(map (+1) [2,...])
((+1) 1)
2

To anyone remotely familiar with the concept of laziness I'm sure this seems somewhat intuitive.  You only need the first element of the list, so only the first element has the argument to map applied to it.  It's a simple consequence of the structure of lists and the definition of map, the kind of example that you can feel comfortable with after just a minute with a pencil and paper.  So what's my point?

My point is that if you're learning Haskell and you're running into problems with laziness, you should break out the pencil & paper and try to calculate what will happen when your function is called.  It's something you don't really have to do with other languages, but I think it's the best way to see how your functions and data structures interact during evaluation until you have better intuition.