Objective-C, Day 6 (Back from Dylan-land)

I've been a little sick -- maybe something in our water, because our tap water started tasting like hose water -- but it seems to be clearing up. There's nothing like having flu-like symptoms to celebrate the first couple of days of summer! But I'm more-or-less back on my feet, although still a little queasy. Yesterday the weather station closest to our home in Saginaw hit 93, "feels like 100" with the humidity. I know that's nothing compared to some of the folks out west, but it came on us pretty fast, and I'd happily trade 100 in the low-humidity desert for 90 in Saginaw. I've got the A/C unit set up in the home office, since we finally need it, and I'm pressing on with my re-engineering of the old Mac Polar game.

The Dylan implementation I discussed last time helped focus my thinking about, if not the optimal, at least a fairly clear model for implementing game piece behavior. It also clarified what I should do with game objects in Objective-C, and that is "nothing." The "model" class still deserves to live, but the tile pieces just don't derive any benefit from being classes. The two main reasons are (1) Objective-C doesn't really support static methods in the sense that C++ does, and (2) Objective-C's dispatch mechanism isn't sophisticated enough to help us significantly save on "code to find code." So the tiles will be represented by plain old data, and we'll dispatch on their "types" with plain old logic.

The Dylan code has a small infrastructure of helper functions for accessing, filling, and logging the board state. I won't include all of it, because most of what it does is pretty clear from the function name, but there are functions like this:

define method getTileAtPos( model :: <model>, pos :: <pos-or-false> ) =>
    ( tile :: <tile> )
    if ( pos )
        getTileAtXY( model, pos.y-idx, pos.x-idx );
    else
        $the-edge;
    end if;
end;

define function getAdjacentPos( pos :: <pos>, dir :: <dir> )
    => ( pos-or-false :: <pos-or-false> )
    let y-offset :: <integer> = 0;
    let x-offset :: <integer> = 0;
    if ( dir == #"east" )
        x-offset := 1;
    elseif ( dir == #"south" )
        y-offset := 1;
    elseif ( dir == #"west" )
        x-offset := -1;
    elseif ( dir == #"north" )
        y-offset := -1;
    end if;
    let new-y-idx :: <integer> = pos.y-idx + y-offset;
    let new-x-idx :: <integer> = pos.x-idx + x-offset;
    if ( ( ( new-y-idx >= 0 ) & ( new-y-idx < $board-dim-y ) ) & 
         ( ( new-x-idx >= 0 ) & ( new-x-idx < $board-dim-x ) ) )
        make( <pos>, y-idx: new-y-idx, x-idx: new-x-idx );
    else
        #f
    end if;
end;

define method penguinPush( model :: <model> )
    => ( result :: <boolean> )
    let target-pos :: <pos-or-false> = 
        getAdjacentPos( model.penguin-pos, model.penguin-dir );
    let target-tile = getTileAtPos( model, target-pos );
    pushTile( model, model.penguin-dir, target-pos, target-tile );
end;

define method penguinMove( model :: <model>, dir :: <dir> )
    if ( model.penguin-dir ~= dir )
        model.penguin-dir := dir;
        format-out( "Penguin changed dir to %S\n", dir );
        force-output( *standard-output* );
    else
        if ( penguinPush( model ) )
            format-out ( "Penguin moved to %d, %d\n",
                model.penguin-pos.y-idx, model.penguin-pos.x-idx );
            force-output( *standard-output* );
        end if;
        if ( model.heart-count == 0 )
            format-out( "Heart count reached zero, level cleared!\n" );
            force-output( *standard-output* );
        end if;
    end if;
end;

define method penguinMoveTimes( model :: <model>, dir :: <dir>,
    times :: <integer> )
    for ( count from 1 to times )
        penguinMove( model, dir );
    end for;
end;

define method describe-tile( tile :: <tile> ) => ( str :: <string> )
    case
        ( tile == $the-empty     ) => "___ ";
        ( tile == $the-tree      ) => "tre ";
        ( tile == $the-mountain  ) => "mtn ";
        ( tile == $the-house     ) => "hou ";
        ( tile == $the-ice-block ) => "ice ";
        ( tile == $the-heart     ) => "hea ";
        ( tile == $the-bomb      ) => "bom ";
        otherwise                  => "??? ";
    end case;
end method;

define method describe-board( model :: <model> )
    for ( y-idx from 0 below $board-dim-y )
        for ( x-idx from 0 below $board-dim-x )
            format-out( "%S", 
                describe-tile( model.board[ y-idx, x-idx ]  ) );
        end for;
        format-out( "\n" );
    end for;
    force-output( *standard-output* );
end;

In Objective-C, I'm going to get rid of the singletons and tile classes altogether. They will live on in the comments, to clarify what the pseudo-object-dispatch is doing, and vestigially in the code. The board will have the same internal representation as the raw strings of data taken from the original Polar game resources. I'll keep my three main methods from the Dylan code -- pushing a tile, colliding, and sliding -- but these will be single Objective-C methods rather than multi-methods. The tiles are just chars:

#define POLAR_DATA_LEN_Y 4               // 4x24 grid
#define POLAR_DATA_LEN_X 24
#define POLAR_DATA_NUM_LEVELS 6          // In the original game

typedef char tile_t;

enum {
    polar_tile_empty = '0',
    polar_tile_tree,
    polar_tile_mountain,
    polar_tile_house,
    polar_tile_ice_block,
    polar_tile_heart,
    polar_tile_bomb,
    polar_tile_last = polar_tile_bomb
};

/*
    Not part of the level data; an extra flag value representing
    edge of board
*/
#define polar_tile_edge 'X'

typedef const char polar_level_array_t[POLAR_DATA_NUM_LEVELS]
                                      [POLAR_DATA_LEN_Y]
                                      [POLAR_DATA_LEN_X];

typedef char polar_board_array_t[POLAR_DATA_LEN_Y]
                                [POLAR_DATA_LEN_X];

extern polar_level_array_t polar_levels;

Why use #define for array indices and our tile pieces instead of const int and const char? Because using a const integral variable (yeah... a "const variable...") to dimension an array, or represent a case value for a switch statement, is still not standard C everywhere, although it is a common extension to allow the compiler to treat it as so in contexts like this. Enum works fine with characters. Oddly, I have a build issue when using enum values to define the array boundaries. I haven't figured out quite what that is all about -- I think it may be a Clang bug. But I'll worry about that later.

In the implementation file:

polar_level_array_t polar_levels =
{
    {
        "100000000000000100000400"
        "106020545000000000100100"
        "100000000000000050002300"
        "110000100000000000000000"
    },
    // Etc., for the other five levels
}

The model class gets one as a member:

@interface ArcticSlideModel : NSObject
{
    polar_level_array_t board;
    pos_t penguinPos;
    dir_e penguinDir;
    int heartCount;
}

We'll work ourselves down from the external API to the associated implementation:

// The external API
- (void)penguinMoveDue:(dir_e)dir;
- (void)penguinMoveNTimes:(int)n
                      due:(dir_e)dir;

penguinMoveNTimes:due: calls penguinMoveDue: which calls penguinPushDue:. In Dylan:

define method penguinPush( model :: <model> )
    => ( result :: <boolean> )
    let target-pos :: <pos-or-false> = 
        getAdjacentPos( model.penguin-pos, model.penguin-dir );
    let target-tile = getTileAtPos( model, target-pos );
    pushTile( model, model.penguin-dir, target-pos, target-tile );
end;

That's not strictly translatable to C, since we're taking advantage of a type-union to retrieve the position or #f with getAdjacentPos. This usage extends to the lower levels of the implementation, though, so for now we're going to continue to allow getAdjacentPos to return position values that are invalid, and explicitly check for them so we don't read or write at non-existent array indices.

pos_t getAdjacentPos( pos_t original_pos, dir_e dir )
{
    pos_t updated_pos = original_pos;
    int y_offset = 0;
    int x_offset = 0;
    switch ( dir )
    {
        case dir_east:
            x_offset = 1;
            break;
        case dir_south:
            y_offset = 1;
            break;
        case dir_west:
            x_offset = -1;
            break;
        case dir_north:
            y_offset = -1;
            break;
        default:
            NSLog( @"getAdjacentPos: invalid dir %d", dir );
    }
    updated_pos.y_idx += y_offset;
    updated_pos.x_idx += x_offset;;
    return updated_pos;
}

We rely on posValid to explicitly check for invalid tile cases:

BOOL posValid( pos_t pos )
{
    return ( ( ( pos.y_idx >= 0 ) &&
               ( pos.y_idx < POLAR_DATA_LEN_Y  ) ) &&
             ( ( pos.x_idx >= 0 ) &&
               ( pos.x_idx < POLAR_DATA_LEN_X ) ) );
}

That should be pretty non-controversial. Note that BOOL in Objective-C is not a real type; it's just a #define and a typedef based on char_t. So don't get a false sense of security -- it has the same problems that fake bool types always have, and always will have, in straight C.

Anyway, we can now implement our pushTile function. Here is the Dylan:

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

// Handle walkable (empty or tree tile). The penguin
// is allowed to move onto this tile (indicated by
// returning #t).
define method pushTile( model :: <model>, dir :: <dir>,
    target-pos :: <pos>, target-tile :: <walkable> )
    => ( result :: <boolean> )
    model.penguin-pos := target-pos;
    #t;
end;

// Handle movable (bomb, heart, ice block) -- call
// collide which specializes in various combinations.
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;

// Handle fixed (house, mountain, edge) -- do nothing.
// The GUI might play a "fail" beep.
define method pushTile( model :: <model>, dir :: <dir>,
    target-pos :: <pos-or-false>, target-tile :: <fixed> )
    => ( result :: <boolean> )
    #f;
end;

Doing all our own dispatch logic, here is a single method in Objective-C:

- (BOOL)pushTile:(tile_t)target_tile
             due:(dir_e)dir
              at:(pos_t)target_pos
{
    switch ( target_tile )
    {
        /*
            Handle the "walkable" cases. The penguin is allowed to move
            onto these tiles, indicated by returning YES
        */
        case polar_tile_empty: /* FALL THROUGH */
        case polar_tile_tree:
            NSLog( @"pushTile: walkable\n" );
            self->penguinPos = target_pos;
            return YES;

        /*
            Handle "movable" cases. Call collide which specializes in
            various combinations.
        */
        case polar_tile_bomb:      /* FALL THROUGH */
        case polar_tile_heart:     /* FALL THROUGH */
        case polar_tile_ice_block:
            NSLog( @"pushTile: movable\n" );
            {
                pos_t next_pos = getAdjacentPos( target_pos, dir );
                /*
                    Note that next-pos can be invalid, which results
                    in the special "edge" tile value.
                */
                tile_t next_tile = [ self getTileAtPos:next_pos ];
                [ self collideTile:target_tile atPos:target_pos
                    due:dir withTile:next_tile
                    atSecondPos:next_pos ];
            }
            return NO;

        /*
            Handle "fixed" cases. Do nothing; the GUI might play
            a "fail" beep.
        */
        case polar_tile_mountain:   /* FALL THROUGH */
        case polar_tile_house:
            NSLog( @"pushTile: fixed\n" );
            return NO;

        default:
            NSLog( @"pushTile: unexpected tile value %d\n",
                   target_tile );
            return NO;
    }
}

And as in the Dylan version, for interesting interactions this method defers to another method:

- (void)collideTile:(tile_t)first_tile
              atPos:(pos_t)first_pos
                due:(dir_e)dir
           withTile:(tile_t)second_tile
        atSecondPos:(pos_t)second_pos
{
    BOOL empty = ( second_tile == polar_tile_empty );
    /* Blocking includes the special edge tile value */
    BOOL blocking = ( second_tile != polar_tile_empty );
    BOOL mountain = ( second_tile == polar_tile_mountain );
    BOOL house = ( second_tile == polar_tile_house );

    BOOL ice_block = ( first_tile == polar_tile_ice_block );
    BOOL bomb = ( first_tile == polar_tile_bomb );
    BOOL heart = ( first_tile == polar_tile_heart );
    BOOL movable = ( ice_block || bomb || heart );

    if ( bomb && mountain )
    {
        /*
            When a bomb meets a mountain, both bomb and mountain blow up
        */
        NSLog( @"collideTile: bomb / mountain\n" );
        [ self setTile:polar_tile_empty AtPos:first_pos ];
        [ self setTile:polar_tile_empty AtPos:second_pos ];
    }
    else if ( heart && house )
    {
        /*
            When a bomb heart meets a house, we are closer to winning
        */
        NSLog( @"collideTile: heart / house\n" );
        [ self setTile:polar_tile_empty AtPos:first_pos ];
        [ self decrementHeartCount ];
    }
    else if ( ice_block && blocking )
    {
        /*
            When an ice block is pushed directly against any
            blocking tile (including the board edge), it is destroyed.
        */
        NSLog( @"collideTile: ice block / blocking\n" );
        [ self setTile:polar_tile_empty AtPos:first_pos ];
    }
    else if ( movable )
    {
        if ( empty )
        {
            /*
                A movable tile pushed onto an empty tile will slide
            */
            NSLog( @"collideTile: movable / empty: start slide\n" );
            [ self slideTile:first_tile atPos:first_pos due:dir
                   toTile:second_tile atSecondPos:second_pos ];
        }
        else if ( blocking )
        {
            /*
                When a generic movable piece meets any other
                blocking pieces not handled by a special case
                above, nothig happens; it stops. Maybe play
                a "fail" beep.
            */
            NSLog( @"collideTile: movable / blocking\n" );
        }
    }
}

This could have been written with a bunch of ugly, redundant-looking switch statements, but the duplicated cases and defaults just don't seem as clear to me as making flags that precisely describe the nature of the "double dispatch" going on. In this program, having to spell out the logic (using code to find code) is not really onerous. But the problem comes, of course, in code where we keep having to add special cases. I could refactor this method to call some smaller methods but that doesn't seem like a real win. In the Dylan implementation if I wanted to add another special interaction, it might only require adding another generic function. That's assuming my whole class hierarchy didn't change.

Finally, the slide method:

- (void)slideTile:(tile_t)first_tile
            atPos:(pos_t)first_pos
              due:(dir_e)dir
           toTile:(tile_t)second_tile
      atSecondPos:(pos_t)second_pos
{
    BOOL empty = ( second_tile == polar_tile_empty );
    /* Blocking includes the special edge tile value */
    BOOL blocking = ( second_tile != polar_tile_empty );
    
    BOOL ice_block = ( first_tile == polar_tile_ice_block );
    BOOL movable = ( ice_block ||
                     first_tile == polar_tile_bomb ||
                     first_tile == polar_tile_heart );

    if ( ice_block && blocking )
    {
        // A specific movable tile, ice-block, meets a
        // blocking tile; don't call collide since the behavior
        // of a sliding ice block is different than a pushed ice
        // block. It just stops and doesn't break.
        NSLog( @"slideTile: ice block / blocking\n" );       
    }
    else if ( movable && empty )
    {
        // A movable tile interacting with an empty tile --
        // move forward on the board and call slide again.
        NSLog( @"slideTile: movable / empty\n" );
        pos_t third_pos = getAdjacentPos( second_pos, dir );
        tile_t third_tile = [ self getTileAtPos:third_pos ];
        [ self setTile:polar_tile_empty AtPos:first_pos ];
        [ self setTile:first_tile AtPos:second_pos ];
        [ self slideTile:first_tile atPos:second_pos due:dir
                  toTile:third_tile atSecondPos:third_pos ];
    }
    else if ( movable && blocking )
    {
        // A movable tile meets a blocking tile: call collide to
        // handle heart/house, bomb/mountain, edge of world, etc.
        NSLog( @"slideTile: movable / blocking\n" );
        [ self collideTile:first_tile atPos:first_pos due:dir
                  withTile:second_tile atSecondPos:second_pos ];
    }
}

That's the bulk of it. Here's an excerpt from the log as it finishes up the first level:

ArcticSlide[2279:c07] penguinPush: tile at 2, 5 pushed
ArcticSlide[2279:c07] pushTile: walkable
ArcticSlide[2279:c07] Penguin moved to: 2, 5
ArcticSlide[2279:c07] Penguin direction changed to EAST
ArcticSlide[2279:c07] Penguin moving EAST
ArcticSlide[2279:c07] penguinPush: tile at 2, 6 pushed
ArcticSlide[2279:c07] pushTile: movable
ArcticSlide[2279:c07] collideTile: movable / empty: start slide
ArcticSlide[2279:c07] slideTile: movable / empty
ArcticSlide[2279:c07] collideTile: heart / house
ArcticSlide[2279:c07] Heart count reached zero, level cleared!
ArcticSlide[2279:c07] ArcticSlideModel board state:
tre__________________________________________treice_____________________
tre_________mtn_______________________________________tre______tre______
tre____________________________________________________________hou______
tretre____________treice________________________________________________

I'll put in logic to play the remaining levels soon, as additional test cases.

Note that I kept the recursive call to slideTile. It's not an idiom commonly used in C and Objective-C. We only recurse when the moving tile traverses more than one empty tile, and so never more than 23 times. I like to write algorithms recursively when possible while sketching out code. If direct recursion like that is verboten, it can be removed. I don't think my compiler is optimizing it out. But the termination logic now starts to look redundant:

else if ( movable && empty )
    {
        while ( NO == blocking )
        {
            pos_t third_pos = getAdjacentPos( second_pos, dir );
            tile_t third_tile = [ self getTileAtPos:third_pos ];
            [ self setTile:polar_tile_empty AtPos:first_pos ];
            [ self setTile:first_tile AtPos:second_pos ];
            first_pos = second_pos;
            second_pos = third_pos;
            second_tile = third_tile;
            blocking = ( third_tile != polar_tile_empty );
        }
        if ( ice_block )
        {
            NSLog( @"slideTile: ice block / blocking\n" );
        }
        else
        {
            [ self collideTile:first_tile atPos:first_pos due:dir
                      withTile:second_tile atSecondPos:second_pos ];
        }
    }

And if I don't want to call back into methods in my own call chain at all -- that is, if I have to give up calling collideTile, well, I could do that but it would involve putting copying of the logic from collideTile into this method, and by that point this method will be badly breaking the "DRY" (Don't Repeat Yourself) axiom, so it might be clearer to turn collideTile and slideTile into one method.

Anyway, the heat is building up in my office and it is about dinnertime. I think it's time to move on to some user interface, so the app can actually be played on an untethered iOS device. I also am still struggling a bit to get going on a Haskell implementation. I know it can be done -- people describe Haskell as a good imperative language too, for modeling state as safely as possible -- but let's just say that the chapters and examples I'm reading haven't quite "gelled" in my brain. I still feel like someone studying a foreign language who can read it and understand it when spoken, but not speak it yet -- especially the Monadic dialects. But I'm still working on that.

UPDATE: I have put the source on GitHub, such as it is -- for now, ignore the license text; I need to pick an actual license. See: https://github.com/paulrpotts/arctic-slide-ios

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

Objective-Dylan, or Perhaps Subjective-C?

Yesterday my wife took the kids with her on an overnight trip to Ann Arbor so I've had a bit of extra quiet time. How am I making use of this bounty? Getting on with some minor home repairs? Cleaning my office from top to bottom? Er, no... porting the game logic I've written so far in Objective-C back to Dylan, so that I can do some more thinking about it.

So after a phone job interview yesterday (which went well, I thought -- I'm optimistic about this possibility!) I started working on this task, and then about twelve hours later, around 2 a.m., I had the basic setup and population of the game board working. It's embarrassing to admit how long it took. I started on my Mac, and when I began encountering constant runtime errors switched over to my Ubuntu box, thinking that the Mac version of Open Dylan might just be broken (it isn't; I got the identical behavior on the Linux build). I finally figured out workarounds -- it's funny how taking a break clears my head far better than pressing on ever does -- then read a little Gene Wolfe (I'm working my way through In Green's Jungles, one of his books I've repeatedly tried and failed to finish), and fell asleep with no children in the bed to kick or otherwise interfere with a good night's sleep. I'm back up this morning, had a bath, and I'm drinking a large coffee with soy creamer and stevia and trying to hold off on a lunch break until I have some more done. It's about 10 a.m. and I'm expecting my family back in about six hours, so the race is on!

This has taken far longer than I hoped; I lost quite a bit of time stumbling across things in Open Dylan that still seem just plain broken. I had to start working on a smaller and smaller program to figure out exactly what was broken. These things I've flagged in comments, as places where, basically, I wish Dylan worked a certain way, and it doesn't. I may just be asking for something that doesn't quite match the original spec or isn't quite possible, but I'll share those with the Dylan Hackers team and see if it seems like I can help with them. The biggest thing that was broken, though, was me -- my brain, that is -- since it's been a long time since I've worked with Dylan's type-union and singleton pseudo-classes and I had forgotten the details. The compiler was not a big help with this, since it is such a dynamic language and leaves an awful lot of things to the runtime to figure out, which it does by throwing an error message that may or may not help much. The documentation is a bit scanty, but it does contain everything you need to know, if you re-read and squint at the scanty examples that are out there hard enough.

The good news is that the port is working and I'd like to share it. Dylan is still up there with Scheme (and now Haskell) as one of my favorite languages for designing programs -- yes, even though Dylan is quite old as languages go. I like to see what it can do especially with generic functions and its sophisticated model for object-oriented dispatch. I've been a little stymied as to how to express the design best in Objective-C. If it was a complicated game design, I wouldn't feel bad about having a program that looked complex. But it's really an elegantly simple game, and so I feel like the implementation should reflect that. My Objective-C implementation has been feeling more and more bloated and pointlessly complex, although it works, so my thought was to get it down to a simple implementation that takes full advantage of Dylan's object-oriented programming features, largely borrowed from CLOS, and then port that back to Objective-C, adding whatever minimalist support is needed to fake up some of the features that Dylan gives me that Objective-C doesn't have. This might be by way of also writing a Haskell or Scala implementation later, for yet more learning and language comparison, although really what I should focus on is getting the iOS GUI up and working so that I have something to show people.

Anyway, I've got a Dylan program that plays the Polar game, using singletons to represent tile types, and methods dispatched on singletons to handle specific kinds of collisions. The classes -- which are empty, pretty much used only for their usefulness as types, for driving dispatch -- are like so:

In Dylan you can create some instances, and create something called a type-union, which is something that is a type, I think, but not a class. You can use it to define a slot type or a parameter type. But you can't make one:

define constant $the-bomb = make();
define constant $the-empty = make();
define constant $the-heart = make();
define constant $the-house = make();
define constant $the-ice-block = make();
define constant $the-mountain = make();
define constant $the-tree = make();

define constant  = type-union(
    singleton( $the-bomb ), singleton( $the-empty ),
    singleton( $the-heart ), singleton( $the-house ),
    singleton( $the-ice-block ), singleton( $the-mountain ),
    singleton( $the-tree ), singleton( #f ) );

And eventually dispatch on singletons -- meaning that a given method will be called with it is called with references to the exact objects that you specify:

define method collide( model :: <model>, dir :: <dir>,
    heart-pos :: <pos>, heart-tile == $the-heart,
    house-pos :: <pos>, house-tile == $the-house )
    format-out( "collide: $the-heart / $the-house\n" );
    setTileAtPos( model, heart-pos, $the-empty );
    model.decrementHeartCount();
end;

That gives you an idea of how some of the code in the Dylan program is organized. I have it mostly working, however, I'm not going to present the full code quite yet because I have a crashing bug, and I haven't yet been able to figure out if it is a dumb mistake on my part or a compiler or runtime bug in Open Dylan. I've also asked the Dylan hackers to take a look at my design and see what they think -- if they can find, as I put it, "a simpler design struggling to get out." Which is always the challenge, when trying to write not just functional, but model code, isn't it?

Generic Functions and Pointers to Member Functions

People who know me know that I still carry a torch for a wonderfully-designed but little-used programming language called Dylan. In my arrogant opinion Dylan took much of the best of Common Lisp and CLOS, regularized and streamlined it, and gave it a syntax more acceptable (due to familiarity) to programmers from the C and C++ world (although this annoyed some prefix syntax fans in the process). Dylan is a multi-paradigm language, where "everything is an object," designed to support functional styles, object-oriented styles, and procedural styles.

Dylan is still alive and kicking with several impressive implementations available here including d2c, an amazing compiler that generates C code from Dylan source, and which is written primarily in Dylan itself, and the formerly commercial Functional Objects compiler, which generates native machine code. I have not studied the Functional Objects codebase very much, but I have spent time with d2c. It is an amazing piece of code. Studying it makes me wish I was able to strap on an auxilliary brain or two and take a pill that gave me a post-graduate education in language implementation without all that tedious mucking about in graduate school, so I could contribute something useful to the project instead of just an occasional bug report or ignorant question.

In Dylan, and in Dylan's sire Common Lisp with CLOS, classes contain data. Classes don't contain methods. Methods are implemented using a construct known as a generic function. A generic function lets you define several specialized functions to operate on objects of different classes. A variety of functions with the same name are bundled together; as you define additional functions, they get added to the generic function. At run-time, when you make a call to the generic function, the specific function chosen can depend on the actual run-time type (the class) of the object you send to it. Classes can inherit from one or more other classes; this inheritance tree is used to make the decision about which actual method to call for a given object. Generic functions can be specialized in other ways; they are extraordinarily flexible and powerful. But I'm only going to touch today on generic function dispatch specialized on the class of the incoming object, incoming parameters, and return type.

In his article "A First Look at Dylan: Classes, Functions, and Modules," Steve Strassmann writes:

Object-oriented languages, including Dylan, provide polymorphic functions, which means a given function may be executed as one of several possible implementations of that function, called methods... when Dylan sees a call to name(x), depending on what type of object is, one of several methods is selected and executed. In Dylan, name is called a generic function, consisting of a family of name methods that implement the functionality of name for various classes (see Figure 2). Each of these methods "belongs to" its generic function (in this case, name) rather than to a class. This is a key point; it's the core difference between C++'s object model and Dylan's.

In terms of implementation, this means that when you make a generic function call, the generic function isn't a "standard" function; a dispatch mechanism comes into play to select the proper generic function based on the call's arguments. The run-time context contained in the object is explicitly passed to the function.

Strassmann gives examples generic function; I have stripped down one of his examples somewhat here:

// No type declaration, works on any type of object
define method double (x)
   pair(x, x);
end method double;

// Works on all numbers
define method double (x :: <number>)
   2 * x;
end method double;

// Works on all strings
define method double (x :: <string>)
   concatenate(x, x);
end method double;

When double is invoked on an argument, the most specific method is invoked... for example, double("foo") would invoke the third method, because <string> is more specific than <object>, which is what the first method is specialized to. If no match is found, Dylan will catch it and signal an error.

Besides a plethora of different ways to specialize generic functions, Dylan supplies various forms of introspection; if you want to extend or alter the run-time dispatch, you can do so.

To C++ programmers, this is inside-out. In C++, classes "contain" methods, known more commonly as "member functions" because they are "members" of the class. C++ supports polymorphism and dispatch based on run-time type. I'm going to talk a little bit about how objects and member functions work together in C++ and how you can use them, and how, when we look at C++ in light of Dylan or CLOS, C++ actually gives us a subset of object dispatch, presented in an obfuscated form.

Let's say you don't want to just make a new subclass with specialized methods and allow polymorphic dispatch to operate based on run-time type, but instead you want to handle your own run-time dispatch. In Dylan you can do this using introspection and some handlers that allow you to override the standard generic function dispatch. Since you have the object and the generic function and can get at specific functions, you can just call them, passing the object.

To do the same thing in C++ you need to work around the fact that C++ obfuscates what is actually going on when you call a method. You can do this by using a slightly obscure C++ construct called the pointer to member. For the present discussion the member in question will always be a member function, but keep in mind that pointers to members can work with data members as well. This use is probably even less common since if you have an object, or a pointer or reference to an object you can access public members directly as you would access members of a struct, or via an accessor function; I would think that pointers to data members are necessary only for serious runtime hacking or compiler implementation. But the key point here is that C++ pretends that both data members and member functions are part of classes, while CLOS and Dylan much more explicitly separate these concepts.

Pointers to member functions are uncommonly used, probably in part because of its somewhat obscure syntax. The only place I've seen them used, in fact, is the Darwin kernel's IOKit source code. Recently I've had a need to customize class behaviors at runtime without subclassing and without a complete refactoring of a class into modular pieces, so I've been investigating the construct again.

The syntax is awkward, but it is consistent with the general C school of thought which says that declarations are read backwards (right to left). In C, if you have an integer variable:

int i;

to make a pointer out of it, you insert an asterisk to the left of the variable name:

int * i;

Similarly, if you have a prototype for a function returning int and taking an int parameter:

int fn ( int );

to take a pointer to it, you insert an asterisk to the left of the name:

int * fn ( int );

but the order of evaluation means that the parser reads it as a function returning a pointer to int. So you have to change the order of evaluation using parentheses:

int ( *fn ) ( int );

Now fn means a pointer to a function, not a function returning a pointer.

A member function is basically the same, with the addition of the class name and the scope resolution operator (::). When you are declaring your class, this prefix is not wanted or needed (it is implicit within the class declaration's curly braces), but when you define your methods, you do so like this:

int my_class::my_member_func( int )
{
   /* function body */
}

An aside: the separation between the class declaration and class definition is just one of the speed bumps you have to live with when using C++; it is there to support separate compilation, but if you've ever made the switch from C++ to Java you know that giving up the need to keep header files and implementation files in perfect synchronization gives you an immediate productivity boost.

If we want to make a variable that can point to that member function, we put an asterisk to the left of the name:

int my_class::*my_member_func_ptr( int );

The precedence rules get confused by this (during parsing, it probably looks like a collision between a definition of a member function and a conventional function returning a pointer with no type attached, or some such nonsense), so again we have to use parentheses:

int ( my_class::*my_member_func_ptr )( int );

and this gives us a variable, my_member_func_ptr, which can hold a pointer to a member function with the signature "returns int and takes one int parameter." Note that the parameter list, as in a function prototype or member function declaration, only requires the types of the parameters and not the names, although you can supply names for documentation purposes if you want.

Another aside: it would be easy to ridicule this syntax, but ridiculing the syntax of C++ is kind of like shooting fish in a barrel. I've shown that the syntax is at least somewhat consistent with the other C++ syntactical forms. Because of that, this particular syntax doesn't really bother me; if I can't remember it off the top of my head, I can mentally follow this derivation path and reason it out. This isn't necessarily true of a lot of other pieces of C++ syntax which do bother me and which I'm quite happy to rant about; see my piece on struct.

A pointer to member function does not have a standard implementation; the implementation (size, etc.) may differ between implementations; you should probably treat it as an opaque data structure and make no assumptions about what it actually looks like inside, unless you want to write very non-portable code. There's nothing in the standard that says that pointers to member functions have to be the same size, for example, and the standard specifically says they are _not_ just specially typed pointers; they are not convertible to and from void* by casting, as other pointer types are, using either the old-style or new-style casts.

This is because pointer to member function is not a usable pointer by itself; instead it contains whatever extra information is needed to represent a specific member function for a given class, probably an index or offset of some sort. You can imagine that the compiler needs a mechanism like this for its own use, so that it can turn

object.member_function(...)

or

object_pointer->member_function(...)

into C-style function calls with the addition of a hidden parameter:

looked_up_member_function( this, ... )

Remember our discussion on generic function dispatch? You might notice that when you rewrite the code to explicitly pass in the contest (the "this"), it starts to look like Dylan (or, ignoring the difference between infix and prefix notation, CLOS). You can actually think of the C++ object model as a much more limited and obfuscated form of CLOS generic function dispatch. How weird is that?

The "this" pointer allows the function body access to the specific object instance variables, and can also be passed on to any subsidiary member function calls on the same object. In Dylan or CLOS you would access the data members (in slots) of the incoming object explicitly; C++ gives you access to the data members and member functions of "this" implicitly, although you can still use this-> as a prefix if you want to make very clear what you are doing, or protect against accidentally accessing something global or local in the member function's namespace that might inadvertently shadow a member. This merging of namespaces is another rich source of potential errors (remember my comment about how C++ is like obfuscated Dylan?)

Note that our pointer to member function is not defined to refer to a specific member function in the given class. It can have assigned to it any member function that is part of the class (or a derived class), and that has the same signature (that is, matching return type and parameter types). This, as you might imagine, allows the compiler to do dynamic dispatch based on runtime type; you can do the same thing, based on any criteria you choose.

Note also that the variable you've created is not yet initialized. There's that obfuscation again! In a language where everything is done by reference, that isn't even quite possible; your reference will wind up referring to something. But pointers enable whole new classes of errors, and there is unfortunately no such thing as a "reference to member function" in C++. Be careful to make certain you initialize it before use, preferably at the point the variable is defined! Not doing so will cause you severe tire damage!

And, in fact, the compiler may not help you avoid this. I tested GCC by writing a call to an uninitialized regular function pointer:

void ( *fptr ) ( void );
fptr();

and it generated a helpful warning for this case. When I wrote a similar call using an uninitialized pointer to a member function, like so:

void ( Class_c::*mptr ) ( void );
( this->*mptr ) ();

GCC produced no warning at all, and as you might expect, the call caused an immediate crash. This is the likely outcome, but according to the C++ standard the behavior is undefined (this is very bad; it means the program is not required by the standard to catch this as an error; it is free to silently fail in some insidious way, or destroy your hard drive, or electrify your keyboard).

You can initialize them to zero, the null pointer constant (there is an explicitly allowed conversion), but the results of calling a null pointer to member function are also undefined, so this doesn't buy you anything; you are better off initializing them at the point where they are defined. Here is an example of how to do so:

void ( my_class::*mp ) ( void ) = &my_class::member_function;

Since pointers to member functions are hard to read, especially for member functions that that accept a long list of parameters, it is valuable to make the construct into a type using typedef. I recommend using the naming convention class name + the _kind_ of member func + "_pm_t"

But follow your own convention, or your team's convention, if you like. Keep in mind that the type can be used to represent any member function of the class (or a derived class) that matches the signature. The member function will probably represent a handler of some kind, or in design pattern terms a specific strategy. Describe what it handles, or what the strategies are trying to accomplish.

When you write the typedef, keep in mind that it looks just like the variable definition, except that the type name replaces the variable name and you put typedef in front. To define a type called my_class_SomethingHandler_pm_t, use the form:

typedef int ( my_class::*my_class_SomethingHandler_pm_t ) ( int );

Once you have a type, the following definition creates a variable with the new type and initializes it with a specific member function:

my_class_SomethingHandler_pm_t pm = &my_class::my_member_func;

This assignment can also take place in parameter binding. This means you can write a standalone function, member function, or static member function that accepts any pointer to member function matching the specified signature, and then pass it a specific one at run-time.

Once you have a pointer to member function, you can call that member function, but to do this you need an object (the "this" that will be in effect for the duration of the call). If you have a pointer to the object (which could be "this"), use the syntax:

( object_ptr->*mp )( params );

If you have a local or global variable holding an object or a reference to an object, use the syntax:

( object.*mp ) ( params );

Note that the parentheses around the first part are mandatory, to help the parser. If your object pointer or pointer to member function is stored in a structure or you are accessing it via pointer you will probably have to introduce more parentheses to make sure the parts of the expression are evaluated in the right order. This kind of construct can get ugly fast, so be careful.

In his C++ FAQ Lite section on pointers to member functions available here Marshall Cline suggest that when making calls using pointers to member functions, you always define a calling macro like this:

#define CALL_MEMBER_FN(object,ptrToMember) ((object).*(ptrToMember))

and then do the call like this:

result = CALL_MEMBER_FN(PO,PM)( PL );

but I wouldn't necessarily recommend that; C-style macros are still quite evil, and can make it very hard to find out what the compiler is complaining about, or even what it actually compiled that you didn't intend.