Re: [boost] Re: dynamic inheritance with FC++

From: Brian McNamara (lorgon_at_[hidden])
Date: 2004-02-28 19:29:09

On Sat, Feb 28, 2004 at 09:38:26AM -0600, Larry Evans wrote:
...
> OK, YAT (Yet Another Thing), the tree<B> virtual functions
> must be able to treat their children in the tree as tree<B>
> instances also.
...

Ok, now I think I understand what you want.

I don't understand the regexp domain well enough, so I'll present an
example from a different domain and show how I would do it.  The domain
is compilers; and I have a tree to represent expressions, and then
later decorate the tree with types.

For simplicity there are just two kinds of expressions: BinOps and Vars.
There are just 3 operators (+,<,==) and two types (int,bool).

The class "Expr" is the interface for the AST; it has a virtual
to_string() method so that any expression can be printed.  E_BinOp and
E_Var are concrete derived classes.

The class "TExpr" extends the "Expr" interface with a virtual type()
method.  T_BinOp and T_Var are the concrete subclasses.

The program below creates an Expr tree, and then overlays it with a
TExpr tree.  The pointers only go "one way"; after adding the type
information, you can only "see" all the information by starting at the
root of the TExpr tree.  The Expr tree remains unchanged, and the TExpr
nodes have pointers to the corresponding Expr nodes, and delegate the
Expr interface methods.  The delegation is done "manually".

As a result, an expression like "x+y" ends up being represented by a
data structure that looks something like this:

       Expr tree           TExpr tree
          + <----------------- .
         / \                  / \
        /   \                /   \
       x_    y_            int   int
       |\    |\_____________/_____/
         \_________________/

where the tree on the right contains only the "added data" as well as
pointers to the corresponding nodes of the original tree.

I happened to use FC++ and a fold_tree method in my implementation, but
you could just as well use the visitor pattern instead.

There are really no "clever tricks" here; I just represented what it
seems like you want.  Lemme know if the idea or the code needs any
explaining, or if there are capabilities you need that still aren't
addressed.

#include <string>
using std::string;
#include <iostream>
using std::cout;
using std::endl;

#define BOOST_FCPP_ENABLE_LAMBDA
#include "prelude.hpp"
using namespace boost::fcpp;

//////////////////////////////////////////////////////////////////////

struct Expr {
   virtual string to_string() const = 0;
   virtual ~Expr() {}
};

// Assume just three ops
typedef enum { PLUS, LESS, EQ } Op;

struct E_BinOp : Expr {
   Op op;
   Expr* left;
   Expr* right;

   E_BinOp( Op o, Expr* l, Expr* r ) : op(o), left(l), right(r) {}
   string to_string() const { 
      return left->to_string() 
         + (op==PLUS ? "+" : (op==LESS ? "<" : "==")) 
         + right->to_string();
   }
};

struct E_Var : Expr {
   string name;

   E_Var( string n ) : name(n) {}
   string to_string() const      { return name; }
};

//////////////////////////////////////////////////////////////////////

// effectively the FP version of Visitor; you could use a visitor
// instead if you prefer
struct FoldExpr {
   template <class E, class B, class V> struct sig : fun_type<
      typename RT<V,E_Var*>::result_type> {};
   template <class BOF, class VF>
   typename sig<Expr*,BOF,VF>::result_type
   operator()( Expr* e, const BOF& bof, const VF& vf ) const {
      if( E_BinOp* x = dynamic_cast<E_BinOp*>(e) ) {
         return bof( x, (*this)(x->left,bof,vf), (*this)(x->right,bof,vf) );
      }
      else if( E_Var* x = dynamic_cast<E_Var*>(e) ) {
         return vf( x );
      }
      else throw "bad";
   }
};
typedef full3<FoldExpr> fold_expr_type;
fold_expr_type fold_expr;

//////////////////////////////////////////////////////////////////////

// Assume just two types
typedef enum { T_INT, T_BOOL } VarType;

struct TExpr : Expr {
   virtual VarType type() const = 0;
};
   
struct T_BinOp : TExpr {
   E_BinOp* expr;
   TExpr* left;
   TExpr* right;

   T_BinOp( E_BinOp* e, TExpr* l, TExpr* r ) : expr(e), left(l), right(r) {}
   string to_string() const      { return expr->to_string(); }
   VarType type() const          { return expr->op==PLUS ? T_INT : T_BOOL; }
};

struct T_Var : TExpr {
   E_Var* expr;
   VarType ty;

   T_Var( E_Var* e, VarType t ) : expr(e), ty(t) {}
   string to_string() const   { return expr->to_string(); }
   VarType type() const       { return ty; }
};

//////////////////////////////////////////////////////////////////////

// assume vars whose names start with 'b' are bools, all else ints
VarType var_type( E_Var* v ) {
   if( v->name[0] == 'b' )
      return T_BOOL;
   return T_INT;
}

//////////////////////////////////////////////////////////////////////

int main() {
   Expr* exp2( new E_BinOp( PLUS, new E_Var("x"), new E_Var("y") ) );
   Expr* exp1( new E_BinOp( LESS, exp2, new E_Var("z") ) );
   Expr* exp( new E_BinOp( EQ, exp1, new E_Var("b") ) );
   // exp: ((x+y)<z) == b
   cout << exp->to_string() << endl;

   lambda_var<1> X;
   TExpr* texp = fold_expr( exp, new3<T_BinOp>(), 
      lambda(X)[ construct1<TExpr*>()[ 
                 new2<T_Var>()[ X, ptr_to_fun(&var_type)[X] ] ] ] );
   cout << texp->to_string() << endl;
   cout << (texp->type()==T_INT ? "int" : "bool") << endl;
}

-- 
-Brian McNamara (lorgon_at_[hidden])