traversing a stack

[RoS]

In data Mon, 03 Dec 2007 00:06:33 +0000, Mark McIntyre scrisse:

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.

i think the above is not true for recursive functions

 

[Ian Collins]

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.

Only as many parameters as there are input/output registers, beyond
that, the stack is used (at least for Sparc and probably PPC versions
with a finite number of registers).

 

[Richard Tobin]

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.

Of course they use a stack. Where do you think they put large local
arrays?

Anyway, those registers are effectively just a cache of the top of the
stack. if you recurse deeply enough, the registers will be written
out to memory. Or to look at it another way, part of the stack is in
registers. There's still a stack.

-- Richard

 

[James Fang]

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

If you mean the stack data structure, it of course can be tranversed,
the way to tranverse the stack depends on the stack implementation.

If you mean the stack supported by the push/pop commands of the
processor and managed by the OS, it can also be tranversed with ease,
but you have to know sth about the internal operating system data
structure and compiler impl.

 

[James Fang]

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

Anyway, the stack-tranversing-operation is not defined in the standard
stack interface.If you need to tranverse a stack data structure, the
platform independent method is as follows:

You need one additional stack for temporary storage of the stack
elements.

void tranverseStack(struct Stack* pStack,void (*TRANVERSE)(void*))
{
void *pElem;
struct Stack local_stack;
while( NULL != (pElem=pStack->pop()) )
{
TRANVERSE(pElem);
local_stack.push(pElem);
}
while( NULL != (pElem=local_stack.pop()) )
{
pStack->push(pElem);
}
}


Thanks and Regards,
James Fang

 

[Tor Rustad]

jacob navia wrote:

[...]

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>

Nonsense.

Most C programs does not have any recursive function calls, also MISRA C
ban such functions. In case there are no recursive calls, the translator
don't need a stack for the return address. Storage for local objects can
be allocated in global area, at fixed addresses known at link-time.

The function call tree, can be used to identify which function life
times are mutually exclusive, hence storage of object with automatic
storage duration, can be overlaid.

This is not just some theoretical observation, but can be expected in
real world C implementations. For example, when targeting the Intel 8051
(only a 128 byte stack), make such an approach quite interesting.

 

[Richard Harter]

jacob navia wrote:

[...]

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>

Nonsense.

Most C programs does not have any recursive function calls, also MISRA C
ban such functions. In case there are no recursive calls, the translator
don't need a stack for the return address. Storage for local objects can
be allocated in global area, at fixed addresses known at link-time.

The function call tree, can be used to identify which function life
times are mutually exclusive, hence storage of object with automatic
storage duration, can be overlaid.

This is not just some theoretical observation, but can be expected in
real world C implementations. For example, when targeting the Intel 8051
(only a 128 byte stack), make such an approach quite interesting.

You're missing the point. It doesn't matter where the storage
for is; the pattern of usage is that of an abstract stack.




Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die

 

[Richard]

jacob navia wrote:

[...]

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>

Nonsense.

Most C programs does not have any recursive function calls, also MISRA
C ban such functions. In case there are no recursive calls, the
translator don't need a stack for the return address. Storage for
local objects can be allocated in global area, at fixed addresses
known at link-time.

The function call tree, can be used to identify which function life
times are mutually exclusive, hence storage of object with automatic
storage duration, can be overlaid.

This is not just some theoretical observation, but can be expected in
real world C implementations. For example, when targeting the Intel
8051 (only a 128 byte stack), make such an approach quite interesting.

Which part of "conceptually" do you not understand? Does the whole
idea of call stack (call tree...) go out of the window? The storage
method is immaterial. The concept is still that of an abstract stack.

 

[Walter Roberson]

Which part of "conceptually" do you not understand? Does the whole
idea of call stack (call tree...) go out of the window? The storage
method is immaterial. The concept is still that of an abstract stack.

Oh, *conceptually*. Well, *conceptually* it is really four enormous
elephants riding on the back of a turtle that is swimming through
space. If it isn't immediately clear why so, then the secret is to
"Bang the rocks together, guys".

 

[Tor Rustad]

Richard Harter wrote:

[...]

You're missing the point.

If not context here was "traversing a stack", I must indeed be missing
something.

> It doesn't matter where the storage
for is; the pattern of usage is that of an abstract stack.

Since when, was traversing overlaid memory similar to traversing a stack?

In particular, I recommend that you give some thought to where the
function return address could be, before considering how to pop it.

As it turns out, the abstract C machine has no requirement for
implementations to use a "stack", and a search for the word "stack" in
the C standard, gave me nada... zero.

The *relevant point* is that translators can take advantage of this, and
use overlaid memory (in some cases), which is a highly relevant point in
the context of traversing such a memory arena, while "usage pattern" is
not.

 

[Richard Harter]

Richard Harter wrote:

[...]

You're missing the point.

If not context here was "traversing a stack", I must indeed be missing
something.

The title is "traversing a stack" - the context is something
else.

The immediate question at hand is whether the function
call/return semantics in C are an instance of the abstract data
type, stack. Quite simply, they are; flow control and automatic
storage are LIFO.

In fact, if they weren't you couldn't use a hardware stack to
implement C.

Since when, was traversing overlaid memory similar to traversing a stack?

In particular, I recommend that you give some thought to where the
function return address could be, before considering how to pop it.

It doesn't matter.

As it turns out, the abstract C machine has no requirement for
implementations to use a "stack", and a search for the word "stack" in
the C standard, gave me nada... zero.

Irrelevant.

The *relevant point* is that translators can take advantage of this, and
use overlaid memory (in some cases), which is a highly relevant point in
the context of traversing such a memory arena, while "usage pattern" is
not.

Much like the chap who spoke prose all of his life and didn't
know it, you've been using a stack all of this time and don't
know it.



Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
The good news is that things could be worse; the bad
news is that things aren't as good as they should be.

 

[Tor Rustad]

Richard Harter wrote:

[...]

You're missing the point.

If not context here was "traversing a stack", I must indeed be missing
something.

The title is "traversing a stack" - the context is something
else.

I advice you to read posts more carefully within context in the future,
particularly when responding to an originator of a sub-thread.

 

[Mark McIntyre]

Of course they use a stack. Where do you think they put large local
arrays?

a) We snipped too much context. The point was being made in relation to
function parameters, not local variables.

b) I've no idea. But note that no stack is *necessary* to store local
variables.

Anyway, those registers are effectively just a cache of the top of the
stack.

Eh? Registers are hardware locations.

 

[Richard Harter]

Richard Harter wrote:

[...]

You're missing the point.
If not context here was "traversing a stack", I must indeed be missing
something.

The title is "traversing a stack" - the context is something
else.

I advice you to read posts more carefully within context in the future,
particularly when responding to an originator of a sub-thread.

Practice what you preach.


Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
The good news is that things could be worse; the bad
news is that things aren't as good as they should be.

 

[David Thompson]

jacob navia wrote:

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.

They continue to exist and may be accessed, yes.

Nothing needs to be passed if, and only if, the called routine is
nested (directly or indirectly) within the routine, or module or
package respectively, whose local/private(s) it wants to access.
And there is not a more-local declaration of the same name(s).

Anywhere else, you do need to pass something. In Pascal (always) and
Ada (usually) this can be a reference parameter so what you pass isn't
_written as_ a pointer, but in fact is one under the covers.

I hope you meant the former, as the latter is mostly sophistry.

- formerly david.thompson1 || achar(64) || worldnet.att.net

 

[CBFalconer]

They continue to exist and may be accessed, yes.

Nothing needs to be passed if, and only if, the called routine is
nested (directly or indirectly) within the routine, or module or
package respectively, whose local/private(s) it wants to access.
And there is not a more-local declaration of the same name(s).

This is c.l.c. There are NO nested routines in C. NONE. Illegal.

 

[Richard Harter]

This is c.l.c. There are NO nested routines in C. NONE. Illegal.

Perhaps you should address your comments to CBFalconer, the
person who brought up "in better designed languages".

 

[CBFalconer]

Perhaps you should address your comments to CBFalconer, the
person who brought up "in better designed languages".

Err - I suggest you read the attributions. My last comment was
about nested functions.

 

[Richard Heathfield]

CBFalconer said:

Err - I suggest you read the attributions. My last comment was
about nested functions.

Err - I suggest you read closely the material that Richard Harter quoted,
because it contained an earlier comment from *you*, regarding "better
designed languages".

Richard Harter's point is that, since *you* introduced the discussion of
"better designed languages", you have no justification for playing
topic-cop when other people then discuss those "better designed languages"
- you can't switch topicality on and off when it suits you, any more than
you can change netiquette rules to sui... er, never mind.

 

[CBFalconer]

CBFalconer said:

Err - I suggest you read closely the material that Richard Harter
quoted, because it contained an earlier comment from *you*,
regarding "better designed languages".

Err - he directed his comment to 'you', who is the author of the
material with '>>>' quotes above, and turns out to be me. And yes,
I did earlier, in a separate message, mention "better designed
languages". And finally, this is not worth wasting electrons
over. Out.