Looking Out To Sea

Last year I was standing at the bus stop, awaiting my carriage home, and looking at the real-time LCD bus tracker next to me. If these things are really real-time, I thought to myself, they must be communicating with the buses and with each other so they know when buses are delayed or cancelled. Surely this information is available somewhere?

I looked around on the Lothian Buses website but found nothing. So I wrote them an email. I suggested they make the data available as some text feed or RSS — something simple to manipulate. I never got a response.

But earlier this year someone else noticed that Bus Tracker had been launched, which provides a front end to the bus data I was looking for. They had also added links to Google Maps to plot the stops of a bus, or to interactively choose your nearest bus stop. It’s a damned interesting site — not very pretty but quite powerful.

I thought it would be useful/interesting to write a program to query the BusTracker site. At this point I’m just writing a library to do the tasks. Wrapping an interface around this can come at a later date.

The full library can be found online, or get the darcs repository with:

darcs get http://www.dougalstanton.net/code/buses/

Continue Reading »

A few weeks ago Randall Munroe published XKCD 426: Geohashing and apparently invented a new sport…

The idea is quite simple. The world is divided into little degree-by-degree segments (by latitude and longitude). If you see these on a map they look mostly rectangular at the equator and gradually get more triangular at the poles, because the pole-wards side is shorter than the equator side. You can see a picture of the geographical segment around Edinburgh on the wiki.

If you imagine that each rectangle has a starting corner (the one nearest the equator and nearest the Greenwich meridian), which we’ll call (0.0, 0.0). We can identify any spot in your rectangle with a fractional offset from this point — like (0.456, 0.235).

If you want to know the major co-ordinates for your home then a good place to start would be this list for the major cities of the countries of the world.

I’ve put together a Haskell program to demonstrate the next stage of the procedure, though there are plenty of web-based tools to do the same thing. I just wanted to try out the new cabal-install package (akin to CPAN, gems etc for other languages).

Continue Reading »

This is written with the inspiration of Simon Peyton Jones’ talk about pudding combinators. (He may also have mentioned financial contracts.)

Imagine we have a board game, with two opposing sides. To make things easy, this board game only has one type of piece on each side — there are no rooks and bishops and cuddies.

A Strategy is a mapping from the circumstances you find your players in to a move you can make.

type Strategy = Situation -> Direction
type Situation = (Location, [Location], [Location])

The situation for any one piece is its location, the location of the pieces on its side and the location of pieces on the opposing side.

The base Strategy is to not move at all. This is no way to win, so we need to improvise a few strategies. We could move all of our pieces towards the enemy in a mindless deathmarch:

attractfoes :: Strategy
attractfoes (me, _, foes) = attraction me foes

We can do the same for friends (so that pieces can clump together) and with repulsion (so pieces avoid their team-mates, for example).

repelfriends :: Strategy
repelfriends (me, friends, _) = repulsion me friends

Brief diversion: Attraction and Repulsion

So far I’ve assumed the existence of a few things. Some of them you can guess at (eg, Location is just a tuple of x and y co-ordinates). The functions attraction and repulsion need some more explanation. From the given type signatures we can infer that their type is:

attraction, repulsion :: Location -> [Location] -> Direction

The first argument is the piece under study and the second argument is all the pieces it is attracted to/repelled from. Between each pair of locations (pieces) there is a force — either toward or away:

attract, repel :: Location -> Location -> Direction

It seems to me that these should be the “primitives” of this system. (In a sense they are, but not in any formal way. That’s just what these strategies ultimately rely on.) Maybe working up from these functions would reveal a nicer system. (I say “these functions” but really there is only one: each is the negation of the other, so either could be implemented in terms of the other.)

Now where was I? Combining strategies

Assuming we have four simple strategies (attracted to and repelled from both friends and foes) we probably want to combine them. The simplest means is by addition:

(<+>) :: Strategy -> Strategy -> Strategy
s1 <+> s2 = \x -> s1 x + s2 x

Let’s say that s1 is attracted towards enemy pieces but s2 is repelled from them. (This is a silly example, but instructive.) The combinator shown above allows these two urges to neutralise each other — since as I’ve already mentioned, attraction and repulsion are negations of each other anyway.

Of course we may decide that some urges are more important than others. The urge to clump with friends is more important than the urge to avoid the enemy. So we want a scaling system, to increase or reduce the importance of a particular strategy compared to others.

(<*>) :: Double -> Strategy -> Strategy
n <*> s = scale n . s

(The scale function scales a Direction tuple by its first argument.) We can then increase or decrease the importance of a strategy by scaling it:

(0.7 <*> attractfriends) <+> attractfoes :: Strategy

So far we’ve assumed that one strategy is applicable in all cases. This is never the case — there are always corner cases and special situations which we should test for and evaluate accordingly. Let’s say we want our pieces to clump together until the crowd reaches a certain critical point. Then they march out to war or something.

I imagine we would run such a system a bit like the ?: operator from C.

condition <?> consequent <:> alternate :: Strategy

Let’s break it down. The part after <?> is a choice of two strategies, only one of which is applied. The choice is as simple as a tuple of (Strategy, Strategy) — so <:> is essentially an alias for the tuple constructor.

(<:>) :: Strategy -> Strategy -> (Strategy, Strategy)
(<:>) = (,)

The condition is slightly more intricate. What kinds of things would the predicate test? I guess anything that can be determined by looking at the circumstances of this player.

(<?>) :: (Situation -> Bool) -> (Strategy, Strategy) -> Strategy
predicate <?> choices = \x -> if predicate x
                                    then fst choices
                                    else snd choices

The conditional combinator is brand new for this post — I haven’t implemented it in the code yet. So I don’t know how horribly wrong it is! More on that later.

And because my post yesterday was mostly about baking but slightly about Haskell, I suppose I should balance things up by noting that yesterday’s loaf tasted even better this morning. Slightly moister and very tasty. But I’m going outside into the sunshine now!

Helen wasn’t feeling well yesterday so we didn’t get go anywhere. Instead I made a chocolate cake. It didn’t turn out quite right though — it split in my hands as it came out of the tin and is quite sticky inside. I don’t know where the fault lies — either with me or the recipe or the oven. It’s alright if you want to eat it with a spoon but not so great to eat in your hand.

Today I made a loaf of white bread. It takes quite a while but there’s something very therapeutic and calming about kneading dough. Especially if you get into a rhythm and just blank your mind.

I left it a little long on the second proving and so it has rather outgrown the loaf tin. At least this one rose at all — my last attempt was a bit like a sack of gravel to look at. Tasted a bit dull too!

The bread’s cooling now and there’s some cheese sitting out to warm up. There’s been a round of Camembert in the fridge for a wee while, waiting to assault the nasal passages whenever the door is opened. We’ll show it who’s boss this time.

In between the baking I have been playing with some of GHC’s type extensions to Haskell. In particular, generalized¹ newtype deriving and phantom types.

What’s the latest on Thud?, I’m sure I heard you say. Well, bits and pieces. I’m still at the point where I don’t really have a good strategy for the AI, I’m just playing. But whenever I have an idea it takes a while to link it in to the current system. So I’d like to get some strategy combinators working. That might help to add a bit more structure to my code, which is looking quite messy now.

Also, I made some enquiries about other board game implementations and received some good replies from the Haskell Café list. A couple of notable ideas:

• Don’t bother holding an array for the board, just carry around separate lists for each piece. Makes it easy to locate friends and foes on an otherwise-quite-large board.
• Use Prompt to abstract ideas of user/computer interaction. I’ll have to look into this again but from what I remember it was quite an elegant way of containing a two-sided conversation (between user and computer, for example).

I also wrote a bit of simple network code to see how to write a server. I can connect to a known port with telnet and send the server messages; it sends back the number of characters in each line in return. It then hangs up on receiving “quit!” — not complex, but pretty close to what I need.

On Friday, Mat came round and we played Thud. As a means of exploring the territory, honest.

I’d asked him and a bunch of others if they could solve a trig problem I was having¹ which led to me explaining why I needed the answer, which led to Nick saying he’d like to get involved with this project too.

I’m writing a server-based game of Thud, so that Mat’s GUI client will have something to play against. Obviously big gobs of such a server is player AI for non-human players. Nick is the only one out of the three of us with genuine AI credentials, which will be helpful.

At the moment I’m throwing together simple heuristics as social potential fields and implementing them in the almost-bluntest way I can imagine. I haven’t got round to making a communication protocol yet, though it shouldn’t be difficult. The best step will be to look at how Mat’s client works, since the shorter the distance between the semantics of my protocol and his the better.

Naturally we’re going to have some hardcore language-advocacy arguments — my implementation is Haskell, Mat’s is C# and Nick wants to write in Java to play with a 3D framework he’s got his eye on. All in good spirits, of course. ;-)

If this comes to fruition in any way (I honestly don’t know how keen the other guys are, or how much free time they have for such things) it should be good fun. Solitary programming is enjoyable, but collectively working towards some goal provides an extra level of challenge and satisfaction.

I’ve been fiddling with Mono lately, the free software implementation of the Microsoft .Net system. I say, fiddling, mostly just looking at. My good friend Matt wrote a network game of Thud! in C# for Windows. I was trying to get it working under Linux.

I’m happy to say that migrating a Visual Studio project with MonoDevelop worked flawlessly for me. Then I just hit Build Project and it worked. The game is human-player only, so I wanted to write a rudimentary AI to play against. (I don’t really know how to play, so I think I could beat me fairly easily.)

Then I hit this bug in the Mono system which causes complete failure whenever you try to open a network connection — but only if your machine has a dynamic IP address. Yeah, I know…

I wanted to simplify the networking protocol (currently it’s the default .Net serialisation system, which is rather opaque). That will have to wait until I can play the game without crashing it.

Been trying — and mostly failing — to engage with Haskell’s foreign function interface (FFI). I have just managed to get something together although bits of it are closer to cargo cult programming at the moment. Write these keywords, intone these phrases, bam it works.

Lost at C

For this exercise I wanted to write a ‘library’ in C then call it from within the Haskell code. My magic C library has two parts, foo.c and foo.h. The first part squares the supplied integer! Amazing!

#include "foo.h"
 
int square(int n)
{
    return n * n;
}

The other part is the header file for this:

int square(int n);

I bet you would all have struggled to come up with something so hardcore…

Deep Voodoo

The Haskell to link to this great library is:

module Main where
 
import System.Environment
 
main = do [n] <- getArgs
          print $ sqr $ read n
 
foreign import ccall "foo.h square" sqr :: Int -> Int

And I have to admit that the last line doesn’t really mean much to me. I know what all the bits do, but I wouldn’t know how to adapt that to more interesting or varied callouts.

But one step at a time is the way to go.

Compilation and Linking

The first step is to create the library we want to call out to, then build the Haskell around it.

$ ghc -c foo.c
$ ghc --make -fffi Foo.hs foo.o -o foo

So you need to create foo.o and then pass it and the Haskell source to the compiler with the -fffi argument. Then we try it out:

$ ./foo 3
9

Not bad. (Though not actually what one might call “good” either. Merely satisfactory.) At some later point I will attempt side-effectful functions and maybe even some data structures.

And Reg will not be happy.

module Main where
 
import Data.Maybe
 
fizz = concat $ repeat $ replicate 2 Nothing ++ [Just "Fizz"]
buzz = concat $ repeat $ replicate 4 Nothing ++ [Just "Buzz"]
fizzbuzz = zipWith (maybeWith (++)) fizz buzz
numbers = map (Just . show) [1..]
 
maybeWith f (Just a) (Just b) = Just (a `f` b) 
maybeWith _ (Just a) Nothing  = Just a
maybeWith _  Nothing (Just b) = Just b
maybeWith _  Nothing Nothing  = Nothing
 
-- an infinite list of fizzbuzzes
results = map fromJust $ zipWith (maybeWith const) fizzbuzz numbers

I bothered posting this at all because I feel sure that maybeWith can be implemented as a simple combination of other functions. It’s sort of like liftM2, except it doesn’t throw away good values when it has one good and one bad.

Also, I used it twice in five lines, so it surely must be a known function. But for the life of me I can’t think what it could be.

From a programming language blogger comes this little WTF:

When talking about how dynamic scripting languages are designed, people have a tendency to divide them into “There is more than one way to do it” and “There is one way to do it”. Perl is the quintessential example of “more than one way”, and Python is the opposite, going so far as to make it impossible to have your own indentation.

I am disturbed by the notion that choosing your own indentation counts as language flexibility. Whither the closures, the higher-order functions, the parametric polymorphism? This seems like arguing that a paintbrush that you can also hold in your left hand is inherently more powerful than one you can only hold in your right. And yet neither actually gives you any more interesting abilities than daubing paint.