### Syntactic versus Semantic Matching

To illustrate what is meant by semantic pattern matching, consider

A semantic pattern matcher would give the answer . In Mathematica the above is ineffective, even though is mathematically the same as and there is a reduction for to . This matching does not take place because we would have made the semantic step of being equal to . To achieve this in standard Mathematica we must construct an algebraic rule as follows.

We can further illustrate the concept of semantic matching by considering

There is no reduction in Mathematica because even though the argument is semantically equivalent to it is not syntactically equivalent. Furthermore, unlike the previous example, we cannot use `AlgebraicRules` to rectify this behavior. In a truly semantic pattern matching language, we might want the above expression to reduce to . However, in standard Mathematica this is difficult. To solve this problem, we have to generalize the pattern matching capabilities of Mathematica to include full semantic pattern matching.

It is a matter of opinion whether restricting pattern matching to being only syntactic is a major limitation. In general it is undecidable whether two expressions are semantically equivalent in a rewriting system. Thus the idea of semantic pattern matching is of course limited to the matching algorithm used to compare expressions. Consequently, all semantic pattern matchers are necessarily intrinsically limited. This does not necessarily stop them being useful in practice. An intrinsic problem with semantic matching is that there are often many and possibly an infinite number of ways to semantically match something. Finding a uniform and sensible way to choose which one of these semantic reductions to make can be a major headache.

Mathematica is generally viewed as being a strictly syntactic pattern matching language. In actuality it has some limited forms of semantic matching available to it, as we will see in the next section. In addition, we are able to extend Mathematica naturally to include full semantic pattern matching mechanisms. These capabilities and extensions are examined in the following sections.

Converted by Mathematica      September 30, 1999

[Prev Page][Next Page]