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

[Bill Page]

-----Original Message-----
From: Bill Page [mailto:address@hidden 
Sent: November 13, 2006 1:13 AM
To: address@hidden
Cc: 'Martin Rubey'; 'Ralf Hemmecke'; 'Bill Page'
Subject: RE: data structure vs. mathematical structure (was:
[Axiom-developer] Graph theory)


On November 11, 2006 11:11 AM Ralf Hemmecke wrote:
> ...
> Bill Page wrote:
> > I think one of the neat things about Axiom is that it is
> > usually not necessary or even desirable to make a distinction
> > between data structures and mathematical structures. Data
> > structures are just another kind of "mathematical" object.
> 
> 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.

We usual think of Rep as more "primitive" than % and as if Rep
is the underlying "data" structure and % is the mathematical
structure. But in general in Axiom this need to be the case.
There is indeed a most primitive domain which is not defined
in terms of any other, called simply Lisp. But it would not be
possible if the representation graph to contain loops so that
one can not say of any domain in the loop that it is more
primitive than another.

So using previously defined domains, and domain constructors
one builds a representation for the desired new domain and then
"encapsulates" it by exporting an interface to the essential
operations of this representation and hiding the non-essential
and irrelevant parts. And I think this might be applied in a
mutually recursive manner.

So is computational complexity a relative thing, i.e. we take
the operations from the representation as units and then express
the complexity of the operations of the new domain in terms of
these? Or is it an absolute thing that must be expressed in
terms of the most primitive domain (Lisp) or even deeper in
terms of a given hardware architecture?

> After all that is a distincion between classic mathematics
> and constructive mathematics.
>

I am not sure that I would agree that this is the right distinction.
Ultimately in computer algebra systems I think all mathematics must
be constructive. In a sense, that is what we mean by "algebra". An
existence proof or a proof by contradiction is not of much use in
such a system.
 
> 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).

> Both basically represent the mathematical idea of tuples.

No, I don't think so. As mathematical objects lists, arrays and
tuples are all quite distinct however I agree that they all provide
the necessary methods on which sort may operate.

> But we care about the actual representation on a computer.

Agreed.

> 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.
It is not clear to me how or when we can say that something is
"mathematically the same thing".

> 
> 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.
 
> Drawing the line between "data structures" and "mathematical 
> structures" is hard if not impossible. But for data structures
> I somehow feel that their documentation should clearly say
> something about the complexity of operations.
>

The current Axiom library does make such a distinction at least
conceptually. See for example the Algebra and Data structure
hierachies in the end covers of the Axiom book. However note that
at least SetCategory, Finite, and OrderedSet appear in both
diagrams.
 
> > For example, is an Axiom set, i.e. a member of the domain Set,
> > a data structure or a mathematical structure?
> 
> How expensive is it to add a new element to an existing set of
> type Set(T) where T has no ordering function? How expensive is
> it to add a new element to Set(T) if T provides an ordering
> function?
> 

All domains that have SetCategory are required to have a hash into
SmallInteger. I suppose that this means that the cost of adding
new elements is independent of Type T.

> I actually don't care about much about whether to call it "data 
> structure" or "mathematical structure" since in a general sense
> the first is (as an abstract data type) clearly a mathematical
> object. What I care about is stating complexity properties and
> providing a rich set of basic data structures for Axiom/Aldor.
> 

On November 12, 2006 9:23 AM Ralf Hemmecke wrote:
> ...
> Bill Page wrote:
> > Should we call the domain Set a mathematical structure or only
> > the category SetCategory to which it belongs? And of course not
> > everything that we would like to call a set in Axiom is finite.
> 
> Actually, "Set" is a bad choice for the domain of finite sets
> that all have the same type of elements. It should at least be
> called "FiniteSet".

I don't agree. Finite is yet another category.

> But then, would make "Set" as a _domain_ in the sense of
> mathematics be an interesting domain at all?

Why not? As a domain, Set need not be finite.

(1) -> Integer has SetCategory

   (1)  true
                                                 Type: Boolean

(2) -> ZMOD 7 has SetCategory

   (2)  true
                                                 Type: Boolean

(3) -> Set Integer has Finite

   (3)  false
                                                 Type: Boolean

(4) -> Set ZMOD 7 has Finite

   (4)  true
                                                 Type: Boolean

(5) -> size()$Set ZMOD 7

   (5)  128
                                       Type: NonNegativeInteger

Note that size:()->NNI, i.e. the size of the Domain, is different
then #:%->NNI, or cardinality of the size of a given set. It is
true that all members of Set have a finite cardinality. But not
all domains in SetCategory are Finite.

> 
> > Essentially the only requirement of SetCategory is that the
> > domain has equality and inequality.
> 
> That is OK, I think.
> 
> > I think a Graph in Axiom has to be something nearly as
> > fundamental as a Set.
> 
> As a category, I agree, but there is not *the* graph domain.

Similar to Set, I think we need to admit the possibility of an
infinite number of members of the Graph domain, i.e. Graph need
not have Finite.

As a category I think I would want GraphCategory to require at
least

  Node: SetCategory
  Edge: SetCategory
  Source: Edge -> Node
  Target: Edge -> Node

But I do not want to require that all domains in GraphCategory
are Finite. Just as all domains in SetCategory are not Finite.

On November 12, 2006 11:34 AM Vanuxem Grégory wrote:
> ...
> I played a little with this and reread aggcat which contains the
> aggregate categories used in src/algebra.
> ...

I think it is interesting that multisets only have cardinality if
the domain has finiteAggregate since count is unbounded.

Regards,
Bill Page.