### How Semantica's Definitions Work

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.

This definition is transformed into something similar to the following.

If the user enters an expression involving `f`, say `f[19]`, then will match `19`. The rule proceeds if the condition is true, that is, if the equation (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 ).

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

`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 . We can test this definition by

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

This will be transformed to something like

The general function `func` works almost identically to `f`, described above. First 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.

We can generate the transformed definition by hand.

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`.

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.

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.

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 .

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.

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

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.

It is clearly evident that the equation present in the transformed definition, namely , is solvable in all cases. In fact, using `Reduce` we get

To create an optimized solution, we can alter the reductions by turning the `Equal` () into a `Set` (`=`) and the `Module` into a `With`. This results in

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.

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.

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, ) 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.

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]