The Tagof Operator

Each datatype constructor has an associated unique integer called the tag. The tag of a datatype or datatype field can be accessed using the tagof operator. For example, given the datatype Exp defined previously, we can write a structural comparison function which enforces an order on expressions as follows:

  bool sameexp(datatype Exp @e1, datatype Exp @e2) {
    switch $(e1,e2) {
    case $(&Int(i),&Int(j)): return i - j;
    case $(&Float(f),&Float(g)): 
        if (f == g) return 0;
        if (f < g) return -1;
        return 1;
    case $(&Unop(u1,ea),&Unop(u2,eb)): 
        int c = u1 - u2;
        if (c != 0) return c;
        return sameexp(ea,eb);
    case $(&Binop(b1,ea1,ea2),&Binop(b2,eb1,eb2)):
        int c = b1 - b2;
        if (c != 0) return c;
        c = sameexp(ea1,eb1);
        if (c != 0) return c;
        return sameexp(ea2,eb2);
    default: return tagof(e1) - tagof(e2);

This function compares the structure of two expressions e1 and e2 and returns a number less than zero if e1 < e2, zero if e1 == e2, and a number greater than zero otherwise. Notice that the default case needs to handle all of the situtations where e1 and e2 are different constructors. To achieve this, we extract the tags from the two datatype values and return their difference. This keeps us from having to write a more tedious match that would include the following cases:

   case $(&Int(_),_): return -1;
   case $(_,&Int(_)): return 1;
   case $(&Unop(_,_),_): return -1;
   case $(_,&Unop(_)) return 1;