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

[Gabriel Dos Reis]

"Bill Page" <address@hidden> writes:

| On November 11, 2006 2:29 PM Gaby wrote:
| > 
| > This is what we do in the Generic Programming community under
| > the heading of "Musser--Stepanov style Generic Programming".
| >
| 
| See:
| 
| http://www.cs.rpi.edu/~musser
| 
| Algorithm-Oriented Generic Libraries (1994)
| 
| http://citeseer.ist.psu.edu/41800.html
| 
| It is irritating to me to realize how isolated the IBM ScratchPad
| (Axiom) project was from mainstream computer science and yet how
| much they were ahead of the curve on some ideas in programming
| language design.

Hey, Dave and Alex gave an invited talk at ISSAC almost two decades
ago :-)

     http://www.stepanovpapers.com/genprog.pdf

If you browse through the papers by Dave, Alex and collaborators
(especially, those in the early '80), you'll see that they noted
the potential of ScratchPad.  See, for example, the paper 
"Operators and Alegbraic Structures"

    http://www.stepanovpapers.com/p59-kapur.pdf

where they cite the paper by Jenks and Tragger.

| I think that it is clear that in modern terms
| a lot of the innovation in the design of the SPAD language (and
| Aldor) would be described as "generic programming". No?

Yes and No.  In many aspects, Axiom has painted itself into a corner
and insisting beyond reason on object-orientation, which clearly leads
to absurdities like having an Abelian monoid that is not a monoid,
or a ring that is just a monoid without being a group.  I don't think
any freshman in math would get its degree with those nonsense, but
Axiom seems to get away with it :-(  See past discussions on the topic.

You'll see many aspects of generic programming on Alex's site, in
particular in his class on generic programming he is giving at Adobe.

In our collaborative effort to design a "concept system" for C++, we
have tried very hard to ensure that we don't get into the same trap as
Axiom (but it is hard :-).  See for example, our paper "Specifying C++
concepts" 

      http://www.research.att.com/~bs/popl06.pdf

(where it in the related work, you'll see we have specifically mention
computer algebra as area of exploration, referring to Axiom), where we
insisted that we must resist class hierarchies (it has been tried many
times, and it fails). And further work

     http://www.research.att.com/~bs/oopsla06.pdf

There is a another aspect to Generic Programming, called "data-type
generic programming" in the functional programming community that put
less emphasis on algorithmic complexities and more on the structure
of datatype, abstracting over the concrete algebras and focusing on
the pattern functors and algorithms that could be defined solely in
terms of those.  We are working on connecting both views.

      http://lcsd05.cs.tamu.edu/papers/dos_reis_et_al.pdf

Chase the citations to the datatype generic programming.

-- Gaby