RE: [Axiom-developer] RE: symbolic manipulation of expressions in Axiom

[Bill Page]

On April 1, 2007 7:02 PM Gaby wrote:

> ...
> | > 
> | > and I'm saying that once you've added them [to InputForm],
> | > as for Expression T, you'll see no difference.  Adding them
> | > is precisely what people do when they start "symbolic
> | > computation" and "simplification".
> | 
> | No. I disagree at a deep level. I think what is done in the
> | Axiom library is completely different. What Axiom is doing is
> | fundamentally *algebraic*. Simplification of symbolic expressions
> | does not require any algebra.
> 
> Well, I do disagree there.  If you don't do any algebra, you
> cannot manage your symbolic expressions.

We need to define exactly what we mean by "algebra". I think
your definition is probably much more general then mine. What
I mean very specifically would probably normally be called
abstract algebraic data types - objects that obey a specific
set of axioms and which necessarily have some (normally hidden)
internal representation. The fact that a representation exists
is the essential part, not the specific details of that
representation. The representation takes something that is
"free" over some syntactically defined set of expressiones
and maps them into some other domain (Rep).

  Interpret: Expressions --> Rep

Formally % is the image of Expression in Rep. Looking at
Interpret in reverse as "fibre bundles" is what makes this
"algebraic".

> 
> For a symbolic expression, you first need to chose on a 
> "standard form" (or "normal form", depending on your
> religion).
> 

In Axiom's case coercion of % to OutputForm defines a
distinguished section of the representation bundle. I think
that (roughly) corresponds to what you called a "standard form".
That is why expressions that are interpreted as members of a
given domain appear to be "simplified" in particular ways.
But really simplification is not the goal. The goal is an
algebraic computation.

> The fundamental reason why "simplify" is so ill-defined for
> symbolic expressions is precisely that whatever they have
> to do is profoundly influenced by the algebra of the standard
> form structures.
> 

Are you thinking of standard forms as representatives of
some equivalence class of expressions? If so, then I think
maybe we agree but are just using different words.

> 
> For example, when you see something like
> 
>      x^2 * 3 * x^(-4) * 5/89
> 
> you have to come up with algebraic computations for the
> "constant" parts, and for the exponent parts -- many
> symbolic manipulation systems assume tht "*" is commutative.

In Axiom what we say is that we have a problem of assigning
functions to all of the operators in this expression. We do
this by either explicitly, or in various implicit ways,
specify the domains involved. Coercions to these domains
are performed as required and we actually mechanically
compute a result by applying the interpretation via the
interface provided with each domain. The final result is
a member of some domain. Finally a coercion of this member
to the OutputForm domain is displayed to the user.

Is that what you mean by "algebraic computations"?

> 
> | For example to simplify an expression it is not necessary
> | to instantiate an object which directly represents a
> | polynomial in the way polynomials are represented in Axiom.
> 
> But, you do need to come up with standard form that requires
> you do define algebra rules on the objects.  In particular,
> you do need to make alegbraic assumptions regarding the
> polynomials.

I would like to understand better how standard forms define
algebraic rules. Can you give an example or suggest an
appropriate reference?

> 
> | All that you need to do is to apply a set of re-write rules
> | that accomplish (or not) your desired goal.
> 
> But, the rewrite rules do embody algebraic semantics.

That is not clear to me. I am not exactly sure here what you
mean by "algebraic semantics". Reference?

> 
> | On the other hand creating a polynomial *object* (and some
> | other algebraic objects) is exactly what Axiom does in the
> | Expression domain.
> 
>  simplify(differentiate (sin(x) + x, x)^2 + (sin(x) + x)^2)
> 

What is this example intended to show?

(1) -> sin(x) + x

   (1)  sin(x) + x
                                      Type: Expression Integer

(2) -> differentiate(%,x)

   (2)  cos(x) + 1
                                      Type: Expression Integer

(3) -> %^2

              2
   (3)  cos(x)  + 2cos(x) + 1
                                       Type: Expression Integer

(4) -> %+(sin(x)+x)^2

              2                     2              2
   (4)  sin(x)  + 2x sin(x) + cos(x)  + 2cos(x) + x  + 1
                                        Type: Expression Integer

(5) -> simplify %

                               2
   (6)  2x sin(x) + 2cos(x) + x  + 2
                                        Type: Expression Integer

(7) -> kernels %

   (7)  [sin(x),cos(x),x]
                             Type: List Kernel Expression Integer

Yes the internal representation of

  sin(x)+x

and the things which we derive from it are all

  Fraction SparseMultivariatePolynomial(Integer,Kernel %)

> 
> | > [...]
> | > 
> | > | > Also, be aware than the Axiom designers, in many places,
> | > | > thought of Expression as the general domain for symbolic
> | > | > manipulation and have appropriate hardwired type inference
> | > | > rules in the interpreter.
> | > | > 
> | > | 
> | > | Of course that is no problem. If you are able to read and
> | > | understand Stephen Watt's paper on this subject, I am sure
> | > | that this would be clear to you.
> | > 
> | > That has nothing to do with what I'm saying. 
> | >
> | 
> | ??? But that is exactly what I am saying.
> 
> "that is exactly" what?

The discussion of symbolic computation versus computer algebra
in Stephen Watt's paper.

> ...
> | 
> | It is possible that I do not understand "the distinction
> | between Expression T and InputForm that you are concerned
> | with", but I did think that my concern in this regard was
> | the same as yours. If that is the case then I strongly
> | disagree with your conclusion.
> | I also feel strongly that understanding this distinction
> | is critical to understanding what is different about Axiom
> | as a computer algebra system, so I have a lot of motivation
> | to continue this discussion until we can find some agreement.
> 
> I believe I understand what makes the difference between Axiom
> and other CASes,

I would like to say explicitly what this difference is for you.
Would you agree that other CASes do not do computer algebra
the sense that I described above but that Axiom does work this
way? 

> but I think both you and me seem to profoundly between the
> outcome of InputForm augmented with all that is necessary to
> mimic other CASes and Expression T.

That was *not* my intention in the email that started this
thread. What I said was that I thought InputForm was an
appropriate domain in which to represent symbolic manipulation
of expressions and what I thought was lacking was a convenient
coercion of InputForm to OutputForm that made this more
obvious. As it turns out, InputForm does in fact export a
function which performs this conversion (expr:%->OutputForm)
but this function is not automatically involved as a coercion
by the Axiom interpreter. Instead it uses a coercion to
something that looks more like an Sexpression. I would have
preferred that Axiom use expr as the automatic coercion and
display as an SExpression-like output as a separate function.
But in any case, I now think that InputForm has all that is
needed for manipulating expression symbolically.

This is very different than suggesting that InputForm should
be modified to implement symbolically some of the algebra
that is already implemented by Expression. I never said that!

>  Consequently I do not see the link

Nor do I. I guess that is a result of some confusion over what
you thought I initial proposed. Perhaps Martin also had this
wrong impression - judging from the tone of his original
reply.

> ... 
> | Would it help if I try to described more formally my
> | understanding of exactly how Axiom captures matematical
> | semantics in terms of the representation of objects and
> | how that differs from more syntactical things like term
> | re-writing? Or do continue to insist that we not talk
> | about representation?
> 
> I believe the distinction must be explained through interfaces.
> If we must resort to internal representations, then the
> distinction is artificial, not fundamental; therefore, we can
> ignore it as being merely non-fundamental artefacts.
> 

I started to do this anyway earlier in this email. I don't
think it is necessary to deal with the details of any specific
internal representation - only that this representation defines
a mapping that in turn defines the algebraic properties of the
domain.

Regards,
Bill Page.