Another view example

Suppose we use the following alternative implementation, a Expression class hierarchy to represent an expression in our AST. Note that Exp is an abstract base class inherited by the classes Number, Operator, Identifer, etc.

class Expression
{
public:

   // This class uses a ``wide'' interface
   virtual int  number() const         = 0;  // returns a number
   virtual const char * ident() const  = 0;  // returns an identifier

   // returns the ith subchild
   virtual const Expression * child(int) const = 0;
   // mutable version of above
   virtual Expression *& child(int) = 0;
};

typedef Expression * Exp;

class NullExp  : public Expression { ... };
class Number   : public Expression { ... };
class Operator : public Expression { ... };
class Identifier : public Expression { ... };

In order to provide a suitable interface to Prop's view mechanism, we introduce an additional member function to return a variant tag:

class Expression
{
public:
   enum Variant { None, Int, Ident, Add, Sub, Mul, Div };
   virtual Variant get_variant() const = 0;
}

In addition, we assume the following constructor functions have been implemented:

extern Exp INT(int);
extern Exp IDENT(const char *);
extern Exp ADD(Exp, Exp);
extern Exp SUB(Exp, Exp);
extern Exp MUL(Exp, Exp);
extern Exp DIV(Exp, Exp);

Now, with these definitions in place, we can define a datatype view of the above Expression hierarchy using the following definition:

datatype Exp :: view
   = match (this->get_variant())
     view Expression::None  => NONE
   | view Expression::Int   => INT (int = this->number())
   | view Expression::Ident => ID  (const char * = this->ident())
   | view Expression::Add   => ADD (Exp = this->child(0),
                                    Exp = this->child(1))
   | view Expression::Sub   => SUB (Exp = this->child(0),
                                    Exp = this->child(1))
   | view Expression::Mul   => MUL (Exp = this->child(0),
                                    Exp = this->child(1))
   | view Expression::Div   => DIV (Exp = this->child(0),
                                    Exp = this->child(1))
   ;

An evaluation function can be written using Prop's pattern matching construct:

int eval(Exp e, const Env& env)
{  match (e)
   {  NONE:          { return 0; }
   |  INT i:         { return i; }
   |  ID id:         { return env(id); }
   |  ADD (x,y):     { return eval(x,env) + eval(y,env); }
   |  SUB (x,y):     { return eval(x,env) - eval(y,env); }
   |  MUL (x,y):     { return eval(x,env) * eval(y,env); }
   |  DIV (x,INT 0): { cerr << "Division by zero"; return 0; }
   |  DIV (x,y):     { return eval(x,env) / eval(y,env); }
   }
}

Note that this code works equally well with the tagged union representation defined in section 7.1.

We can also use rewriting to transform an expression tree as follows

void simplify(Exp& e)
{
   rewrite (e) type (Exp)
   {  ADD(INT i, INT j): INT(i+j)
   |  SUB(INT i, INT j): INT(i-j)
   |  MUL(INT i, INT j): INT(i*j)
   |  DIV(INT i, INT j): INT(i/j)
   }
}