traversing a stack

[asit]

We kno that data can be pushed onto the stack or popped 4m it. Can
stack be traversed ??

 

[santosh]

We kno that data can be pushed onto the stack or popped 4m it. Can
stack be traversed ??

C3rt41n1y.

 

[Flash Gordon]

asit wrote, On 01/12/07 15:01:

We kno that data can be pushed onto the stack or popped 4m it.

Do we? Which stack would that be anyway? The return address stack built
in to the processor or a stack implemented using one of the normal index
registers? Or possibly a stack implemented as a data structure in C?

Can
stack be traversed ??

If your C implementation uses a stack for auto variables and/or return
addresses (which not all do, although they use something that implements
similar semantics) then the answer is it depends, but not in portable C.
If you mean a stack data structure implemented in C then the answer is
it depends.

 

[ravi]

We kno that data can be pushed onto the stack or popped 4m it. Can
stack be traversed ??

yes stack can be traversed whether it is in static or dynamic memory
allocation
if it is static implementation using arrays then it can be traversed
by simply for loop as in case of arrays
or if it is in dynamic or linked list repesentation it can be
traversed by setting a pointer to the top and then traversing address
of the next pointer until its null

 

[Tor Rustad]

We kno that data can be pushed onto the stack or popped 4m it. Can
stack be traversed ??

What stack does the abstract C machine have?

 

[CBFalconer]

What stack does the abstract C machine have?

Just in case this is a serious question, none.

 

[jacob navia]

Just in case this is a serious question, none.

This is wrong.

When a function is called, the value of the local variables is no longer
active and is preserved until the called function returns.

When the called function returns, the local variables are reactivated.
If this is not a stack, I do not know what a stack is...

A function call is a push into this stack, a function return is
a pop.

 

[santosh]

This is wrong.

When a function is called, the value of the local variables is no
longer active and is preserved until the called function returns.

When the called function returns, the local variables are reactivated.
If this is not a stack, I do not know what a stack is...

A function call is a push into this stack, a function return is
a pop.

As K and R themselves note, the function call and return mechanism in C
impose a stack like discipline on local variables, but this feature
need not actually be implemented with a stack (hardware or otherwise).
You could do the same with data structures based on dynamically
allocated memory too (heap), but it would be cumbersome and warranted
only when a stack will not work.

I would guess that no actual implementation of C has ever done it this
way, but the Standard doesn't forbid it and hence does not mandate a
stack.

 

[Richard]

As K and R themselves note, the function call and return mechanism in C
impose a stack like discipline on local variables, but this feature
need not actually be implemented with a stack (hardware or otherwise).
You could do the same with data structures based on dynamically
allocated memory too (heap), but it would be cumbersome and warranted
only when a stack will not work.

This would still be a "stack" in the algorithmic sense.

This ridiculous "we dont do stack" view is nothing short of silly word
games. And I will continue to think that until someone proves to me that
the variable behaviour you describe is not "stack like" behaviour in C.

I would guess that no actual implementation of C has ever done it this
way, but the Standard doesn't forbid it and hence does not mandate a
stack.

It is still a stack IMO.

 

[jacob navia]

This would still be a "stack" in the algorithmic sense.

This ridiculous "we dont do stack" view is nothing short of silly word
games. And I will continue to think that until someone proves to me that
the variable behaviour you describe is not "stack like" behaviour in C.


It is still a stack IMO.

Of course it is a stack. The standard doesn't mandate a stack because
everybody knows what a stack is, and uses a stack. The standard doesn't
write

2+2 -->4
or
sqrt(25) --> 5

or whatever.

There are things that are self evident except for some people here that
like to confuse beginners when they ask a question.

"There is no stack in C".

The only objective with this answer is to confuse people.


And nobody here (nor the OP) is speaking about a hardware stack. It is
conceptually a stack!

 

[CBFalconer]

This is wrong.
When a function is called, the value of the local variables is no
longer active and is preserved until the called function returns.

Wrong. The variables remain in active existence. To reach them, a
pointer needs to be passed to the called routine. In better
designed languages, such as Pascal and Ada, the passed pointer is
not required.

 

[Keith Thompson]

As K and R themselves note, the function call and return mechanism in C
impose a stack like discipline on local variables, but this feature
need not actually be implemented with a stack (hardware or otherwise).
You could do the same with data structures based on dynamically
allocated memory too (heap), but it would be cumbersome and warranted
only when a stack will not work.

I would guess that no actual implementation of C has ever done it this
way, but the Standard doesn't forbid it and hence does not mandate a
stack.

Once again, we're talking at cross purposes, seeming to disagree about
whether C requires a stack while actually just using the word "stack"
in two different ways.

Clearly, C requires some sort of stack-like last-in/first-out data
structure to manage function calls. Regardless of how this is
implemented, it's a "stack".

Equally clearly, C does not require a "hardware stack", a region of
memory that grows and shrinks contiguously, with the top indicated by
a "stack pointer", typically a dedicated CPU register. And there are
real-world implementations (on IBM mainframes, I think) whose "stack"
(in the abstract data structure sense) is not implemented by
contiguous hardware stack, but by the equivalent of a heap-allocated
linked list.

CBFalconer is entirely correct if he's using the word "stack" in the
sense of a hardware stack, but he probably should have been clearer
that he wasn't referring to a "hardware stack". jacob is also correct
if he's using the word "stack" only in the sense of the abstract data
structure, but he ignores the other meaning of the word.

I don't think we know which kind of stack the original poster was
referring to; he didn't give us enough information. His use of the
phrase "the stack" leads me to suspect that he's talking about a
contiguous hardware stack, but that's only a guess, and there's really
no point in speculating without further information.

asit: Please post again and tell us exactly what you mean. What are
you trying to accomplish?

 

[Keith Thompson]

There are things that are self evident except for some people here that
like to confuse beginners when they ask a question.

"There is no stack in C".

The only objective with this answer is to confuse people.

No the objective is to point out that C doesn't require a *hardware
stack*.

And nobody here (nor the OP) is speaking about a hardware stack. It is
conceptually a stack!

How do you *know* the OP wasn't talking about a hardware stack?

 

[Flash Gordon]

jacob navia wrote, On 02/12/07 14:04:

Of course it is a stack. The standard doesn't mandate a stack because
everybody knows what a stack is, and uses a stack. The standard doesn't
write

There are things that are self evident except for some people here that
like to confuse beginners when they ask a question.

"There is no stack in C".

The only objective with this answer is to confuse people.

No, the objective is to make people understand what is and is not
guaranteed by the C language.

And nobody here (nor the OP) is speaking about a hardware stack. It is
conceptually a stack!

It could be multiple stacks, the most likely being one stack for return
addresses and a separate stack for parameters and locals (possibly a
third stack for floating points to take advantage of floating point
hardware) so talking about "the stack" can be misleading. The reason for
separate return address and parameter/variable stacks should be obvious.
Note that one processor I used to use did have a HW stack specifically
for return addresses, although as it was only 8 deep entries did have to
be pulled on to it and dumped else where, but NOT if the compiler could
prove the call depth would not exceed 8 (generally on a stack
implemented using one of the index registers, although that index
register was not as far as the processor was concerned a stack pointer).

I actually agree that some of the time some people go too far on this,
since obviously whatever is used is behaving in a stack like manner, and
for anyone who knows what a stack is it is an easy way to understand
what is happening.

As an unrelated note, the compiler manual also contains the following,
"The TMS320C2x/C2xx/C5x produces a 32-bit result even when 16-bit values
are used as data operands; thus, arithmetic overflow and underflow
cannot be handled in a predictable manner. If code depends on a
particular type of over-flow/underflow handling, there is no assurance
that this code will execute correctly. Generally, it is a good practice
to avoid such code because it is not portable." So we have an example of
a C compiler where arithmetic overflow/underflow is explicitly
documented by the compiler as producing unexpected and unpredictable
results!

 

[Ben Pfaff]

So we have an example of a C compiler where arithmetic
overflow/underflow is explicitly documented by the compiler as
producing unexpected and unpredictable results!

GCC also documents this:

`-fstrict-overflow'
Allow the compiler to assume strict signed overflow rules,
depending on the language being compiled. For C (and C++) this
means that overflow when doing arithmetic with signed numbers is
undefined, which means that the compiler may assume that it will
not happen. This permits various optimizations. For example, the
compiler will assume that an expression like `i + 10 > i' will
always be true for signed `i'. This assumption is only valid if
signed overflow is undefined, as the expression is false if `i +
10' overflows when using twos complement arithmetic. When this
option is in effect any attempt to determine whether an operation
on signed numbers will overflow must be written carefully to not
actually involve overflow.

See also the `-fwrapv' option. Using `-fwrapv' means that signed
overflow is fully defined: it wraps. When `-fwrapv' is used,
there is no difference between `-fstrict-overflow' and
`-fno-strict-overflow'. With `-fwrapv' certain types of overflow
are permitted. For example, if the compiler gets an overflow when
doing arithmetic on constants, the overflowed value can still be
used with `-fwrapv', but not otherwise.

The `-fstrict-overflow' option is enabled at levels `-O2', `-O3',
`-Os'.

 

[Joe Wright]

yes stack can be traversed whether it is in static or dynamic memory
allocation
if it is static implementation using arrays then it can be traversed
by simply for loop as in case of arrays
or if it is in dynamic or linked list repesentation it can be
traversed by setting a pointer to the top and then traversing address
of the next pointer until its null

No. There is no 'stack', dynamic or otherwise, in C.

 

[Keith Thompson]

No. There is no 'stack', dynamic or otherwise, in C.

That's quite correct given one common and useful definition of the
word "stack" (i.e., a contiguous hardware stack). (But even given
that definition, it should be made clear that although the C standard
doesn't require this kind of stack, it's certainly an allowed and
quite common implementation choice; saying "There is no 'stack'" could
easily obscure that point.)

It's quite incorrect given another common and useful definition of the
word "stack" (i.e., the abstract data structure).

I suggest that your response is therefore incomplete and potentially
misleading. See my followup elsewhere in this thread for details.

 

[Mark McIntyre]

Of course it is a stack. The standard doesn't mandate a stack because
everybody knows what a stack is, and uses a stack.

No. The standard doesn't mandate a stack because C can be, and has been,
implemented on machines which don't use a stack. For example, the
PowerPC annd Sparc chips have so many registers that function parameters
are passed through these.

Note that within computer programming, "the stack" has a specific
meaning, and does not apply to general purpose software stacks
implemented by the programmer.

"There is no stack in C".

The only objective with this answer is to confuse people.

Bollocks. The objective is to free people from the mistaken belief that
C requires a stack.

 

[Keith Thompson]

jacob navia wrote: [...]

"There is no stack in C".

The only objective with this answer is to confuse people.

Bollocks. The objective is to free people from the mistaken belief
that C requires a stack.

The objective *should* be to help people understand that the word
"stack" has more than one meaning. Since the C standard doesn't
happen to define, or even use, the word "stack", we should make the
meaning clear when we talk about "stacks" here. Assuming that only
one meaning is relevant and deliberately ignoring the other, as both
Mark and jacob have been doing, is not helpful. (Though I don't
believe for a moment that either of you has the objective of confusing
people.)

The OP didn't give us enough information to be sure what he meant by
the word "stack". Until he does so, this discussion is not useful in
answering the OP's question.

 

[jacob navia]

No. The standard doesn't mandate a stack because C can be, and has been,
implemented on machines which don't use a stack. For example, the
PowerPC annd Sparc chips have so many registers that function parameters
are passed through these.

Yeah of course. Like windows 64, like linux 64 in the AMD chips...

You are telling NONSENSE. The power PC architecture has a dedicated
stack register! (Register 1)

In non AIX architectures it could be another register but
ALL of them have a hardware stack.

Note that within computer programming, "the stack" has a specific
meaning, and does not apply to general purpose software stacks
implemented by the programmer.

It is interesting that you leave out the sentence from my
message where I say:

<quote>
And nobody here (nor the OP) is speaking about a hardware stack. It is
conceptually a stack!
<end quote>