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

Semantica: A Full Semantic Pattern Matcher

[Graphics:../Images/index_gr_42.gif]

The previous sections have commented that Mathematica has some degree of inherent "semantic-ness" in its pattern matching ability. This occurs through the use of the pattern construct Optional and its defaults as well as the attributes Orderless, Flat, and OneIdentity. However, using standard Mathematica we are unable to define semantic patterns as general as those alluded to when we introduced the concept in the context of rewriting. Therefore, the Semantica package has been developed to resolve these limitations.

Semantica is a full semantic pattern matcher that extends the pattern matching capabilities of Mathematica to include semantic patterns. It does this by translating semantic patterns into corresponding syntactic patterns. One might think that this would be excessively difficult, but it is actually conceptually quite simple. However, the implementation of Semantica involves sophisticated pattern matching which will be outlined later in this article.

This section and the next deal primarily with how to use semantic patterns, their syntax, and their limitations. We present many examples of semantic pattern matching that demonstrate the full range of abilities of Semantica. Semantic patterns function correctly with single blanks, head restricted single blanks, semantic symbols, structural symbols, PatternTest constructs, Condition constructs, Optional constructs, named pattern objects, assignments, and transformation rules. In short, semantic patterns function with the normal pattern matching mechanisms of Mathematica.

In most circumstances the option [Graphics:../Images/index_gr_43.gif] can be used when Semantica creates definitions. Definitions created in this way operate at close to the same speed as normal definitions. Although we can use this option most of the time, discussion of it will be delayed until the next section. Therefore, for the short term let us turn the optimizing option off.

[Graphics:../Images/index_gr_44.gif]
[Graphics:../Images/index_gr_45.gif]

Conceptually speaking, semantic patterns are different from syntactic patterns, therefore we must notationally differentiate between them. Semantica uses the wrapper [Graphics:../Images/index_gr_46.gif] in standard form, or Semantic in full form, to indicate that a pattern expression should match semantically. For example, [Graphics:../Images/index_gr_47.gif] matches an expression that is semantically equal to [Graphics:../Images/index_gr_48.gif]for some [Graphics:../Images/index_gr_49.gif]. We can use this semantic pattern in a definition as follows.

[Graphics:../Images/index_gr_50.gif]
[Graphics:../Images/index_gr_51.gif]
[Graphics:../Images/index_gr_52.gif]

It is clearly evident that semantic matching was used in the above. Let us examine this matching process in detail. [Graphics:../Images/index_gr_53.gif] matched f[6] by [Graphics:../Images/index_gr_54.gif] semantically matching 3. It is important to note that 6 is not of the form [Graphics:../Images/index_gr_55.gif], so it is impossible for [Graphics:../Images/index_gr_56.gif] to syntactically match 6. However, [Graphics:../Images/index_gr_57.gif] semantically matches 6 by [Graphics:../Images/index_gr_58.gif] being bound to 3, and so f[6] gets rewritten to [Graphics:../Images/index_gr_59.gif] or 9.

We can examine some further evaluations by again using the function ResultTable, defined in TableFormatting.m.

[Graphics:../Images/index_gr_60.gif]

[Graphics:../Images/index_gr_61.gif]

In the second evaluation, [Graphics:../Images/index_gr_62.gif] was bound to 3 c/2, again through semantic matching. For the other arguments 1, 0, [Graphics:../Images/index_gr_63.gif], and [Graphics:../Images/index_gr_64.gif], the semantic pattern variable [Graphics:../Images/index_gr_65.gif] was respectively bound to 1/2, 0, [Graphics:../Images/index_gr_66.gif], and [Graphics:../Images/index_gr_67.gif]/2.

The fifth example above, where [Graphics:../Images/index_gr_68.gif] evaluates to [Graphics:../Images/index_gr_69.gif], demonstrates that semantic patterns obey proper scoping as expected. That is, a semantic pattern variable [Graphics:../Images/index_gr_70.gif] can match expressions containing the symbol [Graphics:../Images/index_gr_71.gif] without conflict. (This is due to the pattern variables being scoped by a Module.)

Let us now put simple conditions on semantic pattern variables. We restrict the matching of a semantic blank to a specified head in exactly the same way as we restrict a syntactic blank--by appending the specific head to the blank. Consider the following function, which matches even and odd integers.

[Graphics:../Images/index_gr_72.gif]
[Graphics:../Images/index_gr_73.gif]

[Graphics:../Images/index_gr_74.gif]

Here, even though the pattern variable [Graphics:../Images/index_gr_75.gif] in [Graphics:../Images/index_gr_76.gif] matches semantically, [Graphics:../Images/index_gr_77.gif] is still subject to the requirement that its Head is an Integer. Restrictions don't just need to be in the form of forcing a pattern variable to have a specific head. We can also use PatternTest and Condition constructs in the same way as they are used with standard syntactical patterns.

PatternTest constructs are valid inside and outside of a Semantic wrapper. For example, consider the following trial functions that we define to illustrate semantic matching with PatternTest.

[Graphics:../Images/index_gr_78.gif]

To examine the behavior of the trial functions [Graphics:../Images/index_gr_79.gif], [Graphics:../Images/index_gr_80.gif], and [Graphics:../Images/index_gr_81.gif], we can use a CompositionTable, which is also defined in TableFormatting.m. CompositionTable returns a table of each function applied to each argument.

[Graphics:../Images/index_gr_82.gif]

[Graphics:../Images/index_gr_83.gif]

By examining the table above, we can see that our trial functions are behaving as desired.

Condition constructs are also allowed inside and outside of a Semantic wrapper. Furthermore, conditions are similarly allowed on the right hand side of assignments and transformation rules. To give a simple example using a condition, consider

[Graphics:../Images/index_gr_84.gif]
[Graphics:../Images/index_gr_85.gif]

[Graphics:../Images/index_gr_86.gif]

The examples so far have used semantic patterns in conjunction with assignments. However, as one would expect, semantic patterns can also be used in transformation rules.

[Graphics:../Images/index_gr_87.gif]
[Graphics:../Images/index_gr_88.gif]

There are a couple of important differences in scoping between semantic patterns and syntactic patterns. The reasons for this will become clear once we cover the implementation of Semantica in the next section.

The pattern matching construct Pattern can also be used in semantic patterns, and the notation is exactly the same as that used in normal syntactic patterns. Pattern variables can label subpatterns both inside and outside a semantic pattern.

[Graphics:../Images/index_gr_89.gif]
[Graphics:../Images/index_gr_90.gif]

We can use Dispatch on our semantic rules to increase their speed, since this avoids recompiling the semantic rules each time they are used.

Like syntactic pattern variables, semantic pattern variables are treated nonlinearly when used more than once in a semantic pattern. Here is an example which combines Dispatch and a semantic transformation rule containing nonlinear semantic patterns.

[Graphics:../Images/index_gr_91.gif]
[Graphics:../Images/index_gr_92.gif]
[Graphics:../Images/index_gr_93.gif]

So far we have only used simple patterns that either yield a unique solution or no solution. However, we can easily specify semantic patterns which yield more than one semantic solution. Our hypothetical semantic matching example of [Graphics:../Images/index_gr_94.gif], given in the previous section, can now easily be implemented by the following.

[Graphics:../Images/index_gr_95.gif]
[Graphics:../Images/index_gr_96.gif]

The answer is close to what we wanted, but it was returned as a multiple-solution object, indicated by the [Graphics:../Images/index_gr_97.gif]. Such objects will be returned whenever there is more than one solution to our semantic matching. We know that every quadratic will have two solutions, so we can expect something like this.

Consequently, a wrapper is needed that will contain multiple solutions. Semantica uses the wrapper MultipleSolutions, which in standard form is [Graphics:../Images/index_gr_98.gif]. Intuitively, a multiple-solutions object should behave like, well, a multiple solution. If we perform any arithmetic operations on one of these objects, then that operation should be done on each solution. Also, a multiple-solutions object should be "flat." Formally, MultipleSolutions objects have the following properties:

[Graphics:../Images/index_gr_99.gif]

where [Graphics:../Images/index_gr_100.gif] is restricted to an arithmetic operation and the [Graphics:../Images/index_gr_101.gif] are expressions. Semantica implements MultipleSolutions objects by using the attribute Flat and distributing expressions over functions that have the attribute Listable. We can easily demonstrate the behavior of MultipleSolutions objects with the following example.

[Graphics:../Images/index_gr_102.gif]
[Graphics:../Images/index_gr_103.gif]

We can avoid receiving answers that contain multiple solutions by including a condition in the rule that restricts the solution space to a unique solution. For instance, let us consider a simple function that tests to see if an expression is syntactically greater than zero. Let us use the notation [Graphics:../Images/index_gr_104.gif] to mean that a is syntactically greater than zero.

[Graphics:../Images/index_gr_105.gif]

Now we can eliminate the syntactically negative solutions as follows.

[Graphics:../Images/index_gr_106.gif]
[Graphics:../Images/index_gr_107.gif]

In essence, we have used the condition that a minus sign is not explicitly present at the head of the expression. This is an ungainly solution. However, in future versions of Mathematica you may be able to declare the fact that an argument is real, greater than zero, etc., in more than just simplification or integration. Once this is the case, we could explicitly use the condition s > 0, which would be a far more elegant solution. This will be discussed in more detail in the penultimate section, Future Extensions.

It is sometimes desirable to be able to force Mathematica to choose a single solution. This is inherently a dangerous mathematical thing to do. However, to accomplish this you can set the option MultipleSolutionsOpt to False.

[Graphics:../Images/index_gr_108.gif]

To demonstrate the above, let us live dangerously and look at some examples with the multiple solutions option and its warning message turned off.

[Graphics:../Images/index_gr_109.gif]
[Graphics:../Images/index_gr_110.gif]
[Graphics:../Images/index_gr_111.gif]

Due to the nature of how Semantica functions, new assignments using the same semantic patterns do not clear any old assignments. Clear or ClearAll must be used to clear these older definitions.

Most features of pattern matching that make sense semantically make sense in Semantica. There are several other aspects of semantic matching that have not yet been mentioned, and these will be taken up in the next section as well as in the penultimate section, where the implementation of Semantica is discussed.


Converted by Mathematica      September 30, 1999

[Prev Page][Next Page]