Although a comparable evaluation function can be written in object oriented style using late binding, as in below, in general pattern matching is much more powerful than late binding in C++, which only allows dispatching based on the type of one receiver.
// Class definitions
class Exp {
public:
virtual int eval(const map<const char *, int>& env) const = 0;
};
class INT : Exp {
int i;
public:
int eval(const map<const char *, int>& env);
};
class ID : Exp {
const char * id
public:
int eval(const map<const char *, int>& env);
};
...
// Member functions
int INT::eval(const map<const char *, int>& env) const { return i; }
int ID ::eval(const map<const char *, int>& env) const { return id; }
int ADD::eval(const map<const char *, int>& env) const
{ return e1->eval(env) + e2->eval(env); }
int SUB::eval(const map<const char *, int>& env) const
{ return e1->eval(env) - e2->eval(env); }
int MUL::eval(const map<const char *, int>& env) const
{ return e1->eval(env) * e2->eval(env); }
int DIV::eval(const map<const char *, int>& env) const
{ return e1->eval(env) / e2->eval(env); }
For example, in the following function we use nested patterns, non-linear patterns (i.e. patterns with multiple occurrences of a pattern variable), and guards to perform algebraic simplification of an expression. Although the patterns are relatively simple in this example, in general arbitrarily complex patterns may be used.
Exp simplify (Exp redex)
{ // recursive traversal code omitted ...
// match while repeats the matching process
// until no more matches are found.
match while (redex)
{ ADD(INT 0, ?x): { redex = ?x; }
| ADD(INT ?x, INT ?y): { redex = INT(?x+?y); }
| ADD(?x, INT 0) { redex = ?x; }
| SUB(?x, INT 0): { redex = ?x; }
| SUB(?x, ?x): { redex = INT(0); }
| SUB(INT ?x, INT ?y): { redex = INT(?x-?y); }
| MUL(INT 0, ?x): { redex = INT(0); }
| MUL(?x, INT 0): { redex = INT(0); }
| DIV(?x, ?x): { redex = INT(1); }
// don't divide by zero.
| DIV(INT ?x, INT ?y) | ?y != 0: { redex = INT(?x/?y); }
| ...
}
return redex;
}
Pattern matching in Prop is not restricted to one datatype at
a time. In the following example, we use matching on multiple values to
define equality on expressions inductively. For variety, we'll
use the fun variant of match, which defines a function
in rule form. Notice that the last case
of the match set uses wild cards _ to catch all the other
non-equal combinations. Since C++ does not provide multiple dispatching,
implementing binary (or n-ary) matching operations on variant datatypes are
in general cumbersome and verbose in object-oriented style. In contrast,
using an applicative pattern matching style many manipulations and
transformations on variant datatypes with tree-like or graph-like structure
can be expressed succinctly.
fun equal INT ?i, INT ?j: bool: { return ?i == ?j; }
| equal ID ?a, ID ?b: { return strcmp(a,b) == 0; }
| equal ADD(?a,?b), ADD(?c,?d): { return equal(?a,?c) && equal(?b,?d); }
| equal SUB(?a,?b), SUB(?c,?d): { return equal(?a,?c) && equal(?b,?d); }
| equal MUL(?a,?b), MUL(?c,?d): { return equal(?a,?c) && equal(?b,?d); }
| equal DIV(?a,?b), DIV(?c,?d): { return equal(?a,?c) && equal(?b,?d); }
| equal _, _: { return false; }
;