Motivation

Almost a year ago I started seriously exploring functional programming, with a desire to implement business rules engines. My initial thoughts appear in a few articles from January, 2012.

At that time I became aware of the Scala programming language, but already had experience using Prolog. Specifically, I had a working implementation of a two-card poker game known as Hurricane Poker. This program is described in my article Playing Poker with Prolog and Java.

My work on a demonstration rules engine that operates in a Java programming environment is described on the next article Prolog and Java Get Along by Following the Rules.

The interoperation between the Prolog logic portions of those programs and the hosting Java application involves a distinct context switch. The compiled Java program loads Prolog logic and data predicates as text, and then hands them to the tuProlog engine for interpretation and solution of a goal. Upon completion of the goal, the Prolog engine can return a compound list structure to the Java application containing the problem solution(s).

This technique works well once the Prolog logic predicates have been properly written and debugged. Detecting flaws in the logic predicates can be non-trival, however; there is no breakpoint debugger available during the Prolog engine execution. Debugging requires use of trace printing statements to analyze the actual logic flow and intermediate data values.

Scala provides a compiled programming environment that executes in a Java Virtual Machine (JVM). Scala and Java source modules can be combined to produce a complete application. The flow of execution from Scala to Java and Java to Scala is truly seamless. The interactive debugging environment allows breakpoints in to be set at both Scala and Java source lines.

I decided to see if my Prolog logic rules could be transcribed into Scala functions.

Logic Programming vs. Functional Programming

The Programming paradigm Wikipedia article makes this comparison:

  • Functional programming is a subset of declarative programming. Programs written using this paradigm use functions, blocks of code intended to behave like mathematical functions. Functional languages discourage changes in the value of variables through assignment, making a great deal of use of recursion instead.
  • The logic programming paradigm views computation as automated reasoning over a corpus of knowledge. Facts about the problem domain are expressed as logic formulae, and programs are executed by applying inference rules over them until an answer to the problem is found, or the collection of formulae is proved inconsistent.

I am still a beginner in Scala. I have learned enough basic features of Scala to be able to make these comparisons:

  • Prolog is a logic programming language, as its name implies. (It was invented in France, but can be described in English as Programming in Logic.) Logical predicates are applied to a set of data tuples that reside in an in-memory fact database, analogous to a relational database. Logic predicates can execute assert and retract operations to save and update state data within this database.
  • Scala is a hybrid functional and object-oriented language. It allows pure functional programming, but also allows mixing in traditional imperative and object-oriented operations. Immutable values are preferred; purely functional constructs require them. Traditional variables are also available; the values contained in them can vary during the execution of the program.
  • Both languages provide similar support for list processing. Both languages promote recursion over loop iteration. (Both also have some support for non-recursive looping.)
  • Both languages support pattern matching of tuple records against component values to allow conditional flow of control. Both allow designation of wild-card match patterns.

Prolog Backtracking

Prolog provides a unique execution feature known as backtracking. Prolog applies logical predicates to essentially confirm or deny the statement of a goal. Besides solving the goal as true or false, a Prolog program can also return data values that satisfy the goal as “proof”. In practice, these data values are often more meaningful than the truth or falsity of the goal.

Roman Barták provides a nice definition in Guide to Prolog Programming: How does it work?

  • backtracking

    Backtracking is a powerful feature of Prolog that simplifies development of many programs. It enables the program to use other alternative if the previous alternative fails. Thus, programming of generate and test algorithms is natural in Prolog. Also, it is usually possible to find one solution as well as all solutions using the same program.

My main concern in migrating an application from using Prolog to using Scala has been how to work without this backtracking feature. As I discovered in my current exercise, some of the purposes of backtracking can be approximated in Scala using guard clauses on match case patterns.

Teaching Scala to Play Poker

My usual practice when learning a new programming language is to develop a game. I prefer turn based board games or gambling games over action games. The actual game chosen is secondary; however, games that are enjoyable provide motivation during manual integration testing cycles.

Adapting an existing game program from one language or environment to another provides some useful grounds for comparison. I decided to use my Hurricane Poker program as my first Scala training exercise. This program pits you, the human, against seven computer opponents in a simplified poker tournament. Play is similar to a casino video poker machine in that a good portion of luck is involved, but a few simple decision points exist so you can try to focus your luck.

The end result of the exercise is available as open source via GitHub:

The GitHub repository includes Eclipse .project and .classfile files. A complete Scala integrated development environment (IDE), including Eclipse, is available here: Typesafe Scala IDE

Hurricane Poker

Hurricane is two-card draw poker, deuces wild, played as high/low. Aces and deuces play both high and low.

No straights, no flushes are used; only pairs and high-card hands occur.

Checking is allowed; the maximum bet or raise is $3. 1 bet and 2 raises are allowed per betting round.

After dealing two cards to each player, the player to the dealer’s left starts the first betting round. This is the “leading edge” of the storm.

After the first round of betting, players may optionally discard a card and draw a replacement. This is the “eye of the storm”.

The player to the dealer’s left then starts the final betting round. This is the “trailing edge” of the storm.

After the final round of betting, there is a showdown among the survivors, and damage is assessed!

The High hand and the Low hand split the pot. (Odd chip goes to the High hand.) If hands are tied, those players divide that half of the pot evenly.

Remember that 2’s are wild, and can be used as different cards in the High and the Low hands. However, two 2’s are always a pair.

An Ace is the top card in High hands, and the low card in Low hands. An “Acey-Deucy” (A2) always wins both High hand (as a pair of Aces) and Low hand (as an Ace and a Deuce).

For the high hand A2 ties with 22 as a pair of Aces; for the low hand A2 beats 22 since 22 is still a low pair, and A2 chooses a natural 2 for the wild value.

For the low hand 23 ties with A3 since 23 chooses Ace for the wild value.

Before and After: Comparison of Prolog and Scala Logic

Mutable State

Prolog contains an in-memory database where tuples can be stored and later retrieved via partial pattern matching. For Scala I decided to use var references to Map structures. (These are equivalent to HashMap in Java or Dictionary in C#.)

These Map structures only allow retrieval by the single key value, but this met my needs for this exercise. (This is somewhat analogous to retrieval restrictions for several No-SQL document databases or column-stores when compared to SQL relational databases.)

Here is the Scala function used to initialize the Map of player hand values, indexed by the integer Player #. Each Player’s hand is stored as a 2-tuple (double) of single-character strings, such as (“A”,”2″).

  def new_player_hand_map: collection.mutable.Map[Int, Tuple2[String, String]] = {
    val handMap = (1 to gPlayerCount) map(p => (p, gHandEmpty)) toMap
    var mutableMap = collection.mutable.Map(handMap.toSeq: _*)
    
    return mutableMap
  }

I use mutable maps to allow changing each player’s hand throughout the game, etc.

I also declare the reference variable as var rather than val for two reasons:

  1. Some Maps are re-initialized between hands in the game by calling the initialization function to generate a new “empty” Map.
  2. Even for Maps where only the contents change, declaring var rather than val openly declares that are using the hybrid features of Scala and violating pure functional programming techniques.

Initial Syntax Conversion

Here is the main predicate body in Prolog:

  text_title(" Hurricane Poker "),
  write(" Hurricane is two-card draw poker,"),
  nl, write(" played as high/low, with deuces wild."),
  nl, write(" Aces and deuces play both high and low;"),
  nl, write(" two deuces always pair."),
  nl, nl, write(" No straights, no flushes."),
  nl, write(" Checking allowed."),
  nl, write(" Maximum bet/raise is $3."),
  nl, write(" 1 bet and 2 raises per round."),
  nl,
  shuffle_deck(new),
  shuffle_deck(old),
  nl, write(" Shuffled new deck "), nl, !,
  clear_player_amt(0, pot),
  clear_player_amt(0, hand),
  set_player(init),
  show_players(clear),
  repeat,
    main_menu(CHOICE),
    /* until */  game_over(CHOICE), !,
  text_close.

Here are the matching Scala statements. Note that the comma sub-predicate separators become semicolon statement separators. (The final semicolon on a statement line in Scala is allowed but is not required.)

  text_title(" Hurricane Poker w/ Scala ");
  write(" Hurricane is two-card draw poker;");
  nl; write(" played as high/low; with deuces wild.");
  nl; write(" Aces and deuces play both high and low;");
  nl; write(" two deuces always pair.");
  nl; nl; write(" No straights; no flushes.");
  nl; write(" Checking allowed.");
  nl; write(" Maximum bet/raise is $3.");
  nl; write(" 1 bet and 2 raises per round.");
  nl;
  shuffle_deck_new;
  shuffle_deck_old;
  nl; write(" Shuffled new deck. "); nl;
  clear_player_amt_pot;
  clear_player_amt_hand;
  initialize_players;
  show_players_clear;
  main_loop;
  text_close;    

For each built-in Prolog predicate, such as nl (new-line to the console), I wrote a Scala function that performs the same side-effects.

For each user-defined predicate, such as shuffle_deck, I wrote one or more Scala functions. More than one function was sometimes needed to replace the pattern matching selection of separate Prolog predicate bodies. Thus shuffle_deck(new) became shuffle_deck_new. I chose to keep the underscores in my converted Scala function names to simplify copy/paste/edit source code conversion.

Backtracking Part 1: Repeat/Fail Loop

Prolog has one non-recursive looping pattern based on back-tracking:

  repeat,
    main_menu(CHOICE),
    /* until */  game_over(CHOICE), !,
  text_close.

The game_over predicate only returns true if the passed menu choice represents the end-of-game (or a player has gone broke). Most of the time it returns false to indicate failure. In that case, backtracking engages and the Prolog engine starts walking back up the sequence of predicates to find a multi-valued one that can supply an alternate solution candidate. The main_menu predicate is a side-effect prompting predicate, but it acts like a single-valued predicate. Thus, the engine backtracks to the repeat predicate. This is a special multi-valued construct that returns a continuous stream of success results. It acts as a “reflector” to cause the Prolog engine to resume forward iteration of the following predicates.

(The exclamation mark (!) is called the “cut”; it prunes any backtracking options at that point in the predicate sequence. Any attempt to backtrack into the cut causes the backtracking engine cease any more backtracking for the current predicate.)

For Scala we use a self-recursive main_loop function to perform our looping. The self-recursive call is the last statement in the function, so tail-recursion optimization activates to avoid a constantly growing call-stack. (Prolog recursion also includes this optimization.)

  def main_loop: Unit = {
    val brokePlayerCount = gPlayerAmountStake count { case (p, v) => v <= 0 }
    brokePlayerCount match {
      case 0 => {
        val choice = main_menu
        if (game_over(choice)) {
          return
        }
      }
      case 1 => {
        ask_ok_1(" A player is busted. ")
        end_of_game
        return
      }
      case n => {
        ask_ok_1(" " + n.toString() + " players are busted. ")
        end_of_game
        return
      }
    }
    
    main_loop
  }

  def game_over(choice: Int): Boolean = {
    val gameIsOver = choice match {
      case 4 => true
      case _ => false
    }
    
    if (gameIsOver) {
      end_of_game
    }
    
    return gameIsOver
  }

Here is a portion of the Prolog game_over predicate logic that corresponds to the preceding Scala decision match patterns:

  game_over(4) :- !,
    game_over(-1).
  game_over(CHOICE) :-
    CHOICE > 0,
    player_amt(_, stake, A),
    A =< 0, !,
    ask_ok("Game Over."),
    game_over(-1).
  game_over(-1) :-
    text_title(" Game Over. "),
  
    . . .

Backtracking Part 2: Pattern Matching with Alternate Paths

Here is a simple recursive loop in Prolog that works its way around the players at the poker table to obtain and process their betting decisions for a round. The second parameter (P) is the current player number. The third parameter (N) is the number of player positions still eligible to bet (or call a prior bet). Upon reaching zero, the recursive loop terminates, after displaying the current chip counts and pot size.

  player_round(bet, _, 0, _, _, _) :- !,  % Terminate recursion
    show_players(pot),
    show_players(human).
  player_round(bet, P, N, R, T, _) :-
    N > 0,
    player_hand(P, _, _), !,  % Player still in 
    player_mode(P, M),
    get_action(bet, M, P, N, R, T, ACT, B),
    player_round(ACT, P, N, R, T, B).
  player_round(bet, P, N, R, T, _) :-  % Player folded 
    N > 0, !,
    next(P, NP),
    N1 is N - 1,
    player_round(bet, NP, N1, R, T, 0).

In the second alternate of the player_round(bet predicate, if the player has folded, the player_mode(P, M) tuple fetch fails, triggering backtracking. The Prolog engine backtracks up and out of that predicate alternate, and proceeds to evaluate the next predicate alternate.

Scala does not have this ability to move backward thru its statements. To achieve the same provisional match followed by a failed successive match test, we need to use a guard condition on our match case expression:

  val gCardEmpty = " "
  val gCardFolded = "x"
  val gHandEmpty = (gCardEmpty, gCardEmpty)
  val gHandFolded = (gCardFolded, gCardEmpty)

  def player_round_bet(player: Int, remainingPlayers: Int, remainingBets: Int, totalBet: Int): Unit = {
    remainingPlayers match {
      case 0 => {
        show_players_pot
        show_players_human
        return // Terminate recursion.
      }
      case _ => {
        val playerHand = gPlayerHand(player)
        playerHand match {
          case h if h == gHandFolded => {
            // Player folded.
            val nextPlayer = next_player(player)
            val stillRemainingPlayers = remainingPlayers - 1
            player_round_bet(nextPlayer, stillRemainingPlayers, remainingBets, totalBet)
          }
          case _ => {
            val mode = gPlayerMode(player)
            val (action, betAmount) = get_action_bet(mode, player, remainingPlayers, remainingBets, totalBet)
            process_player_bet_action(player, action, betAmount, remainingPlayers, remainingBets, totalBet)
          }
        }
      }
    }
  }

The relevant guard condition occurs in the playerHand match { case h if h == gHandFolded pattern match condition. This occurs inside the remainingPlayers match { case _ wild card condition.

The player’s hand is retrieved as a 2-tuple via the val playerHand = gPlayerHand(player) Map fetch statement. The full case match only proceeds when the if condition returns true. Otherwise the pattern matching proceeds to evaluate the next case condition.

The preceding example could also be performed using simple if … else imperative logic, but it provides a focused introduction to Scala’s pattern matching guard conditions.

Here is a more advanced example from the actual rules engine portion of the application. Each player is randomly assigned one of several artificial intelligence modes that determine its playing pattern.

Here are the decision rules for the human, checker, and highrise modes. The Prolog logic looks like this:

  get_action(bet, human, P, _, R, T, ACT, B) :-
    show_players(pot),
    show_players(human),
    player_amt(P, bet, PB),
    CB is T - PB,  % Call bet amount 
    bet_menu(R, CB, ACT, B).

  get_action(bet, checker, _, _, _, _, call, 0).

  get_action(bet, highrise, P, _, _, _, raise, 3) :-  % Raise on wild 
    player_hand(P, _, '2'), !.
  get_action(bet, highrise, P, _, _, _, raise, 3) :-  % Raise on A,K,Q pair 
    player_hand(P, C1, C2),
    C1 = C2,
  denomination_value(C1, D1, _),  % Use "high" value 
    D1 > 11, !.   
    get_action(bet, highrise, P, _, _, _, raise, 2) :-  % Raise on pair 
    player_hand(P, C1, C2),
    C1 = C2, !.
  get_action(bet, highrise, P, _, _, _, raise, 1) :-  % Raise on A,K,Q 
    player_hand(P, C, _),
    denomination_value(C, D, _),  % Use "high" value 
    D > 11, !.
  get_action(bet, highrise, P, _, _, _, fold, 0) :-  % Fold if poor high card 
    player_amt(0, draws, 0),  % Only before draw 
    player_hand(P, C1, C2),
    C1 \= C2,  % Stay on a pair 
    denomination_value(C1, D1, _),  % Use "high" value 
    D1 < 10, !.
  get_action(bet, highrise, P, _, _, _, fold, 0) :-  % Fold if "medium" 
    player_amt(0, draws, N), N > 0,  % Only after draw 
    player_hand(P, C1, C2),
    C1 \= C2,  % Stay on a pair 
    denomination_value(C1, D1, _),  % Use "high" value 
    D1 > 5, D1 < 12, !.
  get_action(bet, highrise, _, _, _, _, raise, 1) :-  % Defensive raise 
    player_amt(0, draws, 0), !.  % Only before draw 
    get_action(bet, highrise, _, _, _, T, fold, 0) :-  % Fold if BIG bet 
    player_amt(0, draws, N), N > 0,  % Only after draw 
    T > 6, !.
  get_action(bet, highrise, _, _, _, _, call, 0) :- !.

Here are the same decision rules transcribed to Scala. Note how the pattern matching moves out of the predicate/function header into the match case constructs. The successive Prolog “test” predicates that can trigger backtracking upon failure evaluation must be converted into guard conditions on each case pattern.

  // Returns (action, betAmount)
  def get_action_bet(mode: String, player: Int, remainingPlayers: Int, remainingBets: Int, totalBet: Int): (String, Int) = {
    val hand = gPlayerHand(player)
    
    mode match {
      case "human" => {
        show_players_pot
        show_players_human
        val playerBet = gPlayerAmountBet(player)
        val callAmount = totalBet - playerBet
        val actionBetAmount = bet_menu(remainingBets, callAmount)
        
        return actionBetAmount
      }
      case "checker" => {
        return ("call", 0)
      }
      case "highrise" => {
        hand match {
          case (_, "2") => {
            // Raise on wild.
            return ("raise", 3)
          }
          case (c1, c2) if c1.equals(c2) && (card_high_value(c1) > 11) => {
            // Raise on A, K, Q pair.
            return ("raise", 3)
          }
          case (c1, c2) if c1.equals(c2) => {
            // Raise on any other pair.
            return ("raise", 2)
          }
          case (c1, _) if (card_high_value(c1) > 11) => {
            // Raise on unpaired A, K, Q.
            return ("raise", 1)
          }
          case (c1, _) if (card_high_value(c1) < 10) && (gPlayerAmountDraws(player) == 0) => {
            // Fold on unpaired poor high card if before draw.
            return ("fold", 0)
          }
          case (c1, _) if ((6 to 11) contains card_high_value(c1)) && (gPlayerAmountDraws(player) > 0) => {
            // Fold on unpaired medium high card if after draw.
            return ("fold", 0)
          }
          case (_, _) if (gPlayerAmountDraws(player) == 0) => {
            // Defensive raise if before draw.
            return ("raise", 1)
          }
          case (_, _) if (totalBet > 6) &&  (gPlayerAmountDraws(player) > 0) => {
            // Fold if REALLY BIG bet after draw.
            return ("fold", 0)
          }
          case _ => {
            return ("call", 0)
          }
        }        
      }

Next Steps

Having dipped my toes into the concise and flexible language known as Scala, I will attend a one-day tutorial at this week’s CodeMash conference. I expect to learn some refinements I can make to this simple poker game application.

More ambitiously, I hope to take the more advanced rules engine in my News Goggles demonstration application and convert it from Prolog to Scala.

In addition to the easier access to breakpoint debugging mentioned above, I see value in Scala over Prolog in terms of likely acceptance by corporate architects for use in a Java application shop. The Scala compiler produces regular Java byte-code, compatible with JVM 1.5 and higher. At run-time, a Scala library JAR file must be deployed with the application but this does not differ from any other open-source support tool used to enhance Java developer productivity.

Advertisements