RFC: DFA::StateMachine
Hi All, 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. 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 Thanks! David
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
ANN: FSA::Rules
On Dec 15, 2004, at 12:43 PM, David E. Wheeler wrote: 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. And here it is: The following report has been written by the PAUSE namespace indexer. Please contact [EMAIL PROTECTED] if there are any open questions. Id User: DWHEELER (David Wheeler) Distribution file: FSA-Rules-0.02.tar.gz Number of files: 11 *.pm files: 1 README: FSA-Rules-0.02/README META.yml: FSA-Rules-0.02/META.yml Timestamp of file: Wed Dec 15 22:06:02 2004 UTC Time of this run: Wed Dec 15 22:34:51 2004 UTC The following packages (grouped by status) have been found in the distro: Status: Successfully indexed module: FSA::Rules version: 0.02 in file: FSA-Rules-0.02/lib/FSA/Rules.pm status: indexed __END__ This reminds me, though. Is there a way to specify keywords for the CPAN indexer, preferably in Build.PL? I'd like to add the keywords DFA and NFA, if for no other reason than that people can find FSA::Rules when they search on those terms, in case they're not familiar with FSA. Anyway, enjoy! David
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: RFC: DFA::StateMachine
On Dec 15, 2004, at 3:56 PM, Paul Hoffman wrote:
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??
I went with FSM::Rules. I think it's a good name, and falls in line, I
think, with your suggestions.
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.
That's a good idea. I think I'll add that to the Ctry_switch() method
(which is what I ended up renaming from Ccheck()). Really simple.
Look for it in 0.05 in a bit.
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!
Thanks! I just wanted it to be an empty hash that the states could
stash stuff into. Makes it easier to subclass, too.
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.
Yeah. That's low-ish on my priority list, though.
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}.
You're a mind reader. Ovid suggested the same thing to me, and it's now
in 0.04 (making its way to CPAN). He even suggested the same name! It
can optionally be a code reference, too, which makes it potentially
more convenient.
Regards,
David
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 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
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: [RESEND] Machine-Manipulatable Arguments for Module::Build
On Aug 2, 2008, at 13:40, David E. Wheeler wrote:
2. Not capabale of being manipulated by an external program - Only
perl can
understand Perl, etc..
It looks like M::B does not current put the keywords into the
META.yml file when you run `make distmeta`. It ought to.
Actually, I was mistaken: It does. You just have to write it like this:
meta_add = {
keywords = [qw(foo bar baz)],
},
And then it gets written to META.yml. So I'm not sure what more you
could need.
Best,
David
Re: [RESEND] Machine-Manipulatable Arguments for Module::Build
On Aug 3, 2008, at 05:19, Shlomi Fish wrote: Hmmm... that's interesting. Sounds useful. Is it supported in search.cpan.org/kobesearch yet? Of course, I'd also like to have Freshmeat-like categories: http://freshmeat.net/browse/18/ You would need to get them into the META spec, I think. Because The only thing that can parse Perl is perl. It would be very hard to write a third-party program that will parse a typical Build.PL syntax and manipulate it along with all the possible edge-cases. For example, in some of my modules I have used a sub-class of Module::Build (which I called Test::Run::Builder) instead, so if I'm looking for Module::Build I won't find it. Um, nothing has to parse Build.PL. It generates META.yml, which can be parsed. End of story. (Oh, and BTW, Adam Kennedy put the lie to only Perl can parse Perl myth.) Similarly, I can name the Module::Build instance in any way I want which will further complicate things. Or I can put some of the parameters in variables, etc. I don't follow you here. Yes, but if I over-ride the paramaters in META.yml, then it will be over-written once I re-run Build.PL. META.yml is entirely at the mercy of Build.PL and should not be edited by hand. Correct. I want to allow a program or a human to give parameters to Build.PL so they'll eventually be preserved there. You can pass parameters to Build.PL quite easily: via the command-line. No, it's not. Build.PL places some other parameters into META.yml, like the individiuals .pm files and their versions, etc. We need a way to input it paraemeters in a way that's not hard-coded in the Build.PL Perl code. Why? I find Perl easier to type than YAML. YAML is much more error-prone, IMO. Yes, but computer programs can more easily read and write YAML. Hence META.yml. Well, I'm not proposing that we completely do away with Build.PL or even with the parameters given to the Module::Build constructor. I'm just saying that we should give a way for programs to give it arguments as well, without having to parse the Perl and try to make sense of it. Yep, that's what the command-line arguments are for. So we have the machine+human-manipulatable input and the data and code in the Build.PL as input to Module::Build. I'm pretty sure you can already do what you want via command-line arguments. If some are not properly passed through, well then you can patch that, that seems reasonable to me. And I could see a case for a Module::Build::Config or something that uses a configuration file to call Build.PL and pass it parameters (See SVN::Notify::Config for an example of a third-party module that uses YAML to replace command-line options to another program). It's entirely possible I'm missing your point, but it sure seems like you can pretty much already do what you want to do, without requiring any new features in Module::Build. But a patch demonstrating what you want would probably be more convincing, in that we could much better understand what it is you want. Best, David
Re: [RESEND] Machine-Manipulatable Arguments for Module::Build
On Aug 2, 2008, at 07:17, Shlomi Fish wrote: http://xrl.us/bi6n9 (link to svn.berlios.de) is a functional spec for a way to tag and classify CPAN modules. Those tags and catgories should end up in the META.yml. However, inserting them by hand by editing the Build.PL will be: You are aware of the keywords param to new(), right? =item keywords For describing the distribution using keyword (or tags) in order to make CPAN.org indexing and search more efficient and useful. See Lhttp://module-build.sourceforge.net/META-spec-current.html#keywords . 1. Error-prone. Why is that? 2. Not capabale of being manipulated by an external program - Only perl can understand Perl, etc.. It looks like M::B does not current put the keywords into the META.yml file when you run `make distmeta`. It ought to. That's where you should start your patch, IMHO. Once the're in the META.yml, any YAML- compliant program can of course read them. Of course, this is not limited to this issue. I've overheard a conversation on a #perl where some people said they'd like to have all the (non-code) parameters to Module::Build be speicified in a YAML format or so. Um, what for? Write a YAML file to be read by M::B to write out META.yml? Seems silly to me. So I've been thinking of having a special file or files for this (or alternatively possibly re-use the __DATA__ section of the Build.PL) in order to specify machine-manipulatable parameters to the Build process. I find Perl easier to type than YAML. YAML is much more error-prone, IMO. Given enough willingness, I'm willing to volunteer the time to implement it in the current version of M::B (and possibly EU::MM and M::I). I suppose it can also be implemented as a user-land wrapper around Module::Build, but would like to get some input first. As a start, all of the keys specified in the META spec should be written to META.yml. Beyond that, well, just know that the Ant folks started out just using XML in their build files, but then needed processing, and so created a Turing-complete XML programming language. James Duncan Davidson has since told me that if he had to do it again, Ant build files would just have been written in Python or Ruby or something, rather than XML. So, let's not try to learn that lesson in reverse, eh? Best, David
Re: Distributing the CPAN
On Apr 1, 2010, at 1:12 PM, Tim Bunce wrote: Yes, I was envisaging something like gitPAN. Though if this took off then moving the tarball-git import logic to the PAUSE server would probably be a good idea. /me stashes these ideas away for PGAN…
