The Mathematica Journal
Departments
Download This Issue
Home
Feature Articles
Graphics Gallery
Tricks of the Trade
In and Out
Columns
The Mathematica Programmer
New Products
New Publications
Classifieds
Calendar
News Bulletins
Editor's Pick
Mailbox
Letters
Write Us
About the Journal
Staff and Contributors
Submissions
Subscriptions
Advertising
Back Issues

Syntactic versus Semantic Matching

To illustrate what is meant by semantic pattern matching, consider

[Graphics:../Images/index_gr_3.gif]
[Graphics:../Images/index_gr_4.gif]

A semantic pattern matcher would give the answer [Graphics:../Images/index_gr_5.gif]. In Mathematica the above is ineffective, even though [Graphics:../Images/index_gr_6.gif] is mathematically the same as [Graphics:../Images/index_gr_7.gif] and there is a reduction for [Graphics:../Images/index_gr_8.gif] to [Graphics:../Images/index_gr_9.gif]. This matching does not take place because we would have made the semantic step of [Graphics:../Images/index_gr_10.gif] being equal to [Graphics:../Images/index_gr_11.gif]. To achieve this in standard Mathematica we must construct an algebraic rule as follows.

[Graphics:../Images/index_gr_12.gif]
[Graphics:../Images/index_gr_13.gif]
[Graphics:../Images/index_gr_14.gif]

We can further illustrate the concept of semantic matching by considering

[Graphics:../Images/index_gr_15.gif]
[Graphics:../Images/index_gr_16.gif]

There is no reduction in Mathematica because even though the argument [Graphics:../Images/index_gr_17.gif] is semantically equivalent to [Graphics:../Images/index_gr_18.gif] 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 [Graphics:../Images/index_gr_19.gif]. 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]