Recently in sam Category

I finally got the project web site for the Sam State Machine Engine project launched and added to the Xephyrus Labs index.

Now I'm working on getting the version 2.0 functionality in place.  You know, in my spare time.  (That's a joke.)

The 2.0 feature list is fun.  I've been playing with using Annotations to register the state worker methods (so you will no longer have to do a manual "register()" call), and cycle callbacks, and other fun things.  The feature list is on the main site, too.  (winkyface)

Let's write a quick little version of Penney's Game using the clever little state machine engine, sam.  Penney's Game is a fun little bar game you can con your friends into playing to get them to pay for the drinks.

I want to focus on the implementation here, so here's a link for you to find out about Penney's Game (if you need it).

Before we start throwing code together, let's talk a bit about how we might put our state machine together.  We have a few options.  We could build a state for each pattern.  If we limit the pattern length to 3, that would mean 17 states: an empty start state, single flip heads and tails states, 4 double flip states covering the possible combos there, 8 triple flip states to cover those combos, then a state for player 1 winning and a state for player 2 winning.

I'm lazy and that sounds like a lot of work.  Plus, if we follow that route, we wouldn't be able to run a 4-flip game.  At least, not without adding in aw geez more states.

Another option is to just have states representing game loop flow, like one for flipping, another for checking victory conditions, and so like that.  That feels nicer to me, so that's the approach I'm going with.

Here are the states I've come up with:

public enum PenneysState
{
  ValidatePatterns,
  Flip,
  CheckVictory,
  VictorFound
}

There are really only 2 working states, Flip and CheckVictory.  But this is supposed to be a nice simple demo, so few is good.

For the payload, we need to track a few things:

• Player 1's victory pattern.
• Player 2's victory pattern.
• The history of flips for this game.
• Which player won.

We also have to have an id for the payload to fulfill the Payload contract.  Our usage pattern for this game is a single execution, so the id is pretty much useless to us.  Still, a contract is a contract and our honor is at stake.  So, we'll just put a little something in for the id too.

Here's what I have for the payload:

public class PenneysPayload
  implements Payload
{
  public enum Flip
  {
    Heads,
    Tails
  }

  public PenneysPayload (String playerOnePattern, String playerTwoPattern)
  {
    _playerPatterns = new String[] { playerOnePattern, playerTwoPattern };
    _flips = new StringBuilder();
    _id = System.currentTimeMillis();
  }

  public void addFlip (Flip flip)
  {
    _flips.append(flip.name().charAt(0));
  }

  public String getFlips ()
  {
    return _flips.toString();
  }

  @Override
  public Long getId ()
  {
    return _id;
  }

  public String getPlayerOnePattern ()
  {
    return _playerPatterns[0];
  }

  public String getPlayerTwoPattern ()
  {
    return _playerPatterns[1];
  }

  public String[] getPlayerPatterns ()
  {
    return _playerPatterns;
  }

  public Integer getVictor ()
  {
    return _victor;
  }

  public void setVictor (Integer victor)
  {
    _victor = victor;
  }

  private Long _id;
  private StringBuilder _flips;
  private String[] _playerPatterns;
  private Integer _victor;
}

The player patterns are immutable, so there are no setters for those.  The flip history is only additive, so instead of a setter, we only have an adder for that.  The victor is the only settable property.

I'm stashing the player patterns in an array of 2 so that in the validation step I can just walk through the list of patterns and validate each one.  I could have kept them separate on the inside and provided a getAsList method or something like that, but that would complicate the code a bit more than I'm comfortable with.  I kept getters for each individual pattern to emphasize the distinctness of those two patterns.  The intent is that if you're accessing a single pattern, you use the specific accessor, and if you're accessing all patterns, you use the array accessor, but there's no way to enforce that behavior.

I'm tracking the flip history as a String, but only 'H' or 'T' is valid, so I set up an enum to enforce that addFlip is never called with anything other than a valid option.  (Well, a clever coder could still shove null in there to great effect.  Don't do that.)

Once we have the states determined and the payload laid out, it's really just a matter of walking through the steps to put the machine together.  Let's break that guy down by step.

First the validations.  We need to make sure the patterns input are valid, otherwise Strange Things might occur.

public PenneysState validatePatterns (PenneysPayload payload)
    throws PenneysException
{
  int i = 1;
  for (String playerPattern: payload.getPlayerPatterns())
  {
    if (playerPattern == null)
    {
      throw new PenneysException("No pattern for player " + i);
    }

    if (_INVALID_PATTERN.matcher(playerPattern).find())
    {
      throw new PenneysException("Player " + i + "'s pattern contains invalid indicators.  " +
          "Are those Heads or Tails?");
    }

    i += 1;
  }

  if (payload.getPlayerOnePattern().length() != payload.getPlayerTwoPattern().length())
  {
    throw new PenneysException("The player's patterns are not the same length!");
  }

  return PenneysState.Flip;
}

You'll notice that I'm using an exception to indicate validation failures, rather than having an error state.  Sam considers any Throwable to be an error state, and indicates the error condition in the completion notification.

We just check to make sure neither player submitted a null pattern.  And we check to make sure the pattern only contains H's and T's.  Ah, here's that regular expression being referenced:

static final private Pattern _INVALID_PATTERN = Pattern.compile("[^HT]");

Our final check is to make sure both players submitted the same number of flips in their patterns.  We can't have a good, clean, fair game if one guy submits 4 flips and the other only 3, after all.

Sometimes people think I'm quirky because I do things like i += 1 instead of i++.  In this case, it's because i++ is intended as an inline operative, whereas i += 1 is intended as an assignment operative.  So, yeah, they're right, I am quirky.
 
The flip state code is really just a flip.  That makes it nice and simple:

public PenneysState flip (PenneysPayload payload)
{
  payload.addFlip((_RANDOM.nextInt() % 2 == 0 ? Flip.Heads : Flip.Tails));
  return PenneysState.CheckVictory;
}

Grab a psuedo-random value, mod it down to odd or even, and translate that to heads or tails.

That leaves us with the victory checker.

public PenneysState checkVictory (PenneysPayload payload)
{
  int i = 1;
  for (String playerPattern: payload.getPlayerPatterns())
  {
    if (payload.getFlips().endsWith(playerPattern))
    {
      payload.setVictor(i);
      return PenneysState.VictorFound;
    }
    i += 1;
  }
  return PenneysState.Flip;
}

To check for victory, we need to look at the tailing end of the flip history, that is, the most recent flips.  The stock endsWith call takes care of that for us.  So, if we find a match, we set the victor in the payload and jump to the end state.  If we get to the end of the check, we know there was no victor, and we need to flip again.

Since we don't have annotations in sam yet, we still need to manually associate the states with their worker methods.  We take care of that in the constructor.

protected PenneysMachine ()
    throws NoSuchMethodException
{
  super(PenneysState.class,PenneysPayload.class);
  registerState(PenneysState.ValidatePatterns,"validatePatterns");
  registerState(PenneysState.Flip,"flip");
  registerState(PenneysState.CheckVictory,"checkVictory");
}

By the way, that call to super in the constructor is a must.  Skipping that will cause breakages.

Also, remember that end states, such as VictorFound, don't get worker methods associated with them.  That's how sam knows which states are end states.  For those of you who are quirky in different ways than I, you could also use null as an end state.  If any state worker returns null instead of a state, that payload will be considered to be in it's end state.  But I like having a valid, indicated end state.  It serves as a nice resolution for my brain.

The last piece we need to build is the user interface.  We put the machine together so that we could really paint any type of user interface on this thing, a web service, a Swing application, even an FX application.  For our little example, we'll keep it small and simple and just do a command-line interface with output spewing to standard out.  After all, this is about the state machine, not some UI framework.

We will need the state machine to tell us the results of each execution.  So, our main class will need to implement the CompletionListener.

public class PenneysGame
  implements CompletionListener<PenneysState,PenneysPayload>

We'll need a few steps to set up the machine and kick it off before we try to process our game payload.  We do that in the constructor so everything is ready to roll upon instantiation.

public PenneysGame ()
    throws NoSuchMethodException
{
  _machine = new PenneysMachine();
  _machine.setProcessingQueue(new MemoryProcessingQueue<PenneysState,PenneysPayload>());
  _machine.addCompletionListener(this);
  _machine.start();
}

We set ourselves to be notified on completion, and start up the beastie.

To start a new game, we can have a little method called play.

public void play (String player1Pattern, String player2Pattern)
{
  System.out.println("Player 1's pattern: " + player1Pattern);
  System.out.println("Player 2's pattern: " + player2Pattern);
  System.out.println("\nPlaying...\n");

  _machine.process(new PenneysPayload(player1Pattern,player2Pattern));
}

Then, to handle the notifications, here's the notifyComplete part.

@Override
public void notifyComplete (PenneysPayload payload, PenneysState lastState, Exception error)
{
  if (error != null)
  {
    System.out.println("ERROR: " + error.toString());
  }
  else
  {
    System.out.println("Flip pattern was: " + payload.getFlips());
    System.out.println("Victor was: Player " + payload.getVictor());
  }
  _machine.requestStop();
}

This completion handles both happy path and error conditions.  Since we're only playing a single round per execution, we shutdown the machine once we get our first notification, regardless of whether or not that payload ended in an error state.

There's one more little tool we'll need before we can build the main.  We need to be able to have our UI thread pause and wait until the game completes.  It may take any number of flips to complete; we have no way of knowing how long it will be.  We could guess that it'll be less than a second (and we'd be right) and just have the main sleep for a second.  But that's a pretty lousy and brittle solution.  Any change to the system that changed how long that step takes could break it.

In general, it's best to avoid using timed waits for synchronization.

Instead, we could do a timed wait then check to see if the machine is still running.  Something like this.

public void waitWhilePlaying ()
{
  while (_machine.isAlive())
  {
    try
    {
      Thread.sleep(1000L);
    }
    catch (InterruptedException ignore)
    {
    }
  }
}

But then, it would really be better if we could just tell our thread to pause for as long as the machine is active, and continue as soon as it's not.  Good news, everybody.  A machine is a thread, so you can join a machine with all the proud confidence you would join any old processing thread.

public void waitWhilePlaying ()
{
  try
  {
    _machine.join(10000L);
  }
  catch (InterruptedException ignore)
  {
  }
}

Of course, in this case the join works because we're stopping the machine as soon as we get a completion notification.  In a more complex example, you might need to ... well, do something more complex.

Finally, yes, finally, we're ready to throw our main together.  We already have everything coded up, so the main just links all our nice code to the command-line itself.

static public void main (String[] args)
{
  try
  {
    if (args.length < 2)
    {
      System.out.println("PenneysGame usage:");
      System.out.println("  java -jar penneysgame.jar {player1pattern} {player2pattern}\n");
      System.out.println("Each pattern can consist of any number of H's (for heads) or T's ");
      System.out.println("(for tails), however each pattern must be the same length.");
    }
    else
    {
      PenneysGame game = new PenneysGame();
      game.play(args[0],args[1]);
      game.waitWhilePlaying();
    }
  }
  catch (NoSuchMethodException e)
  {
    System.out.println("ERROR: " + e.toString());
  }
}

We do a quick little check just to make sure the user isn't just hunting blindly for usage information, then kick up our PenneysGame and fire off a game.

Cool!  Let's run it and see what happens!  I'll run it with an extreme case, HHH and THH.

Player 1's pattern: HHH
Player 2's pattern: THH

Playing...

Flip pattern was: HTTHH
Victor was: Player 2

And that, ladies and gentlemen, is Penney's Game in sam.

Sam is a Java state machine engine.  I know, it sounds redundant putting that word engine after the word machine.  What I mean is it's an engine for driving state machines.

I'm going to assume you know what a state machine is, and how it's used.  If not, here's some reading for you:

• Finite-state Machine, Wikipedia
• Using State Machines, Hank Wallace, Atlantic Quality Design, Inc

So, now, let's talk about the basic functionality of sam.

There are three basic entities that sam works with: the state, the payload and the machine.  The state is an enum type which defines all the possible states of the machine.  The payload is a pojo which is the piece that is worked upon.  The machine is the code that runs it all.

It might be easiest to walk through a quick example.  Let's say we have a simple A-B-C state machine: A goes to B, B goes to C.  So, first off, let's define our states:

public enum AbcState
{
  A,
  B,
  C
}

Now for our payload, let's have the payload include a little cycle tracker which just tracks how many times it's been called.  This is just to give the payload something to carry.  Normally it would carry the information being processed, along with whatever context is needed to process it.

The only requirement for a payload is that it define an Id field.  We use the Payload interface to enforce that.  So, here's our payload:

public class AbcPayload
  implements Payload
{
  public AbcPayload (Long id)
  {
    _id = id;
    _cycle = 0;
  }

  public Long getId ()
  {
    return _id;
  }

  public int cycle ()
  {
    return _cycle++;
  }
  
  private Long _id;
  private Integer _cycle;
}

For the machine, we just need to define the methods to perform the work of each state.  Each of these worker methods must take the payload as it's only parameter and must return the state upon completion.  In other words, they must be defined with the method signature:

State functionName (Payload payload)

In version 1 of sam, we don't yet have annotations, so each worker method has to be registered with the state machine.  In this example we'll take care of that in the constructor, which seems a fine place to do that sort of thing.  Here's what we have for our simple little ABC State Machine:

public class AbcStateMachine
  extends StateMachine<AbcState,AbcPayload>
{
  public AbcStateMachine ()
      throws NoSuchMethodException
  {
    super(AbcState.class,AbcPayload.class);
    registerState(AbcState.A,getClass().getMethod("doA",AbcPayload.class));
    registerState(AbcState.B,"doB");
  }

  public AbcState doA (AbcPayload payload)
  {
    int cycle = payload.cycle();
    if (cycle < 3)
    {
      return AbcState.A;
    }
    return AbcState.B;
  }

  public AbcState doB (AbcPayload payload)
  {
    int cycle = payload.cycle();
    if (cycle < 8)
    {
      return AbcState.B;
    }
    return AbcState.C;
  }
}

You may notice that there is no worker method for state C.  That's because it's the Done state.  When the state machine reaches a state with no method, it considers that payload done and stops processing it.

Another thing you may notice is that the first register call finds the method and registers it, while the second just passes the name of the method.  Both ways work.  Personally, I like the second method since it's so much easier.

So then, to get this beast rolling and processing something, we need a few lines of setup and configuration:

Instantiate the machine:

StateMachine<AbcState,AbcPayload> machine = new AbcStateMachine();

Set the queue manager (more on that later):

machine.setProcessingQueue(new MemoryProcessingQueue<AbcState,AbcPayload>());

And start the machine:

machine.start();

Then, to plunk a new payload into the machine for processing:

machine.process(myMagicPayload);

One of the things I'm happy with in sam is how easy it is to set up a new state machine.  No twisting abstractions or convoluted declarations.*  Just set it up and make it go.


* Well, other than registering each worker method manually, but annotations will fix that right up good.

Way back when, in the olden days, the early ought days, the days when the memories of a big technology bubble were still fresh in my mind, I was racking my brain for something COOL to do.  I would have loved to have come up with something like video-in-flash, or a yeti batting a penguin, but my brain didn't find those ideas.

Flume was a clever little idea to address an issue I ran into all the time: Different groups like to work with different technologies, but some suit always wants to hook together pieces from all those groups.  Flume was a pipelining tool which would take a context and pass it to different technologies.  While I was writing the little proof-of-concept prototype, I thought, Why do I have to write a new state machine every time I need one?  There should be a generic state machine library.  I wrote one as part of Flume, but it was horrid.

Fast forward a few years to an evening with my friend Robert, or Trebor if you like handles.  Robert write beautiful code.  He is brilliant at finding the perfect balance between abstraction and effectiveness.  He also has a thing for genetic algorithms.  That night we had a long conversation about using structured tree languages in genetic algorithms.  It inspired me, so a few weeks later I wrote another state machine for some weekend project playing around with defining a structured tree programming language using XML, but it was a bit too... recursive.

In another few years I started working extensively with workflow engines.  I wrote and worked on several proprietary workflow engines, which all begged to be state machine driven (but weren't).  Finally I wrote a nice big complicated generic state machine Tool.  Notice the capital T?  Yeah, that rhymes with P.  And I now think of that state machine as Trouble.

About 6 months ago I sat down and wrote out a framework for a generic state machine engine which is small and simple.  It's easy to use and easy to forget about, which is nice.

And thus, sam was born.