Bill Page wrote:
>
> Waldek,
>
> I would like to continue the discussion in this thread a little even
> if it goes somewhat beyond the scope of the original question.
>
> On Thu, Mar 17, 2011 at 5:39 PM, you wrote:
> >
> > Basic result is theorem of Richardson which says that what we would
> > like to have is impossible (problem of deciding if an expression
> > is zero is undecidable). =A0Generalities are niecely described
> > in Davenport, Siret, Tournier book (look for canonical form):
> >
> > http://staff.bath.ac.uk/masjhd/masternew.pdf
> >
>
> What you are describing is the situation when equality is "canonical",
> i.e. when equality on the domain is the same as the equality on its
> underlying representation. Is this the case for Expression?
'=' for expressions is equality of representations. This not
always agrees with mathematical equality.
> In
> principle a domain can use a non-canonical representation and then
> define equality in a computationally intensive manner or even
> incomplete (possibly non-terminating) manner. But FriCAS does not
> currently permit equality to be anything other than Boolean valued.
'=' may produce whatever type we need. The real problem is that
result of equality tests is used to make decisions in code and
having say 'if' the 'then' part either will be executed or not,
which forces boolean result. So FriCAS premits equality of
arbitrary type, but useful equality is boolean (no matter if
in FriCAS or in other system). In principle equality can
raise exceptions ("can not decide") but that does not change
too much.
>
> >
> > Details of representaion used and empleyed "simplifications" vary
> > from system to system. =A0FriCAS expression is a parametric domain.
> > If nothing interesting is known about the parameter, then FriCAS
> > represents expression essentially as trees and does almost no
> > simplifications.
>
> Could you give an example of defining Expression over a domain where
> "nothing interesting is known"? I tried several things but so far I
> have been unable to produce an example of a value in such a domain.
>
For experiments I am using the following domain:
)abbrev domain IBT IntegerAsComparable
IntegerAsComparable : Join(BasicType, Comparable,
ConvertibleTo Pattern Integer, PatternMatchable(Integer)) with
0 : () -> %
1 : () -> %
_- : % -> %
coerce : Integer -> %
coerce : % -> Integer
== Integer add
coerce(n : Integer) : % == n pretend %
coerce(x : %) : Integer == x pretend Integer
after you compile it you can do:
ET:=Expression(IntegerAsComparable)
(6) -> 1::ET
(6) 1
Type: Expression(IntegerAsComparable)
(7) -> sin := operator 'sin
(7) sin
Type: BasicOperator
(8) -> sin(1::ET)
(8) sin(1)
Type: Expression(IntegerAsComparable)
(9) -> _+ := operator '_+
(9) +
Type: BasicOperator
(10) -> sin(_+(1::ET, 2::ET))
(10) sin(+(1,2))
Type: Expression(IntegerAsComparable)
Basically, declare whatever operators you need and build a tree
from them. You can also analyse the tree and rewrite it.
Currently tree rewriting is rather unpleasent because pattern
matching does not work on general expressions. But it is not
hard to extend pattern matcher (I am experimenting with such an
extension), the main problem is that currently pattern matcher
assumes that '*' is commutative which is not appropriate for
fully general expressions (pattern matcher also assumes that
'+' is commutative but I feel that this is acceptable: using
'+' for noncommutative operation would be quite confusing,
while noncommutative '*' happens quite frequently).
> > ...
> > If you do not go into details it is very similar to what other
> > systems do, but details differ. =A0AFAIK officialy Mathematica
> > uses pure tree representation for expressions but almost
> > surely converts to something like rational functions of
> > kernels for computations.
>
> I know Maple fairly well and I would say that this does not accurately
> describe what Maple does. Besides very simple "automatic"
> simplifications, Maple does very little re-writing of the original
> input expression. All the real work is done by operations applied
> later to the expression tree such as "simplify", "expand" etc.
>
That I consider detail.
> I FriCAS (and other incarnations of Axiom) it seems to me that usually
> 'simply' does very little. Effects like '
>
> How could one distinguish between a "pure tree representation" versus
> "rational functions of kernels" in Mathematica. Aren't these both
> "expression trees"? How is this different from simply rewriting
> expression trees?
If system internally changes representation and does not expose
any relatad operation than as long as it works correctly you
should not be able observe this from results. External
observer could make some deductions based on timing and bugs,
but in practice if you want to discuss this deeper you need
to find insider willing to share information.
> > =A0Macsyma/Maxima give user a choice between
> > tree representation and rational function representation,
> > but sometimes automatically switches representations.
> >
>
> Like Maple in Maxima there are operations such as "full_simplify"
> which attempt to reduce expressions to some canonical "simple" form.
> It seems to me that most automatic simplifications are avoided.
>
> I think Reduce is a good example of a CAS where there is a serious
> attempt to automatically reduce expressions to canonical form but even
> here there are many times when this must be avoided for specific types
> of calculations.
>
Personally I think that FriCAS is doing too much simplifications
automatically. For example most special functions can be
represented as instances of Meijer G function. We could
internally implement some algorithms only for Meijer G function
and convert to/from Meijer G form as needed. But if we
allow any automatic simplification which changes Meijer G
to simpler form, then algorithms based on Meijer G representation
may be broken.
This is a bit tricky because currently some parts of FriCAS
assume very eager simplification (for example 'numeric' would
be broken otherwise), while in other places we depend on
having very specific form (and simplifications that would
change such form are not allowed).
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
