The Mathematica Journal
Download This Issue
Feature Articles
Graphics Gallery
Tricks of the Trade
In and Out
The Mathematica Programmer
New Products
New Publications
News Bulletins
Editor's Pick
Write Us
About the Journal
Staff and Contributors
Back Issues


This paper concerns semantic pattern matching in Mathematica. Throughout the beginning sections, the concept of semantic matching will be introduced and discussed in the context of the Mathematica language. Once the concept of a semantic pattern is understood, we can comment on the current semantic pattern matching capabilities of Mathematica.

The middle sections of this paper introduce the Semantica package, which comprehensively extends the pattern matching behavior of Mathematica to include semantic patterns. We examine the elementary capabilities of Semantica, its semantic pattern matching mechanisms, their usage and syntax, and a large number of examples. After covering standard semantic patterns, the following section progresses onto the more advanced capabilities of Semantica, including its available options, optimization, and structural symbols.

The later sections explore the implementation of Semantica. We unveil how a syntactic translation/compilation of a semantic pattern actually operates, and then briefly describe how the syntactic translations of semantic patterns are generated by Semantica. The conclusion contains a summary of the paper and comments on the future capabilities of Semantica within the framework of the new functionality of assumptions being introduced in later versions of Mathematica.

In some sections all global variables are cleared and the line numbering is reset. This allows more freedom to reuse variables like f and g, thus increasing readability. Also, uniformly throughout the paper, all pattern variables are scripted. For instance, a definition like [Graphics:../Images/index_gr_1.gif] would appear as [Graphics:../Images/index_gr_2.gif]. In the author's opinion, this style of coding is more readable since it separates pattern variables from normal symbols.

There are other formalisms and fields of study which involve concepts that have some resemblance to semantic matching. In particular, the fields of Constraint Logic Programming, Quantifier Elimination, and Algebraic Unification all involve concepts that have similarities to semantic matching in some way, shape, or form.

Semantic matching is to a large extent dependent on having a symbolic computation engine and is not strictly associated with functional rewrite rule languages. For instance, neither ML [8] nor Clean [9, 10] have semantic matching features. In contrast, the Macsyma language [7] has some simplistic semantic pattern matching features. The AXIOM language [5] was extended by Broadbery, Gomez-Diaz, and S. Watt [2] to incorporate "dynamic evaluation", which has similarities to the multiple solution objects which arise in the later stages of this paper. The REDLOG language [3] also has conceptual overlap with what we are trying to achieve in this paper.

However, the focus here is to introduce an additional language mechanism into the Mathematica pattern matching language and follow through the consequences of its introduction. In this sense, Semantica makes use of other underlying solving engines by adding a language mechanism that incorporates their functionality in a pattern matching way.

Converted by Mathematica      September 30, 1999

[Next Page]