[Haskell-cafe] Implementing a MUD server in haskell

[Jules Bean]

Jack Kelly wrote:
> struct room{
>   ...
>   struct player * players;
>   ...
> };
> 
> struct player{
>   ...
>   struct room * room;
>   ...
> };
> 
>  From what I can see, I'd use a record type for players and rooms, but 
> I'm not sure how to replicate the pointer effects: 

Essentially you have to choose some form of identity (relational DB fans 
might call it a "key") for your players and rooms. My gut feeling is 
that String will do fine; it's nice for debugging, gives rise to a 
natural way to write your admin commands and so on. However, it may not 
be quite good enough (100 mobs all called "an orc" need individual keys) 
and you may end up using an Int or Int64 for your key.

Once you've chosen a key, you can do something very like the C++ 
structure, but instead you have

Room { ... players :: [String] ... }

Player { ... room :: String }

..although you may find life is made more pleasant by

newtype RoomID = RoomID String
newtype PlayerID = PlayerID String

which improves the looks of your types, helps the compiler help you, and 
also makes it easier to change to another representation later.

I should mention, actually, that there is also the naive solution:

Room { ... players :: [Player] ... }
Player { ... room :: Room ... }

The main reason to dislike this is that if something in a Player 
structure changes, you have to remember to change all the references to 
it... Depending on your design, it may be that rooms themselves can't 
really change, so this may not matter for rooms (except for the player 
list, but maybe we don't need that, read on...)

 > keeping each player
> pointing to a single instance of a consistent world and maintaining the 
> invariant that (given: p :: Player, r :: Room):
> 
> p `elem` (Room.players r) => (Player.room p == r)

There are always two techniques for maintaining invariants. One is to 
design your data structures so it is impossible to violate them, (our DB 
fan would call this normalization), and the other is to ensure that all 
modifications are carried out via a relatively small set of functions 
which are responsible to maintaining the invariant (which the DB fan 
would call middleware).

In solution 1, you would simply not store the player list in the room 
structure at all. Instead, you would only store the room in the player, 
and whenever you wanted to answer the question "Which players are in 
this room" you would do a quick search through all players to find them

playersInRoom :: Room -> [Player]
playersInRoom r = [p | p <- allplayers, (room p) == r]
-- Just like a database! In SQL we'd say:
-- SELECT p FROM allplayers WHERE p.room = r

Of course the disadvantage to this is the linear search through all the 
players. Depending on how often this is performed, this may actually 
cost you less that explicitly "caching" the value inside the room.

In solution 2, of course, whenever you  move a player from room A to 
room B you do it via a function which is explicitly designed to keep 
everythign up to date:

movePlayer PlayerID -> RoomID -> RoomID -> Game ()
movePlayer pid raid rbid = do
   p <- getPlayer pid
   setPlayer pid (p {room = rbid})
   ra <- getRoom raid
   rb <- getRoom rbid
   setRoom raid (ra {players = (players ra)\\[pid]} )
   setRoom rbid (rb {players = pid : (players rb)} )

Which I've written in an imaginary Game monad, and using rather ugly 
low-level combinators get/set Room/Player. You could make it look much 
more pleasant in practice with some better chosen combinators.

Still I think solution 1 (don't store redundant data which can get out 
of sync) has a lot to recommend it and solution 2 may be premature 
optimization; i.e. implement solution 2, which is a kind of caching of 
computed data, only once you've convinced yourself that recalculating 
that data every time really is slowing you down.

> This needs to stand up to concurrent modification of a shared world 
> structure, but I think I'll set up the concurrency controls after I get 
> my head around this.t
The simplest way to do this is to bundle all your big shared mutable 
world into a single MVar. What this amounts to is perfect brute force 
serialisation of the actual modification part: i.e. all world 
modifications share a global lock. This is easy to implement and easy to 
reason about.

If that turns out to be too restrictive, then you split up the MVars 
into smaller pieces, but then you have to think a bit harder to convince 
yourself it is safe.

Jules