Re: ++i vs i++

From: John Bode (john_bode_at_my-deja.com)
Date: 10/01/04 

Date: 1 Oct 2004 14:45:01 -0700

"Malcolm" <malcolm@55bank.freeserve.co.uk> wrote in message news:<cjhng8$27n$1@newsg4.svr.pol.co.uk>...
> "John Bode" <john_bode@my-deja.com> wrote
> >
> > Didn't you just say that evidence isn't proof?
> >
> > This is priceless. The bug had *** all to do with the preincrement
> > operator; like Michael pointed out, the same UB would have shown up if
> > I hadn't used the preincrement. The root cause of the bug is that C
> > arrays are 0-origin (and that I wasn't paying close enough attention).
> >
> Here's the code
>
> added by Malcolm
>
> int stack[STACK_SIZE];
> int sp;
>
> > if (sp < STACK_SIZE)
> > {
> > /*
> > ** The following statement replaces these two statements
> > **
> > ** sp = sp + 1;
> > ** stack[sp] = value;
> > */
> > stack[++sp] = value;
> > }
> > else
> > {
> > /* handle overflow */
> > }
> >
> Seems to me quite clearly that the pre-increment is contributing to the
> problem.

What if I had written

if (sp < STACK_SIZE)
{
    sp = sp + 1;
    stack[sp] = value;
}

The pre-increment operator is nowhere in sight, yet the bug is still
there. It seems to me that the problem is in the test (actually, the
problem's in the overall logic; more on that below).

> On entry, sp < STACK_SIZE, so writing "stack[sp++] = value;" would
> give you the right behaviour, at the price of making sp no longer pointing
> to stack top but to the empty space above it.

Which is not what I want sp to do. I want sp to point to the last
thing pushed onto the stack, not the next available slot.

Actually, now that I've thought about it, the *right* solution is to
grow from the top down:

static int sp = STACK_SIZE;

void push (int value)
{
    if (sp > 0)
        stack[--sp] = value;
    else
        /* overflow */
}

int pop (void)
{
    if (sp < STACK_SIZE)
        return stack[sp++];
    else
        /* underflow */
}

A little cleaner, and all array elements actually get used. Like I
said, I tossed off the original example while waiting for something
else to finish and didn't verify it properly. Bad me. No cookie.

> >
> > > However programmers make errors all of the time.
> >
> However we all make mistakes, so to conclude that pre-increment is confusing
> on the basis of one bug is a bit premature. To conclude that it is not
> confusing (evidence isn't proof, therefore evidence that falls short of
> proof is evidence against) is a fallacy.
> >
> > The maximum stack size is a *logical* entity; there's no reason why
> > the physical implementation has to be the same size. In fact, the way
> > I wrote it, the array *has* to be STACK_SIZE+1 elements to hold
> > STACK_SIZE items, because element 0 is never written to.
> >
> You're in good company here. No less than the authors of "Numerical Recipies
> in C" endorse 1-based arrays. Mathematicians count 1, 2, 3 ..., computers
> count 0, 1, 2 ... . However the consensus is that 1-based arrays in C are a
> bad idea.

I don't *endorse* the idea of 1-based arrays in C. I was merely
pointing out that the bug in my code was due to not taking 0-origin
arrays into account, not because I used a preincrement operator.
Since the bug still exists if I replace the preincrement with a
separate increment statement, I'd say my point is valid.

And my *actual* point was that the physical and logical
representations of a stack didn't have to map exactly.