Integer Overflow

I’ve received a request to release the source for Kinetic, a project I worked on in Haskell around the winter of 2006 (iirc). There are two reasons why I’ve put this off:

1. This was one of the first projects I worked on in Haskell, and the source shows that. My experience has been Haskell is often criticized based on the quality of code produced by its n00bs. This is an unreasonable thing to do (imagine judging a unicycle based on how well someone can ride it on their first go!) but I see it often none the less. I hope that this release does not lead to more of this nonsense.
2. The project had ambitious goals that I never had the time to pursue (I’m sure many hackers know that feeling…) I’m really not interested in hearing about how I didn’t deliver on that. It’s just something I was working on when I was in college, you dig?

I’ve uploaded a snapshot of my development directory here. The build process attempts to download the source to ghc-6.6 and build it locally for use in the construction of the kernel. It will also try to find (using very basic means) the object files for many non-system C routines used to support the GHC runtime.

The Makefile should be able to produce a bootable CD ISO that can be used with VMWare. The operating system includes a driver for the VMWare graphics adapter, which it will assume is what the host system provides (so it probably won’t get very far in Bochs or qemu).

Of course, when I tried building it on my current machine, the build failed in ghc-6.6. I know that I was working on replacing the GUI with a console-based shell at some point; it’s possible that the source I posted is somewhere in the middle of that, and won’t build as a result. I’ll investigate this more when I get a chance.

I’d be happy to answer any questions about the system as best as I can. Happy hacking!

Today’s post is more of a “thinking out loud.”

A few years back I started working on an “operating system written in Haskell. The code drew on some C++ that I had already written for dealing with CPU-level data structures, together with some new Haskell code I had written for interfacing with it. I wound up leaving the project to rest soon after that, more or less because I didn’t like the way the code was turning out. I’d later look back and realize that my haskell-foo just wasn’t up to the task of writing the code in good style (I’m planning to release the source this weekend, so you’ll get a chance to see what I mean).

Recently I learned that House, a Haskell-based OS project that preceded my own, is once more in active development. This is good news for two distinct reasons:

1. It was an interesting project that accomplished much more than I managed to, and
2. If I ever find the time to work on an operating system again, there’s a project to contribute to rather than re-invent.

All of this made me wonder, though: what would it take to make GHC itself bootable? It’s already the standard compiler; more or less everything works with it. Every day Hackage grows with more software that works in it. At some point, doesn’t it make sense to just boot to GHC?

How would it be done? Perhaps in much the same way as I made Kinetic bootable: create a stripped down POSIX environment, include whatever standard libraries are needed to support the thing, and run Bochs until the kinks get worked out.

What do you think?

On 24 February 2009 I’ll be giving a talk for the University of Utah GSAC Colloquium on sub-exponential algorithms for number factorization. The talk will cover Pomerance’s Quadratic Sieve, as well as other current methods. The plan is to focus on the connections between number factorization and other problems in mathematics whose connections to number theory are both non-obvious and highly useful.

This will be a survey of known methods, rather than a presentation of original work.

The Haskell community it abuzz over this article by Brian Hurt. His article is an interesting one, because it documents some insightful first-impressions about Haskell.

Undoubtedly, the part that has gotten the most attention is his suggestion that the Haskell community stop using mathematical names (as a default) for our common idioms. To quote:

One thing that does annoy me about Haskell- naming. Say you’ve noticed a common pattern, a lot of data structures are similar to the difference list I described above, in that they have an empty state and the ability to append things onto the end. Now, for various reasons, you want to give this pattern a name using on Haskell’s tools for expressing common idioms as general patterns (type classes, in this case). What name do you give it? I’d be inclined to call it something like “Appendable”. But no, Haskell calls this pattern a “Monoid”. Yep, that’s all a monoid is- something with an empty state and the ability to append things to the end. Well, it’s a little more general than that, but not much. Simon Peyton Jones once commented that the biggest mistake Haskell made was to call them “monads” instead of “warm, fluffy things”. Well, Haskell is exacerbating that mistake. Haskell developers, stop letting the category theorists name things. Please. I beg of you.

I’m a mathematician, so perhaps my opinion on this should be taken with a grain of salt. But to be fair, I came to Haskell years before I had taken any category theory, and back before my abstract algebra was where it is today.

It’s been said elsewhere, but I think it bears repeating: we basically have two choices on this issue.

1. We use less technical names, so that we don’t scare off people who are scared of technical names.
2. We call it what it is, with the added benefit that people who are familiar with these ideas can come to the language and apply some existing intuition.

Each option picks a preferred audience, where the audience for (2) is undoubtedly in the minority. But is that necessarily a bad thing?

Haskell is a Great Language Experiment. Originating in academia, it has been built out of a vast collection of wildly strange ideas, more or less just to see how well these ideas would work out. We’re watching that experiment unfold today.

Some parts of the experiment are obvious, such as using monads to bring side effects into the type system. Others are less obvious, such as suggesting that we should think about our software in terms of category theory and abstract algebra.

So thus I suggest the following perspective: just as we have become convinced that monads are a better way of modeling side effects, so too may we be convinced that these branches of math provided a good way of thinking about programs. If we do become convinced of this, then it behooves us to stick with this nomenclature and rethink our approach to training programmers. After all, it might be the case that an army of programmers who thinks in these terms will produce better results than army that doesn’t. If so, we should adopt this practice!

Of course, this has the obvious disadvantage of disenfranchising those programmers who won’t or cannot think of their problems in these terms. That’s fine; Haskell doesn’t need to be for everybody, just as not everybody needs to love Java, or Python, or Assembly, or Ada, or whatever.

What’s best is to attract people to Haskell who can like it for what it is, because once we decide we need to change Haskell to suit the needs of the people who don’t like it, then we’re no longer talking about Haskell, but rather some strange derivative language. In principle there’s nothing wrong with that; I’m not married to Haskell — just to the ideas that make it great. After all, at some point a language will come along that takes Haskell’s ideas as a foundation and expands on them in some nontrivial way. When that happens, I’ll convert to the new language, just as I converted to Haskell. It’s not clear to me, though, that renaming everything will bring about this sort of revolution.

Besides, let’s be honest: is it really the names that are tripping people up, or is this just more “monads are like burritos?” Sure, you can look at a monoid and say “aha! if only someone had called this thing appendable, I would have understood it from the beginning.” But is that really true, or is it just an excuse for having a tough time grappling with a genuinely new idea?

Sure, I grant that it’s not very helpful to try to teach monads to people by starting with examples of adjoint functors, talking about the semantics of join, etc. It’s much more helpful to start by explaining how the idea gets used, and then get into the abstract business of it all (for the people who are so inclined). But this is a problem in how we explain the ideas, not in what we call them.

Indeed, let us not forget that this abstract business does have some advantages. For instance, if one invests the (admittedly serious amount of) time to read a bit about monads and categories, then one finds that it should be obvious that linked lists are monads, since linked lists are really just free monoids, and the free monoid is adjoint to the forgetful functor, so that the composition gives a monad. Technical? Absolutely. But if you can get past that, then there’s a lot of insight one can gain into the underlying nature of what’s going on.

These algebraic and category theoretic foundations have inspired a lot of great ideas in the Haskell community. Renaming everything obfuscates the ideas, and will slow down future developments and unifications. In my experience (and I suspect the experience of many others), the “call it what it is” approach has made it much easier to see the big picture in my programs. Are we really ready to give up the conventions and way of thinking that got us where we are?

I’ve read a few comments about why Haskell is awesome. I even wrote an ironic blog post about it. Today I’m going to explain why I use Haskell for doing real work, entirely in terms of the tools Haskell developers use.

Edit: Immediately after posting, I found this article on Sententia cdsmith about reasons why Haskell is a good language. So between this post on tools and his post on the language, I think we’ve got our bases covered :)

I first really came into appreciating libraries by way of Perl’s CPAN, probably around 1999. These days I’m absolutely convinced that your language needs to have a searchable, cross-referenced, dependency-tracking library repository. For Haskell, it’s Hackage.

Hackage has many desirable qualities: Packages are written to work together rather than compete with one another. Searching for packages by name or description is performed by Google, and has all of the quality you’d expect as a result. But Hackage has another search option, which brings me to my next point…

Haskell is strongly-typed and purely-functional. Good Haskell style is all about writing tiny functions (one-liners!) and remaining abstract (code-reuse!). These qualities make the type signature of a function very telling.

Think about how many times you’ve been working with data in one format and needed a function that could convert it to something else. You’d like to avoid writing the function yourself (code-reuse!) but don’t know what it is called. How would you find it? Google around with related terms? Ask a mailing list?

The Haskell community has two search engines that trivially solve this problem: Hooge and Hayoo!. These engines can search for a function by name or by its type signature; and Hayoo! is linked into Hackage, so it is able to tell you which library contains the function you want.

Here’s a concrete example: I’ve got a list of numbers, and I want to split it up into two lists — one consisting of the evens, one consisting of the odds. This seems like a pretty specialized task, so I doubt there’s a function written for it explicitly. So let’s look for a function that takes a list, and a boolean test, and splits it into two lists — one consisting of the elements satisfying the test, and the other consisting of the elements that don’t.

That is, I need a function that takes a list of integers, and a function from integers to bools, and produces two lists of integers.

No problem: I jump over to Hoogle and search for functions of type [Int] -> (Int -> Bool) -> ([Int], [Int]). It produces a short list of results, tells me what library they are in, and even gives a brief description of what the function does. I quickly see that partition is the function I want.

Remember that Hayoo! works in conjunction with Hackage, so that I have this ability for all of the libraries in the standard repository. What other language is so centralized?

We’ve got all the usual things — source control by darcs, unit testing by HUnit, automated testing by Quick Check, and source documentation by Haddock. We’ve also got package management by Cabal (tied into Hackage, of course).

We’ve got one other tool that is perhaps the strongest reason for the language — the Glorious Glasgow Haskell Compiler. You won’t find a more advanced compiler anywhere on earth. It produces code that is performance-competitive with C, has built in support for profiling, and features a rich interactive mode that both helps you test code and also explore types and interfaces.

For many people, the initial draw to Haskell is the advanced technology that is built into the language. Haskell was originally drafted as a “language playground,” giving researchers a place to experiment with new ideas. Over time it has adapted to keep the experiments that worked. Today it stands alone in its simultaneous support for many language features that the mainstream world probably won’t see for at least another 10 years.

This stuff isn’t just syntactic sugar, either. Haskell probably has better support for concurrency than any other language, due to a combination of its pure semantics, modern memory sharing techniques, and data-driven parallelism.

To get a sense for how wildly amazing Haskell-related technology, check out Automatic generation of free theorems — a tool that, given a function’s type signature, can write a function for you that has the correct signature! You won’t find this kind of thing anywhere else.

Lastly we come to one of the most special features that Haskell offers: its unique developer community.

The Haskell community is famous for its strange blend of pure academics, working engineers, and tinkering hobbyists. The community has active mailing lists where people pour unimaginable amounts of time into giving each other detailed and useful answers. It is not at all uncommon for the discussion on the lists to lead to groundbreaking developments in Haskell development.

The community also has one of the most active language-centric IRC channels, complete with an IRC bot that evaluates Haskell code publicly, giving everyone a chance to experiment with code together in real-time.

Of course, the community does the “web 2.0″ thing as well: we’ve got an active reddit, tons of active and insightful blogs, an electronic magazine, a Wikibook, and a weekly newsletter of online Haskell community happenings.

Haskell programmers generally feel like they’ve caught on to something very special. Every day there are new developments in the community that push the boundaries of technology, enabling people to write sophisticated programs in less time and with greater reliability. There really is a sense that we’re playing with the toys of the future, which have somehow been gifted to us today.

It’s a strange language — far enough ahead of the others that it can be tricky for beginners — but it really has quite a bit to offer. And with the availability of the supporting tools we’ve just looked at, it is beyond ready for prime time.

While working on Armada in Ubuntu, I observed the following obnoxious behavior: the windows I was creating using GLUT.Window.createWindow didn’t have a border. To clear things up for search engines: the windows had no border, had no frame, had no title bar.

I’ve worked with GLUT in Haskell on Mac OS X and did not have this problem. After a bit of googling, I found a suggestion that the culprit was Compiz — the silly program which consumes hardware resources for the dubious purpose of making X-windows more eye-candy laden. Obviously Ubuntu uses it by default.

So here’s the bottom line: if you’re working with GLUT — createWindow in particular — and finding that your windows have no borders, then you should disable Compiz. I know for sure this is an issue with the Haskell bindings for GLUT, though a great deal of people have complained about this who are working in C directly, suggesting that it’s not a Haskell problem — though that much should be obvious, since Haskell is ready for prime time.

Yes.

Encouraged by the interest generated by my last post, I decided to do some more hacking on the real-time strategy game, which I’ve named Armada. I’ve now posted it on hackage; it can be found here.

The version on hackage adds quite a bit:

• Refinery units can now mine ore and transfer it to builder units.
• Builder units can now actually build units, if they have enough ore to do so.
• The scene is rendered using OpenGL/GLUT. Units are color-coded by player, with text describing their health and how much ore they have (except for fighters, which don’t carry ore).

I hope to keep adding to the project this week, though I haven’t decided what step to take next (don’t tell Joel!)

As a grad student, I spend most of my time doing math, and the rest of my time feeling guilty for not doing math. One of my friends who has “been there” suggested I should do something besides math during break. Other friends said I should use this as a chance to do a ton of math. Compromise: hang out in Seattle playing Grand Theft Auto IV and goofing off in Haskell.

So while the controller wasn’t in my hands (it was my host’s XBox, after all), I thought it’d be fun to see how succinctly I could get a real-time strategy game expressed in Haskell. I’m still working on it, but I figured I’d post what I have for now. This is literate Haskell, so you can dump this post into ghci and it’ll be ready to rock.

If you pay close attention, you’ll see that we have (something close to) knot-tying going on (we use integers to identify objects, and tie the knot using them as a lookup key) as well as some usage of software transactional memory.

In this post, we are going to write a real-time strategy game. We won’t give it
a GUI; instead, we are going to use a command-line interface, typing commands to
tell our army what to do.

The usual module imports:

> import Control.Concurrent
> import Control.Concurrent.STM
> import Control.Monad.State
> import Data.Complex
> import Data.List
> import Data.Maybe

We will have three types of units:

> data UnitType = Builder | Refinery | Fighter
>	deriving (Show, Eq)

Each type has its own initial health:

> type Health = Int
> defaultHealth :: UnitType -> Health
> defaultHealth Builder  = 55
> defaultHealth Refinery = 8
> defaultHealth Fighter  = 13

We need a notion of location. I’m going to use complex numbers for everything
since they come with a lot of functionality.

> type Location = Complex Double
> type Velocity = Complex Double
> type Speed = Double

There are a few commands we can give our units:

> data Command = Attack Unit | Mine | Build UnitType | Go Location | Idle
>   deriving Eq
> instance Show Command where
>  show (Attack _) = "Attack"
>  show Mine = "Mine"
>  show (Build ut) = "Build " ++ (show ut)
>  show (Go l) = "Go " ++ (show l)
>  show Idle = "Idle"

Units need to have some attributes:

> type UnitID = Int
> data Unit = Unit { ident   :: UnitID,
>		     owner   :: Player,
>		     utype   :: UnitType,
>		     pos     :: Location,
>		     health  :: Health,
>		     cmd     :: Command }
>  deriving Show
> instance Eq Unit where
>  u == v = ident u == ident v

Not all units can travel at the same speed. Here’s a function that tells us how
fast units move:

> speed :: Unit -> Double
> speed u = case (utype u) of
>		Builder  -> 1
>		Refinery -> 2
>		Fighter  -> 3

Not all units cause the same amount of damage:

> damage :: Unit -> Health
> damage u | utype u == Builder  = 0
>	   | utype u == Refinery = 0
>	   | utype u == Fighter  = 3

We need a notion of player. Players have units:

> type Name = String
> data Player = Player Name
>	deriving (Eq, Show)

And a notion of game:

> data Game = Game { units :: [Unit],
>		     players :: [Player],
>		     idents :: [UnitID],
>		     msgs :: [ (Unit, Command) ] }
> instance Show Game where
>  show g = "Players: " ++ (show $ players g) ++ "\nUnits: " ++ (show $ units g)
> makeGame :: [Player] -> Game
> makeGame ps = Game [] ps [1 .. ] []

We’re going to use the State monad for, well, managing the state of the game.
But let’s give it a fancy name, just to keep things clear:

> type GameSt a = State Game a

We need a command for adding a unit to the game.

> addUnit :: Player -> UnitType -> Location -> GameSt Unit
> addUnit p ut l
>     = do g@Game{units=us, idents=i:is} <- get
>	   let u = Unit { ident = i, owner = p, utype = ut, pos = l,
>			  health = defaultHealth ut, cmd = Idle }
>	   put g{units=u:us, idents=is}
>	   return u

We also need a command for telling units what to do.

> command :: Unit -> Command -> GameSt ()
> command u c = do g <- get
>		   put g{ msgs = (u,c):(msgs g) }
>		   return ()

Now we need a method for “ticking” the game. First, we say that a player is
dead when they have no builders left.

> playerIsAlive :: Game -> Player -> Bool
> playerIsAlive g p = foldl (\t -> \u -> t || isBuilder u) False (units g)
>	where isBuilder u = (owner u == p) && (utype u == Builder)

A game tick consists of ticking each of the units, then leaving only the players
who still are alive.

> tick :: GameSt (Maybe Player)
> tick = do g@Game{ players = ps, units = us } <- get
>	    let g' = g{ units   = (mapMaybe (tickUnit g g') us),
>			players = (filter (playerIsAlive g) ps),
>			msgs = [] }
>	    put g'
>	    if (length $ players g') == 1 then return (Just $ head $ players g')
>					  else return Nothing

Unit ticking is the trickiest part. Since the collection of units is a directed
cyclic graph (units can attack each other), it is the case that we need to “tie
the knot.” To do this, the tickUnit function needs to know what the updated
game state is, so that it can create references to the newly updated targets.
Luckily we are in a lazy evaluation situation, so this is completely reasonable.

> tickUnit :: Game -> Game -> Unit -> Maybe Unit
> tickUnit g@Game{ units = us } Game{ units = us' } u
>   = (takeDamage $ deliverMsgs $ procCmd u) >>= checkPlayer
>  where procCmd u = case (cmd u) of
>			Idle -> u
>			Go l -> goTo l u
>			Attack v ->
>			  maybe u{ cmd = Idle }
>				(\v' -> (goNear u $ pos v'){ cmd = Attack v' })
>				(find (v ==) us)
>			Mine    -> u
>			Build _ -> u
>	 goTo l u = let vec = (l - (pos u))
>			vel = vec / (0 :+ ((magnitude vec) * (speed u)))
>		    in if (magnitude vec) > 2 then u{ pos = l + vel } else u
>	 goNear u l = let dist = magnitude $ (pos u) - l
>		      in if dist > attackRange then (goTo l u) else u
>	 takeDamage u = let h' = foldl (checkAttack) (health u) us
>			in if h' <= 0 then Nothing else Just u{ health = h' }
>	 checkAttack h v = let dist = magnitude $ (pos u) - (pos v)
>			       d    = if isAttacking then (-1) else 0
>			       isAttacking = (dist <= attackRange) &&
>					     (cmd v == Attack u)
>			   in (d * damage v)+h
>	 attackRange = 10
>	 deliverMsgs u = case (filter ((==) u . fst) (msgs g)) of
>				((_,c):_) -> u{ cmd = c }
>				[]	  -> u
>	 checkPlayer u = if (playerIsAlive g $ owner u) then Just u else Nothing

Here’s a function that, given a game, plays it for n turns. If there’s a winner
by then, the winner gets returned. If not, it returns Nothing.

> play :: Int -> GameSt (Maybe Player)
> play n = if n == 0 then return Nothing
>		     else do mp <- tick
>			     case mp of
>				Nothing -> play $ max (-1) (n-1)
>				Just p  -> return $ Just p

Here is what the game looks like:

> tim   = Player "Tim"
> chris = Player "Chris"
> cyndi = Player "Cyndi"
> (w,g) = runState (
>		     do tim_builder   <- addUnit tim Builder (0 :+ 0)
>			chris_builder <- addUnit chris Builder (100 :+ 50)
>			cyndi_builder <- addUnit cyndi Builder (75 :+ 5)
>			tim_f1 <- addUnit tim  Fighter ((-3) :+ 0)
>			tim_f2 <- addUnit tim  Fighter (0 :+ 0)

>			chr_f1 <- addUnit chris Fighter (0 :+ 0)
>			command tim_f1 (Attack chris_builder)
>			command tim_f2 (Attack cyndi_builder)
>			command chr_f1 (Attack tim_f2)
>			play 100
>		    )
>		    (makeGame [tim, chris, cyndi])

If you play the above game, there won’t be a winner because chr_f1 will kill
tim_f2 before tim_f2 can finish killing cyndi_builder. If you take out the
command to chr_f1, then tim will win.

This is all pretty cool, but we still don’t have any type of interactivity.
Once we start the game, it just kinda does its thing. It’d be much better if
we could feed commands in during the simulation. To do this, we need to
introduce some concurrency. We will have one thread that plays the game, and
another to feed commands into it. We will use Software Transactional Memory to
manage the shared game object.

> makeSharedGame :: [Player] -> IO (TVar Game)
> makeSharedGame = atomically . newTVar . makeGame

> playSharedGame :: (TVar Game) -> IO Player
> playSharedGame tvg = do w <- atomically $
>				do g <- readTVar tvg
>				   let (w,g') = runState tick g
>				   writeTVar tvg g'
>				   return w
>			  case w of
>				Nothing -> do threadDelay 1000
>					      playSharedGame tvg
>				Just p  -> return p

We’ve got a bunch of commands for modifying game state. Here’s a function that
applies them to the shared game state thingy.

> applyCommand :: (TVar Game) -> (GameSt a) -> IO a
> applyCommand tvg c = atomically $
>			do g <- readTVar tvg
>			   let (a,g') = runState c g
>			   writeTVar tvg g'
>			   return a

Here’s an example of how we use this from ghci. No special extensions needed:

shared <- makeSharedGame [tim, chris, cyndi]

tim_builder <- applyCommand shared $ addUnit tim Builder (0 :+ 0)
chr_builder <- applyCommand shared $ addUnit chris Builder (0 :+ 0)
cyn_builder <- applyCommand shared $ addUnit cyndi Builder (0 :+ 0)

forkIO $ (playSharedGame shared) >>= (putStrLn . ("Winner: " ++) . show)

tim_f1 <- applyCommand shared $ addUnit tim Fighter ((-3) :+ 0)
tim_f2 <- applyCommand shared $ addUnit tim  Fighter (0 :+ 0)

applyCommand shared $ command tim_f1 (Attack chr_builder)
applyCommand shared $ command tim_f2 (Attack cyn_builder)

For instance, here’s what this looks like in ghci:

An interactive session in ghci

Now to get around to adding some more unit functionality, along with a graphical display of the game world!

…and then I’ll understand why so many Haskell examples are examples of language interpreters. Until then, seriously, no one actually writes that kinda stuff, so honestly, it’s a silly example that we’ve really beaten to death. Give it up already. For real.