Re: DFA::StateMachine
On Dec 15, 2004, at 12:00 PM, [EMAIL PROTECTED] wrote: - get_next_state() returns a new DFA object, which is in the next state. If there is no next state, it returns undef. In version 2 I'll make the states objects. But this will do for now. :-) I mean making the whole DFA an object. Once you can return a whole DFA, you could easily explore states and do backtracking in a higher level of abstraction. - Flavio S. Glock
Re: DFA::StateMachine
On Dec 16, 2004, at 4:16 AM, [EMAIL PROTECTED] wrote: In version 2 I'll make the states objects. But this will do for now. :-) I mean making the whole DFA an object. Once you can return a whole DFA, you could easily explore states and do backtracking in a higher level of abstraction. Yes, I had the same thought. And while I may well add that aat some point, as I said, this gets me what I need for now. Ovid did add a stack() method, at least, so you can get a list of all the states your machine has been in. That's in 0.05. Cheers, David
RE: DFA::StateMachine
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. 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. /pedant mode: The term DFA::StateMachine is like say Car::Car. A DFA is by definition a state machine (it stands for determinisitic finite state automata). And after a review of the code IMO using the term DFA is a bad call. Normally DFA implies a specific type of implementation of a pattern matcher (as compared to say perls NFA [nondeterministic finite state automata] regex engine). While I can see the overlap that you are getting at here I think you will find less people review your work just because they think it must have to do with pattern matching and not to do with the generic construction of a rules processor. This is more of a turing machine than what is normally called a DFA. A term that you encounter in the literature for this type of construct is an FSA (finite state automaton/aka turing machine) which doesn't have such a strong association to pattern matching. Maybe: FSA::Rules is better? /end pedant mode Having said that it looks like an interesting module. Id be curious as to what you use it for tho. Yves
RE: DFA::StateMachine
--- Orton, Yves [EMAIL PROTECTED] wrote: Maybe: FSA::Rules is better? I'm quite happy about that name, assuming it truly describes what we've done. I also don't have a strong comp-sci background, so I appreciate pedant mode. Having said that it looks like an interesting module. Id be curious as to what you use it for tho. After much laborious effort, trying to track all of the special rules for a complex build system (Bricolage) just became too tedious and error-prone. With a rules-based system, David drew a diagram of the of the rules and I implemented them (but with a wrapper around DFA::Simple. http://use.perl.org/~Ovid/journal/22298). Once this solution was in place, adding new rules was trivial, but DFA::Simple is a curious beast and was causing us problems. Cheers, Ovid = Silence is Evil http://users.easystreet.com/ovid/philosophy/decency.html Ovid http://www.perlmonks.org/index.pl?node_id=17000 Web Programming with Perl http://users.easystreet.com/ovid/cgi_course/
RE: DFA::StateMachine
Based on this definition, I'm not sure if my module is a DFA or an NFA state machine. In each state, you can define rules for transitioning to other states. When you call the check() method, it checks each of these in the order you defined them and transitions to the first state for which the rule evaluates to a true value. This means that multiple rules could evaluate to a true value, but since it short-circuits and there is no backtracking, technically only one transition can occur. I guess that makes it a DFA, no? IMO yes. However its also similar to the type of production system described by Church. (hefty IIRC on that :-) So long as there can only be one legal transition for a given configuration of the machine then its a DFA. Yves
Re: DFA::StateMachine
On Dec 15, 2004, at 11:00 AM, David Coppit wrote: Yes, but not in the traditional sense. Traditionally, you can only have 1 transition from a state for a given input. i.e. the model all by itself defines a deterministic behavior. What you actually have is model+algorithm defining a deterministic behavior. Right. IMHO, I would simply disallow multiple transitions in the model, which would make it a real DFA. This change shouldn't impact your algorithm. (i.e. it's doesn't find the *first* match, but rather *the* match.) Hrm. I'm not sure how I would enforce that. But either way, I think DFA::Rules is a good name. I'm pretty sure you don't want to try to implement an NFA directly. You'd have to explore each possible transition (and following transitions), backtracking when you reach a dead end. It would be better to convert an NFA into a DFA. (NFAs are equivalent in power to DFAs.) Yeah, I have no interest in implementing an NFA. This DFA does what I need with 1/100th the work. ;-) Thanks for the feedback! David
Re: DFA::StateMachine
On Dec 15, 2004, at 7:04 AM, Tim Bunce wrote:
- I'd suggest renaming check() to
attempt_transition() and have it return
the new state or undef (not croak) if it can't
transition at the moment.
How 'bout I borrow DFA::Simple's
Check_For_NextState()? No?
attempt_transition() is a bit long. Maybe
eval_rules()? Right now check() returns the
object itself and croaks on failure.
- get_next_state() returns a new DFA object, which
is in the next state. If there is no next state, it
returns undef.
Examples:
if ( $state1-get_next_state() )
{
$state1-next_state;
}
else
{
die no next state;
}
if ( $state2 = $state1-get_next_state() )
{
$state1 = $state2;
}
else
{
die no next state;
}
- Flavio S. Glock
Re: DFA::StateMachine
On Wed, 15 Dec 2004, David E. Wheeler wrote: I guess that makes it a DFA, no? Yes, but not in the traditional sense. Traditionally, you can only have 1 transition from a state for a given input. i.e. the model all by itself defines a deterministic behavior. What you actually have is model+algorithm defining a deterministic behavior. IMHO, I would simply disallow multiple transitions in the model, which would make it a real DFA. This change shouldn't impact your algorithm. (i.e. it's doesn't find the *first* match, but rather *the* match.) I'm pretty sure you don't want to try to implement an NFA directly. You'd have to explore each possible transition (and following transitions), backtracking when you reach a dead end. It would be better to convert an NFA into a DFA. (NFAs are equivalent in power to DFAs.) David _ David Coppit [EMAIL PROTECTED] The College of William and Maryhttp://coppit.org/ Government big enough to supply everything you need is big enough to take everything you have ... The course of history shows that as a government grows, liberty decreases. -- Thomas Jefferson
Re: DFA::StateMachine
On Dec 15, 2004, at 12:00 PM, [EMAIL PROTECTED] wrote: - get_next_state() returns a new DFA object, which is in the next state. If there is no next state, it returns undef. What's that from? In version 2 I'll make the states objects. But this will do for now. :-) Regards, David
RE: DFA::StateMachine
On Wed, 15 Dec 2004, Orton, Yves wrote: The term DFA::StateMachine is like say Car::Car. Right. A DFA is by definition a state machine (it stands for determinisitic finite state automata). And after a review of the code IMO using the term DFA is a bad call. Normally DFA implies a specific type of implementation of a pattern matcher (as compared to say perls NFA [nondeterministic finite state automata] regex engine). I disagree. A DFA can be used to implement a pattern matcher, but that's not all. A DFA is just a data structure. This is more of a turing machine than what is normally called a DFA. A term that you encounter in the literature for this type of construct is an FSA (finite state automaton/aka turing machine) which doesn't have such a strong association to pattern matching. FSA is a more general term that encompasses both DFA and NFA. Not having checked the code, I'm not sure if it supports nondeterministic transitions. However, you're incorrect in saying FSA==turing machine. The key limitation is that FSAs are *finite* and a turing machine is not. More details: http://en.wikipedia.org/wiki/Finite_state_machine http://www.cs.wm.edu/~coppit/wiki/index.php?title=Quals:_Computer_Theory_and_Algorithms I'm not sure if this discussion helps the OP any, but I thought I should clarify. :) David P.S. My whiz-bang super-fast computer is also equivalent in power to a DFA because its memory is finite. _ David Coppit [EMAIL PROTECTED] The College of William and Maryhttp://coppit.org/ Government big enough to supply everything you need is big enough to take everything you have ... The course of history shows that as a government grows, liberty decreases. -- Thomas Jefferson
RE: DFA::StateMachine
David Coppit replied on 15 December 2004 14:21
On Wed, 15 Dec 2004, Orton, Yves wrote:
The term DFA::StateMachine is like say Car::Car.
Right.
A DFA is by definition a state machine (it stands for
determinisitic
finite state automata). And after a review of the code IMO
using the
term DFA is a bad call. Normally DFA implies a specific type of
implementation of a pattern matcher (as compared to say perls NFA
[nondeterministic finite state automata] regex engine).
I disagree. A DFA can be used to implement a pattern matcher,
but that's not all. A DFA is just a data structure.
But if you do a search for literature talking about DFA's _most_ will be
related to pattern matching. For instance I just googled for determinisitc
finite state automata and most of this hits that i followed concerned
pattern matching or used the language of pattern matching to explain DFA's.
Im not arguing that you are wrong about this, just that the primary
association in most folks heads when they see DFA will be pattern matching.
In fact when discussing DFA's most of the literature discusses the
alphabet the DFA will operate on, and the language it is designed to
accept. (http://en.wikipedia.org/wiki/Deterministic_finite_automaton)
This is more of a turing machine than what is normally called a DFA. A
term that you encounter in the literature for this type of construct is
an FSA (finite state automaton/aka turing machine) which doesn't have
such a strong association to pattern matching.
FSA is a more general term that encompasses both DFA and NFA. Not having
checked the code, I'm not sure if it supports nondeterministic
transitions.
I didnt see any support for non deterministic transitions. And yes FSA does
include DFA and NFA's but it also includes DTM's and NDTM's (determinisitic
turing machines and non determinisitic turing machines).
My point was that FSA's emphasize the point that there is external memory
and that there are actions involved wheras DFA/NFA's normally have no
actions.
However, you're incorrect in saying FSA==turing machine. The key
limitation is that FSAs are *finite* and a turing machine is not. More
details:
http://en.wikipedia.org/wiki/Finite_state_machine
http://www.cs.wm.edu/~coppit/wiki/index.php?title=Quals:_Computer_Theory_and
_Algorithms
I'm not sure if this discussion helps the OP any, but I thought I should
clarify. :)
Actually i think you are wrong here. And the links you provide seem to back
me up. A turing machine does NOT have an infinte number of states. It has an
infinite memory. From the wikipedia article we see the following: (note
point #3)
quote
More precisely, a Turing machine consists of:
1. A tape which is divided into cells, one next to the other. Each cell
contains a symbol from some finite alphabet. The alphabet contains a special
blank symbol (here written as '0') and one or more other symbols. The tape
is assumed to be arbitrarily extendible to the left and to the right, i.e.,
the Turing machine is always supplied with as much tape as it needs for its
computation. Cells that have not been written to before are assumed to be
filled with the blank symbol.
2. A head that can read and write symbols on the tape and move left and
right.
3. A state register that stores the state of the Turing machine. The
number of different states is always finite and there is one special start
state with which the state register is initialized.
4. An action table (or transition function) that tells the machine what
symbol to write, how to move the head ('L' for one step left, and 'R' for
one step right) and what its new state will be, given the symbol it has just
read on the tape and the state it is currently in. If there is no entry in
the table for the current combination of symbol and state then the machine
will halt.
/quote
As far as I know a DFA is defined as a finite automaton where each
state/input combination can result in only one legal transition.
(http://en.wikipedia.org/wiki/Finite_state_machine) An NFA of course can
have multiple transitions for a given state/input combination. (You can see
this definition in regards to determinisitc turing machines and non
deterministic turing machines in the wikipedia article as well.)
P.S. My whiz-bang super-fast computer is also equivalent in power to a DFA
because its memory is finite.
Well, yeah sure, because the memory is finite and it only allows for a
single transition from a given state and input it is formally a DFA. However
this formal equivelency is a bit useless. DFA's have no memory so they cant
handle type 0 languages. However as we all know your desktop does handle
type 0 languages as in practice most statements written in type 0 languages
dont need infinte memory to resolve. But a DFA cant recurse, there is NO
stack just states.
So to put it as the article you linked to did: For example, a Turing
machine describing an algorithm may have a few hundred
Re: DFA::StateMachine
On Wed, Dec 15, 2004 at 10:08:43AM -, Orton, Yves 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.
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.
[...]
Maybe: FSA::Rules is better?
There's a Computer::Theory::FSA module already:
http://search.cpan.org/~frighetti/Computer-Theory-FSA-0.1_05/lib/Computer/Theory/FSA.pm
but it doesn't look pleasant to use.
FSA::Rules seems okay, but it doesn't express the simple utility
of the module. I hate to suggest FSA::Simple but it almost seems
appropriate here.
Having said that it looks like an interesting module. Id be curious as to
what you use it for tho.
I'm looking for a simple FSA module to help manage states in a GUI.
Some quick observations:
- I'd prefix some of the actions with on_
on_enter = sub { ...},
on_leave = sub { ...},
because they don't 'perform' the enter/leave they're just triggered by it.
- The docs aren't very clear about when do actions are run.
They talk about while in the state and in the state.
Saying after entering the state would be more clear.
- Using undef to mean 'always' in the goto rules is confusing.
Using 1 (or any true scalar) would seem more natural.
- Hooks for tracing execution would be helpful.
Using empty methods and requiring users to sub-class would suffice.
- There's scope for refactoring into finer-grained methods.
- I'd suggest renaming check() to attempt_transition() and have it return
the new state or undef (not croak) if it can't transition at the moment.
- Then define check() to be { self-attempt_transition() || croak ... }
But a better name than check() would also be good.
- Looks good!
Any idea how soon it might reach CPAN once a name is chosen?
Tim.
Re: DFA::StateMachine
On Dec 15, 2004, at 9:42 AM, David E. Wheeler wrote:
- Then define check() to be { self-attempt_transition() || croak
... }
But a better name than check() would also be good.
Ah, I guess you like the idea of attempt_transition() returning undef
on failure but not die'ing, eh? I guess it'd be easy enough to support
both approaches, as you suggest.
How about try_switch()? Much shorter, but with the same meaning. And it
does operate rather like Switch.pm -- it essentially executes a
short-circuiting switch statement.
I think I like it. Then I could have switch() be the one that croaks.
Thoughts?
Cheers,
David
Re: DFA::StateMachine
On Dec 15, 2004, at 11:27 AM, David E. Wheeler wrote: On Dec 15, 2004, at 6:34 AM, Orton, Yves wrote: As far as I know a DFA is defined as a finite automaton where each state/input combination can result in only one legal transition. (http://en.wikipedia.org/wiki/Finite_state_machine) An NFA of course can have multiple transitions for a given state/input combination. (You can see this definition in regards to determinisitc turing machines and non deterministic turing machines in the wikipedia article as well.) Based on this definition, I'm not sure if my module is a DFA or an NFA state machine. In each state, you can define rules for transitioning to other states. When you call the check() method, it checks each of these in the order you defined them and transitions to the first state for which the rule evaluates to a true value. This means that multiple rules could evaluate to a true value, but since it short-circuits and there is no backtracking, technically only one transition can occur. It short-circuits and there's no backtracking? That's odd. Seems like that should be stated in the docs somewhere, since that's how most people expect an FSA to work. In any case, in order to be a DFA, it must satisfy the following conditions: 1) Mutually exclusive set of transitions away from any node (which you basically satisfy by only using the first match) 2) Every transition must consume some input. For pattern-matching, this means every transition steps forward through the target string, but since the transitions in your module are arbitrary and user-defined, it seems like one could easily create a machine where this (or an analog of it) isn't necessarily true. So it looks like you've got NFAs (or just FSAs, if you prefer), not DFAs. -Ken
Re: DFA::StateMachine
On Dec 15, 2004, at 12:02 PM, Ken Williams wrote: It short-circuits and there's no backtracking? That's odd. Seems like that should be stated in the docs somewhere, since that's how most people expect an FSA to work. I'm expanding the docs now, even as I incorporate people's suggestions. In any case, in order to be a DFA, it must satisfy the following conditions: 1) Mutually exclusive set of transitions away from any node (which you basically satisfy by only using the first match) Cool. 2) Every transition must consume some input. For pattern-matching, this means every transition steps forward through the target string, but since the transitions in your module are arbitrary and user-defined, it seems like one could easily create a machine where this (or an analog of it) isn't necessarily true. Yes, that's true. So it looks like you've got NFAs (or just FSAs, if you prefer), not DFAs. D'oh! I've already renamed it DFA::Rules in Subversion. Ah, well, at least it's easy to change. Look for the new module to be on CPAN later today. Thanks for the feedback and definitions, Ken. Regards, David
