On Dec 15, 2004, at 2:17 AM, David E. Wheeler wrote:
Ovid and I were getting fed up with the horrible DFA::Simple
module, so I wrote a new module, DFA::StateMachine, to take
its place in our work.
Cool.
But I'm no computer scientist, so I'm not even sure whether
the name is right or if the module functions the way a DFA
state machine is supposed to behave. So I would greatly
appreciate feedback on it. You can grab it from here:
http://www.justatheory.com/computers/programming/perl/modules/DFA-
StateMachine-0.01.tar.gz
It's been several years since my algos class, but I'm not sure
that DFA is the right term to use in the name. According to the
jargon file:
A deterministic FSM (DFA) is one where the next state is
uniquely determinied [sic] by a single input event. The next
state of a nondeterministic FSM (NFA) depends not only on the
current input event, but also on an arbitrary number of
subsequent input events.
According to wikipedia.org:
A further distinction is between deterministic and
nondeterministic automata. In deterministic automata, for each
state there is exactly one transition for each possible input
(DFA). In non-deterministic automata, there can be none or
more than one transition from a given state for a given
possible input (NFA, GNFA).
It seems to me that your code could be used to implement either
a DFA or an NFA, so you might want to call it it an FSM.
Algorithm::FSM, perhaps? Or maybe Decision::FSM??
Anyhow, I think of each transition in an FSM being triggered by
some input (say, the next line in a file) or event -- rather
than just telling it to check to see which state to transition
to next, you feed it the next input and that's what it uses to
decide (along with other things, though IIRC that would make it
an NFA rather than a DFA). I'd expect it to work something like
this:
# State machine
my $dfa = DFA::StateMachine->new(
foo => {
# NOTE: $_[0] is the DFA object and $_[1] is the input
enter => sub { print ">> foo\n" if $DEBUG },
do => sub { $_[0]->{foo} = $_[1] },
goto => [
bar => sub { $_[1] =~ /^bar\b/ },
baz => sub { $_[1]->isa('Foo::Bar') }
qux => 1, # Or undef, whatever magic value you want
],
leave => sub { print "<< foo\n" if $DEBUG },
},
bar => { ... },
baz => { # A terminal state
enter => sub { print "All done!\n" if $verbose },
do => sub { $_[0]->done(1) },
},
qux => { ... },
);
# "Driver" code
$dfa->start('foo');
while (!$dfa->done) {
my $input = fetch_next_input();
last unless defined $input;
chomp;
$dfa->process($input); # Or C<check> if you prefer
}
die "DFA didn't reach a terminal state"
unless $dfa->done;
In essence, you've written DFA::StateMachine to use a "pull"
model in which the code that checks what to do next "fetches"
the input itself, where I would generally want to use a "push"
model in which the driver code takes care of that. They're
effectively equivalent, it just might be more straightforward to
use a push model, especially if your program is dealing with
input that's awkward to "unpull" such as file I/O.
The nice thing is, easy to use a push-oriented API in a pull
kind of way; just don't feed the DFA any input (C<$dfa->process>
rather than C<$dfa->process($input)>) and write your "goto"
closures so they don't expect to get any input.
BTW, I really like how your implementation avoids polluting the
object with special elements (e.g., $self->{__states__} or some
such) by keying the states off the stringified object. Nice!
You might want to factor out some common subexpressions,
C<$states{$self}> in particular. That's a bit nitpicky --
premature optimization yadda yadda -- but in some places it
would make the code easier to read.
If you like my ideas but you're short on time, let me know; I
might be able to whip up a patch.
Paul.
P.S.: You could implement DFA::StateMachine::done() by setting
the done flag in $states{$self}->{done} or simply undef'ing
$states{$self}->{current}.
--
Paul Hoffman :: [EMAIL PROTECTED] :: http://www.nkuitse.com/
