Conformant Arrays in C (a better solution?)

[Eric McQueen]

Summary:  Standard run-time function would be a better solution.

Problems with conformant arrays:
  - Complicates what should be a simple compiler (we don't want ADA, please!)
  - Does not allow for allocation of matrices at run time (unless I mis-
        understand the proposal) -- why make C as bad as Fortran?

I believe the addition of a couple of simple functions to the standard library
would provide more power than conformant arrays, is more within the "spirit
of C", and does not complicate the compiler (I can provide source for these
routines written in portable C -- no extra effort required when developing the
compiler for a new environment).

In message <42529 at sun.uucp> David Hough and/or Richard O'Keefe write:
>     I know no C translation that's as clear as the  follow-
>ing Fortran code:
>        SUBROUTINE MATMUL(X,LX,Y,LY,Z,LZ,NX,NY,NZ)
>        REAL X(LX,*),Y(LY,*),Z(LZ,*)
>[arrays are accessed via "X(I,J)"]
>[then proposes the following C syntax]
>        void matmul(double a[?ar][?ac], /* ar >= p, ac >= q */
>                    double b[?br][?bc], /* br >= q, bc >= r */
>                    double c[?cr][?cc], /* cr >= p, cc >= r */
>                    int p,              /* 0 <= p <= min(ar,cr) */
>                    int q,              /* 0 <= q <= min(ac,br) */
>                    int r)              /* 0 <= r <= min(bc,cc) */
>[arrays are accessed via "a[i][j]"]
>[mentions having to disallow sizeof() in some cases]

As has been pointed out several times [recently in <2336 at umd5.umd.edu> by Chris
Torek (chris at trantor.umd.edu)], the following is already possible:

void matmul( double **a, double **b, double **c, int p, int q, int r)
{       /* arrays are accessed via "a[i][j]" */

and is much simpler.  The only problem I see with this is that it is difficult
to declare such an array in the calling procedure.  Several people have
proposed methods to allocate "row vector" arrays.  I feel that some such
method should be standardized by the committee and routines to handle it be
provided in the standard library.  The allocation of arrays would be as simple
as:

  float ***m;   /* 3-Dimensional Matrix ALLOCation: */
        m = d3malloc( sizeof(float), 2, 3, 4 );

or:

  float **m;
  int d[] = { 2, 3, 4 };        /* Multi-Dimensional Matrix ALLOCation: */
        m = mdmalloc( sizeof(**m), 3, d );

Both of which would yield:

  m:  &a  &b   0        /* Pointers ("0" means "NULL"): */
  a:  &c  &d  &e   0
  b:  &f  &g  &h   0

  c:  000 001 002 003   /* Elements (must be contiguous): */
  d:  010 011 012 013
  e:  020 021 022 023
  f:  100 101 102 103
  g:  110 111 112 113
  h:  120 121 122 123

where "102" represents where "m[1][0][2]" is stored.  We allocate room for
11 pointers in a contiguous block and for 24 numbers in a contiguous block.
The space required for the pointers would on the order of that required if you
increased the last array dimension by 1 (not too bad).  The null pointers are
included to allow efficient traversal of the entire array.

Of course, this method doesn't provide for the Fortran trick of:
        real a(10,20), b(9,14), c(5,11)
        call matmult( a(2,3), 10, b(4,1), 9, c(2,5), 5, 2, 2, 2 )
for getting at strange sub-matrices.  But I think you should do this via:
        void matmult( a, ar, b, br, c, cr, p, q, r )
          float *a, *b, *c;  int ar, br, cr, p, q, r;
        #define  A(i,j)  a[ar*i+j]
which is what Fortran is really doing anyway.

I plan to send a more detailed proposal along these lines to the committee.
Any suggestions about my choice of allocation style would be appreciated.
For the sake of definateness, here are the basic prototypes:

void *mdmalloc(
  size_t siz    /* Size of elements in the array. */
, int    ndim   /* Number of dimensions. */
, int    d[]    /* Maximum dimensions "arr[ d[0] ]...[ d[ndim-1] ]". */
);

void *d2malloc( size_t siz, int d1, int d2 ) {
  int d[2];  d[0] = d1;  d[1] = d2;  return( mdmalloc( siz, 2, d );
}
void *d3malloc( size_t, siz, int d1, int d2, int d3 ) {
  int d[3];  d[0] = d1;  d[1] = d2;  d[2] = d3;  return( mdmalloc( siz, 3, d );
}

void mdmfree( void *arr, int ndim );
#define   d2free( arr )   d2free( arr, 2 )
#define   d3free( arr )   d2free( arr, 3 )

I think some strange systems would want to provide special versions that deal
only with certain data types if, say, sizeof(float *) < sizeof(void *):

float   **d2falloc( int d1, int d2 );
double ***d3dalloc( int d1, int d2, int d3 );

But I think most systems would just use:

#define  d3dalloc(d1,d2,d3)  (double ***) d3malloc( sizeof(double), d1, d2, d3 )

Is there any reason to:
    *Explicitly* provide for allocating multi-dimensional arrays of anything
        other than float, double, int, or long?
    Force non-strange systems to provide {md,d2,d3}{f,d,i,l}alloc()?
    Provide for the allocation of rows separately in case of fragmented memory?
    Make the inclusion of the null pointers optional or drop them altogether?
    Include the dimensions or number of dimensions in the array structure?
    Not include these routines in the standard?  (no-cost added option?)

Comments not of general interest to the net could be mailed directly to me.
I will summarize significant comments.  (Comments not of significant interest
should just be shouted at your roommate/boss/dog.)

---
Eric Tye McQueen          Mathematics Department        Also at (after some
ericmc at usu.bitnet         Utah State University           time in March):
 (801) 753-4683           Logan, Utah  84322-3900       ericmc at usu.usu.edu

   UUCP:  ...{uunet,psuvax1}!usu.bitnet!ericmc     "Nothing is obvious
  CSNET:  ericmc%usu.bitnet at relay.cs.net            unless you're over-
   Arpa:  ericmc%usu.bitnet at cunyvm.cuny.edu         looking something."