Re: [boost] Re: Experiment in Automata syntax

From: Vladimir Prus (ghost_at_[hidden])
Date: 2001-06-26 08:52:03

On Friday 22 June 2001 01:59, vincent.lemaout_at_[hidden] wrote:
> Hi,
>
> D. Revuz and I have been working on ASTL and we sure would be pleased
> if the
> library could benefit from remarks, works and enhancements from you
> all (there is still so much do be done).
[snip]
> > I have two points:
> > 1) I'm a little concerned about q0.set_initial(). In your
> > dfa_state_handle both pointer to dfa and state index is stored.
> > How extra memory consumption due to dfa pointer will affect
>
> performace?
>
> > Is alternative implementation possible? Maybe, DFA::state should
>
> have no
>
> > operations at all?
>
> That's the design decision we took from the start. We met no specific
> problems with it that could make us change our mind. In fact, there is
> no point in making a state a "complex" object. 

I agree. 

[snip cursors overview]
> The interesting thing here is that you can write adapters performing
> any operation
> "on-the-fly" during the traversal. For instance intersection :
>
> template <class Cursor1, class Cursor2>
> class intersection_cursor

Well, this example is cursors' trump card. And, maybe, one can create real 
DFA from intersection cursor with 'ccopy' algorithm? That would be rather 
elegant way of computing automata intersection.

> > 2) I never thought about trap() state. Are complete automatons used
>
> often
>
> > enough to justify special method for their support?. Even if they
>
> are
>
> > usefull, they are likely to demand considerably more memory.

> This is what I call the sink state, if I get it right. The behavior of
> the cursor
> makes virtually all automata complete with undefined transitions
> directed to the sink, most of the time the handler 0 which does not
> mean they are actually stored in the structure. Let's call them sink
> transitions.

The question is: if "default" transitions are used by delta1, should they be 
listed in delta2? I think no. Would such difference make sense?

> > > Acceptors are output iterators that apply the symbols output
> > I find that acceptors are really usefull.
> I agree. Not far from the cursors, just a matter of interface. 

Right, no far. Acceptor can be easily implemented in terms of cursor, but it 
present a slightly more high-level interface. Especially important are 
visitors.

> > As a closing remark, I'd like to say that I will like automata library to 
> > be created. The simplest way would be through enhancing ASTL, if
> > its authors are still willing to boostify it 
> > [snip]

> Yes, I think cursors are good concepts we should investigate further
> and there couldn't be any reason not to "boostify" it :-)

Good. So I think interested persons can start giving comments. Here's my 
attempt.

1. Interface. 
Rather good already, but
        i) Adding tag to transition may be reasonable. (Consider, e.g. example
         of creating Mealy machine that Douglas Gregor gives).
        ii) I would prefer if all member names were fully spelled, ---
        delete_transition instead del_trans, &c. (Just personal opinion, of cause).

2. Portability. 
Should be increased. (bcc doesn't compiles it for sure). Probably, ASTL can 
benefit from boost/config.hpp --- at the moment there are some #ifdef WIN32, 
which are intended to catch VC only.

3.  Algorithms.
Should be more of them. E.g. I would like to see Hopcroft's minimization 
algorithm and isomorphism algorithm. Fortunately, new algorithm can be 
plugged as they are written, so this issue is not very important.

-- 
Regards,
Vladimir