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

How Semantica's Definitions Work

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

We saw in the previous sections how to use Semantica. We observed that it uniformly extended all of the normal syntactic matching mechanisms to semantic matching mechanisms (at least for the pattern matching mechanisms that make semantical sense). How did we accomplish this feat? This section will introduce the concepts behind Semantica and gradually work towards the implementation that has been coded in the package Semantica.m.

Semantica takes semantic patterns, surgically rips them apart and reassembles equivalent syntactic patterns. It is easier to see how Semantica transforms semantic patterns when optimization is off. Let us look very roughly at how a simple semantic assignment is transformed.

[Graphics:../Images/index_gr_175.gif]
[Graphics:../Images/index_gr_176.gif]

This definition is transformed into something similar to the following.

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

If the user enters an expression involving f, say f[19], then [Graphics:../Images/index_gr_178.gif] will match 19. The rule proceeds if the condition is true, that is, if the equation [Graphics:../Images/index_gr_179.gif] (in our case, 19 == 2 n) is solvable for n. If a solution is found, then n is replaced everywhere on the right hand side by the solution of the equation, namely solution, (in our case, the rule set [Graphics:../Images/index_gr_180.gif]).

Let us now actually create a Mathematica definition that works as indicated above and fills in solution and solvable.

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

fByHand is almost the same as our outline above, except that solution is explicitly set inside the condition. Also solution must not be equal to {}, which is equivalent to requiring that the equation must be solvable. It is also convenient at this stage to take the first of all possible returned solutions by using [Graphics:../Images/index_gr_182.gif]. We can test this definition by

[Graphics:../Images/index_gr_183.gif]
[Graphics:../Images/index_gr_184.gif]

There are problems with our definition for fByHand, which we will soon address; but in principal, the concept is sound.

After the above motivation we can now give an outline of the compiled definition of a single semantic pattern. Consider some definition like

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

This will be transformed to something like

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

The general function func works almost identically to f, described above. First [Graphics:../Images/index_gr_187.gif] matches any expression; next it is determined whether the equations are solvable; if solvable, then the rule proceeds and the solution for the equations is substituted throughout the rhs. These essential steps remain unchanged for all of our transformed definitions, until we consider optimization.

As mentioned previously, there are a few problems with the specific style of the definition of fByHand. First, the scoping of the pattern variables (that is n and solution) is ignored. Second, the right hand side is evaluated before the replacement is performed. Let us rectify these general shortcomings in another example generated by hand. Let us complicate matters deliberately by using an assignment which contains two semantic patterns.

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

We can generate the transformed definition by hand.

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

We scoped x, y, and solution by a Module, so this solves the first problem; and we wrapped the right hand side in an Unevaluated, which resolves the second problem. The behavior of gByHand is exactly the same as g.

[Graphics:../Images/index_gr_190.gif]
[Graphics:../Images/index_gr_191.gif]
[Graphics:../Images/index_gr_192.gif]
[Graphics:../Images/index_gr_193.gif]

The reader may have been curious throughout the previous sections as to what a semantic assignment actually looks like, since no full definitions were ever given. Now that we have presented a general outline of what semantic rules and assignments are transformed into, it is time to fully unveil the true syntactic definitions corresponding to semantic definitions. We start with the syntactic definition for the unoptimized f above.

[Graphics:../Images/index_gr_194.gif]
[Graphics:../Images/index_gr_195.gif]
[Graphics:../Images/index_gr_196.gif]

This is very similar to the solution we would generate by hand. In fact, the only difference is that the Solve has been replaced by a new function SolveWithConditions. This new solving function will be explained shortly, but for now it suffices to say that it consists of a judicious mix of Solve, SolveAlways, and Select.

Intuitively, the syntactic definitions are constructed by replacing any Semantic wrapper by a new unique name on the left hand side. A function that removes the patterns and blanks from an expression is applied to the pattern inside the Semantic wrapper to turn the wrapped stuff into equations. At the same time, the conditions and pattern tests are collected into criteria which the final solutions must satisfy. The details of this overall process are given in the next section.

Let us consider another example of a semantic definition, this time with a more complex structure.

[Graphics:../Images/index_gr_197.gif]
[Graphics:../Images/index_gr_198.gif]
[Graphics:../Images/index_gr_199.gif]
[Graphics:../Images/index_gr_200.gif]

The correspondence between the original semantic assignment and the equations in the ensuing syntactic version is clearly evident. The pattern variables are scoped by the Module as well as being passed to SolveWithConditions. Finally, all of the solutions must satisfy the condition [Graphics:../Images/index_gr_201.gif].

Now that we have seen several examples of actual definitions generated by Semantica, the description of SolveWithConditions should be more meaningful. It is the main solving engine behind the functioning of Semantica. SolveWithConditions[equations, solve-variables, structural-variables, conditions] returns the solutions of the equations solved for the solve-variables, subject to the requirement that these solutions are true for all structural-variables and that the solutions satisfy the conditions. The following is the code for SolveWithConditions when there are no structural variables.

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

This code is relatively transparent. First the equations are solved, then the solutions that do not satisfy the conditions are eliminated by verifySolutions. Finally, the solutions are processed by cleanUpSolutions. This cleaning up returns a single solution if there is only one after the conditions have been satisfied. However, if verifySolutions returns multiple solutions, then depending on the option MultipleSolutionsOpt, cleanUpSolutions will return a MultipleSolutions object or warn the user and return a single solution.

The general case for SolveWithConditions is very similar to the above, with the Solve[eqns, solveVars] being replaced by

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

This code is virtually identical to the code for SolveAlways, and I will not explain why this works other than to say that the interested reader should trace through a small example by hand, something like a x + b == 2 x + 3 with solveAlwaysVars = {x}.

Now that we have covered the fundamentals of how Semantica functions, we are ready for the next conceptual leap. The generated solutions up until now have all called Solve for each usage. This is extremely computationally expensive. Yet the input is different each time, and so we must use Solve for each attempted match. Or must we? Reduce will give all the solutions to a set of equations together with the conditions each solution must satisfy. So for certain classes of problems, we can generate all the solutions, thus giving us multiple definitions, and enter these. We can again clarify this by looking at examples. Let us re-examine the following semantic definition and its corresponding syntactic version generated by Semantica.

[Graphics:../Images/index_gr_204.gif]
[Graphics:../Images/index_gr_205.gif]
[Graphics:../Images/index_gr_206.gif]
[Graphics:../Images/index_gr_207.gif]

It is clearly evident that the equation present in the transformed definition, namely [Graphics:../Images/index_gr_208.gif], is solvable in all cases. In fact, using Reduce we get

[Graphics:../Images/index_gr_209.gif]
[Graphics:../Images/index_gr_210.gif]

To create an optimized solution, we can alter the reductions by turning the Equal ([Graphics:../Images/index_gr_211.gif]) into a Set (=) and the Module into a With. This results in

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

Using the "reduce" approach allows a couple of simplifications. First, the Unevaluated is no longer necessary since the pattern variable n is scoped using a With, and gets evaluated before the body of the right hand side. In fact, this scoping structure can be thought of as forcing the binding of n. Second, the solution variable is no longer present. Finally, and most importantly, there is now no Solve present in this definition.

Let us compare the definition above generated by hand to the one generated by Semantica when optimization is on.

[Graphics:../Images/index_gr_213.gif]
[Graphics:../Images/index_gr_214.gif]
[Graphics:../Images/index_gr_215.gif]
[Graphics:../Images/index_gr_216.gif]
[Graphics:../Images/index_gr_217.gif]

Our version generated by hand is virtually identical to that generated by Semantica. They both appear innocuously simple. However, as our equations become more complex, the output of Reduce becomes increasingly complex. This increase in complexity will occur in any case since we will have to solve the equations sometime. Let us examine the optimized definition corresponding to the following semantic assignment.

[Graphics:../Images/index_gr_218.gif]
[Graphics:../Images/index_gr_219.gif]
[Graphics:../Images/index_gr_220.gif]
[Graphics:../Images/index_gr_221.gif]
[Graphics:../Images/index_gr_222.gif]
[Graphics:../Images/index_gr_223.gif]
[Graphics:../Images/index_gr_224.gif]
[Graphics:../Images/index_gr_225.gif]

There are now three rules present for foo! This multiplicity is due to Reduce producing three solutions. Unfortunately, in general there is no easy way to determine if the conditions imposed on the original semantic assignment (for example, [Graphics:../Images/index_gr_226.gif]) are sufficient to be able to eliminate all but one of the solutions before the specific input is known. Therefore, we cannot warn if there are multiple solutions. However, in certain cases we can circumvent this problem. This topic is again covered in more detail in the section Future Extensions.

It is also important to realize that there are conditions present on the left hand sides of these optimized definitions. These conditions stop the With being evaluated when the pattern variables (for example t and p) are inconsistent with the values of some of the other symbols (for example, a and b). If a is zero, then evaluating either the second or third solution will lead to an error because t would get evaluated and t has an a in the denominator. Therefore, these restrictions must be on the left hand side.

In describing how Semantica is implemented it should again be pointed out that Semantica loads the Notation package which ships with Mathematica. To achieve the formatting for semantic patterns and multiple solutions introduced in the earlier sections, Semantica declares the following notations.

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

The reader now should be aware of how the definitions produced by Semantica work. Semantica uses the native intelligence of Solve and Reduce.


Converted by Mathematica      September 30, 1999

[Prev Page][Next Page]