Porting a Poker Hand Evaluator from C to Factor

To help teach myself Factor, I started solving a lot of the problems at Project Euler and approached each one, not only as a way to learn a new language, but as a means of exploring unfamiliar programming/mathematical methods, structures, and algorithms. This article explains the process I went through to port a fairly complicated poker hand evaluation algorithm from C to Factor.

Problem 54

In order to solve Problem 54, I needed to come up with a way to programatically determine the winner when comparing two poker hands. I had recently read an extensive blog post covering various poker hand evaluators, so I knew that I didn’t want to bother with a naive solution when there were much better options out there. After reading through the different techniques, one stood out to me in particular; it was a relatively small amount of code, it didn’t require a ton of storage space, and it was plenty fast…

Cactus Kev’s Poker Hand Evaluator

Through the power of mathematics (combinatorics in particular), you can ascertain that out of all 2,598,960 possible poker hands (52 choose 5), there are actually only 7462 distinct hand values that you need to be concerned with. The basic idea behind Cactus Kev’s Poker Hand Evaluator is that you can take advantage of this fact by storing a card’s representation in an efficient manner, do some basic bit twiddling, some multiplication (which is computationally cheap), add in a couple lookup tables, and you can determine a hand’s equivalence class value very quickly.

The key concept here is that each of a card’s possible 13 ranks (deuce through ace) is stored as a different prime number, and by multiplying a hand’s five prime numbers together, you’ll get a unique result that can then be used to determine that hand’s overall value. If you handle the special cases of flushes, straights, and high cards, the rest can be boiled down to a simple binary search. You can read the gory details at Kevin Suffecool’s site.

The Porting Process

Bitfield Representation

Each card will be stored as a bitfield, inside of an interger that’s 4-bytes long:

+-------------------------------------+
| xxxbbbbb bbbbbbbb ssssrrrr xxpppppp |
+-------------------------------------+
  xxxAKQJT 98765432 CDHSrrrr xxpppppp
  -----------------------------------
  00001000 00000000 01001011 00100101  =  134236965  =  King of Diamonds
  00000000 00001000 00010011 00000111  =     529159  =  Five of Spades
  00000010 00000000 10001001 00011101  =   33589533  =  Jack of Clubs

For now, I’m going to ignore how we get cards into this particular format, but I’ll come back to that in a bit.

Constants

Now that we have an efficient means of representing individual cards, we need to establish some basic constants to align with the above bitfield representation and overall hand values…

Constants In C:

#define CLUB     0x8000
#define DIAMOND  0x4000
#define HEART    0x2000
#define SPADE    0x1000

#define Deuce  0
#define Trey   1
#define Four   2
#define Five   3
#define Six    4
#define Seven  5
#define Eight  6
#define Nine   7
#define Ten    8
#define Jack   9
#define Queen  10
#define King   11
#define Ace    12

#define STRAIGHT_FLUSH   1
#define FOUR_OF_A_KIND   2
#define FULL_HOUSE       3
#define FLUSH            4
#define STRAIGHT         5
#define THREE_OF_A_KIND  6
#define TWO_PAIR         7
#define ONE_PAIR         8
#define HIGH_CARD        9

static char *value_str[] = {
    "",
    "Straight Flush",
    "Four of a Kind",
    "Full House",
    "Flush",
    "Straight",
    "Three of a Kind",
    "Two Pair",
    "One Pair",
    "High Card"
};

Constants In Factor:

CONSTANT: CLUB     8
CONSTANT: DIAMOND  4
CONSTANT: HEART    2
CONSTANT: SPADE    1

CONSTANT: DEUCE  0
CONSTANT: TREY   1
CONSTANT: FOUR   2
CONSTANT: FIVE   3
CONSTANT: SIX    4
CONSTANT: SEVEN  5
CONSTANT: EIGHT  6
CONSTANT: NINE   7
CONSTANT: TEN    8
CONSTANT: JACK   9
CONSTANT: QUEEN  10
CONSTANT: KING   11
CONSTANT: ACE    12

CONSTANT: STRAIGHT_FLUSH   0
CONSTANT: FOUR_OF_A_KIND   1
CONSTANT: FULL_HOUSE       2
CONSTANT: FLUSH            3
CONSTANT: STRAIGHT         4
CONSTANT: THREE_OF_A_KIND  5
CONSTANT: TWO_PAIR         6
CONSTANT: ONE_PAIR         7
CONSTANT: HIGH_CARD        8

CONSTANT: VALUE_STR { "Straight Flush" "Four of a Kind" "Full House" "Flush"
    "Straight" "Three of a Kind" "Two Pair" "One Pair" "High Card" }

Here, the only difference I made in the Factor version was to start the hand value types at 0 instead of 1 to eliminate the empty string at index 0…it’s unnecessary.

Prime Number Representations

As mentioned above, each card rank will be represented by its own prime number, so we’ll need a way to reference that…

Prime Numbers In C:

int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 };

Prime Numbers In Factor:

CONSTANT: RANK_STR { "2" "3" "4" "5" "6" "7" "8" "9" "T" "J" "Q" "K" "A" }

: card-rank-prime ( rank -- n )
    RANK_STR index { 2 3 5 7 11 13 17 19 23 29 31 37 41 } nth ;

A minor change I made here was to establish a RANK_STR constant to make it easier to develop ways to parse and print card representations later (see the section on printing below for the C equivalent). That said, card-rank-prime in the Factor version has the same purpose as the primes array in the C version, but it performs the lookup for you.

Initializing Cards

Now that we have some basic infrastructure in place, we can tackle initializing cards in the desired format. Cactus Kev’s code glosses over this process and only demonstrates how to generate an entire deck, so I’ll just cover the Factor code here…

Initializing Cards In Factor:

: card-rank ( rank -- n )
    {
        { "2" [ DEUCE ] }
        { "3" [ TREY  ] }
        { "4" [ FOUR  ] }
        { "5" [ FIVE  ] }
        { "6" [ SIX   ] }
        { "7" [ SEVEN ] }
        { "8" [ EIGHT ] }
        { "9" [ NINE  ] }
        { "T" [ TEN   ] }
        { "J" [ JACK  ] }
        { "Q" [ QUEEN ] }
        { "K" [ KING  ] }
        { "A" [ ACE   ] }
    } case ;

: card-suit ( suit -- n )
    {
        { "C" [ CLUB    ] }
        { "D" [ DIAMOND ] }
        { "H" [ HEART   ] }
        { "S" [ SPADE   ] }
    } case ;

: card-rank-bit ( rank -- n )
    RANK_STR index 1 swap shift ;

: card-bitfield ( rank rank suit rank -- n )
    {
        { card-rank-bit 16 }
        { card-suit 12 }
        { card-rank 8 }
        { card-rank-prime 0 }
    } bitfield ;

:: (>ckf) ( rank suit -- n )
    rank rank suit rank card-bitfield ;

: >ckf ( string -- n )
    #! Cactus Kev Format
    >upper 1 cut (>ckf) ;

: parse-cards ( string -- hand )
    " " split [ >ckf ] map ;

To use this code, you’d start with a string representing a card, like "AS" for the Ace of Spades or "7H" for the Seven of Hearts, and then pass it to >ckf to get its integer representation. The parse-cards word simply does this conversion for an entire hand; given a string like "7C 5D 4H 3S 2C", it will output an array of the proper integers:

(scratchpad) "7C 5D 4H 3S 2C" parse-cards .
{ 2131213 541447 270853 135427 98306 }

Due to Factor’s concatenative nature, you tend to write a lot of small words that do one specific thing, and then tie them together. Words are expected to be defined before you reference them (unless they’ve been deferred), so when reading code from top to bottom, you’ll see big-picture words defined after the more-focused words they use. It’s also a convention to name helper words the same as the word from which they’re called, but with parentheses around the name.

One special thing to note is the use of locals in the (>ckf) helper word…if you start a word definition with :: instead of just :, Factor will bind the named inputs (from the stack declaration) to lexical variables from left to right. It’s used in this case because we need to pass these values to the card-bitfield word in a specific order, and shufflers would make this a bit more confusing.

The last thing to explain is the card-bitfield word itself…it looks up the proper bit values for the different parts of our card representation, and then constructs the final 4-byte integer from those values. See the bitfield documentation for more details on its syntax.

Shuffling Decks and Printing Hands

Initializing and shuffling a deck wasn’t strictly necessary for solving the Project Euler problem, but it was a useful abstraction and would be expected in a general poker library. Printing out a poker hand falls under this same category, but I’ve included it here as well since it was part of Cactus Kev’s original code. This is where the languages start to noticibly deviate in their implementations…

Initializing a Deck In C:

init_deck( int *deck )
{
    int i, j, n = 0, suit = 0x8000;

    for ( i = 0; i < 4; i++, suit >>= 1 )
        for ( j = 0; j < 13; j++, n++ )
            deck[n] = primes[j] | (j << 8) | suit | (1 << (16+j));
}

Initializing a Deck In Factor:

: <deck> ( -- deck )
    RANK_STR SUIT_STR 2array [ concat >ckf ] product-map ;

Shuffling a Deck In C:

double  drand48();

shuffle_deck( int *deck )
{
    int i, n, temp[52];

    for ( i = 0; i < 52; i++ )
        temp[i] = deck[i];

    for ( i = 0; i < 52; i++ )
    {
        do {
            n = (int)(51.9999999 * drand48());
        } while ( temp[n] == 0 );
        deck[i] = temp[n];
        temp[n] = 0;
    }
}

Shuffling a Deck In Factor:

ALIAS: shuffle randomize

Printing a Hand In C:

print_hand( int *hand, int n )
{
    int i, r;
    char suit;
    static char *rank = "23456789TJQKA";

    for ( i = 0; i < n; i++ )
    {
        r = (*hand >> 8) & 0xF;
        if ( *hand & 0x8000 )
            suit = 'c';
        else if ( *hand & 0x4000 )
            suit = 'd';
        else if ( *hand & 0x2000 )
            suit = 'h';
        else
            suit = 's';

        printf( "%c%c ", rank[r], suit );
        hand++;
    }
}

Printing a Hand In Factor:

: >card-rank ( card -- string )
    -8 shift HEX: F bitand RANK_STR nth ;

: >card-suit ( card -- string )
    {
        { [ dup 15 bit? ] [ drop "C" ] }
        { [ dup 14 bit? ] [ drop "D" ] }
        { [ dup 13 bit? ] [ drop "H" ] }
        [ drop "S" ]
    } cond ;

: card>string ( card -- string )
    [ >card-rank ] [ >card-suit ] bi append ;

: print-hand ( hand -- )
    [ card>string ] map " " join print flush;

I’m cheating a bit here with the shuffle word, as Factor already implements randomize using the Fisher-Yates algorithm; so rather than re-inventing the wheel, I just aliased the wheel. With Factor, you’ll also notice that count-controlled loops are much less common in comparison to using sequence operators directly on the elements of a data structure.

Lookup Tables

We can almost get to the actual evaluation of hands to determine their relative value, but before that, we’ll need the proper lookup tables. These are all straight-forward arrays, and we have four to consider:

  1. a table for all flushes (including straight flushes)
  2. a table for all non-flush hands consisting of five unique ranks (i.e. either straights or high card hands)
  3. a table of the product of prime values associated with a hand
  4. a table covering the final hand values of all hands not covered by the flushes/unique5 tables

A zero means that specific combination is not possible for that type of hand…

Lookup Tables In C:

short flushes[] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1599, 0, 0, 0, 0, 0, 0, 0, 1598, 0, 0, 0, 1597, 0, 1596,
...
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1
};

short unique5[] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1608, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 7462, 0, 0, 0, 0, 0, 0, 0, 7461, 0, 0,  0,  7460,  0,
...
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0,  0,  0,  0,  0, 0, 0, 0, 0, 0, 0, 1600
};

int products[] = {
48, 72, 80, 108, 112, 120, 162, 168, 176,  180,  200,  208,  252,
264,  270, 272, 280, 300, 304, 312, 368, 378, 392, 396, 405, 408,
420, 440, 450, 456, 464, 468, 496, 500, 520, 552, 567, 588,  592,
...
66737381,   71339959,  73952233,  76840601,  79052387,  81947069,
85147693, 87598591, 94352849, 104553157
};

short  values[] = {
166, 322, 165, 310, 164, 2467, 154, 2466, 163,  3325,  321,  162,
3324,  2464,  2401,  161,  2465, 3314, 160, 2461, 159, 2400, 320,
3323, 153, 2457, 6185, 2463, 3303, 2452,  158,  3322,  157,  298,
...
1676, 14, 168, 2469, 2468, 1611, 23, 1610, 13, 179, 12, 167, 11
};

Lookup Tables In Factor:

CONSTANT: flushes-table
{ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1599 0 0 0 0 0 0 0 1598 0 0 0 1597 0 1596 8 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1595 0 0 0 0 0 0 0 1594 0 0 0 1593 0 1592 1591 0 0 0 0 0 0 0 0 1590
...
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 }

CONSTANT: unique5-table
{ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1608 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 7462 0 0 0 0 0 0 0 7461 0 0 0 7460 0 7459 1607 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 7458 0 0 0 0 0 0 0 7457 0 0 0 7456 0 7455 7454 0 0 0 0 0 0
...
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1600 }

CONSTANT: products-table
{ 48 72 80 108 112 120 162 168 176 180 200 208 252 264 270 272 280 300 304 312
368 378 392 396 405 408 420 440 450 456 464 468 496 500 520 552 567 588 592 594
612 616 630 656 660 675 680 684 696 700 702 728 744 750 760 780 828 882 888 891
...
64379963 64992503 66233081 66737381 71339959 73952233 76840601 79052387
81947069 85147693 87598591 94352849 104553157 }

CONSTANT: values-table
{ 166 322 165 310 164 2467 154 2466 163 3325 321 162 3324 2464 2401 161 2465
3314 160 2461 159 2400 320 3323 153 2457 6185 2463 3303 2452 158 3322 157 298
2460 2446 152 3292 156 2398 3321 2462 5965 155 6184 309 2456 3320 2439 3313
...
1622 191 3546 2490 2470 15 2600 25 3326 169 24 1612 2479 1677 1621 1676 14 168
2469 2468 1611 23 1610 13 179 12 167 11 }

Hand Evaluation

Finally, we can get to the actual evaluation of hands…

Hand Evaluation In C:

int findit( int key )
{
    int low = 0, high = 4887, mid;

    while ( low <= high )
    {
        mid = (high+low) >> 1;      // divide by two
        if ( key < products[mid] )
            high = mid - 1;
        else if ( key > products[mid] )
            low = mid + 1;
        else
            return( mid );
    }
    fprintf( stderr, "ERROR:  no match found; key = %d\n", key );
    return( -1 );
}

short
eval_5cards( int c1, int c2, int c3, int c4, int c5 )
{
    int q;
    short s;

    q = (c1|c2|c3|c4|c5) >> 16;

    /* check for Flushes and StraightFlushes
    */
    if ( c1 & c2 & c3 & c4 & c5 & 0xF000 )
    return( flushes[q] );

    /* check for Straights and HighCard hands
    */
    s = unique5[q];
    if ( s )  return ( s );

    /* let's do it the hard way
    */
    q = (c1&0xFF) * (c2&0xFF) * (c3&0xFF) * (c4&0xFF) * (c5&0xFF);
    q = findit( q );

    return( values[q] );
}

Hand Evaluation In Factor:

: flush? ( hand -- ? )
    HEX: F000 [ bitand ] reduce 0 = not ;

: rank-bits ( hand -- q )
    0 [ bitor ] reduce -16 shift ;

: lookup ( hand table -- value )
    [ rank-bits ] dip nth ;

: prime-bits ( hand -- q )
    [ HEX: FF bitand ] map-product ;

: hand-value ( hand -- value )
    dup flush? [ flushes-table lookup ] [
        dup unique5-table lookup dup 0 > [ nip ] [
            drop prime-bits products-table sorted-index
            values-table nth
        ] if
    ] if ;

Each language’s implementation checks for flushes first, then for hands with five unique ranks, and if all else fails, multiplies the primes together, searches for that product in a lookup table, and then uses that index to determine the hand’s final value. The findit function in C is the binary search, and once again I used Factor’s built-in libraries to do the same thing with the sorted-index word.

Hand Ranking

We’re basically done at this point…the hand with the lowest value (from 1 to 7462) wins. If the values are the same, the hands are tied. A simple comparison function can tell you which hand is best.

One last function that’s handy though, is the ability to output what that value actually means…

Hand Ranking in C:

int
hand_rank( short val )
{
    if (val > 6185) return(HIGH_CARD);        // 1277 high card
    if (val > 3325) return(ONE_PAIR);         // 2860 one pair
    if (val > 2467) return(TWO_PAIR);         //  858 two pair
    if (val > 1609) return(THREE_OF_A_KIND);  //  858 three-kind
    if (val > 1599) return(STRAIGHT);         //   10 straights
    if (val > 322)  return(FLUSH);            // 1277 flushes
    if (val > 166)  return(FULL_HOUSE);       //  156 full house
    if (val > 10)   return(FOUR_OF_A_KIND);   //  156 four-kind
    return(STRAIGHT_FLUSH);                   //   10 straight-flushes
}

Hand Ranking in Factor:

: value>rank ( value -- rank )
    {
        { [ dup 6185 > ] [ drop HIGH_CARD ] }        ! 1277 high card
        { [ dup 3325 > ] [ drop ONE_PAIR ] }         ! 2860 one pair
        { [ dup 2467 > ] [ drop TWO_PAIR ] }         !  858 two pair
        { [ dup 1609 > ] [ drop THREE_OF_A_KIND ] }  !  858 three-kind
        { [ dup 1599 > ] [ drop STRAIGHT ] }         !   10 straights
        { [ dup 322 > ]  [ drop FLUSH ] }            ! 1277 flushes
        { [ dup 166 > ]  [ drop FULL_HOUSE ] }       !  156 full house
        { [ dup 10 > ]   [ drop FOUR_OF_A_KIND ] }   !  156 four-kind
        [ drop STRAIGHT_FLUSH ]                      !   10 straight-flushes
    } cond ;

: string>value ( string -- value )
    parse-cards hand-value ;

: hand-rank ( string -- string )
    string>value value>rank VALUE_STR nth ;

Cactus Kev’s code didn’t include the code for explicit output of a string, but he did include the value_str array which could be used for this purpose.

Putting it All Together

To use the poker evaluator directly in Factor’s interactive listener environment, you can enter something like these examples:

(scratchpad) "7H 7S 7D AS AC" hand-rank .
"Full House"

(scratchpad) "7C 5D 4H 3S 2C" "KD QS JC TH 9S" [ string>value ] bi@ > .
t

Solving Problem 54

Getting back to our original goal of solving Project Euler’s Problem 54, we can now quite easily determine how many times Player 1 wins out of 1000 random hands dealt to two players…

: source-054 ( -- seq )
    "resource:extra/project-euler/054/poker.txt" ascii file-lines
    [ [ 14 head-slice ] [ 14 tail-slice* ] bi 2array ] map ;

: euler054 ( -- answer )
    source-054 [ [ string>value ] map first2 before? ] count ;

The source-054 word simply converts the provided text file into the format our evaluator expects and the hand comparisons are subsequently handled by the euler054 word and counted up! Let’s just say that Player 2 is much better at poker :-)

Vocabulary Improvements

Since porting the initial version of the poker vocabulary, many improvements have been made to generalize the code for use beyond just solving Project Euler problems. I ended up dropping the binary search in favor of using the Senzee Perfect Hash Optimization, and other Factor contributors have added code specifically for Texas Hold’em and Omaha evaluation. I didn’t want to cover all of that here, as the focus of this article is the direct comparison between C and Factor, but you can view the current poker vocabulary to see all of these enhancements.

As always, feel free to drop me a line if you’d like to discuss things further.

Magnetic-Based versus Flash-Based Storage

This article is the answer I wrote to an exam question for a basic cyber forensics course I took back in Feb 2009. I recently ran across this exam in my files and thought others might be interested in a high-level overview of the differences between magnetic-based and flash-based storage technologies…

The Question

“Briefly discuss the differences between magnetic-based storage and flash-based storage. What effect do these differences have on digital evidence investigations?”

My Answer

Between the two types of disk storage technology of magnetic-based and flash-based hard drives (HDDs and SSDs respectively), magnetic-based drives are more common, with flash-based drives quickly gaining speed in development and adoption rates.

Magnetic-based drives use a series of stacked metal or glass disks called “platters”, which store microscopic magnetic information on concentric rings called “tracks”, which are further split into smaller “sectors” of 571 bytes each. A sector only holds 512 bytes of actual data and uses the remaining bytes for syncing purposes, a header with a location ID, and error detection via CRC checksums. A magnetic read head hovers over the metal platters as they spin, and depending on the electrical impulses that motion creates, you get either a one or zero represented as binary data. A “cylinder” is the combined data for a single track on all of the platters in a drive (both sides of each platter). Once the data is read, on-board hardware decodes that information and transmits it to the computer via a standardized interface.

Flash-based drives are quite different. There are no physically moving parts, and they store data electronically instead of magnetically. Using a pair of transistor gates (a float gate and a control gate), flash-based storage sends electrical impulses to logically segmented areas in memory to store the appropriate ones and zeros in binary format (just like magnetic drives). Because they use only electricity and don’t have to wait for actuator arms to physically move heads into position for reads and writes, flash-based storage is typically much faster at I/O operations. Like magnetic drives, flash-based drives also have a built-in hardware controller to manage its operation and to convert the data into a standardized format to be read by the computer.

The effect each one of these has on a digital investigation is wide-spread. First of all, they both retain data for different amounts of time when left sitting. Magnetic data is not very reliable after a year or so, while flash-based data will usually last quite a bit longer. Flash-based memory also has a limited number of erase cycles, after which, whatever data is stored on that segment will not change. This can actually help in an investigation if you can trick the hardware controller into thinking it can no longer use the memory, you could essentially turn it into a read-only device and preserve evidence. Likewise, magnetic disks often have a residual magnetic signature of previous data, even if it has been overwritten. Sometimes these properties can be exploited by an expert lab with the proper equipment to recover data that was intentionally destroyed.

Both storage mediums will usually not overwrite data when it is deleted, but will simply update an allocation table to specify that a cluster or segment is free for writing again.

Keeping in mind how each of these technologies transforms physical properties into a common, logical storage interface can help you to make better decisions on how to preserve data, how to find evidence, and what to expect when doing an investigation. If you don’t pay attention to how these technologies differ, you have the potential to either miss important information, or in the worst case, destroy the information you do have.

Beginning Factor – Shufflers & Combinators

In the previous installment of Beginning Factor, we discussed some of the attributes of stack-based languages and the syntax for defining words in Factor. This time around, I’d like to introduce stack shufflers, quotations & combinators, and touch on some more basic data types and their properties.

Up until now, we’ve essentially been using Factor as an overqualified RPN calculator. I just wanted to make sure that you don’t underestimate Factor because of these particular examples; Factor is an extremely capable and modern language that can be used for everything from web applications, to game development, to complex text parsing, and so on. I’m purposefully using over-simplified examples as a means to demonstrate specific points about the language. Stick with me, and I assure you the examples will gradually get more expressive.

Stack Shufflers

Because of Factor’s stack-based nature, you sometimes need the ability to rearrange or copy items in the stack to ensure that they are in the correct position for future use. The way to go about this is a group of words called “stack shufflers”.

Much like the name implies, stack shufflers are merely words that change the order (or number) of the items on the top of the stack. It is said that shuffle words “control the flow of data between words that perform actions.” In fact, you already know one stack shuffler… drop

There are three basic varieties of stack shufflers. Here they are along with the most commonly used word for each type:

  1. Removing Shufflers

    drop ( x -- )
    removes the top item from the stack and discards it

  2. Duplicating Shufflers

    dup ( x -- x x )
    duplicates the top item on the stack

  3. Permuting Shufflers

    swap ( x y -- y x )
    exchanges the positions of the first and second items on the top of the stack

Swapping Two Items on the Top of a Stack

…and here are a couple of word definitions that use these shufflers appropriately:

: sq ( x -- y )
    dup * ;

: neg ( x -- -x )
    0 swap - ;

(scratchpad) 5 sq .
25
(scratchpad) 1 neg .
-1

Caveats

There are many more shuffle words that support intricate rearrangements and the duplication/removal of multiple items from differing locations within the stack. The problem is, code that is full of stack shufflers can easily become confusing. In general, you should try to minimize the use of stack shufflers to keep things understandable.

Of course there are exceptions to that rule, times when shufflers make the most sense, but the preferred alternative to complicated stack shufflers is the use of a “combinator” that fits your use case. That said, combinators will take a bit of explaining…

Quotations

Before we can get to the idea of combinators, we first have to discuss quotations:

(scratchpad) 5 [ "hello" print ] times
hello
hello
hello
hello
hello

In this example, [ "hello" print ] is a quotation.

In layman’s terms, a quotation is a way to encapsulate a snippet of code so it doesn’t get called right away, but can be passed around on the stack and called later. The computer science term for this is an “anonymous function”. It’s referred to as “anonymous” because it is fundamentally a word that has no name.

If we didn’t have quotations, that same example would get ugly real fast:

(scratchpad) "hello" dup dup dup dup print print print print print
hello
hello
hello
hello
hello

Imagine if you wanted to print “hello” 1000 times!

To create a quotation, you just surround your code snippet with square brackets, and it will be pushed onto the stack: [ ... ]. In order to do anything useful with that quotation once it’s on the stack, what you need is a combinator.

What is a Combinator?

A combinator is just a fancy name for a word that takes a quotation as one of its inputs. In the example above, times is a combinator which takes an integer (n) and a quotation from the stack, and it calls that quotation n times.

Factor uses quotations & combinators extensively for conditionals, sequence traversal, namespaces, closures, and more…but that’s jumping the gun a bit. Before we dive into all of that, I’d like to get back to the idea of minimizing the use of stack shufflers by replacing them with appropriate combinators instead.

Combinators That Express Intent

While our code examples thus far have been easy to follow, when you start tackling more realistic problems, stack shufflers will begin to obfuscate your code. If we can represent our intentions consistently with a combinator instead, then code becomes cleaner and you can consequently focus more on your problem domain and less on mentally organizing your stack.

To illustrate this point, I’d like to introduce a couple of simple combinators:

dip ( x quot -- x )
calls a quotation while temporarily hiding the top item on the stack
keep ( x quot -- x )
calls a quotation with an item on the stack, restoring that item after the quotation returns

While both of these combinators have the same stack effect declaration, their usage is a bit different:

(scratchpad) 1 2 4 [ + ] dip

--- Data stack:
3
4

(scratchpad) clear
(scratchpad) 1 2 4 [ + ] keep

--- Data stack:
1
6
4

These two combinators alone can greatly reduce the number of stack shufflers your code will need. If you’re curious about how these combinators work, they both secretly take advantage of an auxiliary stack (called the “retain stack”) to temporarily store items while the supplied quotation is being executed. There are a few other preserving combinators that are worth exploring as well.

Cleave, Spread, and Apply

The cleave, spread, and apply combinators are your best weapons when trying to reduce the use of stack shufflers while simultaneously expressing intent. The key point being that they should express intent…if you find yourself writing code where these combinators don’t fit logically, then try another option.

  1. Cleave Combinators

    These are used when you want to apply multiple quotations to the same set of items on the top of the stack.

    Let’s say that you want to find the average of a bunch of numbers in an array. The steps are straightforward, you take the sum of all the numbers and divide that sum by how many numbers you have (the length of the array):

    (scratchpad) { 1 2 3 } dup sum swap length / .
2

    We can eliminate the need for those stack shufflers and better express our intent by using a cleave combinator to achieve the same thing:

    bi ( x p q -- )
    applies quotation p to x, then applies quotation q to x

    Cleave Combinator Demonstration

    (scratchpad) { 1 2 3 } [ sum ] [ length ] bi / .
2

    The different cleave combinators change either the number of quotations applied to your items (bi vs. tri), or the number of items used as input for your quotations (bi vs. 2bi).

  2. Spread Combinators

    These are used when you want to apply a different quotation to different items on the top of the stack. The spread combinators are closely related to dip, but provide a bit more flexibility while also expressing intent.

    Let’s say that you have two coordinate positions in the form of { x y }, and you’d like to extract the x-coordinate from the first position, and the y-coordinate from the second position to form a new position with those values:

    (scratchpad) { 1 2 } { 3 4 } swap first swap second 2array .
{ 1 4 }

    We can eliminate the need for those stack shufflers and better express our intent by using a spread combinator to achieve the same thing:

    bi* ( x y p q -- )
    applies quotation p to x, then applies quotation q to y

    Spread Combinator Demonstration

    (scratchpad) { 1 2 } { 3 4 } [ first ] [ second ] bi* 2array .
{ 1 4 }

    When you want to do the same thing with more than two quotations/items, then using spread combinators eliminates the need for nested dips or shufflers and the added clarity becomes much more evident.

    The different spread combinators change the number of quotations applied to the corresponding number of items on the stack (bi* vs. tri*).

  3. Apply Combinators

    These are used when you want to apply a single quotation to multiple items on the top of the stack.

    Let’s say that you have two strings, each containing a name, and you want to see if those names are the same. In order to ignore case when doing the comparison, you decide to convert both strings to upper case before checking for equality:

    (scratchpad) "john" "John" swap >upper swap >upper = .
t

    We can eliminate the need for those stack shufflers and better express our intent by using an apply combinator to achieve the same thing:

    bi@ ( x y quot -- )
    applies the quotation to x, then to y

    Apply Combinator Demonstration

    (scratchpad) "john" "John" [ >upper ] bi@ = .
t

    The different apply combinators change the number of items on the stack your quotation is applied to (bi@ vs. tri@).

The cleave, spread, and apply combinators are all closely related; if you’re having trouble keeping them apart, try to memorize the naming convention:

Once you learn these combinators, you should be able to express almost any pattern of complicated stack shufflers. Note that there are also generic forms for all of these combinators that can take additional inputs from the stack. If you find that you resort to using the generic forms more often then not, that’s usually a good indication that you should rethink your approach or put your data into a more appropriate structure.

Data Type Details

Before I turn you loose, I wanted to offer a few extra details about some of Factor’s basic data types…

Sequences

In the cleave and spread examples above, I was sneaky and used sequences without explaining them formally. A sequence is a finite, ordered, collection of elements. Any data type that implements the sequence mixin class (meaning a data type that knows its length and will let you set/get an element at a specific index) gains the ability to use the powerful built-in sequence operators. Read through that documentation to get an idea on how to manipulate sequences and their elements.

Factor has many sequence types that you may already be familiar with, such as arrays (fixed-size mutable sequences) and vectors (resizable mutable sequences), but there are also other data types that you might not expect to be sequences, such as strings. In Factor, a string is merely an array of Unicode 5.0 code points.

Using the sequence operators and combinators together, you can create all sorts of powerful abstractions that I’ll talk more about next time. Here are a couple of examples to whet your appetite:

(scratchpad) { 1 2 3 4 5 } [ even? ] filter .
{ 2 4 }
(scratchpad) { 1 2 3 } [ . ] each
1
2
3
(scratchpad) "Hello" [ alpha? ] all? .
t
(scratchpad) "Hello!!!" [ alpha? ] all? .
f

Keep in mind that in Factor, sequences are zero-based.

Numbers

So far, we have only used integers, but Factor also supports rational numbers (fractions), floats (decimal approximations of a number), and complex numbers (imaginary numbers).

(scratchpad) 100 330 / .
10/33
(scratchpad) 5/4 1/2 + .
1+3/4
(scratchpad) 5/4 0.5 + .
1.75
(scratchpad) 2 5 rect> .
C{ 2 5 }

Iota

One last thing that is going to come in handy, is a word for creating sequences from integers:

iota ( n -- iota )
creates a sequence of length n, whose elements are its non-negative predecessors (i.e. 0 to n-1 inclusive)

This word can be very helpful when performing counted loops or other control flow statements. For example, the following two lines are equivalent:

{ 0 1 2 3 4 5 6 7 8 9 } [ . ] each

10 iota [ . ] each

Next Time

Next time we’ll stick with a theme of “flow” and discuss control flow for your words and after that, the typical work flow when developing code with Factor. Hope you enjoyed this installment!