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

How Semantica Builds Definitions


The previous section showed in detail how the syntactic definitions corresponding to a semantic definition actually function. It showed which Mathematica constructs were used to achieve semantic pattern matching. This section outlines how these syntactic functions are built from the semantic definitions. As anticipated, this involves considerable and sophisticated expression surgery, which we achieve by patterns matching patterns.

Performing extensive expression surgery forces us to face some major design decisions. Chief among these is the fact that we must maintain all expressions in a held form while we are performing the surgery. A naïve attempt to accomplish this might entail setting the HoldAll attribute of all of our functions involved in the surgery, as well as using Unevaluated, etc. Unfortunately, using HoldAll and Unevaluated is only practical when there are just a few functions that perform expression surgery. A better solution is to wrap a holding function around all parts of the expression. We cannot use Hold since we would not be able to tell the difference between the holds we have added and the ones that were already there, so we must use something else like hold, myHold, etc. One still has to be careful using this design, but it is safer and better than just using HoldAll and Unevaluated. The main problem with this approach is that the holds wrapped around everything have to be taken into consideration when using patterns to try to match the held expressions containing the new holds.

The best design is surprisingly simple. Take every symbol in the expression to a new symbol in a context, say inert`. One only has to do this at the start of the surgery and reverse this at the end. Also, one now does not have to worry about the intricacies of patterns matching patterns. For instance, if one wants to match a condition in the inert expression, one uses something like inert`System`Condition[expr_,cond_]. This is much nicer than having to wrap a dummy pattern variable around the condition. How do we accomplish this transformation and its inverse? As follows


It is instructive to demonstrate the functions toInert and fromInert on a simple pattern.


As an aside, if you are going to use the functions toInert and fromInert extensively, it would probably be beneficial to introduce notations for inert system functions. For example, a notation for the inert condition used in the above example might be


Of course, holding the expression using the inert` context relies on the fact that no other application has symbols defined in the inert` context; but if necessary one could easily change inert` to some other context, even a private context.

Now that we can sedate the expression, we can progress on to actually performing the surgery. The strategy is to work recursively through the left hand side, collecting up pattern variables, structural symbols, equations, and conditions. Once we have sufficiently transformed the left hand side, we must decide if the semantic pattern is optimizable by examining the generated equations. According to the optimizability, a syntactic definition is built that is either simple and unoptimized or more complex and optimized.

The actual lists that store the collections of pattern variables, structural symbols, equations, and conditions are respectively solveVars, solveAlwaysVars, equations, and conditionList. We have to keep track of these lists at all times, so instead of passing them around to all the functions that use them, we scope these variables with a Block. The actual function that processes the left hand side is dissectSemanticPattern, and it gets mapped onto all cases of [Graphics:../Images/index_gr_235.gif].

We next, list the cases dissectSemanticPattern has to handle, and the order in which it has to handle them, along with a brief description of the outcome. (For brevity, dissectSemanticPattern will be denoted by dissect.) Alternatively, the reader might want to skip forward a paragraph and study the example using dissect, only referring back to the table below when needed.

[Graphics:../Images/index_gr_236.gif] [Graphics:../Images/index_gr_237.gif] [Graphics:../Images/index_gr_238.gif]
[Graphics:../Images/index_gr_239.gif] [Graphics:../Images/index_gr_240.gif] [Graphics:../Images/index_gr_241.gif]
[Graphics:../Images/index_gr_242.gif] [Graphics:../Images/index_gr_243.gif] [Graphics:../Images/index_gr_244.gif]
[Graphics:../Images/index_gr_245.gif] [Graphics:../Images/index_gr_246.gif] [Graphics:../Images/index_gr_247.gif]
[Graphics:../Images/index_gr_248.gif] [Graphics:../Images/index_gr_249.gif] [Graphics:../Images/index_gr_250.gif]
[Graphics:../Images/index_gr_251.gif] [Graphics:../Images/index_gr_252.gif] [Graphics:../Images/index_gr_253.gif]
[Graphics:../Images/index_gr_254.gif] [Graphics:../Images/index_gr_255.gif] [Graphics:../Images/index_gr_256.gif]
[Graphics:../Images/index_gr_257.gif] [Graphics:../Images/index_gr_258.gif]
[Graphics:../Images/index_gr_259.gif] [Graphics:../Images/index_gr_260.gif] [Graphics:../Images/index_gr_261.gif]

To get an intuitive idea of how dissect works, let us step through an example transforming a semantic pattern.


For readability, we will temporarily ignore the fact that all the symbols are now prefixed by inert`. First, the whole Semantic clause is replaced by a temporary variable, say [Graphics:../Images/index_gr_263.gif], then the equation [Graphics:../Images/index_gr_264.gif] is added to the set of equations, and [Graphics:../Images/index_gr_265.gif] is returned. Then, the expression wrapped by the dissect will be recursively dissected. The next step in this dissection is to amputate the condition [Graphics:../Images/index_gr_266.gif] appearing in this equation and add it to the conditionList.

At this stage we have collected no pattern variables, no structural symbols, a single condition [Graphics:../Images/index_gr_267.gif], and a single equation [Graphics:../Images/index_gr_268.gif]. Since the head of the expression inside dissect is Plus, which is not a pattern matching mechanism, dissect gets threaded over this expression resulting in the following equation


Plus and 4 are non-structural atoms, so they are simply returned and [Graphics:../Images/index_gr_270.gif] reduces to [Graphics:../Images/index_gr_271.gif]. This results in our equation reducing to [Graphics:../Images/index_gr_272.gif]. However, the reduction to [Graphics:../Images/index_gr_273.gif] has the side effect of adding [Graphics:../Images/index_gr_274.gif] to the list solveVars of pattern variables and adding the new equation [Graphics:../Images/index_gr_275.gif] to our list of equations.

There are now two equations: [Graphics:../Images/index_gr_276.gif] and [Graphics:../Images/index_gr_277.gif]. The second of these equations is similarly dissected down to [Graphics:../Images/index_gr_278.gif], with [Graphics:../Images/index_gr_279.gif] and [Graphics:../Images/index_gr_280.gif] being added to the list of solveVars, as well as the condition [Graphics:../Images/index_gr_281.gif] being added to the conditionList.

The actual implementation of dissectSemanticPattern is relatively straightforward. Here are several typical snippets of the code for the cases of Semantic[expr] and expr /; cond. The others are similar.


Note the use of inert` prefixing all the mechanisms that we are destructuring.

The actual code in Semantica.m handles a few other postoperative cases. It strips any conditions from the top level of the right hand side of the expression and adds them to the conditionList. It also strips any residual conditions containing semantic pattern variables from the left hand side and adds these to the conditionList.

Now that we have dissected the left hand side of the expression, we must analyze the generated equations to determine whether they are optimizable. If the equations do not contain any structural symbols (that is, if solveAlwaysVars == {}) and if the Optimizing option is true, then we can attempt optimization. To do this we examine the result of Reduce[equations*, solveVars]. Here equations* is the same set of equations as equations, but all of the System` symbols inside equations have been reactivated from their inert` form to allow Reduce to function properly. For example, if equations is the list [Graphics:../Images/index_gr_284.gif], then equations* would be [Graphics:../Images/index_gr_285.gif].

If Reduce returns a result, we must ensure that the result is consistent. That is, the only time a solve variable should be present in the reductions is when it appears in the form solve-variable == expression-free-of-solve-variables. For instance, the following is inconsistent.


We accomplish this decision concerning optimizability using


Based on Optimizable, we either construct an optimized solution or a solution that has to be solved every time.


The construction of the "solve-every-time" solution is almost trivial. The new right hand side is very close to


with the following replacements:

isolateScope -> [Graphics:../Images/index_gr_291.gif]
solutionForm :> [Graphics:../Images/index_gr_292.gif]

Finally, we simply build the rule. To make this more readable, we can identify (up to evaluation) the built rule with


We do not have to be concerned with evaluation in the above code since all the structures here are inert.

The construction of the optimized solution is more tricky but is still conceptually straightforward. First, the reductions that Reduce produces are separated into single solutions. Each solution is further split into subsolutions for the pattern variables and the reduction conditions that this solution must obey. Then, a rule for each solution is defined with an appended condition that collects the solutions but returns False. We can see the results of this by again looking at the generated definitions of the timeForDistance function.


There is one final implementation issue that must be mentioned. How do we automatically intercept semantic patterns so that they get compiled to syntactic patterns? The following piece of code safely accomplishes this interception when the semantic pattern is used inside a SetDelayed.


Here, containsSemanticPatternQ tests to see whether lhs contains a semantic pattern. It is quite important that this testing function does not evaluate its arguments, so it must be carefully constructed. If there is a semantic pattern present in the lhs, then the assignment is compiled into syntactic rules. These rules are then entered into the system via SetDelayed being applied to them. The actual code used in Semantica is slightly more sophisticated, and has to take into account the correct evaluation of the left hand side of the assignment in keeping with standard Mathematica. The code for Set, Replace, ReplaceRepeated, and ReplaceAll is very similar.

Converted by Mathematica      September 30, 1999

[Prev Page][Next Page]