Dispatch for the Polar Game in Dylan

So with some assistance from the folks on the Dylan Hackers mailing list I got enough clues to press on and get my Dylan implementation of the Polar game working, at least up through the end of the first board. I haven't verified that every possible tile interaction works yet, but it's a start. This seems like a silly problem, but it interests me because of several problems. Dispatch (or simulated dispatch) is "double dispatch," based on the types of two different objects interacting. The breakdown of how to categorize the classes of objects isn't 100% clear -- there is some overlap that I can't seem to eliminate, and the compiler has to decide what methods constitute the most specific match. And finally, the logic does not seem easily fixed in either classes representing the tiles, or a single class representing the board.

If I wrote it in C, the tile classes pretty much wouldn't exist; they'd exist only as flag enumerations in an array of tiles, and the code would consist mostly of switch or if-else logic that did the "double dispatch" in a fixed, predictable order, without relying on the compiler very much. Objective-C, again mostly C with a thin layer for representing classes, doesn't really give these classes enough features to make them worthwhile, so I will probably just keep the board (the model in the model/view/controller) and treat the tiles like I would in plain old C. But in Dylan they have an interesting life in terms of how they can be used to organize the code -- using generic functions -- so that I'm doing less writing of "code to find code" -- that is, code to look at run-time identity of objects and "manually" dispatch on it.

Here are the tile classes:

define abstract class <tile> ( <object> ) end;
define abstract class <blocking> ( <tile> ) end;
define abstract class <walkable> ( <tile> ) end;
define abstract class <movable> ( <blocking> ) end;
define abstract class <fixed> ( <blocking> ) end;
define class <bomb> ( <movable> ) end;
define class <heart> ( <movable> ) end;
define class <ice-block> ( <movable> ) end;
define class <house> ( <fixed> ) end;
define class <mountain> ( <fixed> ) end;
define class <edge> ( <fixed> ) end;
define class <tree> ( <blocking>, <walkable> ) end;
define class <empty> ( <walkable> ) end;

Oy, is that a pain to replace all the angle brackets with HTML entities... there must be a better way in Blogger! Anyway, these tile classes have no state -- in Dylan, no slots -- and are used in my program solely for their types. Edge does not actually appear on the board, but is used internally when the penguin or another moving object attempts to interact with the edge of the board. We treat this just like another blocking object, as if the board was surrounded by immovable, inert objects.

Diagramatically, like so:

There did not seem to be one absolute best way to represent these classes. I want to organize their abstract base classes by behavior, but their behavior does not break down with complete consistency -- for example, tiles with trees are "blocking" with respect to sliding objects, except for the penguin. The ice block is "blocking" except for the case where the penguin pushes it and it is not adjacent to an empty tile -- then it is crushed. Bombs and hearts seem to have the same interactions with mountains and houses whether they traverse an empty tile by sliding first across one or more empty tiles, while ice blocks behave differently -- if they slide first and then collide with a blocking object, they are not destroyed, they just stop. So the groupings of the concrete classes isn't going to be able to coherently divide up all their possible behaviors.

The scheme I settled on for object interactions involves three layers, in the form of three generic functions. The first represents interactions of the player's "avatar," the penguin, with tiles:

define generic pushTile( model :: <model>, dir :: <dir>,
    pos :: <pos-or-false>, target-tile :: <tile> );

define method pushTile( model :: <model>, dir :: <dir>,
    target-pos :: <pos>, target-tile :: <walkable> )
    => ( result :: <boolean> )
    model.penguin-pos := target-pos;
    #t;
end;

define method pushTile( model :: <model>, dir :: <dir>,
    target-pos :: <pos>, target-tile :: <movable> )
    => ( result :: <boolean> )
    let next-pos :: <pos-or-false>  = 
        getAdjacentPos( target-pos, dir );
    let next-tile = getTileAtPos ( model, next-pos );
    collide( model, dir, target-pos, target-tile,
        next-pos, next-tile );
    #f;
end;

define method pushTile( model :: <model>, dir :: <dir>,
    target-pos :: <pos-or-false>, target-tile :: <fixed> )
    => ( result :: <boolean> )
    #f;
end;

Dylan doesn't strictly require that I define the generic function before defining methods for it; if I just start writing methods with the same name, it will assume that I mean them to be associated with a generic function. But defining the generic function first has a benefit -- the compiler will tell me whether my methods make sense, in that their parameters are all strictly the same type or a more specific subclass of the types mentioned in the define generic statement. Note that <pos-or-false> is a type union of a simple <pos> class with singleton( #f ). The generic uses that type union, but one of the methods are more specific: they require an actual <pos> instance and will not accept #f.

The first method handles the case where the penguin is pushing a <walkable> tile, and returns false to indicate that the penguin position can be updated. The pos must not be #f. The second method handles pushing any <movable> tiles. And the third handles the <fixed> tiles. Between the three methods, you might notice that they cover all the leaf classes (all the instantiable classes) in the graph above, in 3 separate groups with no overlapping. You could shade in the leaf nodes covered by the three different methods with three different colors, going from the abstract classes mentioned downward, and all the leaves would all be colored and none would be colored more than once:

So on the tile parameter, the coverage of the concrete classes is complete and the dispatch algorithm should not have any difficulty. Combined with the position parameter, though, the situation is slightly trickier. At runtime, a caller could call pushTile with #f for pos and <empty>; or <bomb> for tile and the dispatcher would, correctly, throw up its hands at this point and say that there was no applicable method. I could have defined a more general method to handle this case, but I didn't -- there shouldn't ever be an empty or bomb tile without a corresponding valid position, since they are real tiles on the board, and I want the runtime to help me catch that case if it ever happens. Similarly, I could have defined a method that handled <blocking> or <tile> as part of this generic function but the whole point is that I don't know what to do with those more general classes here.

So, you may notice that the middle pushTile method calls collide with a second tile and position, adjacent to the first in a specified direction. That generic function looks like this:

define generic collide( model :: <model>, dir :: <dir>,
    tile-1-pos :: <pos>, tile-1 :: <movable>,
    tile-2-pos :: <pos-or-false>, tile-2 :: <blocking-or-empty> );

define method collide( model :: <model>, dir :: <dir>,
    movable-pos :: <pos>, movable-tile :: <movable>,
    next-pos :: <pos>, next-tile :: <empty> )
    slide ( model, dir, movable-pos, movable-tile,
            next-pos, next-tile );
end;

define method collide( model :: <model>, dir :: <dir>,
    ice-block-pos :: <pos>, ice-block-tile :: <ice-block>,
    icebreaking-pos :: <pos-or-false>,
    ice-breaking-tile :: <blocking> )
    setTileAtPos( model, ice-block-pos, $the-empty );
end;

define method collide( model :: <model>, dir :: <dir>,
    heart-pos :: <pos>, heart-tile :: <heart>,
    house-pos :: <pos>, house-tile :: <house> )
    setTileAtPos( model, heart-pos, $the-empty );
    decrementHeartCount( model );
end;

define method collide( model :: <model>, dir :: <dir>,
    bomb-pos :: <pos>, bomb-tile :: <bomb>,
    mountain-pos :: <pos>, mountain-tile :: <mountain> )
    setTileAtPos( model, bomb-pos, $the-empty );
    setTileAtPos( model, mountain-pos, $the-empty );
end;

define method collide( model :: <model>, dir :: <dir>,
    movable-pos :: <pos>, movable-tile :: <movable>,
    blocking-pos :: <pos-or-false>, blocking-tile :: <blocking> )
end;

You might notice that before long you hit yet another method call you haven't seen before -- slide. This is, as you might guess, yet another generic function. (Doesn't this program every get around to doing anything? In fact it does, but this is the often-paradoxical-seeming logic of object-oriented design -- individual methods that seem too small and simple to get anything done can actually get a lot done together, especially when aided by a smart dispatcher that eliminates most of the need to write "code to find code."

The type-union <blocking-or-empty> allows us to specify, for our generic function, as tight a class as possible out of two otherwise disjoint sections of our class diagram. We don't have to loosen the type specification needlessly by using <tile>, which would allow <walkable> as a valid class for this parameter. Meanwhile, we can loosen tile-2-pos so that we make our intention to allow #f explicit here.

The methods break down as follows. The first one handles any movable tile that is moving onto an empty tile, by calling a slide method to be defined later. The second one is a special case to handle the crushable <ice-block> class -- if it is pushed into the world edge, or any other object, it is destroyed (replaced with $the-empty class instance). The third and fourth methods handle specific interactions between hearts and houses, and bombs and mountains. And finally, to handle the case where the penguin pushes a heart against a mountain, or a bomb against the edge of the world, we have a less specific method that dispatches on <movable> and <blocking>. This prevents the runtime from generating an error in this case, but also gives us a place where we could generate some kind of feedback to the user, like a special sound to indicate failure.

The breakdown of instantiable tile classes here is much more complex, especially given that we are dispatching on two class parameters drawn from the same hierarchy. We could try coloring them by using two copies of the diagram:

Err, that's pretty, but is it helpful? I'm using colors and borders to indicate that classes are handled by specific methods, but the main thing I hope I'm illustrating is that, unlike with the first generic function, in this one there is significant overlap between the classes handled by the different methods. This is where the dispatch mechanism really has to shine. There is an ordering that makes sense from my point of view, and that is one in which the most specific matching method will be called. However, as you can see, quantifying "most specific" may be slightly complex when dispatching on more than one class parameter, throwing in type-unions for fun. Fortunately this code is now working, but while I was developing it I became familiar with a warning message in Open Dylan that says something like "the method dispatch handling this set of classes is determined by arbitrary and capricious rules" -- indicating that the dispatch logic is still considered a work in progress. I was concerned that the current version of the Open Dylan compiler wasn't quite solid enough to make this work, but it does seem to work. The backup plan was to dispatch entirely on type-unions made up of different sets of singletons, but that is longer and obscures what is meant by the abstract classes.

I won't go to the trouble to do the same diagram on my slide method, but that code looks like this:

define generic slide( model :: <model>, dir :: <dir>,
    movable-pos :: <pos>, movable-tile :: <movable>,
    next-pos :: <pos-or-false>, next-tile :: <blocking-or-empty> );

define method slide( model :: <model>, dir :: <dir>,
    movable-pos :: <pos>, movable-tile :: <movable>,
    next-pos :: <pos>, next-tile :: <empty> )
    let next-next-pos :: <pos-or-false> =
        getAdjacentPos( next-pos, dir );
    let next-next-tile = getTileAtPos( model, next-next-pos );
    setTileAtPos( model, next-pos, movable-tile );
    setTileAtPos( model, movable-pos, $the-empty );
    slide( model, dir, next-pos, movable-tile ),
           next-next-pos, next-next-tile );
end;

define method slide( model :: <model>, dir :: <dir>,
    movable-pos :: <pos>, movable-tile :: <movable>,
    next-pos :: <pos-or-false>, next-tile :: <blocking> )
    collide( model, dir, movable-pos, movable-tile,
              next-pos, next-tile );
end;

define method slide( model :: <model>, dir :: <dir>,
    ice-block-pos :: <pos>, ice-block-tile :: <ice-block>,
    next-pos :: <pos-or-false>, next-tile :: <blocking> )
end;

Aaaand that's pretty much the whole of the logic for handling interaction between the penguin and the various tiles. Note that we call ourselves recursively. It looks kind of like we have no termination condition! Except note that the method isn't calling itself, it's doing the same method dispatch that found it in the first place. When we come to a termination condition for our recursions, we'll actually call a different method of the same generic function -- most likely the third one, where a sliding object encounters a blocking object. That condition can include hitting the edge of the board. And fortunately -- we already have logic for that, mostly -- in our collide generic function! So sliding hearts and bombs are handled just the same as if they were pushed instead of ending a slide.

There's a slightly tricky part where we want to bind up the next tile beyond the two tiles we were dispatched on, then perform two set operations to move the currently sliding tile, then dispatch on the starting tile at its moved position. To figure that out I had to draw some bits of the game board with circles and arrows (but not a paragraph on the back of each one to be used as evidence against me). (If you don't get that reference, either you're too young or I'm too old!)

This is not the whole program, obviously, but these are the key methods for encoding the collisions between tiles. If you'd like to play with the whole program, you might come and join the Dylan Hackers mailing list, or leave me a note. If there is interest I'll publish it, here or elsewhere. I am now curious as to how a similar set of overlapping dispatches -- via pattern matching, perhaps? -- might look in Haskell. I might try to write that next. If you've got an idea about the clearest and most idiomatic way to do it, I welcome your comments.

UPDATE: the code, such as it is, is on GitHub. Ignore the license for now; I have to decide on an actual license. See: https://github.com/paulrpotts/arctic-slide-dylan