Generative Programming In The Large - Applied C++ meta-programming

ACCU 2007 Generative Programming in the Large Applied meta-programming Schalk W. Cronjé ysb33r@gmail.com

ACCU 2007 Even in this new millennium, many engineers will still build components that have very little reuse potential due to the inflexible way that they were constructed. This leads to excessive time required to adapt a component for usage in another system.

ACCU 2007 The world of modern C++ Generative Programming is a vastly untapped field (we are just scraping the surface)

ACCU 2007 Definition It is a software engineering paradigm where the aim is to automatically manufacture highly customised and optimised intermediate or end-products from elementary, reusable components by means of configuration knowledge. Implies Code Generation Domain-specific language Generic Techniques

ACCU 2007 Elements of Generative Programming Problem space Solution space Configuration Knowledge Illegal feature combinations Default settings & dependencies Construction rules Optimisations Configured ComponentsDomain-specific concepts Features Generic Components

ACCU 2007 Key Code-level Strategy

ACCU 2007 For effective implementation there is one basic principle that encompasses most GP strategies: Dijkstra's Separation of Concerns This principle accepts the fact that we cannot deal with many issues at once and that important issues should be addressed with purpose.

ACCU 2007 Key Code-level Strategies Develop elementary components as generic components Fully testable outside of the intended product configuration Configure these components using generated artefacts appropriate to the programming language Aim for zero cyclomatic-complexity in the generated artefacts Eliminate defects as early as possible

ACCU 2007 In the large ... Generative C++ can lead to large number of configuration classes or meta-classes being generated. It is not uncommon to work with 50+ tag classes within a single type-list Effective integration of meta-programming, compile- time paradigms and run-time paradigms are required. Code-bloat must be avoided!

ACCU 2007 Conventions For the examples assume that the following namespace aliases exist using namespace AccuConf; namespace mpl = AccuConf::mpl; namespace bmpl = boost::mpl; All code are implemented in namespace AccuConf.

ACCU 2007 Building a rule evaluator (as an example of a generative library)

ACCU 2007 Requirement #1: Solve complex boolean statements if (cond_A && cond_B || !cond_C) return outcome_A; else if (cond_D) return outcome_B; else return outcome_C;

ACCU 2007 Requirement #2: Rule-types are defined in a DSL condition_expr: input: IP-address operation: == condition_expr: input: IP-address operation: in_netmask condition_expr: input: Email-address operation: regex_match

ACCU 2007 Requirement #3: Short-circuit // Jump to evaluate !cond_C if (cond_A && !cond_A || !cond_C) // Never evaluate cond_D if( cond_B || !cond_B || cond_D) // Don't evalute cond_A twice if( cond_A || cond_A ) if( cond_A && cond_A )

ACCU 2007 Requirement #4: Compile-time & run-time rules // Hard-code compile-time rule1 = cond_A && cond_B // Loaded at run-time rule2 = load_rule( "ip in FEFE::/64" );

ACCU 2007 Requirement #5: Early enforcment Only allow attribute-operator combinations that have been defined in DSL Only allow attributes to be passed that were defined in DSL

ACCU 2007 The conceptual evaluator Evaluating rules class Evaluator { public: /**Evaluates the rules against a supplied set * of attributes * @param A A collected set of attributes that will * be used as input to the rules. * @return The outcome associated with the rule * that triggered */ Outcome const& resolve( Properties const& A) const; };

ACCU 2007 The conceptual evaluator Adding rules class Evaluator { public: Outcome const& resolve( Properties const& A) const; /**Adds a rule to the rule set * @param O The outcome to return if this rule * triggers * @param N The order of this rule in the ruleset * @param R the rule to add */ void add_rule( Outcome const& O,Order const& N,Rule const& R ); };

ACCU 2007 Idiom #1: Generative Property Bag What does the Properties class look like?

ACCU 2007 Properties class This can be implemented as a heap-based or a stack- based approach. Heap-based: More memory-efficient, only allocate stored attributes. Suffers heap-access penalty. Potential for heap fragmentation. Stack-based: Pre-allocate space for all attributes, even if not used.

ACCU 2007 Heap-based Properties class Use boost::any to provide generic storage Use boost::map to provide conditional storage Index using meta-indexes template <typename GeneratedPropSet> class Properties { public: // To be implemented ... private: typedef std::map< int,boost::any > container_type; container_type m_attrs; };

ACCU 2007 Generated Property Set struct prop { struct ip_addr { typedef IPAddress value_type; typedef to-be-decided valid_matches; }; struct email_addr { typedef std::string value_type; typedef to-be-decided valid_matches; }; typedef boost::mpl::vector< ip_addr, email_addr > valid_attrs; };

ACCU 2007 Setting a Property template <typename GeneratedPropSet> class Properties { public: template <typename P> void set( typename mpl::property_value::type const& ); private: typedef std::map< int,boost::any > container_type; }; Properties<prop> A; A.set< prop::ip_addr >( "192.168.1.1" );

ACCU 2007 Implementing Property::set template <typename GeneratedPropSet> template <typename P> void Properties<GeneratedPropSet>::set( typename mpl::property_value::type const& v_ ) { // Ensure that P is valid ! BOOST_MPL_ASSERT_MSG( (bmpl::contains< typename mpl::valid_properties< GeneratedPropSet >::type,P >::value), THIS_IS_NOT_A_VALID_PROPERTY, (P) ); // Rest to follow ... } Static Assertion provides relatively useful compile-time error if a invalid type is supplied

ACCU 2007 Implementing Property::set template <typename GeneratedPropSet> template <typename P> void Properties<GeneratedPropSet>::set( typename mpl::property_value::type const& v_ ) { // Ensure that P is valid ! BOOST_MPL_ASSERT_MSG( bmpl::contains< typename mpl::valid_properties< GeneratedPropSet >::type,P >::value, THIS_IS_NOT_A_VALID_PROPERTY, (P) ); // Rest to follow ... } boost::mpl::contains is a metapredicate that returns TRUE if P is in the list of valid properties

ACCU 2007 Implementing Property::set template <typename GeneratedPropSet> template <typename P> void Properties<GeneratedPropSet>::set( typename mpl::property_value::type const& v_ ) { // Ensure that P is valid ! BOOST_MPL_ASSERT_MSG( (bmpl::contains< typename mpl::valid_properties< GeneratedPropSet >::type,P >::value), THIS_IS_NOT_A_VALID_PROPERTY, (P) ); // Rest to follow ... } mpl::valid_properties is our own metaclass to extract the MPL sequence of valid property names from GeneratedPropSet

ACCU 2007 Implementing Property::set template <typename GeneratedPropSet> template <typename P> void Properties<GeneratedPropSet>::set( typename mpl::property_value::type const& v_ ) { BOOST_MPL_ASSERT_MSG( ... ); // Find key for map const int pos = mpl::property_pos< GeneratedPropSet, P >::value ; // Rest to follow ... } mpl::property_pos is our own metaclass returning the relative position of a type in a typelist. We use this value as a key into the map. Due to the MPL_ASSERT we can be ensured that this is a valid value.

ACCU 2007 Implementing Property::set template <typename GeneratedPropSet> template <typename P> void Properties<GeneratedPropSet>::set( typename mpl::property_value::type const& v_ ) { BOOST_MPL_ASSERT_MSG( ... ); // Find key for map const int pos = mpl::property_pos< GeneratedPropSet, P >::value ; // Rest to follow ... } Use of 'const int' allows for optimisation at compile-time

ACCU 2007 Implementing Property::set template <typename GeneratedPropSet> template <typename P> void Properties<GeneratedPropSet>::set( typename mpl::property_value::type const& v_ ) { BOOST_MPL_ASSERT_MSG( ... ); const int pos = ... ; // Assign the value typedef typename mpl::property_value::type value_type; m_attrs[pos] = v_; }

ACCU 2007 Implementing Property::set (alternative) template <typename GeneratedPropSet> template <typename P,typename V> void Properties<GeneratedPropSet>::set( V const& v_ ) { BOOST_MPL_ASSERT_MSG( ... ); const int pos = ... ; // Assign the value typedef typename mpl::property_value::type value_type; m_attrs[pos] = value_type(v_); }

ACCU 2007 Getting a Property template <typename GeneratedPropSet> class Properties { public: template <typename P> typename mpl::property_value::type const& get() const; private: typedef std::map< int,boost::any > container_type; }; Properties<prop> A; A.set< prop::ip_addr >( "192.168.1.1" ); std::cout << A.get< prop::ip_addr >( );

ACCU 2007 Implementing Property::get template <typename GeneratedPropSet> template <typename P> typename mpl::property_value::type const& Properties<GeneratedPropSet>::get() const { BOOST_MPL_ASSERT_MSG( ... ); // Find key for map typename container_type::const_iterator itr = m_attrs.find( mpl::property_pos< GeneratedPropSet, P >::value ); // Rest to follow ... } Reusing mpl::property_pos we obtain an iterator to the appropiate property. Note the use of MPL_ASSERT to ensure a valid index value

ACCU 2007 Implementing Property::get template <typename GeneratedPropSet> template <typename P> typename mpl::property_value::type const& Properties<GeneratedPropSet>::get() const { BOOST_MPL_ASSERT_MSG( ... ); ... itr = m_attrs.find( ... ); if( m_attrs.end() == itr ) throw range_error("Property not set"); // Rest to follow ... } Throw an exception if the property is not set. Use Property::is_set predicate if a no_throw check is needed. (is_set implementation left as an exercise)

ACCU 2007 Implementing Property::get template <typename GeneratedPropSet> template <typename P> typename mpl::property_value::type const& Properties<GeneratedPropSet>::get() const { BOOST_MPL_ASSERT_MSG( ... ); ... itr = m_attrs.find( ... ); if( m_attrs.end() == itr ) ... ; typedef typename mpl::property_value::type value_type; return *boost::any_cast<value_type> (&(itr->second)); } We can assume that the type stored is correct. Need to use the & to invoke a non-copy version of any_cast.

ACCU 2007 Idiom #2: GGS Generic-Generated Separation: Access to generated typelists from generic code should go through metaclasses.

ACCU 2007 MPL metaclasses Abstract access to type information through metaclasses This allows for specialisation when needed Improves long-term maintenance

ACCU 2007 Obtaining the value_type template <typename Property> struct property_value { typedef typename Property::value_type type; };

ACCU 2007 Sequence of Valid Properties template <typename Properties> struct valid_properties { typedef typename Properties::valid_properties type; };

ACCU 2007 Property Position template <typename Properties,typename Property> struct valid_properties : bmpl::find< typename valid_properties< Properties>::type, Property >::type::pos { // Prevent invalid Property BOOST_MPL_ASSERT_MSG( bmpl::contains< typename valid_properties< Properties>::type, Property >::value, PROPERTY_NOT_FOUND_IN_SEQUENCE, (Property,Properties) ); };

ACCU 2007 Idiom #3: Visit Each Apply an operation to each generated member

ACCU 2007 Using Boost for_each bmpl::for_each< mpl::valid_properties<Properties>::type >( FUNCTOR() ); struct FUNCTOR { template <typename P> void operator()(P) const; }; For each type in sequence calls the functor

ACCU 2007 Using Boost for_each bmpl::for_each< mpl::valid_properties<Properties>::type >( FUNCTOR() ); struct FUNCTOR { template <typename P> void operator()(P) const; }; Functor must be able to accommodate each type, otherwise compile-error will occur

ACCU 2007 Using Boost for_each struct print_ip { Properties const& p; print_ip(Properties const& p_) : p(p_) {} template <typename P> void operator()(P) const {} void operator()(ip_addr) const {std::cout << p.get<ip_addr>();} }; bmpl::for_each< mpl::valid_properties<Properties>::type >( print_ip(my_properties) );

ACCU 2007 Idiom #4: Type-erasure A known interface irrespective of the types used

ACCU 2007 Rule Evaluation Signature template <typename Properties> bool Functor( Properties const& ); boost::function< bool(Properties const&) >

ACCU 2007 Rule Class template <typename Properties> class Rule { public: // C-tors to follow ... Rule operator || (Rule const&) const; Rule operator && (Rule const&) const; Rule operator !() const; bool operator()(Properties const&) const; private: boost::function< bool(Properties const&) > m_rule; };

ACCU 2007 Rule Class template <typename Properties> class Rule { public: template < typename Property, typename Operand > Rule( Operand<Property> const& op_ ); };

ACCU 2007 Idiom #5: Hekaton Typelist Working around limitations in existing typelist libraries

ACCU 2007 Limitations in Boost MPL sequences Maximum size of template parameter list is implementation-dependant Typically 20 GP might require very long lists 100 types are not uncommon A special type-list might be needed to convert a very long generated list into a standard Boost MPL sequence.

ACCU 2007 Hekaton-typelist template < typename T0 = bmpl::na, typename T1 = bmpl::na, ..., typename T99 = bmpl::na > struct typelist { typedef bmpl::vector<T0,...,T19> _list0; typedef bmpl::vector<T20,...,T39> _list1; typedef bmpl::vector<T40,...,T59> _list2; // etc. // Join lists typedef bmpl::joint_view<_list0,_list1 > _join0; typedef bmpl::joint_view<_join0,_list2 > _join1; //etc. // until the last join which becomes typedef to-be-defined type; };

ACCU 2007 Hekaton-typelist (detail) namespace detail { template < typename V0 = bmpl::vector<>, typename V1 = bmpl::vector<>, ..., typename V9 = bmpl::vector<> > struct typelist { // detail to follow ... }; } // namespace detail

ACCU 2007 Hekaton-typelist (detail) namespace detail { #define P_LIST(z,n,t) BOOST_PP_COMMA_IF(n) typename V##n = t template < BOOST_PP_REPEAT(10,P_LIST,bmpl::vector<>) > struct typelist { // detail to follow ... }; #undef P_LIST } // namespace detail

ACCU 2007 Hekaton-typelist (detail) namespace detail { #define P_LIST(z,n,t) BOOST_PP_COMMA_IF(n) typename V##n = t template < BOOST_PP_REPEAT(10,P_LIST,bmpl::vector<>) > struct typelist { typedef bmpl::joint_view<_V0,_V1 > _join0; typedef bmpl::joint_view<_join0,V2 > _join1; //etc. until the last join which becomes typedef bmpl::joint_view<_join8,V9 > type; }; #undef P_LIST } // namespace detail

ACCU 2007 Hekaton-typelist (final) #define P_LIST1(z,n,t) BOOST_PP_COMMA_IF(n) typename T##n = t #define P_LIST2(z,n,t) BOOST_PP_COMMA_IF(n) t##n #define P_LIST3(z,n,t) BOOST_PP_COMMA_IF(n) t < BOOST_PP_REPEAT_FROM_TO( BOOST_PP_MUL(n,20), BOOST_PP_ADD(BOOST_PP_MUL(n,20),20), P_LIST2,T ) > template < BOOST_PP_REPEAT( 100,P_LIST1,bmpl::na ) > struct typelist : detail::typelist< BOOST_PP_REPEAT( 5,P_LIST3, bmpl::vector ) > ::type {}; #undef P_LIST1 #undef P_LIST2 #undef P_LIST3

ACCU 2007 Idiom #6: Discriminant Union from Typelist boost::make_variant_over

ACCU 2007 Discriminant Union typedef mpl::valid_properties<prop>::type example_typelist; typedef boost::make_variant_over< example_typelist >::type example_variant; X

ACCU 2007 Discriminant Union struct extract_value_type { template <typename T> : mpl::property_value<T> struct apply {}; }; typedef boost::transform_view< mpl::valid_properties<prop>::type, extract_value_type >::type example_typelist typedef boost::make_variant_over< example_typelist >::type example_variant;

ACCU 2007 Implementation Specifics

ACCU 2007 Compiler Limitations Few compilers can handle the deep level of template instantiation very well gcc 4.x is fast VC 8 (VS2005) is adequate gcc 3.x is slow and has big memory footprint It is not always possible to use the puristic template solution Use the Boost Preprocessor Library Generate code of higher levels of cyclomatic- complexity

ACCU 2007 Touching the void Pushing C++ skills far beyond the knowledge of many C++ practitioners Politics of introducing a new technology Teaches very good software skills outside the C++ domain Am I in the wrong language? (Yeah, thanks Kevlin!) Shows requirements for future languages Powerful syntax Simplicity of expression

Generative Programming In The Large - Applied C++ meta-programming

More Related Content

What's hot

Viewers also liked

Similar to Generative Programming In The Large - Applied C++ meta-programming

More from Schalk Cronjé

Generative Programming In The Large - Applied C++ meta-programming

Editor's Notes