The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.

NAME

Auto::Mata - A simple, reliable finite state machine

VERSION

version 0.03

SYNOPSIS

  use strict;
  use warnings;
  use Auto::Mata;
  use Types::Standard -types;

  my $NoData   = Undef,
  my $HasFirst = Tuple[Str];
  my $HasLast  = Tuple[Str, Str];
  my $Complete = Tuple[Str, Str, Int];

  sub get_input {
    my $query = shift;
    print "\n$query ";
    my $input = <STDIN>;
    chomp $input;
    return $input;
  }

  my $fsm = machine {
    ready 'READY';
    terminal 'TERM';

    transition 'READY', to 'FIRST',
      on $NoData,
      with { return [get_input("What is your first name? ")] };

    transition 'FIRST', to 'LAST',
      on $HasFirst,
      with { return [@$_, get_input("What is your last name? ")] };

    transition 'LAST', to 'AGE',
      on $HasLast,
      with { return [@$_, get_input("What is your age? ")] };

    transition 'AGE', to 'TERM',
      on $Complete;
  };

  my $prog = $fsm->();
  my $data;

  while (my ($state, $output) = $prog->($data)) {
    ;
  }

  printf "Hello %s %s, aged %d years!\n", @$data;

DESCRIPTION

Finite state machines (or automata) are a technique for modeling the workflow of a program as a series of dependent, programmable steps. State machines are useful tools for building software whose behavior can be predicted with a high degree of confidence.

Using a state machine to implement a program helps to ensure determinacy, where the program state is known at all times. Designing software this way leads to greater accuracy and testability.

WHAT IS A STATE MACHINE

A program can be described as a set of discrete states. Each state is defined by the existence or value of a variable, the presence of a file, etc. A state machine replaces the if/else clauses typically used to inspect and branch based on run-time conditions.

Rather than performing ad hoc tests using if/else conditions, the program is instead described as a set of transitions which move the program from an initial state to a final state. The state machine begins in the "ready" state. The initial state is described using an identifier and a type constraint (see Type::Tiny and Types::Standard). When input matches the transition's initial state, the transition step is executed, after which the new initial state is the final state described in the transition. This proceeds until the "terminal" state is reached.

EXPORTED SUBROUTINES

Auto::Mata is an Exporter. All subroutines are exported by default.

machine

Creates a lexical context in which a state machine is defined. Returns a function that creates new instances of the defined automata.

The automata instance is itself a function that performs a single transition per call. It accepts a single reference value as input representing the program's current state. This value in conjunction with the current state label is matched (see "on") against the transition table (defined with "transition") to determine the next state.

Once a match has been made, the action defined for the transition (using "with") will be executed. During evaluation of the "with" function, $_ is a reference to the input value.

The return value is new state's label in scalar context, the label and state in list context, and undef after the terminal state has been reached.

Note that the reference used as input may (and likely will have) have been modified during the transition. It will always be the reference passed as input.

  # Define the state machine
  my $builder = machine {
    ...
  };

  # Create an instance of the machine that operates on $state.
  my $program = $builder->();

  # Run the program
  my $state = [];
  while (my ($token, $data) = $program->($state)) {
    print "Current state is $token\n"; # $token == label of current state (e.g. READY)
    print "State data: @$data\n";      # $data == $state input to $program
  }

ready

Sets the name given to the "ready" state. This is the initial state held by the state machine.

terminal

Sets the name given to the "terminal" state. This is the final state held by the state machine. Once in this state, the machine will cease to perform any more work.

term

Alias for "terminal".

transition

Defines a transition between two states by matching the symbol identifying the state at the end of the most recent transition and the input passed into the transition engine (see "machine") for the transition being performed.

The first argument to transition is the symbol identifying the state at the outset of the transition. A Type::Tiny constraint is used to identify the expected input using "on". When both of these match the current program state, the return value of "with" replaces the current input in place. "with" is permitted to the current input. If "with" is not specified, the input remains unchanged. Once the transition is complete, the symbol supplied by "to" will identify the current program state.

It is an error to have two identical transitions, even with different constraints. This is intentional. A transition that matches two different states is, in fact, two distinct transitions, and the program should be modeled as such in order to prevent errors due to unexpected or improperly checked data. In general, it is a good idea to be as specific as possible with the type constraints used to define the initial transition state.

The first transition is always from the "ready" state. The final transition is always to the "terminal" state. There may be no transitions from the "terminal" state.

The following functions are used in concert with "transition".

to

A name identifying the state held after the transition.

on

A Type::Tiny constraint that matches the state immediately before the transition.

with

A code block whose return value is the mutable state used to determine the next transition to perform. Within the code block $_ is a reference to the program state.

  machine {
    ...

    transition 'INITIAL_STATE', to 'THE_NEXT_STATE',
      on Dict[command => Str, remember => Bool],
      with {
        if ($_->{command} eq 'fnord') {
          return {command => undef, remember => 0};
        }
        else {
          return {command => undef, remember => 1};
        }
      };
  };

DEBUGGING

If $ENV{DEBUG_AUTOMATA} is true, helpful debugging messages will be emitted to STDERR.

AUTHOR

Jeff Ober <jeffober@gmail.com>

COPYRIGHT AND LICENSE

This software is copyright (c) 2017 by Jeff Ober.

This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.