Re: [boost] lisp similarity? (was Re: [proto]purpose of binary_expr<T, L, R>::type ?

From: Larry Evans (cppljevans_at_[hidden])
Date: 2008-03-23 17:02:19

On 03/22/08 22:12, Eric Niebler wrote:
 > Larry Evans wrote:
[snip]
 >> The following grammar I think summarizes the difference between
 >> grammar and expression:
 >>
 >> expr //describes an expression.
 >>    = terminal
 >>    | expr+
 >>      //i.e. 1 or more expressions (e.g. expr<tag::plus,expr0,expr1>)
 >>    ;

In addition, I wanted some way to tell what's
a valid 1st arg to matches.  The above description of expr is for a
grammar.  Now a valid 1st arg to matches would apply ::type to each
node in the above tree, AFAICT.  At first, I thought of:

   expr_type
      = terminal::type
      | expr_type+
      ;

but that would make:

      ( terminal::type, terminal::type, terminal::type )

a valid expresion when what's needed is:

      ( terminal::type, terminal::type, terminal::type )::type

OK, it's getting too abstract to make it clear; so I'll have to make
it more concrete:

   expr_gram
      = expr<tag::terminal>  //Args argument not included intentionally
      | expr<Tag,expr_gram+>
      ;

and expr_type would have to be a kinda algebraic homomorphism:

   expr_type(expr<tag::terminal>) ->
     expr<tag::terminal>::type;

   expr_type(expr<Tag,expr_gram_1, ... expr_gram_n>) ->
     expr<Tag,expr_type(expr_gram_1), ... expr_type(expr_gram_n)>::type

For example, in the case of

   a_expr_gram == 
expr<tag::shift_right,expr<tag::terminal>,expr<tag::terminal> >

the morphism "trace" would be:

   expr_type(a_expr_gram)
   ->
   expr
   < tag::shift_right
   , expr_type(expr<tag::terminal>)
   , expr_type(expr<tag::terminal>)
   >::type
   ->
   expr
   < tag::shift_right
   , expr<tag::terminal>::type
   , expr<tag::terminal>::type
   >::type

The definition of algebraic homomorphism I'm using is at planetmath:

http://planetmath.org/encyclopedia/HomomorphismBetweenAlgebraicSystems.html

The planetmath f corresponds to above the expr_type.  The planetmath
operators, w_A and w_B, correspond to the above expr<Tag, ...> and
expr<Tag, ...>::type, respectively.

Is that about right?

Also, I've got the feeling that the pass_through transform is similar
to a homomorphism.  Is that about right?