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

Advanced Capabilities of Semantica

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

The last section introduced and demonstrated Semantica. This section will disclose several of the more advanced features and options with which we can control the behavior of semantic pattern matching. These include the option Optimizing, which enormously speeds up semantic pattern matching, and the dual use of "free" symbols in semantic patterns.

Up to this point in all of our semantic pattern matching examples, there has been a conspicuous lack of any symbols besides pattern variables. What happens when free or non-pattern symbols are used in a definition or a rule? For instance, what happens when x occurs in [Graphics:../Images/index_gr_113.gif]? This raises a perplexing question. Should non-pattern symbols, like x here, occurring in a Semantic wrapper, be treated semantically or structurally? This question never arises in structural pattern matching since everything is structural. Which case do we want? It transpires that we sometimes want structural behavior and sometimes semantic behavior. Luckily we can incorporate both structural and semantic behavior into Semantica.

Before we explain how each behavior is used and where, let us consider some motivating cases for the two different uses. Let us define a function that takes a polynomial in x of degree at most two and returns its coefficients. (This is hard to express with only standard structural pattern matching.)

[Graphics:../Images/index_gr_114.gif]
[Graphics:../Images/index_gr_115.gif]

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

So the solution to our problem of creating a pattern that would match polynomials and return their coefficients is to use a simple semantic pattern. If we wanted to match a strict quadratic in x we would just include the condition that [Graphics:../Images/index_gr_117.gif], as in [Graphics:../Images/index_gr_118.gif].

Our use of x in this example of poly is definitely structural. Our solution for the pattern variables [Graphics:../Images/index_gr_119.gif], [Graphics:../Images/index_gr_120.gif], and [Graphics:../Images/index_gr_121.gif] depends on the fact that they are free of x. This semantic pattern is unsolvable if x is not being used structurally, since we would then have a single equation with four unknowns. We see this from

[Graphics:../Images/index_gr_122.gif]
[Graphics:../Images/index_gr_123.gif]
[Graphics:../Images/index_gr_124.gif]

This solution is clearly not what we want.

In light of the above, when would we ever want symbols to be used semantically? Actually, we have unwittingly used them in practically every example using semantic patterns given so far. A few of the symbols we used semantically were: Plus, Times, Power, [Graphics:../Images/index_gr_125.gif], and Log. If these symbols were treated structurally, then we would have mimicked standard structural matching, which is what we tried to avoid in the first place! To illustrate these claims, let us give the following example.

[Graphics:../Images/index_gr_126.gif]
[Graphics:../Images/index_gr_127.gif]

Here we have used addition in [Graphics:../Images/index_gr_128.gif] and multiplication in _ _. If the Times and Plus present in these patterns were acting structurally, then _ _ could not have matched 3 or c since neither of these arguments are of the form Times[_,_]. Therefore, in the above Plus and Times need to act semantically.

A further example of semantic matching with semantic symbols is the function semanticE which we will denote by [Graphics:../Images/index_gr_129.gif].

[Graphics:../Images/index_gr_130.gif]
[Graphics:../Images/index_gr_131.gif]
[Graphics:../Images/index_gr_132.gif]
[Graphics:../Images/index_gr_133.gif]

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

Above we define semanticE, that is [Graphics:../Images/index_gr_135.gif], as the semantic inverse of Log. The result table clearly shows that Log is being used semantically in the definition of semanticE since it is not explicitly present in the majority of the input examples. It is worth pointing out that in most cases where we require a certain symbol to act structurally we can usually explicitly reformulate the pattern to accommodate this.

Based on the above considerations, Semantica treats all symbols inside a semantic wrapper (that are not pattern variables) as being semantic, unless explicitly specified otherwise. To declare that symbol(s) should be treated structurally, we use DeclareStructural[symbol(s)]. We can reverse this by DeclareSemantic[symbol(s)].

Now that we know how non-pattern symbols are treated, we can generalize the previous semantic rule for h using the semantic symbols [Graphics:../Images/index_gr_136.gif] and [Graphics:../Images/index_gr_137.gif] (semantic by default since [Graphics:../Images/index_gr_138.gif] and [Graphics:../Images/index_gr_139.gif] are normal symbols).

[Graphics:../Images/index_gr_140.gif]
[Graphics:../Images/index_gr_141.gif]

To further illustrate the use of semantic symbols, let us implement an example from physics. Simple physical dynamics and elementary calculus show that a uniformly accelerating object obeys the following equation.

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

Let us therefore create a simple function that returns the time t taken to travel a given distance.

[Graphics:../Images/index_gr_143.gif]
[Graphics:../Images/index_gr_144.gif]

We can now determine how long it will take to travel a given distance, say [Graphics:../Images/index_gr_145.gif].

[Graphics:../Images/index_gr_146.gif]
[Graphics:../Images/index_gr_147.gif]

Notice that the acceleration is present in the denominator. If the object is not accelerating, this answer is incorrect. To get the correct answer, we just set the acceleration to zero and again ask for the time it takes to travel the distance [Graphics:../Images/index_gr_148.gif].

[Graphics:../Images/index_gr_149.gif]
[Graphics:../Images/index_gr_150.gif]

We can set the dependent variables a, [Graphics:../Images/index_gr_151.gif], and [Graphics:../Images/index_gr_152.gif] to anything we like, and the equations will solve the semantic pattern correctly. Here is an example.

[Graphics:../Images/index_gr_153.gif]
[Graphics:../Images/index_gr_154.gif]

One can easily verify this result by explicitly solving the underlying system.

[Graphics:../Images/index_gr_155.gif]
[Graphics:../Images/index_gr_156.gif]

We can put in some fairly nasty conditions and the function timeForDistance will still work correctly.

[Graphics:../Images/index_gr_157.gif]
[Graphics:../Images/index_gr_158.gif]

In most cases, Semantica can optimize its definitions, speeding up semantic pattern matching to the execution times of normal definitions. The notation for semantic patterns remains exactly the same when using optimization. Whenever the semantic pattern is non-degenerate and contains no structural symbols, optimization can be used. Degenerate patterns also can be optimized, but the solution returned cannot always be in as simple a form as when optimization is turned off. This is an intrinsic problem that we will discuss shortly. First though, let us look at some examples using optimized functions.

We can compare the timings of our simple f from the previous section with the same function when optimization is turned on.

[Graphics:../Images/index_gr_159.gif]
[Graphics:../Images/index_gr_160.gif]
[Graphics:../Images/index_gr_161.gif]

We see in the above case that optimization only speeds up the function about 20 times. This increase in speed typically varies from around 10 times up to several thousand times. Let us redefine the function timeForDistance with optimization on.

[Graphics:../Images/index_gr_162.gif]
[Graphics:../Images/index_gr_163.gif]
[Graphics:../Images/index_gr_164.gif]
[Graphics:../Images/index_gr_165.gif]
[Graphics:../Images/index_gr_166.gif]

Here the gain in speed is around 10 times. The result of the optimized function, however, is not in quite as compact a form as that of the unoptimized function. Why is this? When optimizing is off, each semantic match, in essence, has to be solved each time. Performing a Solve for every match is slow but allows the solution to be tailored to the specific arguments of the function call. In contrast, when the optimizer is on, generic solutions to a semantic pattern are found and definitions based on these are created. These generic solutions are much faster but cannot take advantage of the specific arguments that the semantic pattern is matching. The reason the optimized version above is not faster is that a significant amount of time is taken choosing the symbolically simplest solution to the semantic pattern (since we have the multiple solutions option turned off). To demonstrate that generic solution answers can sometimes be convoluted, compare the following.

[Graphics:../Images/index_gr_167.gif]
[Graphics:../Images/index_gr_168.gif]

We can circumvent the problem of unsimplified generic solution answers in most cases by enclosing the right hand side by an ExpandAll or a Simplify.

Despite not always taking account of the specific arguments of the function, optimized functions do take into account all cases of the pattern variables as well as the semantic variables. For example, our time-for-distance function easily handles the case when the denominator is zero.

[Graphics:../Images/index_gr_169.gif]
[Graphics:../Images/index_gr_170.gif]

It should be mentioned that semantic patterns currently do not work correctly with Alternatives. The reason for this behavior is that in patterns with alternatives, it is undecidable whether a pattern variable will be bound to a value before the specific expression to be matched is given. This is a complication that, at this stage, Semantica does not handle.

It should also be mentioned that optionals work nicely in conjunction with semantic patterns. We need this behavior since sometimes Mathematica has trouble with transcendental solutions.

[Graphics:../Images/index_gr_171.gif]
[Graphics:../Images/index_gr_172.gif]

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

In conclusion, Semantica is a powerful extension to Mathematica that enables one to use semantic patterns in many different situations. An intuitive description of how Semantica functions, together with some of the gritty details of how it is implemented, are given in the following sections.


Converted by Mathematica      September 30, 1999

[Prev Page][Next Page]