Re: [boost] Re: Standard Matrix interfaces

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-08-21 15:10:21

helmut.zeisel_at_[hidden] wrote:

> As I wrote already in a previous answer, it depends on the purpose
> of the "matrix interface".

A reasonable purpose for a 'standard matrix' interface
is teaching.

A second purpose is algorithm verification: a physicist can
use the standard system to check small cases against
purpose written code, before running the latter on
a super computer with a large data set.

In both these cases, encapsulation will serve well.
For performance, OO encapsulation is wrong: you really
need to know the exact representation and write the algorithms
you need using it (in a large number of cases).

For example, for a teaching interface:

        m.determinant()
        m.invert()

makes sense, but no physicist would ever program that in a real
application, since you find the determinant doing the inversion
anyhow. OTOH, if the matrix is normal, the determinant
is known to be 1, so both routines could be significantly
optimised. Etc..

As a general comment: there is a wrong idea that an interface
'hides' the representation. This idea is wrong. An abstraction
provided by an interface is just that: its _an_ abstraction.
It provides one level of indirection, but the interface
itself is usually just another representation.
Indeed, the underlying representation is itself
abstract -- its written in a high level language,
after all. :-)

This is particularly true for most OO interfaces,
since covariance ensures no purely abstract interface
can exist in almost all real world cases.
A 'purely' abstract interface is one in which 
no methods return 'significant' concrete types,
nor accept them as arguments. The existence of
such types in method signatures is the proof that
the interface is just another representation.

Matrices are the perfect demonstration. Perhaps the interface
hides the ordering of the elements, and you can provide
some representation hiding using a multiply method,
but the determinant is going to produce a float
or complex result, revealing the ground field,
and if you follow Stepanov and include complexity
measures for the methods, then it comes close
to exposing the physical representation.
The existence of a 'set element' method guarrantees
the matrix isn't symmetric, and constant time performance
indicates the storage is organised linearly.

Another example is the classic 'pair': the representation:

        struct X { int a; int b; }

is perfectly abstract because the core language provides
'get' and 'set' methods for cartesian products represented
using structs, and the interface:

        struct X { .. get_a .. get_b .. set_a .. set_b }

with the guarrantee that the get and set methods correspond,
and those for a and b are independent, provides exactly
the same level of abstraction as the original struct:
in both cases, we have a categorical product, guarranteed,
and in both cases, there must be discrete storage for
each element somewhere. Of course, the use of methods
may permit use of pointers:

        struct X { ... int *a; int *b; }

whereas the concrete struct does not, but such a change in the
storage organisation doesn't change the fact that the
interface _implied_ by C++ core language reference semantics
and the POD struct is isomorphic to the encapsulated one:
The isomorphism guarratees the level of abstraction is the
same in both cases. In fact, the semantics are _endangered_
by using methods, since the independence and correspondence
axioms might not be maintained by arbitrary code,
whereas the guarrantee is manifest in the POD.
The POD is the best representation, because it is the simplest,
and the semantic guarrantee is ensured by the compiler:
there isn't a more abstract representation available.

All of this rave is basically to say that an 'abstract'
representation of matrices is a practical impossibility.
The very methods provided are themselves a representation,
and will differ almost as widely for subtypes of
a general matrix as the physical data layout:
even for dense/sparse matrices which are semantically
equivalent, the methods are likely to differ
(I'd _never_ use iterators for a dense matrix, but 
that's probably the best way to access elements of
a sparse one).

To put this another way: a general dense matrix
already has an optimal perfectly abstract representation:

        float mat[n][m];

[except that this isn't a first class type!]
To see this, I'll debunk the popular myth that
Fortran and C store matrices in different orders.
Nope. They store them in the same order.
Its the interfaces that differ: you write
the subscripts in different orders. 
[You can't tell the difference between the two
representations: 'concrete' and 'interface'
because neither is more abstract than the other:
they're both interfaces, and they're both
representations]

[What I wrote is 'technically' a lie, since
you can coerce a square matrix to a linear
one in both languages, and then the storage
ordering is evident: ignore that for the sake
of argument :-]
-- 
John (Max) Skaller, mailto:skaller_at_[hidden] 
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
New generation programming language Felix  http://felix.sourceforge.net
Literate Programming tool Interscript     
http://Interscript.sourceforge.net