[boost] Re: FSM review

From: Jonathan Turkanis (technews_at_[hidden])
Date: 2005-03-10 11:22:23

Andreas Huber wrote:
> Hi Jonathan
>
> Thanks for your review!

I'm sorry it was not more positive.

> It seems that at least one of your doubts/questions I have already
> answered elsewhere, especially:
>
>> The explanation of why the performance difference shouldn't matter is
>> also unconvincing. I'm particularly disturbed by the implication that
>> FMSs should not be used for parsing. Why not? I have a candidate
>
> http://article.gmane.org/gmane.comp.lib.boost.devel/119246

Sorry I missed this. I think I missed the whole message.

> Let me know whether that's convincing or not.

Okay. Let me see if I understand you correctly:

Andreas Huber wrote:
> ... What I want to say here
> is that it is a bad idea to use this library for parsing, as it is so
> general that performance tradeoffs are inevitable.

This seems to be a restatement of the performance vs. scalability part of the
rationale, correct?

> For parsing, one
> is much better off with a parser framework, which is optimized for
> the task.

> The IMO important observation is the following: Parsers
> like Spirit only need to return when they have finished processing
> all "events" (characters). An FSM however must return after
> processing each event.  can exploit this fact and store state
> with recursive calls, which is of course much faster (some stuff can
> even be inlined) than any super-clever double-dispatch scheme.
> There is often a hard limit for stack space which - I think - is the
> reason why FSMs do make sense in parsers nevertheless.

Here are you talking about any FSM framework or about your library in
particular? At any rate, I don't understand why recursion is more efficient.

In the case I mentioned -- non-blocking filters -- there is a strong resemblence
with FSMs because the filter may be interrupted at any point during its
processing if input is temporarily unavailable or if output buffers are full.
Filter writers must categorize the various points at which the filtering
algorithm might be interupted and save this information so that when processing
begins again the algorithm can continue correctly. These categories correspond
to states. Furthermore, there is often auxilliary information that must be
stored; e.g., if a filter was interupted after it had consumed a character but
before it could pass it downstream, the character must be stored together with
the state. This auxilliary information varies from state to state; it would
therefore seem to correspond to state-local storage.

> However, all
> the FSM-employing parsers I know are of the dynamic variant (e.g.
> regex) and these FSMs are not directly designed by humans but
> computed by an algorithm.

I don't see the relevance of this.

> Last but not least I think it would be
> tedious for a human to implement a parser on the state- level

It's also tedious to write a non-blocking filter by hand; being able to use FSMs
could help bring some order to the chaos.

> At the moment, I don't
> have time to answer your other points.

Okay.

> Regards,

Jonathan