Tuesday, October 20, 2009

Using "=?" in ParaSail to implement "==", "!=", "<=", ">=", etc.

Here is a simple ParaSail feature.  It is often the case that a user-defined type will have its own definition for equality and comparison.  However, it is always a bit of an issue to make sure that "==" and "!=" are complements, and similarly for "<" and ">=", ">" and "<=".  ParaSail skirts this issue by requiring the user to define only one operator, "=?", which returns a value from the enumeration Less, Equal, Greater, Unordered.  The comparison and equality operators are defined in terms of "=?" (which is pronounced "compare"), in the natural way:
  • "==" -- Result of "=?" is Equal
  • "!="  -- Result of "=?" is not Equal
  • "<"   -- Result of "=?" is Less
  • ">"   -- Result of "=?" is Greater
  • "<=" -- Result of "=?" is Less or Equal
  • ">=" -- Result of "=?" is Greater or Equal
"Unordered" is used for types with only a partial ordering (or no ordering at all).  "Ordered" is defined as the subtype containing only the values "Equal," "Less," and "Greater."  The typical generic "Sort" operation would expect a "=?" operator whose result is guaranteed (via a postcondition) to be within the "Ordered" subtype.

The "=?" operator can be used explicitly if desired, which is often convenient when searching a binary tree:
    case Desired_Key =? Node.Key of
        Equal :   return Node;
        Less :    return Search(Node.Left, Desired_Key);
        Greater : return Search(Node.Right, Desired_Key);
    end case;
This would be another situation where the "=?" would be required to return an Ordered result, since we don't have an alternative that handles "Unordered."

No comments:

Post a Comment