[boost] [proto]emulation of homomorphisms in hierarchical algebras (was in spirit-devl list

From: Larry Evans (cppljevans_at_[hidden])
Date: 2007-06-27 14:57:47

As Eric suggested below, this has been moved from spirit-devel at:

http://thread.gmane.org/gmane.comp.parsers.spirit.devel/3200/focus=3211

On 06/25/2007 04:53 PM, Eric Niebler wrote:
 > (This seems to be drifting off-topic for this Spirit-devel list. Perhaps
 > we should move this discussion to the boost list.)
 >
[snip]
 > Of course, ET transforms are not purely compile-time, or at least, they
 > don't have to be. They can have a run-time counterpart, too. I've added
 > some examples recently to demonstrate this. Have a look at the
 > CountLeaves transform at http://tinyurl.com/2qme82 for an example that
 > uses std::plus to accumulate a runtime value.

Thanks Eric. I'll have a look.

 >
 >
 >    However, I just thought I'd try and see if the
 >> lookaheaads could be calculated a compile time.  That's what I
 >> attempted in:
 >>
 >>    <boost-vault>/Strings - Text Proccesing/gram_lookahead.zip
 >>
 >> As the comments indicate, it's not completed.  I ran against a problem
 >> with the first/follow attributes which is, I think, related to proto's
 >> terminals.  If you recall, about a week or month ago, there was some
 >> discussion about the arity of proto terminals.  You decided to change
 >> the arity to 0.  This was good because it was consistent with the way
 >> algebra's and their morphisms are defined.  However, in the case of
 >> gram_lookahead.zip, this lead to the aforementioned problem with
 >> first/follow calculation.
 >
 >
 > Which problem?
 >

The problem involves my attempt to model the lookahead problem
as an algebra problem whose solution involved the following steps.

   1) For a grammar expression, e_gram, (a "source" algebra expression)
      perform a homomorphism, gram2X. to a corresponding target
      algebra, X, expression, e_X, where X is one of {empty,first,follow}.

      For example,

        gram2empty(inp | epsilon) =
          not_empty & yes_empty

      where inp is any element in the terminals of the grammar and
      epsilon is, of course, the epsilon expression representing the
      empty string.

   2) Perform a sequence of reductions, based on "laws" of the target
      algebra, until a  "constant" in the target algebra is reached.

      For example, some of the "laws" of the empty algebra are:

        not_empty & e_empty   -reduce-> not_empty
        e_empty   & not_empty -reduce-> not_empty

      where e_empty means any expression in the empty algebra.  Based
      on this, and the example expression in 1):

          not_empty & yes_empty -reduce-> not_empty

      And not_empty is a "constant" in the empty algebra; do, the
      sequence of reductions is complete.

Now, IIUC, a homomorphism maps functions with arity, n, in the source
to functions with arity n in the target.  Thus | in the gram algebra
was mapped to & in empty algebra.  If n = 0, this means constants in
the source are mapped to cconstants in the target.  For example, in
the above example, inp_0, a constant in gram algebra was mapped to
not_empty, a constant in the empty algebra.  However, for gram2first,
things aren't that simple.  The constants in the first algebra are
*sets* of constants in the gram algebra. More concretely:

   1) homomorphism: gram2first

     1.1) constants:

       gram2first(inp_0) = {inp_0}
       gram2first(inp_1) = {inp_1}
       ...
       gram2first(inp_n) = {inp_n}

       where n is the number of terminal symbols in the grammar.

     1.2) binary |:

       gram2first(|) = \/
         where \/ is set union operator or function.

       gram2first(e_gram_0 | e_gram_1)
       = gram2first(e_gram_0) \/ gram2first(e_gram_0)

However, {inp_0} and {inp_1} and ... {inp_n} are not really a
constants in the first grammar.  Instead they are really
composite terms or expressions in a multisorted set algebra with the
single constant, empty_set, and binary function, insert:

      insert(empty_set,inp_0)
      insert(empty_set,inp_1)
      ...
      insert(empty_set,inp_n)

and this is what lead me to look for something like the hierarchical
algebra, which, I guess, is similar to the "hierarchical abstract
type" in (6) here:

   http://tinyurl.com/ypekyd

The type, P, in the above tinyurl corresponds to the multisorted set
algebra mentioned above, and insert(empty_set,inp_0) would be an
example of the "primitive term" mentioned in the tinyurl.

 >
 >    In gram_lookahead.zip, the morphisms
 >> cannot proceed down the expression tree after a node with arity==0 is
 >> reached.
 >
 >
 > Huh, there is nothing "down" after a node with arity 0. That's all you
 > get. :-)
 >

The above definition of homomorphism mapped constants (functions with
arith=0) to constants.  However, in the case of gram2first, the
mapping was from constants to some term in the primitive subalgebra of
the target algebra (I don't even know if that's been defined
somewhere, but I'd be very surprised if there were'nt some reference
somewhere defining the idea). So instead of mapping constants to
constants, in proto I'd be mapping arity-0 terms to arity-0 terms;
however, the contents of those target arity-0 terms would be the
primitive subalgebra terms; hence, there would be a "down" to get at
the subalgebra term (in this case, probably implemented as
mpl::set<GrammarTerminalNumeral,TermNum>).

 >
 >   However, with the first and follow algebra, the terminal
 >> values are not single values like true or false, but instead multiple
 >> values like {ident,value,lpar} (e.g. the first attribute of factor
 >> nonterminal in arith_expression grammar).
 >
 >
 > OK, so your terminal is a 3-tuple. It's still a terminal.
 >

Yes, but also a composite term in the primitive subalgebra.  Your
probably wondering why I'm so fixated on using the algebra concepts
and I'm beginning to wonder myself ;) .  However, my original intent
was to try and be more formal and possibly gain some insight about how
to do it other ways.

 >
 >    So, the reduction of values
 >> in this grammar must continue through the value contained in the proto
 >> terminal (which is an instance of mpl::set on grammar terminals, like
 >> ident, value, or lpar).
 >
 >
 > I don't think you need proto to "recurse" into your terminals. I just
 > think you need to write a custom transform that does something
 > appropriate with your terminals.
 >

OK, you're probably right and the attempt at formality is not worth
the effort.

 >
 >    This lead me to search for something in
 >> algebra literature to handle this, and that lead to something called
 >> "heirarchical albebras" where the arity-0 expressions are actually
 >> values in some other algebra (if I'm interpresting things correctly).
 >> This sounds like what I was looking for.  I would be interesting if
 >> the transforms in proto actually were more like heirarchical algebra
 >> morphisms. Just something to think about (probably in the distant
 >> future ;) ).
 >
 >
 > Well, that's one approach. In fact, you can approximate that in proto
 > today by wrapping a proto expression in a template, effectively hiding
 > its proto-ness from proto, which would then treat it like any other
 > terminal. You would be responsible for writing the transforms and/or
 > contexts that knew about these special terminals and recursed into them.
 >
 >

OK, now you've inspired me to continue trying.

Thanks for the feedback!

-regards,
Larry