traversing a stack

Discussion in 'C Programming' started by asit, Dec 1, 2007.

  1. asit

    asit Guest

    We kno that data can be pushed onto the stack or popped 4m it. Can
    stack be traversed ??
    asit, Dec 1, 2007
    #1
    1. Advertising

  2. asit

    santosh Guest

    asit wrote:

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


    C3rt41n1y.
    santosh, Dec 1, 2007
    #2
    1. Advertising

  3. asit

    Flash Gordon Guest

    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.
    --
    Flash Gordon
    Flash Gordon, Dec 1, 2007
    #3
  4. asit

    ravi Guest

    On Dec 1, 8:01 pm, asit <> wrote:
    > 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
    ravi, Dec 1, 2007
    #4
  5. asit

    Tor Rustad Guest

    asit wrote:
    > 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?

    --
    Tor < | tr i-za-h a-z>
    Tor Rustad, Dec 2, 2007
    #5
  6. asit

    CBFalconer Guest

    Tor Rustad wrote:
    > asit wrote:
    >
    >> 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?


    Just in case this is a serious question, none.

    --
    Chuck F (cbfalconer at maineline dot net)
    <http://cbfalconer.home.att.net>
    Try the download section.



    --
    Posted via a free Usenet account from http://www.teranews.com
    CBFalconer, Dec 2, 2007
    #6
  7. asit

    jacob navia Guest

    CBFalconer wrote:
    > Tor Rustad wrote:
    >> asit wrote:
    >>
    >>> 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?

    >
    > 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.



    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
    jacob navia, Dec 2, 2007
    #7
  8. asit

    santosh Guest

    jacob navia wrote:

    > CBFalconer wrote:
    >> Tor Rustad wrote:
    >>> asit wrote:
    >>>
    >>>> 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?

    >>
    >> 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.


    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.
    santosh, Dec 2, 2007
    #8
  9. asit

    Richard Guest

    santosh <> writes:

    > jacob navia wrote:
    >
    >> CBFalconer wrote:
    >>> Tor Rustad wrote:
    >>>> asit wrote:
    >>>>
    >>>>> 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?
    >>>
    >>> 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.

    >
    > 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.
    Richard, Dec 2, 2007
    #9
  10. asit

    jacob navia Guest

    Richard wrote:
    > santosh <> writes:
    >
    >> jacob navia wrote:
    >>
    >>> CBFalconer wrote:
    >>>> Tor Rustad wrote:
    >>>>> asit wrote:
    >>>>>
    >>>>>> 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?
    >>>> 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.

    >> 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.


    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!


    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
    jacob navia, Dec 2, 2007
    #10
  11. asit

    CBFalconer Guest

    jacob navia wrote:
    > CBFalconer wrote:
    >> Tor Rustad wrote:
    >>> asit wrote:
    >>>
    >>>> 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?

    >>
    >> 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.


    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.

    --
    Chuck F (cbfalconer at maineline dot net)
    <http://cbfalconer.home.att.net>
    Try the download section.


    --
    Posted via a free Usenet account from http://www.teranews.com
    CBFalconer, Dec 2, 2007
    #11
  12. santosh <> writes:
    > jacob navia wrote:
    >> CBFalconer wrote:
    >>> Tor Rustad wrote:
    >>>> asit wrote:
    >>>>> 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?
    >>>
    >>> 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.

    >
    > 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 (The_Other_Keith) <>
    Looking for software development work in the San Diego area.
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Dec 2, 2007
    #12
  13. jacob navia <> writes:
    [...]
    > 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?

    --
    Keith Thompson (The_Other_Keith) <>
    Looking for software development work in the San Diego area.
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Dec 2, 2007
    #13
  14. asit

    Flash Gordon Guest

    jacob navia wrote, On 02/12/07 14:04:
    > Richard wrote:
    >> santosh <> writes:
    >>
    >>> jacob navia wrote:
    >>>
    >>>> CBFalconer wrote:
    >>>>> Tor Rustad wrote:
    >>>>>> asit wrote:


    <snip does C have a stack?>

    >>> 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.

    >
    > 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


    <snip>

    > 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!
    --
    Flash Gordon
    Flash Gordon, Dec 2, 2007
    #14
  15. asit

    Ben Pfaff Guest

    Flash Gordon <> writes:

    > 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'.

    --
    char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
    ={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa67f6aaa,0xaa9aa9f6,0x11f6},*p
    =b,i=24;for(;p+=!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
    2:{i++;if(i)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}
    Ben Pfaff, Dec 2, 2007
    #15
  16. asit

    Joe Wright Guest

    ravi wrote:
    > On Dec 1, 8:01 pm, asit <> wrote:
    >> 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


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

    --
    Joe Wright
    "Everything should be made as simple as possible, but not simpler."
    --- Albert Einstein ---
    Joe Wright, Dec 2, 2007
    #16
  17. Joe Wright <> writes:
    > ravi wrote:
    >> On Dec 1, 8:01 pm, asit <> wrote:
    >>> 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

    >
    > 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.

    --
    Keith Thompson (The_Other_Keith) <>
    Looking for software development work in the San Diego area.
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Dec 2, 2007
    #17
  18. jacob navia wrote:

    > 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.
    Mark McIntyre, Dec 3, 2007
    #18
  19. Mark McIntyre <> writes:
    > 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.

    --
    Keith Thompson (The_Other_Keith) <>
    Looking for software development work in the San Diego area.
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Dec 3, 2007
    #19
  20. asit

    jacob navia Guest

    Mark McIntyre wrote:
    > jacob navia wrote:
    >
    >> 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.
    >


    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>



    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
    jacob navia, Dec 3, 2007
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Surinder Singh
    Replies:
    1
    Views:
    1,181
    Richard Bos
    Dec 20, 2007
  2. Casey Hawthorne
    Replies:
    3
    Views:
    1,070
    Flash Gordon
    Nov 1, 2009
  3. Debajit Adhikary
    Replies:
    36
    Views:
    2,258
    Andre Kaufmann
    Feb 10, 2011
  4. Sam Roberts
    Replies:
    1
    Views:
    216
    Yukihiro Matsumoto
    Feb 11, 2005
  5. Kenneth McDonald

    Why stack overflow with such a small stack?

    Kenneth McDonald, Aug 30, 2007, in forum: Ruby
    Replies:
    7
    Views:
    251
    Kenneth McDonald
    Sep 1, 2007
Loading...

Share This Page