next up previous contents index
Next: Another view example Up: User defined datatypes: Previous: User defined datatypes:

A first example

 . To illustrate the use of views, we'll begin with a simple example.

Suppose in our application we use the following tagged C union to represent our expression datatype. An expression is represented simply as a pointer to this structure. An null expression is represented simply as the NULL pointer.

enum exp_tag { Int = 1, Ident, Add, Sub, Mul, Div };
struct exp {
   enum exp_tag tag;
   union {
      int          number;
      const char * ident;
      struct { struct exp * l, * r } children;
   } u;
};
typedef struct exp * Exp;
/* User defined constructor functions */
Exp NONE = NULL;
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);

Suppose this data structure is already used extensively in other modules, and we'd like to Prop pattern matching mechanisms while keeping the old code intact. We can accomplish this by declaring a view to this data structure, using a datatype view  definition:

dataype Exp :: view =
   match (this ? this->tag : 0)
     view 0     => NONE
   | view Int   => INT(int = this->u.number)
   | view Ident => ID (const char * = this->u.ident)
   | view Add   => ADD(Exp = this->u.children.l, Exp = this->u.children.r)
   | view Sub   => SUB(Exp = this->u.children.l, Exp = this->u.children.r)
   | view Mul   => MUL(Exp = this->u.children.l, Exp = this->u.children.r)
   | view Div   => DIV(Exp = this->u.children.l, Exp = this->u.children.r)
   ;

In the above, a view named Exp is defined. Let's describe what the definition means: in general, a view definition has three main parts, the view selector, a set of view transformation rules, and a set of view accessor expressions. These parts perform the following tasks:

View selector
The view selector is specified in the the match  part of the definition. In this example, the expression associated with match is this ? 0 : this->tag. This returns a variant discrimination integer from 0 to Div. Note that the pseudo variable this  refers to an object of type Exp.

View transformation rules
Each of the clauses
    view exp => term
specifies a view transformation rule. These rules are used to specify how to transform a computed variant tag into a pattern. In general, expression exp must be a constant expression usable in a case statement.

View accessors
In each of the constructor arguments, an view accessor expression can be defined to access the logical components of the constructor. In the rule:
   | view Add   => ADD(Exp = this->u.children.l, Exp = this->u.children.r)

The expressions this->u.children.l and this->u.children.r tell Prop how to access the left and right child of the an addition expression node.

Note that since the variant NONE has no arguments, it is represented as a nullary constructor, and no accessors expressions are defined.

A pretty printing function for struct exp can be implemented in Prop using pattern matching as follows:

ostream& operator << (ostream& s, Exp e)
{  match (e)
   {  NONE:     { s << "none"; }
   |  INT i:    { s << i; }
   |  ID id:    { s << id; }
   |  ADD(a,b): { s << '(' << a << " + " << b << '); }
   |  SUB(a,b): { s << '(' << a << " - " << b << '); }
   |  MUL(a,b): { s << '(' << a << " * " << b << '); }
   |  DIV(a,b): { s << '(' << a << " / " << b << '); }
   }
   return s;
}

Note that this is exactly the same code we would've written if Exp is defined as a datatype rather than a view. This means that the user can reimplement the expression data structure as a Prop's datatype at a latter time, without altering the Prop source code. In effect, the logical view of a datatype, and its physical implementation can separately. With this representation transparency capability, programs written in Prop's pattern matching formalisms can evolve in an incrementally and pain-free manner.

The generated code for the above function will resemble the following output. Note that all the view selectors and view accessors are inlined into the code, and in general, views incur no overhead to their use.

ostream& operator << (ostream& s, Exp e)
{  switch (e ? e->tag : 0)
   {  case 0:      { s << "none"; }
      case Int:    { s << e->u.number; }
      case Ident:  { s << e->u.ident; }
      case Add:    { s << '(' << e->u.children.l
                       << " + " << e->children.r << '); }
      case Sub:    { s << '(' << e->u.children.l
                       << " - " << e->children.r << '); }
      case Mul:    { s << '(' << e->u.children.l
                       << " * " << e->children.r << '); }
      case Div:    { s << '(' << e->u.children.l
                       << " / " << e->children.r << '); }
   }
   return s;
}


next up previous contents index
Next: Another view example Up: User defined datatypes: Previous: User defined datatypes:

Allen Leung
Mon Apr 7 14:33:55 EDT 1997