/usr/share/doc/axiom-doc/hypertex/funpatternmatching.xhtml

<?xml version="1.0" encoding="UTF-8"?>
<html xmlns="http://www.w3.org/1999/xhtml" 
      xmlns:xlink="http://www.w3.org/1999/xlink"
      xmlns:m="http://www.w3.org/1998/Math/MathML">
 <head>
  <meta http-equiv="Content-Type" content="text/html" charset="us-ascii"/>
  <title>Axiom Documentation</title>
  <style>

   html {
     background-color: #ECEA81;
   }

   body { 
     margin: 0px;
     padding: 0px;
   }

   div.command { 
     color:red;
   }

   div.center {
     color:blue;
   }

   div.reset {
     visibility:hidden;
   }

   div.mathml { 
     color:blue;
   }

   input.subbut {
     background-color:#ECEA81;
     border: 0;
     color:green;
     font-family: "Courier New", Courier, monospace;
   }

   input.noresult {
     background-color:#ECEA81;
     border: 0;
     color:black;
     font-family: "Courier New", Courier, monospace;
   }

   span.cmd { 
     color:green;
     font-family: "Courier New", Courier, monospace;
   }

   pre {
     font-family: "Courier New", Courier, monospace;
   }
  </style>
  <script type="text/javascript">
<![CDATA[
     // This is a hash table of the values we've evaluated.
     // This is indexed by a string argument. 
     // A value of 0 means we need to evaluate the expression
     // A value of 1 means we have evaluated the expression
   Evaled = new Array();
     // this says we should modify the page
   hiding = 'show';
     // and this is the id of the div tag to modify (defaulted)
   thediv = 'mathAns';
     // commandline will mark that its arg has been evaled so we don't repeat
   function commandline(arg) {
     Evaled[arg] = 0;  // remember that we have set this value
     thediv='ans'+arg; // mark where we should put the output
     var ans = document.getElementById(arg).value;
     return(ans);
   }
   // the function only modifies the page if when we're showing the
   // final result, otherwise it does nothing.
   function showanswer(mathString,indiv) {
     if (hiding == 'show') { // only do something useful if we're showing
       indiv = thediv;  // override the argument so we can change it
       var mystr = mathString.split("</div>");
       for (var i=0; i < mystr.length; i++) {
         if (mystr[i].indexOf("mathml") > 0) {
           var mymathstr = mystr[i].concat("</div>");
         }
       }
       // this turns the string into a dom fragment
       var mathRange = document.createRange();
       var mathBox=
               document.createElementNS('http://www.w3.org/1999/xhtml','div');
       mathRange.selectNodeContents(mathBox);
       var mymath = mathRange.createContextualFragment(mymathstr);
       mathBox.appendChild(mymath);
       // now we need to format it properly
       // and we stick the result into the requested div block as a child.
       var mathAns = document.getElementById(indiv);
       mathAns.removeChild(mathAns.firstChild);
       mathAns.appendChild(mathBox);
     }
   }
   // this function takes a list of expressions ids to evaluate
   // the list contains a list of "free" expression ids that need to
   // be evaluated before the last expression. 
   // For each expression id, if it has not yet been evaluated we
   // evaluate it "hidden" otherwise we can skip the expression.
   // Once we have evaluated all of the free expressions we can
   // evaluate the final expression and modify the page.
   function handleFree(arg) {
     var placename = arg.pop();      // last array val is real
     var mycnt = arg.length;         // remaining free vars
       // we handle all of the prerequired expressions quietly
     hiding = 'hide';
     for (var i=0; i<mycnt; i++) {   // for each of the free variables
       if (Evaled[arg[i]] == null) { // if we haven't evaled it
         Evaled[arg[i]] = 0;         // remember we evaled it
         makeRequest(arg[i]);        // initialize the free values
       }
     }
       // and now we start talking to the page again
     hiding = 'show';                // we want to show this
     thediv = 'ans'+placename;       // at this div id
     makeRequest(placename);         // and we eval and show it
   }
]]>
<![CDATA[
  function ignoreResponse() {}
  function resetvars() {
    http_request = new XMLHttpRequest();         
    http_request.open('POST', '127.0.0.1:8085', true);
    http_request.onreadystatechange = ignoreResponse;
    http_request.setRequestHeader('Content-Type', 'text/plain');
    http_request.send("command=)clear all");
    return(false);
  }
]]>
 function init() {
 }
 function makeRequest(arg) {
   http_request = new XMLHttpRequest();         
   var command = commandline(arg);
   //alert(command);
   http_request.open('POST', '127.0.0.1:8085', true);
   http_request.onreadystatechange = handleResponse;
   http_request.setRequestHeader('Content-Type', 'text/plain');
   http_request.send("command="+command);
   return(false);
 }
 function lispcall(arg) {
   http_request = new XMLHttpRequest();         
   var command = commandline(arg);
   //alert(command);
   http_request.open('POST', '127.0.0.1:8085', true);
   http_request.onreadystatechange = handleResponse;
   http_request.setRequestHeader('Content-Type', 'text/plain');
   http_request.send("lispcall="+command);
   return(false);
 }
 function showcall(arg) {
   http_request = new XMLHttpRequest();         
   var command = commandline(arg);
   //alert(command);
   http_request.open('POST', '127.0.0.1:8085', true);
   http_request.onreadystatechange = handleResponse;
   http_request.setRequestHeader('Content-Type', 'text/plain');
   http_request.send("showcall="+command);
   return(false);
 }
 function interpcall(arg) {
   http_request = new XMLHttpRequest();         
   var command = commandline(arg);
   //alert(command);
   http_request.open('POST', '127.0.0.1:8085', true);
   http_request.onreadystatechange = handleResponse;
   http_request.setRequestHeader('Content-Type', 'text/plain');
   http_request.send("interpcall="+command);
   return(false);
 }
 function handleResponse() {
  if (http_request.readyState == 4) {
   if (http_request.status == 200) {
    showanswer(http_request.responseText,'mathAns');
   } else
   {
     alert('There was a problem with the request.'+ http_request.statusText);
   }
  }
 }

  </script>
 </head>
 <body onload="resetvars();">
  <div align="center"><img align="middle" src="doctitle.png"/></div>
  <hr/>
  <div align="center">Rules and Pattern Matching</div>
  <hr/>
A common mathematical formula is 
<pre>
log(x)+log(y)==log(x*y)
</pre>
for any x and y. The presence of the word "any" indicates that x and y
can stand for arbitrary mathematical expressions in the above formula. You
can use such mathematical formulas in Axiom to specify "rewrite rules". 
Rewrite rules are objects in Axiom that can be assigned to variables for
later use, often for the purpose of simplification. Rewrite rules look like
ordinary function definitions except that they are preceded by the reserved
word rule. For example, a rewrite rule for the above formula is:
<pre>
  rule log(x) + log(y) == log(x * y)
</pre>
Like function definitions, no action is taken when a rewrite rule is issued.
Think of rewrite rules as functions that take one argument. When a rewrite
rule A=B is applied to an argument f, its meaning is "rewrite every
subexpressions of f that matches A by B". The left-and side of a rewrite rule
is called a <a href="glossarypage.xhtml#p38600">pattern</a>; 
its right-hand side is
called its <a href="glossarypage.xhtml#p49000">substitution</a>. 

Create a rewrite rule named logrule. The generated symbol begins with a
"%" and is a place holder for any other terms that might occur in the sum.
<ul>
 <li>
  <input type="submit" id="p1" class="subbut" 
    onclick="makeRequest('p1');"
    value="logrule:=rule log(x)+log(y)==log(x*y)" />
  <div id="ansp1"><div></div></div>
 </li>
</ul>
Create an expression with logarithms.
<ul>
 <li>
  <input type="submit" id="p2" class="subbut" 
    onclick="makeRequest('p2');"
    value="f:=log sin x + log x" />
  <div id="ansp2"><div></div></div>
 </li>
</ul>
Apply logrule to f.
<ul>
 <li>
  <input type="submit" id="p3" class="subbut" 
    onclick="handleFree(['p1','p2','p3']);"
    value="logrule f" />
  <div id="ansp3"><div></div></div>
 </li>
</ul>
The meaning of our example rewrite rule is "for all expressions x and y,
rewrite log(x) and log(y) by log(x*y)". Patterns generally have both operation
names 
(here, <a href="dboplog.xhtml">log</a> and <a href="dbopplus.xhtml">+</a>)
and variables (here, x and y). By default, every operation name stands for
itself. The <a href="dboplog.xhtml">log</a> matches only "log" and not
any other operation such as <a href="dbopsin.xhtml">sin</a>. On the other
hand, variables do not stand for themselves. Rather, a variable denotes a
<a href="glossarypage.xhtml#p39400">pattern variable</a> 
that is free to match any expression whatsoever.

When a rewrite rule is applied, a process called 
<a href="glossarypage.xhtml#p38661">pattern matching</a> 
goes to work by systematically 
scanning the subexpressions of the argument. When a subexpression is found
that "matches" the pattern, the subexpression is replaced by the right hand
side of the rule. The details of what happens will be covered later.

The customary Axiom notation for patterns is actually a shorthand for a
longer, more general notation. Pattern variables can be made explicit
by using a percent ("%") as the first character of the variable name. To
say that a name stands for itself, you can prefix that name with a quote
operator ("'"). Although the current Axiom parser does not let you quote
an operation name, this more general notation gives you an alternative way
of giving the same rewrite rule:
<pre>
  rule log(%x) + log(%y) == log(x*y)
</pre>
This longer notation gives you patterns that the standard notation won't
handle. For example, the rule
<pre>
  rule %f(c * 'x) == c*%f(x)
</pre>
means "for all f and c, replace f(y) by c*f(x) when y is the product
of c and the explicit variable x".

Thus the pattern can have several adornments on the names that appear there.
Normally, all of these adornments are dropped in the substitution on the
right hand side. To summarize:
<hr/>
To enter a single rule in Axiom, use the following syntax:
<pre>
  rule lefthandside == righthandside
</pre>
The lefthandside is a pattern to be matched and the righthandside is its
substitution. The rule is an object of type
<a href="db.xhtml?RewriteRule">RewriteRule</a> that can be assigned to a
variable and applied to expressions to transform them.
<hr/>
Rewrite rules can be collected into rulesets so that a set of rules can be
applied at once. Here is another simplification rule for logarithms.
<pre>
  rule y*log(x) == log(x**y)
</pre>
for any x and y. If instead of giving a single rule following the reserved
word rule you give a "pile" of rules, you create what is called a
ruleset. Like rules, rulesets are objects in Axiom and can be assigned to
variables. You will find it useful to group commonly used rules into
input files, and read them in as needed. Create a ruleset named logrules.
<ul>
 <li>
  <input type="submit" id="p4" class="subbut" 
    onclick="makeRequest('p4');"
    value="logrules:=rule (log(x)+log(y)==log(x*y) ; y*log(x)==log(x^y))" />
  <div id="ansp4"><div></div></div>
 </li>
</ul>
Again, create an expression f containing logarithms.
<ul>
 <li>
  <input type="submit" id="p5" class="subbut" 
    onclick="makeRequest('p5');"
    value="f:=a*log(sin x)-2*log x" />
  <div id="ansp5"><div></div></div>
 </li>
</ul>
Apply the ruleset logrules to f.
<ul>
 <li>
  <input type="submit" id="p6" class="subbut" 
    onclick="handleFree(['p4','p5','p6']);"
    value="logrules f" />
  <div id="ansp6"><div></div></div>
 </li>
</ul>
We have allowed pattern variables to match arbitrary expressions in the
above examples. Often you want a variable to match onlyh expressions 
satisfying some predicate. For example, you may want to apply the
transformation 
<pre>
  y*log(x) == log(x^y)
</pre>
only when y is an integer. The way to restrict a pattern variable y by a
predicate f(y) is by using a vertical bar "|", which means "such that",
in much the same way it is used in function definitions. You do this only
once but at the earliest (meaning deepest and leftmost) part of the pattern.
This restricts the logarithmic rule to create integer exponents only.
<ul>
 <li>
  <input type="submit" id="p7" class="subbut" 
    onclick="makeRequest('p7');"
    value="logrules2:=rule (log(x)+log(y)==log(x*y) ; (y | integer? y)*log(x)==log(x^y))" />
  <div id="ansp7"><div></div></div>
 </li>
</ul>
Compare this with the result of applying the previous set of rules.
<ul>
 <li>
  <input type="submit" id="p8" class="subbut" 
    onclick="handleFree(['p5','p8']);"
    value="f" />
  <div id="ansp8"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p9" class="subbut" 
    onclick="handleFree(['p5','p7','p9']);"
    value="logrules2 f" />
  <div id="ansp9"><div></div></div>
 </li>
</ul>
You should be aware that you might need to apply a function like
<a href="dbopinteger.xhtml">integer</a> within your predicate expression
to actually apply the test function. Here we use 
<a href="dbopinteger.xhtml">integer</a> because n has type 
<a href="dbexpressioninteger.xhtml">Expression Integer</a> but
<a href="dbopevenq.xhtml">even?</a> is an operation defined on the integers.
<ul>
 <li>
  <input type="submit" id="p10" class="subbut" 
    onclick="makeRequest('p10');"
    value="evenRule:=rule cos(x)^(n | integer? n and even? integer n)==(1-sin(x)^2)^(n/2)" />
  <div id="ansp10"><div></div></div>
 </li>
</ul>
Here is the application of the rule.
<ul>
 <li>
  <input type="submit" id="p11" class="subbut" 
    onclick="handleFree(['p10','p11']);"
    value="evenRule(cos(x)^2)" />
  <div id="ansp11"><div></div></div>
 </li>
</ul>
This is an example of some of the usual identities involving products of sines and cosines.
<ul>
 <li>
  <input type="submit" id="p12" class="subbut" 
    onclick="makeRequest('p12');"
    value="sinCosProducts:=rule (sin(x)*sin(y)==(cos(x-y)-cos(x+y))/2 ; cos(x)*cos(y)==(cos(x-y)+cos(x+y))/2 ; sin(x)*cos(y)==(sin(x-y)+sin(x+y))/2 )" />
  <div id="ansp12"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p13" class="subbut" 
    onclick="makeRequest('p13');"
    value="g:=sin(a)*sin(b)+cos(b)*cos(a)+sin(2*z)*cos(2*a)" />
  <div id="ansp13"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p14" class="subbut" 
    onclick="handleFree(['p12','p13','p14']);"
    value="sinCosProducts g" />
  <div id="ansp14"><div></div></div>
 </li>
</ul>
Another qualification you will often want to use is to allow a pattern to
match an identity element. Using the pattern x+y, for example, neither x 
nor y matches the expression 0. Similarly, if a pattern contains a product
x*y or an exponentiation x^y, then neither x nor y matches 1. If identical
elements were matched, pattern matching would generally loop. Here is an
expansion rule for exponentials.
<ul>
 <li>
  <input type="submit" id="p15" class="subbut" 
    onclick="makeRequest('p15');"
    value="exprule:=rule exp(a+b)==exp(a)*exp(b)" />
  <div id="ansp15"><div></div></div>
 </li>
</ul>
This rule would cause infinite rewriting on this if either a or b were
allowed to match 0.
<ul>
 <li>
  <input type="submit" id="p16" class="subbut" 
    onclick="handleFree(['p15','p16']);"
    value="exprule exp x" />
  <div id="ansp16"><div></div></div>
 </li>
</ul>
There are occasions when you do want a pattern variable in a sum or product
to match 0 or 1. If so, prefix its name with a "?" whenever it appears in
a left-hand side of a rule. For example, consider the following rule for the
exponential integral
<pre>
  integral((y+exp x)/x,x) == integral(y/x,x)+Ei x
</pre>
for any x and y. This rule is valid if y=0. One solution is to create a
<a href="db.xhtml?Ruleset">Ruleset</a> with two rules, one with and one
without y. A better solution is to use an "optional" pattern variable. 
Define rule eirule with a pattern variable ?y to indicate that an
expression may or may not occur.
<ul>
 <li>
  <input type="submit" id="p17" class="subbut" 
    onclick="makeRequest('p17');"
    value="eirule:=rule integral((?y+exp x)/x,x)==integral(y/x,x)+Ei x" />
  <div id="ansp17"><div></div></div>
 </li>
</ul>
Apply rule eirule to an integral without this term.
<ul>
 <li>
  <input type="submit" id="p18" class="subbut" 
    onclick="handleFree(['p17','p18']);"
    value="eirule integral (exp m/m,m)" />
  <div id="ansp18"><div></div></div>
 </li>
</ul>
Apply rule eirule to an integral with this term.
<ul>
 <li>
  <input type="submit" id="p19" class="subbut" 
    onclick="handleFree(['p17','p19']);"
    value="eirule integral(sin m+exp m/m,m)" />
  <div id="ansp19"><div></div></div>
 </li>
</ul>
Here is one final adornment you will find useful. When matching a pattern
of the form x+y to an expression containing a long sum of the form
a+...+b, there is no way to predict in advance which subset of the sum
matches x and which matches y. Aside from efficiency, this is generally
unimportant since the rule holds for any possible combination of matches
for x and y. In some situations, however, you many want to say which
pattern variable is a sum (or product) of several terms, and which should
match only a single term. To do this, put a prefix colon (":") before the
pattern variable that you want to match mutliple terms. The remaining rules
involve operators u and v.
<ul>
 <li>
  <input type="submit" id="p20" class="subbut" 
    onclick="makeRequest('p20');"
    value="u:=operator 'u" />
  <div id="ansp20"><div></div></div>
 </li>
</ul>
These definitions tell Axiom that u and v are formal operators to be
used in expressions.
<ul>
 <li>
  <input type="submit" id="p21" class="subbut" 
    onclick="makeRequest('p21');"
    value="v:=operator 'v" />
  <div id="ansp21"><div></div></div>
 </li>
</ul>
First define myRule with no restrictions on the pattern variables x and y.
<ul>
 <li>
  <input type="submit" id="p22" class="subbut" 
    onclick="makeRequest('p22');"
    value="myRule:=rule u(x+y)==u x + v y" />
  <div id="ansp22"><div></div></div>
 </li>
</ul>
Apply myRule to an expression.
<ul>
 <li>
  <input type="submit" id="p23" class="subbut" 
    onclick="handleFree(['p20','p21','p22','p23']);"
    value="myRule u(a+b+c+d)" />
  <div id="ansp23"><div></div></div>
 </li>
</ul>
Define myOtherRule to match several terms so that the rule gets applied
recursively.
<ul>
 <li>
  <input type="submit" id="p24" class="subbut" 
    onclick="makeRequest('p24');"
    value="myOtherRule:=rule u(:x+y)==u x + v y" />
  <div id="ansp24"><div></div></div>
 </li>
</ul>
Apply myOtherRule to the same expression
<ul>
 <li>
  <input type="submit" id="p25" class="subbut" 
    onclick="handleFree(['p20','p21','p24','p25']);"
    value="myOtherRule u(a+b+c+d)" />
  <div id="ansp25"><div></div></div>
 </li>
</ul>
Here are some final remarks on pattern matching. Pattern matching provides
a very useful paradigm for solving certain classes of problems, namely, 
those that involve transformations of one form to another and back. However,
it is important to recognize its limitations.

First, pattern matching slows down as the number of rules you have to
apply increases. Thus it is good practice to organize the sets of rules
you use optimally so that irrelevant rules are never included.

Second, careless use of pattern matching can lead to wrong answers. You
should avoid pattern matching to handle hidden algebraic relationships
that can go undetected by other programs. As a simple example, a symbol
such as "J" can easily be used to represent the square root of -1 or some
other important algebraic quantity. Many algorithms branch on whether an
expression is zero or not, then divide by that expression if it is not. If 
you fail to simplify an expresison involving powers of J to -1, algorithms
may incorrectly assume an expression is no-zero, take a wrong branch, and
produce a meaningless result.

Pattern matching should also not be used as a substitute for a domain. In
Axiom, objects of one domain are transformed to objects of other domains
using well-defined <a href="dbopcoerce.xhtml">coerce</a> operations. 
Pattern matching should be used on objects that are all of the same type.
Thus if your application can be handled by type 
<a href="db.xhtml?Expression">Expression</a> in Axiom and you think you 
need pattern matching consider this choice carefully. You may well be
better served by extending an existing domain or by building a new domain
of objects for your application.
 </body>
</html>
axiom-hypertex-data 20120501-8 / usr / share / doc / axiom-doc / hypertex / funpatternmatching.xhtml
