This type of transformation is often required, and this chapter discusses this issue. The types of transformations required will be discussed, along with possible implementation schemes.
The first, basic type of expression one would like to be able to match is an expression like ...*a^n*...*a^m*..., which in its most general form discovers that an expression only contains multiplications, and that it contains a factor a^n and a factor a^m. We would like this expression to be changed into ...*a^(n+m)*....
Another example is simplification using trigonometric identities, where a term containing two trigonometric factors is reduced to two terms with each one trigonometric factor. Identities like
are easy to write down in one line. Ideally, Yacas would allow a programmer to write this down in one line and then have a global pattern matcher recognize when this pattern is applicable, and apply the transformation rule.
Other examples include:
and for a given integer k:
These are all patterns that could be found within one term containing only factors.
In this case, it is possible to write this expression as:
which in turn can be simplified further, by setting
yielding
and thus y= -1 , Exp(x/2)= -1 after factoring. It then follows that the solution is x=I*2*Pi:
In> Solve((Exp(x/2)+1)^2==0,x) Out> Complex(0,2*Pi); In> f(x):=N(Exp(x)+2*Exp(x/2)+1) Out> True; In> f(Complex(0,2*Pi)) Out> 0; |
For instance, for trigonometric identities, there is sometimes an exact result if the argument is a rational number times Pi. One would like to be able to recognize Pi/2 , 1/2*Pi , Pi*1/2 , 4*Pi*1/8, and perhaps even 0.5*Pi as being half Pi.
With integration, there is often an antiderivative for an expression if an argument can be written as a*x+b where x is the variable being integrated over, and a and b are constants that do not depend on x.
Furthermore, in keeping with the rest of the design of the language, it should be possible to write only a few lines of code in order to specify patterns to be matched and transformations to be performed.
...*a^n*...*a^m*... .
One solution is to do it in scripts. One needs to gather all the factors. The first option is to write a custom bit of code for this type of transformation, where all factors are gathered in a list, combining the symbol with its exponent. While traversing the expression, one adds items to this list.
For instance for an expression a*b^2*c*d*a one would first add (a,1), then (b,2), (c,1) and (d,1). Lastly, for the last factor, a, the system could notice that it was already in the list, and just update this item to (a,2). One would end up with the set ((a,2),(b,2),(c,1),(d,1)). This could be called an internal representation.
After this process finishes, one can traverse this list, producing the required result a^2*b^2*c*d.
This process can be generalized. The steps involved are:
The above scheme is flexible, in that the specific method of adding a sub-expression to the already existing database can be customized for different types of simplification or pattern matching. transformations could even be done in-place. The specific algorithm for adding a term to the database then acts as a filter.
The difficult part is to choose the form of the database, as that ultimately defines the types of transformations and simplifications that are possible.
When only transformations within one term are needed, the situation is not too difficult.
$$ (a[1][1] * ... *a[1][n1]) / (b[1][1] * ... * b[1][m1]) + ... + (a[p][1] * ... *a[p][np]) / (b[p][1] * ... * b[p][mp]) $$
Eg. one could write an expression as a set of terms, where each term is a rational function, consisting of a numerator and denominator, each with just simple factors. One could then process each term, and maintain a database for each term. Thus one could readily simplify a^n/a^m to a^(n-m), or (n+1)! /n! to n+1. The trigonometric simplification scheme described earlier in this chapter would be more sophisticated, as it would require changing one term to two (as a multiplication within a term is changed into an addition of two terms).
For instance, the database might already have an entry representing a^n. When a new term a^m is encountered, one would want to combine these two into a^(n+m). This is easy to do with custom code that can directly access the database internal representation.
At the same time, one would ideally want to specify this transformation using notation similar to
In stead of writing custom hand-written code for this transformation, one would want a system were the a^n part is matched in the database and the a^m part in the expression being processed. The result, a^(n+m), would be the result, and one would want the system to remove the a^n from the database and put back a^(n+m).
Actually, for efficiency reasons, one would want the system to change a^n to a^(n+m) in the database. But this is a very specific example where this is easily possible. For transformation rules like
one needs a database for a rational function, and one needs to remove one factor and replace it with many other factors.
In the case of the trigonometric identities, one needs to replace something of the form A*B to something of the form C+D, which requires actually removing the actual term at hand (and not just one factor) and replace it with two terms.
One option is to have the a^n*a^m=a^(n+m) simplification be performed automatically, then convert the entire expression into internal representation with one additional facility in the internal representation that one additional collection is made; one can collect factors or terms that one knows will be relevant for the simplification. when simplifying factorials, one can collect all factorials in a special part of the internal representation so they are all grouped together. The algorithm can then proceed to process only these parts. For instance,
could be converted to
So that the left side part can be further simplified, resulting in
This can be a problem when the expression is brought into the form described above, as this normalization step would first convert (a+b)/c to a/c+b/c. This breaks up the expression. If a+b and c had common factors, this is now lost.
Thus the rational expression first needs to be scanned for greatest common divisors before being split up.
The problem of finding greatest common divisors is a little bit more complicated than described here. For instance the following expression
is actually equivalent to
This can only be discovered if the first and the last term are combined into one, leaving out the middle term. Perhaps the fact that the two denominators have a greatest common divisor not equal to one can be used to find terms that can be combined.
Another option is to not split up rational terms when there is an addition involved in the denominator, as little is expected to be gained from the simplification any way after removing greatest common divisors. In stead, the numerator and denominator could be simplified as sub-expressions in their own simplification step.
This scheme might not be the most suitable solution when matching patterns for use in other algorithms. In such cases one is generally interested in whether an expression can possibly be brought into a specific form, which does not necessarily match the form the simplifier brings the expression in.
Suppose we want to find out if an expression matches the form a*x+b where both a and b don't depend on x. Further more, the algorithm is likely to need the actual values for a and b.
If the algorithm for simplification described earlier were used, one would end up with a list of terms, each with lists of factors in the intermediate format. The information that is needed would be missing. For example:
would have to be written down as
before one can recognize that a*x+b fits, and find the exact forms for a and b.
In a sense the method for arriving at this stage is almost the same: first gather information, and then return the information in the requested form. The problem is that this feature, global pattern matching, requires more flexibility.
The fact that the algorithms and internal representation of the simplification scheme described above are not suited for this task can be seen from the following example; suppose we wanted to match a*x+b to the expression
One would want this expression written out as
so that the constants can readily be identified. However, as discussed in the section on rational terms, for simplification it is not wise to split up such rational terms. It is required for this example, however. The filtering step could be made more sophisticated so that this operation can be dealt with.
A more serious concern is with efficiency. Apart from splitting up the expression in too small chunks (one only needs a and b, and thus would only need to gather these), there is another danger: the conversion to internal representation continues until the full expression is processed.
In practice, while the expression is being processed, if custom code were written, the matcher could decide while matching, that the pattern will never fit, and terminate immediately. For example, a and b should be independent of x, so if a factor like Sin(x) is encountered the matching can stop immediately.
If the scheme described in the section dealing with simplification is to be used for general pattern matching also, another step needs to be added to it; the filter operation should be able to terminate the process when it decides early on that code further upstream will fail any way.
In this case, if Sin(b*a) were first converted to Sin(a*b), the system could readily collect terms and discover that the terms described above cancel each other out and result in zero.
For this, the system needs to impose an order for factors. For this, LessThan can be used. LessThan defines an ordering for atoms:
In> LessThan(a,b) Out> True; In> LessThan(b,a) Out> False; In> LessThan(2,a) Out> True; In> LessThan(2,1) Out> False; In> LessThan(a,"b") Out> False; |
Ordering for composed expressions can be created based on the LessThan function.
does not hold. This has consequences for a system that is trying to simplify the expression passed in. When gathering information to be stored in the database, what the operation is in fact doing is moving factors around until they are next to each other and can be combined. For instance,
would first be re-ordered to
which then readily converts to
Extending this system to also support non-commuting algebra involves disallowing these swaps. For groups of symbols, one could specify that two symbols do not commute. For the above example, supposing A and B do not commute, the resulting expression could then terminate as:
One step further would be to support commutation relations. Suppose that after one established that A and B do not commute, that the following relation holds:
Then the part of the expression B*A could be converted to A*B-C. This could then result in the expression:
Which then can be written as:
Factoring could then yield:
A potential risk is with the global transformation rules, which do not necessarily adhere to the rules for non-commuting algebras. A special non-commuting multiplication operator could be defined for this to guarantee that this is never a problem.
The difference between a problem stated and a solution given is a subtle one. From a mathematical standpoint,
In> Integrate(x,0,B)Cos(x) Out> Sin(B); |
And thus
Integrate(x,0,B)Cos(x) == Sin(B) |
is a true statement. Furthermore, the left hand side is mathematically equivalent to the right hand side. Working out the integration, to arrive at an expression that doesn't imply integration any more is generally perceived to be a more desirable result, even though the two sides are equivalent mathematically.
This implies that the statement of a set of equations declaring equalities is on a same footing as the resulting equations stating a solution:
If the value of x is needed, the right hand side is more desirable.
Viewed in this way, the responsibility of a Solve function could be to manipulate a set of equations in such a way that a certain piece of information can be pried from it (in this case the value of x==x(a,b,c).
A next step is to be able to use the result returned by a Solve operation.
In> x^2+y^2 Where x==2 And y==3 Out> 13; |
Solve can return one such solution tuple, or a list of tuples. The list of equations can be passed in to Solve in exactly the same way. Thus:
In> Solve(eq1,var) Out> a1==b1; In> Solve(eq1 And eq2 And eq3,varlist) Out> {a1==b1 And a2==b2,a1==b3 And a2==b4}; |
These equations can be seen as simple simplification rules, the left hand side showing the old value, and the right hand side showing the new value. Interpreted in that way, Where is a little simplifier for expressions, using values found by Solve.
Assigning values to the variables values globally can be handled with an expression like
solns := Solve(equations,{var1,var2}); {var1,var2} := Transpose({var1,var2} Where solns); |
Multiple sets of values can be applied:
In> x^2+y^2 Where {x==2 And y==2,x==3 And y==3} Out> {8,18}; |
This assigns the the variables lists of values. These variables can then be inserted into other expressions, where threading will fill in all the solutions, and return all possible answers.
Groups of equations can be combined, with
Equations := EquationSet1 AddTo EquationSet2 |
or,
Equations := Equations AddTo Solutions; |
Where Solutions could have been returned by Solve. This last step makes explicit the fact that equations are on a same footing, mathematically, as solutions to equations, and are just another way of looking at a problem.
The equations returned can go farther in that multiple solutions can be returned: if the value of x is needed and the equation determining the value of x is x:=Abs(a), then a set of returned solutions could look like:
Solutions := { a>=0 And x==a, a<0 And x== -a } |
The semantics of this list is:
either a >= 0 And x equals a, or a < 0 And x equals -a |
When more information is published, for instance the value of a has been determined, the sequence for solving this can look like:
In> Solve(a==2 AddTo Solutions,{x}) Out> x==2; |
The solution a<0 And x==-a can not be satisfied, and thus is removed from the list of solutions.
Introducing new information can then be done with the AddTo operator:
In> Solutions2 := (a==2 AddTo Solutions); Out> { a==2 And a>=0 And x==a, a==2 And a<0 And x==-a }; |
In the above case both solutions can not be true any more, and thus when passing this list to Solve:
In> Solve(Solutions2,{x}) Out> x==2; |
AddTo combines multiple equations through a tensor-product like scheme:
In> {A==2,c==d} AddTo {b==3 And d==2} Out> {A==2 And b==3 And d==2,c==d And b==3 And d==2}; In> {A==2,c==d} AddTo {b==3, d==2} Out> {A==2 And b==3,A==2 And d==2,c==d And b==3,c==d And d==2}; |
A list a,b means that a is a solution, OR b is a solution. AddTo then acts as a AND operation:
(a or b) and (c or d) => (a or b) Addto (c or d) => (a and c) or (a and d) or (b and c) or (b and d) |
Solve gathers information as a list of identities. The second argument is a hint as to what it needs to solve for. It can be a list of variables, but also "Ode" (to solve ordinary differential equations), "Trig" (to simplify for trigonometric identities), "Exp" to simplify for expressions of the form Exp(x), or "Logic" to simplify expressions containing logic. The "Logic" simplifier also should deal with a>2 And a<0 which it should be able to reduce to False.
Solve also leaves room for an 'assume' type mechanism, where the equations evolve to keep track of constraints. When for instance the equation x==Sin(y) is encountered, this might result in a solution set
y == ArcSin(x) And x>=-1 And x <= 1 |
Nevertheless, this chapter will try to specify a graphical user interface that services users other than power users.
The single big usability issue is currently that one already needs to know the system a bit before one can use it. The user is greeted with an intimidating flashing cursor, waiting for the user to enter a command. The user needs to know which commands are available, and when to use those commands. In short, the user, whether it is a new or experienced user, can be greatly helped with information that is more readily available.
The following sections describe the possible features a graphical front end could offer to facilitate these.
The user can then play around with some commands, and finally set up a file with code that will perform the calculation and run that file.
A graphical user interface offers the opportunity to allow the user to access relevant information more quickly than scanning the hundreds of pages of documentation (with the chance of getting lost).
Of course documentation in combination with examples that show how to do specific types of calculations go a long way when a user needs to find out how to do a specific calculation, or wants to know what is possible. However, a user interface might provide the required information more readily.
One solution might be to pop up a tip box with the possible ways the command can be completed.
When the user doesn't know which command to use in the first place, the system could provide a list of possible commands, perhaps categorized by type of operation. For each command a short blurb could be shown about what the routine does, when it is applicable, and perhaps some examples for the user to try out to get a handle on the command.
Arguably the last option is offered by the manual already.
The user can then use the example as a template for his own calculation. The user interface could even offer a facility to have a template for a calculation, where the user enters some final parameters for that specific calculation. With such a template, most of the work is already done, and all the user needs to do is change some parameters to reflect the calculation he wants to do.
A tree view of the source code, allowing a programmer to easily navigate through the code could be useful. As a project (and the code body) becomes larger and larger it becomes harder to find things in the scripts.
The idea behind the static code checkers is to check that coding standards are upheld, and to mark code that is dangerous and thus is likely to be buggy.
The following sections each describe one specific type of test. The static code analysis code can be found in codecheck.rep .
The rules that should be upheld are:
The interface check also assumes the code to consist of simple function definitions. It is meant to be used for the scripts in the standard scripts library. Exposing functionality to the outside world is usually less of a problem in one-off scripts to do specific calculations, for instance.
59 Temple Place, Suite 330 Boston, MA, 02111-1307 USA |
Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed.
This License is a kind of ``copyleft'', which means that derivative works of the document must themselves be free in the same sense. It complements the GNU General Public License, which is a copyleft license designed for free software.
We have designed this License in order to use it for manuals for free software, because free software needs free documentation: a free program should come with manuals providing the same freedoms that the software does. But this License is not limited to software manuals; it can be used for any textual work, regardless of subject matter or whether it is published as a printed book. We recommend this License principally for works whose purpose is instruction or reference.
A ``Modified Version'' of the Document means any work containing the Document or a portion of it, either copied verbatim, or with modifications and/or translated into another language.
A ``Secondary Section'' is a named appendix or a front-matter section of the Document that deals exclusively with the relationship of the publishers or authors of the Document to the Document's overall subject (or to related matters) and contains nothing that could fall directly within that overall subject. (For example, if the Document is in part a textbook of mathematics, a Secondary Section may not explain any mathematics.) The relationship could be a matter of historical connection with the subject or with related matters, or of legal, commercial, philosophical, ethical or political position regarding them.
The ``Invariant Sections'' are certain Secondary Sections whose titles are designated, as being those of Invariant Sections, in the notice that says that the Document is released under this License.
The ``Cover Texts'' are certain short passages of text that are listed, as Front-Cover Texts or Back-Cover Texts, in the notice that says that the Document is released under this License.
A ``Transparent'' copy of the Document means a machine-readable copy, represented in a format whose specification is available to the general public, whose contents can be viewed and edited directly and straightforwardly with generic text editors or (for images composed of pixels) generic paint programs or (for drawings) some widely available drawing editor, and that is suitable for input to text formatters or for automatic translation to a variety of formats suitable for input to text formatters. A copy made in an otherwise Transparent file format whose markup has been designed to thwart or discourage subsequent modification by readers is not Transparent. A copy that is not ``Transparent'' is called ``Opaque''.
Examples of suitable formats for Transparent copies include plain ASCII without markup, Texinfo input format, LaTeX input format, SGML or XML using a publicly available DTD, and standard-conforming simple HTML designed for human modification. Opaque formats include PostScript, PDF, proprietary formats that can be read and edited only by proprietary word processors, SGML or XML for which the DTD and/or processing tools are not generally available, and the machine-generated HTML produced by some word processors for output purposes only.
The ``Title Page'' means, for a printed book, the title page itself, plus such following pages as are needed to hold, legibly, the material this License requires to appear in the title page. For works in formats which do not have any title page as such, ``Title Page'' means the text near the most prominent appearance of the work's title, preceding the beginning of the body of the text.
You may also lend copies, under the same conditions stated above, and you may publicly display copies.
If the required texts for either cover are too voluminous to fit legibly, you should put the first ones listed (as many as fit reasonably) on the actual cover, and continue the rest onto adjacent pages.
If you publish or distribute Opaque copies of the Document numbering more than 100, you must either include a machine-readable Transparent copy along with each Opaque copy, or state in or with each Opaque copy a publicly-accessible computer-network location containing a complete Transparent copy of the Document, free of added material, which the general network-using public has access to download anonymously at no charge using public-standard network protocols. If you use the latter option, you must take reasonably prudent steps, when you begin distribution of Opaque copies in quantity, to ensure that this Transparent copy will remain thus accessible at the stated location until at least one year after the last time you distribute an Opaque copy (directly or through your agents or retailers) of that edition to the public.
It is requested, but not required, that you contact the authors of the Document well before redistributing any large number of copies, to give them a chance to provide you with an updated version of the Document.
If the Modified Version includes new front-matter sections or appendices that qualify as Secondary Sections and contain no material copied from the Document, you may at your option designate some or all of these sections as invariant. To do this, add their titles to the list of Invariant Sections in the Modified Version's license notice. These titles must be distinct from any other section titles.
You may add a section entitled ``Endorsements'', provided it contains nothing but endorsements of your Modified Version by various parties -- for example, statements of peer review or that the text has been approved by an organization as the authoritative definition of a standard.
You may add a passage of up to five words as a Front-Cover Text, and a passage of up to 25 words as a Back-Cover Text, to the end of the list of Cover Texts in the Modified Version. Only one passage of Front-Cover Text and one of Back-Cover Text may be added by (or through arrangements made by) any one entity. If the Document already includes a cover text for the same cover, previously added by you or by arrangement made by the same entity you are acting on behalf of, you may not add another; but you may replace the old one, on explicit permission from the previous publisher that added the old one.
The author(s) and publisher(s) of the Document do not by this License give permission to use their names for publicity for or to assert or imply endorsement of any Modified Version.
The combined work need only contain one copy of this License, and multiple identical Invariant Sections may be replaced with a single copy. If there are multiple Invariant Sections with the same name but different contents, make the title of each such section unique by adding at the end of it, in parentheses, the name of the original author or publisher of that section if known, or else a unique number. Make the same adjustment to the section titles in the list of Invariant Sections in the license notice of the combined work.
In the combination, you must combine any sections entitled ``History'' in the various original documents, forming one section entitled ``History''; likewise combine any sections entitled ``Acknowledgements'', and any sections entitled ``Dedications''. You must delete all sections entitled ``Endorsements.''
You may extract a single document from such a collection, and distribute it individually under this License, provided you insert a copy of this License into the extracted document, and follow this License in all other respects regarding verbatim copying of that document.
If the Cover Text requirement of section 3 is applicable to these copies of the Document, then if the Document is less than one quarter of the entire aggregate, the Document's Cover Texts may be placed on covers that surround only the Document within the aggregate. Otherwise they must appear on covers around the whole aggregate.
Each version of the License is given a distinguishing version number. If the Document specifies that a particular numbered version of this License "or any later version" applies to it, you have the option of following the terms and conditions either of that specified version or of any later version that has been published (not as a draft) by the Free Software Foundation. If the Document does not specify a version number of this License, you may choose any version ever published (not as a draft) by the Free Software Foundation.
Copyright (C) YEAR YOUR NAME. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation; with the Invariant Sections being LIST THEIR TITLES, with the Front-Cover Texts being LIST, and with the Back-Cover Texts being LIST. A copy of the license is included in the section entitled ``GNU Free Documentation License''. |
If you have no Invariant Sections, write ``with no Invariant Sections'' instead of saying which ones are invariant. If you have no Front-Cover Texts, write ``no Front-Cover Texts'' instead of ``Front-Cover Texts being LIST''; likewise for Back-Cover Texts.
If your document contains nontrivial examples of program code, we recommend releasing these examples in parallel under your choice of free software license, such as the GNU General Public License, to permit their use in free software.