On 5 April 2015 at 17:43, Waldek Hebisch <[email protected]> wrote:
> ...
> The discussion is more about equality and builtin simplifications.
> We could use representation like above for Expression(Integer).
> But then we would have to provide special code to implement
> simplifications due to associative law, distributive law, etc.
>
I agree that the main point of the discussion is equality. Although
caching is involved, performance is not the main issue. As I now
understand it, the point of caching kernels is to dynamically
establish a set of canonical representatives.
> For Expression(Integer) user expectation is that say 'x*(y + z)'
> is equal to 'y*x + x*z' and we implement equality so that this
> is true.
At the risk of unnecessarily complicating your example which I presume
was intended to address other issues, I would say that it is not
accurate to say that "we implement equality so this is true". In fact
it is not so easy even to represent 'x*(y+z)' as something of type
Expression and if we try we get:
(1) -> y*x+x*z=x*paren(y+z)
(1) x z + x y= x(z + y)
Type: Equation(Expression(Integer))
(2) -> test %
(2) false
Type: Boolean
It is a good question perhaps whether or not it is a good thing that
Expression considers these two expressions not equal.
This needs some explanation. Expression is based first of all on
polynomials (SparseMultivariatePolynomial to be precise). In this
domain multiplication necessarily distributes over addition:
(3) -> x*(y+z)
(3) x z + x y
Type: Polynomial(Integer)
So at a fundamental level this equality is inevitable
(4) -> y*x+x*z=x*(z+y)
(4) x z + x y= x z + x y
Type: Equation(Polynomial(Integer))
In order to write 'x*(z+y)' in Expression and have it stay that way we
need the help of a special operator, i.e. 'paren', which really does
nothing but displays as parenthesis. The representation here is still
as a polynomial but now, in addition to variables x,y, and z, we also
have the kernel 'paren(z+y)' which at the level of polynomials is
treated like just another variable.
But Expression does provide
(5) -> distribute(x*paren(y+z))
(5) x z + x y
Type: Expression(Integer)
> For logic formula user do not expect such simplifications,
> so it is enough to provide equality essentially as trees. I other
> words for your purpose you can just use equality from representation.
> Of course, you could get more ambitious and say that two formulas
> are equal in your domain if and only if they are logically equivalent.
> For pure Boolean propositional logic there are representations with
> such property, namely disjunctive (or conjunctive) normal forms
> or binary decision diagrams. But if you enrich your logic
> a bit then you would have similar (probably worse) problems
> to the ones appearing in Expression(Integer).
>
Yes. Although FriCAS does do a remarkably good job of defining
equality in Expression in terms of canonical forms - especially as
extended for kernels, I am unconvinced that this is possible in
general, that is for the case of "mathematical equality". Worse I
suppose, is that I do not know when or how the current algorithm might
fail. I am interested instead in the details of efficiently
representing equality as a quotient (at least in part). A simple
example of this might be representing equality in formal fractions
without the using GCD cancellation to obtain a canonical form. Or this
old example of defining integers in terms of natural numbers:
http://axiom-wiki.newsynthesis.org/SandBoxDefineInteger
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
