###
*Semantica*: A Full Semantic Pattern Matcher
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 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.
Conceptually speaking, semantic patterns are different from syntactic patterns, therefore we must notationally differentiate between them. *Semantica* uses the wrapper in standard form, or `Semantic` in full form, to indicate that a pattern expression should match semantically. For example, matches an expression that is semantically equal to for some . We can use this semantic pattern in a definition as follows.
It is clearly evident that semantic matching was used in the above. Let us examine this matching process in detail. matched `f[6]` by semantically matching `3` . It is important to note that `6` is *not* of the form , so it is impossible for to *syntactically* match `6` . However, *semantically* matches `6` by being bound to `3` , and so `f[6]` gets rewritten to or `9` .
We can examine some further evaluations by again using the function `ResultTable` , defined in `TableFormatting.m` .
In the second evaluation, was bound to `3 c/2` , again through semantic matching. For the other arguments `1` , `0` , , and
, the semantic pattern variable was respectively bound to `1/2` , `0` , , and
`/2` .
The fifth example above, where evaluates to , demonstrates that semantic patterns obey proper scoping as expected. That is, a semantic pattern variable can match expressions containing the symbol 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.
Here, even though the pattern variable in matches semantically, 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` .
To examine the behavior of the trial functions , , and , we can use a `CompositionTable` , which is also defined in `TableFormatting.m` . `CompositionTable` returns a table of each function applied to each argument.
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
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.
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.
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.
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
, given in the previous section, can now easily be implemented by the following.
The answer is close to what we wanted, but it was returned as a *multiple-solution object*, indicated by the . 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 . 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:
where is restricted to an arithmetic operation and the 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.
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 to mean that `a` is syntactically greater than zero.
Now we can eliminate the syntactically negative solutions as follows.
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` .
To demonstrate the above, let us live dangerously and look at some examples with the multiple solutions option and its warning message turned off.
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] |