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
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]