Re: [Axiom-math] POLY INT =\\= UP(x, INT)

[Dylan Thurston]

(This conversation on the type heirarchy seems to be a little split
between axiom-math and axiom-developer.  I think axiom-math is the more
appropriate forum; please followup there.)

On Fri, Oct 10, 2003 at 02:55:07AM -0400, William Sit wrote:
> Dylan Thurston wrote:
> > On Wed, Oct 08, 2003 at 05:20:20PM -0400, Page, Bill wrote:
> > > SetCategory exports only one function, = . ...
> > 
> > I was shocked by this, so I went and checked.  It's worse than that:
> > SetCategory exports equality, printing (standard and LaTex), and
> > hashing.  This was my major peeve with the Haskell type system (in
> > Haskell terms, Print and Eq are parents of the Num class).
> 
> There seems to be some misunderstanding of the inheritance mechanism
> of the Axiom hierarchy. Even though most types (group, ring, etc) are
> descendents of SetCategory, and we all know that the word problem in
> group theory is in general unsolvable, it does not mean that when a
> particular group or ring that has an equality testing algorithm that
> this function must be inherited from the SetCategory one. In fact, in
> any descendent domain the set equality function will be overriden
> whenever the descendent actually defines equality. If the descendent
> does not, then it is inherited, say, from the equality function of the
> data-representation.  If a finite group has its elements somehow
> encoded by a bijection to a set of integers, it would be reasonable,
> though not obligatory, to inherit the equality test from integers.
> This inheritance can be explicitly given as, for example,
>   x = y == x$Rep = y$Rep

Right.  So that means that if I define a domain which is, say, a group
with undecideable word problem, I'm forced to have an equality defined
on it; but this equality function is guaranteed to be semantic
gibberish.  And what if the data representation is by a function that
returns the next element of the continued fraction expansion?  Equality
would be, I guess, comparing to see if the two functions have the same
memory address; but again, this has no semantic meaning.

Being forced to define functions that have no semantics is sure to lead
to trouble.  For instance, suppose I have an algorithm that only works
if I can actually compare elements for equality (with the standard
mathematical definition of equality, not equality of representations,
which is only a vaguely useful heuristic approximation).  How can I tell
if it's safe to apply it to a particular group?

> The same holds for the print function. Each domain can have its own print
> function, or inherit it from the domain that is used as its representation.
> 
>   print(x) == print(x$Rep)
> 
> To print real numbers to a certain number of digits, one possible way
> is to do something like in Mathematica SetPrecision or SetAccuracy.
> But in Axiom, because the same mathematical objects can often be
> represented differently (for example, a real number represented by
> decimal expansion or continued fraction or as root of a polynomial if
> the number is algebraic), setting a global value is not a good idea.
> Instead, the domain that uses the decimal expansion would have such a
> parameter, the domain that uses continued fraction will have a
> different parameter (the length of the continued fraction), and the
> domain for algebraic numbers as a root of polynomial would not need
> any (the variable of the polynomial is usually system generated using
> a symbol such as %).

Hmm, I hadn't thought about that approach.  So in the case I mentioned,
real numbers that can lazily be computed to any desired precision, if I
parametrize the type by the number of digits I desire on the output,
will I still be able to add reals that have different number of desired
digits on output?  Even so, it seems a little ugly to have to
parametrize by the number of digits on output, even if the numbers are
only used internally and never output at all.

OTOH, look at this code from the ContinuedFraction domain (in
contfrac.spad.pamphlet):

    coerce(c:%): OUT ==
      wh := c.value.whole
      fr := c.value.fract
      empty? fr => wh :: OUT
      count : NonNegativeInteger := _$streamCount$Lisp
      l : List OUT := empty()
      for n in 1..count while not empty? fr repeat
        l  := concat(zagRec frst fr,l)
        fr := rst fr
      if showAll?() then
        for n in (count + 1).. while explicitEntries? fr repeat
          l  := concat(zagRec frst fr,l)
          fr := rst fr
      if not explicitlyEmpty? fr then l := concat("..." :: OUT,l)
      l := reverse_! l
      e := reduce("+",l)
      zero? wh => e
      (wh :: OUT) + e

If I understand this code correctly, it's doing just what you suggested
was a bad idea, using _$streamCount$Lisp (which is a global variable,
right?) to control how many terms to print if you have a non-terminating
continued fraction.

(By the way, in case anyone things I'm too fanatical: I don't propose to
worry seriously about this now or for a while, until there is a
completely working and stable AXIOM with graphics, documentation
browser, and all.  But at some point, I'd like to try to perform surgery
on the category tree, removing links which are spurious or semantically
ill-defined.)

Peace,
        Dylan

signature.asc
Description: Digital signature