Re: [boost] Interest in DSL framework

From: Andreas Pokorny (andreas.pokorny_at_[hidden])
Date: 2006-08-07 17:58:51

On Mon, Aug 07, 2006 at 07:47:43AM +0800, Joel de Guzman <joel_at_[hidden]> wrote:
> To be honest, right now, for Spirit-2, I am inclined to use Eric's
> proto. It's been there for quite some time now and is quite mature.
> But, like your library, there are no docs yet (as far as I know).
> I'm not sure when Eric will have the time to get it outside xpressive
> as a standalone ET library, for review. At any rate, it would be
> interesting if you can form a collaboration with him. So, instead
> of having 2 separate ET entries, we can just have one that has the
> the best of both. Is that possible at all? Or is your library too
> different from Proto?

The whole thing was derived from proto, I changed some type names. Added
a rule system. Then the domain_tag used for rule set dispatching, and
finally the fusion-2 map to support attributes.
With the attributes a DSL can be defined as a S-attributed grammar.

There is yet another feature I havent mentioned yet. It is also possible
to extend existing grammars. In a way that all existing rules are reused
if no rule of the derived domain matches. This might help you defining
the differences of xpressive spirit and karma. 

I think it is time to explain how the system works: 

Some helper strucutures required to explain the system:

struct defined {}; //< used to mark a rule as 'defined', required for
                   // domain extension/reuse
sturct undefined{}; //< the opposite, rules marked with undefined do not apply in a domain
                    // the default implementation of rule metafunctions
                    // are marked as undefined 

template<typename DomainTag>  
struct extends { typedef mpl::void_ type; };
// Usage:
// A extends B   ==>  template<> struct extends<A> { typedef B type; };

Rules:
----------

Rules are boolean metafunction with an additional return type called
'result_type' and a static init-member function which only returns a 
value of result_type. 

The default rule:

template <typename DomainTag,typename OperatorTag,typename LeftType,
          typename RightType = void,typename EnableIfT = void >
struct rule : undefined,mpl::false_ 
{
};
 
The first parameter identifies the domain, the rule will be used for.
The OperatorTag is just like in proto, a type_tag to identifiy operators
or functions. LeftType and RightType just hold the operand types of the 
expression. RightType stays void if OperatorTag is an unary operator. 

As you can see the system would also benefit from variadic templates. I
considered having rule_1 rule_2 rule_3 .. for unary binary
operators/functions, and rule_3 for functions with three parameters. 
The rule template above only works for unary and binary
functions/operators. This is one of the interface changes I planed 
for the near future. 

Domains: 
--------- 

To define a domain a domain_tag has to be created: 
struct linear_algebra_domain_tag{};

In linear algebra there are several elementwise operations like add and 
subtract that only work on objects of equal dimensions. To capture 
all these operations in a single rule and with the help of traits, we 
have to write this rule specialisation:

template<typename OperatorTag,typename LeftType,typename RightType>
struct rule<linear_algebra_domain_tag,OperatorTag,LeftType,RightType,
  typename enable_if<
    mpl::and_<
        math_lib::requires_equal_dimension<OperatorTag>
            , math_lib::have_equal_dimension<LeftType,RightType>
        >   
      >::type > : defined,mpl::true_
{              
  typedef /* omitted */ result_type;
  static result_type init( LeftType const& left, RightType const& right ) 
  { return ....; }
};

Note that we now derive from defined, to tell the rule system that this 
rule has to be applied, if the template parameter substition succeeded.
The mpl::true_ is the boolean response of the metafunction, telling the 
rule system that the expression is valid. 

A domain is defined by a set of rules. Attributes are somehow outside 
of domains, but can and should be used for validity check tests in rules. 
But there is no coupling between a certain domain or a set of rules and the 
attributes. 

The code of have_equal_dimension accesses the dimension attribute of the 
two operand types. 

Operators and rule invocation:
------------------------------

The framework already provides overloads for all operators, and provides
a macro to define additional functions which also invoke the rule system. 

This is simple defintion of operator+: 

template<typename LeftT, typename RightT>
inline typename lazy_enable_if<
  mpl::and_< \
    is_expression<LeftT> 
    , is_expression<RightT>
    , is_binary_expression_allowed<add_tag,LeftT,RightT>
    >
 , get_result_type<add_tag,LeftT,RightT>
 >::type
operator +( LeftT const& left, RightT const& right ) 
{
  return get_rule<add_tag,LeftT,RightT>::type::init(  left, right );
}

With the adaptation of foreign types, the operator overload becomes 
a little more complex. 

is_binary_expression_allowed calls get_rule<..>::type, which does all the work. 
In get_rule<OP,L,R> the domain_tag attributes of the left and right
operand type are accessed. If the domain_tag types differ a user
sepcializeable meta function is called to resolve the conflict. 

With the final domain_tag a metafunction get_rule_impl is invoked: 
template<typename DomainTag, typename Op,typename L, typename R>
struct get_rule_impl
  : lazy_if<

      mpl::or_<
        is_defined<rule<DomainTag,Op,L,R> >             // returns true if the instantiated rule derives from defined. 
        , is_same<typename extends<DomainTag>::type,mpl::void_> 
      > 

      // then:
      , lazy<rule<DomainTag,Op,L,R> >                   

      // else:
      , get_rule_impl<typename extends<DomainTag>::type,Op,L,R>
     >
{};

This code recusively walks through all rules until a 'defined' rule, 
or no further extended domain is found. 

I hope this sheds enough light onto the rule system.
There are two further topics to cover the expression tree encoding 
and the attributes. 

Expression Encoding: 
---------------------

template<typename AttributeMapType>
struct basic_expression : expression_node                 // expression_node is used inside of is_expression<T> from above
{
  typedef AttributeMapType attribute_map_type;
  typedef AttributeMapType tuple_type;

  tuple_type attributes;

  basic_expression( tuple_type const& t )
    : attributes(t)
   {}
}; 

template<typename L,typename L, typename AttributeMapType>
struct binary_expression : basic_expression<AttributeMapType>
{
  typedef typename call_traits<L>::value_type left_operand_type;
  typedef typename call_traits<L>::value_type right_operand_type;
  typedef AttributeMapType tuple_type;

  left_operand_type left_operand;
  right_operand_type right_operand;

  binary_expression( L const& lop, R const& rop, tuple_type const& t )
    : basic_expression<AttributeMapType>(t)
      , left_operand( lop )
      , right_operand( rop )
  {}
};

// similar code for unary_expression .. 

Right now three structure templates are available to encode nodes
in the expression tree. From my current point of view the first one
should be sufficient, since all other information can be stored 
in the attribute map. 

The information stored in attributes of the operands can be updated 
and forwared to expression encoding type by calling user defined 
update/combine Metafunction. 

I think thats enough for this email at least. I hope I find more 
time to write tomorrow

Best Regards
Andreas Pokorny