Re: FW: data structure vs. mathematical structure (was: [Axiom-developer] Graph theory)

[Vanuxem Grégory]

Le lundi 13 novembre 2006 à 21:39 -0500, Bill Page a écrit : 

[...]

> > Oh, don't believe that I don't see data structures as
> > mathematical structures. They are. But I rather have the feeling
> > that for efficiency reasons it is desirable to have some basic
> > data structures underlying the mathematics where one can say
> > something about the complexity of the functions.
> 
> Axiom actually has a very specific notion of what it means for
> one mathematical structure to underly another - representation.
> In Axiom domains have an associated internal representation, Rep.
> The domain Rep is given in terms of domain constructors (such as
> Record) applied to other previously defined domains. Then members
> of the new domain % are mapped into Rep via the rep operator and
> from Rep into % by the per operator. The exported operations of
> % are defined in terms of the "underlying" operations in Rep.

>From my point of view, Axiom has no real notion of what is Rep.
If I restrict me to Spad since I do not really use Aldor (it's not free) even
if the compiler has a notion of Rep it's just a "conventional" notation. If you
play with an element of type Rep you "package call" function. Of course if the
compiler know its type it's not necessary. You can hide this representation,
see for example the Integer domain but you can have more than one representation
too. My experimentation on this:

http://wiki.axiom-developer.org/LispsFractionIntegerDomain

This is an experimentation, in particular I played in what I call the "dark 
side".
I do not like this experimentation, in the Axiom world (more below).

[...]

> > Example. You want to implement quicksort. Would someone choose
> > lists to do that instead of arrays?
> 
> In Axiom this is not really an appropriate question. quicksort
> would be implemented in a generic manner so that it can be applied
> to any domain that provides the necessary methods. In fact in the
> Axiom book contains exactly this example (bubble sort actually).

I do not totally agree. Yes it's good to implement default algorithm in
categories but each domain has the possibility to provide its own
implementation and this is a good thing. Do you want, for the
exponentiation of Integers, to use the repeatedSquaring algorithm coded
in Spad ? For me it's an important question. 

[...]

> > Why does Axiom have distributed and recursive polynomials. 
> > Mathematically it's the same thing, so why bother?
> 
> This may not be such a good example since I think the difference
> here is primarily related to how these domains coerce to OutputForm.

I totally disagree :-) This is a good example. I forgot where and
if this is the example used in the Axiom book but the authors insisted
on this point. I do not think this is related only to the coercion to 
OutputForm.
Just an example, if you want to implement sparse matrix you'll inherit operation
from MatrixCategory, but you'll have to provide your own implementation to
access each element (the *elt* family). After that it'll be possible to use
the matrix multiplication algorithm implemented in MatrixCategory. The
representation problem is for me is important. I'm not a specialist of the
Polynomial domains/categories in Axiom (which are, I think, the most developed
areas in Axiom) so I can not argue about this, but some
algorithms depends intimately on the internal representation used.

 
> > I hope you get somehow the feeling what I meant when I said
> > that I care for data structures of graphs. We all know that
> > some representation is better than the other for certain
> > algorithms.
> >
> 
> Yes that is true and I agree that it is an important issue.

Yes :-) But even for the question of implementing generic things. You have
to choose a category or create a new one. You can use a general category but
you can choose a more specialised category expressively defined (definition in 
the usual
sense for example in the documentation) to handle efficiently what you are
trying to do. I'm not a fan of performance and, in another mail, I said that
Axiom need to be able to compile to object code. I'm not against compiling to
bytecode, but sometimes it's necessary to have optimised code.

I'm, when I say that, in the "dark side" of Axiom. A lot of
algorithm (I do not speak about Polynomials) in Axiom are extremely general
and I love that but... some of them from my point of view need to be specialised
in the sense that another implementation need to be added in the domains
(this is the "dark side").

It seems to me that the authors of Axiom were sometimes too general probably
by lack of time but sometimes I'm asking if in fact, no, "they did not want to
specialise the code" they wanted to have the more general algorithm possible
(which is necesssary too :-)).

It's a pity that, for example, Manuel Bronstein did not
implement modular algorithm for computation of determinant of matrices
(since I know it worked on this) or any other specialised thing.
I have some difficulties to express what I think, this is somewhat
a philosophical question :-) :  do we want sometimes to restrict the generality 
of an
operation (and restrict the user to use what we think it has to use) ?
For example quickSort is implemented for FiniteLinearAggregate and I'm
happy with that, but do you want to apply this operation on a big list ?

Hmm... I'm pretty sure you'll not understand me...

Greg

PS: the Lisp's fraction integer specialisation is not a good example of what I 
think !!!
(it opens some questions on the architecture of Axiom though).
PS2: I love how Axiom and Mupad (it's no longer free :-() are, conceptually, 
implemented.