Boost logo

Boost :

From: Chris Russell (cdr_at_[hidden])
Date: 2003-06-08 08:34:25


Hi Andreas,

I've taken the liberty of starting a new thread to talk about these
inter-FSM protocol issues as they don't related directly to your current FSM
lib submission.

For the benefit of people cruising the archives at a later date, this
conversation derives from this exchange:
http://news.gmane.org/onethread.php?group=gmane.comp.lib.boost.devel&root=%3Cbbjf53%24448%241%40main.gmane.org%3E

---
After posting http://article.gmane.org/gmane.comp.lib.boost.devel/20971
(suggests that inter-FSM protocols need some sort of semantic concept
checking that depends on metadata that characterizes the FSM's between which
the protocol is being established), it occurred to me that all but the
simplest protocols themselves depend on a FSM mechanism...
So let me take another shot at it:
Related to concept checking (references: Category theory [1], and Morphisms
[2]):
"A category is given by two pieces of data: a class of objects and, for any
two objects X and Y, a set of morphisms from X to Y."
What I was trying to suggest is that the objects in the category are FSM's,
and the set of morphisms defined for any two FSM's X and Y is a concept that
needs to be checked. Speaking as a layman, and not a discrete math theorist,
at first glimpse it would seem reasonable to think that the various flavors
of morphism might provide us with a nomenclature for describing the set(s)
of inter-FSM event exchanges that a protocol could legally define without
violating the semantics of any of the FSM objects in the category.
After thinking about it a little more and realizing that all but the
simplest protocols are themselves based on some sort of FSM mechanism, maybe
what we need is boost::fsm + boost::morphism to deal formally with protocols
at a high-level. Totally shooting from the hip, we might for example
consider codifying a concept hierarchy for the various flavors of morphisms
(see p.151 of the BGL book or
http://www.boost.org/libs/graph/doc/graph_concepts.html for an inspirational
example). Climbing further out on the limb, such a library might leverage
boost::property_map to aggregate the FSM's in a category (value_type ==
event source/sink metadata), and the actual morphism concept would be
defined as a set of references into the property_map that performs concept
check via boost::concept_check, and perhaps (wild speculation alert)
generation of the code to actually implement the morphism mapping (i.e.
wiring FSM event sources/sinks) via boost::mpl? This would provide
compile-time concept checking and theoretically make it possible to design
protocols at a very high-level of abstraction and leave the messy wiring to
the C++ compiler (starts to blur the line between functional and imperative
which is a good thing).
I'm certain I've overlooked some important considerations. Viscerally, it
feels like the right light to stumble towards though. Comments?
- Chris
Category theory entry on Wikipedia
[1] http://www.wikipedia.org/wiki/Category_theory
Morphism entry on Wikipedia
[2] http://www.wikipedia.org/wiki/Morphism
>
> Ok, I see that concept checking could be helpful...
>
> > I've been staring at the Wikipedia sections on Morphisms [1] and Group
> > Theory [2] looking for a suitable nomenclature for describing these
> > protocol concepts. Basically my idea is that the actual protocol
> > would formally specify what flavor of *morphism it's attempting to
> > establish and use information from FSM's in the group to determine if
> > such a mapping is possible (the concept check) and if so, affect the
> > mapping generically somehow (i.e. the protocol itself doesn't
> > get involved with event types and data semantics directly). Unclear
> > to me if this is done at compile time, runtime, or <gasp> both...
> >
> > What do you guys think of these ideas?
>
> Errr, while I got what a group is I don't really get what a *morphism is.
> The description is too formal for me and the examples don't help either.
> Moreover, I also fail to see the connection between groups and FSMs. Have
I
> been drinking too much lately ;o)?
>
> Regards,
>
> Andreas
>

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk