Overooped

Mutable Adventure, Pedro and Erlang Text Processing

As some of you might know, I’m currently writing a game called Mutable Adventure, a 2D sidescrolling platformer MMOG with the editability of Second Life.

The thing about Mutable that interests me the most, however, is the networking. I’m using a library/protocol called Pedro, by Peter Robinson, which I found when Keith Clark presented it at work. Before I go on, I need to explain why this protocol is so goddamned cool.

Pedro and software agents

It’s based on Prolog, more specifically, his own implementation of QuProlog. It’s sort of a blackboard system, with a central messaging server that everyone connects to. It’s string-based, and what you send over the network are prolog fact-style messages, called a notification, for example:

  playerWasHit(152, 12388)

This is then broadcasted to everyone to subscribe to this message. A subscription might look like this:

  playerWasHit(PlayerID, ObjectID), PlayerID = 152

Notice that the expression contains Prolog variables, and a guard expression. This means that several clients may subscribe to the same notification, but with a guard expression that says they only want player info about their own player.

Each subscription is accompanied by a number, so that you on the client side can redirect the incoming notification to the right place. In Python I’ve implemented this so that individual objects may subscribe, and that individual objects may receive notifications. For example, say a ball is spawned in the game world. At the instance it’s instansiated, it may subscribe to information pertaining to this specific instance, by giving the subscription a guard expression with its own ID number. Boom, automatic network message propagation within your game client or server. As an example, in the client, the Tilemap class is appended with a category/mixin with the following code (notice the third argument, the guard):

  gClient.net.subscribe(self, "tilemap(TilemapName, NameOfTilesetTilemapUses, ScrollX, ScrollY, AutoScrollX, AutoScrollY)", 
                              "TilemapName = \"%s\""%self.name)
  gClient.net.subscribe(self, "tileInMap(TilemapName, TileX, TileY, TileIndexInRoomTileset)",
                              "TilemapName = \"%s\""%self.name)
  gClient.net.subscribe(self, "tilesInMap(TilemapName, FromIndex, ToIndex, TileIndexArray)",
                              "TilemapName = \"%s\""%self.name)

(Voxar has significantly improved the syntax in the Pedro python wrapper since then)

Suddenly, your objects aren’t mere objects; because they can communicate on their own with the outside world, and respond on their own, they’re now software agents. Also, because the messaging medium is now separate from the server instance, your game server may now be freely split as you see fit into several processes, both for load balancing and for division of labor into discrete entities, with higher cohesion and lower coupling.

The downside

Peter Robinson’s implementation of this concept isn’t perfect, however. First off, it’s written in plain c, and it depends on glib2. GObjects. I can’t stand GObjects. I can’t stand manual memory management. And it’s 5000 lines of code for a relatively simple concept.

Secondly, you just traded yourself simplicity for the price of a single bottleneck. A buggy, unstable, memory leaking single bottleneck with no means of load balancing or distribution. Written in C with a single maintainer, based on glib2 which is pretty hard to get running under Windows, if you would want to.

(I attended a 24 hour game development challenge a while back, where I wrote a networked 3D racer. Because I couldn’t get pedro running under Windows, I had to run it on my own server at home, while the judges tested the game from the other side of the country. >1sec lag and no lag compensation or similar whatsoever in the code = I certainly didn’t win that competition :( )

Erlang, The Savior

After reading Joe Armstrong’s book on Erlang, I was itching to write something. I tried writing a Twitter clone, thinking that Erlang’s highly distributed nature would come to great use there, but every line took a minute to write (because I’m so new to Erlang), and Twitter just felt too big and too difficult to write as a first project, so that got abandoned.

So, the next thing I’m trying is to write a Pedro clone in Erlang. It’s a good match, since the hardest part of of Pedro is the pattern matching, and Erlang got that as a part of being a functional programming language. I’ve set out to get it to work in 100 lines or less. So far I’m up to 60 lines, and I think I have a chance of making it.

In Erlang, processes are cheap and abundant. You spawn a lot of processes and then do all communication through erlang messaging. A common pattern is the middle man pattern. While cleaning the dishes I remembered this pattern, from its usage in an IRC client built in the book, and tried to apply it to Erdro (Erlang Pedro :P) conceptually in my head (Sorry, the following is a bit hazy as 1) I haven’t implemented it yet 2) it contains a lot of erlang terms). One problem with Erdro is that in its current implementation, even if you have a supervisor process watching the server and respawning if it does, restoring all the stack state, the process would be dead and the sockets meaningless, and all clients would have been lost and restring state would be pointless. However, if each client is abstracted away with a middle man process (meaning all socket communication goes to and from a separate process, and communication with the server is handled through erlang messages), you could store all the state including process pointers to these middle men in a mnesia database or similar, and if the server dies, respawn the server and its state and everything you’d have lost was a single message (the one that made the server crash); all socket connections would be alive and all clients just continue communicating.

Put the middle men on a cluster of machines away from the messaging server, each with its own IP and bandwidth, and you’ve distributed your network load. The machine containing the messaging server could self-immolate, still only a single message would be lost (given that there is another computer that could act as messaging server).

Process load balancing of the server, however, is left as an exercise for the reader.

The nitty gritty details of text processing in Erlang

There’s a slight mismatch between Erlang and Prolog, given that they’re completely different languages (one is functional, the other is logical). In the context of Pedro, however, I could only think of a single difference that mattered, and had to be changed.

In Prolog, the term “myFunctor(atom, anotherAtom)” defines a fact. In Erlang, it’s a function call. So, for this to work, I’d have to convert that term to something equivalent that could be used in Erlang pattern matching: a tuple, like so, “{myFunctor, atom, anotherAtom}”. Since Pedro doesn’t have tuples, the transformation is reversible and fully equivalent (I hope! It’s not like I’ve tested my code yet…). How would you do this? The first thing on my mind, being a ruby coder, was regular expressions. My first realization was the erlang’s regexp support is really, really, really horrible. Not only is it slow, its syntax support is so basic you might as well do without. My second realization was that regular expressions were a really bad match for the task at hand anyway. So my first real piece of Erlang code was a text search-and-replace implementation with pattern matching specific to my task:

functor_to_struct(PrologString) ->
  [First|Rest] = PrologString,
  fts("", [First], Rest, false, 0).

fts(BeforeFunctor, Functor, [], _, _) ->
    BeforeFunctor++Functor;
fts(BeforeFunctor, Functor, Rest, InStringEscapeMode, Prev) ->
  [Next|Rest2] = Rest,
  case Next of
    34 when (Prev == $\\) and InStringEscapeMode -> % \"
      fts(BeforeFunctor++[34], "", Rest2, true, Next);
    34 -> % "
        fts(BeforeFunctor++[34], "", Rest2, not InStringEscapeMode, Next);
    Char when InStringEscapeMode ->
      fts(BeforeFunctor++[Char], "", Rest2, true, Next);

    $( ->
      fts(BeforeFunctor++"{++Functor++", " , "", Rest2, false, Next);
    $) ->
      fts(BeforeFunctor++Functor++"}", "", Rest2, false, Next);
    Char when ((Char >= $a) and (Char == $A) and (Char == $0) and (Char =
      fts(BeforeFunctor, Functor++[Char], Rest2, false, Next);
    Char ->
      fts(BeforeFunctor++Functor++[Char], "", Rest2, false, Next)
  end.

Half-way through the code, it felt so horrible, I felt like I was writing the worst code in the universe. Now that it’s done, though, I find it pretty nice. It’s relatively short for what it accomplishes (replaces function calls with tuples, being careful not to interpret parens inside a quoted string) imo. However, after a good night’s sleep, I realized that this was a really stupid way of doing it. Why? Because Erlang has a code parser in its standard library.

  {ok, Scanned, _} = erl_scan:string("foo(bar)."),
  {ok, Parsed} = erl_parse:parse_exprs(Scanned)

yields [{call,1,{atom,1,foo},[{atom,1,bar}]}], a perfectly fine nested Erlang data structure that can be traversed and parsed. So that’s what I did!

  transform_calls_to_tuples(ParseTree) ->
    tctt(ParseTree, []).

  tctt([], Collected) ->
    lists:reverse(Collected);
  tctt([Token|Rest], Collected) when element(1, Token) == call ->
    {call, 1, FunctorNameAtom, ArgumentList} = Token,
    tctt(Rest, [{tuple, 1, [FunctorNameAtom | tctt(ArgumentList, [])]} | Collected]);
  tctt([Token|Rest], Collected) ->
    tctt(Rest, [Token|Collected]).

… which yields the same result, but in a parse tree (which you can turn into a string again with erl_pp, the pretty printer).

That’s it! I’ll get back to you when Erdro is done.

Properly bundling .frameworks in your application package

Update: My blog post on @rpath supersedes/complements this post (it’s not finished yet, though).

I’m sure you’ve run into it. You build your app and it works fine, but when you distribute it, your users get:

Library not loaded: /Users/Richard/Library/Frameworks/libmng.framework/Versions/A/libmng
  Referenced from: /Users/nevyn/Downloads/Sphere-Mac RC3/SphereEngine.app/Contents/MacOS/SphereEngine
  Reason: image not found

One more time. This subject seems to pop up quite often, but I think I’ve finally gotten it nailed. Before I used to fetch the sources of all the libraries I was using, set up an .xcodeproj and set install_name to “@executable_path/../Frameworks/” (and that I did here). That’s not really necessary, and not possible for non-open source frameworks. So, no matter what framework or library you have, this is how you bundle it anyway, no matter what the install_name is.

1. Add an extra Copy Files target action in your XCode project (and rename it Copy Frameworks)
2. Get info on the new terget action, and set its destination to Frameworks.
3. Then, drag all custom frameworks to this target action, and they will be automatically bundled with the application when you build.
4. You will now need to gather some information. Run `otool -L on YourApp.app/Contents/MacOS/YourApp` and note its output for each of the lines corresponding to a framework you just bundled.
5. Next, add a Shell Script target action. This target action will call the install_name_tool to rewrite the linking information in the built binary to reference the bundled frameworks instead, even if the frameworks haven’t been built with an install_name of @executable_path/../Frameworks. Copy and modify as appropriate:

function relocateLibraryInCurrentApp() {
  install_name_tool -change $1$2 @executable_path/../Frameworks/$2 $CONFIGURATION_BUILD_DIR/$EXECUTABLE_PATH
}

relocateLibraryInCurrentApp /usr/local/lib/ libfmodex.dylib #note the space
relocateLibraryInCurrentApp /Library/Frameworks/ Foobar.framework/Versions/A/Foobar #note the space

Addendum: I realized that making a post that just describes how to do something, not why, is kind of lame.

In Mac OS, each binary contains a list of paths to binaries which it was linked to and which need to be loaded for all code to be available. When you launch an app, the runtime will thus load the app’s code, and for each library it needs to find will try to load it from the path set in the app’s binary. (For frameworks it’ll also look in /System/Library/Frameworks and /Library/Frameworks). What install_name_tool does is simply to rewrite that path inside the binary given as the fourth argument, searching exactly for the string argument #2, and change it to argument #3.

Additional resources:

• http://qin.laya.com/tech_coding_help/dylib_linking.html
• http://balanceinmotion.net/blog/2007/12/26/free-love-frustration/

Lazy Man’s Logging

file_put_contents(…, FILE_APPEND) to log is a bad idea and you know it, but it’s sometimes good enough, or you just don’t get paid enough to make something serious. I just let you make it a tiny bit more serious, a whole lot more dependable, and still just change a single line of code.

  /// Creates a table called $table as (id, when, message) if none such exists, and inserts a row with $message in it.
  /// If no connection details are given, it uses the current database connection. Same goes for $database and $when.
  ///
  /// @returns TRUE on success or FALSE on failure.
  ///
  /// @example mysql_put_contents("orders", "I CAN HAZ CHEEZBURGER?", "mysite", NULL, "127.0.0.1:3306", "mysite_user", "secret") or die(mysql_error());
  /// @example mysql_put_contents("guestbook", "Longcat says: I'm loooooooooooong") or die("Errorz!");
  function mysql_put_contents($table, $message, $database = NULL, $when = NULL, $host = NULL, $user = NULL, $pass = NULL) {
    if($host)
	    mysql_connect($host, $user, $pass);
	  if($database)
	    mysql_select_db($database);
	
	  $qry = "CREATE TABLE IF NOT EXISTS `$table` (
             `id` INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
             `when` TIMESTAMP DEFAULT NOW(),
             `message` TEXT NOT NULL
           );";
    $result = mysql_query($qry);
    if($result === FALSE)
      return FALSE;
      
    $qry = "INSERT INTO `$table` VALUES(NULL, ".($when ? $when : 'NULL').", '".mysql_real_escape_string($message)."');";

    $result = mysql_query($qry);
    if($result === FALSE)
      return FALSE;
      
    return TRUE;
  }
	

PHP: Timeout on file_get_contents

Since there doesn’t seem to be a single piece of documentation or example on the use of the context option for file_get_contents, and everyone’s actually setting the PHP app’s ini value for timeout (euugh) instead of doing it right, I thought I’d feed this to google:

The unit on the timeout argument is seconds as a float; that is, it is possible to use fractions (e g set timeout to 0.1).

The truth, it hurts, it hurts! (Default parameters in Python seem to be evaluated once)

Nevyn’s First Rule of Singleton Evilness

I finally figured out a litmus test for whether being a singleton is okay or evil for a particular class:

If a class is thread-safe and has no state that can be changed, it may be a singleton.

NSFileManager: OK. RMS::Sound::Gateway: Not so much.

I suppose there are ways to circumvent this rule; e g most of Apple’s singletons may be created either through the+[defaultManager] method, or instantiated on-the-spot, e g if you want several separate NSNotificationCenter inside the same application.

This discussion came up during the creation of the RMS game engine, among many other times. Now that I’m ripping out parts of the engine for re-use, I realize that it was a very bad design decision to use singletons the way we did. For example, my 2D modeler prototype for my candidate thesis is document-based, thus it needs an RMS::Sound::Gateway for each window. This is no-can-do until I fix the code, because for example the Voice class has the delegated play method, and the way it works is that it gets the global gateway and adds itself to the gateway’s list of playing voices.

“State that can be changed”? Oh, right. +[NSColor redColor] has state, but it can still be a singleton since that state can’t be changed by my code. Same for NSEvent’s singleton methods, and so on.

Not sure why Core Audio isn’t an Objective C API

It’s for performance, right? It’s the only good reason I can think of. And, you know, it sounds sensible. I mean, ultra-low latency and all that, you probably don’t want that objc dispatch overhead.

I just did an experiment, however. I dislike working with C APIs, so I’m writing Cocoa wrappers for Core Audio, just exposing those pesky Component properties that take five lines to set or get, with simple methods. Suddenly I thought, “Wait, what if I try to use an objc method as a render callback? Those require very low latency and are called often. So I should be seeing some of that objc overhead.”.

Very unscientific comparison, comparing a simple sine renderer in c and objc, on an MBP 1.83x2 (source available on request):

• CPU usage in app using C callback: 3.0%
• CPU usage in app using ObjC callback: 3.1%

This isn’t, by far, any compelling evidence that Core Audio should be Objective C; I’m just saying it seems more feasible than I originally thought it’d be. Also, actually thinking about the problem, I realize that the callback’s only called 44100/512 ≈ 86 times a second and has about 10 ms to complete (astronomically long in computer terms).

But NeXT did it that way, didn’t they? I want to remember that NeXT had basically /everything/ in objc, including drivers and audio and such things. So, why not Mac OS X? NeXT was hardly known for being a slow OS. Tell me what I’m missing in the comments.

Three Points On Error Handling

I’ve been ranting on Twitter lately about how to do error checking the wrong way. Coincidentally, the latest topic on Mac Developer Roundtable was about just that, error handling.

I don’t think this episode of MDR was very interesting. It was essentially an overview of the three common error handling strategies (exceptions, enum returns, pass-by-ref error object), and some general C++/Java likeage from Uli (which is not a compliment :P). However, it got me writing a real blog entry, which is a good thing :)

So: Three things kept repeating in my head while I listened to MDR#3, hoping that someone’d mention it so that we can rid the world of more bad code.

First off, stay far far away from nested ifs. I don’t remember which Mac dev blog I read it on, maybe Wil Shipley’s or ridiculous_fish, but whoever it was recommended to always try to keep the code as far to the left as possible. Use the outermost block for the common, correct case, and use inner blocks for error cases. What I mean by this is, check for the error condition and treat it in-place, don’t check for the not-error case and treat the error in an else far far away. An example is in order…

// Don't:
void collectPhazon() {
  PhazonDetector *detector = findNearestPhazonDetector();
  if(detector) {
    Phazon *nearestPhazon = detector->scanForPhazon();
    if(nearestPhazon) {
      sendPhazonCollectorDrone(nearestPhazon->position());
    } else {
      beep(kNoPhazonFoundBeep);
    }
  } else {
    beep(kMajorlyCatastrophicErrorBeep);
  }
}

// Do:
void collectPhazon() {
  PhazonDetector *detector = findNearestPhazonDetector();
  if(!detector) { beep(kMajorlyCatastrophicErrorBeep); return; }
  
  Phazon *nearestPhazon = detector->scanForPhazon();
  if(!nearestPhazon) { beep(kNoPhazonFoundBeep); return; }
  
  sendPhazonCollectorDrone(nearestPhazon->position());
}

This also applies to smaller scopes, such as for and while loops. Instead of having a big if block inside the loop, say if(error_condition) continue;. Feel free to use gotos as well, eg:

  Baz *a() {
    ...
    if(error) goto a_cleanup;

    return myBaz;
  a_cleanup:
    free(myBaz);
    fclose(bazHandle);
    return NULL;
  }

The same effect can be achieved with try-catch-finally, so use whichever makes your code the easiest to understand.

Secondly, never use just a boolean NO or a nil return value as an error return for a method or function that can fail in more than one way. If you do, the user of your library (or yourself, if it’s in your app!) can’t know what actually went wrong.

This leads to error dialogs such as “Couldn’t connect to iPod” — why not? Because one isn’t connected? Because it’s the wrong model? Because I hit it with a hammer? The sentence is lacking a ‘because’ because the reason is hidden behind bad abstractions.

This is where NSError is your friend, and I think that this is the answer to Scotty’s burning question: ‘When should I use NSError’? The answer is simple: whenver there’s more than one way to fail; whenver a NO/nil can mean more than one kind of failure.

Third, and this was actually mentioned, if you’re checking for errors, make sure you understand /why/ you’re checking for that error, and what the logical response is.

This snippet from Apple’s sample “ComplexPlayThru” is a perfect example of how not to do it (ComplexPlayThru.cpp, line 353-354):

  comp = FindNextComponent(NULL, &desc);
  if (comp == NULL) exit (-1);

Nice! My app suddenly disappeared with no explanation whatsoever! And I’m sure no other part of the app uses the error code ‘-1’! Awesome. Also, the component that they’re looking for is an Apple default, must-be-there-or-any-sound-app-will-crash component. It’s safe to assume that it will always be there, and just skip the error check.

This also goes against Gus’ advice: please don’t just copy any sample code you find, even if it’s from Apple.

NSURLConnection, rails, apache, spaces in URLs and “Your browser sent a request that this server could not understand”

My Rails application uses redirect_to at one point in my code where it redirects to a pdf document on an apache server. The URL that it redirects to contains spaces. URLs may not contain spaces. redirect_to does not escape these spaces, but issues a ‘302 Found’ redirect response with the unescaped URL.

When my Cocoa application receives this redirect request through the currently running NSURLConnection, it follows the new url. In 10.4, it escaped the URL before sending the GET request. In 10.5, this is no longer the case, and apache (correctly) barfs on the request with

Bad Request

Your browser sent a request that this server could not understand.

The request line contained invalid characters following the protocol string.

I’m guessing first or second; I’m supposing there’s a very good reason why Apple chose to change the behaviour of NSURLConnection. Also, the Rails documentation does say, String starting with protocol:// (like http://): Is passed straight through as the target for redirection, which would put the responsibility square on me. However, Rails is generating an invalid response, so I’ll go with blaming rails.