[comp.lang.c] Why does C hate 2d arrays?

ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (05/25/90)

> In article <3060@goanna.cs.rmit.oz.au> I wrote
>                                                       Heck, if C was all
>about primitives, we wouldn't have floating point.  Why coddle these weak
>programmers by providing a sqrt() function; they have all the primitives
>they need to build it themselves.

In article <2429@psuhcx.psu.edu>, hannum@schubert.psu.edu (Charles Hannum) writes:
> C does not provide a sqrt() function to "coddle the programmer."
> Your standard library, on the other hand, may include such a function.

Re coddling the programmer, don't you recognise irony when you see it?

This thread was concerned with ANSI C.  And the standard library *IS* part
of ANSI C.  sqrt() is not an _optional_ part of ANSI C.

> And yes, C *is* all about primitives.
> Read "The C Programming Language" if you don't believe this.

I have read "The C Programming Language", thanks, many times.
C is not about primitives.  It is about TRADEOFFS.  I repeatedly said in
my postings in this thread that C's strength comes from what it left out,
which is pretty much a paraphrase of the extract Hannum quoted in his
previous posting.

For example, malloc() is not a primitive.  In UNIX, it used to be built
on top of a _real_ primitive, namely brk().  Writing code for a PDP-11,
I often used brk() and sbrk() myself because I wanted to keep all that
library code *out* to leave room for my data.  Can anyone claim that
printf() is a primitive, with a straight face?  (I would also keep
stdio *out* too, it was much too big when I had only 64k to play with
and 30k of code and 30k of data...)

No, malloc() and printf() are tradeoffs:  the extra convenience is
worth while, and the price in terms of compiler and library support
is not too high.

The C philosophy was to provide you with ALL the primitives you need.
It was not to provide ONLY the primitives.  Adding dynamic arrays to C,
*if it could be done without disruption* would not compromise the C
philosophy in any way.  Only if programmers *had* to use the new
dynamic array mechanism *instead* of pointer arithmetic would that be so.

Any rate, all that really matters is that C should continue to work as
Eiffel's portable assembly code (:-).
-- 
"A 7th class of programs, correct in every way, is believed to exist by a
few computer scientists.  However, no example could be found to include here."

ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (05/25/90)

In article <12722:May2501:41:2690@stealth.acf.nyu.edu>,
 brnstnd@stealth.acf.nyu.edu writes:
> I've tried to shorten this article by replacing flames with the phrase
> 'Nuff said.

That's more incendiary than most flames.

> The language gcc compiles is a C-*like* language. 'Nuff said.
No, *not* enough said.  It does *not* handle all the cases which were
being discussed.  

> > It looks rather silly to be dogmatic about a language that doesn't
> > exist yet:
> The language gcc compiles certainly does exist. 'Nuff said.

No, *not* enough said.  The language gcc compiles does not meet the
criteria of this discussion.  However, I did over-state the case; C++
does exist.

> > > I find it very difficult to believe that a compliant Ada implementation
> > > can work with any other language.
> > Believe it.
 
> Name a validated Ada compiler that can produce stdio routines usable
> from C on the same machine. 'Nuff said.

Oh, _now_ I see!  An implementation of Ada can work "with ANY OTHER language"
only if it can be used to implement stdio!  Why didn't I think of that?
I thought that "working with any other language" meant that applications
programmers could call either language from the other, passing a useful
variety of data in either direction, even if not absolutely everything.
By this criterion, it would of course be impossible to mix Fortran and C
(can't implement stdio in Fortran) or Pascal and C (can't implement stdio
in Pascal) and those Lisp vendors who think their language can call C in
a useful sense are deluding themselves (hard to implement stdio in Lisp).
It doesn't matter if an Ada program can interface to an X Window System
implementation in C without difficulty or if C code can call back to Ada,
if you can't implement stdio you just aren't "working with" C.

Indeed, there is a sense in which it is impossible for *C* to "work with"
C itself according to this criterion.  The stdio function names are
reserved by the standard, and a portable program may not redefine them.
(Ok, as macros or statics is ok, but then who else can call them?)


> > > > In the presence of dynamic arrays, [whether sizeof X is legal in a
> > > > static expression is] no longer a simple syntactic test.
        ^^^^^^
> > > Say what? The same is true with or without dynamic arrays.
> > False.  sizeof is currently ALWAYS legal in a static expression.
                                                  ^^^^^^
> Rather than repeatedly insisting that you're right, why don't you give
> an example of a sizeof that can't be used in a dynamic expression with
					         ^^^^^^^
> the obvious C extensions. Repetition does not replace logic. 'Nuff said.

Sir, please have the goodness to read what I wrote.  I wrote
	[whether sizeof X is legal in a ***STATIC*** expression...]
I don't know of any instances of sizeof that can't be used in DYNAMIC
expressions, and I never said that there were any.  Misreading does not
replace logic!  The posting I am following up now quoted in the next
few lines just such an example of a sizeof which would not be legal in
a *STATIC* expression.  I ***DID*** give an example of what I was
talking about.  brnstnd QUOTED it.

You might reasonably argue that it isn't important or that the semantic
check required isn't that hard to do.  And to be perfectly fair, there
is already a semantic check required which I had overlooked:
	static char *x = &y;
is legal only if y is static or extern, and if you're going to keep that
much symbol table around in a checker, you might as well keep track of
which arrays are statically dimensioned and which aren't.

> Your example doesn't show the point you're trying to make, so why should
> anyone be expected to see it?

Another reader of this newsgroup _did_ see the point, which was that as
declared the initialiser wasn't legal.


> > > > 	void dynamic_own_array(int m, int n)
> > > > 		static double a[m][n];
> 
> Sorry, missed the ``static'' here. Without the static, assuming m and n
> are declared as const int parameters, this is fine, as I said.

Yes, but again, why assume something contrary to what I explicitly
declared?  The point is that there was once a rather nice programming
languge in which *precisely* this construct was legal, defined, meaningful,
and sometimes useful.  Look up "dynamic own arrays" in a good survey of
programming languages some time.

> Real computers have floating-point operations. 'Nuff said.

Oh dear.  That means that the Sun-3/50 in my office is not a real computer.
I must be imagining it.  Every Macintosh I have ever used must have been
just a toy.  (The PC I used last year, _that_ was a toy, I grant you.)

> > > > With specific reference to fwrite(), there are at least three fairly
> > > > obvious possible complications which I'll not trouble you with.
> > > How about naming them?  I see no problem.
> > It shows.
> Again you attempt to replace logic with rhetorical bullshit. I doubt you
> can state your ``three fairly obvious possible complications,'' because
> they don't exist. You've had two chances; think you can be explicit on
> your third? 'Nuff said.

Of course I can state them.  But I'm afraid the examination runs the
other way.  If you don't know what they are without my telling you,
you haven't understood the problem.  If someone _else_ would like to
know what the problems are, ask, and I'll hand out the model answers.

> > Here's another question about dynamic arrays.  Consider
>   [ void f(int n) { double a[n]; int m = g(n); double b[m]; ... } ]

> Better stated:

>   void f(const int n)
>   { double a[n]; int m; m = g(n); { const int x = m; { double b[x] ...

That's not "better stated".  That's **RE**stated, as in CHANGED.
There were two significant features about the way I formulated the
question:  m was *NOT* const, and the declarations were in one group.
If brnstnd means that he expects that his restatement is how a compiler
would implement such declarations, fine.  Algol 68 and Ada both allow
a series of declarations like this, and at least some Algol 68
implementations used to handle it with one stack frame.

With reference to m:  there is one language (fortunately dying) in which
the equivalent of
	int (*a)[m];
"declare a as pointer to array-m-of-int" used the value of 'm' which
was current whenever 'a' was _used_, not when it was _declared_.
In fact, proposals that array parameters should be handled as

	f(... int m, int n, elt_t a[m][n] ...)

are in essence suggesting exactly the same thing, that the shape of
an array should not be a property of the array value itself but of
the value of some other variable entirely at a later time.  So there
is a serious decision to be made: if 'm' is changed, does that affect
the apparent size of the array?

An interface I suggested for C once would have looked like

	f(... elt_t a[int m][int n] ...)

This has a two-fold point:  the programmer would not have to explicitly
pass the array bounds (so that _using_ such a function is simpler) and
it would be impossible to get the bounds wrong.  That interface would,
alas, not have allowed a programmer to pass an 'extern' 2-d array where
the size of the first dimension was unknown, so I'm afraid it just won't
fly.  C is not Pascal, thank goodness.

> (The inner braces are for clarity and to handle a different view of
> initializers.) This is perfectly fine. Upon f entry, n is in the frame.
> a and m are either in the frame or allocated immediately. x is either in
> the frame upon entry, allocated immediately after entry, or allocated
> upon entry to the second block. Finally, b is allocated after x

Yes, but *where* is b[] allocated?  In the absence of even gcc's
half-baked dynamic arrays (if you can't have dynamic arrays in records
-- as you can in Algol 68, Simula 67, Ada, &c -- you still haven't got
full dynamic arrays), every variable is at an offset from one end of the
stack frame, which offset is known at compile time.  Indeed, in many C
compilers, internal blocks are a notational fiction, entering and leaving
a block involves no stack adjusting.  (So jumping out of a block is easy,
and the justly notorious switch()ing into a block is not an allocation
problem.)  The simplest answer is to make dynamic arrays pointers, so
that

    void f(int n) 
	{ 
	    double a[n];
	    int m = g(n);
	    double b[m];
	    ...
	}

is treated as the equivalent of

    void f(int n)
	{
	    double * const a = alloca(n * sizeof *a);
	    int m = g(n);
	    double * const b = alloca(m * sizeof *b);
	    ...
	}

Now, I can see how to make this work on a PR1ME, because although
you are not in general going to be able to fit a bunch of arrays in
a stack frame there, there is an instruction for extending the frame.
The new block it returns may be in another segment entirely, but the
instruction that returns from a procedure will delink and reclaim 
these stack extensions.  However, a 'goto' leading out of a block
gets complicated.  Not impossible.  Just complicated.  It has to
deallocate all the local dynamic arrays.  I haven't got gcc at the
moment.  What happens if I do

	int i;
	for (i = 1; i <= 10000; i++) {
	    {
		double a[i];
		int j;
		for (j = 0; j < i; j++)
		    if (rand()%16 == 0) goto bogeyman; 
		    else a[j] = j*2+1;
		foo(a);
	    }
bogeyman:   { ... }
	}

Will a[] be deallocated by the 'goto'?  It should be.	    

What does gcc do with
	if (i >= 0) switch (i) {
	    double a[i+1];
	    case  0: ...a[i-1]...; break;
	    case  1: ...a[i-2]...; break;
	    default: ...a[i/2]...; break;
	}

If the dimension of a[] here were a static expression with a sufficiently
large value, this would be legal and meaningful C.

What does gcc do with
	int m = f();
	int (*a)[m] = malloc(sizeof a);

In case it isn't obvious, I respect C a lot.  It's a beautiful example of
well chosen tradeoffs.  C was not intended for the kinds of applications
that Fortran 90 has been designed for (Fortran 90 has dynamic arrays...).
The point that I have been making is that if you really want to do a
thorough job of supporting multi-dimensional dynamic arrays, there are
lots of details to get right.  My argument is _support_ for C in more or
less its present form.  Better not to offer a feature than to pretend to
have it and get it wrong.  We _don't_ want C to turn into something like
SQL.

-- 
"A 7th class of programs, correct in every way, is believed to exist by a
few computer scientists.  However, no example could be found to include here."

peter@ficc.ferranti.com (Peter da Silva) (05/25/90)

In article <12923:May2502:17:3090@stealth.acf.nyu.edu> brnstnd@stealth.acf.nyu.edu (Dan Bernstein) writes:
> In article <K3O3WK1@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes:
> > [assume: array[m][n] works for m and n not constants]
> > What possible advantage would there be to requiring that m and n not
> > change value while array is in scope?

> The compiler isn't *forced* to make extra, possibly unnecessary, copies
> of m and n.

The compiler is not forced to make extra copies of m and n either way. Only
if they're found to have changed.

> > Since m andd n can be expressions,
> > you are going to want to stash the values away anyway just for the sake
> > of optimisation.

> Not necessarily: m and n may be in registers anyway. To generalize a
> bit: C is a constant, calculated from expression E. We have to know the
> value of C for the lifetime of A. ``Therefore,'' you say, ``we must pick
> an arbitrary time in that lifetime, calculate E then, and stash it away
> in C's special hiding place.''

If you want to guarantee that C is to remain constant during the duration
of E. What about this case:

struct _point { int x, y };

foo(box)
struct point box[2];
{
	char tmp[box[1].x - box[0].x][box[1].y - box[0].y];

	bar(box, tmp);
	print(box, tmp);
}

How do you guarantee that box is constant? In general, you can't. This is
back to the old noalias problem. Better sidestep it completely by just using
the value of box at declaration.

> Do you agree that, given this scenario, it's better for the programmer
> to have access to C's value than not?

How do you feel about:

	char *a = malloc(some_expression);

How does this materially differ from:

	char a[some experssion];

in the context of this discussion?

Do you agree that, given this scenario, it's better for the programmer to
have access to !some expression!'s value than not? Whether you're mallocing
or not.

> In other words, do you agree that
> C should be explicitly declared and initialized by the programmer?

It may be good programming practice, but this is C, not Pascal. C is expected
to bend over backwards to do weird stuff that flakey programmers might want
to do.
-- 
`-_-' Peter da Silva. +1 713 274 5180.  <peter@ficc.ferranti.com>
 'U`  Have you hugged your wolf today?  <peter@sugar.hackercorp.com>
@FIN  Dirty words: Zhghnyyl erphefvir vayvar shapgvbaf.

platt@ndla.UUCP (Daniel E. Platt) (05/25/90)

In article <16703@haddock.ima.isc.com>, karl@haddock.ima.isc.com (Karl Heuer) writes:
> In article <3034@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
> >There is, however, a silver lining in that cloud.  All you have to do is to
> >write your own array allocator which returns a pointer to a single block of
> >(Nrows pointers then alignment padding then Nrows*Ncols data).
> 
> Yes, ideally one should be able to write
> 	foo_t **p = (foo_t **)alloc2(nrows, ncols * sizeof(foo_t));
> 	p[i][j] = f;
> for arbitrary type foo_t.  Unfortunately, it is impossible to portably write a
> single function, since it has no way to know the type of pointer to use for
> the dope vectors.  (This is why I dropped the function from my private
> library.)
> 

I'm not sure I understand the problem...

How about:

	void **alloc2(nrows, ncols)
	int nrows, ncols;   /* ncols includes size info */
	{
		int i;

		void **tmp;

		if((tmp = (void **)malloc(nrows * sizeof(void *))) == NULL){
			/* do something about this problem */
		}

		for(i = 0; i < nrows; i++)
			if((tmp[i] = (void *)malloc(ncols)) == NULL){
				/* do something about this problem.. need to de-allocate what
				was allocated */
		}
		return tmp;
	}

If you're not using ANSI-C, then you can replace all the 'void's with
'char's and it will work just fine with appropriate type-casting.  My
documentation on malloc indicates that "malloc returns a pointer to a block
of at least 'size' bytes suitably aligned for any use",  which implies that
all you'd need to do in a structure containing doubles is make sure that there
were nice allignment paddings in the structures....

I'm not sure what's wrong with the above approach.  I've written lots of nice
library functions for my use (things like fft's, matrix inversion and
diagonalization, &c) around things like this, and I've had no complaints.
Further, these routines can be used to handle arrays with weird shapes...
Most of the semantics (what a, a[] and a[][] mean) is pretty much the same
at the code level anyway -- it does mean something different at the assembler
level, and the declarations look different -- when comparing doubly dimensioned
arrays with pointer arrays of pointers to arrays.

Or did I miss the point?

> It's impossible for a user to write it in portable C.  

Is the above not portable?

>                                                        But it's relatively
> easy for the *implementor* to provide it, since he can add compiler hooks as
> necessary.  On a vaxlike architecture this would simply be implemented as
> 	#define malloc2d(nr, nc, T) ((T **)alloc2((nr), (nc)*sizeof(T)))
> where alloc2() is the function mentioned earlier.  On a word-addressed
> architecture with two or more flavors of pointers, you use
> 	#define malloc2d(nr, nc, T) ((T **)_alloc2((nr), (nc)*sizeof(T), \
> 		__whichpointer(T)))
> where __whichpointer() is some mapping from types to small integers to encode
> the information about pointers.  (alignof() might suffice.)  Then the actual
> function simply does
> 	switch (wp) {
> 	case __whichpointer(char):
> 	    ((char **)vec)[i] = (char *)&block[i*nc*sz];  break;
> 	case __whichpointer(int):
> 	    ((int **)vec)[i] = (int *)&block[i*nc*sz];  break;
> 	}
> 

I thought malloc() was supposed to handle allignment problems by starting
blocks on the largest appropriate boundary.

Dan Platt

PS... I'm not trying to be argumentative or contrary -- its just that if I've
missed a fine point of C, I'd like to know about it...

karl@haddock.ima.isc.com (Karl Heuer) (05/26/90)

In article <311@ndla.UUCP> platt@ndla.UUCP (Daniel E. Platt) writes:
>In article <16703@haddock.ima.isc.com>, karl@haddock.ima.isc.com (Karl Heuer) writes:
>>Yes, ideally one should be able to write
>>	foo_t **p = (foo_t **)alloc2(nrows, ncols * sizeof(foo_t));
>>	p[i][j] = f;
>>for arbitrary type foo_t.  Unfortunately, it is impossible to portably write
>>a single function, since it has no way to know the type of pointer to use
>>for the dope vectors.
>
>I'm not sure I understand the problem...
>[Example code that appears to solve the problem]
>	... tmp = (void **)malloc(nrows * sizeof(void *));
>	... tmp[i] = (void *)malloc(ncols); ...
>Is the above not portable?

Afraid not.  It fails on word-addressible machines, if `foo_t *' and `void *'
have different internal formats.  The value stored in tmp[i], despite being
maximally aligned, is still a char pointer; but it eventually gets referenced
(via p[i]) as if it were a word pointer.

For an extreme example, suppose that sizeof(foo_t *) is 2 but sizeof(void *)
is 4.  Then the call alloc2(2, 1*sizeof(foo_t)) contiguously allocates two
four-byte cells (each of which it initializes to a pointer to FOOSIZE
additional bytes, which we don't care about for now) and returns a pointer to
the eight-byte block.  The caller casts this to (foo_t **) and stores it in p,
then attempts to reference p[1][0].  But since p is declared to be a pointer
to a `foo_t *', it sees the eight-byte block as four two-byte chunks; the
reference to p[1] will actually fetch bytes 2-3 of the block, which isn't even
in the right section.  (To get the correct answer you'd have to fetch bytes
4-7 and convert them from char-pointer to word-pointer.)

(You don't have to have different sized pointers to get this effect, but it
makes it easier to illustrate.)

The solutions are:
[0] Forget it
[1] Limit yourself to vaxlike architectures
[2] Make the function handle some specific type instead of being generic
    (i.e. write one such function for each type that you might want)
[3] Change the specs to be
	void **p = alloc2(nrows, ncols * sizeof(foo_t));
	((foo_t *)p[i])[j] = f;

Karl W. Z. Heuer (karl@ima.ima.isc.com or harvard!ima!karl), The Walking Lint

brnstnd@stealth.acf.nyu.edu (05/28/90)

In article <N.O32W6@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes:
> In article <12923:May2502:17:3090@stealth.acf.nyu.edu> brnstnd@stealth.acf.nyu.edu (Dan Bernstein) writes:
> > In article <K3O3WK1@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes:
> > > [assume: array[m][n] works for m and n not constants]
> > > What possible advantage would there be to requiring that m and n not
> > > change value while array is in scope?
> > The compiler isn't *forced* to make extra, possibly unnecessary, copies
> > of m and n.
> The compiler is not forced to make extra copies of m and n either way. Only
> if they're found to have changed.

How do you expect it to figure that out? And once m and n do change,
where do you think it's going to store the original values? Why not let
the programmer have control over those values?

> struct _point { int x, y };
> foo(box) struct point box[2]; {
> 	char tmp[box[1].x - box[0].x][box[1].y - box[0].y];
> 	bar(box, tmp); print(box, tmp); }
> How do you guarantee that box is constant? In general, you can't.

Q requires that array dimensions be const (i.e., unvarying within their
scope, lifetime, whatever). Given box declared const, the answer is
``yes, you can.'' const filters down through function invocations: if
bar were to change box, then it couldn't declare box constant in the
function declaration, so bar(box,tmp) (rather, bar(&box,&tmp), because Q
treats arrays differently) wouldn't be valid.

This all makes perfect sense. What are you objecting to?

> > Do you agree that, given this scenario, it's better for the programmer
> > to have access to C's value than not?
> How do you feel about:
> 	char *a = malloc(some_expression);
> How does this materially differ from:
> 	char a[some experssion];
> in the context of this discussion?
> Do you agree that, given this scenario, it's better for the programmer to
> have access to !some expression!'s value than not? Whether you're mallocing
> or not.

No. In the malloc() case, the expression is evaluated at one particular
moment, and the dimension isn't carried in the type (which is just
``pointer to char''). In the array case, the type of the array (``array
size some_expression of character'') includes the dimension, and that
dimension had better be constant.

Given that we *have* to carry around a constant value for the array type
to work, it's better for the programmer to have access to that value.
The premise isn't true for malloc().

On the other hand, if you wanted to have a as a pointer to a malloc()ed
array of that length, then you'd write char (*a)[some_expression] = ...
and then it would be part of the type.

(Side note: There's a separate issue from array type checking here,
namely pointer bounds checking. A pointer to char is really a pointer to
chars within an object consisting of an array of chars, and to check the
validity of pointer use you have to know the lower bound and size of
that array. I'm still working on this problem; for the moment, Q has a
couple of noop type qualifiers specifying those bounds.)

> It may be good programming practice, but this is C, not Pascal. C is expected
> to bend over backwards to do weird stuff that flakey programmers might want
> to do.

Why don't you give an example where requiring the dimensions to be
const restricts the programmer? I see it as more flexible.

---Dan

rschmidt@silver.ucs.indiana.edu (roy schmidt) (05/28/90)

In article <5391@helios.TAMU.EDU> john@stat.tamu.edu (John S. Price) writes:
>In article <ASHERMAN.90May21052525@dino.ulowell.edu> asherman@dino.ulowell.edu (Aaron Sherman) writes:
>>[stuff deleted]
>> C needs variable length arrays. Anything else is just forcing work
>>onto the programmer or the machine or both that should be the compiler's
>>job.
>>			-AJS
>
>But, I ask again, why?  There really isn't a need...
>
Exactly so!  The price we pay for the fantastic flexibility which C
gives us is the burden of doing such tasks ourselves.  Sure, we could
have the compiler do a lot of things, but for each of these, we would
lose the opportunity to do it differently...and that is the essence of
C!  If you are fed up with this, then do it in BASIC!  You can get away
with murder in BASI
-----------------------------------------------------------       ^
Roy Schmidt                 |  #include <disclaimer.h>           | |
Indiana University          |  /* They are _my_ thoughts,        | |
Graduate School of Business |     and you can't have them,      <   >
Bloomington                 |     so there! */                    X
___________________________________________________________       X

brnstnd@stealth.acf.nyu.edu (05/30/90)

In article <3066@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
> In article <12722:May2501:41:2690@stealth.acf.nyu.edu>,
>  brnstnd@stealth.acf.nyu.edu writes:
> > I've tried to shorten this article by replacing flames with the phrase
> > 'Nuff said.
> That's more incendiary than most flames.

Quite right, and I apologize. I was in a bad mood.

As for whether Ada can work with any other language: I accept your
criterion that ``working with'' language X means that ``applications
programmers could call either language from the other, passing a useful
variety of data in either direction, even if not absolutely everything.''

I'm aware of one non-compliant Ada implementation that ``works with'' C,
but I don't know of any compliant implementations that do. You say that
they exist; given the restrictions on what an Ada environment has to be
like, I still find it very difficult to believe you. You could convince
me by very simply naming your evidence.

> > > > > In the presence of dynamic arrays, [whether sizeof X is legal in a
> > > > > static expression is] no longer a simple syntactic test.

By ``simple syntactic test'' I assumed you meant ``simple compile-time
test'': by far the most important issue here is what can be done well by
the compiler, and I thought you were sticking to that. Apparently you
weren't. My new response is ``Who cares? It's still an absolutely
trivial compile-time test.'' (As you admit, it isn't purely syntactic
[type-independent as well as value-independent] for straight C anyway.)

  [ dynamic own array ]

You're perverting the meaning of ``static'' in your example. In C, a
static variable can be allocated, with a fixed size, at compile time.
Dynamic own arrays just don't work that way. They're easy enough to set
up without pretending that they're static, so what's your problem?

> > Real computers have floating-point operations. 'Nuff said.
> Oh dear.  That means that the Sun-3/50 in my office is not a real computer.

Quite right.

> > > > > With specific reference to fwrite(), there are at least three fairly
> > > > > obvious possible complications which I'll not trouble you with.

I challenged you twice to name your ``obvious'' complications. You've
now failed to name them three times. I'd be surprised if you can answer,
because in my Q-to-C translator already supports dynamic arrays (which,
as Chris Torek pointed out many articles ago, are easy to implement),
with a perfectly consistent type structure. It has absolutely no trouble
working with fwrite(), because arrays are implemented as pointers.

> If someone _else_ would like to
> know what the problems are, ask, and I'll hand out the model answers.

Grow up.

> > > Here's another question about dynamic arrays.  Consider
> >   [ void f(int n) { double a[n]; int m = g(n); double b[m]; ... } ]
> > Better stated:
> >   void f(const int n)
> >   { double a[n]; int m; m = g(n); { const int x = m; { double b[x] ...
> That's not "better stated".  That's **RE**stated, as in CHANGED.
> There were two significant features about the way I formulated the
> question:  m was *NOT* const, and the declarations were in one group.

m is not const in the new version either, and the placement of
declarations into ``groups'' is for purely syntactic reasons. How are
these significant?

Are you complaining that b's dimension (which is now x, not m) is forced
to be const? That's how dynamic arrays work in Q. That's what scientific
programmers want for variable-sized arrays. How is this ``restriction''
significant?

Anyway, your question was how the compiler would allocate the arrays,
and neither of those ``significant features'' invalidates my answer.

    [ how things are allocated ]
> Yes, but *where* is b[] allocated?
  [ in straight C, offsets are known at compile time ]

I'd expect it to be allocated in the frame, though of course internal
behavior isn't standardized. Offsets not known at compile time do hurt
efficiency, and can seriously impair certain types of optimization; but
they're not fundamentally harder to compile.

> The simplest answer is to make dynamic arrays pointers,

There's no reason an implementation can't do that, and that's what q2c
does.

> However, a 'goto' leading out of a block
> gets complicated.

I agree. Q's implementation doesn't have gotos at the moment, partially
because I can't easily define their syntax or semantics, partially
because I've found no use for them given flexible breaks and exceptions,
and partially because I just haven't bothered. Anyway, if someone breaks
from a block that has something allocated, he'll typically go through a
break handler that deallocates the object. This applies to your example,
with the goto replaced by an appropriate break.

Your example of allocating an array[i] inside a switch(i) would be
handled the same way. (Though i would have to be const, and a smart
compiler might take advantage of this.)

> 	int m = f();
> 	int (*a)[m] = malloc(sizeof a);

Assuming m const... a is a pointer to an m-sized integer array. You're
initializing it to equal a pointer to an object of pointer size? What
are you trying to do here?

---Dan

peter@ficc.ferranti.com (Peter da Silva) (05/30/90)

In article <1376:May2720:09:0690@stealth.acf.nyu.edu> brnstnd@stealth.acf.nyu.edu (Dan Bernstein) writes:
> How do you expect it to figure that out?

I can ask you the same question.

In my case, it's just an optimisation. In your case, it's needed to even
generate legal code. Think of the possibilities for hidden bugs!

> And once m and n do change,
> where do you think it's going to store the original values?

Up to the compiler writer. There are a number of possibilities. It's like
structure passing/returning.

> Why not let the programmer have control over those values?

Why not let the programmer have control over these variables?

> 
> > struct _point { int x, y };
> > foo(box) struct point box[2]; {
> > 	char tmp[box[1].x - box[0].x][box[1].y - box[0].y];
> > 	bar(box, tmp); print(box, tmp); }
> > How do you guarantee that box is constant? In general, you can't.

> Q requires that array dimensions be const (i.e., unvarying within their
> scope, lifetime, whatever). Given box declared const, the answer is
> ``yes, you can.'' const filters down through function invocations: if
> bar were to change box, then it couldn't declare box constant in the
> function declaration, so bar(box,tmp) (rather, bar(&box,&tmp), because Q
> treats arrays differently) wouldn't be valid.

> This all makes perfect sense. What are you objecting to?

Now the compiler has to mark all the variables in those expressions const
as well? Or require that?

What if "box" is an extern?

What if the expression evaluation requires a function call? (say, using
object oriented techniques.

There are only two alternatives that I see that make sense.

The compiler squirrels the dimensions away.

The dimensions are const auto integer variables, autoinitialised before
the declaration of the array if they're not formal parameters.

> Why don't you give an example where requiring the dimensions to be
> const restricts the programmer? I see it as more flexible.

You can't use a function or an external variable in deriving the
dimensions. None of the variables involved can be aliased.
-- 
`-_-' Peter da Silva. +1 713 274 5180.  <peter@ficc.ferranti.com>
 'U`  Have you hugged your wolf today?  <peter@sugar.hackercorp.com>
@FIN  Dirty words: Zhghnyyl erphefvir vayvar shapgvbaf.